Question

1. 最近神经网络的成功推动了模式识别和数据挖掘的发展。很多机器学习任务，如目标检测、机器翻译、语音识别任务，它们曾经高度依赖于手工特征工程 handcrafted feature engineering 来抽取特征，但是这些任务最近被各种端到端的深度学习范式所变革，如卷积神经网络CNN、递归神经网络 RNN、自编码器 autoencoder 。

   深度学习在许多领域的成功部分归因于快速发展的计算资源（如 GPU）、大量可用的训练数据、以及深度学习从欧几里得数据（如图像、文本、视频）中抽取潜在 representation 的有效性。以图像数据为例，我们可以将图像表示为欧几里得空间中的规则网格，而卷积神经网络CNN 能够利用图像数据的平移不变性shift-invariance 、局部连通性local connectivity 、以及组合性 compositionality 。结果，CNN 可以抽取在整个数据集上共享的、局部的、有意义的特征，从而进行各种图像分析。

   虽然深度学习有效地捕获了欧几里得数据的隐藏模式，但是越来越多的应用application 以图graph 的形式表示数据。例如：电商领域中基于图的学习系统可以利用用户和商品之间的交互来提高推荐准确性；化学领域中分子被建模为图，并需要确定其生物活性以进行药物发现。图数据的复杂性对现有的机器学习算法提出了重大挑战：

   • 由于图可能是不规则的，因此图可能包含可变数量的无序节点。而且，图中的节点可能具有不同数量的邻居，从而导致一些在图像领域很容易实施的重要的操作（如卷积）很难应用于图领域。
   • 此外，现有机器学习算法的核心假设是样本彼此独立。该假设在图数据上不再成立，因为图数据中每个节点通过各种类型的链接（如引用、好友、交互）和其它节点相关联。

   最近越来越多的人关注将深度学习方法扩展到图数据上。受深度学习的 CNN、RNN、autoencoder 等技术的推动，过去几年中一些关键算子的新的推广、新的定义快速发展，从而能够处理图数据的复杂性。例如，可以从 2D 卷积中推广出图卷积。如下图所述，可以将图像视为特殊的、相邻像素连接的图。和 2D 卷积类似，可以通过获取节点邻域信息的加权均值来执行图卷积。

   • 图 (a)：一个 2D 卷积。图像中每个像素视为一个节点，其中邻域由卷积核确定。2D 卷积采用红色节点及其邻域像素的像素值的加权平均，节点的邻域是有序的、固定大小的。

     加权平均的权重由卷积核来指定。

   • 图(b)：一个图卷积。为获得红色节点的 hidden representation，一种简单的图卷积运算是获取红色节点及其相邻节点的 representation 均值。和图像数据不同，节点的邻域是无序的、大小可变的。

   

   目前有关图神经网络 GNN 的 review 的数量有限，论文 《A Comprehensive Survey on Graph Neural Networks》 给出了一份 GNN 的全面综述。具体而言：

   • 作者提出了新的分类方法，将图神经网络划分为四类：递归图神经网络recurrent graph neural network:RecGNN、卷积图神经网络convolutional graph neural network:ConvGNN、图自编码器 graph autoencoder:GAE、时空图神经网络spatial-temporal graph neural network:STGNN 。

     对于每种类型的图神经网络，作者提供有关代表性模型的详细说明、必要的比较、并总结相应的算法。

   • 作者收集了大量资源，包括 SOTA模型、benchmark 数据集、开源代码、实际应用。作者指出：该综述可以用于了解、使用、开发各种现实应用的不同的图深度学习方法的指南 hands-on guide 。

   • 最后作者探讨了图神经网络的理论方面，分析了现有方法的局限性，并就模型深度model depth 、可扩展性scalability 、异构性heterogeneity 、动态性dynamicity 提出了四个未来可能的研究方向。

3.1 背景

1. GNN 的历史：《Supervised neural networks for the classification of structures》 首次将神经网络应用于有向无环图，这激励了早期对 GNN 的研究。《A new model for learning in graph domains》 最初概述了图神经网络的概念，《The graph neural network model》 进一步阐述了这个概念。这些早期的研究属于递归图神经网络（recurrent graph neural network: RecGNN）的范畴。它们通过以迭代的方式传播邻居信息来学习目标节点的 representation，直到达到一个稳定的不动点。这个过程的计算成本很高，最近有越来越多的人在努力克服这些挑战。

   在计算机视觉领域 CNN 成功的鼓舞下，大量为图数据重新定义卷积概念的方法被提出。这些方法都属于卷积图神经网络（convolutional graph neural network: ConvGNN）的范畴。卷积图神经网络分为两个主要方向，即基于谱域的方法和基于空间域的方法。

   • 第一个关于基于谱域的卷积图神经网络的突出研究是由 《Spectral networks and locally connected networks on graphs》 提出的，他们开发了一个基于谱图理论的图卷积。此后，对基于谱域的卷积图神经网络的改进、扩展越来越多。
   • 基于空间域的卷积图神经网络的研究比基于谱域开始得更早。《Neural network for graphs: A contextual constructive approach》 首次通过架构上来组合非递归层来解决图的相互依赖性，同时继承了递归图神经网络的消息传递思想。然而，这项工作的重要性被忽略了。

   除了递归图神经网络和卷积图神经网络，过去几年中还开发了许多其他的 GNN，包括图自编码器和 "空间-时间"图神经网络。这些学习框架可以建立在递归图神经网络、卷积图神经网络或其他用于图建模的神经架构上。

2. GNN vs graph embedding：GNN 和 graph embedding 密切相关。

   • graph embedding 目的是将网络节点表示为低维embedding 向量，同时保持网络拓扑结构和节点内容信息，以便可以使用简单的、已有的机器学习方法（如支持向量机）轻松执行任何后续的图分析任务（如节点分类、节点聚类、推荐）。

   • GNN 是深度学习模型，旨在以端到端的方式解决图相关的任务。很多 GNN 显式地提取 high-level representation 。

   • GNN 和 graph embedding 主要区别在于：

     • GNN 是一组为各种任务而设计的神经网络模型，而 graph embedding 覆盖了同一个任务的各种不同方法。因此，GNN 可以通过图自编码器框架解决 graph embedding 问题。
     • 另一方面，graph embedding 也包含其它非深度学习方法，如矩阵分解 MF、随机游走。

3. GNN vs graph kernel：Graph Kernel 曾经是历史上解决图分类问题的主流技术。这些方法设计核函数 kernel function 来度量graph pair-wise 之间的相似度，使得 kernel-based 算法（如支持向量机）可用于图上的监督学习。

   • 和 GNN 相似，Graph Kernel 可以通过映射函数将图或节点嵌入到向量空间。不同之处在于：Graph Kernel 的这个映射函数是确定性的，而不是通过学习得到。
   • 由于 pair-wise 相似性的计算，Graph Kernel 方法遇到了计算瓶颈。
   • GNN 基于抽取的 graph representation 直接执行图分类，因此比 Graph Kernel 方法更有效。

3.2 GNN 分类

1. 定义图$\mathcal{G}=(\mathcal{V},\mathcal{E})$$ \mathcal G=(\mathcal V, \mathcal E) $ ，其中$\mathcal{V}=\{v_1,\cdots ,v_n\}$$ \mathcal V=\{v_1,\cdots,v_n\} $ 为节点集合，$\mathcal{E}=\{e_{i,j}\}$$ \mathcal E=\{e_{i,j}\} $ 为边集合。

   • 边$e_{i,j}=(v_i,v_j)\in \mathcal{E}$$ e_{i,j}=(v_i,v_j)\in \mathcal E $ 表示一条从$v_j$$ v_j $ 指向$v_i$$ v_i $ 的边。
   • 节点$v$$ v $ 的邻域定义为${\mathcal{N}}_v=\{u\in \mathcal{V}\mid (v,u)\in \mathcal{E}\}$$ \mathcal N_v = \{u\in \mathcal V\mid (v,u)\in \mathcal E\} $ 。
   • 邻接矩阵$\mathbf{A}\in {\mathbb{R}}^{n\times n}$$ \mathbf A\in \mathbb R^{n\times n} $ 定义为：如果$e_{i,j}\in \mathcal{E}$$ e_{i,j}\in \mathcal E $ 则$A_{i,j}=1$$ A_{i,j}=1 $ ，否则$A_{i,j}=0$$ A_{i,j} = 0 $ 。
   • 每个节点$v\in \mathcal{V}$$ v\in \mathcal V $ 关联一个节点属性${\overrightarrow{\mathbf{x}}}_v\in {\mathbb{R}}^d$$ \mathbf{\vec x}_v\in \mathbb R^{d} $ ，其中$d$$ d $ 为属性维度。所有节点的属性构成节点属性矩阵$\mathbf{X}\in {\mathbb{R}}^{n\times d}$$ \mathbf X \in \mathbb R^{n\times d} $ ，其中第$v$$ v $ 行对应于节点$v$$ v $ 的属性${\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec x}_v $ 。
   • 每条边$e=(v,u)\in \mathcal{E}$$ e=(v,u)\in \mathcal E $ 关联一个边属性${\overrightarrow{\mathbf{x}}}_{v,u}^e\in {\mathbb{R}}^c$$ \mathbf{\vec x}^e_{v,u} \in \mathbb R^c $ ，其中$c$$ c $ 为属性维度。所有边的属性构成边属性矩阵${\mathbf{X}}^e\in {\mathbb{R}}^{m\times c}$$ \mathbf X^e\in \mathbb R^{m\times c} $ ，其中$m$$ m $ 为边的数量，第$e$$ e $ 行对应于边$e=(v,u)$$ e=(v,u) $ 的属性${\overrightarrow{\mathbf{x}}}_{v,u}^e$$ \mathbf{\vec x}^e_{v,u} $ 。

2. 定义有向图是所有边都是有向边的图，其中有向边指的是每条边都从一个节点指向另一个节点。

   • 无向图是有向图的特殊情况，其中每条有向边都存在与之相反方向的另一条边。
   • 当且仅当邻接矩阵是对称矩阵时，图才是无向图。

3. 定义时空图spatial-temporal graph 为一个属性图，其中节点属性随时间动态变化，记作${\mathcal{G}}^{(t)}=(\mathcal{V},\mathcal{E},{\mathbf{X}}^{(t)})$$ \mathcal G^{(t)}=\left(\mathcal V, \mathcal E, \mathbf X ^{(t)}\right) $ ，其中${\mathbf{X}}^{(t)}\in {\mathbb{R}}^{n\times d}$$ \mathbf X^{(t)}\in \mathbb R^{n\times d} $ 。

4. 我们将图神经网络 GNN 分类为：循环图神经网络 RecGNN、卷积图神经网络ConvGNN、图自编码器 GAE、时空图神经网络STGNN，如下表所述。

   

   下表给出了各种模型架构的一些示例。

   • 具有多个图卷积层graph convolutional layer 的 ConvGNN。图卷积层通过聚合来自邻域的特征信息，从而得到每个节点的 hidden representation，并在特征聚合之后再应用非线性变换。通过堆叠多个图卷积层，每个节点的最终 hidden representation 将接收来自更远邻域的消息。

     

   • 具有池化层和 readout 层的、用于图分类的 ConvGNN 。图卷积层之后是池化层，从而将图粗化 coarsen 为子图，以便粗化图上的节点representation 能够表达更高的 graph-level representation 。readout 层通过获取粗化图所有节点的 hidden representation 均值或sum 结果，从而得到最终的 graph representation 。

     

   • 用于graph embedding 的 GAE。编码器使用图卷积层获取每个节点的 graph embedding，解码器根据graph embedding 计算节点的 pairwise 距离。在应用非线性激活函数之后，解码器重构图邻接矩阵。通过最小化实际的图邻接矩阵、重构的图邻接矩阵之间的差异来训练网络。

     

   • 用于时空图预测的 STGNN。图卷积层后面是1D-CNN 层：图卷积层在$\mathbf{A}$$ \mathbf A $ 和${\mathbf{X}}^{(t)}$$ \mathbf X^{(t)} $ 上操作从而捕获空间相关性；而 1D-CNN 沿时间轴在$\mathbf{X}$$ \mathbf X $ 上滑动以捕获时间相关性。输出是一个线性变换，可以为每个节点生成预测，如下一个time step 的、未来的取值。

     

5. 循环图神经网络 RecGNN：大多数是图神经网络的早期作品。RecGNN 目的是通过递归神经网络体系架构学习节点的 representation。他们假设图中的节点不断与其邻居交换消息，直到到达稳定的平衡。

   RecGNN 在概念上很重要，并激发了后续对卷积图神经网络的研究。具体而言，RecGNN 消息传递的思想被基于空间的卷积图神经网络所继承。

6. 卷积图神经网络ConvGNN：推广了从网格数据到图数据的卷积运算。主要思想是通过聚合节点自身的特征${\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec x}_v $ 和邻居特征${\overrightarrow{\mathbf{x}}}_u,u\in {\mathcal{N}}_v$$ \mathbf{\vec x}_u, u\in \mathcal N_v $ 来生成节点$v$$ v $ 的representation 。和 RecGNN 不同，ConvGNN 堆叠多个图卷积层从而获得high-level 节点 representation 。

   ConvGNN 在搭建很多其它更复杂的 GNN 模型中起着核心作用。

7. 图自编码器 GAE：是一种无监督的学习框架，可以将节点/图编码到潜在的 embedding 空间，并根据编码后的信息重建图数据。

   GAE 用于学习 graph embedding 以及图生成分布 graph generative distribution 。

   • 对于 graph embedding任务，GAE 通过重构图结构信息（如图的邻接矩阵）来学习潜在的节点 representation。
   • 对于图生成任务，一些方法逐步生成图的节点和边，而另一些方法则一次性生成整个图。

8. 时空图神经网络STGNN：旨在从时空图学习隐藏的模式 hidden pattern ，这在各种应用中变得越来越重要，例如：交通速度预测 traffic speed forecasting 、驾驶员操纵预测、人类动作识别等。

   STGNN 的关键思想是同时考虑空间依赖性spatial dependency和时间依赖性temporal dependency 。当前的许多方法将图卷积和 RNN/CNN 集称在一起，其中图卷积捕获空间依赖性，RNN/CNN 捕获时间依赖性。

9. GNN 的输入为图结构和节点内容信息，但是 GNN 的输出依赖于具体的图分析任务：

   • node-level 输出：和节点回归、节点分类任务有关。

     RecGNN 和 ConvGNN 可以通过消息传播/图卷积抽取high-level 节点representation，然后使用多层感知机 multi-perceptron:MLP 或者 softmax 层作为输出层。最终 GNN 能够以端到端的方式执行 node-level 任务。

   • edge-level 输出：和edge 分类、链接预测任务有关。

     使用来自 GNN 的两个节点的 hidden representation 作为输入，然后利用相似度函数或神经网络来预测边的标签或链接强度。

   • graph-level 输出：和图分类任务有关。

     为获得 graph-level 的紧凑表示compact representation，GNN 通常与池化操作、readout 操作配合使用。

