https://arxiv.org/pdf/2103.13125

Learning Graph Representation by Aggregating Subgraphs via Mutual Information Maximization，2021，arxiv preprint

总结： 前面文章提到过，图对比学习中常用的数据增强策略可以归纳为4种，mask属性、增删节点、增删边和子图。本文作者从子图入手提出了一种图对比学习模型。具体来说，作者提出了一种自回归子图生成模型，然后将生成的子图聚合到一起作为新图，再和原图进行对比，用于无监督/半监督图分类任务。另外作者还添加了一些小trick，进一步提高了模型性能。

1. 简介

1.1 摘要

In this paper, we introduce a self-supervised learning method to enhance the graph-level representations with the help of a set of subgraphs. For this purpose, we propose a universal framework to generate subgraphs in an auto-regressive way and then using these subgraphs to guide the learning of graph representation by Graph Neural Networks. Under this framework, we can get a comprehensive understanding of the graph structure in a learnable way. And to fully capture enough information of original graphs, we design three information aggregators: attribute-conv, layer-conv and subgraph-conv to gather information from different aspects. And to achieve efficient and effective contrastive learning, a Head-Tail contrastive construction is proposed to provide abundant negative samples. Under all proposed components which can be generalized to any Graph Neural Networks, in the unsupervised case, we achieve new state-of-the-art results in several benchmarks. We also evaluate our model on semi-supervised learning tasks and make a fair comparison to state-of-the-art semi-supervised methods.

本文，我们提出了一种自监督图学习方法，通过子图集合提高图层级表示质量。为此，作者提出了一种通用的框架，以自回归的方式生成子图，然后用这些子图来指导GNN学习图表示。通过该框架，我们能够以一种可学习的方式深入理解图结构。另外，为了充分捕捉原始图信息，我们设计了三种类型信息聚合器：attribute-conv，layer-conv和subgraph-conv，从不同方面收集信息。为了实现高效的对比学习，作者提出了一种head-tail对比结构，可以提供丰富的负样本。通过将这些组件应用到GNNs中，作者在一些标准数据集上实现了sota效果。作者也进行了一些半监督实验来评估该模型。

1.2 本文工作

背景： GNNs虽然被广泛用于图表示学习，但是大多数都用于有标签数据集。在很多领域数据标记成本过高，因此无监督或者半监督学习方法是一种非常重要的技术。现有的方法主要有两类：一种是通过重构图结构比如VGAE，另一种是对比学习。

动机： 作者关注于如何从原始图中聚合信息，以及如何定义一个更好的、合理的约束来保留图的基本信息，提出一种新的无监督图对比学习方法。（说白了就是从子图这种增强策略入手，搞图对比学习）

作者贡献： 从子图入手，提出了一种图对比学习模型用于图分类任务。作者在一些现有工作的基础上添加了一些小trick，使模型性能有一点提升。具体来说：

1. 设计了三种类型信息聚合器：attribute-conv，layer-conv和subgraph-conv，从不同方面收集信息。attribute-conv用于融合不同种类的原始信息；layer-conv用于聚合不同尺度的节点表示；subgraph-conv用于得到reconstructed graph的图表示。
2. 提出了一种通用的可学习的自回归子图生成框架。利用生成的子图和subgraph-conv，可以对图进行重构，然后将重构图和原始图进行对比可以得到一个合理的目标函数。
3. 提出了一种新的负样本采集方法Head-Tail对比采样，可以为学习到的表示提供有意义的约束。

注：上述提到的所有组件都是可插拔的，可以灵活迁移到任意图模型中。

2. 方法

整个框架可以划分成Node-Agg，Layer-Agg和Subgraph-Agg三个阶段。

• 首先在Node-Agg阶段，通过attribute-conv对各种属性进行聚合，得到基本的节点表示。
• 然后在Layer-Agg阶段，通过layer-conv对GNNs中不同尺度节点表示进行聚合，得到最终节点表示。
• 在Subgraph-Agg阶段，通过自回归进行子图采样，得到子图后，再利用subgraph-conv对所有子图信息进行聚合得到重构图的图表示。这一过程可以看做：数据增强（得到一个新的graph view）+图表示学习。
• 最后对比原始图表示$h(G)$和重构图表示$\tilde h(G)$，优化模型。

