• 图神经网络
  • 资料
  • 图挖掘
  • 复杂网络
  • Graph 定义
• 图神经网络 GCN
  • 1 什么是图？
  • 2 图神经网络
  • 3 图神经网络历史
  • 图神经网络研究进展
    • 1 图神经网络的表达能力
    • 2 训练深度图神经网络
    • 3 大规模图神经网络
    • 4 图神经网络的自监督 / 无监督学习
  • 三 图神经网络应用进展
    • 1 用于社交网络的 GNN
    • 2 用于医疗影像的 GNN
• 图匹配
  • 什么是子图匹配？
  • 图同构与图匹配的关系
  • 研究现状
    • 2.1 近似约束子图匹配（Approximate Constrained Subgraph Matching）
    • 2.2 使用索引的近似子图匹配（SAGA: Approximate Subgraph Matching using Indexing）
    • 2.3 挖掘相关密集子图（Mining Coherent Dense Subgraphs）
    • 2.4 张量分析（Tensor Analysis）
    • 2.5 图范围（Graph Scope）
    • 2.6 凸松弛的子图匹配（Subgraph Matching via Convex Relaxation）
• 潜图学习
  • DGCNN
  • DGM
  • 流形学习
  • 潜图学习的其它应用
  • 总结
  • 模型
    • GCN 图卷积神经网络
    • ST-GCN 时空图卷积
• 工具
  • networkx
• 结束

图神经网络

资料

• 【2020-9-24】腾讯AI Lab联合清华港中文，解读图深度学习历史、进展应用
  • 将分图神经网络历史、图神经网络的最新研究进展和图神经网络的应用进展三大部分归纳总结该课程 Theme II: Advances and Applications 部分的核心内容。作者包括腾讯荣钰、徐挺洋、黄俊洲，清华大学黄文炳，香港中文大学程鸿
• 【2020-10-16】没有完整图时，如何使用图深度学习？需要了解流形学习2.0版本
• 图卷积神经网络笔记——第一章：从欧式空间到非欧式空间

图挖掘

• 图挖掘技术总结
  • 
• 简述
• 图匹配 ：比较图之间结构相似性的过程
• 近似图匹配
  • 在数据图中搜索出与模式图在数据和节点与边属性上匹配的子图，允许噪声和错误，最大公共子图，最小公共超图来衡量两个图之间的相似程度
  • SUBDUE算法
  • LAW算法
• 图中关键字查询
• 频繁子图挖掘
• 显著性子图挖掘
• 密集子图挖掘
• 图的聚类
  • 图剖分
    • 理论上是NP-hard的，通常研究的都是图的二剖分
  • 凝聚法
    • 寻找社团最中心的边，不断把最相似的两个点聚到一起
    • 凝聚法简单，但是两个点一旦合并就永远在一个社团中无法撤销，对单个点比较敏感
      • 算法一：直接计算相似性
      • 算法二：看两个点合并到一起后模块度变化的情况Newman2004年提出的算法
  • 分裂法
    • 找出最有可能位于社团之间的边，把这些边去掉，就自然产生了不同社团
  • Louvain算法（综合最好算法）
    • 是基于模块度最优化的启发式算法，算法两层迭代，外层的迭代是自下而上的凝聚法，内层的迭代是凝聚法加上交换策略
  • Canopy算法+K-Means
  • 基于密度的快速聚类
    • 找出每个类的中心点，将剩余的点按一定策略分配到每个类中
• 图的分类
• 不确定图的挖掘

复杂网络

• 复杂网络（Complex Network）指具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络。钱学森给出了复杂网络的一个较严格的定义：具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。

Graph 定义

图是复杂网络研究中的一个重要概念。Graph是用点和线来刻画离散事物集合中的每对事物间以某种方式相联系的数学模型。网络作为图的一个重要领域，包含的概念与定义更多，如有向图网络（Directed Graphs and Networks）、无向图网络（Undirected）等概念。

图神经网络 GCN

• 传统深度学习方法在提取欧氏空间数据（比如图片是规则的正方形栅格，语音数据是一维序列）的特征方面取得了巨大的成功。
• 但是，许多任务中，数据不具备规则的空间结构，即非欧氏空间下的数据，如电子交易、推荐系统等抽象出来的图谱，图谱中每个节点与其他节点的连接不是固定的。
• 在经典的 CNN、RNN 等框架无法解决或效果不好的情况下，图神经网络应运而生。
  • 图左（红框）：欧氏空间数据；图右：非欧氏空间数据
  • 

