【ICML2020】图神经网络谱聚类

谱聚类(SC)是一种常用的聚类方法，该方法能够根据特征值分解找到联系密切的communities.谱聚类如果用到图网络上，一种自然而然的想法是对联系紧密的communities进行pooling，然后进行下一步的操作。但是谱分解涉及到拉普拉斯矩阵的分解，复杂度非常的高，另外如果pooling完，我们还要继续pooling,需要重新计算一次分解，这个过程是不可导的。另外谱聚类的方法没有用到节点的特征，只是根据拉普拉斯矩阵进行分解的。这篇论文非常巧妙地提出了一种minCUT的方法，可以求导，并且不需要进行谱分解，代码已经公开。

具体来看，本文提出了一种最小割的loss作为regularization,也就是下面的公式，其中L_c根据minCUT学习一个assignment matrix,使得联系紧密的communities内部更加紧凑，L_o是一个约束，约束这些assignment matrix之间不要都一样了（正交），不然所有的点都聚在一起了，这里不做过多介绍，有兴趣请查看原文，公众号后期会做进一步详细的解析，尽请关注。

https://www.zhuanzhi.ai/paper/662405fed0b0ccd3c1a375864ab42e8b