2.1 Node-Agg阶段

图数据中往往包含丰富的信息，比如节点和边的属性信息，甚至是局部结构信息。我们可以通过将这些不同类型信息聚合到一起，提高学习到的节点表示的质量，进而学习到更好的图表示。

具体来说，假设有N中类型节点属性：$X_1,X_2,...,X_N\ X_i\in\mathbf R^{|V|\times N_i}$。为了简化分析过程，我们考虑只有节点属性$X_V\in\mathbf R^{|V|\times D_V}$和边属性$X_V\in\mathbf R^{|E|\times D_E}$的情况：

• 首先将两者的转化成相同维度：

  $X_{V}^{(0)}=\operatorname{MLP}_{\mathbf{v}}\left(X_{V}\right) \in \mathbf{R}^{|V| \times d}\tag 2$

  $X_{E}^{(0)}=\mathbf{A G G}\left(\operatorname{MLP}_{\mathbf{E}}\left(X_{E}\right)\right) \in \mathbf{R}^{|V| \times d}\tag 3$

  其中$AGG$表示将边嵌入整合到相关节点中。

• 得到初始节点、边嵌入$X_{V}^{(0)}, X_{E}^{(0)} \in \mathbf{R}^{|V| \times d}$后，利用一个卷积核将两者合并到一起：

  $X^{(0)}=\operatorname{attribute-conv}\left(\left[X_{V}^{(0)} ; X_{E}^{(0)}\right]\right) \in \mathbf{R}^{|V| \times d}\tag 4$

  这样我们就得到了GNNs的输入$X^{(0)}$。

2.2 Layer-Agg阶段

GNNs每一层都会得到一个节点表示：$\left(X^{(1)}, X^{(2)}, \ldots, X^{(L)}\right)$，虽然$X^{(L)}$通常是有用的，但是不可避免的会丢失一些有用的节点信息。因此，作者使用一个layer-conv将GNNs每一层输出都聚合到一起作为最终节点嵌入：

$X_{\mathcal{G}}=\operatorname{layer-conv}\left(\left[X^{(1)} ; X^{(2)} ; \ldots ; X^{(L)}\right]\right) \in \mathbf{R}^{|V| \times d}\tag 5$

得到所有节点的嵌入后，再通过一个readout函数计算整图表示：

$h(\mathcal{G})=\mathbf{R E A D O U T}\left(X_{\mathcal{G}}\right) \in \mathbf{R}^{d}\tag 6$

2.3 Subgraph-Agg阶段

作者认为多视角图对比学习那篇文章中对比节点和图表示无法学习到高质量的图表示，因为节点表示和图表示蕴含的信息不在同一个层级。

本文作者提出了一种类似集成学习的子图方法，通过一系列原始图的子图构建一张新图和原始图进行对比，即：

$\max \mathcal{I}(h(\mathcal{G}) ; \tilde{h}(\mathcal{G}))\tag 7$

其中$\tilde h(\mathcal G)$表示重新构建的新图$G^{rec}$的表示向量。具体来说，$G$表示原始图，$G^{rec}=\{\mathcal G_i,i=1,2,...,S\}$表示子图集合，公式7可以写成：

$\max \mathcal{I}\left(\mathbf{G} ; \mathbf{G}^{\mathbf{r e c}}\right)=\mathbb{E}_{\mathbf{G}}\left[\mathbf{K L}\left(p\left(\mathbf{G}^{\mathrm{rec}} \mid \mathbf{G}\right) \| p\left(\mathbf{G}^{\mathbf{r e c}}\right)\right)\right]$

其中$\mathbf{KL}(·||·)$表示KL散度。下面详细介绍下该阶段的细节。

2.3.1 子图生成

对于子图生成方法，作者采用自回归模型：

$\begin{aligned}p\left(\mathbf{G}^{\text {rec }} \mid \mathbf{G}\right) &=p\left(\left\{\mathcal{G}_{i}, i=1,2, \ldots, S\right\} \mid \mathbf{G}\right) \\&=\prod_{i=2}^{S} p\left(\mathcal{G}_{i} \mid \mathbf{G}, \mathcal{G}_{1}, \ldots, \mathcal{G}_{i-1}\right) .\end{aligned}\tag 8$

作者提出了两种生成方法：Tree-split和Multi-head。