图神经网络利用关系归纳偏置来处理以图形式数据。

• 然而，在许多情况下，并没有现成的图。

那么图深度学习适用于这类情形吗？潜图学习（latent graph learning）和更早的流形学习（manifold learning）

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》中，作者提出使用图注意力多实例学习来准确判断结直肠癌是处于早期、中期还是晚期。

图匹配

什么是子图匹配？

• 给定一个查询图Q和目标图G，我们的任务是从G中匹配到Q或者一个与Q最相似的子图，这就是经典的子图匹配(Subgraph Matching)。

• 子图匹配是一种重要的图搜索技术，一般情况下包含了下面两种任务：

  • 查询图Q是否在目标图G中存在，即回答是或者否即可
  • 从目前图G中搜索一个与查询图最相似的子图，并比较该子图与查询图Q的相似性

图同构与图匹配的关系

• 注意下图同构和图匹配并不是一类问题，他们的区别如下：
  • 图同构(Graph Isomorphism)：只需判断两个图之间是否是同构的，但如果同构的话，并不要求具体找出任何做成同构的对应关系
  • 图匹配(Graph Matching)：判断两个图是否同构，如果同构，找出至少一个使得两者做成同构的节点间的一一对应关系
• 使用networkx算法包，相关的图同构算法代码介绍

研究现状

2.1 近似约束子图匹配（Approximate Constrained Subgraph Matching）

• 论文：Approximate Constrained Subgraph Matching
• 一种可能的方法是为近似图匹配构建声明性框架，其中可以对匹配的设计各种约束。例如，有一组人研究了一种方法，在这种方法中，潜在的近似必须满足一些约束条件，如强制和可选的节点和边。此外，还有一些不被匹配的禁止边。虽然这将导致更明确的搜索，但用户必须拥有关于他想要匹配的模式的详细信息。这种方法的缺点是，很多时候，我们搜索子图时没有任何要找到的模式的先验知识。因此，我们可能没有有效使用这种方法所必需的先验知识。

2.2 使用索引的近似子图匹配（SAGA: Approximate Subgraph Matching using Indexing）

• 论文：SAGA: Approximate Subgraph Matching using Indexing
• 为了应对现有的图匹配方法过于严格的问题，开发了一种名为基于子结构索引的近似图对齐(SAGA)[22]的工具。这种技术考虑到了节点间隙、节点不匹配和图形结构差异，并且不需要预先设计任何约束。总而言之，在数据库中存储关于图的小子结构的索引。查询图被分解成小片段，然后使用匹配算法探测数据库，从而为查询中的子结构生成命中值。缺点是必须维护一个小型结构的数据库，并且它是基于查询的。在生物网络中的图挖掘等应用中，我们可能希望在没有识别查询的情况下提取子图。

2.3 挖掘相关密集子图（Mining Coherent Dense Subgraphs）

• 论文：Mining coherent dense subgraphs across massive biological networks for functional discovery
• 所谓挖掘相干密集子图的方法可能是最适合我们的应用程序的方法。它构造了一个摘要图，其中的边在图集中出现的次数大于k次。然后，它使用一种算法在摘要图中挖掘子图，该算法基于规范化切割将该图递归划分为子图。然而，该算法的局限性是它从所有时间点构造的静态图中找到子图。因此，它无法捕获在局部时间点发生的交互作用。

2.4 张量分析（Tensor Analysis）

• 论文：Beyond Streams and Graphs: Dynamic Tensor Analysis
• 与之前的方法不同，Sun等人在张量的情况下表示了这个问题。张量的第一和第二模态对应图的邻接矩阵，第三模态对应时间。提出了一种张量分解(即矩阵主成分分析的推广)，它可以在张量中找到“簇”(即相同模态内和不同模态间的相关维数)。提出了一种适用于在线设置的增量算法。这项工作似乎与我们寻找循环子图的目标有关。然而，通过张量分解在多个时间点上发现的“簇”是否在实践中等价于重复出现的子图，目前还不完全清楚。一组基因可能在两个时间点t1和t2中高度连接(聚集在一起)，但t1中连接它们的边缘集可能与t2中连接它们的边缘集完全不同。对于生物学中常见的稀疏网络，该方法的表现还有待观察。

2.5 图范围（Graph Scope）

