【精选】快速上手：图聚类入门 Graph Clustering

硕士研究工作基本告一段落了，静候佳音中～ 其实一直想总结一下图节点聚类的一些工作，算是一个逗号吧。 个人总结，若有错误欢迎指正。

本文从问题定义入手，再到近几年的工作，最后进行横向对比，并提供一些个人向的future work，以供参考。

这部分介绍一下聚类、图、图神经网络。都掌握的不错的同学可以直接跳过。

聚类就是在未知标签的前提下，将样本集合分为多个子集合，每个子集合都有不同的标签。这里举个例子，如图所示： 针对用户群，我们需要根据其隐式特征挖掘其内在关联，来给它们进行无标签分类。这样的分类结果往往会有一些特殊语义，如图所示这样的用户群划分可能会潜在具有一定的运动兴趣偏好。当我们能够验证部分用户的运动兴趣符合的时候，其同集合的其他节点往往也有着相同的倾向，这样我们就可以设计出一些个性化的应用了，如电商领域的购物兴趣、小视频领域的观看兴趣等。

就聚类而言其定义是十分简单的：

聚类(Clustering) 是按照某个特定标准(如距离)把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。——知乎

在这里我们来提出一些问题：

关于第一个问题，在西瓜书机器学习里面有详细介绍，即相似性度量，如欧式距离、闵可夫斯基距离、马氏距离、余弦相似度、皮尔逊相关系数和KL散度等。

KL散度不能称之为距离（需满足非负性、同一性、对称性、直递性），因为其不满足交换性，不过有一个替代版本可用即JS距离

第二个问题也很简单，也就是K-means、谱聚类这些方法，当然近年也有关于深度嵌入聚类（Deep Embedding Clustering，DEC）的相关研究成果，来将深度学习引入特征聚类领域。下面提供简单的介绍：

Xie, Junyuan, Ross Girshick, and Ali Farhadi. “Unsupervised deep embedding for clustering analysis.” International conference on machine learning. PMLR, 2016.

第三点是大家接触较少的点。就仿佛题目总是让你去将这堆数据分为3类、分为5类，但是却不知道为何是3类5类。其实也是有一些方法的，如肘部法则SSE、轮廓系数等。

知乎：https://zhuanlan.zhihu.com/p/98918878

这里再列一下我在论文中看到的一个方法，度量可概化性G：

现在现实世界从互联网技术（IT）时代基本进入了数据技术（DT）时代。数据作为新一代的核心驱动力，受到越来越大的关注和应用，如数据建模、数据挖掘、数据科学、数据安全等。 数据是信息的载体。信息包括结构化信息和非结构信息。

结构化信息（欧式数据）

非结构信息（非欧式数据）

下图展示了像素组成的图片（结构信息）和社交网络示意（非结构信息）：

非结构数据往往可以使用关系进行表示，即被视为关系数据。而关系数据的主流数据结构就是图结构。看到这有的人会说了，图不就是节点和边嘛，有啥可讲的。

其实不然，大家传统认知的图只是普通图，但是研究可并不会受限于普通图。这里我们给出一些研究前沿比较热衷的图的种类，以供大家细化自己的工作方向。

在实际应用的时候，这些图都会有不同的效果，其实最核心的地方在于，如何定义节点和边，也就是如何解释节点和边成为你的方法是否work的重点。

图神经网络（Graph Neural Network, GNN）将图学习引入了神经网络时代，近年来更是最热的研究热点，如图所示（图有点老，请勿吐槽）。 图学习的本质目的在于，将结构信息作为特征的一环，融入学习系统来更好的进行学习任务。对于GNN而言其往往有两类特征，节点特征、结构特征。由于结构将节点们进行连接，形成各种链路，所以GNN早期是循环神经网络（RNN）的相关研究成果变迁而来。不过也有一些工作是直接从结构信息入手，如最有名的GCN。

Kipf, Thomas N., and Max Welling. “Semi-supervised classification with graph convolutional networks.” arXiv preprint arXiv:1609.02907 (2016). 目前GCN已经有好几代的迭代，大家也可以进行了解

