利用节点属性提升图聚类精度,实现快速精准的局部社区发现。
Adaptive Local Clustering over Attributed Graphs
- 将局部聚类建模为双向扩散分布估计,融合拓扑与属性信息。
- 在8个真实数据集上优于17种对比方法,速度最快快于对手数个数量级。
- 适合处理带噪声链接的大规模图,尤其适用于个性化推荐场景。
给定一个图 $G$ 和种子节点 $v_s$,局部图聚类(LGC)的目标是高效识别围绕 $v_s$ 的子图 $C_s$(即局部聚类),时间复杂度接近 $C_s$ 的大小。该方法无需访问全图即可生成个性化聚类,适用于大规模图的众多应用。然而,现有方法多依赖图的拓扑连接,易受真实图中常见缺失或噪声链接的影响。本文通过结合图结构与节点属性的互补性来提升聚类质量。首先,将LGC形式化为双向扩散分布(BDD)的估计,以捕捉带属性时的多跳相似性。提出LACA方法:包含(i)快速且理论保障的属性预处理技术,(ii)具严格理论保证并加速收敛的向量扩散算法,(iii)高效的三步BDD近似方案。在8个真实数据集上与17个对比方法比较,结果表明LACA在聚类质量上全面领先,同时速度提升达数个数量级。代码已开源:https://github.com/HaoranZ99/alac。
原文摘要 · Abstract (English)
Given a graph $G$ and a seed node $v_s$, the objective of local graph clustering (LGC) is to identify a subgraph $C_s \in G$ (a.k.a. local cluster) surrounding $v_s$ in time roughly linear with the size of $C_s$. This approach yields personalized clusters without needing to access the entire graph, which makes it highly suitable for numerous applications involving large graphs. However, most existing solutions merely rely on the topological connectivity between nodes in $G$, rendering them vulnerable to missing or noisy links that are commonly present in real-world graphs. To address this issue, this paper resorts to leveraging the complementary nature of graph topology and node attributes to enhance local clustering quality. To effectively exploit the attribute information, we first formulate the LGC as an estimation of the bidirectional diffusion distribution (BDD), which is specialized for capturing the multi-hop affinity between nodes in the presence of attributes. Furthermore, we propose LACA, an efficient and effective approach for LGC that achieves superb empirical performance on multiple real datasets while maintaining strong locality. The core components of LACA include (i) a fast and theoretically-grounded preprocessing technique for node attributes, (ii) an adaptive algorithm for diffusing any vectors over $G$ with rigorous theoretical guarantees and expedited convergence, and (iii) an effective three-step scheme for BDD approximation. Extensive experiments, comparing 17 competitors on 8 real datasets, show that LACA outperforms all competitors in terms of result quality measured against ground truth local clusters, while also being up to orders of magnitude faster. The code is available at https://github.com/HaoranZ99/alac.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。