Zhu Yu, Segarra Santiago
Department of Electrical and Computer Engineering, Rice University, Houston, TX, United States.
Front Big Data. 2023 Feb 21;6:1020173. doi: 10.3389/fdata.2023.1020173. eCollection 2023.
We study -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 -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.
我们针对最近提出的一种包含边依赖顶点权重（EDVW）的超图模型研究 -拉普拉斯算子和谱聚类。这些权重可以反映超边内顶点的不同重要性，从而赋予超图模型更高的表现力和灵活性。通过构建基于次模 EDVW 的分裂函数，我们将具有 EDVW 的超图转换为次模超图，对于次模超图，谱理论发展得更好。通过这种方式，在次模超图设置下提出的诸如 -拉普拉斯算子和切赫不等式等现有概念和定理可以直接扩展到具有 EDVW 的超图。对于具有基于 EDVW 分裂函数的次模超图，我们提出了一种有效算法来计算与超图 1 -拉普拉斯算子的第二小特征值相关的特征向量。然后，我们利用这个特征向量对顶点进行聚类，实现比基于 2 -拉普拉斯算子的传统谱聚类更高的聚类精度。更广泛地说，所提出的算法适用于所有可图约化的次模超图。使用真实世界数据的数值实验证明了基于 1 -拉普拉斯算子和 EDVW 的谱聚类相结合的有效性。
