转自 PaperWeekly

聚类作为经典的无监督学习算法在数据挖掘/机器学习的发展历史中留下了不可磨灭的印记。其中，经典的聚类算法 K-Means 也被选为数据挖掘十大经典算法。随着深度学习的兴起，一些工作尝试将深度学习技术（如 Autoencoder ）引入到传统聚类算法中，也取得了不错的效果。

近些年，图神经网络已经成为深度学习领域最热门的方向之一， 也在推荐/自然语言处理/计算机视觉等很多领域得到了广泛的应用。那么，能不能利用图神经网络强大的结构捕获能力来提升聚类算法的效果呢？本文梳理总结了图神经网络赋能的深度聚类算法，供大家参考。

1.1 论文动机

本文认为之前的深度聚类算法都是 two-step 的：首先学习数据的特征表示 embedding，然后基于特征表示进行数据聚类。这样所学习的数据 embedding 并不是任务导向的。那么，如果能够在学习 embedding 的过程中，针对聚类任务做一些针对性的设计，那么学习到的 embedding 自然可以实现更好的聚类。

针对上述问题，本文提出了一种聚类导向的深度算法 Deep Attentional Embedded Graph Clustering (DAEGC)。DAEGC 一边通过图神经网络来学习节点表示，一边通过一种自训练的图聚类增强同一簇节点之间的内聚性。

下图清晰的展示 two-step 和本文所提出的 DAEGC 的差异。

1.2 模型介绍

下图展示了 DAEGC 的模型框架：

可以看出，整个 DAEGC 主要包含两大模块：带有注意力机制的图自编码器+自训练聚类。

1.3 带有注意力机制的图自编码器

这里就是经典的 GAE 架构：通过对邻居的聚合来学习节点表示，然后利用节点对的内积来重构原始网络结构。比较有特色的部分就是结合注意力机制来学习邻居的权重， 这样可以更好的学习节点表示。

下式展示了融合注意力机制的 GAE 是如何聚合邻居信息来更新节点表示的。本质上就是对邻居的加权平均。

