Efficiently learning the graph for semi-supervised learning

Dravyansh Sharma, Maxwell Jones

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:

  1. The "Art" of Graph Construction: Choosing parameters like the number of neighbors or similarity bandwidth is usually done via trial-and-error.
  2. 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.

Hybrid optimization combining descent and Newton steps to efficiently find optimal graph parameters.

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.
Classification accuracy vs. graph bandwidth (sigma) on MNIST, Fashion-MNIST, and USPS datasets.

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

Abstract

Computational efficiency is a major bottleneck in using classic graph-based approaches for semi-supervised learning 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 semi-supervised learning from multiple datasets for problems from the same domain, and leveraging techniques for fast approximations for solving linear systems in the graph Laplacian matrix, we propose algorithms that overcome both the above limitations. We show a formal separation in the learning-theoretic complexity of sparse and dense graph families. We further show how to approximately learn the best graphs from the sparse families efficiently using the conjugate gradient method. Our approach can also be used to learn the graph efficiently online with sub-linear regret, under mild smoothness assumptions. Our online learning results are stated generally, and may be useful for approximate and efficient parameter tuning in other problems. We implement our approach and demonstrate significant ($\sim$10-100x) speedups over prior work on semi-supervised learning with learned graphs on benchmark datasets.
BibTeX
@inproceedings{sharma2023efficiently,
  author = {Dravyansh Sharma and Maxwell Jones},
  title = {{Efficiently learning the graph for semi-supervised learning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=rzqiFEaeFP},
}
Figure