Structral Deep Clustering Network
WWW2020
本文为尝试将结构化信息建模在深度聚类任务中，并提出了全新的结构化深度聚类模型，其中包括一个DNN模块、GCN模块和双重自监督模块，并通过一个delivery operator成功将autoencoder和GCN所学到的表示结合在一起，并从理论上证明了其有效性。Paper
ABSTRACT
深度聚类算法目前取得了不错的效果，但是大多数依赖于深度模型的表征能力，比如自编码器（autoencoder），这类深度聚类方法的能力在于提取数据本身的表示，而缺少对数据的结构的建模，本文基于GCN提出Structral Deep Clustering Network(SDCN)，利用delivery operator将自编码器中学到的表示传入对应GCN层中，然后通过一个双自监督机制将两个模型进行整合并一起更新，从而将结构信息融合到自编码器所生成的表示中。本文还对所提出的delivery operator进行理论分析，在这个算子下，GCN作为自编码器的高阶图正则化约束（high-order graph regularization constraint），自编码器可以缓解GCN过平滑（over-smoothing）的问题。在多个任务上取得了SOTA的效果。
INTRODUCTION
聚类任务实质自安于将相似样本归于同一类，深度聚类的基本思想在于将聚类任务和深度学习的表征能力结合，通过学习更有效的数据表示来提升聚类效果，类似的方法只考虑数据本身的特征却忽略了数据的结构信息。
文中提出在深度聚类中结合结构化信息有以下两个难点：
- 哪些结构化信息需要被考虑？低阶与高阶邻居
- 结构化信息和深度聚类之间的关系？DNN每层与多种类型结构信息之间的联系
为了捕获数据的结构化信息，我们首先用KNN构图，用GCN去捕获KNN图中的低阶和高阶的结构信息，从而获得GCN-specific表示。
为了在深度聚类中引入结构化信息，我们利用autoencoder模块捕捉数据的表示，并提出delivery operator将从GCN中或得到的表示与autoencoder获得的表示进行整合，同时我们证明在delivery operator的帮助下，GCN可以为autoencoder提供二阶图正则化，autoencoder则减轻了GCN过平滑的问题。
由于两个模块均能输出数据表示，我们提出双自监督模块对GCN和autoencoder模块进行统一训练，实验表明提出的SDCN在六个数据集上取得了SOTA效果。
THE PROPOSED MODEL
KNN Graph
这一部分就是利用KNN对每个样本进行计算相似度，对每个样本取top-K的邻居生成相应的边。我们用了两种方法计算样本之间的相似度：
1) Heat Kernel:
$$ S_{ij}=e^{- \frac{||x_{i}-x_{j}||^{2}}{t}}$$
2) Dot-product:
$$ S_{ij}=x_{j}^T * x_{i} $$
DNN Module
为了通用性，在本文中我们仅使用basic autoencoder从raw data中获取表示以适应不同的数据特征。最后将decoder的输出与原始数据的输入进行构造重构误差
GCN Module
L层autoencoder获得到多种数据表示$\mathbf{H}^1, \mathbf{H}^2, \cdots, \mathbf{H}^L$，但是忽略了样本之间的联系，本模块用GCN来捕捉结构信息，
我们认为每一层autoencoder的输出都包含了不同的信息且能够对原始数据进行重构，于是使用一个超参$\epsilon=0.5$对两个模型所获取到的表示进行融合
将最后一层的输出投射到相应的label维度，然后利用softmax进行归一化。
Dual Self-Supervised Module
我们虽然已经将autoencoder和GCN整合在一起，但是还未针对深度聚类任务进行构造，通常autoencoder适用于无监督任务，而GCN则应用于半监督任务，因此不能直接应用到聚类问题上。我们提出一个双自监督模块，对两者进行整合，并进行端到端训练用于聚类任务。对于$i-th$样本和$j-th$集簇，使用学生t-分布作为相似度计算核函数，从而计算节点与簇中央节点（预训练autoencoder的表示经过K-Means获得）的相似度。（注意$\mathbf{H}$是从autoencoder中学习到的表示，而$\mathbf{Z}$是GCN模块输出的表示）
$q_{ij}$可以视为样本$i$分到$j$集簇的概率，我们将$Q=[q_{ij}]$作为所有样本指派的分布，然后我们将利用KL Divergence对表示进行更新使$Q$分布趋近于$P$分布（自监督，因为P分布是从Q分布中获得，又监督Q分布的更新过程）
$P$分布的目的让节点表示趋近于其集簇中央，是集簇更紧密，$f_{j}=\sum_{i}{q_{ij}}$
对于训练GCN模块，如果将上面集簇的指派作为真实标签，容易带来噪音和Trivial Solution，使整个模型训练崩塌，因此我们可以让GCN最后一层输出（分类层）的$Z$分布同时也趋近与$P$分布，同样也利用KL Divergence。这里使用KL散度作为目标函数有两个好处：
- 传统的多分类损失函数相比，KL散度可以更缓和的更新整个模型，避免嵌入有过大的波动
- GCN和DNN整合使用同一个优化目标，让训练过程更加一致
模型最终的损失函数如下所示：
最后将模型GCN模块的最终输出Z作为最终的聚类结果，因为GCN中包含了结构信息和数据自身特征
Theory Analysis
暂略
Experiments
我们对6个数据集进行了实验，包括USPS、HHAR、Reuters、ACM、DBLP、Citeseer，对比了6个baseline，并在四个指标上进行了实验，实验结果如下所示
Analysis https://dannywu1996.github.io/2020/02/27/structral-deep-clustering-network/#moreof Clustering Results
- 对于ACM、DBLP、Citeseer直接用原始图作为输入，可以从表格中看到提出的SDCN在4个指标上都要超越其他baseline，
- SDCN普遍高于$SDCN_Q$，表明结构化信息的作用，但同时也依赖于一个噪音少的初始网络
- 对于已经有网络结构的，GCN类的方法要优于基于自编码器的方法，否则相反。构造好的网络很重要！！
Analysis of Different Propagation Layers
通过固定住autoencoder的层数4层去观察，GCN的层数对模型性能的影响：
