机器之心编辑部

本文将分图神经网络历史、图神经网络的最新研究进展和图神经网络的运用进展三大部分归纳总结该课程 Theme II: Advances and Applications 部分的核心内容。
作者包括腾讯荣钰、徐挺洋、黄俊洲，清华大学黄文炳，喷鼻香港中文大学程鸿。

人工智能领域近几年历经了突飞年夜进的发展。
图像、***、游戏博弈、自然措辞处理、金融等大数据剖析领域都实现了超过式的进步并催生了很多改变了我们日常生活的运用。
近段韶光，图神经网络成为了人工智能领域的一大研究热点，尤其是在社交网络、知识图谱、化学研究、文本分析、组合优化等领域，图神经网络在发掘数据中隐含关系方面的强大能力能帮助我们得到更好的数据表达，进而能让我们做出更好的决策。
比如通过图神经网络梳理人类社会关系网络的演化，可有望帮助我们理解人类社会的底层运作模式，进而让我们离空想社会更近一步。

在今年的打算机协会国际数据挖掘与知识创造大会（ACM SIGKDD，简称 KDD）上，图神经网络备受研究关注的现状得到了充分表示：粗略统计，今年 KDD 吸收的 216 篇论文（research track）中有近 40 篇与图神经网络干系。
也因此，一场为期一天的图神经网络干系课程得到了参会职员的重点关注。
该联合课程的主题为「图深度学习：根本、进展和运用（Deep Graph Learning: Foundations, Advances and Applications）」，由腾讯 AI Lab、清华大学、喷鼻香港中文大学等机构联合组织，从根本的图观点一贯谈到了当今最前沿的图神经网络研究进展。

本次课程分为两个主题。
本文将分图神经网络历史、图神经网络的最新研究进展和图神经网络的运用进展三大部分归纳总结该课程 Theme II: Advances and Applications 部分的核心内容，Theme I 以及更多详细的内容可参看课程幻灯片及干系论文：https://ai.tencent.com/ailab/ml/KDD-Deep-Graph-Learning.html

为理解决图学习中的一系列具有寻衅性的问题， 探索图学习运用的边界并在于助力公司各种与图数据干系的业务。
腾讯 AI Lab 于 2017 年下半年开始布局图深度学习的研究，积极探索图深度学习的运用边界。
并且在各大机器学习数据挖掘顶级会议上揭橥多篇文章，涉及大图打算，超深图神经网络，无监督图学习，图的对抗攻击，图的样本学习等。
在未来我们将探索图深度学习在广泛场景的运用，如社交推举，药物研发等。
使其能够真正造福人类。

一 图与图神经网络

1 什么是图？

汉语中的「图」可以对应成英语中多个不同的词：image、picture、map 以及本文关注的 graph。
图（graph）也可称为「关系图」或「图谱」，是一种可用于描述事物之间的关系的构造。
图的基本构成元素为顶点和连接顶点的边。
根据边是否存在方向的性子，还可分为有向图和无向图。
一样平常而言，我们常日可将图表示成点和连接点的线的形式，这有助于我们更直不雅观地理解，如下图所示：

但为便于打算机处理，我们也可用矩阵来表示图。
比如如果定义当 v_i 与 v_j 相连时，A[i,j]=1，否则 A[i,j]=0，则可将以上矩阵表示为毗邻矩阵 A：

图具有很强的表征能力。
物理学系统建模、蛋白质预测、疾病分类以及许多文本和图像处理任务都可以表示成图构造的数据，比如图可用于表示文本中句子的依赖关系和图像中事物的相对位置，也可以用于剖析社交网络中的信息传播和用户关系，还能通过剖析分子之间的关联来创造新药。

2 图神经网络

近些年在大数据和硬件发展双重助力下迎来超过式发展的深度神经网络技能让我们具备了剖析和理解大规模图数据的能力。
总体而言，图剖析任务可分为节点分类、连接预测、聚类三类。