关于GNN的知识还是建议大家从博客或者一些survey入手。下面提供一些不错的survey文章，其中第一篇非常值得一看。

Wu, Zonghan, et al. “A comprehensive survey on graph neural networks.” IEEE transactions on neural networks and learning systems 32.1 (2020): 4-24. Zhou, Jie, et al. “Graph neural networks: A review of methods and applications.” AI Open 1 (2020): 57-81. Zhang, Ziwei, Peng Cui, and Wenwu Zhu. “Deep learning on graphs: A survey.” IEEE Transactions on Knowledge and Data Engineering (2020).

看到这相信大家应该能猜测到图节点聚类到底是怎么一回事了。图节点聚类也就是针对具有图结构的节点集做聚类研究。

其实图节点聚类也有不少的细化。这里我们根据节点是否提供特征可以分为：

这里1是兼容2的，不过2也有一些专门的独立工作，如对比学习模型GCC(2020[KDD] GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training)，感兴趣的可以参考。

我们核心讨论对象是更加具有普适性的属性图聚类。

其研究本质就是如何更好的融合结构特征和节点特征，以完成特征的高效融合来完成聚类标签的生成。

不仅只有图聚类任务可以完成聚类要求，图嵌入、图对比学习学习到的Embedding信息也是融合结构特征和节点特征的有效方法，其也可以直接用来做聚类对比研究。 其实有了上面的基础，我们可以直接对模型进行细致讨论了。

AGC的流程如下： 这篇论文有两个贡献：

下面是他的模型表现：

其本质由图注意力自动编码器组成，进而通过KL loss来优化嵌入表示，最终达到优化聚类的效果。其算法流程如下： 下面是实验效果：

SDCN本质由两部分组成：

其本质：图卷积神经网络GCN+自动编码器AE+深度嵌入聚类DEC

下面是他的算法效果：

图嵌入领域目的在于给图中节点学习到融合自身特征和图结构信息的低维特征表示，这与聚类的目的基本相仿。图嵌入领域也有很多工作在聚类方面也有很好的效果。

本文先针对GAE模型（如上图）提出三个缺点：

针对于此，作者提出了自适应图编码器Adaptive Graph Encoder (AGE)： AGE针对GAE提出了两个新颖的改变：

第一，针对经典的图卷积滤波器进行改造。通过针对真实图结构进行特征分解，发现基本特征值处于0～1.5之间。所以为了更好的综合精细度和覆盖率，这里将频率响应函数设置为 p ( λ p ) = 1 − 2 / 3 × λ q p(\lambda_p)=1-2/3\times\lambda_q p(λp​)=1−2/3×λq​（是不是和上面的AGC）有一丝丝的相像。然后通过多层的滤波学习到最好的融合特征。

第二，针对GAE的端到端学习，这里将其进行解耦，先通过滤波器进行特征与图结构的无监督融合。第二步才通过与图邻接矩阵比较来保留更加完整的图结构。此处并不是直接传统的采用了GAE的方式，通过最小化邻接矩阵元素交叉熵的方法来学习，而是通过一种特别新颖的方式来进行： 将所有节点之间的相似度进行计算，进行降序排序。相似度最高的部分节点对和相似度最低的部分节点对才进行对比学习，来优化MLP，进而学习到原始图嵌入到低维空间的最佳映射。

尽管作者提出了很多有意思的思路和创新点，但是笔者认为该模型存在着很大的一个缺陷：超参数太多，实践成本高，比如融合特征需要进行滤波的阶次、第二步中正负样本对比例的选择。且文中没有给出具体的参数选择方案，同时各个数据所用的参数没有什么规律性。

下面给出该模型的效果： 聚类效果： 注：最后一格描述的是解耦式结构的消融实验和对比实验。

链路预测效果：

图对比学习是近期最热的topic之一了，也可以用来做聚类任务，并且取得了不错的效果。关于这个建议阅读我的另一篇博文，来更加细致的了解：

图对比学习入门

（浅谈、浅谈） 直接列吧！

这里分享一下我收集的论文集吧，希望有所帮助。入门级科研无非是大量输入+持续思考+定期产出。

