232446
20190507143834.0
CONF
Large Scale Graph Learning from Smooth Signals
2017
2017
Conference Papers
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 O(n^2) for n samples. In this paper, we show how to scale it, obtaining an approximation with leading cost of 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.
Graphs
Graph learning
Machine learning
Unsupervised learning
Algorithm
Large scale
246432
Kalofolias, Vassilis
211494
Perraudin, NathanaĆ«l
2098452
http://infoscience.epfl.ch/record/232446/files/large_scale_graph_learning.pdf
Preprint
Preprint
252392
LTS2
U10380
oai:infoscience.tind.io:232446
conf
STI
GLOBAL_SET
179669
EPFL-CONF-232446
EPFL
REVIEWED
SUBMITTED
CONF