Abstract: Hypergraphs provide a natural framework for modeling higher-order interactions, yet their theoretical underpinnings in semi-supervised learning remain limited. We provide an asymptotic consistency analysis of variational learning on random geometric hypergraphs, precisely characterizing the conditions ensuring the well-posedness of hypergraph learning as well as showing convergence to a weighted $p$-Laplacian equation. Motivated by this, we propose Higher-Order Hypergraph Learning (HOHL), which regularizes via powers of Laplacians from skeleton graphs for multiscale smoothness. HOHL converges to a higher-order Sobolev seminorm. Empirically, it performs strongly on standard baselines.
Introduction
Semi-supervised learning (SSL) on graphs has long relied on the assumption that connected nodes should share similar labels. Hypergraphs extend this paradigm by allowing edges to connect more than two nodes, theoretically capturing complex group relationships. However, despite their widespread use, the "continuum limits" of hypergraph learning—the behavior of these algorithms as the number of data points approaches infinity—have remained poorly understood. This paper establishes a rigorous theoretical foundation for hypergraph SSL, identifying fundamental limitations in classical methods and proposing a novel framework for higher-order regularization.
The First-Order Limitation of Classical Hypergraphs
A primary contribution of this work is the revelation that standard hypergraph learning is inherently limited to first-order smoothness. Through asymptotic consistency analysis using tools from the calculus of variations (specifically $\Gamma$-convergence) and optimal transport ($TL^p$ spaces), the authors demonstrate that classical hypergraph learning effectively reduces to reweighted graph learning.
In the large data limit, these variational problems on random geometric hypergraphs converge to a weighted $p$-Laplacian equation. This means that despite the higher-order structure of the hyperedges, the regularization only penalizes pairwise differences within those edges, failing to exploit true higher-order geometry such as curvature or higher derivatives.
Higher-Order Hypergraph Learning (HOHL)
To overcome this limitation, the authors introduce Higher-Order Hypergraph Learning (HOHL). HOHL utilizes a multiscale approach that regularizes using powers of Laplacians, $(L^{(k)})^{p_k}$, derived from "skeleton graphs"—graphs formed by all pairs within hyperedges of a specific size.
In this framework, hyperedge size serves as a proxy for scale. Smaller hyperedges are used to enforce global smoothness, while larger hyperedges, which are more prevalent in high-density regions, enforce fine-grained, higher-order regularity. This allows HOHL to achieve higher-order Sobolev smoothness, distinguishing it from the first-order behavior of previous methods.
Theoretical Insights and Well-Posedness
The paper provides a comprehensive "family tree" of SSL algorithms based on their continuum limits within Sobolev spaces $W^{(k,p)}$. As shown in the taxonomy above, HOHL is uniquely categorized as a higher-order method ($W^{(q,2)}$).
Furthermore, the authors identify precise regimes for "well-posedness." In the large data limit, many SSL algorithms risk becoming ill-posed, where solutions either collapse to a constant or develop non-informative "spikes" at labeled points. The analysis shows that for classical learning, well-posedness requires $p > d$ (where $d$ is the data dimension), a result that mirrors classical Sobolev embedding theorems. HOHL is designed to remain well-posed in regimes where first-order methods fail.
Empirical Results
The theoretical advantages of HOHL translate into significant empirical gains across standard benchmarks, including the Iris, Digits, Salinas A, and MNIST datasets.
On the Digits dataset with a 0.20 labeling rate, HOHL (specifically the IP-QC configuration) achieved 89.12% accuracy, vastly outperforming standard Laplace learning at 68.58%. The "Increasing Powers" (IP) variant, which applies progressively higher-order regularization at finer scales, proved to be the most effective configuration, validating the multiscale hypothesis.
Conclusion
By bridging the gap between discrete hypergraph algorithms and their continuous counterparts, this research provides a roadmap for designing more robust SSL methods. While challenges remain regarding the computational cost of constructing hypergraphs and extending analysis to non-geometric structures, HOHL represents a significant step forward in capturing the true higher-order geometry of complex data.
Summary updated