• 论文：GraphScope: Parameter-free Mining of Large Time-evolving Graphs
• GraphScope是另一种随着时间的推移在图中查找相干簇的方法。GraphScope假设图g1，…Gn是二部图。然后使用信息理论准则将这些图划分为段，然后在每个段中找到簇。这是一种有趣的方法，但由于它将序列图划分为段，因此只能在邻近的时间点找到簇，这是一种有限的方法。然而，我们试图找到可能不会在相邻或邻近时间点出现的重复出现子图。

2.6 凸松弛的子图匹配（Subgraph Matching via Convex Relaxation）

• 论文：Probabilistic Subgraph Matching Based on Convex Relaxation
• Schellewald等人提出了一种基于凸松弛的子图匹配方法。在他们的公式中，有一个大的图G L和一个小的图G K，目标是在G L中找到G K(从G K到G L的顶点的对应关系是未知的)。但是，它们也假设存在一个距离函数d(i, j)，其中i是G K中的一个节点，j是G L中的一个节点。利用gk、gl的邻接结构和距离函数d，它们构造一个二次整数程序，然后将其放宽为凸程序。这种方法是数学原则，但有缺点，它是不找到子图在G K匹配那些在G L，而是寻求匹配所有的G K在G L。因此，它不能扩展到寻找一系列图(超过2个)中的重复子图。

潜图学习

• 从数据中推断出图并在其上应用 GNN，并将其称为「潜图学习」
• 潜图学习是学习具有空边集的图。在这一设置中，输入为高维特征空间中的点云。在集合上进行深度学习的方法（如 PointNet）对每个点应用共享可学习 point-wise 函数，与之不同，潜图学习还寻求跨点信息传递。

DGCNN

• 点云动态图卷积神经网络（DGCNN）是麻省理工学院的 Yue Wang 开发的第一个潜图学习架构。受计算机图形学中涉及 3D 点云分析问题的启发，该架构将图用作点云下局部光滑流形结构的粗略表示。Yue 的一个重要发现是，图在整个神经网络中不需要保持不变，事实上，它可以而且应该动态更新——因此该方法被命名为 DGCNN。
• DGCNN 动态构造一个用于特征扩散的 k 近邻图。图依赖于任务，并在每个层之后更新。这幅图（摘自 [4]）展示了与红点的距离（黄色代表更近的点），表明在分割任务中，更深层次的图捕捉语义关系而不是几何关系，如成对的机翼、发动机等。
• 

DGM

• DGCNN 的一个局限性是用相同的空间来构造图和图上的特征。Anees Kazi 和 Luca Cosmo 提出了一种新的架构——可微图模块（DGM），通过对图和特征构造进行解耦来扩展 DGCNN
• DGM 提供了一种基于输入数据构造图并在图上扩散特征的机制。
• 
• 当应用于医学领域问题时，DGM 显示出优秀的结果，例如根据脑成像数据预测疾病。在这些任务中，研究者获取到多个患者的电子健康记录，包括人口统计学特征（如年龄、性别等）和大脑成像特征，并尝试预测患者是否患有神经系统疾病。之前的工作展示了 GNN 在这类任务中的应用，方法是在一个根据人口统计学特征手工构建的「病人图」上进行特征扩散。而 DGM 提供了学习图的优势，可以传达某些特征在特定诊断任务中是如何相互依赖的。其次，DGM 在点云分类任务中也击败了 DGCNN，不过优势很小。

流形学习

• DGCNN 和 DGM 在概念上与流形学习或非线性降维算法相似，流形学习很早就已出现并流行，且目前仍用于数据可视化。流形学习方法的基本假设是数据具有内在的低维结构。虽然数据可以在数百甚至数千维的空间中表示，但它却只有几个自由度
• 

• 虽然这个数据集中的手部图像是高维的（64x64 像素构成 4096 个维度），但它们本质上是低维的，可以用两个自由度来解释：手腕旋转和手指伸展。流形学习算法能够捕捉数据集的这种内在低维结构，并将其在欧几里德空间中进行表示

• 再比如球面上的一点（即三维欧式空间上的点），可以用三元组来表示其坐标：
  • 
• 但事实上这个三维坐标只有两个变量 θ 和 φ，也可以说它的自由度为 2，正好对应了它是一个二维的流形。
• 流形学习的目的是捕捉这些自由度，并将数据的维数降至其固有维数。流形学习与 PCA 等线性降维方法的重要区别在于，由于数据的非欧几里德结构，我们可能无法通过线性投影恢复流形。如下图所示，线性降维（左）为线性降维，流形学习（右）为非线性降维。
  • 