10. 训练框架：可以在端到端学习框架内以监督学习、半监督学习甚至完全无监督学习的方式训练一些 GNN 模型（如 ConvGNN），具体取决于学习任务和可用的标签信息。

    • 用于 node-level分类的半监督学习：给定一个graph 其中部分节点带类别标记、剩余节点没有类别标记，ConvGNN 可以学习一个 robust 模型，该模型可以有效地识别未标记节点的类别信息 。为此，可以堆叠几个图卷积层，然后跟一个 softmax layer 从而构建端到端的多类别分类框架。

    • 用于 graph-level 分类的监督学习：目的是预测整个图的类标签。可以通过图卷积层、图池化层、和/或 readout layer 的组合来完成端到端的图分类任务。

      • 图卷积层负责获取准确的 high-level 节点 representation。
      • 图池化层充当降采样的角色，从而每次都将图粗化 coarsen 为子结构 sub-structure 。
      • readout layer 将图的所有节点压缩为一个 graph representation 。

      通过将一个多层感知机 MLP 以及一个 softmax layer 应用于 graph representation，我们可以构建用于图分类的端到端框架。

    • 用于 graph embedding 的无监督学习：当图没有可用的类标签时，我们可以在端到端框架中以纯无监督的方式学习 graph embedding 。

      这些算法以两种方式利用 edge-level 信息：

      • 一种简单的方法是采用自编码器框架，其中编码器使用图卷积层将 graph 嵌入到潜在 representation 空间中，然后对潜在 representation 应用解码器来重构图结构。
      • 另一种流行的方法是利用负采样方法，该方法采样一部分节点 pair 对为负边 negative edge，而图中具有链接的节点 pair 对为正边 postive edge。然后应用逻辑回归层 regression layer 来区分正边和负边。

11. 我们在下表中总结了一些典型 RecGNN 和 ConvGNN 的主要特点，并在各种模型之间比较了输入源、池化层、readout layer、以及时间复杂度。更具体而言，我们仅比较每个模型中消息传递/图卷积操作的时间复杂度。

    • 由于 《Spectral networks and locally connected networks on graphs》 和 《Deep convolutional networks on graph-structured data》 中的方法需要特征值分解 eigenvalue decomposition，因此其时间复杂度为$O(n^3)$$ O(n^3) $ 。

    • 由于需要计算节点 pair 对的最短路径，因此 《On filter size in graph convolutional networks》 的时间复杂度也是$O(n^3)$$ O(n^3) $ 。

    • 其它方法的时间复杂度几乎差不多：如果图的邻接矩阵是稀疏的，则时间复杂度为$O(m)$$ O(m) $ ；否则时间复杂度为$O(n^2)$$ O(n^2) $ 。

      这是因为这些方法中，计算每个节点$v_i$$ v_i $ 的 representation 都涉及其$d_i$$ d_i $ 个邻居（$d_i$$ d_i $ 为节点$v_i$$ v_i $ 的 degree ），并且所有节点上$d_i$$ d_i $ 的总和刚好等于边的数量。

    • 表中缺少几种方法的时间复杂度，这是因为：这些方法在原始论文中缺乏时间复杂度分析，或者仅报告其总体模型或算法的时间复杂度。

    • 池化层和 readout layer 中的缺失值 - 表示该方法仅在 node-level/edge-level 任务上进行实验。

    

3.3 RecGNN

1. RecGNN 大多数是 GNN 的早期研究，它在图上的节点反复应用相同的函数，从而抽取high-level 节点 representation。受算力的限制，早期研究主要集中于有向无环图上。

2. 论文 《The graph neural network model》首次提出了图神经网络 GNN，它扩展了已有的递归模型recurrent model 从而处理图数据，如带环图、无环图、有向图、无向图等。为区分通用的术语图神经网络，这里我们将论文中的模型记作 GNN* 。

   GNN* 基于消息传播机制，通过反复交换邻域信息来更新节点的状态，直到达到稳定的平衡状态为止。节点的 hidden state 反复被更新，更新方程为：

   $${\overrightarrow{\mathbf{h}}}_v^{(t)}=\sum _{u\in {\mathcal{N}}_v}f({\overrightarrow{\mathbf{x}}}_v,{\overrightarrow{\mathbf{e}}}_{v,u},{\overrightarrow{\mathbf{x}}}_u,{\overrightarrow{\mathbf{h}}}_u^{(t-1)})$$

   其中$f(\cdot )$$ f(\cdot) $ 是一个可学习的函数，${\overrightarrow{\mathbf{h}}}_v^{(0)}$$ \mathbf{\vec h}_v^{(0)} $ 为随机初始化的hidden state 。

   • 求和运算使得 GNN* 适用于所有类型的节点，即使邻居的数量不同并且不知道邻居节点的顺序。
   • 为了确保收敛，递归函数$f(\cdot )$$ f(\cdot) $ 必须是收缩映射，即两个节点经过$f(\cdot )$$ f(\cdot) $ 之后它们在潜在空间中的距离缩小（相比于原始空间中特征向量之间的距离）。如果$f(\cdot )$$ f(\cdot) $ 是神经网络，则必须对参数的雅可比矩阵施加惩罚。
   • GNN* 交替执行节点状态传播、参数梯度计算，从而最小化训练目标。这种策略使得 GNN* 可以处理有环图。

3. 在后续的工作中，Graph Echo State Network:GraphESN 扩展了 echo state network 来提升 GNN* 的训练效率。

   GraphESN 由编码器和输出层组成。其中，$f(\cdot )$$ f(\cdot) $ 作为编码器是随机初始化且无需训练，它实现了收缩映射从而递归更新节点状态直到收敛。然后通过将 fixed node state 作为输入来训练输出层。

4. Gated Graph Neural Network:GGNN 采用GRU 作为递归函数$f(\cdot )$$ f(\cdot) $ ，并且将递归次数降低到固定的step 数量。其优点是：它不再需要约束参数从而确保$f(\cdot )$$ f(\cdot) $ 收敛。节点 hidden state 根据它之前的 hidden state 以及邻居的 hidden state 来更新：

   $${\overrightarrow{\mathbf{h}}}_v^{(t)}=\text{GRU}({\overrightarrow{\mathbf{h}}}_v^{(t-1)},\sum _{u\in {\mathcal{N}}_v}\mathbf{W}{\overrightarrow{\mathbf{h}}}_u^{(t-1)})$$

   其中${\overrightarrow{\mathbf{h}}}_v^{(0)}={\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec h}_v^{(0)} = \mathbf{\vec x}_v $ 。

   与 GNN*、GraphESN 不同，GGNN 使用时间反向传播 back-propagation through time:BPTT 算法来学习模型参数。这对于大型图可能会出现问题，因为 GGNN 需要在所有节点上多次运行递归函数，并要求将所有节点的中间状态存储在内存中。

5. Stochastic Steady-state Embedding:SSE 提出了一种学习算法，该算法对大型图更具有可扩展性 scalable。

   SSE 以随机的、异步的方式递归地更新节点 hidden state。它交替采样一个 batch 的节点用于状态更新、采样一个 batch 的节点用于梯度计算。为了保持稳定性，SSE 递归函数定义为历史状态和最新状态的加权平均，更新方程为：

   $${\overrightarrow{\mathbf{h}}}_v^{(t)}=(1-\alpha ){\overrightarrow{\mathbf{h}}}_v^{(t-1)}+\alpha {\mathbf{W}}_1\sigma \left({\mathbf{W}}_2[{\overrightarrow{\mathbf{x}}}_v,\sum _{u\in {\mathcal{N}}_v}[{\overrightarrow{\mathbf{h}}}_u^{(t-1)},{\overrightarrow{\mathbf{x}}}_u]]\right)$$

   其中：

   • $\alpha$$ \alpha $ 为超参数。
   • ${\overrightarrow{\mathbf{h}}}_v^{(0)}$$ \mathbf{\vec h}_v^{(0)} $ 为节点$v$$ v $ 的初始状态，它随机初始化。
   • $\sigma (\cdot )$$ \sigma(\cdot) $ 为非线性激活函数，$[\cdot ,\cdot ]$$ [\cdot,\cdot] $ 为向量拼接。
   • ${\mathbf{W}}_1,{\mathbf{W}}_2$$ \mathbf W_1, \mathbf W_2 $ 为模型参数。

   尽管从概念上讲很重要，但是 SSE 并未在理论上证明：通过反复应用上述公式节点状态会逐渐收敛到不动点fixed point 。

3.4 ConvGNN

1. 图卷积神经网络 ConvGNN 和递归图神经网络密切相关。ConvGNN 不是使用收缩约束的映射来迭代节点状态，而是使用固定数量的layer ，其中每层具有不同的权重。下图说明了这一主要区别：

   • 图 (a)：RecGNN 使用相同的 graph recurrent layer:Grec 来更新节点 representation。
   • 图 (b)：ConvGNN 使用不同的 graph convolutional layer:GConv 来更新节点 representation。

   

2. 由于图卷积更有效、更方便与其它神经网络进行组合，因此近年来 ConvGNN 的普及非常迅速。ConvGNN 可以分为两类：基于谱域spectral-based、基于空域 spatial-based。

   • 基于谱域的方法通过从图信号处理的角度引入滤波器来定义图卷积，其中图卷积运算被解释为从图信号中去除噪声。
   • 基于空域的方法继承了 RecGNN 的思想，它通过消息传播来定义图卷积。

   自从 GCN 弥合了基于谱域方法和基于空域方法之间的 gap ，基于空域的方法由于其卓越的效率efficiency 、灵活性flexibility 、通用性generality 而得到迅速发展。

3.4.1 基于谱域的 ConvGNN

1. 基于谱域的ConvGNN 在图信号处理中具有扎实的数学基础。他们认为图是无向的，归一化的图拉普拉斯矩阵是无向图的数学表述，定义为$\mathbf{L}=\mathbf{I}-{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}$$ \mathbf L = \mathbf I - \mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2} $ ，其中 ：

   • $\mathbf{A}$$ \mathbf A $ 为图的邻接矩阵。
   • $\mathbf{D}=\text{diag}(D_1,\cdots ,D_n),D_i=\sum _j{A}_{i,j}$$ \mathbf D=\text{diag}(D_1,\cdots,D_n),D_i=\sum_{j}A_{i,j} $ 为节点的degree 矩阵（一个对角矩阵）。

   归一化的图拉普拉斯矩阵是实对称的、半正定的矩阵，因此可以对其进行特征值分解：

   $$\mathbf{L}=\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^{\mathrm{\top }}$$

   其中：

   • $\mathbf{\Lambda }=\text{diag}({\lambda }_1,\cdots ,{\lambda }_n)$$ \mathbf\Lambda = \text{diag}(\lambda_1,\cdots,\lambda_n) $ 为$n$$ n $ 个特征值，其中${\lambda }_1\le {\lambda }_2\cdots \le {\lambda }_n$$ \lambda_1\le\lambda_2\cdots\le\lambda_n $ 。

   • $\mathbf{U}=[{\overrightarrow{\mathbf{u}}}_1,\cdots ,{\overrightarrow{\mathbf{u}}}_n]\in {\mathbb{R}}^{n\times n}$$ \mathbf U =\left[\mathbf{\vec u}_1,\cdots,\mathbf{\vec u}_n\right]\in \mathbb R^{n\times n} $ 为特征向量eigenvector 组成的矩阵，其中${\overrightarrow{\mathbf{u}}}_i$$ \mathbf{\vec u}_i $ 为特征值${\lambda }_i$$ \lambda_i $ 对应的特征向量。

     $\{{\overrightarrow{\mathbf{u}}}_1,\cdots ,{\overrightarrow{\mathbf{u}}}_n\}$$ \left\{\mathbf{\vec u}_1,\cdots, \mathbf{\vec u}_n\right\} $ 构成了一个线性空间的正交基，数学语言描述为${\mathbf{U}}^{\mathrm{\top }}\mathbf{U}=\mathbf{I}$$ \mathbf U^\top\mathbf U = \mathbf I $ 。

   在图信号处理领域，一个图信号$\overrightarrow{\mathbf{x}}=(x_1,\cdots ,x_n{)}^{\mathrm{\top }}\in {\mathbb{R}}^n$$ \mathbf{\vec x}=(x_1,\cdots,x_n)^\top\in \mathbb R^n $ 是关于所有节点的特征向量 feature vector ，其中$x_i\in \mathbb{R}$$ x_i\in \mathbb R $ 表示在节点$v_i$$ v_i $ 上的取值（一个标量）。针对图信号$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 的图傅里叶变换定义为：

   $$\widehat{\overrightarrow{\mathbf{x}}}=\mathcal{F}\left(\overrightarrow{\mathbf{x}}\right)={\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}$$

   对应的图傅里叶逆变换为：

   $$\overrightarrow{\mathbf{x}}={\mathcal{F}}^{-1}\left(\widehat{\overrightarrow{\mathbf{x}}}\right)=\mathbf{U}\widehat{\overrightarrow{\mathbf{x}}}$$

   图傅里叶变换将输入的图信号投影到正交空间，正交基是由归一化的图拉普拉斯矩阵的特征向量构成。图傅里叶变换后的信号$\widehat{\overrightarrow{\mathbf{x}}}$$ \hat{\mathbf{\vec x}} $ 的元素是新空间中图信号的坐标，因此输入图信号可以表示为：

   $$\overrightarrow{\mathbf{x}}=\sum _i{\hat{x}}_i{\overrightarrow{\mathbf{u}}}_i$$

   这刚好就是图傅里叶逆变换。

   因此对输入信号$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 使用滤波器${\overrightarrow{\mathbf{g}}}_{\theta }\in {\mathbb{R}}^n$$ \mathbf{\vec g}_\theta\in \mathbb R^n $ 的图卷积定义为：

   $$\overrightarrow{\mathbf{x}}{\ast }_{\mathcal{G}}{\overrightarrow{\mathbf{g}}}_{\theta }={\mathcal{F}}^{-1}(\mathcal{F}(\overrightarrow{\mathbf{x}})\odot \mathcal{F}({\overrightarrow{\mathbf{g}}}_{\theta }))=\mathbf{U}({\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}\odot {\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{g}}}_{\theta })$$

   其中$\odot$$ \odot $ 表示逐元素的乘积，$\theta$$ \theta $ 为卷积核参数。

   如果我们定义一个滤波器为：${\mathbf{K}}_{\theta }=\text{diag}\left({\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{g}}}_{\theta }\right)\in {\mathbb{R}}^{n\times n}$$ \mathbf K_\theta = \text{diag}\left(\mathbf U^\top \mathbf{\vec g}_\theta\right)\in \mathbb R^{n\times n} $ （即向量${\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{g}}}_{\theta }$$ \mathbf U^\top \mathbf{\vec g}_\theta $ 的元素组成对角矩阵），则谱域图卷积定义为：

   $$\overrightarrow{\mathbf{x}}{\ast }_{\mathcal{G}}{\overrightarrow{\mathbf{g}}}_{\theta }=\mathbf{U}{\mathbf{K}}_{\theta }{\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}$$

   所有的谱域卷积都遵从这个公式，但是不同的方法选择不同的滤波器${\mathbf{K}}_{\theta }$$ \mathbf K_\theta $ 。

