Hypergraphs with Edge-Dependent Vertex Weights: p-Laplacians and Spectral Clustering
This work addresses hypergraph clustering with enhanced expressivity for applications in data analysis, though it is incremental as it builds on existing submodular hypergraph theory.
The authors tackled the problem of spectral clustering for hypergraphs with edge-dependent vertex weights (EDVW) by extending p-Laplacians and Cheeger inequalities to this model, and they proposed an efficient algorithm for the 1-Laplacian eigenvector that achieved higher clustering accuracy than traditional 2-Laplacian methods in real-world experiments.
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.