Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering

Area of Science:

• Graph theory
• Machine learning
• Data science

Background:

• Hypergraph models offer greater flexibility than traditional graphs.
• Edge-dependent vertex weights (EDVW) enhance hypergraph expressivity.
• Spectral clustering is a powerful technique for data analysis.

Purpose of the Study:

• To extend spectral clustering and p-Laplacian theory to hypergraphs with EDVW.
• To develop an efficient algorithm for computing eigenvectors in EDVW hypergraphs.
• To improve clustering accuracy using a novel spectral clustering approach.

Main Methods:

• Constructing submodular EDVW-based splitting functions to convert hypergraphs.
• Extending existing p-Laplacian and Cheeger inequality concepts to EDVW hypergraphs.
• Proposing an efficient algorithm to compute the eigenvector of the hypergraph 1-Laplacian.

Main Results:

• The proposed method allows direct extension of spectral theory to EDVW hypergraphs.
• An efficient algorithm for computing the 1-Laplacian eigenvector is presented.
• Spectral clustering using the 1-Laplacian and EDVW achieved higher accuracy than 2-Laplacian methods.

Conclusions:

• The developed spectral clustering approach effectively handles hypergraphs with EDVW.
• The algorithm is applicable to all graph-reducible submodular hypergraphs.
• Numerical experiments confirm the effectiveness of the proposed method on real-world data.