2. Spectral Convolutional Neural Network:Spectral CNN 假设图信号是多通道的，通道$i$$ i $ 的输入记作${\mathbf{H}}_{:i}\in {\mathbb{R}}^n$$ \mathbf H_{:i}\in \mathbb R^{n} $ 。

   假设网络有多层，其中第$l$$ l $ 层的输入记作${\mathbf{H}}^{(l-1)}\in {\mathbb{R}}^{n\times d_l}$$ \mathbf H^{(l-1)}\in \mathbb R^{n\times d_l} $ （即$d_l$$ d_l $ 个通道）。Spectral CNN 对于每个通道采用多个卷积层来生成多通道输出。对于第$l$$ l $ 层第$j$$ j $ 个输出通道定义为：

   $${\mathbf{H}}_{:,j}^{(l)}=\sigma \left(\sum _{i=1}^{d_{l-1}}\mathbf{U}{\mathbf{\Theta }}_{i,j}^{(l)}{\mathbf{U}}^{\mathrm{\top }}{\mathbf{H}}_{:,i}^{(l-1)}\right),j=1,2,\cdots ,d_l$$

   其中：

   • ${\mathbf{\Theta }}_{i,j}^{(l)}\in {\mathbb{R}}^{n\times n}$$ \mathbf\Theta_{i,j}^{(l)}\in \mathbb R^{n\times n} $ 为第$l$$ l $ 层对应于输入通道$i$$ i $ 、输出通道$j$$ j $ 的卷积核，它是一个对角矩阵因此只有$n$$ n $ 个参数。（它就是前述的滤波器${\mathbf{K}}_{\theta }$$ \mathbf K_\theta $ ）。
   • ${\mathbf{H}}^{(l-1)}$$ \mathbf H^{(l-1)} $ 为第$l$$ l $ 层的输入信号（也是第$l-1$$ l-1 $ 层的输出信号）。${\mathbf{H}}^{(0)}=\mathbf{X}$$ \mathbf H^{(0)}=\mathbf X $ 。
   • $d_{l-1}$$ d_{l-1} $ 为第$l$$ l $ 层输入信号的通道数，$d_l$$ d_l $ 为第$l$$ l $ 层输出信号的通道数。

   由于图拉普拉斯矩阵的特征分解 eigendecomposition，Spectral CNN 面临三个限制：

   • 首先，对图的任何扰动都会导致特征根 eigenbasis 的变化。
   • 其次，学习的滤波器是transductive 的，它无法应用于具有不同结构的图。
   • 最后，特征分解计算复杂度为$O(n^3)$$ O(n^3) $ 。在后续工作中，ChebNet 和 GCN 通过进行一些近似和简化将计算复杂度降低到$O(m)$$ O(m) $ 。

3. Chebyshev Spectral CNN:ChebNet 通过切比雪夫多项式来逼近滤波器${\mathbf{K}}_{\theta }$$ \mathbf K_\theta $ （注：它是一个对角矩阵）。即：

   $${\mathbf{K}}_{\theta }=\sum _{i=0}^K{\theta }_i{T}_i\left(\tilde{\mathbf{\Lambda }}\right)$$

   其中$\tilde{\mathbf{\Lambda }}=\frac{2\mathbf{\Lambda }}{{\lambda }_{max}}-\mathbf{I}$$ \tilde{\mathbf \Lambda} = \frac{2\mathbf{\Lambda}}{\lambda_\max} - \mathbf I $ ，${\lambda }_{max}$$ \lambda_\max $ 为最大特征值。因此$\tilde{\mathbf{\Lambda }}$$ \tilde{\mathbf \Lambda} $ 是一个对角线元素取值在 [-1,1] 之间的对角矩阵。

   切比雪夫多项式定义为：

   $$\begin{array}{c}{T}_i(x)=2x\times T_{i-1}(x)-T_{i-2}(x)\\ T_0(x)=1,T_1=x\end{array}$$

   因此图信号$\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^n$$ \mathbf{\vec x}\in \mathbb R^n $ 的卷积定义为：

   $$\overrightarrow{\mathbf{x}}{\ast }_{\mathcal{G}}{\overrightarrow{\mathbf{g}}}_{\theta }=\mathbf{U}{\mathbf{K}}_{\theta }{\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}=\mathbf{U}\left(\sum _{i=0}^K{\theta }_i{T}_i\left(\tilde{\mathbf{\Lambda }}\right)\right){\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}$$

   定义$\tilde{\mathbf{L}}=\frac{2\mathbf{L}}{{\lambda }_{max}}-\mathbf{I}$$ \tilde{\mathbf L} = \frac{2\mathbf L}{\lambda_\max} - \mathbf I $ ，则有$T_i(\tilde{\mathbf{L}})=\mathbf{U}{T}_i(\tilde{\mathbf{\Lambda }}){\mathbf{U}}^{\mathrm{\top }}$$ T_i(\tilde{\mathbf L}) = \mathbf UT_i(\tilde{\mathbf \Lambda})\mathbf U^\top $ 。因此得到 ChebNet 卷积公式：

   $$\overrightarrow{\mathbf{x}}{\ast }_{\mathcal{G}}{\overrightarrow{\mathbf{g}}}_{\theta }=\sum _{i=0}^K{\theta }_i{T}_i\left(\tilde{\mathbf{L}}\right)\overrightarrow{\mathbf{x}}$$

   作为对 Spectral CNN 的改进，ChebNet 定义的滤波器是空间局部性的，这意味着滤波器可以独立于图的大小而抽取局部特征。

   另外，ChebNet 将频谱 spectrum 线性映射到 [-1,1] 之间（即线性映射：$2{\lambda }_i/{\lambda }_{max}-1$$ 2\lambda_i/\lambda_\max - 1 $ ）。

4. CayleyNet 进一步使用参数为有理复函数rational complex function 的 Cayley 多项式来捕获窄带信号narrow frequency band 。CayleyNet 的谱图卷积定义为：

   $$\overrightarrow{\mathbf{x}}{\ast }_{\mathcal{G}}{\overrightarrow{\mathbf{g}}}_{\theta }=c_0\overrightarrow{\mathbf{x}}+2\times \text{Re}\left\{\sum _{j=1}^r{c}_j{(h\mathbf{L}-i\mathbf{I})}^j{(h\mathbf{L}+i\mathbf{I})}^{-j}\overrightarrow{\mathbf{x}}\right\}$$

   其中：

   • Re(.) 返回复数的实部。
   • $c_0$$ c_0 $ 为实数系数，$c_j$$ c_j $ 为复数系数，$i$$ i $ 为单位虚数，$h$$ h $ 为卷积核参数用于控制 Cayley 滤波器的谱spectrum 。

   CayleyNet 不仅可以保持空间局部性 spatial locality，而且 ChebNet 可以视为 CayleyNet 的特例。

5. Graph Convolutional Network:GCN 对 ChebNet 采用一阶近似。假设$K=1$$ K=1 $ 以及${\lambda }_{max}=2$$ \lambda_\max = 2 $ ，则ChebNet 卷积公式近似为：

   $$\overrightarrow{\mathbf{x}}{\ast }_{\mathcal{G}}{\overrightarrow{\mathbf{g}}}_{\theta }=\sum _{i=0}^K{\theta }_i{T}_i\left(\tilde{\mathbf{L}}\right)\overrightarrow{\mathbf{x}}\simeq {\theta }_0\overrightarrow{\mathbf{x}}-{\theta }_1{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}\overrightarrow{\mathbf{x}}$$

   为限制参数数量从而缓解过拟合，GCN 进一步假定$\theta ={\theta }_0=-{\theta }_1$$ \theta = \theta_0 = -\theta_1 $ ，因此上式进一步简化为：

   $$\overrightarrow{\mathbf{x}}{\ast }_{\mathcal{G}}{\overrightarrow{\mathbf{g}}}_{\theta }\simeq \theta (\mathbf{I}+{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2})\overrightarrow{\mathbf{x}}$$

   为支持多通道输入和多通道输出，GCN 进一步将上式转换为：

   $$\mathbf{H}=\mathbf{X}{\ast }_{\mathcal{G}}{\mathbf{g}}_{\mathbf{\Theta }}=f\left(\overline{\mathbf{A}}\mathbf{X}\mathbf{\Theta }\right)$$

   其中：

   • $\overline{\mathbf{A}}=\mathbf{I}+{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}$$ \bar{\mathbf A} = \mathbf I+\mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2} $ 。
   • $f(\cdot )$$ f(\cdot) $ 为非线性激活函数。
   • $\mathbf{X}\in {\mathbb{R}}^{n\times d_{in}}$$ \mathbf X\in \mathbb R^{n\times d_{in}} $ 为$d_{in}$$ d_{in} $ 个通道的输入信号。
   • $\mathbf{H}\in {\mathbb{R}}^{n\times d_{out}}$$ \mathbf H\in \mathbb R^{n\times d_{out}} $ 为$d_{out}$$ d_{out} $ 个通道的输出信号。
   • $\mathbf{\Theta }\in {\mathbb{R}}^{d_{in}\times d_{out}}$$ \mathbf \Theta\in \mathbb R^{d_{in}\times d_{out}} $ 为卷积核参数。

   由于使用$\mathbf{I}+{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}$$ \mathbf I+\mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2} $ 实际应用中会导致 GCN 数值不稳定。为解决该问题，GCN 应用了归一化技巧，将$\overline{\mathbf{A}}=\mathbf{I}+{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}$$ \bar{\mathbf A} = \mathbf I+\mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2} $ 代替为：

   $$\begin{array}{c}\overline{\mathbf{A}}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}\\ \tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I},\tilde{\mathbf{D}}=\text{diag}({\tilde{D}}_1,\cdots ,{\tilde{D}}_n),{\tilde{D}}_i=\sum _j{\tilde{A}}_{i,j}\end{array}$$

   GCN 虽然是基于谱域的方法，也可以解释为基于空域的方法。从基于空域的角度来看，GCN 可以视为聚合节点邻域中的特征信息。即$\mathbf{H}=\mathbf{X}{\ast }_{\mathcal{G}}{\mathbf{g}}_{\mathbf{\Theta }}=f\left(\overline{\mathbf{A}}\mathbf{X}\mathbf{\Theta }\right)$$ \mathbf H = \mathbf X*_\mathcal G \mathbf g_\mathbf\Theta = f\left(\bar{\mathbf A}\mathbf X\mathbf \Theta\right) $ 视作：

   $${\overrightarrow{\mathbf{h}}}_v=f\left({\mathbf{\Theta }}^{\mathrm{\top }}\left(\sum _{u\in {\mathcal{N}}_v\cup \{v\}}{\overline{A}}_{v,u}{\overrightarrow{\mathbf{x}}}_u\right)\right),\mathrm{\forall }v\in \mathcal{V}$$

6. 最近的一些工作通过探索某些对称矩阵来代替邻接矩阵从而对 GCN 进行增量改进 incremental improvement 。

   • Adaptive Graph Convolutional Network:AGCN 学习隐藏的结构关系，这种关系未被图的邻接矩阵所给出。

     AGCN 通过一个可学习的距离函数来构造一个所谓的残差图邻接矩阵 residual graph adjacency matrix 。这个距离函数将两个节点的特征作为输入。

   • Dual Graph Convolutional Network:DGCN 引入双图卷积体系架构，它有两个并行的图卷积层。这两个图卷积层共享参数，但是分别使用归一化的邻接矩阵$\overline{\mathbf{A}}$$ \bar{\mathbf A} $ 、以及positive pointwise mutual information:PPMI 矩阵。

     PPMI 矩阵通过从图上采样的随机游走来捕获节点的共现信息，定义为：

     $${\text{PPMI}}_{i,j}=max(\log \left(\frac{c_{i,j}\times |\mathcal{D}|}{c_i\times c_j}\right),0)$$

     其中：

     • ${\text{PPMI}}_{i,j}$$ \text{PPMI}_{i,j} $ 表示节点$v_i,v_j$$ v_i,v_j $ 的共现 PPMI 值。
     • $\mathcal{D}$$ \mathcal D $ 为随机游走统计到的所有节点 pair 对的集合，$|\mathcal{D}|$$ |\mathcal D| $ 表示集合的大小。
     • $c_i$$ c_i $ 表示$\mathcal{D}$$ \mathcal D $ 中节点$v_i$$ v_i $ 出现的频次，$c_j$$ c_j $ 表示$\mathcal{D}$$ \mathcal D $ 中节点$v_j$$ v_j $ 出现的频次，$c_{i,j}$$ c_{i,j} $ 表示$\mathcal{D}$$ \mathcal D $ 中节点$v_i,v_j$$ v_i,v_j $ 共现的频次。

     通过集成 ensembling 来自双图卷积层的输出，DGCN 可以对局部结构信息和全局结构信息进行编码，无需堆叠多个图卷积层。

3.4.2 基于空域的 ConvGNN

1. 和在图像上进行卷积操作的传统 CNN 类似，基于空域的方法基于节点的空间关系定义图卷积。

   图像可以被视为图的一种特殊形式，其中：图像上每个像素代表一个节点，每个像素直接与其附近的像素相连。在图像上应用一个 3x3 的卷积可以获得每个通道上中心节点及其邻居（共9 个节点）像素值的加权均值。

   类似地，基于空域的图卷积将中心节点的representation 和邻居的 representation 进行卷积，从而得到中心节点的更新 representation 。

   从另一个角度来看，基于空域的 ConvGNN 和 RecGNN 共享相同的消息传递思想。空域图卷积运算本质上是沿着edge 传播节点信息。

