# Hypergraphs with Edge-Dependent Vertex Weights: p-Laplacians and Spectral Clustering

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 46 references that are in the map.
- First posted on arXiv 15 Aug 2022.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond](https://mlsanity.com/paper/2101.05510/) (2021)
- [Random Walks on Hypergraphs with Edge-Dependent Vertex Weights](https://mlsanity.com/paper/1905.08287/) (2019)
- [p-Laplacian Based Graph Neural Networks](https://mlsanity.com/paper/2111.07337/) (2021)
- [The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited](https://mlsanity.com/paper/1312.5179/) (2013)
- [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 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)
- [Reflection methods for user-friendly submodular optimization](https://mlsanity.com/paper/1311.4296/) (2013)
- [Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions](https://mlsanity.com/paper/1502.02643/) (2015)
- [Community detection in networks via nonlinear modularity eigenvectors](https://mlsanity.com/paper/1708.05569/) (2017)
- [Co-clustering Vertices and Hyperedges via Spectral Hypergraph Partitioning](https://mlsanity.com/paper/2102.10169/) (2021)
- [Hypergraph Cuts with Edge-Dependent Vertex Weights](https://mlsanity.com/paper/2201.06084/) (2022)

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

- [Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality](https://mlsanity.com/paper/2411.03331/) (2024)

## Abstract (arXiv)

We study p-Laplacians and spectral clustering for a recently proposed hypergraph model that incorporates edge-dependent vertex weights (EDVW). These weights can reflect different importance of vertices within a hyperedge, thus conferring the hypergraph model higher expressivity and flexibility. By constructing submodular EDVW-based splitting functions, we convert hypergraphs with EDVW into submodular hypergraphs for which the spectral theory is better developed. In this way, existing concepts and theorems such as p-Laplacians and Cheeger inequalities proposed under the submodular hypergraph setting can be directly extended to hypergraphs with EDVW. For submodular hypergraphs with EDVW-based splitting functions, we propose an efficient algorithm to compute the eigenvector associated with the second smallest eigenvalue of the hypergraph 1-Laplacian. We then utilize this eigenvector to cluster the vertices, achieving higher clustering accuracy than traditional spectral clustering based on the 2-Laplacian. More broadly, the proposed algorithm works for all submodular hypergraphs that are graph reducible. Numerical experiments using real-world data demonstrate the effectiveness of combining spectral clustering based on the 1-Laplacian and EDVW.