Abstract
Computational efficiency is a major bottleneck in using classic graph-based approaches for semi-supervised learning (SSL) on large datasets. This paper introduces a framework to provably learn optimal graph parameters from data 10–100x faster than previous methods. By leveraging graph sparsity and conjugate gradient approximations, the proposed algorithms overcome the limitations of heuristic graph construction and provide principled approximation guarantees.
Introduction
In semi-supervised learning, a small amount of labeled data is combined with a large volume of unlabeled data to build predictive models. A popular approach represents data as a graph where nodes are examples and edges represent similarity. However, this approach faces two major hurdles:
- The "Art" of Graph Construction: Choosing parameters like the number of neighbors or similarity bandwidth is usually done via trial-and-error.
- Computational Bottlenecks: Previous attempts to provably learn the best graph parameters required $O(n^4)$ time, making them practically unusable for large $n$.
The authors bridge this gap by creating algorithms that are both theoretically guaranteed to find near-optimal graphs and fast enough for real-world applications.
Methodology
The authors propose several innovations to speed up the "learning to learn" process for graphs:
Sparse Graph Families
Instead of dense, fully connected graphs, the research focuses on $k$-nearest neighbor (kNN) and thresholded graphs. They prove that these sparse structures have a lower "pseudodimension," meaning they are statistically easier to learn and require fewer instances to converge on optimal hyperparameters.
Conjugate Gradient (CG) Acceleration
To avoid the $O(n^3)$ cost of inverting the graph Laplacian matrix, the iterative Conjugate Gradient method is used. This allows for much faster approximation of the graph's behavior. Furthermore, CG is more robust than standard matrix inversion, which can become numerically unstable (ill-conditioned) for certain graph parameters.
Hybrid Optimization
To find the specific parameter values where predicted labels "flip"—the critical points for optimization—the authors use a combination of Newton’s method and Nesterov’s accelerated gradient descent. This hybrid approach effectively handles regions where gradients are either too flat or too steep.
Experimental Evaluation
The researchers evaluated their approach on three standard image recognition benchmarks: MNIST, Fashion-MNIST, and USPS. They focused on binary classification tasks to test the efficiency of their graph-learning algorithms.
Key Results
- Massive Speedups: The proposed algorithms achieved 10x to 100x speedups over the previous state-of-the-art for provable graph learning. On MNIST with 500 nodes, the time per interval dropped from ~818 seconds to ~58 seconds.
- Accuracy Preservation: Despite using approximations, the models maintained classification accuracy compared to exact but slower methods.
- Scalability: The approach successfully scaled to larger subsets of data where previous "provable" methods would have timed out.
Conclusion
This work provides a scalable and theoretically grounded framework for learning graph structures in SSL. By utilizing sparsity and efficient linear solvers, the authors demonstrate that high-performance graph learning is possible without prohibitive computational costs. Future work includes extending these techniques to multi-class settings and more complex SSL architectures like graph neural networks.
Summary updated