一、Basic Operator

先看一种基本操作，作者提出的两种子图生成方法都是在这一基本操作基础上衍化而来。

首先通过公式5得到每个节点嵌入$X_\mathcal G\in\mathbf R^{|V|\times d}$后，再做一个线性转换后计算一个概率矩阵：

$P=\operatorname{Softmax}\left(X_{\mathcal{G}} \cdot W\right) \in \mathbf{R}^{|V| \times 2}\tag {11}$

P中的元素$p_{ij}$表示节点$i$出现在子图$j$中的概率。公式11表示将原始图划分成两个子图。

二、Tree-split

如下图所示，Tree-split方法就是不断迭代执行basic operator，在前一轮生成的子图上执行basic operator，就想一棵二叉树一样。经过T论basic operator后，可以得到$S=2^T$个子图$\left\{X_{\mathcal{G}_{1}^{T}}, \ldots, X_{\mathcal{G}_{2 T}^{T}}\right\}$。

三、Multi-head

和多头注意力机制一样，使用S个可学习矩阵$\left\{W^{1}, \ldots, W^{S}\right\}$，并行执行basic operator，得到S个概率矩阵$\left\{P^{1}, \ldots, P^{S}\right\}$。如果$P_{j, 1}^{i} \geq \frac{1}{2}$，则表示子图$i$中保留节点$j$。

2.3.2 子图聚合

• 通过上述方法生成子图后，每个子图$\mathcal G_i$执行一个readout函数，得到子图表示$h(\mathcal G_i)$：

  $h\left(\mathcal{G}_{i}\right)=\mathbf{R E A D O U T}\left(X_{\mathcal{G}_{i}}\right) \in \mathbf{R}^{d}, i=1,2, \ldots, S\tag 9$

• 得到子图表示后，像集成学习一样，再利用subgraph-conv卷积操作将所有子图表示聚合到一起：

  $\tilde{h}(\mathcal{G})=\operatorname{subgraph}-\operatorname{conv}\left(\left[h\left(\mathcal{G}_{1}\right) ; h\left(\mathcal{G}_{2}\right) ; \ldots ; h\left(\mathcal{G}_{S}\right)\right]\right) \in \mathbf{R}^{d}\tag {10}$

2.4 模型训练

$\phi$表示模型所有参数，模型的目标函数定义为：

$\begin{aligned}\max \mathcal{L}_{\phi, \omega}^{u n s} & \triangleq \sum_{\mathcal{G} \in \mathbf{G}} \frac{1}{|\mathbf{G}|} \mathcal{L}_{\phi, \omega}^{u n s}(\mathcal{G}) \\&=\sum_{\mathcal{G} \in \mathbf{G}} \frac{1}{|\mathbf{G}|} I_{\phi, \omega}\left(h_{\phi}(\mathcal{G}) ; \tilde{h}_{\phi}(\mathcal{G})\right)\end{aligned}\tag{13}$

$I_{\phi, \omega}\left(h_{\phi}(\mathcal{G}) ; \tilde{h}_{\phi}(\mathcal{G})\right)$表示互信息，本文采用 Jensen-Shannon散度：

