图级聚类不再把多类样本挤进少数簇:S3GLC用谱签名补全局拓扑,REDDIT-12K准确率提升14.6%
核心概要
图级聚类要把一组图按语义分成若干组,但常用的GIN编码器看不到全局拓扑,多类场景下深度聚类还会把样本挤进少数簇。S3GLC把邻接矩阵特征值构成的谱签名作为图编辑距离的严格下界,与GIN的局部空间表示融合,并用最优传输的Sinkhorn-Knopp归一化约束簇规模。在10个真实数据集、15个基线上,它在REDDIT-12K上ACC提升14.6%,在DD上NMI提升35.2%。
深度剖析
图级聚类现在可以同时利用全局拓扑和局部邻域信息,而不必只依赖GIN编码器给出的图级向量。 GIN与1-WL测试的判别力等价,无法区分某些非同构图,而图编辑距离虽能刻画这种差异却是NP难问题。 在10个真实数据集上与15个基线比较,REDDIT-12K上ACC提升14.6%,DD上NMI提升35.2%。
方法为每张图单独计算一个谱签名,用邻接矩阵排序特征值的欧氏距离近似图编辑距离。 Hoffman-Wielandt不等式保证这一距离是图编辑距离的严格下界,因此无需逐对求解NP难的匹配问题。 谱签名只取每张图邻接矩阵的前若干个最大特征值,可在小型稀疏矩阵上直接求解。
谱签名与GIN空间表示通过联合流形保持稀疏回归融合,聚类目标则用最优传输施加等分约束。 现有深度聚类只最小化软分配与伪标签的KL散度,缺少簇规模约束,多类数据上易出现簇坍缩。 Sinkhorn-Knopp算法求解带熵正则的传输问题,使目标分布行列双重归一化;在ENZYMES上DCGLC与DGLC的划分坍缩比远高于真实标签。
启示与展望
演示范围是10个真实图数据集上的无监督图级聚类,覆盖分子、生物和社交网络三类数据,类别数从二类到多类;方法面向同质、静态图结构。作者提出后续将算法扩展到异质图或动态图数据。
作者指出当前设计主要针对同质图,且局限于静态图结构。超参数分析显示谱签名维度增大到一定程度后性能会下降,融合特征维度过大也会使指标变差。
