# Finding Bipartite Components in Hypergraphs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 40 references that are in the map.
- First posted on arXiv 5 May 2022.

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

- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Random Walks on Hypergraphs with Edge-Dependent Vertex Weights](https://mlsanity.com/paper/1905.08287/) (2019)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [Inhomogeneous Hypergraph Clustering with Applications](https://mlsanity.com/paper/1709.01249/) (2017)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering](https://mlsanity.com/paper/1803.03833/) (2018)
- [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)
- [Cheeger Inequalities for Submodular Transformations](https://mlsanity.com/paper/1708.08781/) (2017)
- [Local Hyper-Flow Diffusion](https://mlsanity.com/paper/2102.07945/) (2021)
- [Local Algorithms for Finding Densely Connected Clusters](https://mlsanity.com/paper/2106.05245/) (2021)

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

- [Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework](https://mlsanity.com/paper/2210.12048/) (2022)
- [On Learning the Structure of Clusters in Graphs](https://mlsanity.com/paper/2212.14345/) (2022)
- [Online Sparsification of Bipartite-Like Clusters in Graphs](https://mlsanity.com/paper/2508.05437/) (2025)
- [Hypergraph Generation via Structured Stochastic Diffusion](https://mlsanity.com/paper/2605.05024/) (2026)

## Abstract (arXiv)

Hypergraphs are important objects to model ternary or higher-order relations of objects, and have a number of applications in analysing many complex datasets occurring in practice. In this work we study a new heat diffusion process in hypergraphs, and employ this process to design a polynomial-time algorithm that approximately finds bipartite components in a hypergraph. We theoretically prove the performance of our proposed algorithm, and compare it against the previous state-of-the-art through extensive experimental analysis on both synthetic and real-world datasets. We find that our new algorithm consistently and significantly outperforms the previous state-of-the-art across a wide range of hypergraphs.