Large Scale Graph Learning from Smooth Signals

2017/10/16 by Vassilis Kalofolias, Kalofolias, Vassilis, Nathanaël Perraudin +1 · 5 citations
Computer Science · Mathematics · #Advanced Graph Neural Networks #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1710.05654

openalex publication_date 2017/10/16 · arxiv created 2019/05/01 · arxiv updated 2019/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 O(n²) 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.

Citations

• Deep Convolutional Networks on Graph-Structured Data
• GSPBOX: A toolbox for signal processing on graphs
• Matrix Completion on Graphs
• Playing with Duality: An overview of recent primal?dual approaches for solving large-scale optimization problems
• A tutorial on spectral clustering
• How to learn a graph from smooth signals
• Gated Graph Sequence Neural Networks
• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• Semi-Supervised Classification with Graph Convolutional Networks

Cited by

• Learning Conditional Independence Differential Graphs From Time-Dependent Data
• T2T-LA: A Topology-to-Topology LLM Agent for Graph Learning with Neither Feature Access nor Task Knowledge
• Signed Graph Learning: Algorithms and Theory
• Leveraging Low-rank Factorizations of Conditional Correlation Matrices in Graph Learning
• Algorithm Unrolling-based Denoising of Multimodal Graph Signals

Related

• Large-Scale Semi-Supervised Learning via Graph Structure Learning over High-Dense Points
• How to learn a graph from smooth signals
• Optimizing k in kNN Graphs with Graph Learning Perspective
• Fast and Accurate Graph Learning for Huge Data via Minipatch Ensembles
• Efficiently Learning the Graph for Semi-supervised Learning