图神经网络时代的深度聚类
©PaperWeekly 原创 · 作者｜纪厚业
学校｜北京邮电大学博士生
研究方向｜图神经网络和推荐系统
聚类作为经典的无监督学习算法在数据挖掘/机器学习的发展历史中留下了不可磨灭的印记。其中，经典的聚类算法 K-Means 也被选为数据挖掘十大经典算法。随着深度学习的兴起，一些工作尝试将深度学习技术（如 Autoencoder ）引入到传统聚类算法中，也取得了不错的效果。
近些年，图神经网络已经成为深度学习领域最热门的方向之一， 也在推荐/自然语言处理/计算机视觉等很多领域得到了广泛的应用。
IJCAI 2019
本文认为之前的深度聚类算法都是 two-step 的：首先学习数据的特征表示 embedding，然后基于特征表示进行数据聚类。这样所学习的数据 embedding 并不是任务导向的。那么，如果能够在学习 embedding 的过程中，针对聚类任务做一些针对性的设计，那么学习到的 embedding 自然可以实现更好的聚类。
针对上述问题，本文提出了一种聚类导向的深度算法 Deep Attentional Embedded Graph Clustering (DAEGC)。DAEGC 一边通过图神经网络来学习节点表示，一边通过一种自训练的图聚类增强同一簇节点之间的内聚性。
下图清晰的展示 two-step 和本文所提出的 DAEGC 的差异。
可以看出，整个 DAEGC 主要包含两大模块：带有注意力机制的图自编码器+自训练聚类。
1.3 带有注意力机制的图自编码器
这里就是经典的 GAE 架构：通过对邻居的聚合来学习节点表示，然后利用节点对的内积来重构原始网络结构。比较有特色的部分就是结合注意力机制来学习邻居的权重， 这样可以更好的学习节点表示。
下式展示了融合注意力机制的 GAE 是如何聚合邻居信息来更新节点表示的。本质上就是对邻居的加权平均。
有了节点表示后， GAE 可以通过计算节点对的内积来重构原始网络结构，进而实现无监督的节点表示学习。
1.4 自训练聚类
1.5 论文实验
作者在 3 个数据集上进行了实现， DAEGC 在大部分情况下都取得了最好的效果。
WWW 2020
代码链接：https://github.com/461054993/SDCN
深度自编码器可以通过多层非线性编码来提取特征信息，而图神经网络可以聚合邻居信息来充分挖掘结构信息。为了同时实现对特征的降维抽取和对结构信息的挖掘， 本文提出了 Structural Deep Clustering Network （SDCN）。
通过堆叠多层 GNN， SDCN 实现了对高阶结构信息的捕获。同时，受益于自编码器和 GNN 的自监督， 这里的多层 GNN 并不会出现所谓的过平滑现象。过平滑现象指的是，随着层数的增加，GNN 所学习到的节点表示逐渐变得不可区分。
2.2 模型介绍
在开始介绍模型之前，需要说明的是：如果数据集本身并没有图结构，作者将会通过计算节点之间的 Top-K 相似性利用 KNN 手动构建一张图。下面是两种相似性计算方法：Heat Kernel 和 Dotp roduct。
下图展示了整个 SDCN 的模型架构图。可以看出，整个模型主要包含 3 个部分：GCN 模块，DNN 模块和双重自监督模块。
2.4 GCN模块
另一方面， GCN 可以聚合邻居信息来更新节点表示，其更新过程如下：
2.5 双重自监督模块
最后是一个双重自监督模块，其作用体现在两个方面：（1）通过 GCN 部分和 DNN 部分的互相监督可以实现模型的无监督学习。（2）通过引入聚类信息来更好的学习任务导向的节点表示。
与上一篇 19 IJCAI Attributed Graph Clustering：A Deep Attentional Embedding Approach 类似， SDCN 也设计了两个分布。这里不再赘述，详见上一篇的解读。
节点的类别分布为：
同样的，也是最小化两个分布之间的 KL 散度：
模型完整损失函数如下：
2.6 论文实验
作者在 6 个数据集上做了大量的有效性实验。可以看出， SDCN 在所有数据集上都取得了大幅的提升。
比较有意思的实验是模型层数实验，如下图所示。可以看出，随着层数的增加，模型的效果会有大幅度的提升，并没有出现过平滑现象。
IJCAI 2019
3.1 论文动机
与上一篇 SDCN 相似，本文也利用了高阶结构信息（多层 GNN）来提升聚类的效果。尽管这两篇非常相似，它们也是有一些差异的：1） 本文所提出的AGC是从图信号处理谱图理论的角度来理解 GNN 并增强了聚类效果；2） 本文所涉及的 AGC 可以自适应的选择高阶信息的阶数，而 SDCN 则需要手动指定超参数。
这里首先简单回顾一下谱域的图卷积：
为什么这里需要涉及到“平滑”这个概念呢？图上的“平滑”程度反映了相邻节点的相似程度。图上的高频意味着不平滑，特征值大; 图上的低频意味着平滑，特征值小。
那么在一组基中， 相对平滑的图信号实际上是有利于聚类的。因为聚类的目的是把相似的节点放到一起。
一阶图卷积可以写作：
到这里，也就可以聚合 k 阶邻居来学习节点表示了，也就是所谓的 k 阶图卷积。同时注意，卷积过程中抑制了高频信号，更多的低频信号（更符合聚类要求）被捕获了。
现在还剩一个问题需要解决，图卷积的 k 阶该如何确定？
这里作者用了一个启发式的方法：逐渐增加 k， 当类内距离开始变小时，停止搜索。内类距离如下所示：
可以看出，这里 k 的选择也是比较符合聚类的要求（类内距离最小，类间距离最大）。
3.3 论文实验
作者在 4 个经典数据集上进行了实验。总的来说，AGC 的效果还是不错的。
arXiv 2020
论文标题：Embedding Graph Auto-Encoder with Joint Clustering via Adjacency Sharing
论文来源：arXiv 2020
论文链接：https://arxiv.org/abs/2002.08643
4.1 论文动机
本文与之前几篇的类似，也是用 GNN 来学习适合于聚类任务的节点表示。比较特别的是，本文同时考虑了 K-Mean 聚类和谱聚类来实现更好的聚类。
4.2 模型介绍
下图展示了本文所提出的 Embedding Graph Auto-Encoder with JOint Clustering via Adjacency Sharing (EGAE-JOCAS) 的整体框架。
联合聚类的公式如下图所示：
第二项是谱聚类，直观的理解就是，相近的节点应该属于相同的簇。回顾上一篇的"平滑程度"，可以发现它们有异曲同工之妙。
最后，作者在四个数据集上进行了实验。总的来说，EGAE-JOCAS 在所有数据集上都取得了明显的提升。
总结
聚类是机器学习/数据挖掘的一个基础性问题。从传统聚类到深度聚类以及现在图神经网络赋能的聚类， 各种各样的聚类算层出不穷，也在很多领域得到了广泛的应用。
点击以下标题查看更多往期内容：
让你的论文被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。
总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。
PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学习心得或技术干货。我们的目的只有一个，让知识真正流动起来。
📝 来稿标准：
• 稿件确系个人原创作品，来稿需注明作者个人信息（姓名+学校/工作单位+学历/职位+研究方向）
• 如果文章并非首发，请在投稿时提醒并附上所有已发布链接
• PaperWeekly 默认每篇文章都是首发，均会添加“原创”标志
📬 投稿邮箱：
• 投稿邮箱：hr@paperweekly.site
• 所有文章配图，请单独在附件中发送
• 请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通
🔍
现在，在「知乎」也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」订阅我们的专栏吧
关于PaperWeekly
PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。