Abstract
Computational efficiency is a major bottleneck in using classic graph-based approaches for semi-supervised learning (SSL) on datasets with a large number of unlabeled examples. Known techniques to improve efficiency typically involve an approximation of the graph regularization objective, but suffer two major drawbacks: first, the graph is assumed to be known or constructed with heuristic hyperparameter values; second, they do not provide a principled approximation guarantee for learning over the full unlabeled dataset. Building on recent work on learning graphs for SSL from multiple datasets and leveraging techniques for fast approximations for solving linear systems in the graph Laplacian matrix, we propose algorithms that overcome both limitations. We show a formal separation in the learning-theoretic complexity of sparse and dense graph families and demonstrate how to approximately learn the best graphs from sparse families efficiently using the conjugate gradient method. Our approach also extends to online learning with sub-linear regret. We implement our approach and demonstrate significant (10-100x) speedups over prior work on benchmark datasets while maintaining classification accuracy.
Introduction
In graph-based semi-supervised learning, data points are represented as nodes in a graph where edge weights reflect the similarity between instances. The success of these models is heavily dependent on the quality of the underlying graph structure, which is typically governed by hyperparameters such as the "bandwidth" ($\sigma$) of a Gaussian kernel.
While recent theoretical advancements have shown that it is possible to learn these optimal hyperparameters directly from data, the resulting algorithms have been computationally prohibitive. Specifically, previous state-of-the-art methods scaled at $O(n^4)$, rendering them impractical for datasets beyond a few hundred samples. This paper addresses this "efficiency bottleneck," providing a framework to make provably robust graph learning practical for large-scale applications.
Theoretical Foundations: Sparse vs. Dense Graphs
A primary contribution of this work is the formal justification for using sparse graph families, such as $k$-nearest neighbor ($k$-NN) graphs, over dense, fully connected ones. The authors demonstrate a formal separation in the learning-theoretic complexity between these two families.
By analyzing the "pseudodimension" of these graph families, the research proves that sparse graphs are inherently easier to learn with fewer data samples. Beyond the obvious memory savings, this lower complexity provides a rigorous theoretical basis for why $k$-NN graphs often outperform dense graphs in practical SSL tasks. This shift from dense to sparse structures allows the computational complexity to drop from $O(n^4)$ to approximately $O(n^2)$.
Algorithmic Innovations
To achieve these efficiency gains, the paper introduces several algorithmic optimizations:
1. Approximate Laplacian Inversion
Traditional SSL requires inverting the graph Laplacian matrix, an $O(n^3)$ operation. The authors replace this exact calculation with the Conjugate Gradient (CG) method. CG provides a fast, iterative approximation that is significantly cheaper, particularly when applied to the sparse matrices generated by $k$-NN graphs. The authors prove that as long as the approximation error is controlled, the resulting "label flip" points remain accurate enough to identify optimal hyperparameters.
2. The APPROXFEEDBACKSET Algorithm
The core contribution, Algorithm 4 (APPROXFEEDBACKSET), is designed to find "critical points"—the specific values of $\sigma$ where a change in the hyperparameter causes a predicted label to flip. To navigate the piecewise-constant loss landscape, the algorithm employs a hybrid of Newton’s method and Nesterov’s accelerated gradient descent. This combination allows the algorithm to converge reliably even when gradients are extremely small or large, which is a common challenge in graph-based optimization.
3. Online Learning and Regret Analysis
The framework is extended to an online setting where the model receives data sequentially. The authors provide a generalized regret analysis for "approximate semi-bandit feedback," showing that near-optimal results are achievable even with access only to noisy, approximate versions of the loss function. This results in sub-linear regret, meaning the system's hyperparameter selection improves consistently as more data is processed.
Experimental Results
The proposed methods were evaluated on three standard image recognition benchmarks: MNIST, Fashion-MNIST, and USPS. The experiments focused on binary classification tasks to compare the efficiency and accuracy of the new algorithms against traditional exact-matrix-inversion methods.
- Massive Speedups: The approach achieved 10x to 100x speedups compared to previous methods.
- Accuracy Preservation: Despite the use of approximations, the algorithms matched or slightly exceeded the classification accuracy of exact methods across all datasets.
- Scalability: By reducing the complexity to $O(n^2)$, the authors demonstrated that graph learning can finally be applied to datasets that were previously unreachable for these techniques.
Conclusion and Future Work
This work bridges the gap between the theoretical ideal of learning optimal graphs and the practical necessity of computational efficiency. By leveraging sparse graph families and iterative approximation methods like Conjugate Gradient, the authors provide a scalable path forward for graph-based SSL.
Future research directions include extending these efficiency gains to modern Graph Neural Networks (GNNs) and exploring the simultaneous learning of multiple hyperparameters (e.g., individual feature weights) using similar approximation techniques. While the current proofs rely on certain smoothness assumptions for the label functions, the empirical success of the algorithms suggests broad applicability in real-world semi-supervised learning scenarios.
Summary updated