Abstract
We propose a hypergraph-based active learning scheme which we term $HS^2$; $HS^2$ generalizes the previously reported algorithm $S^2$ originally proposed for graph-based active learning with pointwise queries. $HS^2$ is the first model-free active learning algorithm for hypergraphs that supports both pointwise and pairwise queries. It achieves significantly lower query complexity than traditional graph-based methods by directly leveraging high-order data structures rather than "squashing" them into standard graphs.
Introduction
Active learning (AL) is essential when labeling data is expensive or time-consuming. Most existing research focuses on Graph-based Active Learning (GAL), where data points are nodes and edges represent pairwise similarities. However, many real-world relationships are "higher-order"—for example, in subspace clustering, a relationship might only be defined by a group of $d+1$ points. While these are best modeled as hypergraphs, researchers typically handle them via clique expansion (CE), turning every hyperedge into a cluster of standard edges.
The Hypergraph Advantage
The authors argue that the standard projection of hypergraphs into graphs causes significant distortion and leads to inefficient labeling. As shown in Figure 1, the clique expansion process creates a dense network of edges that may not accurately reflect the underlying high-order structure.
By operating directly on the hypergraph, $HS^2$ avoids the redundant queries triggered by clique expansion. The core insight is that the number of "cut hyperedges" (hyperedges containing nodes from different classes) in a hypergraph is often much smaller than the number of cut edges in its clique-expanded graph.
The $HS^2$ Algorithm
$HS^2$ (Hypergraph $S^2$) operates in two alternating phases:
- Random Sampling: The learner queries random nodes until it finds two nodes belonging to different classes.
- Aggressive Search: Once a boundary between classes is detected, the algorithm performs a binary-search-like procedure along the shortest path in the hypergraph to pinpoint the cut hyperedges.
The framework introduces two key variants: $HS^2$-point for standard pointwise queries across $k$ classes, and $HS^2$-pair, a model-free approach for pairwise queries. The latter includes a robust version for noisy oracles, using a normalized majority voting strategy to maintain high confidence even when the oracle makes mistakes.
Key Results
The authors evaluated $HS^2$ using synthetic data and the Hopkins 155 dataset for motion segmentation. In motion segmentation, trajectories are modeled as 5-uniform hypergraphs, providing a more natural fit than standard graphs.
As illustrated in Figure 4, $HS^2$ reaches a 100% success probability with significantly fewer queries than the "Clique Expansion + $S^2$" baseline. On synthetic data, $HS^2$-point outperformed standard graph-based algorithms by roughly a factor of 2 in query complexity. Furthermore, the query complexity of $HS^2$-pair scales almost linearly with the number of classes ($k$), confirming its scalability for multi-class problems.
Conclusion
$HS^2$ represents a significant step forward in active learning by demonstrating that higher-order data structures should be treated directly rather than simplified into graphs. While the computational overhead of finding shortest paths in dynamic hypergraphs remains a consideration, the reduction in human query budget is substantial. Future work may explore non-parametric settings or more complex noise models for pointwise oracles.
Summary updated