mlsanityData to 7 Oct 2026

How to learn a graph from smooth signals

arXiv 1601.02513 ↗First posted 11 Jan 2016stat.ML cs.LG physics.data-ancited by 146

Not on the map. Why?

Abstract (arXiv)

We propose a framework that learns the graph structure underlying a set of smooth signals. Given X∈ℝm× n whose rows reside on the vertices of an unknown graph, we learn the edge weights w∈ℝ_+m(m-1)/2 under the smoothness assumption that trX^top LX is small. We show that the problem is a weighted ℓ-1 minimization that leads to naturally sparse solutions. We point out how known graph learning or construction techniques fall within our framework and propose a new model that performs better than the state of the art in many settings. We present efficient, scalable primal-dual based algorithms for both our model and the previous state of the art, and evaluate their performance on artificial and real data.

Key facts. Cited by 146 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 Jan 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 22; 2022: 32; 2023: 24; 2024: 25; 2025: 26; 2026: 17.

146 papers.

Sort:

By area:

  1. 2022Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methodscited by 146
  2. 2021Graph Learning: A Surveycited by 140
  3. 2023SGFormer: Simplifying and Empowering Transformers for Large-Graph Representationscited by 131
  4. 2021A Survey on Graph Structure Learning: Progress and Opportunitiescited by 70
  5. 2022Graph Filters for Signal Processing and Machine Learning on Graphscited by 53
  6. 2023AbDiffuser: Full-Atom Generation of in vitro Functioning Antibodiescited by 35
  7. 2022Multi-modal Graph Learning for Disease Predictioncited by 34
  8. 2022Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashingcited by 31
  9. 2022Modeling Multivariate Biosignals With Graph Neural Networks and Structured State Space Modelscited by 29
  10. 2021Learning to Learn Graph Topologiescited by 26
  11. 2022Make Heterophily Graphs Better Fit GNN: A Graph Rewiring Approachcited by 23
  12. 2024Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partitioncited by 23
38 more
  1. 2021Learning Connectivity with Graph Convolutional Networks for Skeleton-based Action Recognitioncited by 20
  2. 2022Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Neural Networkscited by 19
  3. 2024SLMRec: Distilling Large Language Models into Small for Sequential Recommendationcited by 18
  4. 2021Accelerated Graph Learning from Smooth Signalscited by 16
  5. 2021Signal processing on simplicial complexescited by 12
  6. 2021Learning Time-Varying Graphs from Online Datacited by 12
  7. 2023GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networkscited by 12
  8. 2023Chasing Fairness in Graphs: A GNN Architecture Perspectivecited by 12
  9. 2024Gegenbauer Graph Neural Networks for Time-varying Signal Reconstructioncited by 12
  10. 2022MM-GNN: Mix-Moment Graph Neural Network towards Modeling Neighborhood Feature Distributioncited by 11
  11. 2022Joint Network Topology Inference via a Shared Graphon Modelcited by 11
  12. 2022Principle of Relevant Information for Graph Sparsificationcited by 9
  13. 2022Restructuring Graph for Higher Homophily via Adaptive Spectral Clusteringcited by 9
  14. 2022A Unified Framework for Optimization-Based Graph Coarseningcited by 9
  15. 2022Learning Hypergraphs From Signals With Dual Smoothness Priorcited by 9
  16. 2021Online Graph Learning under Smoothness Priorscited by 8
  17. 2022Learning Graphical Factor Models with Riemannian Optimizationcited by 8
  18. 2024LAN: Learning Adaptive Neighbors for Real-Time Insider Threat Detectioncited by 8
  19. 2022Methods for Recovering Conditional Independence Graphs: A Surveycited by 7
  20. 2024Non-negative Weighted DAG Structure Learningcited by 7
  21. 2022Bag Graph: Multiple Instance Learning using Bayesian Graph Neural Networkscited by 6
  22. 2023Bures-Wasserstein Means of Graphscited by 6
  23. 2025Learning Sheaf Laplacian Optimizing Restriction Mapscited by 6
  24. 2021Sparse Graph Learning Under Laplacian-Related Constraintscited by 5
  25. 2022Learning Graph Structure from Convolutional Mixturescited by 5
  26. 2022Learning Product Graphs from Spectral Templatescited by 5
  27. 2022ProductGraphSleepNet: Sleep Staging using Product Spatio-Temporal Graph Learning with Attentive Temporal Aggregationcited by 5
  28. 2023A Markov Random Field model for Hypergraph-based Machine Learningcited by 5
  29. 2021Distributionally Robust Graph Learning from Smooth Signals under Moment Uncertaintycited by 4
  30. 2022Learning Sparse Graphs via Majorization-Minimization for Smooth Node Signalscited by 4
  31. 2022Learning Expanding Graphs for Signal Interpolationcited by 4
  32. 2022Finding MNEMON: Reviving Memories of Node Embeddingscited by 4
  33. 2024Learning Latent Graph Structures and their Uncertaintycited by 4
  34. 2024Graph Structure Learning with Interpretable Bayesian Neural Networkscited by 4
  35. 2024Efficient Learning of Balanced Signed Graphs via Iterative Linear Programmingcited by 4
  36. 2021Robust Graph Learning Under Wasserstein Uncertaintycited by 3
  37. 2022Joint graph learning from Gaussian observations in the presence of hidden nodescited by 3
  38. 2023Graph Laplacian Learning with Exponential Family Noisecited by 3

50 most cited of 146 All 146 (JSON)