用压缩感知提升图上局部聚类，少标签下效果领先
Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methods
- 基于图拉普拉斯的稀疏解法，结合随机采样与扩散提取局部簇
- 在低标签率下超越现有方法，理论证明结果正确性
- 适合标签稀缺的图数据聚类，如社交网络、生物网络
局部聚类旨在不依赖图整体结构信息的情况下，识别大规模图中的特定子结构。这些子结构通常远小于整个图，因此可通过求解与图拉普拉斯相关的线性系统的稀疏解来实现。本文首先提出一种在极少量标注数据下识别特定局部簇的方法，称为半监督局部聚类；随后将其扩展至无标签信息的无监督场景。所提方法通过随机采样图，进行局部簇提取的扩散过程，并分析结果间的重叠以发现每个簇。我们建立了任意两节点共属同一簇的充要条件，并严格证明了方法的有效性。大量实验表明，该方法在低标签率情况下达到当前最优性能。
原文摘要 · Abstract (English)
Local clustering aims to identify specific substructures within a large graph without any additional structural information of the graph. These substructures are typically small compared to the overall graph, enabling the problem to be approached by finding a sparse solution to a linear system associated with the graph Laplacian. In this work, we first propose a method for identifying specific local clusters when very few labeled data are given, which we term semi-supervised local clustering. We then extend this approach to the unsupervised setting when no prior information on labels is available. The proposed methods involve randomly sampling the graph, applying diffusion through local cluster extraction, then examining the overlap among the results to find each cluster. We establish the co-membership conditions for any pair of nodes, and rigorously prove the correctness of our methods. Additionally, we conduct extensive experiments to demonstrate that the proposed methods achieve state of the art results in the low-label rates regime.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。