# Local Hyper-Flow Diffusion

arXiv: https://arxiv.org/abs/2102.07945 · HTML: https://mlsanity.com/paper/2102.07945/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 51 references that are in the map.
- First posted on arXiv 16 Feb 2021.

## Builds on (most cited first, 22 of 22)

- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys](https://mlsanity.com/paper/1506.03645/) (2015)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time](https://mlsanity.com/paper/1711.07601/) (2017)
- [Random Walks on Hypergraphs with Edge-Dependent Vertex Weights](https://mlsanity.com/paper/1905.08287/) (2019)
- [The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited](https://mlsanity.com/paper/1312.5179/) (2013)
- [Inhomogeneous Hypergraph Clustering with Applications](https://mlsanity.com/paper/1709.01249/) (2017)
- [Clustering in graphs and hypergraphs with categorical edge labels](https://mlsanity.com/paper/1910.09943/) (2019)
- [Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering](https://mlsanity.com/paper/1803.03833/) (2018)
- [Hypergraph Random Walks, Laplacians, and Clustering](https://mlsanity.com/paper/2006.16377/) (2020)
- [p-Norm Flow Diffusion for Local Graph Clustering](https://mlsanity.com/paper/2005.09810/) (2020)
- [Hypergraph Clustering Based on PageRank](https://mlsanity.com/paper/2006.08302/) (2020)
- [Variational Perspective on Local Graph Clustering](https://mlsanity.com/paper/1602.01886/) (2016)
- [Hypergraph Cuts with General Splitting Functions](https://mlsanity.com/paper/2001.02817/) (2020)
- [Cheeger Inequalities for Submodular Transformations](https://mlsanity.com/paper/1708.08781/) (2017)
- [Strongly Local Hypergraph Diffusions for Clustering and Semi-supervised Learning](https://mlsanity.com/paper/2011.07752/) (2020)
- [Capacity Releasing Diffusion for Speed and Locality](https://mlsanity.com/paper/1706.05826/) (2017)
- [Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms](https://mlsanity.com/paper/1408.2425/) (2014)
- [Quadratic Decomposable Submodular Function Minimization: Theory and Practice (Computation and Analysis of PageRank over Hypergraphs)](https://mlsanity.com/paper/1902.10132/) (2019)
- [Landing Probabilities of Random Walks for Seed-Set Expansion in Hypergraphs](https://mlsanity.com/paper/1910.09040/) (2019)
- [Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance](https://mlsanity.com/paper/2004.09608/) (2020)
- [Local Hypergraph Clustering using Capacity Releasing Diffusion](https://mlsanity.com/paper/2003.04213/) (2020)

## Built on by (most cited first, 8 of 8)

- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [Recent Advances in Hypergraph Neural Networks](https://mlsanity.com/paper/2503.07959/) (2025)
- [Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees](https://mlsanity.com/paper/2605.18775/) (2026)
- [Finding Bipartite Components in Hypergraphs](https://mlsanity.com/paper/2205.02771/) (2022)
- [Learning the effective order of a hypergraph dynamical system](https://mlsanity.com/paper/2306.01813/) (2023)
- [Hypergraph Neural Diffusion: A PDE-Inspired Framework for Hypergraph Message Passing](https://mlsanity.com/paper/2604.10955/) (2026)
- [Local Graph Clustering with Noisy Labels](https://mlsanity.com/paper/2310.08031/) (2023)
- [Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components](https://mlsanity.com/paper/2110.14859/) (2021)

## Abstract (arXiv)

Recently, hypergraphs have attracted a lot of attention due to their ability to capture complex relations among entities. The insurgence of hypergraphs has resulted in data of increasing size and complexity that exhibit interesting small-scale and local structure, e.g., small-scale communities and localized node-ranking around a given set of seed nodes. Popular and principled ways to capture the local structure are the local hypergraph clustering problem and related seed set expansion problem. In this work, we propose the first local diffusion method that achieves edge-size-independent Cheeger-type guarantee for the problem of local hypergraph clustering while applying to a rich class of higher-order relations that covers many previously studied special cases. Our method is based on a primal-dual optimization formulation where the primal problem has a natural network flow interpretation, and the dual problem has a cut-based interpretation using the ℓ2-norm penalty on associated cut-costs. We demonstrate the new technique is significantly better than state-of-the-art methods on both synthetic and real-world data.