# Large Scale Graph Learning from Smooth Signals

arXiv: https://arxiv.org/abs/1710.05654 · HTML: https://mlsanity.com/paper/1710.05654/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2017.

## Built on by (most cited first, 27 of 27)

- [Accelerated Graph Learning from Smooth Signals](https://mlsanity.com/paper/2110.09677/) (2021)
- [GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networks](https://mlsanity.com/paper/2201.12741/) (2022)
- [Online Graph Learning under Smoothness Priors](https://mlsanity.com/paper/2103.03762/) (2021)
- [Bag Graph: Multiple Instance Learning using Bayesian Graph Neural Networks](https://mlsanity.com/paper/2202.11132/) (2022)
- [Sparse Graph Learning Under Laplacian-Related Constraints](https://mlsanity.com/paper/2111.08161/) (2021)
- [A Markov Random Field model for Hypergraph-based Machine Learning](https://mlsanity.com/paper/2308.14172/) (2023)
- [Hypergraph-MLP: Learning on Hypergraphs without Message Passing](https://mlsanity.com/paper/2312.09778/) (2023)
- [Distributionally Robust Graph Learning from Smooth Signals under Moment Uncertainty](https://mlsanity.com/paper/2105.05458/) (2021)
- [Learning Sparse Graphs via Majorization-Minimization for Smooth Node Signals](https://mlsanity.com/paper/2202.02815/) (2022)
- [Node Copying: A Random Graph Model for Effective Graph Sampling](https://mlsanity.com/paper/2208.02435/) (2022)
- [SAGMAN: Stability Analysis of Graph Neural Networks on the Manifolds](https://mlsanity.com/paper/2402.08653/) (2024)
- [Graph Laplacian Learning with Exponential Family Noise](https://mlsanity.com/paper/2306.08201/) (2023)
- [A Unified Framework for Fair Spectral Clustering With Effective Graph Learning](https://mlsanity.com/paper/2311.13766/) (2023)
- [Optimizing k in kNN Graphs with Graph Learning Perspective](https://mlsanity.com/paper/2401.08245/) (2024)
- [Distributed Graph Learning with Smooth Data Priors](https://mlsanity.com/paper/2112.05887/) (2021)
- [SF-SGL: Solver-Free Spectral Graph Learning from Linear Measurements](https://mlsanity.com/paper/2302.04384/) (2023)
- [Joint Graph Learning and Model Fitting in Laplacian Regularized Stratified Models](https://mlsanity.com/paper/2305.02573/) (2023)
- [Higher-Order GNNs Meet Efficiency: Sparse Sobolev Graph Neural Networks](https://mlsanity.com/paper/2411.04570/) (2024)
- [Scalable Hypergraph Structure Learning with Diverse Smoothness Priors](https://mlsanity.com/paper/2504.03583/) (2025)
- [Leveraging Low-rank Factorizations of Conditional Correlation Matrices in Graph Learning](https://mlsanity.com/paper/2506.10628/) (2025)
- [Bayesian Graph Convolutional Network for Traffic Prediction](https://mlsanity.com/paper/2104.00488/) (2021)
- [Free Lunch for Privacy Preserving Distributed Graph Learning](https://mlsanity.com/paper/2305.10869/) (2023)
- [Graph-Dictionary Signal Model for Sparse Representations of Multivariate Data](https://mlsanity.com/paper/2411.05729/) (2024)
- [Adversarial-Robustness-Guided Graph Pruning](https://mlsanity.com/paper/2411.12331/) (2024)
- [Signed Graph Learning: Algorithms and Theory](https://mlsanity.com/paper/2507.09717/) (2025)
- [Learning Conditional Independence Differential Graphs From Time-Dependent Data](https://mlsanity.com/paper/2512.06960/) (2025)
- [T2T-LA: A Topology-to-Topology LLM Agent for Graph Learning with Neither Feature Access nor Task Knowledge](https://mlsanity.com/paper/2512.08964/) (2025)

## Abstract (arXiv)

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(n2) for n samples. In this paper, we show how to scale it, obtaining an approximation with leading cost of O(nlog(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.