2009[Australas J. Combin]Note on the normalized Laplacian eigenvalues of signed graphs.pdf 2013[IEEE Signal Proc.] The Emerging Field of Signal Processing on Graphs 2014[KDD] DeepWalk- online learning of social representations 2017[IEEE SPM]Geometric deep learning- going beyond Euclidean data 2020[ICML]Graph Structure of Neural Networks 2021[AAAI] Identity-aware Graph Neural Networks

2018[arxiv]Graph Convolutional Neural Networks for Web-Scale Recommender Systems 2019[CIMK]Fi-GNN- Modeling Feature Interactions via Graph Neural Networks for CTR Prediction 2019[CVPR]Chen_Multi-Label Image Recognition With Graph Convolutional Networks 2019[CVPR]Two-Stream Adaptive Graph Convolutional Networks for Skeleton-Based Action Recognition 2019[Gene]Gene selection for microarray data classification via adaptive hypergraph embedded dictionary learning 2019[ICCV]Graph-Based Object Classification for Neuromorphic Vision Sensing

2016[ICLR][GGNN] Gated Graph Sequence Neural Networks 2017[ICLR] [GCN] semi-supervised classification with graph convolutional networks 2018[ICLR] [GAT] Graph Attention Networks 2019[ICCV]DeepGCNs- Can GCNs Go as Deep as CNNs? 2019[ICLR] [GIN] How Powerful are Graph Neural Networks 2019[ICML] MixHop- Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing 2019[UAI] [NGCN] N-GCN- Multi-scale Graph Convolution for Semi-supervised Node Classification 2020[AAAI] [MRA-BGCN] Multi-Range Attentive Bicomponent Graph Convolutional Network for Traffic Forecasting 2020[arxiv] [C&S] Combining Label Propagation and Simple Models Out-performs Graph Neural Networks

2016[KDD]Structural Deep Network Embedding 2016[NIPS]Variational Graph Auto-Encoders 2019[ICCV] [GALA] Symmetric Graph Convolutional Autoencoder for Unsupervised Graph Representation Learning 2020[arxiv] [AGE] Adaptive Graph Encoder for Attributed Graph Embedding

2019[ICLR] [DGI] Deep Graph Informax 2019[ICLR] [DIM] Learning deep representations by mutual information estimation and maximization 2020[CVPR] [MoCo] Momentum Contrast for Unsupervised Visual Representation Learning 2020[ICLR] InfoGraph- Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization 2020[ICLR] [InfoGraph] InfoGraph- Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization 2020[ICML] Contrastive Multi-View Representation Learning on Graphs 2020[ICML] [CoGE] Contrastive Graph Neural Network Explanation 2020[KDD] [GCC] GCC- Graph Contrastive Coding for Graph Neural Network Pre-Training 2020[NeurIPS] [GraphCL] (Appendix) Graph Contrastive Learning with Augmentations 2020[NeurIPS] [GraphCL] Graph Contrastive Learning with Augmentations 2020[WWW] [GMI] Graph Representation Learning via Graphical Mutual Information Maximization 2020[arxiv] [GCA] Graph Contrastive Learning with Adaptive Augmentation 2020[arxiv] [GRACE] Deep Graph Contrastive Representation Learning

2014[AAAI]Learning deep representations for graph clustering 2016[ICML]Unsupervised Deep Embedding for Clustering Analysis 2018[ECCV]Deep Clustering for Unsupervised Learning of Visual Features 2019[IJCAI] [AGC] Attributed Graph Clustering via Adaptive Graph Convolution 2019[IJCAI] [DAEGC] Attributed Graph Clustering： A Deep Attentional Embedding Approach 2020[IJCAI] [MAGCN] Multi-View Attribute Graph Convolution Networks for Clustering 2020[WWW] [SDCN] Structural Deep Clustering Network 2020[arxiv] [DMON] Graph Clustering with Graph Neural Networks 2020[arxiv]Embedding Graph Auto-Encoder with Joint Clustering via Adjacency Sharing 2020[arxiv]Unsupervised Domain Adaptation via Structurally Regularized Deep Clustering