# Large Scale Graph Learning from Smooth Signals

Source: [Large Scale Graph Learning from Smooth Signals](<https://www.sota2.com/research/paper/68fa65a81e209131cea0baba>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T21:32:37.817Z

Authors: Vassilis Kalofolias, Nathana\\"el Perraudin

Published: 2017-10-16T12:42:15.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Edge Recovery on SBG 32 graphs, 20 win. size (test)](<https://www.sota2.com/research/sota/edge-recovery-on-sbg-32-graphs-20-win-size-test.md>): Edge Recovery; SBG 32 graphs, 20 win. size (test); MCC: 33.6.

- [Edge Recovery on EMEG 512 graphs, 1 win. size (test)](<https://www.sota2.com/research/sota/edge-recovery-on-emeg-512-graphs-1-win-size-test.md>): Edge Recovery; EMEG 512 graphs, 1 win. size (test); MCC: 36.

- [Edge Recovery on SBG 512 graphs, 1 win. size (test)](<https://www.sota2.com/research/sota/edge-recovery-on-sbg-512-graphs-1-win-size-test.md>): Edge Recovery; SBG 512 graphs, 1 win. size (test); MCC: 28.6.

- [Edge Recovery on EMEG 32 graphs, 20 win. size (test)](<https://www.sota2.com/research/sota/edge-recovery-on-emeg-32-graphs-20-win-size-test.md>): Edge Recovery; EMEG 32 graphs, 20 win. size (test); MCC: 37.7.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1710.05654>)

[PDF](<https://arxiv.org/pdf/1710.05654.pdf>)