2. Neural Network for Graphs:NN4G 和 GNN* 同一时期被提出，它是针对基于空域的 ConvGNN 的第一项工作。

   和 RecGNN 截然不同的是，NN4G 通过每层具有独立参数的组合神经网络体系架构来学习节点的相互依赖关系。节点的邻域可以通过体系结构的增量构建来扩张。

   NN4G 通过直接聚合节点的邻域信息来执行图卷积，它还使用残差链接 residual connection 以及跳跃连接 skip connection 来记住每一层的信息。最终NN4G 的节点状态更新方程为：

   $${\overrightarrow{\mathbf{h}}}_v^{(l)}=f({\mathbf{W}}^{(l{)}^{\mathrm{\top }}}{\overrightarrow{\mathbf{x}}}_v+\sum _{i=1}^{l-1}\sum _{u\in {\mathcal{N}}_v}{\mathbf{\Theta }}^{(l{)}^{\mathrm{\top }}}{\overrightarrow{\mathbf{h}}}_u^{(i)})$$

   其中：$f(\cdot )$$ f(\cdot) $ 为非线性激活函数，${\overrightarrow{\mathbf{h}}}_v^{(0)}=\overrightarrow{\mathbf{0}}$$ \mathbf{\vec h}_v^{(0)} = \mathbf{\vec 0} $ 。

   上式也可以写作矩阵形式：

   $${\mathbf{H}}^{(l)}=f(\mathbf{X}{\mathbf{W}}^{(l)}+\sum _{i=1}^{l-1}\mathbf{A}{\mathbf{H}}^{(i)}{\mathbf{\Theta }}^{(l)})$$

   这类似于 GCN 的形式。一个区别是 NN4G 使用未归一化的邻接矩阵，这可能潜在地导致节点的 hidden state 具有极为不同的量级。

3. Contextual Graph Markov Model:CGMM 受到NN4G 启发，从而提出了一种概率模型。CGMM 在保持空间局部性的同时，还具有可解释性的优势。

4. Diffusion Convolutional Neural Network:DCNN 将图卷积视为扩散过程。它假定信息以一定的转移概率从一个节点转移到相邻节点之一，从而使得信息分布可以在几轮之后达到平衡。DCNN 将扩散图卷积diffusion graph convolution 定义为：

   $${\mathbf{H}}^{(l)}=f({\mathbf{W}}^{(l)}\odot \left({\mathbf{P}}^l\mathbf{X}\right))$$

   其中：

   • $f(\cdot )$$ f(\cdot) $ 为非线性激活函数，$\odot$$ \odot $ 为逐元素相乘。
   • $\mathbf{P}={\mathbf{D}}^{-1}\mathbf{A}\in {\mathbb{R}}^{n\times n}$$ \mathbf P= \mathbf D^{-1}\mathbf A\in \mathbb R^{n\times n} $ 为转移概率矩阵，${\mathbf{P}}^l=\underset{l}{\underbrace{\mathbf{P}\cdots \mathbf{P}}}$$ \mathbf P^l = \underbrace{\mathbf P\cdots\mathbf P}_{l} $ 为$l$$ l $ 个$\mathbf{P}$$ \mathbf P $ 相乘。
   • ${\mathbf{W}}^{(l)}\in {\mathbb{R}}^{n\times d}$$ \mathbf W^{(l)}\in \mathbb R^{n\times d} $ 为第$l$$ l $ 层的参数。

   注意在 DCNN 中，hidden representation 矩阵${\mathbf{H}}^{(l)}$$ \mathbf H^{(l)} $ 的维度和输入特征矩阵$\mathbf{X}\in {\mathbb{R}}^{n\times d}$$ \mathbf X\in \mathbb R^{n\times d} $ 相同，并且不是前一层 hidden representation 矩阵${\mathbf{H}}^{(l-1)}$$ \mathbf H^{(l-1)} $ 的函数。

   最终 DCNN 拼接${\mathbf{H}}^{(1)},\cdots ,{\mathbf{H}}^{(L)}$$ \mathbf H^{(1)},\cdots,\mathbf H^{(L)} $ 为模型最终输出。

5. 由于扩散过程的平稳分布是概率转移矩阵的幂级数的总和，因此 Diffusion Graph Convolution:DGC 将每个扩散step 中的结果相加，而不是进行拼接。它定义扩散图卷积diffusion graph convolution 为：

   $$\mathbf{H}=\sum _{l=0}^{L}f\left({\mathbf{P}}^l\mathbf{X}{\mathbf{W}}^{(l)}\right)$$

   其中：

   • $f(\cdot )$$ f(\cdot) $ 为非线性激活函数。
   • ${\mathbf{W}}^{(l)}\in {\mathbb{R}}^{d\times d_{out}}$$ \mathbf W^{(l)}\in \mathbb R^{d\times d_{out}} $ ，其中$d$$ d $ 为输入特征维度，$d_{out}$$ d_{out} $ 为输出representation 维度。这使得hidden representation 矩阵${\mathbf{H}}^{(l)}\in {\mathbb{R}}^{n\times d_{out}}$$ \mathbf H^{(l)}\in \mathbb R^{n\times d_{out}} $ 的维度和输入特征矩阵$\mathbf{X}\in {\mathbb{R}}^{n\times d}$$ \mathbf X\in \mathbb R^{n\times d} $ 维度可以不同。

6. 使用转移概率矩阵的幂意味着距离遥远的邻居向中心节点贡献的信息很少。PGC-DGCNN 根据最短路径增加遥远邻居的贡献，它定义最短路径邻接矩阵${\mathbf{S}}^{(j)}$$ \mathbf S^{(j)} $ ：如果从节点$v$$ v $ 到节点$u$$ u $ 的最短路径为$j$$ j $ 则${\mathbf{S}}_{v,u}^{(j)}=1$$ \mathbf S_{v,u}^{(j)} = 1 $ ，否则${\mathbf{S}}_{v,u}^{(j)}=0$$ \mathbf S_{v,u}^{(j)} = 0 $ 。

   转移概率矩阵的幂次意味着邻居节点的重要性随着距离的增加呈指数型衰减，而这里的权重设定为 1 。

   通过使用超参数$r$$ r $ 控制感受野大小receptive field size，PGC-DGCNN 引入了图卷积运算如下：

   $${\mathbf{H}}^{(l)}=|{|}_{j=0}^{r}f\left({\left({\tilde{\mathbf{D}}}^{(j)}\right)}^{-1}{\mathbf{S}}^{(j)}{\mathbf{H}}^{(l-1)}{\mathbf{W}}^{(j,l)}\right)$$

   其中：

   • $f(\cdot )$$ f(\cdot) $ 为非线性激活函数，$||$$ || $ 表示向量拼接。
   • ${\tilde{\mathbf{D}}}^{(j)}$$ \tilde{\mathbf D}^{(j)} $ 为根据${\mathbf{S}}^{(j)}$$ \mathbf S^{(j)} $ 计算得到的度矩阵：${\tilde{\mathbf{D}}}^{(j)}=\text{diag}({\tilde{D}}_1^{(j)},\cdots ,{\tilde{D}}_n^{(j)}),{\tilde{D}}_i^{(j)}=\sum _k{S}_{i,k}^{(j)}$$ \tilde{\mathbf D}^{(j)}=\text{diag}(\tilde D^{(j)}_1,\cdots,\tilde D^{(j)}_n),\tilde D^{(j)}_i=\sum_k S_{i,k}^{(j)} $ 。
   • ${\mathbf{W}}^{(j,l)}\in {\mathbb{R}}^{d_{l-1}\times d_l}$$ \mathbf W^{(j,l)}\in \mathbb R^{d_{l-1}\times d_l} $ 为最短路径$j$$ j $ 在第$l$$ l $ 层的参数，$d_l$$ d_l $ 为第$l$$ l $ 层representation 的维度。

   由于最短路径邻接矩阵${\mathbf{S}}^{(j)}$$ \mathbf S^{(j)} $ 的计算复杂度为$O(n^3)$$ O(n^3) $ ，因此该方法计算代价太高。

7. Partition Graph Convolution:PGC 根据某些原则（不限于最短路径）将节点的邻居划分为$Q$$ Q $ 个分组，并根据每个组定义的邻域来构造$Q$$ Q $ 个邻接矩阵。然后PGC 将具有不同参数的 GCN 应用于每个邻居分组，并对结果求和：

   $${\mathbf{H}}^{(l)}=\sum _{q=1}^Q{\overline{\mathbf{A}}}^{(q)}{\mathbf{H}}^{(l-1)}{\mathbf{W}}^{(q,l)}$$

   其中：

   • ${\mathbf{H}}^{(0)}=\mathbf{X}$$ \mathbf H^{(0)} = \mathbf X $ ，${\mathbf{H}}^{(l)}\in {\mathbb{R}}^{n\times d_l}$$ \mathbf H^{(l)}\in \mathbb R^{n\times d_l} $ 为第$l$$ l $ 层的 representation，$d_l$$ d_l $ 为第$l$$ l $ 层的 representation的维度。
   • ${\overline{\mathbf{A}}}^{(q)}={\left({\tilde{\mathbf{D}}}^{(q)}\right)}^{-1/2}{\tilde{\mathbf{A}}}^{(q)}{\left({\tilde{\mathbf{D}}}^{(q)}\right)}^{-1/2}$$ \bar{\mathbf A}^{(q)} = \left(\tilde{\mathbf D}^{(q)}\right)^{-1/2}\tilde{\mathbf A}^{(q)}\left(\tilde{\mathbf D}^{(q)}\right)^{-1/2} $ ，${\tilde{\mathbf{A}}}^{(q)}={\mathbf{A}}^{(q)}+\mathbf{I}$$ \tilde{\mathbf A}^{(q)} = \mathbf A^{(q)} + \mathbf I $ ，${\tilde{\mathbf{D}}}^{(q)}$$ \tilde{\mathbf D}^{(q)} $ 为${\tilde{\mathbf{A}}}^{(q)}$$ \tilde{\mathbf A}^{(q)} $ 的度矩阵。
   • ${\mathbf{W}}^{(q,l)}\in {\mathbb{R}}^{d_{l-1}\times d_l}$$ \mathbf W^{(q,l)}\in \mathbb R^{d_{l-1}\times d_l} $ 为分组$q$$ q $ 的参数矩阵。

   类似于注意力机制中的 multi-head 。

8. Message Passing Neural Network:MPNN 总结了基于空域的 ConvGNN 的通用框架。MPNN 将图卷积视为一个消息传递过程，其中信息可以直接从一个节点沿着边传递到另一个节点。MPNN 执行$L$$ L $ 步消息传递从而使得信息传递得更远。

   消息传递函数（即空间图卷积）定义为：

   $${\overrightarrow{\mathbf{h}}}_v^{(l)}=U_l({\overrightarrow{\mathbf{h}}}_v^{(l-1)},\sum _{u\in {\mathcal{N}}_v}{M}_l({\overrightarrow{\mathbf{h}}}_v^{(l-1)},{\overrightarrow{\mathbf{h}}}_u^{(l-1)},{\overrightarrow{\mathbf{e}}}_{v,u}))$$

   其中：

   • $U_l(\cdot ),M_l(\cdot )$$ U_l(\cdot), M_l(\cdot) $ 都是可学习的函数。
   • ${\overrightarrow{\mathbf{h}}}_v^{(l)}\in {\mathbb{R}}^{d_l}$$ \mathbf{\vec h}_v^{(l)}\in \mathbb R^{d_l} $ 为节点$v$$ v $ 在第$l$$ l $ 层的 representation，${\overrightarrow{\mathbf{h}}}_v^{(0)}={\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec h}_v^{(0)} = \mathbf{\vec x}_v $ 。

   在得到每个节点的hidden representation 之后，可以将${\overrightarrow{\mathbf{h}}}_v^{(L)}$$ \mathbf{\vec h}_v^{(L)} $ 传递到输出层从而执行 node-level 预测任务，或者传递给 readout 函数从而执行 graph-level 预测任务。readout 函数基于节点hidden representation 从而生成整个图的 representation：

   $${\overrightarrow{\mathbf{h}}}_{\mathcal{G}}=R({\overrightarrow{\mathbf{h}}}_v^{(L)}\mid v\in \mathcal{V})$$

   其中$R(\cdot )$$ R(\cdot) $ 表示可学习的 readout 函数。

9. 虽然 MPNN 可以通过选择不同形式的$U_l(\cdot ),M_l(\cdot ),R(\cdot )$$ U_l(\cdot),M_l(\cdot),R(\cdot) $ 从而覆盖cover 很多现有的 GNN 模型，但是 Graph Isomorphism Network:GIN 发现：基于 MPNN 的方法无法根据它们生成的 graph embedding 来区分不同的图结构。

   为弥补这一缺陷，GIN 通过可学习的参数${ϵ}^{(l)}$$ \epsilon^{(l)} $ 来调整中心节点的权重。它定义图卷积为：

   $${\overrightarrow{\mathbf{h}}}_v^{(l)}=\text{MLP}((1+{ϵ}^{(l)}){\overrightarrow{\mathbf{h}}}_v^{(l-1)}+\sum _{u\in {\mathcal{N}}_v}{\overrightarrow{\mathbf{h}}}_u^{(l-1)})$$

   其中$\text{MLP}(\cdot )$$ \text{MLP}(\cdot) $ 表示多层感知机。

10. 由于节点的邻居数量可能从1 到 1000 甚至更多，因此获取节点的全部邻居效率太低。GraphSAGE 采用采样技术为每个节点获取固定数量的邻居，并定义图卷积为：

    $${\overrightarrow{\mathbf{h}}}_v^{(l)}=\sigma \left({\mathbf{W}}^{(l)}{\text{Agg}}_l({\overrightarrow{\mathbf{h}}}_v^{(l-1)},\{{\overrightarrow{\mathbf{h}}}_u{,}^{(l-1)},\mathrm{\forall }u\in {\mathcal{S}}_{{\mathcal{N}}_v}\})\right)$$

    其中：

    • $\sigma (\cdot )$$ \sigma(\cdot) $ 为非线性激活函数，${\text{Agg}}_l(\cdot )$$ \text{Agg}_l(\cdot) $ 为第$l$$ l $ 层的聚合函数，${\mathcal{S}}_{{\mathcal{N}}_v}$$ \mathcal S_{\mathcal N_v} $ 为节点$v$$ v $ 随机采样的邻域。
    • ${\overrightarrow{\mathbf{h}}}_v^{(l)}\in {\mathbb{R}}^{d_l}$$ \mathbf{\vec h}_v^{(l)}\in \mathbb R^{d_l} $ 为节点$v$$ v $ 在第$l$$ l $ 层的 representation，${\overrightarrow{\mathbf{h}}}_v^{(0)}={\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec h}_v^{(0)} = \mathbf{\vec x}_v $ 。

    聚合函数需要满足排列不变性 permutation invariant ，如均值函数、求和函数、最大值函数等。

