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\}(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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keykalofolias2017large

Related papers

• Grale: Designing Networks For Graph Learning (2020)10.85
• Large-scale Graph Building In Dynamic Environments: Low Latency And High Quality (2025)0.00
• Sketch-gnn: Scalable Graph Neural Networks With Sublinear Training Complexity (2024)0.00
• Learning-based Efficient Graph Similarity Computation Via Multi-scale Convolutional Set Matching (2018)13.60
• Learning Graph Edit Distance By Graph Neural Networks (2020)10.85
• Towards Similarity Graphs Constructed By Deep Reinforcement Learning (2019)0.00
• Graph-based Nearest Neighbor Search: From Practice To Theory (2019)0.00
• Navigable Graphs For High-dimensional Nearest Neighbor Search: Constructions And Limits (2024)4.52