![[2411.03331] Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2411.03331] Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality
Summary
This paper explores hypergraphs as weighted directed self-looped graphs, focusing on their spectral properties, clustering algorithms, and the Cheeger inequality, proposing a new algorithm called HyperClus-G for improved spectral clustering.
Why It Matters
Understanding hypergraphs is crucial in machine learning, particularly for modeling complex relationships. This research addresses gaps in existing algorithms and theoretical frameworks, providing a foundation for future developments in spectral clustering and enhancing the application of hypergraphs in various fields.
Key Takeaways
- Introduces edge-dependent vertex weights (EDVW) as a generalized modeling method for hypergraphs.
- Presents a unified random walk-based formulation for hypergraph properties.
- Proposes HyperClus-G, a new algorithm for spectral clustering on EDVW hypergraphs.
- Demonstrates that HyperClus-G can achieve approximately optimal partitioning.
- Validates theoretical findings through extensive empirical experiments.
Computer Science > Social and Information Networks arXiv:2411.03331 (cs) [Submitted on 23 Oct 2024 (v1), last revised 20 Feb 2026 (this version, v2)] Title:Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality Authors:Zihao Li, Dongqi Fu, Hengyu Liu, Jingrui He View a PDF of the paper titled Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality, by Zihao Li and 3 other authors View PDF HTML (experimental) Abstract: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...
