Research map / Label-efficient and robust learning / Semi-supervised learning
Fast Algorithms for Hypergraph PageRank with Applications to Semi-Supervised Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives fast first-order algorithms for hypergraph Laplacian systems and hypergraph personalized PageRank over a broad class of convex 2-positively homogeneous hypergraph potentials, with convergence guarantees and speedups on semi-supervised categorical clustering and manifold learning.
Problem
Solving hypergraph Laplacian systems and computing hypergraph PageRank vectors is hard because the hypergraph Laplacian is non-linear and non-smooth, so scalable semi-supervised learning with hypergraphs has been impractical.
Approach
A Richardson-like subgradient method for convex 2-positively homogeneous hypergraph potentials, with a multiplicative-error analysis that exploits 2-positive homogeneity; it applies to any potential in the general family and achieves linear-time iterations, with a clique-expansion preconditioner giving a lambda_G-independent bound for U-infinity on bounded-rank hypergraphs.
Key results
- Hypergraph PPR outperforms graph PPR in AUC on concentric hyperspheres and hyperrectangles, with the gap widening as ambient dimension grows (7 and 15 dimensions shown).
- The proposed algorithm matches competitor classification performance on UCI categorical datasets while requiring about one tenth of the running time.
- For U-infinity on bounded-rank hypergraphs, the clique-expansion preconditioned method gives an iteration bound O(max|h|/eps^2) independent of the Poincare constant.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use hypergraph PPR instead of graph PPR | Semi-supervised manifold clustering · Concentric hyperspheres and hyperrectangles, especially at higher dimensions | AUC | Helped |
| use the proposed algorithm instead of competing methods | UCI categorical classification · UCI datasets | running time: tenfold speed-up | Helped |
| use the proposed algorithm instead of competing methods | UCI categorical classification · UCI datasets | classification performance | No clear effect |
| use the Gaussian-kernel weighted potential instead of the unweighted U∞ potential (ablation) | Hypergraph PPR for manifold learning · Manifold learning | AUC | Helped |
Surprising findings
- Subgradient QDSFM has the best per-iteration time but requires many more iterations and often fails to converge to the minimizer.
Limitations
- Iteration count scales as O(1/eps^2) due to non-smoothness, polynomially rather than logarithmically in accuracy
- Clique-expansion preconditioner factor max|h| makes the nearly-linear result unsuitable for large hyperedges
- Manifold learning advantage shown only with preliminary synthetic experiments and no recovery guarantees
Experimental setup
Datasets: UCI categorical datasets (Zoo, Twenty Newsgroups, and others) synthetic concentric hyperspheres and hyperrectangles
Benchmarks: UCI categorical semi-supervised classification synthetic manifold semi-supervised AUC
Metrics: classification accuracy AUC running time convergence to minimizer
Baselines: Hein et al. 2013 primal-dual hybrid gradient Li et al. 2020 QDSFM Subgradient QDSFM graph PPR
Builds on: Spielman-Teng nearly-linear-time Laplacian solvers Hein et al. 2013 hypergraph total variation Takai et al. 2020 hypergraph PageRank Li et al. 2020 QDSFM optimistic mirror descent
Closest papers by meaning
- Nonlinear Feature Diffusion on Hypergraphs (ICML 2022 · similarity 0.89)
- Hypergraph p-Laplacian: A Differential Geometry View (AAAI 2018 · similarity 0.89)
- Hypergraph-enhanced Dual Semi-supervised Graph Classification (ICML 2024 · similarity 0.88)
- Hypergraph Representation Learning with Hyperlink Random Effects (NeurIPS 2026 · similarity 0.86)
- When Hypergraph Meets Heterophily: New Benchmark Datasets and Baseline (AAAI 2025 · similarity 0.85)
- HYGENE: A Diffusion-Based Hypergraph Generation Method (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.