论文阅读“Adaptive Graph Auto-Encoder for General Data Clustering”

Li X, Zhang H, Zhang R. Adaptive Graph Auto-Encoder for General Data Clustering[J]. arXiv preprint arXiv:2002.08648, 2020.

摘要翻译

基于图的聚类在聚类领域具有重要的作用。近年来，关于图卷积神经网络的研究在图形类型数据方面取得了令人瞩目的成功。然而，在一般的聚类任务中，不存在数据的图结构，因此构造图的策略对性能至关重要。因此，如何将图卷积网络扩展到一般的聚类任务中是一个很有吸引力的问题。本文提出了一种用于一般数据聚类的图自编码器，它根据图的生成视角自适应地构造图。自适应过程旨在诱导模型挖掘数据背后的高级信息，充分利用非欧几里德结构。论文进一步设计了一种新的机制，并进行了严格的分析，以避免自适应结构造成的负面影响。通过将网络嵌入的生成模型和基于图的聚类相结合，开发了一种基于图的自动编码器和解码器，使其在加权图的应用场景中表现良好。大量的实验证明了我们的模型的优越性。
GNNs extend classical neural networks into irregular data so that the deep information hidden in graphs is exploited sufficiently.[Scarselli F, Gori M, Tsoi A C, et al. The graph neural network model[J]. IEEE transactions on neural networks, 2008, 20(1): 61-80.]
GCNs have shown superiority compared with traditional network embedding models. []
Similarly, graph auto-encoder (GAE) is developed to extend GCN into unsupervised learning.[Kipf T N, Welling M. Variational graph auto-encoders[J]. arXiv preprint arXiv:1611.07308, 2016.]
切入点：为探索欧式数据域中的拓扑结构信息，论文从生成角度自适应的构造图，并使用GCN更好的提升聚类性能。

主要贡献点

为构建理想的图结构信息，模型合并了网络嵌入的生成模型。基于生成的观点，进一步整合了表示学习，以使图自然编码自然地被用来学习嵌入。（基于生成的思想，更容易探索数据中各节点间的连接分布）
从生成的图模型获得的学习的连通性分布，被用作图自动编码器重构的目标，这也启发了我们为解码器设计一种新颖的体系结构。
模型根据生成的嵌入内容自适应地更新图，从而可以利用深层信息并修改由原始特征导致的不良图。通过更改图形的稀疏度，我们消除了自适应结构导致的崩溃。此外，给出了相关的理论分析以了解该现象。

相关工作结构
深度聚类（AE-based 和 CNN-based）
GAE相关

模型浅析

Probabilistic Perspective of Weighted Graphs

论文有个基础假设，任意两个节点之间的连通性被定义为条件概率 $p(v|v_i)$ ，并且在整张图中有 $\sum_{j=1}^np(v_j|v_i)=1$ 。因此，可以将这种连通性看做采样结果，这也是生成网络嵌入的核心假设。
当然这种采样会由于连通性的差异导致 $p(v_i|v_j)\neq p(v_j|v_i)$ （有向加权图）。因此，加权图的构造等效于找到基础的连通性分布。
为了找到近似的连通分布，论文给出假设1：如果 $p(v_i|v_j)$ 值比较大，等价于节点 $v_i$ 和 $v_j$ 的特征表示是相似的。

红框中是代表为节点 $v_i$ 采样的期望，即期望在该节点的所有邻接节点中选出差异性 $d(v_i,v_j)$ 较小的节点集合。根据图中连通性的稀疏性原则，在自主学习连通性的过程中添加了正则项（由于L0和L1都存在些缺陷，因此论文选择使用L2正则项来保证节点连接的稀疏性）。通过对模型超参数的权衡，论文为所有节点选择相同的稀疏度，并被设置为控制参数的上界。

而 $p_i$ 作者将其定义为节点 $v_i$ 相对于每个节点的条件概率 $p_i=[p(v_1|v_i), p(v_2|v_i), ..., p(v_n|v_i)]$ ，并且在初始化时将其看做最简单的解决方案，即除自身节点外，其余节点的条件概率都等于0.

Graph Auto-Encoder for Weighted Graph

通过上述带权节点的连通性学习，我们其实得到的是有向带权图，在这一部分的运算中将其转换为无向图 $W_{ij}=(p(v_i|v_j)+p(v_j|v_i))/2$ ，并且 $W$ 邻接矩阵被作为GAE的重构目标。

Encoder
在普通GCN运算中邻接信息的引入使用 $(A+I)$ ，通过自环的权重是自适应学习的，而不是原始的 $I$ ，因此在Encoder中，作者将该部分替换为 $W$ ，其余算子未变，因此有:
Decoder
不同于重建A的内积，论文基于假设1来重建连通性分布 $p(v|v_i)$ 。

连通性分布计算