Abstract
We consider a novel data driven approach for designing learning algorithms that can effectively learn with only a small number of labeled examples. This is crucial for modern machine learning applications where labels are scarce or expensive to obtain. We focus on graph-based techniques, where the unlabeled examples are connected in a graph under the implicit assumption that similar nodes likely have similar labels. Over the past decades, several elegant graph-based semi-supervised learning algorithms for how to infer the labels of the unlabeled examples given the graph and a few labeled examples have been proposed. However, the problem of how to create the graph (which impacts the practical usefulness of these methods significantly) has been relegated to domain-specific art and heuristics and no general principles have been proposed. In this work we present a novel data driven approach for learning the graph and provide strong formal guarantees in both the distributional and online learning formalizations. We show how to leverage problem instances coming from an underlying problem domain to learn the graph hyperparameters from commonly used parametric families of graphs that perform well on new instances coming from the same domain. We obtain low regret and efficient algorithms in the online setting, and generalization guarantees in the distributional setting. We also show how to combine several very different similarity metrics and learn multiple hyperparameters, providing general techniques to apply to large classes of problems. We expect some of the tools and techniques we develop along the way to be of interest beyond semi-supervised learning, for data driven algorithms for combinatorial problems more generally.
Introduction
Semi-supervised learning (SSL) is a critical paradigm in machine learning, particularly when labeled data is scarce but unlabeled data is abundant. Graph-based SSL methods are among the most popular approaches, operating on the principle that data points (nodes) connected by edges representing high similarity should share similar labels. However, the effectiveness of these methods is highly dependent on the graph's construction—a process often described as a "black art" due to its reliance on manual tuning and domain-specific heuristics.
The choice of hyperparameters, such as the threshold for edge creation or the width of a Gaussian kernel, significantly impacts performance. If the graph is too sparse, label information cannot propagate; if it is too dense, the resulting labels become noisy. This work moves beyond heuristics by proposing a theoretically grounded, data-driven framework to automatically learn optimal graph hyperparameters across multiple task instances.
Background: Graph-Based SSL Algorithms
Several established algorithms exist for inferring labels once a graph is constructed. These include Mincut, Harmonic functions, Normalized cut, and Label propagation. Each algorithm imposes different constraints on the label function $f$ and utilizes different objective functions $H(f, W)$.
Despite the elegance of these algorithms, the fundamental challenge remains: how to construct the weight matrix $W$ (the graph) in a way that reflects the true underlying structure of the data domain.
Methodology: Data-Driven Graph Construction
The authors frame the selection of graph parameters as a meta-learning problem. They consider three primary families of graph kernels:
- Threshold Graphs: Edges are formed if the distance $d(u,v) \leq r$.
- Polynomial Kernels: Edge weights are proportional to a power of the similarity metric.
- Gaussian RBF Kernels: Weights decay exponentially based on distance and a bandwidth parameter $\sigma$.
The Challenge of Non-Lipschitz Loss
A significant technical hurdle in optimizing these parameters is that the loss function—representing the number of misclassified nodes—is non-smooth and non-Lipschitz. As a parameter like the threshold $r$ varies, the graph structure changes discretely when edges are added or removed, causing "jumps" in the loss function.
To address this, the authors utilize the concept of dispersion. By assuming the similarity metric has a bounded density, they prove that these discontinuities are sufficiently spread out, making the problem learnable.
Theoretical and Algorithmic Contributions
The paper provides strong formal guarantees for both online and distributional learning settings:
- Online Learning: The authors present an algorithm that achieves $\tilde{O}(\sqrt{T})$ regret by maintaining and updating a distribution over the parameter space as new problem instances arrive.
- Efficient Optimization: For threshold graphs, they introduce a "Dynamic Min-Cut" approach that efficiently identifies the intervals where the graph structure remains constant, avoiding the need for exhaustive search.
- Generalization: In the distributional setting, they provide bounds on the number of training instances required to ensure that the learned parameters perform well on unseen tasks from the same domain.
Key Insights and Results
Experimental evaluations on benchmarks like MNIST, Omniglot, and CIFAR-10 reveal several key insights:
- Domain Sensitivity: Optimal parameters are highly dataset-specific. A parameter set that works for handwritten digits (MNIST) is often suboptimal for natural images (CIFAR-10).
- Performance Impact: Choosing a suboptimal parameter can lead to an accuracy gap of over 10%, emphasizing the value of automated tuning.
- Complexity: The pseudodimension of learning the parameter is $O(\log n)$ for unweighted threshold graphs and $\Theta(n)$ for weighted graphs, indicating that learning is feasible even with relatively few task instances.
Conclusion
This work provides a principled foundation for automating graph construction in semi-supervised learning. By treating hyperparameter selection as a data-driven algorithm design problem, the authors replace manual heuristics with algorithms backed by formal guarantees. Future work includes extending these techniques to more complex combinatorial optimization problems and exploring the synergy between learned graphs and active learning strategies.
Summary updated