Large Scale Graph Learning from Smooth Signals

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.

References in corpus (8)

• Semi-Supervised Classification with Graph Convolutional Networks
• Deep Convolutional Networks on Graph-Structured Data
• Gated Graph Sequence Neural Networks
• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• DeepSphere: Efficient spherical Convolutional Neural Network with HEALPix sampling for cosmological applications
• Matrix Completion on Graphs
• Fast Robust PCA on Graphs
• How to learn a graph from smooth signals

Cited by in corpus (12)

• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings
• Graph Neural Networks for Natural Language Processing: A Survey
• Deep Iterative and Adaptive Learning for Graph Neural Networks
• Kernel-based Graph Learning from Smooth Signals: A Functional Viewpoint
• Bayesian Spatio-Temporal Graph Convolutional Network for Traffic Forecasting
• Sparse Graph Learning Under Laplacian-Related Constraints
• GRASPEL: Graph Spectral Learning at Scale
• Learning Product Graphs Underlying Smooth Graph Signals
• Bayesian Graph Neural Network for Fast identification of critical nodes in Uncertain Complex Networks
• Node Copying: A Random Graph Model for Effective Graph Sampling
• SF-SGL: Solver-Free Spectral Graph Learning from Linear Measurements
• Mask Combination of Multi-layer Graphs for Global Structure Inference