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
推荐这个 视频(看着很多,实际上开二倍速,很快就能了解的(理解还是得自己动笔)) 和《统计学习方法》
- EM、Bayesian network 略
- GMM
- 响应度:相当于每个高斯分布的 weight
- 高斯混合模型GMM详细推导 很有助于理解
- VI
- 这里的 elbo 和 VAE 的 elbo 不是同一个 elbo
- VI:P(x) = elbo + KLD
- VAE:elbo = rec + KLD
- 如何简单易懂地理解变分推断(variational inference)? – 过小咩的回答 – 知乎
- 这里的 elbo 和 VAE 的 elbo 不是同一个 elbo
- GCN
- 详见我之前的系列笔记
1.1 VAE
上面三篇是 17 年写的,比较简单,理论上(可能)有点问题,不过作为入门还挺不错
- Auto-Encoding Variational Bayes(VAE) – 慕容三思的文章 – 知乎
- 读经典论文:Auto Encoding Variational Bayes – KyleJin的文章 – 知乎
这两篇是按照 DP Kingma and Max Welling, Auto-Encoding Variational Bayes 这篇文章的思路讲的
- 苏剑林. (Mar. 15, 2018). 《从最大似然到EM算法:一致的理解方式》
- 苏剑林. (Sep. 10, 2020). 《变分自编码器(六):从几何视角来理解VAE的尝试》 入门很好,但是感觉 KL 那一项 loss 说的不是很准确
- 苏剑林. (Mar. 18, 2018). 《变分自编码器(一):原来是这么一回事》
- 苏剑林. (Mar. 28, 2018). 《变分自编码器(二):从贝叶斯观点出发》 这篇写的是真的好
- 苏剑林. (Apr. 03, 2018). 《变分自编码器(三):这样做为什么能成?》 看不懂
- 苏剑林. (Sep. 17, 2018). 《变分自编码器(四):一步到位的聚类方案》 看不懂
- 苏剑林. (Jul. 18, 2018). 《用变分推断统一理解生成模型(VAE、GAN、AAE、ALI)》 看不懂
上面这七篇,它的序号 612 一定要看,其他的我都没有仔细看,没看懂
- 《Auto-Encoding Variational Bayes》论文阅读 – 李强的文章 – 知乎 一些要掌握的概念:SGVB estimator,reparameterization trick
有了以上(其实主要靠苏神的 VAE 6 和 1),VAE 大约就能有一个感性认知了,下面开始是表示学习 & 图表示学习方面的改进:
1.2 VGAE
Kipf T N, Welling M. “Variational graph auto-encoders”, NIPS 2016.
- VGAE(Variational graph auto-encoders)论文详解 – 嘉鱼的文章 – 知乎
- 前半部分是从苏神博客抄的,可用来复习;后半部分,图 VAE 就是编码用两层 GCN($\mu$ 和 $\sigma$ 的 GCN 第一层共享参数),解码用点积
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 的区别
- 推理模型和生成模型不一样
- 计算准确率的方式不一样
- 处理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
- 论文笔记:Attributed Graph Clustering: A Deep Attentional Embedding Approach
- 感觉就是 DEC + GAT?encoder 从 DEC 的半个 AE 变成 GAT,decoder 还是用点积做 link prediction;loss 还是 VAE 的 rec + kld,q 分布与 DEC 保持一致
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
- A Graph Clustering method: AGC – dongZheX的文章 – 知乎
- 改了一下卷积核的表达式:chebynet 是增强高频信号,GCN 就是简单的低通线性滤波器,AGC 改了每个 filter 的系数,抑制高频信号
- 多阶邻居的平滑是把 filter 表达式求幂得到新的 filter,这样又能 k 阶,参数又很少(太妙了!虽然只是初中数学的知识)
- 图神经网络时代的深度聚类 – Houye的文章 – 知乎
- 这篇文章讲了 DAEGC、SDCN、AGC、EGAE-JOCAS,前两部分我懒得看了
- k 采用启发式方法,逐渐增加 k, 当类内距离开始变小时, 停止搜索
- EGAE-JOCAS 没看懂
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:
- 别人做图聚类,都是先学 embedding,再直接 k-means,这样不能端到端 learning(kmeans 相当于用 EM 算法)
- 半监督学习只使用无监督数据的分布来增强结果,但是并没有让监督信息增加;伪标签的方法会让误差累积
- 伪标签在图聚类问题上还没咋用(纯凑数的吧?图聚类的伪标签和普通聚类的伪标签有什么需要改动的区别吗?)
针对这些,作者作出改进:
- 使用 VAE,就能端到端了
- 改进赋予标签的方式,一点一点来,每次都取 confidence 较大的,就不会误差累积了
- 通过共享第一层 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 三个小数据集
- 聚类任务 sota
- 半监督分类任务大部分是 sota,最多 3% 有标签数据,就能打败 GCN 全监督
5 思考
- 好像用不到 DocRED 上,DocRE 是每个 doc 一张图,有的 doc 有监督,有的 doc 弱监督;这篇文章是一大张图,有的 node 有监督,有的 node 无监督。
- 其实我还全都是迷迷糊糊的,三五天速成这一系列的知识还是不现实,机器学习太难了,比 NLP 难 100 倍,我太垃圾了 Orz
6 TODO
- Li, Q.; Han, Z.; and Wu, X. 2018. Deeper insights into graph con- volutional networks for semi-supervised learning. In AAAI, 3538– 3545.