# Finding Cheeger Cuts in Hypergraphs via Heat Equation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2018.

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

- [Hypergraph Modeling via Spectral Embedding Connection: Hypergraph Cut, Weighted Kernel k-means, and Heat Kernel](https://mlsanity.com/paper/2203.09888/) (2022)

## Abstract (arXiv)

Cheeger's inequality states that a tightly connected subset can be extracted from a graph G using an eigenvector of the normalized Laplacian associated with G. More specifically, we can compute a subset with conductance O(√φG), where φG is the minimum conductance of a set in G. It has recently been shown that Cheeger's inequality can be extended to hypergraphs. However, as the normalized Laplacian of a hypergraph is no longer a matrix, we can only approximate to its eigenvectors; this causes a loss in the conductance of the obtained subset. To address this problem, we here consider the heat equation on hypergraphs, which is a differential equation exploiting the normalized Laplacian. We show that the heat equation has a unique solution and that we can extract a subset with conductance √φG from the solution. An analogous result also holds for directed graphs.