• 流形学习算法在恢复「流形」方法上各不相同，但它们有一个共同的蓝图。
  • 首先，创建一个数据表示，通过构造一个 k 近邻图来获取其局部结构。
  • 其次，计算数据的低维表示（嵌入），并试图保留原始数据的结构。
    • 这是大多数流形学习方法的区别所在。这种新的表示将原来的非欧几里德结构「展平」成一个更容易处理的欧几里德空间。
  • 第三，一旦计算出表示，就会对其应用机器学习算法（通常是聚类）。
  • 
• 多种流形学习方法的蓝图：
  • 首先，将数据表示为图；
  • 其次，计算该图的低维嵌入；
  • 第三，将 ML 算法应用于这种低维表示。
• 这其中面临的一项挑战是图构建与 ML 算法的分离，有时需要精确的参数调整（例如邻域数或邻域半径），以确定如何构建图才能使下游任务正常运行。
• 流形学习算法更严重的缺点或许是：数据很少表示为低维的原始形式。例如，在处理图像时，必须使用各种人工制定的特征提取技术作为预处理步骤。
• 图深度学习提供了一种现代方法，即用单个图神经网络代替上文提到的三个阶段。例如，在 DGCNN 或 DGM 中，图的构造和学习是同一架构的一部分：
  • 
• 潜图学习可以看作是流形学习问题的一种现代设置，在这里，图被学习并用作某些下游任务优化的端到端 GNN pipeline 的一部分。
• 这种方法的吸引力在于：将单个数据点和它们所在的空间结合在相同的 pipeline 中。在图像的例子中，我们可以使用传统的 CNN 从每个图像中提取视觉特征，并使用 GNN 来建模它们之间的关系。
  • 
• PeerNet 是标准 CNN 中基于图的正则化层，可聚合来自多个图像的相似像素，从而降低对对抗性扰动的敏感性。（图源 [12]）

潜图学习的其它应用

• 潜图学习还有许多其他有趣的应用。
  • 第一是少样本学习：利用基于图的方法从少量样本中进行归纳（重点：只需要少量带有标注的样本）。在计算机视觉中，数据标注量从几千到上万不等，成本很高，因此少样本学习变得越来越重要。
  • 第二是生物学领域：人们经常通过实验观察生物分子如蛋白质的表达水平，并试图重建它们的相互作用和信号网络。
  • 第三是对物理系统的分析：其中图可以描述多个对象之间的交互作用。尤其是处理复杂粒子相互作用的物理学家，最近对基于图的方法表现出了浓厚的兴趣。
  • 第四是 NLP 问题：在 NLP 领域中，图神经网络可以看作是 transformer 架构的泛化。所提到的许多问题也提出了在图结构中加入先验知识，这一结构在很大程度上仍然是开放的：例如，人们可能希望强迫图遵守某些构造规则或与某些统计模型兼容。
• 潜图学习，虽然不是全新的领域，但它为旧问题提供了新的视角。对于图机器学习问题而言，这无疑是一个有趣的设置，为 GNN 研究人员提供了新的方向。

总结

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

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

模型

GCN 图卷积神经网络

待定

ST-GCN 时空图卷积

详见站内专题: 目标检测-ST-GCN

工具

networkx

networkx工具包

• 复杂网络与NetworkX
• networkx在2002年5月产生，是一个用Python语言开发的图论与复杂网络建模工具，内置了常用的图与复杂网络分析算法，复杂网络数据分析、仿真建模等工作。
• 

• networkx支持创建简单无向图、有向图和多重图；内置许多标准的图论算法，节点可为任意数据；支持任意的边值维度，功能丰富，简单易用。利用networkx可以以标准化和非标准化的数据格式存储网络、生成多种随机网络和经典网络、分析网络结构、建立网络模型、设计新的网络算法、进行网络绘制等。

• Graph 结构
  • 根据Graph的定义，一个Graph包含一个节点集合和一个边集。将图表示为可以在计算机中处理的形式常见表示方式：①邻接矩阵②邻接表③三元组
• Graph分类
  • Graph：指无向图（undirected Graph），即忽略了两节点间边的方向。
  • DiGraph：指有向图（directed Graph），即考虑了边的有向性。
  • MultiGraph：指多重无向图，即两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联。
  • MultiDiGraph：多重图的有向版本。

结束