论文标题：DEEP GRAPH INFOMAX
论文链接：https://arxiv.org/abs/1809.10341
论文来源：ICLR 2019

之前的相关博客：
MINE：随机变量互信息的估计方法
Deep InfoMax：基于互信息最大化的表示学习

一、概述

目前主流的无监督图表示学习方法主要依赖于基于随机游走的，然而这一类的方法受到诸多限制。最显著的是，已知的随机游走目标过分强调接近性信息，而牺牲了结构信息，并且方法的效果高度依赖于超参数的选择。本文提出的方法基于互信息估计，依赖于训练一个统计网络作为分类器来区分开组两个随机变量联合分布和边缘分布乘积的样本。本文的方法从Deep InfoMax改进而来，称为Deep Graph Infomax，可以应用在直推式和归纳式的图表示学习任务中。

二、方法

1. 无监督图表示学习

首先对于一个图我们有一系列节点特征，代表节点数量，代表节点特征。另外节点之间的关系信息用邻接矩阵，可以包含任意的实数（甚至是任意边的特征），也可以是binary的。

我们的目标是学习一个encoder，也就是，代表节点的高级特征，这些特征将被用于下游任务。

本文主要关注图卷积encoder。值得注意的是，一个节点的特征集合了图的一部分子图信息，而不是仅包含这个节点本身。接下来将被称为patch表示。

2. 局部-全局互信息最大化

本文的方法依赖于最大化局部互信息，也就是说我们希望学习能够捕获图全局信息（由summary向量表示）的局部节点特征。

为了获得summary向量，我们利用一个readout函数来将patch表示聚合成图表示，也就是。

为了能够最大化互信息，本文采用一个discriminator，代表这个patch-summary对的概率得分。

的负样本通过将的与另一个图的配对得到。在面对多图数据时，这样的图从训练集中获得。而对于单图数据，则应用一个破坏函数（corruption function）来获得一个负样本的图，也就是。负采样方法的选择能够控制取舍图的特定的结构信息，可以根据任务所需要捕获的特征来进行设计。总结来说，本文方法的正样本为，负样本为。

损失函数采用噪声对比型二值交叉熵损失，以此来最大化和联合分布（正样本）和边缘分布的乘积（负样本）之间的互信息（下面的目标函数应该最大化）：

所有patch表示都被驱动保持与图表示的互信息，这有助于保持patch层级的相似性，举例来说，图中距离较远但是有相同结构特征的节点之间可以建立联系。

3. 算法

假设在单图情况下，Deep Graph Infomax的算法流程如下：
①使用破坏函数采样负样本：；
②通过encoder获取输入图的patch表示：；
③通过encoder获取负样本的patch表示：；
④通过readout函数获取输入图的图表示：；
⑤更新的参数来最大化上面的目标函数。

下图以一种直观的方式展示了算法的流程：

算法

三、实验

本文对直推式（transductive）和归纳式（inductive）任务都进行了实验，其中既包括单图配置，也包括多图配置，并且主要进行分类任务实验。在实验中DGI在完全无监督的情况下学习表示，然后使用简单分类器（逻辑回归）进行微调。

1. 数据集

下表展示了本次实验的数据集配置情况：

数据集

2. 实验设置

对于不同类型（直推式、大图归纳式以及多图归纳式）的实验，采用不同的encoder和破坏函数。

• 直推式学习

encoder采用一个一层GCN：

这里是邻接矩阵加上一个自连接，是对应的度矩阵，，激活函数采用参数化ReLU（PReLU），是应用在每个节点上的可学习的线性变换矩阵，（由于受到内存限制在Pubmed数据集上为）。

此设置中使用的破坏函数旨在鼓励表示正确编码图中不同节点的结构相似性，因此采用的破坏函数保留原有的邻接矩阵，而对于，则通过对进行按行打乱来获得。这样获得的负样本图拥有与原图一样的节点，但是位于不同的位置。

• 大图上的归纳式学习（只有Reddit数据集）

由于GCN的卷积核严重依赖于固定和已知的邻接矩阵，所以在当前配置下采用mean-pooling传播规则的GraphSAGE-GCN：

上式中与相乘意味着执行了一个标准化加和（也就是mean-pooling）。最终采用的encoder为一个三层mean-pooling模型以及跳跃连接：

代表拼接操作，也就是说中心节点和它的邻居节点分开处理。另外且激活函数采用参数化ReLU（PReLU）。

由于图的规模过大导致GPU显存不足，因此额外采用一种下采样策略。具体的方法是首先采样一个minibatch的节点，然后采样每个节点的邻域以最终获得以每个节点为根节点的子图，在每个子图的采样中对于1,2,3层分别采样个邻居节点，因此每个子图就有个节点。只有获取中心节点的patch表示的计算被执行，这些表示然后被用来获得这个minibatch的summary向量。在实验中使用minibatch大小为。

破坏函数与直推式配置类似，但是将minibatch内每个节点采样得到的子图看做独立的图进行破坏（也就是按照行单独打乱这些子图的特征）。这很可能使得中心节点在负样本图中的特征被替换为采样邻居的特征，从而增加了负样本的多样性。最后在中心节点中得到的patch表示被输入给discriminator。

上述过程如下图所示：

框架

• 多图上的归纳式学习（只有PPI数据集）

对于PPI数据集，受以前成功的监督架构的启发，该配置下的encoder如下：

这里是参数矩阵，同样的每个层且激活函数采用参数化ReLU（PReLU）。

负样本就是训练集中的其他图，为了增强负样本的多样性，也会对采样到的负样本图的特征进行dropout。另外实验发现，在将学习到的表示提供给逻辑回归模型之前，将它们标准化是有益的。

• Readout, discriminator等

不同的数据集配置采用同样的readout函数和discriminator架构。

Readout函数采用简单的节点特征平均：

这里是sigmoid函数。随着图的尺寸增大，这种简单平均的策略的效果可能会减弱，这时可以采用一些更先进的方法来替代，比如set2vec、DiffPool等。

Discriminator采用以下结构：

其中是参数矩阵，是sigmoid函数。

另外所有模型使用Glorot initialization初始化，其他具体实验设置参看原文。

3. 实验结果

下图展示了在多个数据集上的实验结果：

实验

另外使用t-SNE进行了特征的可视化：

t-SNE