论文笔记 – Collaborative Graph Convolutional Networks: Unsupervised Learning Meets Semi-Supervised Learning

2021-01-03

Binyuan Hui, et al., “Collaborative Graph Convolutional Networks: Unsupervised Learning Meets Semi-Supervised Learning”, AAAI 2020

这篇是做图深度聚类 & 半监督节点分类，是 VAE 这一个流派的，正好是我做毕设时偷懒没有了解的 T_T 结果课堂 pre 要讲这篇文章，不得不从头补起。唉，欠的债都是要还的！所以第一部分先记录我的基础知识学习过程，这部分可能是本博客最长的一部分了 Orz

目录 展开

1 Preliminaries

整个知识体系大约如下：

  • 1.0 EM 算法、概率图模型、GMM、变分推断，都是机器学习基础
  • 1.1 VAE 是基础
  • 1.2 VGAE 是 VAE 在图表示学习上的进化，1.3 GMVAE, 1.4 VaDE 是 VAE 在聚类上的进化
  • 1.5 DAEGC, SDCN, AGC 是图聚类的一些前人成果
  • 1.6 DGG 是 GMM + VGAE 做聚类

文章都是经典文章，我懒得写引用了，有兴趣自己搜叭

1.0 fundamentals

推荐这个 视频（看着很多，实际上开二倍速，很快就能了解的（理解还是得自己动笔）） 和《统计学习方法》

1.1 VAE

上面三篇是 17 年写的，比较简单，理论上（可能）有点问题，不过作为入门还挺不错

这两篇是按照 DP Kingma and Max Welling, Auto-Encoding Variational Bayes 这篇文章的思路讲的

上面这七篇，它的序号 612 一定要看，其他的我都没有仔细看，没看懂

有了以上（其实主要靠苏神的 VAE 6 和 1），VAE 大约就能有一个感性认知了，下面开始是表示学习 & 图表示学习方面的改进：

1.2 VGAE

Kipf T N, Welling M. “Variational graph auto-encoders”, NIPS 2016.

1.3 GMVAE

Nat Dilokthanakul, et al., “Deep Unsupervised Clustering with Gaussian Mixture Variational Autoencoders”, ICLR 2017

  • GMVAE 笔记 by InceptionZ
    • 用 GMM 做 VAE 的先验，深度聚类。
    • 传统的 VAE，隐变量服从标准高斯分布（单峰），但有时候，单个高斯分布可能不能完全表达图像 x 的特征，比如 MINIST 数据集有 0~9 这 10 个数字，直觉上使用 10 个高斯分布来替代单个高斯分布更为合理，因此有学者将混合高斯分布模型（GMM）与 VAE 进行结合，其结果便是 GMVAE。
    • minimum information constraint，为 KLD 加入一个最小阈值 λ，使得在训练初期模型不要陷入局部解。
    • 写得太详细了，懒得看
  • GMVAE loss 推导
    • 模型结构：（博客中写成四步，关键就是第三步，前两步辅助）从 GMM 中选择一个高斯分布进行采样，得到隐变量 x；GMM 中每个高斯分布的均值和方差将由步骤一采样到的 w 进行变化得到；“从高斯分布采样”的过程由“从 multi 分布采样 z”得到
    • loss 包含四项：reconstruction term, conditional prior term, w-prior term 和 z-prior term。
    • 懒得看 loss 推导
  • GMVAE——基于高斯混合模型的VAE – Light Sea的文章 – 知乎
    • 传统的 deep generative model，例如 VAE，并不是专门为了聚类而设计的。但是像 VAE 这样的深度生成模型中包含了一个重要的东西：latent variable。实际上潜变量建模了一些抽象的概念，潜变量的结构在某些时候就包含了类别信息。然而这样虽然有可能完成聚类，但却没有任何显式的能完成聚类的保证。另外，潜变量的先验分布很简单，因此不能建模复杂数据。因此在这篇文章中作者基于 VAE 设计了一个专门用于聚类的算法。算法假设数据生成于一个多模态(multimodal)的先验分布。作者构建了一个 end-to-end 的模型，从而可以用 BP 轻易更新整个网络。
    • over-regularization problem 是指 ELBO 中 KL 项被过度优化从而导致 KL 项迅速变为 0 的问题。这种情况下，latent variable 会变得非常简单且不能很好的表示数据的结构。一般来说有两种办法解决这个问题。一是给 KL 项添加权重，边训练边增加权重；二是为 KL 项设置一个阈值，一旦它小于这个值就不再优化 KL 项。这里作者使用第二种方法来调整 z-prior term

