2023/04/30 by Yu Zhu, Zhu, Yu, Boning Li +3
Computer Science · Physics and Astronomy · Social Sciences · #Advanced Computing and Algorithms #Advanced Graph Neural Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.2305.00462
openalex publication_date 2023/04/30 · openalex created_date 2023/05/03 · openalex updated_date 2026/07/28
We propose a flexible framework for defining the 1-Laplacian of a hypergraph that incorporates edge-dependent vertex weights. These weights are able to reflect varying importance of vertices within a hyperedge, thus conferring the hypergraph model higher expressivity than homogeneous hypergraphs. We then utilize the eigenvector associated with the second smallest eigenvalue of the hypergraph 1-Laplacian to cluster the vertices. From a theoretical standpoint based on an adequately defined normalized Cheeger cut, this procedure is expected to achieve higher clustering accuracy than that based on the traditional Laplacian. Indeed, we confirm that this is the case using real-world datasets to demonstrate the effectiveness of the proposed spectral clustering approach. Moreover, we show that for a special case within our framework, the corresponding hypergraph 1-Laplacian is equivalent to the 1-Laplacian of a related graph, whose eigenvectors can be computed more efficiently, facilitating the adoption on larger datasets.