摘要

图聚类对于识别给定网络中的社区与群体至关重要。近年来，研究者们提出了多种适用于该任务的工具。其中，最新进展主要基于深度学习的最新成果，尤其是图神经网络（Graph Neural Networks, GNN）的应用。尽管部分方法在整体过程中考虑了图的内在拓扑结构，但令人意外的是，当前主流的聚类方法在最终的聚类分配阶段却忽略了这一关键信息，从而导致性能次优。本文提出了一种名为GSCAN（Graph Stability Clustering for Applications with Noise）的新方法，该方法同时利用节点特征与图结构进行聚类。我们基于经典的“质量过剩法”（Excess-of-Mass, EoM）构建了该方法，其核心思想是最大化聚类的稳定性。EoM方法具有多项优良特性，例如对异常值具有鲁棒性，且无需预先指定聚类数量。我们进一步将EoM扩展至适用于图的内在结构，并提出了两种后处理策略，以解决EoM的一个固有缺陷——容易过度将数据点标记为异常值。这些后处理方法充分利用了图的拓扑信息，显著提升了聚类性能，甚至优于那些端到端训练的先进聚类方法。实验表明，所提出的GSCAN方法可高效、可扩展地实现。我们的结论基于三个广泛使用的基准数据集验证。相关代码已开源，地址为：https://github.com/GraphEoM/GSCAN