1.4 VaDE

Zhuxi Jiang, et al., “Variational Deep embedding: An Unsupervised and Generative Approach to Clustering”, IJCAI 2017

  • 变分深度嵌入(Variational Deep Embedding, VaDE)
    • 该死，数理基础太扎实了
    • 流程：AE 预训练，得到 AE 和 GMM 参数，然后就按照 VAE 的方式训练（？）
  • 关于VaDE模型的理解与思考 – 一颗苞谷米米的文章 – 知乎
    • Motivation 就在于基于神经网络提出一种聚类方法，一是可以用 deep learning 学习一种好的表达，而这种表达可以获取数据的统计结构；二是可以生成样本。
    • 这篇博客里面对流程图说得很清楚
    • 发现 CGCN 里面 4.1 几乎就是转述这篇文章…
  • VaDE 笔记 by InceptionZ
    • DEC 模型的缺陷：DEC 模型没有数据生成的过程，所以不能产生图片，因为它使用的是 Autoencoder
    • 生成模型是公式(3)：p(x,z,c) = p(x|z)p(z|c)p(c)，代表上述的生成过程
    • 推理模型为公式(8)：q(z,c|x)=q(z|x)q(c|x),用来优化我们的变分下界的
    • 与 GMVAE 的区别
      1. 推理模型和生成模型不一样
      2. 计算准确率的方式不一样
      3. 处理over-regularisation问题的方式不一样
  • 深度聚类 VAE 类方法总结（VAE、GMVAE、VaDE）
    • 好文章！1.134 的总结。VAE 部分不错，后面就偷懒了，跟翻译没啥区别

1.5 Graph Clustering

DAEGC

Chun Wang, et al., “Attributed Graph Clustering: A Deep Attentional Embedding Approach”, IJCAI 2019

SDCN

Deyu Bo, “Structural Deep Clustering Network”, WWW 2020

  • WWW2020 Structural Deep Clustering Network – Houye的文章 – 知乎
    • byr 的文章，想法比较简单，还是 DEC 的改进，把 encoder 魔改成了 DNN 和 GCN 交替的多层结构（这里我还是不太清楚，感觉有点奇怪），最后 loss 里面 kld 的部分是让 DNN、GCN 和 q 都尽量靠近。
    • 果然，只要是带清华的文章，不管工作怎么样，引用高还是低，各种媒体报导都是充分的

AGC

Xiaotong Zhang, et al., “Attributed Graph Clustering via Adaptive Graph Convolution”, IJCAI 2019

1.6 DGG

Linxiao Yang, et al., “Deep Clustering by Gaussian Mixture Variational Autoencoders with Graph Embedding”, ICCV 2019

2 简介

这篇文章就是用 GCN + VaDE 聚类来辅助，做半监督节点分类任务。文章里的“GMM-VGAE”其实应该叫成“GCN-VaDE”更为合适（虽然只是 graph + gmm + vae 的不同排列组合）。

motivation 有 3-flod：

  1. 别人做图聚类，都是先学 embedding，再直接 k-means，这样不能端到端 learning（kmeans 相当于用 EM 算法）
  2. 半监督学习只使用无监督数据的分布来增强结果，但是并没有让监督信息增加；伪标签的方法会让误差累积
  3. 伪标签在图聚类问题上还没咋用（纯凑数的吧？图聚类的伪标签和普通聚类的伪标签有什么需要改动的区别吗？）

针对这些，作者作出改进：

  1. 使用 VAE，就能端到端了
  2. 改进赋予标签的方式，一点一点来，每次都取 confidence 较大的，就不会误差累积了
  3. 通过共享第一层 GCN layer 来 multi task learning（而不是直接 loss 相加！），每次更新完 label 都要 retrain（不优雅）

