Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering
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 c...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Frontiers Media S.A.
2023-02-01
|
| Series: | Frontiers in Big Data |
| Subjects: | |
| Online Access: | https://www.frontiersin.org/articles/10.3389/fdata.2023.1020173/full |
| _version_ | 1828010894994440192 |
|---|---|
| author | Yu Zhu Santiago Segarra |
| author_facet | Yu Zhu Santiago Segarra |
| author_sort | Yu Zhu |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T09:07:06Z |
| format | Article |
| id | doaj.art-da55900fcced4c57b53a951c9d883b5f |
| institution | Directory Open Access Journal |
| issn | 2624-909X |
| language | English |
| last_indexed | 2024-04-10T09:07:06Z |
| publishDate | 2023-02-01 |
| publisher | Frontiers Media S.A. |
| record_format | Article |
| series | Frontiers in Big Data |
| spelling | doaj.art-da55900fcced4c57b53a951c9d883b5f2023-02-21T06:45:58ZengFrontiers Media S.A.Frontiers in Big Data2624-909X2023-02-01610.3389/fdata.2023.10201731020173Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clusteringYu ZhuSantiago SegarraWe 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.https://www.frontiersin.org/articles/10.3389/fdata.2023.1020173/fullsubmodular hypergraphsp-Laplacianspectral clusteringedge-dependent vertex weightsdecomposable submodular function minimization |
| spellingShingle | Yu Zhu Santiago Segarra Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering Frontiers in Big Data submodular hypergraphs p-Laplacian spectral clustering edge-dependent vertex weights decomposable submodular function minimization |
| title | Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering |
| title_full | Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering |
| title_fullStr | Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering |
| title_full_unstemmed | Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering |
| title_short | Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering |
| title_sort | hypergraphs with edge dependent vertex weights p laplacians and spectral clustering |
| topic | submodular hypergraphs p-Laplacian spectral clustering edge-dependent vertex weights decomposable submodular function minimization |
| url | https://www.frontiersin.org/articles/10.3389/fdata.2023.1020173/full |
| work_keys_str_mv | AT yuzhu hypergraphswithedgedependentvertexweightsplaplaciansandspectralclustering AT santiagosegarra hypergraphswithedgedependentvertexweightsplaplaciansandspectralclustering |