论文标题
具有边缘依赖的顶点权重的超图：p-laplacians和频谱聚类
Hypergraphs with Edge-Dependent Vertex Weights: p-Laplacians and Spectral Clustering
论文作者
论文摘要
我们研究了p-laplacians和光谱聚类，以融合了边缘依赖性顶点权重（EDVW）的最近提出的超图模型。这些权重可以反映在超边缘内顶点的不同重要性，从而赋予超图模型更高的表达性和灵活性。通过构建基于EDVW的基于EDVW的分裂函数，我们将带有EDVW的超图转换为频谱理论更好地开发的谱图。通过这种方式，现有的概念和定理（例如p-laplacians和cheeger不平等现象）可以直接扩展到具有EDVW的超图。对于具有基于EDVW的分裂函数的下管超图，我们提出了一种有效的算法来计算与HyperGraph 1-Laplacian的第二小特征值相关的特征向量。然后，我们利用此特征向量来聚类顶点，比基于2-Laplacian的传统光谱聚类获得更高的聚类精度。从更广泛的角度来看，所提出的算法适用于所有可降低图形的亚物种超图。使用现实世界数据的数值实验证明了基于1-Laplacian和EDVW结合光谱聚类的有效性。
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.