11. Graph Attention Network:GAT 假设邻居节点对于中心节点的贡献既不像GraphSAGE 一样都是 1 （即所有邻居节点对于中心节点的贡献都相同）、也不像 GCN 一样预先定义（权重为$\frac{1}{\sqrt{{\text{deg}}_i\times {\text{deg}}_j}}$$ \frac{1}{\sqrt{\text{deg}_i\times \text{deg}_j}} $ ），如下图所示。

    

    GAT 采用注意力机制来学习两个相连节点之间的相对权重，它定义图卷积运算为：

    $${\overrightarrow{\mathbf{h}}}_v^{(l)}=\sigma \left(\sum _{u\in {\mathcal{N}}_v\cup \{v\}}{\alpha }_{v,u}^{(l)}{\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}_u^{(l-1)}\right)$$

    其中${\overrightarrow{\mathbf{h}}}_v^{(0)}={\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec h}_v^{(0)} = \mathbf{\vec x}_v $ ，${\alpha }_{v,u}^{(l)}$$ \alpha_{v,u}^{(l)} $ 刻画了节点$v$$ v $ 及其邻居节点$u$$ u $ 的注意力强度：

    $${\alpha }_{v,u}^{(k)}=\text{softmax}\left(g\left({\overrightarrow{\mathbf{a}}}^{\mathrm{\top }}[{\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}_v^{(l-1)}||{\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}_u^{(l-1)}]\right)\right)$$

    其中：

    • $g(\cdot )$$ g(\cdot) $ 为 LeakyReLU 激活函数。
    • $\overrightarrow{\mathbf{a}}$$ \mathbf{\vec a} $ 为可学习的注意力向量。
    • $||$$ || $ 表示向量拼接。
    • softmax 函数可以确保节点$v$$ v $ 的所有邻居（包括节点$v$$ v $ 自身）的注意力权重之和为 1.0 。

    GAT 进一步执行multi-head attention 从而提高模型的表达能力。在节点分类任务上，GAT 相对于 GraphSAGE 有着显著的提升。

12. GAT 假设attention head 的贡献是相等的，而Gated Attention Network:GAAN 认为不同的 attention head 的贡献是不同的。GAAN 引入了一种 self-attention 机制，该机制为每个 attention head 计算一个额外的注意力得分。

13. 除了在空间上 spatially 应用图注意力之外，GeniePath 进一步提出了一种类似于 LSTM 的门控机制，从而控制跨图卷积层的信息流。

    还有其它有趣的图注意力模型，但是它们不属于 ConvGNN 框架。

14. Mixture Model Network:MoNet 采用不同的方法为节点的邻居分配不同的权重，它引入节点伪坐标 pseudo-coordinates 以确定节点及其邻居之间的相对位置。一旦知道两个节点之间的相对位置，则权重函数会根据相对位置计算这两个节点之间的相对权重。这样，图滤波器的参数可以在不同位置 location 之间共享。

    在 MoNet 框架下，通过构造非参数的 nonparametric 权重函数，几种流形manifold 方法如 Geodesic CNN: GCNN、Anisotropic CNN : ACNN、Spline CNN，某些图卷积方法如 GCN、DCNN ，都可以视作 MoNet 的特例。

    MoNet 还提出了一个具有可学习参数的高斯核，从而自适应地学习权重函数。

15. 另一类独特的方法是：根据某些标准对节点的邻居进行排名ranking，并将每个排名与可学习的权重相关联，从而在不同位置实现权重共享。

    • PATCHY-SAN 根据它们的图标签graph label对每个节点的邻居进行排序，并选择 top q 个邻居。图标签本质上是节点得分，可以通过节点 degree、节点中心度centrality、节点 Weisfeiler-Lehman color 得到。

      由于每个节点现在都有固定数量的有序邻居，因此可以将图结构数据转换为网格结构的数据。PATCHY-SAN 采用标准的 1D 卷积滤波器来聚合邻域特征信息，其中滤波器权重的顺序和节点邻居的顺序相对应。

    • PATCHY-SAN 的排名准则仅考虑图结构，这需要大量计算才能进行数据处理。Large-scale Learnable Graph Convolutional Network:LGCN 根据节点特征信息对节点的邻居进行排名。对于每个节点，LGCN 都会拼装assemble 一个由其邻域组成的特征矩阵，并沿着每一列（行代表节点、列代表特征）对该矩阵进行排序。排序后的特征矩阵的前$k$$ k $ 行被用于中心节点的输入数据从而执行标准的卷积运算。

      下图中，矩阵第一行是中心节点的特征向量，它不参与排序。后面 4 行是排序之后的。排序时，不同列之间相互独立排序。

      

3.4.3 空域 ConvGNN 训练效率

1. 通常训练诸如 GCN 之类的 ConvGNN 需要将整个图数据和所有节点的中间状态保存到内存中，因此 ConvGNN 的 full-batch 训练算法遭受内存溢出的困扰，尤其是当一个图包含数百万节点时。

2. 为降低内存需求，GraphSAGE 提出了一种针对 ConvGNN 的 batch 训练算法。对于batch 中的每个节点，它以固定大小递归采样节点邻域从而构成一棵以该节点为根节点的采样树。对于每棵采样树，GraphSAGE 通过从下到上分层聚合节点的 hidden representation 来计算根节点的 hidden representation 。

3. Fast Learning with Graph Convolutional Network:FastGCN 为每个图卷积层采样固定数量的节点，而不是像 GraphSAGE 那样为每个节点采样固定数量的邻居。它将图卷积解释为概率测度下节点 embedding 函数的积分变换，然后采用蒙特卡洛近似Monte Carlo approximation 以及方差缩减技术 variance reduction technique 来加速训练过程。

4. 由于 FastGCN 针对每一层独立采样节点，因此层间连接可能很稀疏。《Adaptive sampling towards fast graph representation learning》 提出一种自适应的逐层采样方法，其中较低层的节点采样以上一层已经采样到的节点为条件。和 FastGCN 相比，该方法以更复杂的采样方案为代价实现了更高的准确率。

5. Stochastic Training of Graph Convolutional Networks:StoGCN 使用历史的节点representation 作为控制变量从而将图卷积的感受野尺寸receptive field size 缩减到任意小的尺度scale。即使每个节点仅有两个邻居（其中一个是它自己），StoGCN 仍然可以达到可比的comparable 性能。但是，StoGCN 仍然必须保存所有节点的中间状态，这对于大型图来讲是非常消耗内存的。

6. Cluster-GCN 使用图聚类算法对子图进行采样，并对所采样的子图中的节点执行图卷积。由于邻域搜索被限制在采样的子图中，因此 Cluster-GCN 能够处理更大的图，并同时使用更少的时间、更少的内存来训练更深的体系架构。

   对于现有的 ConvGNN 训练算法，Cluster-GCN 特别提供了时间复杂度和内存复杂度的直接比较，如下表所示。其中$n$$ n $ 为节点数量、$m$$ m $ 为边数量、$K$$ K $ 为层数、$s$$ s $ 为 batch size、$r$$ r $ 为每个节点采样的邻居数量。为简化讨论，我们假设所有层的 hidden representation 维度都是$d$$ d $ 。

   • GCN 是full-batch 训练方法，它作为 baseline 。
   • GraphSAGE 以牺牲时间效率来节省内存。同时随着$K$$ K $ 和$r$$ r $ 的增加，GraphSAGE 的时间和内存复杂度呈指数级增长。
   • StoGCN 的时间复杂度最高，并且内存瓶颈仍未解决。但是，StoGCN 可以通过很小的$r$$ r $ 获得令人满意的性能。
   • Cluster-GCN 的时间复杂度和 baseline 相同，因为它没有引入冗余计算。
   • 所有方法中，ClusterGCN 实现了最低的内存复杂度。

   

3.4 .4 spectral vs spatial

1. 谱域模型 spectral model 具有图信号处理的理论基础，可以通过设计新的图信号滤波器来构建新的 ConvGNN。但是，由于效率efficiency、通用性generality、灵活性flexibility 等问题，空域模型spatial model 要优于谱域模型。

   • 首先，谱域模型的效率不如空域模型。谱域模型要么需要执行特征向量 eigenvector 计算，要么需要同时处理整个图。

     空域模型对于大型图更具有可扩展性scalable，因为它通过信息传播直接在图域graph domain 中执行卷积。计算可以在一个 batch 的节点上进行，而不是整个图。

   • 其次，依赖于图傅里叶基graph Fourier basis 的谱域模型无法泛化到新的图。因为谱域模型假设图是固定的，对图的任何扰动都将导致本征基eigenbasis 的变化。

     另一方面，空域模型在每个节点的局部执行图卷积，其中模型权重可以在不同位置、不同结构之间轻松共享。

   • 最后，谱域模型仅限于在无向图上运行，而空域模型可以更灵活地处理多种数据源multi-source的图输入graph input，如edge input、有向图、有符号图、异质图等。因为这些图输入可以轻松地集成到空域模型的聚合函数中。

3.4.5 Graph Pooling 模型

1. GNN 生成节点特征后，我们可以将其用于最终任务。但是，直接使用所有节点的特征可能在计算上具有挑战性，因此需要一种降采样策略down-sampling strategy 。根据不同的任务目标、以及降采样在网络中扮演的角色，该策略有不同的称呼：

   • pooling 操作：旨在通过对所有节点representation 进行降采样从而生成规模更小的 representation 从而减少参数大小，进而缓解过拟合、实现置换不变性 permutation invariance、以及解决计算复杂度问题。
   • readout 操作：旨在基于节点 representation 生成 graph-level representation 。

   它们的机制都非常相似，因此这里我们用池化pooling 来指代用于GNN 中的各种降采样策略。

2. 在一些早期的工作中，图粗化算法graph coarsening algorithm 使用特征分解 eigen-decomposition 来基于图的拓扑结构来粗化图。但是这些方法存在时间复杂度问题。

   • Graclus 算法是特征分解的替代方法，用于计算原始图的聚类版本clustering version 。有一些近期的工作将它作为池化操作来粗化图。

   • 如今，mean/max/sum 池化是实现降采样的最原始、最有效的方法，因为在池化窗口中计算 mean/max/sum 值非常快：

     $${\overrightarrow{\mathbf{h}}}_G=\text{mean/max/sum}({\overrightarrow{\mathbf{h}}}_1^{(K)},\cdots ,{\overrightarrow{\mathbf{h}}}_n^{(K)})$$

     其中$K$$ K $ 为最后一层图卷积层的编号（即一共$K$$ K $ 层图卷积层）。

     《Deep convolutional networks on graph-structured data》 表明：在网络开始时执行简单的max/mean 池化对于降低图域的维度、缓解昂贵的图傅里叶变换的成本尤为重要。

     另外，《Graph echo state networks》、《Neural message passing for quantum chemistry》、《On filter size in graph convolutional networks》 也是用注意力机制来改进 mean/sum 池化。

3. 即使使用注意力机制，reduction 操作（如sum pooling ）效果也不理想，因为它使得 embedding 低效 inefficient ：无论图的尺寸 size 如何，都生成固定尺寸 fixed-size 的 embedding 。

   《Order matters: Sequence to sequence for sets》 提出了 Set2Set 方法来生成一个随着输入尺寸而增加的 memory embedding 。然后它实现了一个 LSTM ，该 LSTM 试图在reduction 操作之前将order-dependent 信息集成到 memory embedding 中；否则销毁destroy 该信息。

4. 《Convolutional neural networks on graphs with fast localized spectral filtering》 以另一种方式通过以有意义的方式重排图的节点来解决这个问题。他们在自己的方法 ChebNet 中设计了一种有效的池化策略：

   • 首先通过 Graclus 算法将输入图粗化为多个level 。
   • 粗化之后，输入图的节点及其粗化版本重排为为平衡二叉树。
   • 然后对平衡二叉树从底部到顶部任意聚合，这将使得相似的节点排列在一起。

   池化这种重排的信号要比池化原始信号有效得多。

5. 《An end-to-end deep learning architecture for graph classification》 提出了 DGCNN，它具有类似的叫做 SortPooling 的池化策略，该策略通过将节点重排为有意义的顺序来执行池化。

   和 ChebNet 不同，DGCNN 根据节点在图中的结构角色对节点进行排序。来自空间图卷积的、图的无序的节点特征被视为连续的 WL colors ，然后将它们用于对节点进行排序。除了对节点特征进行排序外，它还通过截断/扩展truncating/extending 节点特征矩阵，从而将图的大小归一化为$q$$ q $ ：

   • 如果$n>q$$ n\gt q $ ，则原始特征矩阵最后$n-q$$ n-q $ 行被截断。
   • 如果$n<q$$ n\lt q $ ，则原始特征矩阵添加$q-n$$ q-n $ 行全零。

6. 上述池化方法主要考虑图的特征而忽略图的结构信息。最近提出了一个可微的池化方法DiffPool，它可以生成图的层次 representation。和所有之前的粗化方法相比，DiffPool 不仅简单地将图上的节点聚类，而且还学习了第$k$$ k $ 层的聚类分配矩阵cluster assignment metrix$\mathbf{S}$$ \mathbf S $ ，记作${\mathbf{S}}^{(k)}\in {\mathbb{R}}^{n_k\times n_{k+1}}$$ \mathbf S^{(k)}\in \mathbb R^{n_k\times n_{k+1}} $ ，其中$n_k$$ n_k $ 为第$k$$ k $ 层的节点数量。

   矩阵${\mathbf{S}}^{(k)}$$ \mathbf S^{(k)} $ 中的概率值是根据节点特征和拓扑结构来生成：

   $${\mathbf{S}}^{(k)}=\text{softmax}\left({\text{ConvGNN}}_k({\mathbf{A}}^{(k)},{\mathbf{H}}^{(k)})\right)$$

   其中：

   • ${\mathbf{A}}^{(k)}$$ \mathbf A^{(k)} $ 为第$k$$ k $ 层的邻接矩阵（粗化后的节点）。
   • ${\mathbf{H}}^{(k)}$$ \mathbf H^{(k)} $ 为第$k$$ k $ 层的节点 representation （粗化后的节点）。
   • ${\text{ConvGNN}}_k$$ \text{ConvGNN}_k $ 为第$k$$ k $ 层采用的 ConvGNN 。

   该方法的核心思想是学习同时考虑图的拓扑结构和特征信息的节点分配 node assignment ，因此上式可以使用任何标准的 ConvGNN 实现（因为 ConvGNN 同时使用图的拓扑结构和特征信息）。但是 DiffPool 的缺点是在池化后会生成稠密图 dense graph，此后的计算复杂度变成$O(n^2)$$ O(n^2) $ （之前是$O(m)$$ O(m) $ ） 。

7. 最近提出了 SAGPool 方法，该方法同时考虑节点的特征信息和图拓扑结构信息，并以一种self-attention 的方式学习了池化。

8. 总体而言，池化是减小图尺寸的基本操作。如何提高池化的有效性、降低计算复杂度是一个尚待研究的问题。

3.4.6 理论分析

1. 我们从不同角度讨论图神经网络的理论基础。

2. 感受野形状shape of receptive field：节点的感受野是有助于确定其final node representation 的一组节点。当组合多个空间图卷积层时，每新增一层，节点的感受野就会向更远的邻居前进一步。

   《Neural network for graphs: A contextual constructive approach》 证明：存在有限数量的空间图卷积层，使得对于任意节点$v\in \mathcal{V}$$ v\in \mathcal V $ ，节点$v$$ v $ 的感受野覆盖了图中所有的节点。结果 ConvGNN 能够通过堆叠局部的图卷积层来抽取全局信息。

