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

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

  • 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:

  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.

Leave a Comment

电子邮件地址不会被公开。