图神经网络（GNN）便是处理图数据的神经网络，个中有两种值得一提的运算操作：图过滤 (Graph Filter, 分为基于空间的过滤和基于谱的过滤）和图池化。
个中图过滤可细化节点特色，而图池化可以从节点表示天生图本身的表示。

一样平常来说，GNN 的框架在节点层面上由过滤层和激活构成，而对付图层面的任务，则由过滤层、激活和池化层组成不同的模块后再连接而成。

在 GNN 的实现方面，目前最常用的方法是通报框架（Message Passing Framework）。
大略总结起来，该框架分为两个步骤。

第一步是天生步骤。
首先，从隔壁节点网络状态数据，然后利用对应函数天生当前节点的。
在第二步中，我们更新目标节点的状态。

目前大多数空间式 GNN 都可以构建为某种通报过程，而且事实上目前大多数用于图的深度学习工具包大都采取了这一框架，比如 Deep Graph Library 和 PyTorch Geometric。

3 图神经网络的发展历史

图神经网络（GNN）并不是一个新事物，最早的 GNN 的历史可以追溯到 1997 年，粗略总结起来，GNN 的发展过程大致可分为三个阶段。

在第一个阶段，GNN 所利用的紧张方法是基于循环神经网络（RNN）的扩展。
众所周知，RNN 善于处理序列数据，而反过来，序列数据则可被视为一种分外模式的图。
因此，早期的一些事情（TNN97 / TNN08）将处理序列数据的 RNN 泛化用于树和有向无环图（DAG）等分外的图构造。
但那之后这一领域的发展险些陷入了结束状态。
然而，在当前这轮深度学习热潮的带动下，对非构造化数据的建模和处理的研究开始广泛呈现，GNN 也迎来了自己的发展契机，顶级会议上的干系论文数量也迅猛增长。

在第二个阶段，卷积被引入到了 GNN 的事情流程中。
当用矩阵进行表示时，图与卷积德于处理的图像具有很多相似性，也因此开启了在 GNN 中利用卷积的时期。
一系列的事情将在谱空间上的图卷积转换为了拓扑空间上的近似，并在此根本上于 2017 年出身了图卷积网络（GCN），其首次利用了逐层卷积来扩展感想熏染野，图神经网络也由此开始了实际运用。

我们现在正处于 GNN 发展的第三个阶段。
图卷积已经涌现了多种变体，把稳力机制已被引入 GNN 中，此外还涌现了图池化（Graph Pooling）技能和高阶 GNN。
这一阶段涌现的主要技能包括：

变体卷积：Lanczos 网络（利用 Lanczos 算法来获取图拉普拉斯的低秩近似）、图小波神经网络（利用小波变换替代傅里叶变换）、双曲 GCN（将 GCN 构建到双曲空间中）。

把稳力机制：图把稳力网络（利用可学习的自把稳力更换固定的聚合权重）、门控把稳力网络（加入了可学习的门来建模每个头的主要度）、谱式图把稳力网络（将把稳力运用于谱域中的高 / 低频组件）。

图池化：SAGE（自把稳图嵌入，在池化时利用自把稳力来建模节点主要度）、通过图剪切实现图池化（通过图剪切算法得到的预演习子图实现图池化）、可微分图池化（DIFFPOOL，通过学习聚类分配矩阵以分层办法来聚合节点表征）、特色池化（EigenPooling，通过整合节点特色和局部构造来得到更好的分配矩阵）。

高阶 GNN：高阶 GNN 是指通过扩展感想熏染野来将高阶附近度（high-order proximities）编码到图中。
高阶附近度描述的是间隔更多样的节点之间的关系，而不仅是隔壁节点之间的关系。
这方面的研究事情包括 DCNN（通过把转移矩阵的幂级数堆叠起来而将毗邻矩阵扩展为张量，然后相互独立地输出节点嵌入和图嵌入）、MixHop（利用了归一化的多阶毗邻矩阵，然后搜集各阶的输出，从而同时得到高阶和低阶的附近度）、APPNP（利用了个性化 PageRank 来为目标节点构建更好的隔壁关系）。

下图大略总结了各种 GNN 变体之间的关系：

二 图神经网络的研究进展

理解了 GNN 的基本知识和发展脉络，接下来我们将踏入当前的前沿研究领域，解读近期的一些理论研究成果和设计创新。

1 图神经网络的表达能力

我们知道图在表达事物的关系方面能力非凡，但图神经网络表达能力的极限在哪里？清华大学打算机系助理研究员、清华大学「水木学者」、腾讯「犀牛鸟访问学者」黄文炳在课程中先容了干系的研究进展。

为了有效地评估 GNN 的表达能力，首先须要定义评估标准。
目前来说，可通过三种范例任务来进行评估：图同构、函数近似和图检测 / 优化 / 评估。

对付图同构任务，GNN 的目标是确定任意给定的两个图是否同构。
这是一个很主要的任务。
对付图分类任务而言，如果两个图是同构的，则 GNN 须要为这两个图输出同样的标签。

但是，剖断图是否同构的问题是一个 NP-hard 问题，传统的 Weisfeiler-Lehman（WL）测试方法除了少数图构造外，基本能否识别大多数图构造是否同构。
而 GNN 能更好地办理这一问题吗？

并不一定。
2019 年，Xu et al. 和 Morris et al. 已经证明 GNN 至多做到与 WL 测试一样强大。
之后，Xu et al. 还进一步证明，如果 GNN 中的聚合和读出函数（readout function）是单射函数，则 GNN 就与 WL 测试等效。

对付函数近似任务，该任务的目标是判断 GNN 能否以任意准确度近似任何基于图的函数。
由于 GNN 本身也是基于图的某种函数，因此 GNN 在这一任务上的表现将能表示其能力。
实际上，DNN 也有类似的评估任务。
我们知道，只要隐蔽单元足够多，DNN 可以收敛到任何向量函数，这便是所谓的「通用近似定理」。
以是我们很自然也会为 GNN 提出类似的问题。

Maron et al. 提出了一种架构，对付拥有图不变映射层（graph invariant layer）和图等变映射层（graph equivariant layer）的 GNN，如果在一个非线性层（比如 ReLU）之后堆叠等变映射层，层层叠加，然后在末了添加图不变映射层。
可以看出这样的模型能在输入的排列办法变革时保持映射不变性。
这样的模型被称为图不变网络（INN）。

INN 有多强大？Maron et al. 证明对付任意连续的不变式图函数，如果某些条件成立，我们可以找到特定的 INN 参数，使其能以任意精度估计该函数。
这是图学习领域一大强有力的理论结果。
对 GNN 而言，这就相称于对 DNN 而言的通用近似定理。

看过了图同构和函数近似的近期进展，更进一步，这两者之间又有何关系呢？Chen et al. 2019 证明在知足一些条件的情形下，这两者实在是等效的。

接下来，我们看看 GNN 是否有足够的表达能力来办理更困难的任务，比如探求图中的最短路径或确定图中是否存在环。
这些任务的难度很高，由于它们须要在节点层面实行很细粒度的推理。

Loukas 证明 GNN 能办理这些任务，他得出结论：只要 GNN 的深度和宽度足够，而且节点之间具有可相互判别的属性，则 GNN 就能完成这些任务。
这里深度是指 GNN 的层数，宽度则是指隐蔽单元的维度。

因此，总结起来，只要架构得当，GNN 实在具有非常强大的表达能力；也因此，要充分发掘 GNN 的真正实力，我们还须要更多架构方面的研究探索。

2 演习深度图神经网络

前面已经大略提到，深度对 GNN 的能力而言是非常主要的。
这一点在深度神经网络（DNN）上也有表示——更深的网络每每具有强大的表达能力，可以说深度网络便是当前的人工智能发展热潮的最紧张驱动力之一。

那么，详细来说，更深度的 GNN 是否也有如此的上风呢？更深度的 GNN 能否像 CNN 一样得到更大的感想熏染野？

答案当然是肯定的。
举个例子，探求最短路径问题须要非常深的感想熏染野来探求所有可能的路径，环检测和子图查找问题也都须要较大的感想熏染野。

那么，我们可以若何增大 GNN 的感想熏染野，使其具备更强大的能力呢？为此，我们须要更深或更宽的 GNN。

首先来看通过大略增加深度来扩展 GNN 的方法。
可以看到，对付下图中的六种 GNN：GCN、GraphSAGE（进一步改进了池化方法）、ResGCN（利用了残差网络的思路）、JKNet（利用了 DenseNet 的思路）、IncepGCN（利用了 Inception-v3 的思路）、APPNP（借用了 PageRank 的思路），大略增加深度并不一定能提升准确度，乃至还可能涌现相反的状况，比如 GCN、GraphSAGE 和 ResGCN 在深度增大时准确度反而显著低落。

这不禁让人疑问：增加深度能提升表达能力的根本缘故原由是什么？又是什么缘故原由阻碍了 GNN 的深度扩展？

近期的研究找到了有碍 GNN 变得更深的三大根本缘故原由：过平滑（over-smoothing）、过拟合（overfitting）和演习动态变革（training dynamics）。
个中后两者也是常见的深度学习问题，而过平滑则是图深度学习方面特有的问题。

过平滑

首先来看过平滑。
GNN 实质上是逐层推送彼此相邻节点稠浊的表征，因此极度地看，如果层数无限多，那么所有节点的表征都将收敛到一个驻点，这也就与输入特色完备无关了，并会导致梯度消逝问题。
因此，过平滑的一个征象是模型的演习丢失和验证丢失都难以低落。
那么，为什么会涌现过平滑呢？

我们以线性 GCN 来进行解释。
首先，GCN 与平滑有何关联？一样平常来说，GCN 可被视为拉普拉斯平滑（Laplacian smoothing）的一种分外形式，如下所示：

这个过程意味着一个节点的新特色是根据其本身和相邻节点的加权均匀而构建的。

要知道这个过平滑过程发生的位置，我们先谈论一下 GCN 何时会因过平滑而失落效？我们将谈论三种过平滑的情形。
第一种是利用线性激活时，隐变量 H_L 会收敛到一个特定的点。
第二种是利用 ReLU 激活时，H_L 会收敛到一个特定的平面 M。
第三种是利用 ReLU 加偏差时，H_L 会收敛到一个特定的子立方体 O(M, r) 的表面。

在利用线性激活的情形下，H_L 为什么会收敛到一个特定的点呢？实际上，这与 L 步随机游走有关。
一个游走器从一个节点游走到其一个相邻节点的概率为「1 / 该节点的度」。
经由 L 步游走后，游走的路径会形成一个已访问节点的序列。
用数学公式表示，随机游走的过程实际上便是一个归一化的矩阵的 L 次幂乘以初始概率。

然后，如果我们用一组在节点特色上的可学习参数更换这个初始概率，它就能转换成一个线性的 L 层 GCN。

可以看出，基于随机游走的一些结论也适用于线性 GCN，个中一项便是随机游走在经由无限多步之后会收敛到一个驻点。

详细地说，我们首先须要进行特色值分解，即将归一化的毗邻矩阵分解为 n 个特色值 λ 及其对应的特色向量 u。

将这个求和展开，可得到下式：

这个图谱中的特色值有一个性子。
即，假设一个图 g 包含 m 个相互连接的分量，则归一化毗邻矩阵的特色值便由 m 个为 1 的最大特色值构成，别的的 λ 则在 (-1,1) 的开区间中。

因此，当 lL 趋近无穷大时，最大的 m 项依然存在，由于其 λ 即是 1。
但是，别的的项都将被忽略，由于这些 λ 的 l 次幂将趋近于零。
这会使得隐变量 H_L 随网络深度增长而趋近于一个特定的点。

另一方面，对付非线性的情形，H_L 将收敛到一个具有非线性激活 ReLU 的特定子空间 M。
首先我们给出 M 子空间的定义：

则随着层的深度增加，隐变量将越来越靠近子空间 M。
H_L+1 离该子空间的间隔至少为：

要把稳，λ_m+1 是毗邻矩阵中最大的非 1 特色值，s_l 则是模型参数 W_l 中最大的奇异值。

接下来我们开始解析这个收敛公式。
这个归一化毗邻矩阵的收敛知足这一不等式。

如果我们假设这个子空间的维度为 m，则 m 个最大的 λ 将位于该子空间，别的的则在 λ_m+1 的范围内。

然后，模型参数 W_l 和 ReLU 的收敛分别知足下列两个不等式：

有关这些不等式的更详细证明，请参阅 ICLR 2020 论文《Graph Neural Networks Exponentially Loss Expressive Power for Node Classification》。

综合这些不等式，可得到隐变量的子空间间隔沿层数变革的收敛性。
可以看到，随着层数趋近于无穷大，子空间间隔将趋近于 0，因此隐变量将会收敛到子空间 M。

接下来是更一样平常的情形，利用 ReLU 加偏差的 GCN 又如何呢？H_L 将收敛到一个特定子立方体 O(M,r) 的表面上。
首先，我们写出带偏差的 GCN 的公式：

很显然，由于 b_l 到子空间的间隔是一个常量，因此其收敛性就知足：

可以看到，当 l 趋近无穷大时，不等式右侧部分便是一个无穷等比序列的和：

因此，可以看到 H_L 将趋近于一个子立方体的表面，其与子空间 M 的间隔为 r，而 r 就即是上式。

总结一下，通过剖析上面三种来自不同场景的情形，可以创造这三种情形之下存在一种普适的公式。
我们可用以下不等式统一过平滑的情形：

然后通过不同的 v 和 r 取值，我们可以得到不同的详细情形：

过拟合和演习动态变革

接下来我们看看过拟合问题。
过拟合是深度学习的一个常见问题，当数据点数量少而参数数量很多时，就会涌现这种情形。
此时模型会与演习数据完备拟合（实质上便是记住了数据），而在验证数据上表现很差。

演习动态变革也是深度学习领域的一大常见问题。
根据链式法则，当模型变深时，s_l-1 乘以 λ_m+1 的结果小于 1，会涌现梯度消逝问题。
如果我们将 RGB 色彩作为以下的图的节点特色，可以看到当层数达到 500 时，这些特色的梯度降为了 0，节点都变成了玄色，即 RGB=[0, 0, 0]。

过拟合和演习动态变革是深度学习的常见问题，这里便不过多赘述了。
下面我们看看在办理过平滑问题方面有什么研究进展。

如何办理过平滑问题？

首先，如何量化平滑？以 GCN 为例，我们先定义一个 ε- 平滑，使得对付任意大于特定层 L 的 l，隐变量 H_l 的子空间间隔将小于 ε：

然后，将 ε- 平滑层定义为能让 H_l 的子空间间隔小于 ε 的最小层。
但是，ε- 平滑层是很难推导的。
因此，我们取一个松弛化的 ε- 平滑层作为上界。
这个松弛化的 ε- 平滑层的公式如下：

用层量化了平滑之后，我们就可以想办法来缓解过平滑问题了。

把稳这里的 λ_m+1 与毗邻矩阵干系，s_max 与模型权重干系，这也暗示了存在两个缓解过平滑问题的方向。

第一，我们可以通过处理毗邻矩阵来缓解过平滑，即增大 λ_m+1，进而使得松弛化的 ε- 平滑层增大：

那么我们如何做到这一点呢？很大略，在每 epoch 都丢弃一些边即可。
研究证明，当丢弃一些边时，图上信息的传播速率会低落，子空间的维度会随连接的分量的增多而增加。
丢弃边后的这两个征象都有助于缓解过平滑问题。

更多详情和实验论证可见腾讯 AI Lab 的 ICLR 2020 论文《DropEdge: Towards Deep Graph Convolutional Networks on Node Classification》。

第二，我们可以通过调度模型权重来缓解过平滑。
为了增大 s_max，我们可以增大初始 W_ls 的值。
下图展示了这种方法的效果。
详见 ICLR 2020 论文《Graph Neural Networks Exponentially Lose Expressive Power for Node Classification》。

其它问题的办理方案

ICLR 2020 上还有一篇论文《PairNorm: Tackling Oversmoothing in GNNs》提出了一种用于办理演习动态变革问题的方法。

PairNorm 的思路对 GCN 输出进行居中和重新缩放或归一化，使得总的两两平方间隔保持不变。
如图所示，GCN 的输出点在图卷积之后常日会更靠近彼此。
但通过利用 PairNorm，新输出的两两间隔能与输入的间隔保持相似。

另一种战胜演习动态变革的方法是在构造中添加捷径。
JKNet、IncepGCN 和 APPNP 等 GNN 能在深度构造中保持性能的方法便是如此。

由于这三个模型全都包含通过聚合层到终点的捷径，因此浅的信息可以传播到末了的层，也因此这些模型实际上仍旧是「浅模型」。

顺便一提，这些不同的 GNN 构造仍旧知足过平滑的一样平常情形：

详细的剖析请参考论文：《Tackling Over-Smoothing for General Graph Convolutional Networks》（https://arxiv.org/pdf/2008.09864.pdf）。
总结一下，在这些新的理论进展的帮助下，演习更深度 GNN 的问题已经得到了初步解答。

3 大规模图神经网络

真实天下的图可能具有非常大的规模，因此让 GNN 有能力处理大规模图是非常主要的研究课题。

基本的 GNN 常日无法处理大规模图，由于其常日无法知足巨大的内存需求，而且梯度更新的效率也很低。

为了让 GNN 有能力处理大规模图，研究者已经提出了三种不同的采样范式：基于节点的采样、基于层的采样和基于子图的采样。

个中，逐节点采样是根据目标节点实行采样，而逐层采样是基于卷积层来实行采样，逐图采样则是从原图采样子图，然后利用子图进行模型推理。

根据这三种范式，可以知道为了实现大规模 GNN，我们须要办理两个问题：如何设计高效的采样算法？如何担保采样质量？

近些年在构建大规模 GNN 方面已经涌现了一些成果，下图给出了这些成果的韶光线：

接下来我们将按这一韶光线简要先容这些研究成果。

首先来看 GraphSAGE，其可被视为原始 GCN 的一种扩展：在 GCN 的均匀聚合器的根本上增加了许多广义上的聚合器，包括池化聚合器和 LSTM 聚合器。
不同的聚合器也会对模型产生不同的影响。
此外，在聚合之后，不同于 GCN 利用的求和函数，GraphSAGE 利用了连接函数来结合目标节点机器临近节点的信息。
这两大改进是基于对 GCN 的空间理解得到的。

为了实现大规模 GNN，GraphSAGE 首先采取了 mini-batch 的演习方法，这样可以降落演习期间的通信本钱。
在每次迭代中，仅会考虑用于打算表征的节点。
但是，mini-batch 演习可能涌现临近节点扩展的问题，使得 mini-batch 在层数较多时须要采取图的大部分乃至全部节点！

为理解决这一问题并进一步提升性能，GraphSAGE 采取了固定采样个数的的临近采样方法，即每层都采样固定大小的临近节点凑集。

从上右图可以看到，采取固定采样个数的采样方法后，采样节点的数量降落了。
当图的规模很大时，这一差距会更加显著。
不过，GraphSAGE 在网络层数较大时依然无法避免临近节点扩展问题，采样质量上也无法得到担保。

为了进一步降落采样规模和得到一些理论上的质量担保，VR-GCN 整合了基于掌握变量的估计器（CV 采样器）。
其可以坚持历史隐蔽嵌入（historical hidden embedding）来得到更好的估计，这个历史隐蔽嵌入可用于降落方差，进而肃清方差，实现更小的采样规模。
VR-GCN 的数学形式如下：

不过，VR-GCN 也有一个缺陷：须要额外的内存来存储所有的历史隐蔽嵌入，这使得我们难以实现大规模扩展。

上面我们可以看到，基于节点的采样方法并不能彻底办理临近节点扩展问题。
接下来看基于层的采样方法。

FastGCN 提出从 Functional generalization 的角度来理解 GCN，并为 GCN 给出了基于层的估计形式：

基于此，我们可以在每层都采样固天命量的节点。
更进一步，FastGCN 还提出了基于主要度的采样模式，从而降落方差。
在采样过程中，每一层的采样都是相互独立的，而且每一层的节点采样概率也保持同等。
下图是 GCN 与 FastGCN 的比拟：

可以看出，FastGCN 的打算本钱显著更低，而且研究表明，这种采样模式从期望上并不会丢失太多信息，由于其在实行主要度采样时会进行随机化处理，通过足够多 epoch 的演习，每个节点和链接都有期望被采样。

可以看出，基于层采样的 FastGCN 彻底办理了临近节点扩展问题，而且采样方法有质量担保。
但是该方法的缺陷是无法得到层之间的干系性，模型的表现也可能受到负面影响。

为了更好地得到层之间的干系性，ASGCN 提出了自适应层式采样方法，即根据高层采样结果动态调度更低层的采样概率。
如下左图所示，在对底层采样的时候 ASGCN 会考虑采样高层采样的邻居节点，使得层之间的干系性得到很好的保留。
如下右图所示，全体采样过程是自上而下的。
我们首先采样输出层的目标节点，然后根据其采样结果采样中间层的节点，然后重复这个过程直到输入层。
在采样过程中，每层采样节点的数目也会保持一个固定值。

其余，为了降落采样方差，ASGCN 还引入了显式方差低落法（explicit variance reduction），以优化丢失函数中的采样方差。

总体来说，ASGCN 能得到更好的性能，方差掌握也更好，但由于采样过程有额外的层间依赖关系须要考虑，采样效率会受到一些影响。

接下来涌现了基于子图的采样方法。
ClusterGCN 首先利用图分割算法将图分解为更小的聚子图，然后在子图层面上组成随机的分批，再将其输入 GNN 模型，从而降单次打算需求。

通过限定子图的大小，这种方法也可以有效避免临近节点扩展问题，由于在每一层中，采样的范围都不会超过聚类子图。

不过，ClusterGCN 的论文并没有对这种方法的采样质量进行实证研究。

GraphSAINT 则并未在采样过程中利用聚类算法（这会引入额外的偏差和噪声），而是直接通过子图采样器来采样用于 mini-batch 演习的子图。
其给出了三种采样器的构建办法，分别为基于节点的采样、基于边的采样和随机游走采样，如下所示：

GraphSAINT 还从理论上剖析了掌握采样器的偏差和方差的方法，个中包括用于肃清采样偏差的丢失归一化和聚合归一化方法：

其余，该论文还提出通过调度边采样概率来降落采样方差。
作为当前最佳的方法，GraphSAINT 的表现也在实验中得到了证明。
详细详情请浏览 ICLR 2020 论文《GraphSAINT: Graph Sampling Based Inductive Learning Method》。

很显然，大规模图神经网络方面还有很大的进一步研究空间，比如更高效的采样技能、适用于异构图或动态图的架构等等。

4 图神经网络的自监督 / 无监督学习

前面谈论的 GNN 的表达能力、深度和规模都是基于监督式方法，也便是说我们有输入图的标签。
但在现实生活中，获取这些标签却并非易事。
比如在分子属性预测任务中，为了获取基本真值标签，我们必需专业人士的帮忙。
此外，演习任务与测试任务并不总是同等的，比如对付社交网络推举任务，我们可能在演习中利用的是节点用户购买商品的数据，但我们却想知道节点用户是否想看某部电影，此时演习标签可能对测试就毫无浸染了。
因此，我们须要研究如何在没有标签的情形下演习 GNN。

目前在自监督图学习方面已经有一些研究成果了。
我们可以根据它们的机制将其分为两大种别：预测方法和基于信息论的方法。
而根据所要办理的任务的差异，又可以分为两种情形：节点分类和图分类。

预测方法

首先来看预测方法。
Yann LeCun 说过：「自监督学习的系统是根据其输入的某些部分来预测输入的其它部分。
」这就意味着在自监督学习中，输入的构造是很主要的。
而图便是高度构造化的，因此天生就很适宜自监督学习。

对付节点分类任务，实现自监督学习的方法常日有两种。
一是逼迫利用相邻节点之间的相似性，二是基于临近节点实行每个节点的重修。

首先，我们来看第一种方法，这种方法由 GraphSAGE 引入，其基本思想是逼迫每个节点与其临近节点有相似的表征。
在这种情形下，设 h_u 为 h_v 的临近节点，则我们的目标是最大化它们的内积。
我们称这些临近节点为正例样本。
然后，我们最小化 h_v 与通过负采样得到的其它节点之间的相似性，这些节点常日是从全体图均匀采样的。
这样，我们就可以利用反向传播来演习 GNN 的参数了。

至于第二种方法，来自 Durán & Niepert 提出的 EP-B，其首先司帐算临近节点的表征的聚合。
目标是最小化重修的结果与真实表征之间的间隔。
与此同时，又最大化这个聚合表征与其它节点的表征之间的间隔。

EP-B 和 GraphSAGE 的紧张差异是 EP-B 逼迫利用了临近节点和每个其它节点的聚合之间的相似性，而 GraphSAGE 则直接逼迫利用了临近节点与每个节点的相似性。

在图分类方面又有哪些方法呢？

我们要先容的第一种方法是 N-Gram Graph。
该方法分为两个阶段：节点表征阶段和图表征阶段。
节点表征阶段利用了一种传统的自监督式节点嵌入方法 CBoW 来学习节点表征。
在第二个阶段，由于已有节点表征，则首先会为每条长度为 n 的路径打算表征，称为 n-gram 路径。
这个路径表征因此该路径中每个节点的表征的积形式得到的。
因此，它们将历经图中所有的 n-gram 路径并归总所有路径的表征。
终极的图表征是通过将 1-gram 到 T-gram 的路径连接起来而得到的。

事实上，这样的打算就即是没有演习的 GNN。
N-Gram Graph 的演习无需任何监督。

另一种用于图分类的方法是 PreGNN，它同样分为两个阶段：第一个阶段是实行节点表征（但利用了两种全新方法），第二阶段是利用大略的读出基于所有节点获取图层面的表征。
但它是通过一种监督式策略交叉熵来演习图层面的表征。
该研究指出，节点层面和图层面的演习对终极性能而言都很主要。

由于其第二个阶段很普通，以是我们只解读一下第一个阶段。

在这一阶段，PreGNN 提出了两种丢失函数。
周围构造预测（context prediction）是逼迫节点表征与其周围构造相似。
其余我们还实行负采样来最小化 h_v 与其它节点的周围构造之间的相似性。
这个方法的思路很大略：每个节点周围的构造定义了该节点的局部拓扑构造。

另一个丢失则是属性掩码（attribute masking）。
这个丢失的设计灵感来自强大的 NLP 模型 BERT。
大略来说，便是随机地利用掩码更换节点，然后构建演习丢失函数来预测输入。
方法很大略，但效果很好。

另一种值得一提的方法是 GCC。
该方法利用了比拟学习（contrastive learning）来实行图层面的无监督学习。
不过 GCC 的一大紧张问题是没有节点层面的演习。

总结一下，在图分类任务上，N-Gram Graph 和 PreGNN 都利用了节点层面的自监督，而 GCC 利用了图层面的自监督。
那么，我们自然会问：能不能同时利用节点层面和图层面的自监督？

答案当然是肯定的。
这就要谈到腾讯 AI Lab 研究团队提出的 GROVER 了。

GROVER 同样分为两个阶段。
在节点阶段，我们还同时考虑了边，但为相识释大略，这里仅谈论节点表征过程。
在这一阶段，首先为每个节点提取一个词典池。
我们称之为 key。
然后我们像 BERT 一样为每个节点加掩码，然后预测每个节点周围的局部构造。
如果局部构造与词典中的一个 key 匹配，则在该维度上输出 1，否则便输出 0。
把稳这是一个多标签分类问题，由于每个节点的局部构造常日有多个。
这样，我们仅须要一类掩码就能做到 PreGNN 的两件事。

然后在图阶段，预测是相似的。
我们也首先提取 graph motif，其由范例的官能团（比如苯环）构成。
然后我们利用 GNN 获取每个图的输出。
利用该输出，我们将预测这个图是否包含这些 graph motif。
把稳这也是一个多标签分类问题。

除此之外，腾讯 AI Lab 还在该研究中提出了一种类似 Transformer 的强大 GNN 模型：GTransformer。
其首先会利用一种新提出的名为 dyMPN 的 动态扩展范围 MPNN 来获取每个输入图的 key、查询和值，然后会像 Transformer 一样获取终极输出结果。
实验结果证明了这一模式的强大能力。

以上这些便是 GROVER 的关键组件。
更进一步的，我们还实现了一个分布式的图演习框架，终极成功在 1000 万个无标注分子数据上预演习带有 1 亿个参数的大模型。

利用这个预演习的模型，我们可以针对下贱任务进行微调。
在此根本上，GROVER 可以取得显著优于 MPNN 和 DMPNN 等传统方法的表现，同时也优于 N-Gram 和 PreGNN 等自监督方法。

基于信息的方法

先容了预测方法，我们再来看基于信息的方法。

优秀的表征该当能将输入中的大量信息保存下来。
受此启示，Vincent et al. 在 2010 年提出利用自动编码器来进行表征学习，这意味着隐蔽表征该当可以解码到与其输入一样。

但自动编码器资源花费高，既须要编码，也须要解码，而在图领域，如何解码图仍还是一个有待办理的问题。
那么还有其它可以直接衡量表征与输入之间的信息的方法吗？有的，那便是互信息（mutual information）。

给定两个随机变量，互信息的定义是它们的边界属性和枢纽关头属性的积之间的 KL 散度，这又可以进一步推导为熵减去条件熵。

互信息为什么可以打算信息关系？我们可以这样看，如果 X 和 Y 相互独立，且 p(X)p(Y)=p(X,Y)，则互信息即是 0，这表明 X 和 Y 不干系。
这是合理的，由于 X 和 Y 相互独立。
如果条件熵为 0，则 X 和 Y 确定是干系的，则互信息输出为最大值。

Hjelm et al. 2019 证明实行自动编码是打算互信息的重修偏差的一个下限。

打算互信息是很困难的，近些年方才涌现一些可行的方法。
这里有三种范例的方法（MINE、JSD MI 和 infoNCE MI），其基本思想是学习一个神经网络来最大化互信息的一个替代函数。
详情请参阅各论文。

回到图，我们能否利用互信息来实现图的自监督学习？DGI 是这方面首个研究成果，其目标设定为最大化输入的节点特色 X 和毗邻矩阵 A 与输出表征 h_i 之间的互信息。
DGI 利用了 JSD 估计器，个中包含正例项和负例项。

但直接打算互信息的难度不小，我们可能须要另一个 GNN 作为互信息的替代。
DGI 利用了表征的读出 s 来替代输入。
如下图所示，原图有两个输入，个中缺点的图是负例，然后我们用同样的 GNN 得到它们的输出，之后再实行读出函数得到 s。
s 可以替代原目标中的 X,A，得到替代目标函数。

DGI 证明这种操作不会导致信息丢失，其还证明这种更换办法实际上就等同于真正的互信息。

不过 DGI 仍还有一些问题。
第一是它须要读出函数来打算互信息，而且这个读出函数须要是单射式的，这并不随意马虎担保。
其余它还须要构建缺点的图来得到负例，因此效率不高。
而在实验中，DGI 须要为不同的任务利用不同的编码器，这并不实用。

针对这些问题，清华大学、西安交通大学与腾讯 AI Lab 互助提出了 GMI，其基本思想是不该用读出函数和缺点样本，而是直接打算互信息。

在 GMI 中，首先分两部分定义互信息。
一是特色互信息，仅度量节点特色和表征之间的信息关系。
二是拓扑互信息，这是预测的边和原始毗邻矩阵之间的互信息。

很显然，这一方法能同时考虑到边和特色，而无需读出函数或缺点样本。
更主要的是，特色互信息还能进一步分解。

我们证明：特色互信息可以分解为局部互信息的加权和。
而每个局部互信息打算的是每个节点及其表征之间的互信息。
权重取决于不同的情形，将它们设置为与预测的边一样也不错。
然后我们可以利用 JSD 互信息估计器来打算特色互信息和边互信息。

在节点分类任务上的实验结果证明 GMI 有更优的表现，干系的代码也已经发布：https://github.com/zpeng27/GMI

至于用于图分类的基于信息的方法，可参看 ICLR 2020 论文《InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization》，这里不再过多赘述。

三 图神经网络的运用进展

图神经网络作为一种有效的深度学习工具，已经在分子属性预测、生物学剖析、金融等许多领域得到了运用。
这里以腾讯 AI Lab 实现的在社交网络和医疗影像领域的运用为例，先容图神经网络的运用进展。

1 用于社交网络的 GNN

首先来看一篇 WWW 2019 论文《Semi-supervised graph classification: A hierarchical graph perspective》，个中腾讯 AI Lab 提出了利用分层图实现半监督图分类的方法。

分层图是指一组通过边相互连接在一起的图实例，如图所示：

在许多现实运用中，很多数据都可以建模身分层图的形式，比如具有分组构造的社交网络和文档凑集（比如具有引用关系的 graph-of-words）。
如上所示，假设我们有一个「用户 - 分组」分层图，我们知道个中部分标签，我们可以若何预测其它组的标签？

如果仅考虑组之间的联系，那么这个问题就又回到了节点分类。
但是，可以看到每一组都有自己的用户图，忽略这样的信息并不得当。
为了在用户和分组层面上利用图信息，我们面临着这样的难题：如何将任意大小的图表征为固定长度的向量？如何整合实例层面和分层层面的信息？

首先来看第一个问题。
图表征与节点表征在不同的层面上；在节点层面上图 G 会被投射到大小为 n×v 的隐蔽空间中；而在图层面上图 G 会被投射成大小为 v 的隐蔽向量。
因此，为了将节点层面的空间转换成图层面的向量，这里引入了自把稳力争嵌入（SGAE）。

首先，将单个图通过一个两层 GCN，得到节点层面的表征 H，其大小为 n×v，然后根据上图中的 S 打算自把稳力。
在经由一个 softmax 函数之后，会得到一个具有 r 个头的多头自把稳分数，其大小为 r×n。
然后，如果我们将这些分数运用到节点层面的表征，我们就会得到大小固定为 r×v 的矩阵。
SAGE 有三大上风：1）其大小因自把稳力而保持不变，2）由于 GCN 平滑而具有排列不变性，3）由于自把稳力而能利用节点主要度。

对付第二个问题：如何整合实例层面和分层层面的信息？这里实例层面是基于 SAGE 的图层面学习，分层层面模型是节点层面的学习。
我们利用了特色共享来连接 SAGE 的输出和 GCN 的输入。
然后又引入一种新的不合丢失（disagreement loss）来最小化实例分类器和分层分类器之间的不一致情形。

其余，我们还利用了主动学习来办理样本数量少的问题。
我们利用了不合丢失来为外部标注选择实例。
有关这两种算法 SEAL-AI 和 SEAL-CI 的详情以及干系实验结果请查阅论文。

接下来看腾讯 AI Lab 另一项被 AAAI 2020 吸收的研究《Rumor Detection on Social Media with Bi-Directional Graph Convolutional Networks》，提出了一种通过双向图卷积网络实现社交网络谣言检测的新思路。

谣言可算是当今社会面临的一大顽疾。
这篇论文提出通过关注和转发关系来检测社交媒体上的谣言。
不管是谣言还是***，它们的传播模式都是树构造的。
但常日来说，谣言的传播有两个属性。
第一如下图 b 所示，其会沿一条关系链进行很深的传播。
第二如图 c，谣言在社交媒体上传播时散布很宽。
举个例子，一个 Twitter 用户可能有大量关注者。

为了同时获取谣言传播的这两种属性，我们设计了一种基于 GCN 的新模型。
这个用于谣言检测的双向 GCN 包含 4 个组件：1）两个不同的有向图，用于描述谣言的传播和扩散度；2）利用二层 GCN 来打算高层面的节点表征；GCN 不仅能学习特色信息，还能学习谣言的传播拓扑构造；3）经由不雅观察，根节点常日就已经包含了谣言或***的紧张内容，而关注者常日只是不带任何内容进行转发，因此通过将根特色连接到树中的每个节点，可以增强每层的隐蔽特色；4）分别根据节点表征对传播和扩散度的两个表征进行池化处理。
这两个表征再被聚合到一起得到终极结果。

我们在 Twitter15、Twitter16、Weibo 三个常用基准上的实验研究对这一方法的效果进行验证，结果表明新方法具有显著更优的表现。

此外，我们还评估了谣言的早期侦测，此时仅给出谣言树上非常有限的节点并且还设置了一个侦测截止韶光，结果表明基于图的方法非常适用于早期创造谣言。

2 用于医疗影像的 GNN

医疗影像也是 GNN 的一个主要运用处景，腾讯 AI Lab 近两年在这一领域取得了一些主要的研究成果。
首先来看腾讯 AI Lab 的 MICCAI 2018 论文《Graph CNN for Survival Analysis on Whole Slide Pathological Images》，个中提出利用图卷积网络基于全切片病理图像进行生存剖析。

生存剖析的目标是预测特定事宜发生的风险，这类事宜包括器官衰竭、药物不良反应和去世亡。
有效的剖析结果具有主要的临床运用代价。
但实际操作时却面临着许多困难。

首先，全切片病理图像（WSI）剖析是一个须要大量打算的过程，由于单张 WSI 的数据量就超过 0.5 GB，而且个中包含数百万个细胞，还涉及局部特色和全局特色，因此非常繁芜。
其余，如何将 WSI 的拓扑特色用于生存剖析也还是一个有待办理的问题。

为此，我们提出将 WSI 建模成图，然后开拓了一种图卷积神经网络（Graph CNN），其利用了把稳力机制，可通过供应 WSI 的最优图表征来实现更好的生存剖析。

实验结果表明，这种新方法优于之前的其它方法。

这一部分同时也先容了近年来 GNN 在医疗图像上的其他事情：在 IPMI2019 揭橥的《Graph Convolutional Nets for Tool Presence Detection in Surgical Videos》中，作者提出利用 GCN 来检测手术***中的工具，这是自动手术***内容剖析的核心问题之一，可用于手术器材利用评估和手术报告自动天生等运用。
这个模型利用了 GCN 沿韶光维度通过考虑连续***帧之间的关系来学习更好的特色。

而在 MICCAI 2020 揭橥的论文《Graph Attention Multi-instance Learning for Accurate Colorectal Cancer Staging》中，作者提出利用图把稳力多实例学习来准确判断结直肠癌是处于早期、中期还是晚期。

总结和展望

在这次课程中，我们先容了图神经网络的发展历史、包括图神经网络的表达能力、深度、大规模扩展、自监督 / 无监督学习等方面的研究进展，也简要先容了腾讯 AI Lab 在图神经网络的社交网络和医疗影像运用方面的一些初步成果。

图深度学习领域仍处于发展之中，有很多有趣的问题等待办理，例如逆向图识别（IGI），即我们在图分类问题中，是否可以根据图的标签来推断每个节点的标签？子图识别，即如何在图中找到关键的子图同时还有图与多示例学习问题的结合形成多图示例学习问题，以及在图上进行攻击与防御干系的图深度学习鲁棒性的研究。
末了，层次图也是一个热门的研究方向。
图神经网络必将在人工智能领域未来的研究和运用中扮演更主要的角色。