3. VC 维：VC 维是模型复杂度的度量，定义为模型能够打散 shattere 的最大样本数。

   分析 GNN 的 VC 维的工作很少。 《The vapnik–chervonenkis dimension of graph and recursive neural networks》指出，给定模型参数数量$p$$ p $ 、图节点数量$n$$ n $ ：

   • 如果使用 sigmoid 或者tanh 激活函数，则GNN* 的 VC 维为$O(p^4{n}^2)$$ O(p^4n^2) $ 。
   • 如果使用分段多项式激活函数，则GNN* 的 VC 维为$O(p^{2}n)$$ O(p^2n) $ 。

   该结果表明：如果使用 sigmoid 或者 tanh 激活函数，则 GNN* 的模型复杂度会随着$p$$ p $ 和$n$$ n $ 的增加而迅速增加。

4. 图同构 graph isomorphism ：如果两个图在拓扑上相同，则它们是同构的。

   给定两个非同构non-isomorphic 图${\mathcal{G}}_1,{\mathcal{G}}_2$$ \mathcal G_1,\mathcal G_2 $ ，《How powerful are graph neural networks 》 证明：如果GNN 将${\mathcal{G}}_1,{\mathcal{G}}_2$$ \mathcal G_1,\mathcal G_2 $ 映射到不同的 embedding ，则可以通过 Weisfeiler-Lehman:WL 同构测试将这两个图识别为非同构的。他们表示：常见的 GNN（如 GCN,GraphSAGE） 无法区分不同的图结构。

   论文进一步证明：如果 GNN 的聚合函数和 readout 函数是单射 injective 的，则 GNN 在区分同构图的能力上最多和 WL test 一样。

   单射函数$f$$ f $ ：若$a\ne b$$ a\ne b $ 则$f(a)\ne f(b)$$ f(a)\ne f(b) $ 。

5. 等变性和不变性equivariance and invariance：执行 node-level 任务时，GNN 必须是等变函数 equivariant function ；而执行 graph-level 任务时，GNN 必须是不变函数 invariant function 。

   • 对于node-level 任务，令$f(\mathbf{A},\mathbf{X})\in {\mathbb{R}}^{n\times d}$$ f(\mathbf A,\mathbf X)\in \mathbb R^{n\times d } $ 为一个 GNN，$\mathbf{Q}$$ \mathbf Q $ 为任意改变节点顺序的排列矩阵 permutation matrix （即单位矩阵$\mathbf{I}$$ \mathbf I $ 经过任意行变换、或列变换得到的矩阵）。如果满足$f(\mathbf{Q}\mathbf{A}{\mathbf{Q}}^{\mathrm{\top }},\mathbf{Q}\mathbf{X})=\mathbf{Q}f(\mathbf{A},\mathbf{X})$$ f(\mathbf Q\mathbf A\mathbf Q^\top,\mathbf Q\mathbf X) = \mathbf Qf(\mathbf A,\mathbf X) $ ，则这个 GNN 是等变的 equivariant 。
   • 对于 graph-level 任务，令$f(\mathbf{A},\mathbf{X})\in {\mathbb{R}}^d$$ f(\mathbf A,\mathbf X)\in \mathbb R^{ d } $ 为一个 GNN，如果满足$f(\mathbf{Q}\mathbf{A}{\mathbf{Q}}^{\mathrm{\top }},\mathbf{Q}\mathbf{X})=f(\mathbf{A},\mathbf{X})$$ f(\mathbf Q\mathbf A\mathbf Q^\top,\mathbf Q\mathbf X) = f(\mathbf A,\mathbf X) $ ，则这个 GNN 是不变的 invariant 。

   为了实现等变性 equivariance 或不变性invariance ，GNN 的组件components 必须满足对节点顺序是不变的invariant 。论文 《Invariant and equivariant graph networks》 从理论上研究了图数据的排列不变性permutation invariant 、排列等变性permutation equivariant 的线性层的特点。

6. 通用逼近 universal approximation：众所周知，具有单层 hidden layer 的MLP 前馈神经网络可以逼近任何 Borel 可测函数。但是很少有人研究 GNN 的通用逼近能力。

   • 《Universal approximation capability of cascade correlation for structures》 证明级联相关cascade correlation 可以逼近结构化输出的函数。
   • 《Computational capabilities of graph neural networks》 证明RecGNN 可以逼近任何函数到任意精度，该函数保持展开等价性unfolding equivalence。如果两个节点的展开树 unfolding trees 相同，则这两个节点的展开等价。其中节点的展开树是通过以一定深度迭代扩展节点的邻域来构造的。
   • 《How powerful are graph neural networks》 表明：在消息传递框架下 ConvGNN 不是在多集合multisets上定义的连续函数的通用逼近器。
   • 《Invariant and equivariant graph networks》 证明了不变图网络 invariant graph network 可以逼近图上定义的任意不变函数invariant function 。

3.5 GAE

1. 图自编码器Graph Autoencoder: GAE 是一种深度神经网络架构，可以将节点映射到潜在表示latent representation ，然后从潜在表示中解码图信息。

   GAE 可用于学习graph embedding 或者生成新图，下表总结了部分 GAE 的主要特点。下文中，我们从 graph embedding 和 graph generation 角度简要概述了 GAE 。

   

3.5.1 Graph Embedding

1. graph embedding 是节点的低维向量表示，可以保留节点的拓扑信息。GAE 使用编码器抽取graph embedding 、并使用解码器来强迫graph embedding 保留图拓扑信息（如PPMI 矩阵和邻接矩阵）从而学习 graph embedding 。