其中，z^l_i,z^{l+1}_i，分别是聚合邻居信息前后的节点i的表示， N_i代表节点 的邻居集合， erfa_{ij表示了节点对 (i, j) 之间的注意力权重 。

有了节点表示后， GAE 可以通过计算节点对的内积来重构原始网络结构，进而实现无监督的节点表示学习。

1.4 自训练聚类

GAE 所学习到的节点表示只是为了更好的重构网络结构，和聚类并没有直接联系。自训练聚类模块就是对 GAE 所学习到的 embedding 进行约束和整合，使其更适合于聚类任务。假定聚类中为\mu_u ， 那么节点i 属于某个类别的概率q_{iiu}， 如下式所示：

这里，q_{iu} 可以看作是节点的分配的分布。进一步的， 为了引入聚类信息来实现聚类导向的节点表示， 我们需要迫使每个节点与相应的聚类中心更近一些，以实现所谓的类内距离最小，类间距离最大。因此，我们定义了如下的目标分布

在目标分布中， 通过二次方q_{iu} 可以实现一种”强调”的效果（二次方后， 分布会变得更加尖锐，也更置信）。在训练过程中，分布 实际起到了一种标签的效果。最后，通过计算两个分布之间的 KL 散度，来实现互相约束，也就是所谓的自训练 。

综合起来，模型最终的损失函数为：

节点i 的所处于的簇 s_i（也可以理解为其标签）可以通过下式计算：

1.5 论文实验

作者在 3 个数据集上进行了实现， DAEGC 在大部分情况下都取得了最好的效果 。

2.1 论文动机

深度自编码器可以通过多层非线性编码来提取特征信息，而图神经网络可以聚合邻居信息来充分挖掘结构信息。为了同时实现对特征的降维抽取和对结构信息的挖掘， 本文提出了 Structural Deep Clustering Network （SDCN）。

通过堆叠多层 GNN， SDCN 实现了对高阶结构信息的捕获。同时，受益于自编码器和 GNN 的自监督， 这里的多层 GNN 并不会出现所谓的过平滑现象。过平滑现象指的是，随着层数的增加，GNN 所学习到的节点表示逐渐变得不可区分。

2.2 模型介绍

在开始介绍模型之前，需要说明的是：如果数据集本身并没有图结构，作者将会通过计算节点之间的 Top-K 相似性利用 KNN 手动构建一张图。下面是两种相似性计算方法：Heat Kernel 和 Dotp roduct。

下图展示了整个 SDCN 的模型架构图。可以看出，整个模型主要包含 3 个部分：GCN 模块，DNN 模块和双重自监督模块。

2.3 DNN模块

这里是一个经典的自编码器。编码器将输入X （也就是  H^{(0)}）通过神经网络编码为隐表示H ；解码器将隐表示H 解码为 /hatT(X)（也就是 H^{(L)}）。

可以看出，通过重构 loss 和多层非线性映射，H^{(l)} 可以较好的反映节点的特征信息。

2.4 GCN模块

另一方面， GCN 可以聚合邻居信息来更新节点表示，其更新过程如下：

2.5 双重自监督模块

最后是一个双重自监督模块，其作用体现在两个方面：（1）通过 GCN 部分和 DNN 部分的互相监督可以实现模型的无监督学习。（2）通过引入聚类信息来更好的学习任务导向的节点表示。

与上一篇 19 IJCAI Attributed Graph Clustering：A Deep Attentional Embedding Approach 类似， SDCN 也设计了两个分布。这里不再赘述，详见上一篇的解读。

节点的类别分布为：

2.6 论文实验

作者在 6 个数据集上做了大量的有效性实验。可以看出， SDCN 在所有数据集上都取得了大幅的提升。

比较有意思的实验是模型层数实验，如下图所示。可以看出，随着层数的增加，模型的效果会有大幅度的提升，并没有出现过平滑现象。

除此之外，作者还测试了不同的混合系数 对模型效果的影响。

3.1 论文动机

3.2.1 谱域的图卷积

这里首先简单回顾一下谱域的图卷积：

到这里，也就可以聚合 k 阶邻居来学习节点表示了，也就是所谓的 k 阶图卷积。同时注意，卷积过程中抑制了高频信号，更多的低频信号（更符合聚类要求）被捕获了。

3.2.2 自适应k选择

现在还剩一个问题需要解决，图卷积的 k 阶该如何确定？

这里作者用了一个启发式的方法：逐渐增加 k， 当类内距离开始变小时，停止搜索。内类距离如下所示：

可以看出，这里 k 的选择也是比较符合聚类的要求（类内距离最小，类间距离最大）。

3.3 论文实验

作者在 4 个经典数据集上进行了实验。总的来说，AGC 的效果还是不错的。

4.1 论文动机

本文与之前几篇的类似，也是用 GNN 来学习适合于聚类任务的节点表示。比较特别的是，本文同时考虑了 K-Mean 聚类和谱聚类来实现更好的聚类。

4.2 模型介绍

下图展示了本文所提出的 Embedding Graph Auto-Encoder with JOint Clustering via Adjacency Sharing (EGAE-JOCAS) 的整体框架。

4.2.1 图自编码器

首先，作者利用图卷积神经网络来学习节点的表示 Z， 然后利用节点表示来尝试重构原始图结构。

4.2.2 联合聚类

4.3 论文实验

最后，作者在四个数据集上进行了实验。总的来说，EGAE-JOCAS 在所有数据集上都取得了明显的提升。

总结

聚类是机器学习/数据挖掘的一个基础性问题。从传统聚类到深度聚类以及现在图神经网络赋能的聚类， 各种各样的聚类算层出不穷，也在很多领域得到了广泛的应用。考虑到图神经网络对结构信息的捕获能力，在涉及到群体结构的聚类任务上，本文所介绍的聚类算法应该会取得更大的提升。