  Graphs are a prevalent tool in data science, as they model the inherent
structure of the data. They have been used successfully in unsupervised and
semi-supervised learning. Typically they are constructed either by connecting
nearest samples, or by learning them from data, solving an optimization
problem. While graph learning does achieve a better quality, it also comes with
a higher computational cost. In particular, the current state-of-the-art model
cost is $\mathcal{O}(n^2)$ for $n$ samples. In this paper, we show how to scale
it, obtaining an approximation with leading cost of $\mathcal{O}(n\log(n))$,
with quality that approaches the exact graph learning model. Our algorithm uses
known approximate nearest neighbor techniques to reduce the number of
variables, and automatically selects the correct parameters of the model,
requiring a single intuitive input: the desired edge density.