2. 早期的方法主要采用多层感知机MLP 来构建用于学习 graph embedding 的 GAE。

   • Deep Neural Network for Graph Representations:DNGR 使用堆叠的降噪自编码器 denoising autoencoder 通过MLP 来编码和解码 PPMI 矩阵。

   • 同时，Structural Deep Network Embedding:SDNE 使用堆叠自编码器来同时保存节点的一阶邻近度 first-order proximity 和二阶邻近度second-order proximity 。SDNE 在编码器输出和解码器输出上分别提出了损失函数。

     • 第一个损失函数针对编码器输出，通过最小化节点的 graph embedding 及其邻居的 graph embedding 之间的距离，来迫使学到的 graph embedding 保持节点的一阶邻近度。这个损失函数定义为：

       $${\mathcal{L}}_{1st}=\sum _{(v,u)\in \mathcal{E}}{A}_{v,u}{\Vert \text{enc}({\overrightarrow{\mathbf{x}}}_v)-\text{enc}({\overrightarrow{\mathbf{x}}}_u)\Vert }^2$$

       其中：

       • ${\overrightarrow{\mathbf{x}}}_v=(A_{v,1},\cdots ,A_{v,n}{)}^{\mathrm{\top }}$$ \mathbf{\vec x}_v = (A_{v,1},\cdots,A_{v,n})^\top $ 为邻接矩阵$\mathbf{A}$$ \mathbf A $ 的第$v$$ v $ 行。
       • $\text{enc}(\cdot )$$ \text{enc}(\cdot) $ 为多层感知机multi-layer perceptron:MLP 组成的编码器。

     • 第二个损失函数针对解码器输出，通过最小化自编码器输入及其重构的输出之间的距离，来迫使学到的 graph embedding 保留节点的二阶邻近度。这个损失函数定义为：

       $${\mathcal{L}}_{2nd}=\sum _{v\in \mathcal{V}}{\Vert (\text{dec}(\text{enc}({\overrightarrow{\mathbf{x}}}_v))-{\overrightarrow{\mathbf{x}}}_v)\odot {\overrightarrow{\mathbf{b}}}_v\Vert }^2$$

       其中：

       • $\text{dec}(\cdot )$$ \text{dec}(\cdot) $ 为多层感知机MLP 组成的解码器。

       • $\odot$$ \odot $ 为逐元素乘积，${\overrightarrow{\mathbf{b}}}_v$$ \mathbf{\vec b}_v $ 定义为：

         $$\begin{array}{c}{b}_{v,u}=\{\begin{array}{ll}1,& \text{if}{A}_{v,u}=0\\ \beta >1,& \text{if}{A}_{v,u}=1\end{array}\end{array}$$

         这迫使模型更关注相连节点的损失。

       这里自编码器的输入为节点的邻接向量，因此重构节点的邻接向量意味着保持节点的邻域，即二阶邻近度。

3. DNGR 和 SDNE 仅考虑和节点pair 对之间的连通性有关的节点结构信息，他们忽略节点可能包含描述节点本身属性的特征信息。《Variational graph auto-encoders》 提出了Graph Autoencoder （记作 GAE* 以示区分）来利用 GCN 同时编码节点结构信息和节点特征信息。

   GAE* 的编码器由两个图卷积层组成，其形式为：

   $$\mathbf{Z}=\text{enc}(\mathbf{X},\mathbf{A})=\text{Gconv}(f(\text{Gconv}(\mathbf{A},\mathbf{X};{\mathbf{\Theta }}_1));{\mathbf{\Theta }}_2)$$

   其中：

   • $\mathbf{Z}$$ \mathbf Z $ 表示图的 graph embedding 矩阵。
   • $f(\cdot )$$ f(\cdot) $ 为非线性激活函数，如 ReLU 。
   • $\text{Gconv}(\cdot )$$ \text{Gconv}(\cdot) $ 为$\mathbf{H}=\mathbf{X}{\ast }_{\mathcal{G}}{\mathbf{g}}_{\mathbf{\Theta }}=f\left(\overline{\mathbf{A}}\mathbf{X}\mathbf{\Theta }\right)$$ \mathbf H = \mathbf X*_\mathcal G \mathbf g_\mathbf\Theta = f\left(\bar{\mathbf A}\mathbf X\mathbf \Theta\right) $ 定义的图卷积层。

   GAE* 的解码器旨在通过重构图邻接矩阵，从而从节点的 embedding 中解码节点之间的关系信息。解码器定义为：

   $${\hat{A}}_{v,u}=\text{dec}({\overrightarrow{\mathbf{z}}}_v,{\overrightarrow{\mathbf{z}}}_u)=\sigma ({\overrightarrow{\mathbf{z}}}_v\cdot {\overrightarrow{\mathbf{z}}}_u)$$

   其中${\overrightarrow{\mathbf{z}}}_v$$ \mathbf{\vec z}_v $ 为节点$v$$ v $ 的 embedding 。

   GAE* 通过最小化给定真实邻接矩阵$\mathbf{A}$$ \mathbf A $ 和重构的邻接矩阵$\hat{\mathbf{A}}$$ \hat{\mathbf A} $ 之间的负交叉熵negative cross entropy 来训练。

4. 由于自编码器的容量capacity ，简单地重构图邻接矩阵可能会导致过拟合。《Variational graph auto-encoders》 同时提出了变分图自编码器Variational Graph Autoencoder:VGAE ，它是GAE 的变分版本，用于学习数据分布。

   VGAE 优化变分下限$L$$ L $ ：

   $$L={\mathbb{E}}_{q(\mathbf{Z}\mid \mathbf{X},\mathbf{A})}[\log p(\mathbf{A}\mid \mathbf{Z})]-\text{KL}[q(\mathbf{Z}\mid \mathbf{X},\mathbf{A})||p(\mathbf{Z})]$$

   其中：

   • KL(.) 为KL 散度函数，用于衡量两个分布之间的距离。

   • $p(\mathbf{Z})$$ p(\mathbf Z) $ 为一个高斯先验分布，其中：

     $$p(\mathbf{Z})=\prod _{i=1}^{n}p({\overrightarrow{\mathbf{z}}}_i)=\prod _{i=1}^n\mathcal{N}({\overrightarrow{\mathbf{z}}}_i\mid \overrightarrow{\mathbf{0}},\mathbf{I})$$

   • $p(A_{i,j}=1\mid {\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)=\text{dec}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)=\sigma ({\overrightarrow{\mathbf{z}}}_i\cdot {\overrightarrow{\mathbf{z}}}_j)$$ p(A_{i,j}=1\mid \mathbf{\vec z}_i,\mathbf{\vec z}_j) = \text{dec}(\mathbf{\vec z}_i,\mathbf{\vec z}_j) = \sigma(\mathbf{\vec z}_i\cdot \mathbf{\vec z}_j) $ 。

   • $q(\mathbf{Z}\mid \mathbf{X},\mathbf{A})=\prod _{i=1}^{n}q({\overrightarrow{\mathbf{z}}}_i\mid \mathbf{X},\mathbf{A})$$ q(\mathbf Z\mid \mathbf X,\mathbf A) = \prod_{i=1}^n q(\mathbf{\vec z}_i\mid \mathbf X,\mathbf A) $ ，$q({\overrightarrow{\mathbf{z}}}_i\mid \mathbf{X},\mathbf{A})=\mathcal{N}({\overrightarrow{\mathbf{z}}}_i\mid {\overrightarrow{\mu }}_i,\text{diag}({\sigma }_i^2))$$ q(\mathbf{\vec z}_i\mid \mathbf X,\mathbf A)=\mathcal N(\mathbf{\vec z}_i\mid \vec \mu_i,\text{diag}(\sigma_i^2)) $ 。其中：高斯分布均值向量${\overrightarrow{\mu }}_i$$ \vec\mu_i $ 为一个编码器输出的第$i$$ i $ 行；$\log {\sigma }_i$$ \log \sigma_i $ 类似于${\overrightarrow{\mu }}_i$$ \vec\mu_i $ ，它是另一个编码器的输出。

   根据上述公式，VGAE 假设经验分布$q(\mathbf{Z}\mid \mathbf{X},\mathbf{A})$$ q(\mathbf Z\mid \mathbf X,\mathbf A) $ 应该和先验分布$\mathbf{p}(\mathbf{Z})$$ \mathbf p(\mathbf Z) $ 尽可能接近。

   损失函数的第一项要求最大后验分布，第二项要求经验分布$q(\mathbf{Z}\mid \mathbf{X},\mathbf{A})$$ q(\mathbf Z\mid \mathbf X,\mathbf A) $ 应该和先验分布$\mathbf{p}(\mathbf{Z})$$ \mathbf p(\mathbf Z) $ 尽可能一致。

5. 为进一步强制经验分布$q(\mathbf{Z}\mid \mathbf{X},\mathbf{A})$$ q(\mathbf Z\mid \mathbf X,\mathbf A) $ 逼近于先验分布$p(\mathbf{Z})$$ p(\mathbf Z) $ ，对抗正则变分图自编码器Adversarially Regularized Variational Graph Autoencoder:ARVGA 采用了生成对抗网络generative adversarial network:GAN 的方案。

   GAN 在训练生成模型时会在生成器 generator 和判别器 discriminator 之间进行竞争比赛：生成器试图生成尽可能真实的 fake 样本，而判别器试图将fake 样本和真实样本区分开。

   受GAN 的启发，ARVGA 努力学习一种编码器，该编码器产生的经验分布$q(\mathbf{Z}\mid \mathbf{X},\mathbf{A})$$ q(\mathbf Z\mid \mathbf X,\mathbf A) $ 和先验分布$p(\mathbf{Z})$$ p(\mathbf Z) $ 难以区分。

6. 类似于 GAE*，GraphSAGE 用两个图卷积层编码节点特征。GraphSAGE 并没有优化重建损失，而是表明两个节点之间的关系信息可以通过负采样来保留，其损失函数为：

   $$\mathcal{L}({\overrightarrow{\mathbf{z}}}_v)=-\log (\text{dec}({\overrightarrow{\mathbf{z}}}_v,{\overrightarrow{\mathbf{z}}}_u))-Q{\mathbb{E}}_{v_n\sim P_n(v)}[\log (-\text{dec}({\overrightarrow{\mathbf{z}}}_v,{\overrightarrow{\mathbf{z}}}_{v_n}))]$$

   其中：

   • 节点$u$$ u $ 是节点$v$$ v $ 的邻居节点，节点$v_n$$ v_n $ 是远离节点$v$$ v $ 的节点并且从负采样分布negative sampling distribution$P_n(v)$$ P_n(v) $ 中采样得到。
   • $Q$$ Q $ 为节点$v$$ v $ 负采样的 “负节点” 数量。

   该损失函数本质上是迫使相邻的节点具有相似的representation、距离遥远的节点具有不同的 representation 。

7. DGI 和 GraphSAGE 不同，它通过最大化局部互信息local mutual information 来驱动局部网络 embedding （local network embedding ）来捕获全局结构信息。从实验上看，它比 GraphSAGE 有明显改进。

8. 上述方法本质上是通过解决链接预测问题来学习 graph embedding。但是，图的稀疏性导致 postive 节点 pair 对的数量远远少于 negative 节点 pair 对的数量。

   为缓解学习graph embedding 中的数据稀疏性问题，另一个方向的工作通过随机排列或随机游走将图转换为序列。通过这种方式，一些适用于序列的深度学习方法可以直接用于处理graph 。

   Deep Recursive Network Embedding:DRNE 假设节点的 graph embedding 应该近似于它邻域节点 embedding 的聚合。它采用 LSTM 来聚合节点的邻域 embedding。DRNE 的重构误差定义为：

   $$\mathcal{L}=\sum _{v\in \mathcal{V}}{\Vert {\overrightarrow{\mathbf{z}}}_v-\text{LSTM}\left(\{{\overrightarrow{\mathbf{z}}}_u\mid u\in {\mathcal{N}}_v\}\right)\Vert }^2$$

   其中：

   • ${\overrightarrow{\mathbf{z}}}_v$$ \mathbf{\vec z}_v $ 为节点$v$$ v $ 的 embedding，它直接通过一个字典 look-up 得到。
   • 节点$v$$ v $ 邻居的随机序列并经过 degree 排序后作为 LSTM 网络的输入。

   如公式所示，DRNE 通过 LSTM 来隐式学到 graph embedding ，而不是直接使用 LSTM 来生成 graph embedding 。它避免了 LSTM 对于节点序列的排列不是不变 invariant 的问题。

9. 对抗正则化自编码器Adversarially Regularized Autoencoder:NetRA 提出一个带通用损失函数的graph encoder-decoder 框架。其损失函数定义为：

   $$\mathcal{L}=-{\mathbb{E}}_{\overrightarrow{\mathbf{z}}\in P_{data}(\overrightarrow{\mathbf{z}})}(\text{dist}(\overrightarrow{\mathbf{z}},\text{dec}(\text{enc}(\overrightarrow{\mathbf{z}}))))$$

   其中：

   • dist(.) 为节点 embedding$\overrightarrow{\mathbf{z}}$$ \mathbf{\vec z} $ 和重构的embedding$\text{dec}(\text{enc}(\overrightarrow{\mathbf{z}}))$$ \text{dec}(\text{enc}(\mathbf{\vec z})) $ 之间的距离。
   • enc(.) 和 dec(.) 分别为编码器和解码器。它们都是 LSTM 网络，使用以节点$v\in \mathcal{V}$$ v\in \mathcal V $ 为根节点的随机游走序列作为输入。

   类似于 ARVGA，NetRA 通过对抗训练将学到的 graph embedding 正则化到先验分布中。尽管 NetRA 忽略了 LSTM 网络中节点的排列不变性的问题，但实验结果验证了 NetARA 的有效性。

3.5.2 Graph Generation

1. 给定多个图，GAE 通过将图编码为hidden representation 并根据这个representation 解码图结构，从而可以学到图的生成分布generative distribution。大多数图生成的 GAE 旨在解决分子图molecular graph 生成问题，这在药物发现中具有很高的实用价值。这些方法要么以顺序方式sequential manner 、要么以全局方式 global manner生成一个新的图。

2. 顺序方式通过逐步生成节点和边来生成图。

   • 《Automatic chemical design using a data-driven continuous representation of molecules》、《Grammar variational autoencoder》、《Syntax-directed variational autoencoder for molecule generation》 用深度 CNN 作为编码器、深度 RNN 作为解码器，对名为 SMILES 的分子图字符串的生成过程建模。

     尽管这些方法是domain-specific，但是它们通过将节点、边迭代地添加到图上直到满足特定条件为止，从而可以适用于一般的图生成。

   • Deep Generative Model of Graphs:DeepGMG 假设图的概率是所有可能的节点排列之和：

     $$p(\mathcal{G})=\sum _{\pi }p(\mathcal{G},\pi )$$

     其中$\pi$$ \pi $ 表示一种节点排列顺序。

     DeepGMG 捕获图中所有节点和边的、复杂的联合概率。

     DeepGMG通过做出一系列决策来生成图，即：是否添加节点、添加哪个节点、是否对这个新节点添加边、这个新节点连接到哪个节点。生成节点和边的决策过程取决于这个不断增长growing 图的节点状态和图状态，其中节点状态和图状态通过 RecGNN 来更新。

   • 在另一项工作中，GraphRNN 提出一个 graph-level 的 RNN 以及一个 edge-level 的 RNN 来建模节点和边的生成过程。每次 graph-level RNN 都会向节点序列中添加一个新的节点，而 edge-level RNN 生成一个binary sequence ，它指示新节点和节点序列中之前生成的节点之间的连接。

3. 全局方式可以一次性生成整个图。

   • 图变分自编码器Graph Variational Autoencoder:GraphVAE 将节点和边的存在建模为独立随机变量。通过假设后验分布posterior distribution$q_{\varphi }(\overrightarrow{\mathbf{z}}\mid \mathcal{G})$$ q_\phi(\mathbf{\vec z}\mid \mathcal G) $ （它由编码器定义）、生成分布generative distribution$p_{\theta }(\mathcal{G}\mid \overrightarrow{\mathbf{z}})$$ p_\theta(\mathcal G\mid \mathbf{\vec z}) $ （它由解码器定义），GraphVAE 优化变分下界：

     $$\mathcal{L}(\varphi ,\theta ;\mathcal{G})={\mathbb{E}}_{q_{\varphi }(\overrightarrow{\mathbf{z}}\mid \mathcal{G})}[-\log p_{\theta }(\mathcal{G}\mid \overrightarrow{\mathbf{z}})]+\text{KL}[q_{\varphi }(\overrightarrow{\mathbf{z}}\mid \mathcal{G})||p(\overrightarrow{\mathbf{z}})]$$

     其中：

     • $p(\overrightarrow{\mathbf{z}})$$ p(\mathbf{\vec z}) $ 为服从高斯分布的先验分布。
     • $\varphi ,\theta$$ \phi,\theta $ 为待学习的参数。

     使用 ConvGNN 作为编码器、使用简单的MLP 作为解码器，GraphVAE 输出生成的图及其邻接矩阵、节点属性、边属性。

   • 控制生成图的全局属性（如图的连接性connectivity、有效性 validity，以及节点兼容性 compatibility）具有挑战性。正则化图变分自编码器Regularized Graph Variational Autoencoder:RGVAE 进一步在图变分自编码器上施加了有效性约束 validity constraint ，从而正则化解码器的输出分布。

   • 分子生成对抗网络 Molecular Generative Adversarial Network:MolGAN 整合了 ConvGNN、GAN 、以及强化学习技术从而生成具有所需特性的图。

     MolGAN 由生成器和判别器组成，它们相互竞争从而提高生成器的真实性 authenticity 。在 MolGAN 中，生成器试图提出一个 fake 图及其特征矩阵，而判别器目标是将 fake 数据和真实数据中区分开。

     另外，引入了和判别器并行的奖励网络，从而鼓励生成的图具有某些特性。

   • NetGAN 将 LSTM 和 Wasserstein GAN 结合起来，通过基于随机游走的方法生成图。NetGAN 训练生成器通过 LSTM 网络生成合理的随机游走，并强迫判别器从真实的随机游走中识别 fake 随机游走。

     训练好之后，通过归一化基于生成器产生的随机游走而计算得到的节点共现矩阵，从而得到新的图。

4. 总之：

   • 顺序方式将图线性化为序列。由于存在环结构，因此它们可能会丢失结构信息。
   • 全局方式可以一次性生成一个图。由于 GAE 的输出空间可达$O(n^2)$$ O(n^2) $ ，因此它不是可扩展的 scalable 。

3.6 SPATIAL-TEMPORAL GNN

1. 在很多实际应用中，图在结构和输入方面都是动态的。时空图神经网络patial-temporal graph neural network: STGNN 在捕获图的动态性中占据重要位置。该类别下的方法旨在建模动态的节点输入，同时假设已连接节点之间的相互依赖性。

   STGNN 假设图的结构不变，需要建模的是节点的动态属性。

   例如，交通网络由放置在道路上的速度传感器组成，其中传感器之间的边的权重由传感器之间距离决定。由于一条道路的交通状况可能取决于其相邻道路的交通状况，因此执行交通速度预测时，必须考虑空间依赖性。作为解决方案，STGNN 可以同时捕获图的空间依赖性和时间依赖性。

   STGNN 的任务可以是预测节点未来的值或标签，或者预测时空图的 graph label 。

2. STGNN 有两个方向，即：基于 RNN 的方法RNN-based method、基于 CNN 的方法CNN-based method 。

3.6.1 Rnn-based

1. 大多数基于 RNN 的方法通过使用图卷积来过滤传递给 RNN 单元的 input 和 hidden state 来捕获时空依赖性。为了说明这一点，假设一个简单的 RNN 采用以下形式：

   $${\mathbf{H}}^{(t)}=\sigma (\mathbf{W}{\mathbf{X}}^{(t)}+\mathbf{U}{\mathbf{H}}^{(t-1)}+\overrightarrow{\mathbf{b}})$$

   其中：

   • ${\mathbf{X}}^{(t)}\in {\mathbb{R}}^{n\times d}$$ \mathbf X^{(t)}\in \mathbb R^{n\times d} $ 为节点在时刻$t$$ t $ 的特征矩阵。
   • ${\mathbf{H}}^{(t)}\in {\mathbb{R}}^{n\times d_h}$$ \mathbf H^{(t)}\in \mathbb R^{n\times d_h} $ 为节点在时刻$t$$ t $ 的 representation 矩阵。
   • $\sigma (\cdot )$$ \sigma(\cdot) $ 为非线性激活函数。

   在插入图卷积之后，上式变为：

   $${\mathbf{H}}^{(t)}=\sigma (\text{GConv}({\mathbf{X}}^{(t)},\mathbf{A};\mathbf{W})+\text{GConv}({\mathbf{H}}^{(t-1)},\mathbf{A};\mathbf{U})+\overrightarrow{\mathbf{b}})$$

   其中 GConv(.) 为一个图卷积层。

2. 图卷积递归网络 Graph Convolutional Recurrent Network:GCRN 结合了 LSTM 网络和 ChebNet。

3. 扩散卷积递归神经网络Diffusion Convolutional Recurrent Neural Network:DCRNN 将扩散图卷积层（$\mathbf{H}=\sum _{k=0}^{K}f({\mathbf{P}}^k\mathbf{X}{\mathbf{W}}^{(k)})$$ \mathbf H=\sum_{k=0}^K f(\mathbf P^k\mathbf X \mathbf W^{(k)}) $ ）整合到 GRU 网络中。此外，DCRNN 采用 encoder-decoder 框架来预测未来$K$$ K $ 步的节点值。

4. 另一项同时进行的工作使用 node-level RNN 和 edge-level RNN 来处理时间信息的不同方面aspect 。

   Structural-RNN 提出了一个循环框架来预测每个time step 的节点标签。它包含两种 RNN，即：

   • node-RNN ：用于传递每个节点的时间信息。
   • edge-RNN ：用于传递每条边的时间信息。

   为整合空间信息，node-RNN 将 edge-RNN 的输出作为输入。

   由于为不同的节点和边采用不同的 RNN 会大大增加模型的复杂度，因此 Structural-RNN 将节点和边进行语义分组semantic group。相同语义组中的节点或边共享相同的 RNN 模型，从而降低计算成本。

3.6.2 CNN-based

1. 基于 RNN 的方法存在耗时的迭代传播、以及梯度爆炸/消失问题。作为替代方案，基于 CNN 的方法以非递归的方式处理时空图，具有计算并行、梯度稳定、内存需求低等优点。

2. 基于 CNN 的方法将 1D-CNN 层和图卷积层交织从而分别学习时间依赖性和空间依赖性。

   假设时空图神经网络的输入为张量$\mathbf{X}\in {\mathbb{R}}^{T\times n\times d}$$ \mathbf X \in \mathbb R^{T\times n\times d} $ ：

   • 1D-CNN 层在${\mathbf{X}}_{[:,i,:]}$$ \mathbf X_{[:,i,:]} $ 上沿着时间轴滑动，从而聚合每个节点的时间信息。

     给定空间，聚合时间。

   • 而图卷积层在${\mathbf{X}}_{[t,:,:]}$$ \mathbf X_{[t,:,:]} $ 上运行从而聚合每个时间步的空间信息。

     给定时间，聚合空间。

3. CGCN 将一维卷积层与 ChebNet 或 GCN 层整合在一起。它通过按顺序堆叠一个门控 1D 卷积层、一个图卷积层、另一个门控 1D 卷积层，从而构成时空块 spatial-temporal block 。

4. ST-GCN 使用 1D 卷积层和 PGC 层（${\mathbf{H}}^{(l)}=\sum _{q=1}^Q{\overline{\mathbf{A}}}^{(q)}{\mathbf{H}}^{(l-1)}{\mathbf{W}}^{(q,l)}$$ \mathbf H^{(l)} = \sum_{q=1}^Q \bar{\mathbf A}^{(q)}\mathbf H^{(l-1)}\mathbf W^{(q,l)} $ ）构成时空块。

5. 之前的方法都使用预定义的图结构，他们假设预定义的图结构反映了节点之间的真正依赖关系。

   但是，利用 spatial-temporal setting 中的很多图数据快照，可以从数据中自动学习潜在的静态图结构。为了实现这一点，Graph WaveNet 提出了一种自适应邻接矩阵来执行图卷积。自适应的邻接矩阵定义为：

   $${\mathbf{A}}_{adp}=\text{Softmax}\left(\text{ReLU}\left({\mathbf{E}}_1{\mathbf{E}}_2^{\mathrm{\top }}\right)\right)$$

   其中：

   • Softmax(.) 函数沿着行维度进行。
   • ${\mathbf{E}}_1$$ \mathbf E_1 $ 表示source 节点 embedding 。
   • ${\mathbf{E}}_2$$ \mathbf E_2 $ 表示 target 节点 embedding 。

   通过将${\mathbf{E}}_1$$ \mathbf E_1 $ 乘以${\mathbf{E}}_2$$ \mathbf E_2 $ ，可以得到 source 节点和 target 节点之间的依赖关系权重。借助基于 CNN 的复杂时空网络，Graph WaveNet 无需提供邻接矩阵即可表现良好。

6. 学习潜在的静态空间依赖性可以帮助研究人员发现网络中不同实体之间可解释的、稳定的相关性。但是，某些情况下，学习潜在的动态空间依赖性可以进一步提高模型的精度。例如，在交通网络中，两条道路之间的通行时间travel time 可能取决于它们当前的交通状况。

   • GaAN 利用注意力机制通过基于 RNN 的方法学习动态空间依赖性。注意力函数用于在给定这个边的两个节点的节点输入的情况下，更新边的权重。
   • ASTGCN 进一步包括空间注意力函数和时间注意力函数，从而通过基于 CNN 的方法学习潜在的动态空间相关性和动态时间相关性。

   学习潜在空间相关性的共同缺点是，它需要计算每对节点 pair 对之间的空间相关性权重，计算复杂度为$O(n^2)$$ O(n^2) $ 。

3.7 应用 & 方向

1. 由于图结构数据无处不在，因此 GNN 有广泛的应用。这里我们分别总结了 benchmark 图数据集、评估方法、开源实现。我们还详细介绍了 GNN 在各个领域的实际应用。

2. 数据集：我们将主要的图benchmark 数据集分为四类，即引文网络citation network、生化图biochemical graph、社交网络social network 以及其它。我们在下表给出了这些数据集的统计信息。

   • 引文网络：由论文、作者、以及它们之间的关系（如引用citation、作者、合著等关系）组成。尽管引文网络是有向图，但是评估节点分类、链接预测、节点聚类等任务的模型性能时，引文网络通常被视为无向图。

     流行的引文网络数据集有：

     • Cora数据集：包含 2708 篇机器学习论文组成，分为七个类别。每篇论文都由一个文章单词的 one-hot 向量表示，表示对应的单词是否出在论文中。
     • Citeseer数据集：包含 3327 篇科学论文，分为六个类别。每篇论文都由一个文章单词的 one-hot 向量表示，表示对应的单词是否出在论文中。
     • Pubmed数据集：包含 19717 篇与糖尿病有关的论文。每篇论文都由单词的 TF-IDF 向量来表示。
     • DBLP 数据集：包含数百万计算机科学论文及其作者，是一个大型的引文网络数据集。

   • 生化图：化学分子和化合物可以用化学图chemical graph 表示，原子为节点、化学键为边。

     • NCI-1 和 NCI-9 数据集：分别包含 4110 和 4127 个化学化合物，标记它们是否具有活性以阻止人类癌细胞系的生长。
     • MUTAG数据集：包含188 种硝基化合物，分别标记它们是芳香族还是杂芳香族。
     • D&D 和 PROTEIN数据集：将蛋白质表示为图，标记它们是酶还是非酶。
     • PTC 数据集：包含 344 种化合物，标记它们对雄性和雌性大鼠是否具有致癌性。
     • QM9数据集：记录最多含 9 个重原子的 133885 个分子的 13 个物理特性。
     • Alchemy 数据集：记录最多含 14 个重原子的 119487 个分子的 12 个量子力学特性。

     另一个重要的数据集是 ProteinProtein Interaction network:PPI数据集：包含 24个生物学图biological graph ，其中节点表示蛋白质，边表示蛋白质之间的相互作用。在 PPI 中，每个图都与一个人体组织相关联。每个节点的标签都是其生物学状态。

   • 社交网络：由在线服务（如 BlogCatalog 、Reddit）的用户交互形成。

     • BlogCatalog数据集：一个由博客作者及其社交关系组成的社交网络。博客作者的类别代表他们的个人兴趣。
     • Reddit数据集：从 Reddit 论坛收集的帖子形成的无向图。如果两个帖子包含同一个用户的讨论，则帖子之间存在链接。每个帖子都有一个标签，标记其所属社区community 。

   • 其它：还有几个其它数据集值得一提：

     • MNIST数据集：包含 70000 张 28 x 28 的图像，标记为 0~9 之间的十个数字。它是经典的手写数字识别数据集。

       我们可以基于像素位置构造一个 8-nearest-neighbor 图，从而将图片转换为 graph。

     • METR-LA数据集：一个时空图数据集。它包含洛杉矶高速公路上的 207 个传感器收集的四个月的交通数据。通过具有高斯阈值的sensor network distance 来计算图的邻接矩阵。

     • NELL数据集：从 Never-Ending Language Learning 项目获得的知识图谱。它由三元组表示的fact 组成，其中涉及两个实体及其关系。

   

3. 节点分类和图分类是评估 RecGNN 和 ConvGNN 性能的常用任务。

   • 节点分类：在节点分类中，大多数方法采用对 benchmark 数据集（包括 Cora,Citeseer,Pubmed,PPI,Reddit）进行标准的train/valid/test 划分。它们报告了多次运行测试数据集的平均准确率或 F1 得分，我们在下表给出了这些方法的实验结果的摘要。

     注意，这些结果不一定表示严格的比较。《Pitfalls of graph neural network evaluation》 指出，GNN 在节点分类任务的性能评估有两个陷阱：

     • 首先，在所有实验中使用相同的train/valid/test 划分会低估泛化误差。
     • 其次，不同的方法采用了不同的训练技术，如超参数调优、参数初始化、学习率衰减、早停技术。

     为了进行公平的比较，我们建议读者阅读论文 《Pitfalls of graph neural network evaluation》 。

     

   • 图分类：在图分类任务中，研究人员通常采用 10-fold 交叉验证进行模型评估。

     然而，正如 《A fair comparison of graph neural networks for graph classification》 所指出的，实验设置是模棱两可的ambiguous，并且在不同论文之间没有统一。具体而言，该论文抛出了在模型选择、模型评估方面对于数据集正确拆分的关注。一个经常遇到的问题是：每个 fold 的外部测试集都用于模型选择和风险评估。该论文在标准的、统一的评估框架中比较 GNN。他们使用一个external 的 10-fold 交叉来评估模型的泛化性能，并使用一个内部holdout 技术（具有 90%/10% 的train/valid 拆分）来选择模型。

     另一种方法是双交叉方法，该方法使用外部的 k-fold 交叉验证进行模型评估，使用内部的 k-fold 交叉验证进行模型选择。可以阅读该论文从而详细比较 GNN 方法的图分类任务性能。

4. 开源实现：我们在下表中给出了本文涉及到的 GNN 模型的开源实现的超链接。另外，PyTorch 有一个 PyTorch Geometirc 的库，它实现了很多 GNN；而 Deep Graph Library:DGL 也提供了很多 GNN 的快速实现。

   

5. GNN 在不同的任务、不同领域中都具有很多应用，这些任务包括节点分类、图分类、graph embedding、图生成、时空图预测、节点聚类、链接预测、图聚类。我们基于以下研究领域详细介绍了一些应用。

   • 计算机视觉Computer vision：GNN 在计算机视觉中的应用包括场景图生成scene graph generation、点云分类point clouds classification、动作识别action recognition 。

     • 识别对象之间的语义关系有助于理解视觉场景背后的含义。场景图生成模型旨在将图像解析为由对象及其语义关系组成的语义图semantic graph 。

       另一类应用通过给定场景图生成逼真的图像来执行场景图生成的逆向过程。由于自然语言可以解析为语义图，其中每个单词代表一个对象，因此对于给定文字说明的图像合成方法是一种很有前途的解决方案。

     • 通过对点云进行分类classifying 和分段segmenting ，LiDAR 设备可以 “看到” 周围的环境。点云是通过 LiDAR 扫描记录的一组 3D 点。

       《Dynamic graph cnn for learning on point clouds》、《Large-scale point cloud semantic segmentation with superpoint graphs》、《Rgcnn: Regularized graph cnn for point cloud segmentation》 将点云转换为 k 近邻图或者超点图 superpoint graph ，并使用 ConvGNN 探索拓扑结构。

     • 识别视频中包含的人的行为可以有助于机器更好地理解视频内容。一些解决方案可以检测视频中人体关节的位置，由骨骼链接的人体关节自然会形成图。给定人体关节位置的时间序列，《Structural-rnn:Deep learning on spatio-temporal graphs》 、《Spatial temporal graph convolutional networks for skeleton-based action recognition》 将 STGNN 用于学习人类行为模式。

       此外，计算机视觉中 GNN 的适用方向数量仍在增长，它包括：human-object 交互、few-shot 图片分类、语义分割semantic segmentation 、视觉推理visual reasoning 、知识问答。

   • 自然语言处理 NLP：GNN 在 NLP 中常见的应用是文本分类。GNN 利用文档或单词的内部关系来推断文档标签。尽管自然语言数据表现出序列结构，但是它们也可能包含图结构，如语法树。语法树定义了句子中单词之间的句法关系。

     《Encoding sentences with graph convolutional networks for semantic role labeling》 提出了运行在 CNN/RNN 句子编码器之上的Syntactic GCN。它根据句子的语法依存关系树syntactic dependency tree 聚合隐藏的单词representation 。

     《Graph convolutional encoders for syntax-aware neural machine translation》 将Syntactic GCN 应用于neural machine translation 任务。

     《Exploiting semantics in neural machine translation with graph convolutional networks》 进一步采用Syntactic GCN 相同的模型来处理句子的语义依赖图 semantic dependency graph 。

     graph-to-sequence learning 学习在给定摘要单词语义图a semantic graph of abstract words 条件下生成具有相同含义的句子，称作 Abstract Meaning Representation 。

     《A graph-to-sequence model for amr-to-text generation》 提出了一种 graph-LSTM 来编码 graph-level 语义信息。

     《Graph-to-sequence learning using gated graph neural networks》 将 GGNN 应用到 graph-to-sequence learning 以及 neural machine translation 。

     逆任务是sequence-to-graph learning。给定一个句子生成语义图或知识图在知识发现knowledge discovery 中非常有用。

   • 交通：在智能交通系统中，准确预测交通网络中的交通速度、交通流量、道路密度至关重要。

     《Gaan: Gated attention networks for learning on large and spatiotemporal graphs》、《Diffusion convolutional recurrent neural network: Data-driven traffic forecasting》、《Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting》 使用 STGNN 解决了交通预测问题。他们将交通网络视为时空图，其中节点是安装在道路上的传感器，边的权重是成对节点之间的距离。每个节点具有窗口内的平均交通速度作为动态输入特征。

     另一个工业级应用是出租车需求预测。给定历史的出租车需求、位置信息、天气数据、事件event 特征，《Deep multi-view spatial-temporal network for taxi demand prediction》 结合了LSTM,CNN 以及 LINE 训练的 graph embedding 从而形成每个位置的联合representation，以预测某个时间间隔内、某个位置所需的出租车数量。

   • 推荐系统：基于图的推荐系统将 item 和 user 作为节点。通过利用 item-item、user-user、user-item 以及内容信息之间的关系，基于图的推荐系统可以生成高质量的推荐。

     推荐系统的关键是评估 user 对于 item 的重要性得分，这可以转换为链接预测问题。为了预测 user 和 item 之间缺失的链接，《Graph convolutional matrix completion》、《Graph convolutional neural networks for web-scale recommender systems》 提出了一种使用 ConvGNN 作为编码器的 GAE 。《Geometric matrix completion with recurrent multi-graph neural networks》 将 RNN 和图卷积相结合，以学习生成已知评级rating 的底层过程 underlying process 。

   • 化学：在化学领域，研究人员应用 GNN 来研究分子/化合物的图结构。在分子/化合物图中，节点为原子、边为化学键。

     节点分类、图分类、图生成是针对分子/化合物图的三个主要任务，目的是学习分子指纹、预测分子特性、推断蛋白质interface、合成化合物。

   • 其它：GNN 的应用不限于上述领域和任务。已有研究者使用 GNN 对各种问题进行探索探索，如程序验证program verification、程序推理program reasoning、社交影响力预测social influence prediction、对抗攻击和预防adversarial attacks prevention、电器健康记录建模electrical health records modeling 、大脑网络brain network 、事件检测event detection 、组合优化combinatorial optimization 等。

6. 尽管 GNN 已经证明它在学习图数据方面的能力，但是由于图的复杂性，仍然存在挑战。我们这里提出 GNN 四个未来的发展方向：

   • 模型深度：深度学习的成功在于较深的神经网络体系架构，但是 《Deeper insights into graph convolutional networks for semi-supervised learning》 表明：ConvGNN 的性能随着图卷积层数量的增加而急剧下降。由于图卷积将相邻节点的 representation 推向彼此靠近，理论上如果卷积层数量无穷，则所有节点的 representation 都将收敛到一个点。这就提出了一个问题：即更深的模型是否仍然是学习图数据的好策略？

   • 扩展性trade-off：GNN 的可扩展性scalability 是以破坏图完整性completeness 为代价的。无论是采样还是聚类，模型都会丢失部分图信息。

     • 通过采样，节点可能会错过它的有影响力的邻居。
     • 通过聚类，可能丢失图的独有的结构模式。

     如何权衡算法的可扩展性和图的完整性可能是未来的研究方向。

   • 异质性 Heterogenity：当前的大多数GNN 假设图为同质图homogeneous 。难以将当前的 GNN 直接应用于异质图，因为异质图可能包含不同类型的节点和边，或者不同形式的节点输入、边输入（如图像和文本）。因此，应该设计新的方法来处理异质图。

   • 动态性Dynamicity：图在本质上是动态的，因为节点或边可能出现或消失，并且节点/边的输入可能会随着时间变化。需要新的图卷积从而适应图的动态性。虽然 STGNN 可以部分解决图的动态问题，但是很少有人考虑在动态空间关系的情况下如何执行图卷积。