《Deep Graph Infomax》论文解读

论文传送门：click here

推荐参考链接：

• DIM：深度学习中的互信息：无监督提取特征 | 机器之心 (jiqizhixin.com)
• $f$ 散度($D_f$)的估算：f-GAN简介：GAN模型的生产车间 - 科学空间|Scientific Spaces (kexue.fm)

论文动机

图神经网络已经有了很大发展，但大多数成功的方法使用的是监督学习，而在现实中大多数的图数据事实上是未标记的。因此针对这种无标签的图信息，一种无监督/自监督学习方法是重要的。

目前的无监督表示学习大多依赖于随机游走方法，其有如下的缺点：

• 过分强调了邻居之间的信息，而牺牲了整体的结构信息
• 性能高度依赖于超参设置
• 可解释性较差，即无法确定随机游走是不是真的提供了有用信息（假设节点与邻居较为相似的观点是一种归纳偏置）

因此本文提出了一种基于互信息得到的无监督图学习方法。

具体来说，本文将这篇论文的 Deep InfoMax 思想运用到了图神经网络中。

核心思想

（我感觉这篇论文就是把CV中的方法直接运用到图神经网络中，似乎并没有改变什么）

我们有什么？

1. 对于图上每一个节点，我们有他们的特征向量集合 $X=\{\vec {x_1}, \vec {x_2}, \dots,\vec {x_N}\}$
2. 我们有邻接矩阵 $A$，论文中设置无边权，即 $A_{ij}\in\{0,1\}$

我们要做什么？

我们希望能够训练出一个编码器 ${\mathcal E} : \mathbb{R}^{N\times F} \times \mathbb{R}^{N\times N} \to \mathbb{R}^{N\times F^{\prime}}$，使得 ${\mathcal E}(X,A)=H=\{\vec {h_1}, \vec {h_2}, \dots,\vec {h_N}\}$表示每个节点编码后的高级表示。

我们怎么做？

核心思想为局部-全局互信息最大化。

具体来说，运用图卷积方法作为编码器 ${\mathcal E}$ ，获得每个节点的表示 $H$ 。事实上，图卷积得到的向量是以节点为中心的图的patch。这是局部信息。

接下来获得全局的图级向量表示 $\vec s$。定义函数 ${\mathcal R} : \mathbb{R}^{N\times F} \to \mathbb{R}^{F}$，实现了从patch到全局的信息汇总：$\vec s=\mathcal R({\mathcal E}(X,A))$。在实验中使用的就是均值函数：
$$
\mathcal R(H)=\sigma\left(\frac1N\sum_{i=1}^N\vec{h}_i\right)
$$
接下来的步骤与对比学习类似，构造图的负样例，得到负样本图上的每一个patch的表示 $\tilde H$。与对比学习不同的是，这里希望 $H$ 与 $\vec s$ 尽可能接“近”，$\tilde H$ 与 $\vec s$ 尽可能”远“。如下图：

而这里刻画”远近“是通过一个判别器 ${\mathcal D}$ 来实现的，这是网络学出来的，具体而言：
$$
\mathcal D(\vec h,\vec s)=\sigma(\vec h^TW\vec s)
$$
整个方法的优化目标为优化如下函数：

优化这个函数事实上就是极大化互信息量。至于为什么，参考链接中给出的两个网址较为清晰全面的进行了推导。

总结！整个过程可以分为五个部分：

实验设置与结果

Transductive learning——直推式学习

编码器采用GCN网络：
$$
\mathcal{E}(\mathbf{X},\mathbf{A})=\sigma\left(\mathbf{\hat{D}}^{-\frac{1}{2}}\mathbf{\hat{A}}\mathbf{\hat{D}}^{-\frac{1}{2}}\mathbf{X}\mathbf{\Theta}\right)
$$
负样例的构造方式为：讲 $X$ 打乱，即每个节点的位置不变，但特征变成其他节点了。至于为什么要保留原图结构，论文给出的说法为 “we find those that preserve the graph structure result in the strongest features.”

Inductive learning on large graphs——大图上的归纳学习

编码参考 GraphSAGE-GCN 论文中的方法：
$$
\mathrm{MP}(\mathbf{X},\mathbf{A})=\mathrm{\hat{D}}^{-1}\mathrm{\hat{A}X}\Theta
$$
改变后得到编码器为：
$$
\widetilde{\mathrm{MP}}(\mathbf{X},\mathbf{A})=\sigma\left(\mathbf{X}\mathbf{\Theta}^{\prime}|\mathrm{MP}(\mathbf{X},\mathbf{A})\right)\quad\mathcal{E}(\mathbf{X},\mathbf{A})=\widetilde{\mathrm{MP}}_3(\widetilde{\mathrm{MP}}_2(\widetilde{\mathrm{MP}}_1(\mathbf{X},\mathbf{A}),\mathbf{A}),\mathbf{A})
$$
又因为图比较大，因此整个图的汇总向量是不方便求解的，因此采用了采样以及minibatch上的汇总向量。

创造负样例的方式与直推式学习一致，不过对每一个子图patch来进行这种操作。

Inductive learning on large graphs——多图上的归纳学习

编码器为：a three-layer mean-pooling model with dense skip connections
$$
\mathbf H_1=\sigma\left(\mathrm{MP_1}(\mathbf{X},\mathbf{A})\right) \quad
\mathbf H_2=\sigma\left(\mathrm{MP_2}(\mathbf{H_1}+\mathbf{XW_{skip}},\mathbf{A})\right)
$$
得到：
$$
\mathcal{E}(\mathbf{X},\mathbf{A}) =\sigma\left(\mathrm{MP_3}(\mathbf{H_2}+\mathbf{H_1}+\mathbf{XW_\mathrm{skip}},\mathbf{A})\right)
$$
负样例采取的方式为随机采样 (randomly sampled training graphs)，也采用了dropout。

实验结果