WWW2020 结构深度聚类网络

“ 图神经网络已经在很多领域得到了广泛的引用,如计算机视觉,自然语言处理和推荐. 那么,图神经网络能不能提升一些基础机器学习任务(如聚类)的表现呢?

本文首次将GNN用到聚类上,提出了一种基于GNN的深度聚类算法 Structural Deep Clustering Network.

”

本文由北邮、腾讯和清华联合发表在WWW2020上。

论文链接: 

https://arxiv.org/abs/2002.01633

 

01

—

介绍

随着深度学习的突破，神经网络在聚类等许多重要任务上取得了巨大成功，深度聚类引起了人们的广泛关注。深度聚类的基本思想是将深度学习强大的表征能力融入到聚类的目标中。因此，有效的学习数据的表征是深度聚类的关键前提。

尽管深度聚类取得了成功，但现有的工作[1][2][3][4]通常只关注数据自身的特性，在学习表征时很少考虑数据的结构。值得注意的是，在数据表征领域，考虑数据样本之间关系的重要性已经被以往的文献和结果所公认。这种结构揭示了样本之间潜在的相似性，从而为学习表征提供了有价值的指导。一种典型的方法是谱聚类，它将样本作为加权图中的节点，利用数据的图结构进行聚类。

最近，新兴的图卷积网络（GCN）同时对图结构和节点属性进行了编码，用于节点表征。目前已经有一些基于GCN的图数据聚类方法[5][6]，他们通过重构图的邻接矩阵来保持数据间的结构，但是这类方法缺少了对数据自身的特性的关注。因此我们考虑如何在保持现有深度聚类框架优点的同时，加入结构化信息。

 

02

—

模型

        为了引入数据间的结构信息，在初始化模型之前，我们首先基于原始数据计算出一个K最近邻图。这个图会被作为GCN模块的输入。整个模型大概包括三部分：深度神经网络模块，图卷积模块和双重自监督模块。

深度神经网络模块主要是利用自编码器学习数据自身的特性，损失函数为解码器的重构数据和原始数据之间的误差：

        图卷积模块主要是将图卷积层学到的GCN特定表征和自编码器学到的特征表征进行结合，然后通过在KNN图上进行传播学习到结构信息。标准图卷积层的形式为：

与标准图卷积层不同，我们的图卷积模块为了同时学习到GCN的表征和自编码器的表征，引入了一个传递算子，它将两个表征进行加权求和：

然后再传入标准图卷积层中学习结构信息：

这样我们就可以为自编码器中每一层学习到的表征都加入结构信息，同时保留自编码器学习数据自身特性的作用。

        双重自监督模块主要有两个作用，一是引入聚类信息来指导模型学习更好的数据表征；二是指导深度神经网络模块和图卷积模块的更新。具体来说，对于自编码器学到的数据x_i的表征h_i，我们利用Student’s t分布作为一个核来衡量数据表征x_i和聚类中心u_j的相似性：

q_{ij}被认为是将样本i分配给簇j的概率，我们将其看作是所以样本的分配的分布。

        在获得聚类分布Q之后，我们想要引入聚类信息来指导模型学习更好的数据表征，具体来说，我们想要让数据表征更紧密的围绕在数据中心周围，以此来提高聚类结果的内聚性，为此我们设计了目标分布P：

在目标分布P中，Q中的每个分配分配都先被平方后归一化，所以每个分配都可以获得更高的置信度，然后引入KL散度作为损失函数来进行优化：

通过最小化Q分布和P分布之间的KL散度，Q分布会逐渐向P分布靠近，以此来达到提升聚类结果的内聚度的效果。

        对于图卷积模块的训练，一种较为直观地方式是将聚类的结果作为真实标签进行分类训练，然而，这种策略会带来噪声和平凡解，并导致整个模型的崩溃。受到聚类损失函数的启发，我们将目标分布P作为监督信息来指导分布Z的更新：

该目标函数有两个优点：(1)与传统的多分类损失函数相比，KL散度以更“温和”的方式更新整个模型，以防止数据表征受到严重干扰；(2)图卷积模块和深度神经网络模块统一在同一优化目标中，使其两个模块的结果在训练过程中趋向于一致。因为深度神经网络模块和图卷积模块的目标是近似目标分布P，而且两个模块之间有很强的关系，所以我们称之为双重自监督机制。

        整个模型的整体损失函数为：

其中,\alpha是平衡原始数据聚类优化和局部结构保存的超参数，\beta是控制图卷积模块对嵌入空间干扰的系数。通过对这个损失函数的优化，我们可以以端到端的方式更新整个模型。

 

03

—

理论分析

我们还进行了一些理论分析来证明我们提出的模型的优越性：

一是GCN模块可以为自编码器学习到的表征施加二阶图正则，相当于为自编码器表征提供了结构信息；

二是传递算子可以缓解GCN中出现的过拟合现象。

 

04

—

实验

我们在六个数据集上分别和现有的深度聚类算法以及基于GCN的聚类算法进行了比较：

 

并做了变体实验，传播层数实验，传递算子参数实验，K敏感性实验等:

 

[1] Bo Yang, Xiao Fu, Nicholas D Sidiropoulos, and Mingyi Hong. 2017. Towards k-means-friendly spaces: Simultaneous deep learning and clustering. In ICML. 3861–3870.

[2] Junyuan Xie, Ross Girshick, and Ali Farhadi. 2016. Unsupervised deep embedding for clustering analysis. In ICML. 478–487.

[3] Xifeng Guo, Long Gao, Xinwang Liu, and Jianping Yin. 2017. Improved deep embedded clustering with local structure preservation. In IJCAI. 1753–1759.

[4] Zhuxi Jiang, Yin Zheng, Huachun Tan, Bangsheng Tang, and Hanning Zhou.2017. Variational deep embedding: An unsupervised and generative approach to clustering. IJCAI (2017).

[5] Thomas N Kipf and Max Welling. 2016. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308 (2016).

[6] Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang.

2019. Attributed Graph Clustering: A Deep Attentional Embedding Approach. IJCAI (2019).