mlsanityData to 7 Oct 2026

Large Scale Graph Learning from Smooth Signals

arXiv 1710.05654 ↗First posted 16 Oct 2017stat.ML cs.LGcited by 27

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 6; 2022: 4; 2023: 7; 2024: 5; 2025: 5.

27 papers.

Sort:

By area:

  1. 2021Accelerated Graph Learning from Smooth Signalscited by 16
  2. 2022GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networkscited by 14
  3. 2021Online Graph Learning under Smoothness Priorscited by 8
  4. 2022Bag Graph: Multiple Instance Learning using Bayesian Graph Neural Networkscited by 6
  5. 2021Sparse Graph Learning Under Laplacian-Related Constraintscited by 5
  6. 2023A Markov Random Field model for Hypergraph-based Machine Learningcited by 5
  7. 2023Hypergraph-MLP: Learning on Hypergraphs without Message Passingcited by 5
  8. 2021Distributionally Robust Graph Learning from Smooth Signals under Moment Uncertaintycited by 4
  9. 2022Learning Sparse Graphs via Majorization-Minimization for Smooth Node Signalscited by 4
  10. 2022Node Copying: A Random Graph Model for Effective Graph Samplingcited by 4
  11. 2024SAGMAN: Stability Analysis of Graph Neural Networks on the Manifoldscited by 4
  12. 2023Graph Laplacian Learning with Exponential Family Noisecited by 3
15 more
  1. 2023A Unified Framework for Fair Spectral Clustering With Effective Graph Learningcited by 3
  2. 2024Optimizing k in kNN Graphs with Graph Learning Perspectivecited by 2
  3. 2021Distributed Graph Learning with Smooth Data Priorscited by 1
  4. 2023SF-SGL: Solver-Free Spectral Graph Learning from Linear Measurementscited by 1
  5. 2023Joint Graph Learning and Model Fitting in Laplacian Regularized Stratified Modelscited by 1
  6. 2024Higher-Order GNNs Meet Efficiency: Sparse Sobolev Graph Neural Networkscited by 1
  7. 2025Scalable Hypergraph Structure Learning with Diverse Smoothness Priorscited by 1
  8. 2025Leveraging Low-rank Factorizations of Conditional Correlation Matrices in Graph Learningcited by 1
  9. 2021Bayesian Graph Convolutional Network for Traffic Predictioncited by 0
  10. 2023Free Lunch for Privacy Preserving Distributed Graph Learningcited by 0
  11. 2024Graph-Dictionary Signal Model for Sparse Representations of Multivariate Datacited by 0
  12. 2024Adversarial-Robustness-Guided Graph Pruningcited by 0
  13. 2025Signed Graph Learning: Algorithms and Theorycited by 0
  14. 2025Learning Conditional Independence Differential Graphs From Time-Dependent Datacited by 0
  15. 2025T2T-LA: A Topology-to-Topology LLM Agent for Graph Learning with Neither Feature Access nor Task Knowledgecited by 0