$\begin{aligned}I_{\phi, \omega}^{J S D}\left(h_{\phi}\right.&\left.(\mathcal{G}) ; \tilde{h}_{\phi}(\mathcal{G})\right) \\=& \mathbf{E}_{P}\left(-s p\left(-T_{\omega}\left(h_{\phi}(\mathcal{G}), \tilde{h}_{\phi}(\mathcal{G})\right)\right)\right.\\&-\mathbf{E}_{Q}\left(s p\left(T_{\omega}\left(h_{\phi}(\mathcal{G}), \tilde{h}_{\phi}(\mathcal{G})\right)\right)\right)\end{aligned}\tag{14}$

前面提到的目标函数只包括正样本，对于负样本的获取方式有两种：一是使用batch中的其他图，二是使用corruption函数污染原始图作为负样本。本文作者采用一种Head-Tail负样本采集方法，具体来说，对于图$\mathcal G^i$：

• head negative pair：通过shuffling节点嵌入$\hat{X}^{(0)}=$ Permute $\left(X^{(0)}\right) \in \mathbf{R}^{|V| \times d}$得到图$\hat{\mathcal G}^i$，$\left(h_{\phi}\left(\hat{\mathcal{G}}^{i}\right), \tilde{h}_{\phi}\left(\mathcal{G}^{i}\right)\right)$称之为头负样本对。
• tail negative pair：利用数据集中其他图$h_{\phi}\left(\mathcal{G}^{j}\right), j \neq i$生成尾负样本对$\left(h_{\phi}\left(\mathcal{G}^{j}\right), \tilde{h}_{\phi}\left(\mathcal{G}^{i}\right)\right)$。

得到这两种类型负样本对后，公式14可以改写成：

$\begin{aligned}\mathcal{L}_{\phi, \omega}^{u n s}(\mathcal{G})=& \mathbf{E}_{p\left(h_{\phi}(\mathcal{G}), \bar{h}_{\phi}(\mathcal{G})\right)}\left(-s p\left(-T_{\omega}\left(h_{\phi}(\mathcal{G}), \tilde{h}_{\phi}(\mathcal{G})\right)\right)\right.\\&-\mathbf{E}_{p\left(h_{\phi}(\mathcal{G})\right) p\left(\bar{h}_{\phi}(\mathcal{G})\right)}\left(s p\left(T_{\omega}\left(h_{\phi}(\mathcal{G}), \tilde{h}_{\phi}(\mathcal{G})\right)\right)\right.\\&-\mathbf{E}_{p\left(h_{\phi}(\hat{\mathcal{G}}), \bar{h}_{\phi}(\mathcal{G})\right)}\left(s p\left(T_{\omega}\left(h_{\phi}(\hat{\mathcal{G}}), \tilde{h}_{\phi}(\mathcal{G})\right)\right)\right.\end{aligned}\tag {17}$

在半监督学习中，我们还利用数据标签计算交叉熵损失：$\mathcal{L}_{\phi, \theta}^{s u p}\left(y_{\phi}\left(\mathcal{G}^{i}\right) ; y^{i}\right)=\mathbb{E}_{p_{\phi}\left(\mathcal{G}^{i} ; h\left(\mathcal{G}^{i}\right)\right)} \log p_{\theta}\left(y \mid h\left(\mathcal{G}^{i}\right)\right)$。此时整个半监督模型的损失函数定义为：

$\max \mathcal{L}_{\phi, \omega, \theta}^{s e m i}=\sum_{i=1}^{\left|G^{L}\right|} \mathcal{L}_{\phi, \theta}^{s u p}\left(y_{\phi}\left(\mathcal{G}^{i}\right) ; y^{i}\right)+\lambda \sum_{j=1}^{\left|\mathbf{G}^{L}\right|+\left|\mathbf{G}^{U}\right|} \mathcal{L}_{\phi, \omega}^{u n s}\left(\mathcal{G}^{j}\right)\tag{18}$

下图展示了模型的伪代码：

3. 实验

3.1 实验设置

一、数据集

无监督： TUDataset，MUTAG，PTC-MR，IMDB-BINARY和IMDB-MULTI，REDDIT-BINARY和REDDIT-MULTI-5K

半监督： QM9

二、实验配置

无监督： 采用图分类任务评估模型，具体流程和InfoGraph一致，采用10-fold交叉验证作为模型分类表现。实验重复7次，去除最大最小值后，取平均值作为最终结果。

半监督： 采用QM9数据集，随机每次随机选取5000个样本作为有标签样本，10000个样本作为验证样本，另外10000个样本作为测试样本，其余的作为无标签训练样本。

三、模型配置

无监督： 采用GIN作为base model，节点度作为初始节点属性，当没有边属性时不需要attribute-conv。所有hidden层维度都是128，batch大小128，GNN层数4，子图数量$S\in\{2,4,8\}$，初始学习率$10^{-3}$，epoch数量100。

半监督： 和无监督实验类似。

3.2 实验结果

3.2.1 对比实验

3.2.2 消融实验

这一部分主要对模型各个组件进行消融实验。

• BASE ：TS或者MH子图生成+layer-conv；
• BASE+NEG：表示在BASE基础上添加head negative samples；
• OURS：在BASE+NEG的基础上添加subgraph-conv。

可以看到，从第一行到最后一行，性能都是有所提升的，说明作者提出的模型中各个组件都是有效的。