3 方法

整体流程如图所示，上半部分是 attributed graph clustering，下半部分是 semi-supervised node classification。

3.1 GMM-VGAE

红色大框框里是他的 GMM-VGAE，其实就是 VaDE 的 encoder 换成两层 GCN，其它完全一样。

GMM 需要一组 $\mu$ 和 $\sigma$ 作为每个子分布（后验分布 $P(Z|X)$）的参数，因此就需要两个两层的 GCN，这俩共享第一层：$$Z^{(1)} = f_{\text{ReLU}}(X,A|W^{(0)}$$ $$Z^{(2)}_\mu = f_{\text{linear}}(Z^{(1)}, A|W^{(1)}_\mu)$$ $$Z^{(2)}_\sigma = f_{\text{linear}}(Z^{(1)}, A|W^{(1)}_\sigma)$$

然后就可以据此来计算整体的后验分布了：$$q(Z|X,A) = \prod_{i=1}^n q(z_i|X,A)$$ $$q(z_i|X,A) = \mathcal{N}(z_i|\mu_i, diag(\sigma_i^2))$$

前面这部分被称作 inference model，用来拟合 GMM 的参数和 GCN 作为 encoder 的参数，下面就是 decoder，要用 link prediction 的方式重建这张图：$$p(\hat{A}|Z) = \prod_{i=1}^n\prod_{j=1}^np(\hat{A}_{ij}|z_i,z_j)$$ $$p(\hat{A}_{ij}|z_i,z_j) = \phi(z_i^T, z_j)$$

这里 $\phi$ 是 sigmoid，$\hat{A}_{ij}$ 是 decoder 重建出来的图。这里和 VaDE 其实有一些区别，VaDE 输入输出都是图片，loss 是 elbo (evidence lower bound)，可以分成两项，即 ① 重构误差 ② 采样分布和 GMM 分布的 kld。本文的 GMM-VGAE 输入 node embedding，输出图的邻接矩阵，用邻接矩阵计算重构误差。

聚类的过程就和 VaDE 一样，在得到每个节点 $x$ 的表达 $z$ 之后，就将这个特征向量 $z$ 输入到 $K$ 个高斯混合的 GMM 中进行聚类。

以上是聚类的部分。半监督分类的部分就直接对所有结点，用两层 GCN + softmax 分类。这里的 GCN 的第一层和 GMM-VGAE 的两个 GCN 的第一层都是同一个。分类的 loss 就用有标签的数据来算交叉熵。

怎么用无监督得到的结果增强监督信息，帮助半监督分类呢？作者给出这样一个方法：在半监督计算出 logit 后，每一类都挑选最高分的样本，按这些样本给聚类的 cluster 归类。然后在半监督分类的无标签样本中，找 top q 个 logit 分数最高的样本，看他们在两个任务上的结果是否一致，如果一致，就将其类别设为监督信息，这样就扩大了有监督样本的集合。一轮下来扩大有监督样本集合之后，再重新训练。

这种做法我还是第一次见（好像这也是我读的第一篇半监督的文章），感觉还挺有道理。但是有一点不太清楚：如果半监督分类的两个不同类别的有标签的样本，在聚类结果中在同一个 cluster，那这个 cluster 被分配给哪一类呢？logit 更大的吗？

4 实验

Cora, Citeseer, Pubmed 三个小数据集

  1. 聚类任务 sota
  2. 半监督分类任务大部分是 sota，最多 3% 有标签数据，就能打败 GCN 全监督

5 思考

  1. 好像用不到 DocRED 上，DocRE 是每个 doc 一张图，有的 doc 有监督，有的 doc 弱监督；这篇文章是一大张图，有的 node 有监督，有的 node 无监督。
  2. 其实我还全都是迷迷糊糊的，三五天速成这一系列的知识还是不现实，机器学习太难了，比 NLP 难 100 倍，我太垃圾了 Orz

6 TODO

  1. Li, Q.; Han, Z.; and Wu, X. 2018. Deeper insights into graph con- volutional networks for semi-supervised learning. In AAAI, 3538– 3545.

发表评论