# Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 60 references that are in the map.
- First posted on arXiv 23 Oct 2024.

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

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Hypergraph Neural Networks](https://mlsanity.com/paper/1809.09401/) (2018)
- [Eigenvalue and Generalized Eigenvalue Problems: Tutorial](https://mlsanity.com/paper/1903.11240/) (2019)
- [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)
- [Heterogeneous Contrastive Learning for Foundation Models and Beyond](https://mlsanity.com/paper/2404.00225/) (2024)
- [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)
- [Hypergraph Clustering Based on PageRank](https://mlsanity.com/paper/2006.08302/) (2020)
- [A Survey on Hypergraph Mining: Patterns, Tools, and Generators](https://mlsanity.com/paper/2401.08878/) (2024)
- [SpherE: Expressive and Interpretable Knowledge Graph Embedding for Set Retrieval](https://mlsanity.com/paper/2404.19130/) (2024)
- [Random walks and community detection in hypergraphs](https://mlsanity.com/paper/2010.14355/) (2020)
- [From Graphs to Hypergraphs: Hypergraph Projection and its Remediation](https://mlsanity.com/paper/2401.08519/) (2024)
- [What Do LLMs Need to Understand Graphs: A Survey of Parametric Representation of Graphs](https://mlsanity.com/paper/2410.12126/) (2024)
- [Representation Learning for Heterogeneous Information Networks via Embedding Events](https://mlsanity.com/paper/1901.10234/) (2019)
- [Hypergraph Cuts with Edge-Dependent Vertex Weights](https://mlsanity.com/paper/2201.06084/) (2022)
- [Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs](https://mlsanity.com/paper/2208.06506/) (2022)
- [Overlapping and Robust Edge-Colored Clustering in Hypergraphs](https://mlsanity.com/paper/2305.17598/) (2023)
- [Hypergraphs with Edge-Dependent Vertex Weights: p-Laplacians and Spectral Clustering](https://mlsanity.com/paper/2208.07457/) (2022)
- [Hypergraphs with Edge-Dependent Vertex Weights: Spectral Clustering based on the 1-Laplacian](https://mlsanity.com/paper/2305.00462/) (2023)

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

- [Can Graph Neural Networks Learn Language with Extremely Weak Text Supervision?](https://mlsanity.com/paper/2412.08174/) (2024)
- [APEX2: Adaptive and Extreme Summarization for Personalized Knowledge Graphs](https://mlsanity.com/paper/2412.17336/) (2024)
- [Local Clustering on Complex Graphs and Complex Hypergraphs](https://mlsanity.com/paper/2412.03008/) (2024)
- [ClimateBench-M: A Multi-Modal Climate Data Benchmark with a Simple Generative Method](https://mlsanity.com/paper/2504.07394/) (2025)

## Abstract (arXiv)

Hypergraphs naturally arise when studying group relations and have been widely used in the field of machine learning. To the best of our knowledge, the recently proposed edge-dependent vertex weights (EDVW) modeling is one of the most generalized modeling methods of hypergraphs, i.e., most existing hypergraph conceptual modeling methods can be generalized as EDVW hypergraphs without information loss. However, the relevant algorithmic developments on EDVW hypergraphs remain nascent: compared to the spectral theories for graphs, its formulations are incomplete, the spectral clustering algorithms are not well-developed, and the hypergraph Cheeger Inequality is not well-defined. To this end, deriving a unified random walk-based formulation, we propose our definitions of hypergraph Rayleigh Quotient, NCut, boundary/cut, volume, and conductance, which are consistent with the corresponding definitions on graphs. Then, we prove that the normalized hypergraph Laplacian is associated with the NCut value, which inspires our proposed HyperClus-G algorithm for spectral clustering on EDVW hypergraphs. Finally, we prove that HyperClus-G can always find an approximately linearly optimal partitioning in terms of both NCut and conductance. Additionally, we provide extensive experiments to validate our theoretical findings from an empirical perspective. Code of HyperClus-G is available at https://github.com/iDEA-iSAIL-Lab-UIUC/HyperClus-G.