Question

1. 摘要：很多学习任务需要处理包含元素之间丰富的关系信息的图数据。图神经网络 Graph Neural Networks:GNNs 是连接主义的模型connectionist model ，它通过图上节点之间的消息传递来捕获图的依赖关系。与标准的神经网络不同，图神经网络保留了一个状态，该状态能够代表来自任意深度的邻域的信息。尽管发现原始 GNN 难以训练得到一个不动点 fixed point ，但是网络体系结构、优化技术、并行计算的很多最新进展使得图神经网络能够成功地学习。

   近年来基于图神经网络的变体，如图卷积神经网络 Graph Convolutional Network: GCN、图注意力网络Graph Attention Network: GAT、图门控神经网络gated graph neural network: GGNN 已经在很多任务上展现了突破性的性能。

2. 引言：图 Graph 是一种数据结构，可用于一组对象（节点）及其关系（边）进行建模。近年来，由于图的强大表示能力，图的分析和研究受到越来越多的关注。作为机器学习中唯一的非欧几何数据结构，图分析重点关注于节点分类、链接预测、聚类。图神经网络 Graph Neural Networks: GNN 是在图上执行的、基于深度学习的方法。由于 GNN 令人信服的性能和高解释性，GNN 最近已经成为一种广泛应用的图分析方法。

   采用 GNN 有以下的动机 motivation：

   • GNN 第一个动机源于卷积神经网络 CNN。CNN 可以提取多尺度局部空间特征，并将其组合以构建高度表达能力的 representation。这导致了几乎所有机器学习领域的突破，并开启了深度学习的新时代。

     随着我们对 CNN 和图的深入研究，我们发现 CNN 的关键特性：局部链接、权重共享、使用 multi-layer 。这些对于解决图领域的问题也非常重要，因为：

     • 图是最典型的局部连接结构。
     • 和传统的谱图理论 spectral graph theory 相比，共享权重降低了计算成本。
     • multi-layer 结构是处理层级模式 hierarchical pattern 的关键，它捕获了各种尺度的特征。

     但是，CNN 只能处理诸如图像（2D 网格）、文本（1D 序列）之类的常规欧氏空间的数据。一种直觉的想法是将 CNN 推广到图数据上。然而，很难在图上定义局部卷积操作和池化操作，这阻碍了 CNN 应用到非欧空间的图上。

   • GNN 第二个动机来自于 graph embedding。graph embedding 学习图的节点、边或者子图subgraph 的 representatation 低维向量。

     在图分析领域，传统机器学习方法通常依赖于人工设计的特征，这种方式灵活性较差、成本很高。 结合表示学习 representation learning 思想以及 word embedding 的做法，DeepWalk 是第一种基于表示学习的 graph embedding 方法，它将 SkipGram 模型应用于图上生成的随机游走序列。类似的方法，如 node2vec,LINE, TADW 也取得了突破。

     但是，这些方法有两个严重不足：

     • 首先，编码器中的节点之间没有共享参数，这导致计算效率较低。因为这意味着参数数量随着节点数量线性增加。
     • 其次，直接 embedding 的方法缺少泛化能力，这意味着它们无法处理动态图，也无法泛化到新的图上。

   基于 CNN 和 graph embedding，人们提出了 GNN 来聚合图结构中的信息，从而可以对节点及其关联进行建模。

   论文 《Graph Neural Networks: A Review of Methods and Applications》 对现有的图神经网络模型进行详细的综述，并解释了 GNN 值得研究的根本原因：

   • 首先，像 CNN/RNN 这样的标准神经网络无法正确处理图输入，因为它们按照特定顺序堆叠了节点特征。但是，图的节点没有自然顺序 natural order。为了解决这个问题，GNN 分别在每个节点上传播，从而忽略了节点的输入顺序。即：GNN 的输出对于节点的输入顺序是不变的。

   • 其次，图的边表示两个节点的依赖关系。在标准神经网络中，依赖关系仅被视为节点的特征。但是，GNN 可以通过图结构进行传播，而不必将其用作特征的一部分。

   • 第三，推理reasoning 是高级人工智能的一个非常重要的研究课题，人脑的推理过程几乎是基于从日常经验中提取的图。标准的神经网络已经显示出通过学习数据的分布来生成合成的synthetic 图像和文档的能力，但是它们仍然无法从大型数据中学习 reasoning graph。

     而 GNN 试图从诸如场景图片、故事文档之类的非结构化数据生成graph ，这可以作为进一步的高级人工智能的强大神经网络模型。

     最近，已经证明具有简单架构的、未经训练的 GNN 也可以很好地发挥作用。

   论文贡献：

   • 论文对现有的图神经网络模型进行了详细的回顾。作者介绍了原始模型、变体、以及若干个通用框架。作者研究了这一领域的各种模型，并提供了一个 unified representation 来展示不同模型中的不同 propagation 步骤。通过识别相应的 aggregator 和 updater ，人们可以很容易地区分不同的模型。
   • 论文对应用进行了系统的分类，将应用分为结构性场景、非结构性场景和其他场景。在每个场景下，论文提出了几个主要的应用和相应方法。
   • 论文提出了未来研究的四个开放性问题。图神经网络存在 over-smoothing 和 scaling 问题。目前还没有有效的方法来处理动态图以及非结构化的感官数据 non-structural sensory data 的建模。作者对每个问题进行了深入分析，并提出了未来的研究方向。

2.1 模型

2.1.1 GNN

1. GNN 的概念第一次是在论文 《The graph neural network model》 中被提出，它用于处理图数据并扩展了现有的神经网络。

   GNN 的目标是：对于每个节点$v\in \mathcal{V}$$ v\in \mathcal V $ ，学习一个状态嵌入 state embedding 向量${\overrightarrow{\mathbf{h}}}_v\in {\mathbb{R}}^s$$ \mathbf{\vec h}_v\in \mathbb R^s $ ，其中包含节点的输入特征以及邻域信息。 状态 embedding 进一步地可以用于产生节点$v$$ v $ 的输出向量${\overrightarrow{\mathbf{o}}}_v\in {\mathbb{R}}^{d_o}$$ \mathbf{\vec o}_v\in \mathbb R^{d_o} $ ，如节点的 label 。其中$s$$ s $ 为 embedding 维度，$d_o$$ d_o $ 为输出向量维度。

2. GNN 定义了两个函数：

   • 定义$f(\cdot )$$ f(\cdot) $ 为一个可学习的函数，称作局部转移函数 local transition function 。它在所有节点之间共享，并根据每个节点的输入特征和邻域来更新节点状态向量。
   • 定义$g(\cdot )$$ g(\cdot) $ 为一个可学习的函数，称作局部输出函数 local output function 。它也在所有节点之间共享，并根据每个节点的状态向量来计算节点输出。

   其中函数$f(\cdot )$$ f(\cdot) $ 和$g(\cdot )$$ g(\cdot) $ 可以解释为前馈神经网络。

   根据这两个函数，则GNN 的更新方程为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_v=f({\overrightarrow{\mathbf{x}}}_v^{\mathcal{V}},\{{\overrightarrow{\mathbf{x}}}_{u,v}^{\mathcal{E}},(u,v)\in \mathcal{E}\},\{{\overrightarrow{\mathbf{x}}}_u^{\mathcal{V}},u\in {\mathcal{N}}_v\},\{{\overrightarrow{\mathbf{h}}}_u,u\in {\mathcal{N}}_v\})\\ {\overrightarrow{\mathbf{o}}}_v=g({\overrightarrow{\mathbf{h}}}_v,{\overrightarrow{\mathbf{x}}}_v^{\mathcal{V}})\end{array}$$

   其中：

   • ${\overrightarrow{\mathbf{x}}}_v^{\mathcal{V}}$$ \mathbf{\vec x}_v^{\mathcal V} $ 为节点$v$$ v $ 的输入特征，${\overrightarrow{\mathbf{x}}}_{u,v}^{\mathcal{E}}$$ \mathbf{\vec x}_{u,v}^\mathcal E $ 为边$(u,v)$$ (u,v) $ 的输入特征。
   • $\{{\overrightarrow{\mathbf{x}}}_{u,v}^{\mathcal{E}},(u,v)\in \mathcal{E}\}$$ \left\{\mathbf{\vec x}_{u,v}^{\mathcal E},(u,v)\in \mathcal E\right\} $ 为节点$v$$ v $ 所有边的输入特征。
   • $\{{\overrightarrow{\mathbf{x}}}_u^{\mathcal{V}},u\in {\mathcal{N}}_v\}$$ \left\{\mathbf{\vec x}_u^\mathcal V,u\in \mathcal N_v\right\} $ 为节点$v$$ v $ 所有邻域节点的特征，${\mathcal{N}}_v$$ \mathcal N_v $ 为节点邻域集合。
   • $\{{\overrightarrow{\mathbf{h}}}_u,u\in {\mathcal{N}}_v\}$$ \left\{\mathbf{\vec h}_u,u\in \mathcal N_v\right\} $ 为节点$v$$ v $ 所有邻域节点的状态向量。

3. 令$\mathbf{H}\in {\mathbb{R}}^{N\times s}$$ \mathbf H\in \mathbb R^{N\times s} $ 为所有节点的状态向量组成的矩阵，称作状态矩阵；令$\mathbf{O}\in {\mathbb{R}}^{N\times d_o}$$ \mathbf O\in \mathbb R^{N\times d_o} $ 为所有节点的输出向量组成的矩阵，称作输出矩阵；令$\mathbf{X}\in {\mathbb{R}}^{N\times d_a}$$ \mathbf X\in \mathbb R^{N\times d_a} $ 为所有特征向量（包含边的特征、邻域特征）组成的矩阵，称作特征矩阵；令${\mathbf{X}}_V$$ \mathbf X_V $ 为所有节点的特征向量组成的矩阵，称作节点特征矩阵。其中$N$$ N $ 为节点数量。则上式转化为：

   $$\mathbf{H}=F(\mathbf{H},\mathbf{X}),\mathbf{O}=G(\mathbf{H},{\mathbf{X}}_N)$$

   其中：

   • $F(\cdot ,\cdot )$$ F(\cdot,\cdot ) $ 被称作全局转移函数 global transition function，它是考虑图上所有节点的$f(\cdot )$$ f(\cdot) $ 函数而来。
   • $G(\cdot ,\cdot )$$ G(\cdot,\cdot) $ 被称作全局输出函数 global output function ，它是考虑图上所有节点的$g(\cdot )$$ g(\cdot) $ 函数而来。

4. 实际上$\mathbf{H}$$ \mathbf H $ 是公式$\mathbf{H}=F(\mathbf{H},\mathbf{X})$$ \mathbf H = F(\mathbf H, \mathbf X) $ 中的不动点，并且仅当$F(\cdot ,\cdot )$$ F(\cdot,\cdot ) $ 是一个收缩映射contraction map 才有定义。

   基于 Banach 不动点理论，GNN 使用以下经典的迭代方案来计算状态矩阵：

   $${\mathbf{H}}^{(t+1)}=F({\mathbf{H}}^{(t)},\mathbf{X})$$

   其中${\mathbf{H}}^{(t)}$$ \mathbf H^{(t)} $ 表示$\mathbf{H}$$ \mathbf H $ 的第$t$$ t $ 次迭代。对于任何初始化值${\mathbf{H}}^{(0)}$$ \mathbf H^{(0)} $ ，该迭代方程以指数形式快速收敛。

5. 当得到 GNN 框架时，下一个问题是如何学习$f(\cdot ),g(\cdot )$$ f(\cdot), g(\cdot) $ 的参数。

   基于监督信息，损失函数可以为：

   $$\mathcal{L}=\sum _{i=1}^{N_l}l({\overrightarrow{\mathbf{t}}}_i,{\overrightarrow{\mathbf{o}}}_i)$$

   其中：

   • $N_l$$ N_l $ 为带标签的节点数量。
   • ${\overrightarrow{\mathbf{t}}}_i$$ \mathbf{\vec t}_i $ 为节点$v_i$$ v_i $ 的标签经过one-hot之后的向量。
   • ${\overrightarrow{\mathbf{o}}}_i$$ \mathbf{\vec o}_i $ 为节点$v_i$$ v_i $ 的输出向量。
   • $l(\cdot ,\cdot )$$ l(\cdot,\cdot) $ 为单个样本的损失。

   然后我们基于梯度下降法按照以下步骤来进行学习：

   • 通过公式${\overrightarrow{\mathbf{h}}}_v=f(\cdot )$$ \mathbf{\vec h}_v =f(\cdot) $ 迭代更新$T$$ T $ 轮从而得到近似的不动点：${\mathbf{H}}^{(T)}\simeq \mathbf{H}$$ \mathbf H^{(T)} \simeq \mathbf H $ 。

   • 然后从损失函数中计算权重$\mathbf{W}$$ \mathbf W $ 的梯度${\mathrm{\nabla }}_{\mathbf{W}}\mathcal{L}$$ \nabla_{\mathbf W} \mathcal L $ 。

     $\mathbf{W}$$ \mathbf W $ 是$f(\cdot )$$ f(\cdot) $ 和$g(\cdot )$$ g(\cdot) $ 的参数。

   • 根据梯度来更新权重$\mathbf{W}$$ \mathbf W $ ：$\mathbf{W}\leftarrow \mathbf{W}-\eta {\mathrm{\nabla }}_{\mathbf{W}}\mathcal{L}$$ \mathbf W \leftarrow \mathbf W -\eta \nabla_{\mathbf W} \mathcal L $ 。

6. 尽管实验结果表明 GNN 是用于对图结构数据建模的强大工具，但是原始GNN 仍然存在一些局限性：

   • 首先，迭代不动点从而更新节点状态的效率太低。如果放松不动点的假设，则我们可以设计一个多层 GNN 来获得节点及其邻域的 stable representation 。
   • 其次，GNN 在迭代 不动点过程中使用相同的参数。但是，流行的神经网络在不同的 layer 使用不同的参数，这是一种层次 hierarchical 特征提取方法。
   • 第三，边上存在一些信息特征，这些特征无法在原始 GNN 中有效建模。例如，异质图中包含不同类型的边，那么不同类型边的消息传播应该有所不同。
   • 最后，如果我们专注于节点的representation而不是图的representation，则不动点并不合适。因为不动点的representation 分布过于平滑，使得难以很好地区分不同的节点。

2.1.2 GNN 变体

1. GNN 的变体有三类：基于图类型的变体 Graph Types、基于传播步骤的变体 Propagation Step、基于训练方法的变体 Training Methods。下图概括了这三类变体。

   

a. Graph Types

1. 原始 GNN 中，输入图由带标签信息的节点以及无向边组成，这是最简单的图。下面我们介绍针对不同类型的图进行建模的方法。

2. 有向图：有向边相比无向边可以带来更多的信息。在知识图谱中，边从 head entity 指向 tail entity ，表示 head entity 是 tail entity 的父节点。这表明我们应该区别对待 head entity （父节点）和 tail entity （子结点）。

   DGP （《Rethinking knowledge graph propagation for zero-shot learning》）使用两种权重矩阵${\mathbf{W}}_p,{\mathbf{W}}_c$$ \mathbf W_p,\mathbf W_c $ 来获得更精确的结构信息，其传播规则为：

   $${\mathbf{H}}^{(l)}=\sigma \left({\mathbf{D}}_p^{-1}{\mathbf{A}}_p\sigma \left({\mathbf{D}}_c^{-1}{\mathbf{A}}_c{\mathbf{H}}^{(l-1)}{\mathbf{W}}_c\right){\mathbf{W}}_p\right)$$

   其中：

   • ${\mathbf{H}}^{(t)}$$ \mathbf H^{(t)} $ 为第$l$$ l $ 层的representation 矩阵。

   • $\sigma (\cdot )$$ \sigma(\cdot) $ 为sigmoid 函数。

   • ${\mathbf{D}}_p^{-1}{\mathbf{A}}_p$$ \mathbf D_p^{-1}\mathbf A_p $ 为父节点的归一化邻接矩阵，${\mathbf{D}}_c^{-1}{\mathbf{A}}_c$$ \mathbf D_c^{-1} \mathbf A_c $ 为子结点的归一化邻接矩阵。

     其中${\mathbf{A}}_p$$ \mathbf A_p $ 表示节点和其父节点的邻接矩阵，${\mathbf{A}}_c$$ \mathbf A_c $ 为节点和其子结点的邻接矩阵，且满足${\mathbf{A}}_p={\mathbf{A}}_c^{\mathrm{\top }}$$ \mathbf A_p = \mathbf A_c^\top $ 。

   • ${\mathbf{W}}_p$$ \mathbf W_p $ 为父节点的参数矩阵，${\mathbf{W}}_c$$ \mathbf W_c $ 为子结点的参数矩阵。

3. 异质图：异质图存在多种类型的节点。

   • 处理异质图最简单的方法是将节点类型转换为 one-hot 向量，然后拼接这个 one-hot 向量到节点原始特征向量之后作为节点新的特征向量。
   • 此外，GraphInception 将 metapath 的概念引入到异质图传播过程中。通过 metapath，我们可以根据邻居节点的类型、邻居节点距当前节点的距离来对邻居节点进行分组。对于每个分组，GraphInception 将其视为同质图中的子图进行传播，并将不同分组的传播结果拼接起来作为邻域节点集合的 representation 。
   • 最近，heterogeneous graph attention network: HAT 提出利用node-level 注意力和 semantic-level 注意力来同时考虑节点重要性和 meta-path 重要性。

4. 边信息：在图的另一类变体中，每条边都带有边信息，如边的权重或类型。对于带边信息的图，有两种处理方式：

   • 首先，可以将图转换为二部图，其中原始边变成节点（称作 edge node），并且一条原始边被拆分为两条新边。这意味着 edge node 分别和原始边的开始节点、结束节点都存在连接。

   • 其次，我们可以对不同类型的边上的传播使用不同的权重矩阵。在 G2S（《Graph-to-sequence learning using gated graph neural networks》） 中，encoder 使用如下的聚合函数：

     $${\overrightarrow{\mathbf{h}}}_v^{(l)}=\rho (\frac{1}{|{\mathcal{N}}_v|}\sum _{u\in {\mathcal{N}}_v}{\mathbf{W}}_r({\overrightarrow{\mathbf{r}}}_v^{(l)}\odot {\overrightarrow{\mathbf{h}}}_u^{(l-1)})+{\overrightarrow{\mathbf{b}}}_r)$$

     其中：

     • ${\overrightarrow{\mathbf{h}}}_v^{(l)}$$ \mathbf{\vec h}_v^{(l)} $ 为节点$v$$ v $ 在第$l$$ l $ 层的representation 向量。
     • $\rho (\cdot )$$ \rho(\cdot) $ 为非线性激活函数。
     • ${\mathcal{N}}_v$$ \mathcal N_v $ 为节点$v$$ v $ 的邻域。
     • ${\mathbf{W}}_r,{\overrightarrow{\mathbf{b}}}_r$$ \mathbf W_r, \mathbf{\vec b}_r $ 为不同边类型的权重（从而考虑边的类型信息）。
     • ${\overrightarrow{\mathbf{r}}}_v^{(l)}$$ \mathbf{\vec r}_v^{(l)} $ 为 reset gate 。

     当边的类型非常多时，R-GCN 引入了两种正则化来减少关系建模的参数数量：基分解 basis-decomposition、块对角分解 block-diagonal-decomposition 。

     • 对于基分解，每个${\mathbf{W}}_r$$ \mathbf W_r $ 定义为：${\mathbf{W}}_r=\sum _{i=1}^B{a}_{r,b}{\mathbf{V}}_b$$ \mathbf W_r = \sum_{i=1}^B a_{r,b} \mathbf V_b $ 。

       其中每个${\mathbf{W}}_r$$ \mathbf W_r $ 是基转换权重 basis transformation${\mathbf{V}}_b$$ \mathbf V_b $ 的线性组合，组合的系数为$a_{r,b}$$ a_{r,b} $ 。

     • 对于块对角分解，R-GCN 通过一组低维矩阵直接求和来定义每个${\mathbf{W}}_r$$ \mathbf W_r $ 。和基分解相比，块对角分解需要更多的参数。

5. 动态图：动态图具有静态图结构和动态输入信号。

   • 为捕获这两种信息，DCRNN 和 STGCN 首先通过 GNN 收集空间信息spatial information，然后将输出馈送到序列模型（如 sequence-to-sequence 或者 CNN ) 从而捕获时序信息 temporal information。
   • 不同的是，Structure-RNN 和 ST-GCN 同时收集空间信息和时序信息。它们通过时序连接 temporal connnection 扩展了静态图结构，因此可以在扩展图上应用传统的 GNN 。

b. Propagation Step

1. 在模型中，propagation step 和 output step 对于获取节点（或边）的 representation 至关重要。对于output step 而言，通常都采用和原始 GNN 相同的、简单的前馈神经网络。但是对于 propagation step，已经有很多种不同于原始 GNN 的修改，如下表所示。

   这些变体利用不同的聚合器 aggregator 从每个节点的邻域聚合消息，并使用不同的更新器 updater 来更新节点的 hidden state 。

   

2. Convolution：近期卷积被应用到图领域，其中主要分为谱域卷积 spectral convolution 和空间卷积 spatial convolution 。

   谱域卷积使用图的谱域表示：

   • Spectral Network：

     论文 《Spectral networks and locally connected networks on graphs》 提出了谱域网络 spectral network 。它通过对图的拉普拉斯算子执行特征分解eigendecomposition ，从而在傅里叶域 Fourier domain 定义卷积运算。

     定义图卷积算子${\ast }_G$$ *_G $ 为：

     $${\overrightarrow{\mathbf{x}}}_1{\ast }_G{\overrightarrow{\mathbf{x}}}_2=\mathbf{U}(\left({\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_1\right)\odot \left({\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_2\right))$$

     其中：

     • ${\overrightarrow{\mathbf{x}}}_1,{\overrightarrow{\mathbf{x}}}_2\in {\mathbb{R}}^N$$ \mathbf{\vec x}_1,\mathbf{\vec x}_2\in \mathbb R^N $ 为定义在图$G$$ G $ 所有节点上的两个信号。每个信号在每个节点上都是一个标量（如，特征向量的某个维度）。
     • $\mathbf{U}$$ \mathbf U $ 为图拉普拉斯矩阵$\mathbf{L}$$ \mathbf L $ 的特征向量 eigenvector 组成的矩阵 。
     • 图拉普拉斯矩阵$\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}$$ \mathbf D $ 为度矩阵。

     定义谱域卷积核为$\mathbf{K}=\text{diag}(g({\lambda }_1),\cdots ,g({\lambda }_N))\in {\mathbb{R}}^{N\times N}$$ \mathbf K = \text{diag}(g(\lambda_1),\cdots,g(\lambda_N))\in \mathbb R^{N\times N} $ 为一个对角矩阵，其对角线元素为拉普拉斯矩阵$\mathbf{L}$$ \mathbf L $ 的特征值 eigenvalue${\lambda }_i$$ \lambda_i $ 的函数$g({\lambda }_i)$$ g(\lambda_i) $ 。其中$g({\lambda }_i)$$ g(\lambda_i) $ 包含可学习的参数。

     因此作用在输入信号$\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^N$$ \mathbf{\vec x}\in \mathbb R^N $ 的卷积运算为：

     $${\overrightarrow{\mathbf{x}}}^{\prime }=\mathbf{U}\mathbf{K}{\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}$$

     其中${\overrightarrow{\mathbf{x}}}^{\prime }$$ \mathbf{\vec x}^\prime $ 为输出信号。

     这种卷积操作的计算复杂度太高，并且得到的滤波器是非空间局部化的 non-spatially localized 。因此，《Deep convolutional networks on graph-structured data》 试图通过引入具有平滑系数的参数来使得谱域滤波器在空域是局部化的。

   • ChebNet：

     《Wavelets on graphs via spectral graph theory》 提出$g({\lambda }_i)$$ g(\lambda_i) $ 可以通过一个截断的$K$$ K $ 阶切比雪夫多项式来近似。则有：

     $${\overrightarrow{\mathbf{x}}}^{\prime }=\mathbf{U}\mathbf{K}{\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}\simeq \sum _{k=0}^K{\theta }_k{\mathbf{T}}_k(\tilde{\mathbf{L}})\overrightarrow{\mathbf{x}}=\sum _{k=0}^K{\theta }_k{\widetilde{\overrightarrow{\mathbf{x}}}}_k$$

     其中：

     • $\tilde{\mathbf{L}}=\frac{2}{{\lambda }_{max}}\mathbf{L}-\mathbf{I}$$ \tilde{\mathbf L} = \frac{2}{\lambda_\max}\mathbf L - \mathbf I $ ，${\lambda }_{max}$$ \lambda_\max $ 为$\mathbf{L}$$ \mathbf L $ 的最大特征值。
     • ${\theta }_k$$ \theta_k $ 为$k$$ k $ 阶切比雪夫多项式的系数。
     • ${\mathbf{T}}_k(x)$$ \mathbf T_k(x) $ 为$k$$ k $ 阶切比雪夫多项式，${\widetilde{\overrightarrow{\mathbf{x}}}}_k={\mathcal{T}}_k(\tilde{\mathbf{L}})\overrightarrow{\mathbf{x}}$$ \tilde{\mathbf{\vec x}}_k = \mathcal T_k(\tilde{\mathbf L}) \mathbf{\vec x} $ 。

     根据切比雪夫多项式的递归定义，有：

     $$\begin{array}{c}{\mathcal{T}}_k(x)=2x{\mathcal{T}}_{k-1}(x)-{\mathcal{T}}_{k-2}(x)\\ {\mathcal{T}}_0(x)=1,{\mathcal{T}}_1(x)=x\end{array}$$

     因此有：

     $$\begin{array}{c}{\widetilde{\overrightarrow{\mathbf{x}}}}_k=2\tilde{\mathbf{L}}{\widetilde{\overrightarrow{\mathbf{x}}}}_{k-1}-{\widetilde{\overrightarrow{\mathbf{x}}}}_{k-2}\\ {\widetilde{\overrightarrow{\mathbf{x}}}}_0=\overrightarrow{\mathbf{x}},{\widetilde{\overrightarrow{\mathbf{x}}}}_1=\tilde{\mathbf{L}}\overrightarrow{\mathbf{x}}\end{array}$$

     可以看出该卷积操作是拉普拉斯矩阵的$K$$ K $ 阶多项式，因此它是 K 阶局部化的K-localized 。

     《Convolutional neural networks on graphs with fast localized spectral filtering》 提出了 ChebNet，它利用这种 K-localized 卷积运算来定义卷积神经网络，从而避免计算拉普拉斯矩阵的特征向量 eigenvector 。

   • GCN：

     《Semi-supervised classification with graph convolutional networks》 通过限制 K=1，从而缓解在节点 degree 分布范围非常广的图中局部邻域结构上的过拟合问题。进一步地它假设${\lambda }_{max}=2$$ \lambda_\max = 2 $ ，因此卷积操作简化为：

     $${\overrightarrow{\mathbf{x}}}^{\prime }=\mathbf{U}\mathbf{K}{\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}\simeq \sum _{k=0}^1{\theta }_k{\widetilde{\overrightarrow{\mathbf{x}}}}_k={\theta }_0\overrightarrow{\mathbf{x}}+{\theta }_1(\mathbf{L}-\mathbf{I})\overrightarrow{\mathbf{x}}={\theta }_0\overrightarrow{\mathbf{x}}-{\theta }_1{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}\overrightarrow{\mathbf{x}}$$

     其中包含两个参数${\theta }_0,{\theta }_1$$ \theta_0,\theta_1 $ 。

     为减少参数数量并令$\theta ={\theta }_0=-{\theta }_1$$ \theta = \theta_0 = -\theta_1 $ ，则有：

     $${\overrightarrow{\mathbf{x}}}^{\prime }=\mathbf{U}\mathbf{K}{\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}\simeq \theta (\mathbf{I}+{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2})\overrightarrow{\mathbf{x}}$$

     注意，堆叠该卷积算子可能会导致数值不稳定性以及梯度消失、梯度爆炸。因此，GCN 引入 renormalization 技巧：

     $$\mathbf{I}+{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}\to {\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}$$

     其中$\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$$ \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}$$ \tilde {\mathbf D} = \text{diag}(\tilde D_{1},\cdots,\tilde D_N), \tilde D_i = \sum_j \tilde A_{i,j} $ 。

     最终，GCN 将上述卷积算子推广到信号$\mathbf{X}\in {\mathbb{R}}^{N\times C}$$ \mathbf X \in \mathbb R^{N\times C} $ ，其中包含$C$$ C $ 的输入通道（即$C$$ C $ 个输入信号），以及$F$$ F $ 个滤波器（即$F$$ F $ 个输出信号）：

     $$\mathbf{Z}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}\mathbf{X}\mathbf{\Theta }$$

     其中：$\mathbf{Z}\in {\mathbb{R}}^{N\times F}$$ \mathbf Z\in \mathbb R^{N\times F} $ 为卷积输出矩阵，$\mathbf{\Theta }\in {\mathbb{R}}^{C\times F}$$ \mathbf\Theta\in \mathbb R^{C\times F} $ 为滤波器参数矩阵。

     这里的输入通道数量$C$$ C $ 就是节点的特征向量的维度。

   • 上述所有方法均使用原始图结构来表明节点之间的关系，然而不同节点之间可能存在隐式关系。为此， 《Adaptive graph convolutional neural networks》 提出了 Adaptive Graph Convolution Network:AGCN 来学习潜在关系。

     AGCN 学习一个残差 residual 图的拉普拉斯算子，并将该残差图的拉普拉斯算子添加到原始的图拉普拉斯算子中。结果在多个图数据集中证明了 AGCN的有效性。

   • 另外 《Bayesian semi-supervised learning with graph gaussian processes》 提出了一种基于高斯过程的贝叶斯方法 Gaussian process-based Bayesian approach:GGP 来解决半监督学习问题。它展示了 GGP 和谱域卷积方法之间的相似之处，这可能会从另一个角度为我们提供一些洞察。

   但是，上述所有谱域方法中，学习的滤波器都取决于拉普拉斯矩阵的特征根 eigenbasis ，而拉普拉斯特征根取决于图结构。即，在特定结构的图上训练的模型无法直接应用于具有不同结构的其它图上。

   空域卷积直接在图上定义卷积，并在空间上相邻的邻域上进行计算。空域方法的主要挑战是：为具有不同大小邻域的节点定义卷积运算，并保持CNN 的局部不变性。

   • Neural FPs：

     《Convolutional networks on graphs for learning molecular fingerprints》 对不同 degree 的节点使用不同的权重矩阵：

     $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_v={\overrightarrow{\mathbf{h}}}_v^{(l-1)}+\sum _{u\in {\mathcal{N}}_v}{\overrightarrow{\mathbf{h}}}_u^{(l-1)}\\ {\overrightarrow{\mathbf{h}}}_v^{(l)}=\sigma \left({\overrightarrow{\mathbf{x}}}_v{\mathbf{W}}^{(l,|{\mathcal{N}}_v|)}\right)\end{array}$$

     其中${\mathbf{W}}^{(l,|{\mathcal{N}}_v|)}$$ \mathbf W^{(l,|\mathcal N_v|)} $ 为第$l$$ l $ 层对应于degree 为$|{\mathcal{N}}_v|$$ |\mathcal N_v| $ 的节点的权重矩阵。

     该方法的主要缺点是无法应用于节点 degree 范围很广的大型图。

   • DCNN：

     《Diffusion-convolutional neural networks》 提出 diffusion-convolutional neural networks: DCNN ，它利用转移矩阵来定义节点邻域。对于节点分类问题，有：

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

     其中：

     • $\mathbf{X}\in {\mathbb{R}}^{N\times F}$$ \mathbf X\in \mathbb R^{N\times F} $ 为输入特征矩阵，F 为节点特征向量的维度。
     • ${\mathbf{P}}^{(\ast )}\in {\mathbb{R}}^{N\times K\times N}$$ \mathbf P^{(*)}\in \mathbb R^{N\times K\times N} $ 包含了转移矩阵$\mathbf{P}$$ \mathbf P $ 的一组幂次：$\{\mathbf{P},\cdots ,{\mathbf{P}}^K\}$$ \left\{\mathbf P, \cdots,\mathbf P^K\right\} $ 。$\mathbf{P}={\mathbf{D}}^{-1}\mathbf{A}$$ \mathbf P= \mathbf D^{-1}\mathbf A $ 是归一化的转移概率矩阵，$P_{i,j}$$ P_{i,j} $ 表示从节点$v_i$$ v_i $ 经过一步转移到节点$v_j$$ v_j $ 的概率。因此${\mathbf{P}}^k$$ \mathbf P^k $ 中的${\left({\mathbf{P}}^k\right)}_{i,j}$$ \left(\mathbf P^k\right)_{i,j} $ 表示节点$v_i$$ v_i $ 经过$k$$ k $ 步转移到节点$v_j$$ v_j $ 的概率。
     • ${\mathbf{W}}^{(c)}\in {\mathbb{R}}^{K\times F}$$ \mathbf W^{(c)}\in \mathbb R^{K\times F} $ 为权重矩阵。
     • $\mathbf{H}\in {\mathbb{R}}^{N\times K\times F}$$ \mathbf H\in \mathbb R^{N\times K\times F} $ 为图上每个节点的 diffusion representation 。
     • $\sigma (\cdot )$$ \sigma(\cdot) $ 为非线性激活函数，$\odot$$ \odot $ 为逐元素乘积。

     对于图分类任务，DCNN 简单地将节点的 representation 取平均：

     $$\mathbf{H}=f({\mathbf{W}}^{(c)}\odot \left({\overrightarrow{\mathbf{1}}}^{\mathrm{\top }}{\mathbf{P}}^{\ast }\mathbf{X}/N\right))$$

     其中${\overrightarrow{\mathbf{1}}}^{\mathrm{\top }}=(\underset{N}{\underbrace{1,1,\cdots ,1}}{)}^{\mathrm{\top }}$$ \mathbf{\vec 1}^\top = (\underbrace{1,1,\cdots,1}_N)^\top $ 为全 1 的向量。

     DCNN 也可以用于边分类任务，只需要将边转换为节点并调整邻接矩阵即可。

   • DGCN：

     《Dual graph convolutional networks for graph-based semi-supervised classification》 提出了 dual graph convolutional network:DGCN 来同时考虑图的局部一致性和全局一致性。它使用两个卷积网络来捕获局部一致性和全局一致性，并采用无监督损失来集成 ensemble 它们。

     • 第一个卷积网络和 GCN 相同：$\mathbf{Z}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}\mathbf{X}\mathbf{\Theta }$$ \mathbf Z = \tilde{\mathbf D}^{-1/2}\tilde{\mathbf A} \tilde{\mathbf D}^{-1/2} \mathbf X \mathbf\Theta $ 。

     • 第二个卷积网络使用 positive pointwise mutual information:PPMI 矩阵代替邻接矩阵：

       $${\mathbf{H}}^{\prime }=\rho \left({\mathbf{D}}_P^{-1/2}{\mathbf{X}}_P{\mathbf{D}}_P^{-1/2}\mathbf{H}{\mathbf{\Theta }}^{\prime }\right)$$

       其中：${\mathbf{X}}_P$$ \mathbf X_P $ 为 PPMI 矩阵，${\mathbf{D}}_P$$ \mathbf D_P $ 为${\mathbf{X}}_P$$ \mathbf X_P $ 的 degree 矩阵。

   • PATCHY-SAN：

     PATCHY-SAN 模型为每个节点提取并归一化邻域，其中邻域刚好包含$k$$ k $ 个邻居节点。然后，归一化的邻域作为常规卷积运算的感受野 receptive field。

   • LGCN：

     LGCN 利用 CNN 作为聚合器。它对节点的邻域矩阵进行最大池化，并获取 top-k 个特征，然后应用一维卷积来计算 hidden representation。

   • MoNet：

     MoNet 推广了前面的几种技术。在流形 manifold 上的Geodesic CNN:GCNN 和 Anisotropic CNN:ACNN 、在图上的 GCN,DCNN 都可以视为 MoNet 的特例。

   • GraphSAGE：

     GraphSAGE 提出了一个通用的 inductive 框架，它通过对节点的局部邻域特征进行采样和聚合来生成节点 embedding ：

     $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{(l)}={\text{AGG}}^{(l)}\left(\{{\overrightarrow{\mathbf{h}}}_u^{(l-1)},\mathrm{\forall }u\in {\mathcal{N}}_v\}\right)\\ {\overrightarrow{\mathbf{h}}}_v^{(l)}=\sigma \left({\mathbf{W}}^{(l)}[{\overrightarrow{\mathbf{h}}}_v^{(l-1)}||{\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{(l)}]\right)\end{array}$$

     其中$||$$ || $ 表示向量拼接。

     但是，GraphSAGE 并没有使用节点邻域中的所有节点来计算${\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{(l)}$$ \mathbf{\vec h}^{(l)}_{\mathcal N_v} $ ，而是通过均匀随机采样来获取固定大小的采样邻域。另外，GraphSAGE 采用了三种聚合函数：

     • 均值聚合：

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

       均值聚合和其它两种聚合不同，因为它并没有将${\overrightarrow{\mathbf{h}}}_v^{(l-1)}$$ \mathbf{\vec h}_v^{(l-1)} $ 和${\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{(l)}$$ \mathbf{\vec h}_{\mathcal N_v}^{(l)} $ 进行拼接的操作。它可以视为 skip connection 的一种形式，并可以实现更好的性能。

     • LSTM 聚合：AGG 使用表达能力很强的 LSTM 网络。但是，LSTM 处理序列数据，因此并不是排列不变的 permutation invariant 。 LSTM 通过对节点邻域随机排序从而应用于无序的邻域集合。

     • 池化聚合：AGG 使用最大池化：

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

       .

3. Gate：有一些工作试图在传播step 中引入门控机制（类似于 GRU/LSTM），从而减少之前 GNN 模型中的缺陷，并改善信息在整个图结构中的 long-term 传播。

   • GGNN：

     《Gated graph sequence neural networks》 提出了 gated graph neural network:GGNN ，它在传播阶段使用 Gate Recurrent Units:GRU ，展开 unroll 固定的 T 个递归步并通过 backpropagation through time:BPTT 计算梯度。

     具体而言，传播模型的基本递归 basic recurrence 公式为：

     $$\begin{array}{c}{\overrightarrow{\mathbf{a}}}_v^{(t)}={\mathbf{A}}_v^{\mathrm{\top }}{[{\overrightarrow{\mathbf{h}}}_1^{(t-1)},\cdots ,{\overrightarrow{\mathbf{h}}}_N^{(t-1)}]}^{\mathrm{\top }}+\overrightarrow{\mathbf{b}}\\ {\overrightarrow{\mathbf{z}}}_v^{(t)}=\sigma ({\mathbf{W}}^{(z)}{\overrightarrow{\mathbf{a}}}_v^{(t)}+{\mathbf{U}}^{(z)}{\overrightarrow{\mathbf{h}}}_v^{(t-1)})\\ {\overrightarrow{\mathbf{r}}}_v^{(t)}=\sigma ({\mathbf{W}}^{(r)}{\overrightarrow{\mathbf{a}}}_v^{(t)}+{\mathbf{U}}^{(r)}{\overrightarrow{\mathbf{h}}}_v^{(t-1)})\\ \stackrel{~}{{\overrightarrow{\mathbf{h}}}_v^{(t)}}=\tanh (\mathbf{W}{\overrightarrow{\mathbf{a}}}_v^{(t)}+\mathbf{U}({\overrightarrow{\mathbf{r}}}_v^{(t)}\odot {\overrightarrow{\mathbf{h}}}_v^{(t-1)}))\\ {\overrightarrow{\mathbf{h}}}_v^{(t)}=(1-{\overrightarrow{\mathbf{z}}}_v^{(t)})\odot {\overrightarrow{\mathbf{h}}}_v^{(t-1)}+{\overrightarrow{\mathbf{z}}}_v^{(t)}\odot \stackrel{~}{{\overrightarrow{\mathbf{h}}}_v^{(t)}}\end{array}$$

     其中：${\overrightarrow{\mathbf{a}}}_v^{(t)}$$ \mathbf{\vec a}_v^{(t)} $ 收集了节点$v$$ v $ 的邻域信息，${\overrightarrow{\mathbf{z}}}_v^{(t)}$$ \mathbf{\vec z}_v^{(t)} $ 为更新门update gate，${\overrightarrow{\mathbf{r}}}_v^{(t)}$$ \mathbf{\vec r}_v^{(t)} $ 为恢复门 reset gate 。

     节点$v$$ v $ 首先聚合来自其邻域的消息，其中${\mathbf{A}}_v$$ \mathbf A_v $ 表示邻接矩阵$\mathbf{A}$$ \mathbf A $ 的子矩阵，表示节点$v$$ v $ 和它邻居的连接。类似于 GRU 的更新函数结合了来自其它节点的信息和上一个时间步的信息，从而更新每个节点的 hidden state。

   • Tree-LSTM：

     在基于树或图的传播过程中，LSTM 也以 GRU 相似的方式使用。《Improved semantic representations from tree-structured long short-term memory networks》 提出基于 LSTM 的两个扩展：Child-Sum Tree-LSTM 和 N-ary Tree-LSTM 。

     类似于标准的 LSTM 单元，每个 Tree-LSTM 单元（由$v$$ v $ 索引）都包含输入门 input gate${\overrightarrow{\mathbf{i}}}_v$$ \mathbf{\vec i}_v $ 、输出门 output gate${\overrightarrow{\mathbf{o}}}_v$$ \mathbf{\vec o}_v $ 、memmory cell${\overrightarrow{\mathbf{c}}}_v$$ \mathbf{\vec c}_v $ 以及 hidden state${\overrightarrow{\mathbf{h}}}_v$$ \mathbf{\vec h}_v $ 。但是，Tree-LSTM 单元对于每个 child$k$$ k $ 包含一个遗忘门 forget gate${\overrightarrow{\mathbf{f}}}_{v,k}$$ \mathbf{\vec f}_{v,k} $ ，而不是单个遗忘门，这使得单元可以有选择地融合每个 child 的信息。

     • Child-Sum Tree-LSTM 递归方程如下：

       $$\begin{array}{c}\stackrel{~}{{\overrightarrow{\mathbf{h}}}_v^{(t-1)}}=\sum _{k\in {\mathcal{N}}_v}{\overrightarrow{\mathbf{h}}}_k^{(t-1)}\\ {\overrightarrow{\mathbf{i}}}_v^{(t)}=\sigma ({\mathbf{W}}^{(i)}{\overrightarrow{\mathbf{x}}}_v^{(t)}+{\mathbf{U}}^{(i)}\stackrel{~}{{\overrightarrow{\mathbf{h}}}_v^{(t-1)}}+{\overrightarrow{\mathbf{b}}}^{(i)})\\ {\overrightarrow{\mathbf{f}}}_{v,k}^{(i)}=\sigma ({\mathbf{W}}^{(f)}{\overrightarrow{\mathbf{x}}}_v^{(t)}+{\mathbf{U}}^{(f)}{\overrightarrow{\mathbf{h}}}_k^{(t-1)}+{\overrightarrow{\mathbf{b}}}^{(f)})\\ {\overrightarrow{\mathbf{o}}}_v^{(t)}=\sigma ({\mathbf{W}}^{(o)}{\overrightarrow{\mathbf{x}}}_v^{(t)}+{\mathbf{U}}^{(o)}\stackrel{~}{{\overrightarrow{\mathbf{h}}}_v^{(t-1)}}+{\overrightarrow{\mathbf{b}}}^{(o)})\\ {\overrightarrow{\mathbf{u}}}_v^{(t)}=\tanh ({\mathbf{W}}^{(u)}{\overrightarrow{\mathbf{x}}}_v^{(t)}+{\mathbf{U}}^{(u)}\stackrel{~}{{\overrightarrow{\mathbf{h}}}_v^{(t-1)}}+{\overrightarrow{\mathbf{b}}}^{(u)})\\ {\overrightarrow{\mathbf{c}}}_v^{(t)}={\overrightarrow{\mathbf{i}}}_v^{(t)}\odot {\overrightarrow{\mathbf{u}}}_v^{(t)}+\sum _{k\in {\mathcal{N}}_v}{\overrightarrow{\mathbf{f}}}_{v,k}^{(t)}\odot {\overrightarrow{\mathbf{c}}}_k^{(t-1)}\\ {\overrightarrow{\mathbf{h}}}_v^{(t)}={\overrightarrow{\mathbf{o}}}_v^{(t)}\odot \tanh \left({\overrightarrow{\mathbf{c}}}_v^{(t)}\right)\end{array}$$

       其中${\overrightarrow{\mathbf{x}}}_v^{(t)}$$ \mathbf{\vec x}_v^{(t)} $ 为标准 LSTM 中时刻$t$$ t $ 的输入向量。

       这里的 LSTM 作用的是节点的状态序列，而 GraphSAGE 中的 LSTM 作用的是节点的邻域。

     • 如果树的分支因子最多为$K$$ K $ ，并且节点的所有子节点均已排序，即它们可以从 1,...,K 进行索引，则可以使用 N-ary Tree-LSTM。

       对于节点$v$$ v $ ，${\overrightarrow{\mathbf{h}}}_{v,k}^{(t)},{\overrightarrow{\mathbf{c}}}_{v,k}^{(t)}$$ \mathbf{\vec h}_{v,k}^{(t)},\mathbf{\vec c}_{v,k}^{(t)} $ 表示它的第$k$$ k $ 个chid 在时刻$t$$ t $ 的 hidden state 和 memory cell 。N-ary Tree-LSTM 的递归方程如下：

       $$\begin{array}{c}{\overrightarrow{\mathbf{i}}}_v^{(t)}=\sigma ({\mathbf{W}}^{(i)}{\overrightarrow{\mathbf{x}}}_v^{(t)}+\sum _{l=1}^K{\mathbf{U}}_l^{(i)}{\overrightarrow{\mathbf{h}}}_{v,l}^{(t-1)}+{\overrightarrow{\mathbf{b}}}^{(i)})\\ {\overrightarrow{\mathbf{f}}}_{v,k}^{(t)}=\sigma ({\mathbf{W}}^{(f)}{\overrightarrow{\mathbf{x}}}_v^{(t)}+\sum _{l=1}^K{\mathbf{U}}_{k,l}^{(f)}{\overrightarrow{\mathbf{h}}}_{v,l}^{(t-1)}+{\overrightarrow{\mathbf{b}}}^{(f)})\\ {\overrightarrow{\mathbf{o}}}_v^{(t)}=\sigma ({\mathbf{W}}^{(o)}{\overrightarrow{\mathbf{x}}}_v^{(t)}+\sum _{l=1}^K{\mathbf{U}}_l^{(o)}{\overrightarrow{\mathbf{h}}}_{v,l}^{(t-1)}+{\overrightarrow{\mathbf{b}}}^{(o)})\\ {\overrightarrow{\mathbf{u}}}_v^{(t)}=\tanh ({\mathbf{W}}^{(u)}{\overrightarrow{\mathbf{x}}}_v^{(t)}+\sum _{l=1}^K{\mathbf{U}}_l^{(u)}{\overrightarrow{\mathbf{h}}}_{v,l}^{(t-1)}+{\overrightarrow{\mathbf{b}}}^{(u)})\\ {\overrightarrow{\mathbf{c}}}_v^{(t)}={\overrightarrow{\mathbf{i}}}_v^{(t)}\odot {\overrightarrow{\mathbf{u}}}_v^{(t)}+\sum _{l=1}^K{\overrightarrow{\mathbf{f}}}_{v,l}^{(t)}\odot {\overrightarrow{\mathbf{c}}}_{v,l}^{(t-1)}\\ {\overrightarrow{\mathbf{h}}}_v^{(t)}={\overrightarrow{\mathbf{o}}}_v^{(t)}\odot \tanh \left({\overrightarrow{\mathbf{c}}}_v^{(t)}\right)\end{array}$$

       和 Child-Sum Tree-LSTM 相比， N-ary Tree-LSTM 为每个 child$k$$ k $ 引入单独的参数矩阵，使得模型可以学习更多关于每个单元的 child 的细粒度表示。

       这两种类型的 Tree-LSTM 可以轻松地应用于图。

   • Graph LSTM：

     • 《Conversation modeling on reddit using a graph-structured lstm》 中的 graph-structured LSTM 是 N-ary Tree-LSTM 应用于图上的例子。

       但是它是简化版本，因为图中的每个节点最多具有 2 个入边 incoming edge （从它的父亲parent 以及同辈的前驱 sibling predecessor ）。

     • 《Cross-sentence n-ary relation extraction with graph lstms》 基于关系抽取任务提出了 Graph LSTM 的另一种变体。

       图和树之间的主要区别在于图的边具有标签 label ，因此该论文使用不同的权重矩阵来表示不同label 的边：

       $$\begin{array}{c}{\overrightarrow{\mathbf{i}}}_v^{(t)}=\sigma ({\mathbf{W}}^{(i)}{\overrightarrow{\mathbf{x}}}_v^{(t)}+\sum _{k\in {\mathcal{N}}_v}{\mathbf{U}}_{m(v,k)}^{(i)}{\overrightarrow{\mathbf{h}}}_k^{(t-1)}+{\overrightarrow{\mathbf{b}}}^{(i)})\\ {\overrightarrow{\mathbf{f}}}_{v,k}^{(t)}=\sigma ({\mathbf{W}}^{(f)}{\overrightarrow{\mathbf{x}}}_v^{(t)}+{\mathbf{U}}_{m(v,k)}^{(f)}{\overrightarrow{\mathbf{h}}}_k^{(t-1)}+{\overrightarrow{\mathbf{b}}}^{(f)})\\ {\overrightarrow{\mathbf{o}}}_v^{(t)}=\sigma ({\mathbf{W}}^{(o)}{\overrightarrow{\mathbf{x}}}_v^{(t)}+\sum _{k\in {\mathcal{N}}_v}{\mathbf{U}}_{m(v,k)}^{(o)}{\overrightarrow{\mathbf{h}}}_k^{(t-1)}+{\overrightarrow{\mathbf{b}}}^{(o)})\\ {\overrightarrow{\mathbf{u}}}_v^{(t)}=\tanh ({\mathbf{W}}^{(u)}{\overrightarrow{\mathbf{x}}}_v^{(t)}+\sum _{k\in {\mathcal{N}}_v}{\mathbf{U}}_{m(v,k)}^{(u)}{\overrightarrow{\mathbf{h}}}_k^{(t-1)}+{\overrightarrow{\mathbf{b}}}^{(u)})\\ {\overrightarrow{\mathbf{c}}}_v^{(t)}={\overrightarrow{\mathbf{i}}}_v^{(t)}\odot {\overrightarrow{\mathbf{u}}}_v^{(t)}+\sum _{k\in {\mathcal{N}}_v}{\overrightarrow{\mathbf{f}}}_{v,k}^{(t)}\odot {\overrightarrow{\mathbf{c}}}_k^{(t-1)}\\ {\overrightarrow{\mathbf{h}}}_v^{(t)}={\overrightarrow{\mathbf{o}}}_v^{(t)}\odot \tanh \left({\overrightarrow{\mathbf{c}}}_v^{(t)}\right)\end{array}$$

       其中$m(v,k)$$ m(v,k) $ 表示节点$v$$ v $ 和节点$k$$ k $ 之间的边标签 edge label 。

     • 《Sentence-state lstm for text representation》 提出了用于改进text encoding 的 Sentence LSTM:S-LSTM 。它将文本转换为图，并利用 Graph LSTM 来学习 representation 。 S-LSTM 在很多 NLP 问题中展现出强大的表示能力。

     • 《Semantic object parsing with graph lstm》 提出了一种 Graph LSTM 网络来解决语义对象解析任务 semantic object parsing task 。它使用置信度驱动方案 confidence-driven scheme 来自适应地选择开始节点并决定节点更新顺序。它遵循相同的思想来推广 LSTM 到图结构数据上，但是具有特定的更新顺序。而我们上述提到的方法和节点的顺序无关。

4. Attention：注意力机制已经成功地应用于很多 sequence-based 任务，例如机器翻译、机器阅读等。

   • 《Graph attention networks》 提出了 graph attention network: GAT 从而将注意力机制融合到传播步骤。它采用 self-attention 机制，通过关注节点的邻域来计算节点的 hidden state 。

     GAT 定义一个 graph attention layer，并通过堆叠多个 graph attention layer 来构建 graph attention network 。该层通过以下方式计算节点 pair 对$(i,j)$$ (i,j) $ 在注意力机制中的注意力系数：

     $${\alpha }_{i,j}=\frac{\exp \left(\text{LeakyReLU}\left({\overrightarrow{\mathbf{a}}}^{\mathrm{\top }}[\mathbf{W}{\overrightarrow{\mathbf{h}}}_i||\mathbf{W}{\overrightarrow{\mathbf{h}}}_j]\right)\right)}{\sum _{k\in {\mathcal{N}}_i}\exp \left(\text{LeakyReLU}\left({\overrightarrow{\mathbf{a}}}^{\mathrm{\top }}[\mathbf{W}{\overrightarrow{\mathbf{h}}}_i||\mathbf{W}{\overrightarrow{\mathbf{h}}}_k]\right)\right)}$$

     其中：

     • graph attention layer 的输入为节点的特征集合$\{{\overrightarrow{\mathbf{h}}}_1,\cdots ,{\overrightarrow{\mathbf{h}}}_N\}$$ \left\{\mathbf{\vec h}_1,\cdots,\mathbf{\vec h}_N\right\} $ ，其中${\overrightarrow{\mathbf{h}}}_i\in {\mathbb{R}}^F$$ \mathbf{\vec h}_i\in \mathbb R^F $ ，$F$$ F $ 为特征维度，$N$$ N $ 为节点数量。

     • graph attention layer 的输出为节点的新的特征集合$\{{\overrightarrow{\mathbf{h}}}_1^{\prime },\cdots ,{\overrightarrow{\mathbf{h}}}_N^{\prime }\}$$ \left\{\mathbf{\vec h}_1^\prime,\cdots,\mathbf{\vec h}_N^\prime\right\} $ ，其中${\overrightarrow{\mathbf{h}}}_i^{\prime }\in {\mathbb{R}}^{F^{\prime }}$$ \mathbf{\vec h}_i^\prime \in \mathbb R^{F^\prime} $ ，$F^{\prime }$$ F^\prime $ 为新的特征维度。其中：

       $${\overrightarrow{\mathbf{h}}}_i^{\prime }=\sigma \left(\sum _{j\in {\mathcal{N}}_i}{\alpha }_{i,j}\mathbf{W}{\overrightarrow{\mathbf{h}}}_j\right)$$

       $\sigma (\cdot )$$ \sigma(\cdot) $ 非非线性激活函数。

     • $\mathbf{W}\in {\mathbb{R}}^{F^{\prime }\times F}$$ \mathbf W\in \mathbb R^{F^\prime\times F} $ 为权重矩阵，它在所有节点之间共享。

     • $\overrightarrow{\mathbf{a}}\in {\mathbb{R}}^{2F^{\prime }}$$ \mathbf{\vec a}\in \mathbb R^{2F^\prime} $ 为单层 feedforward neural network 的权重。

     • $||$$ || $ 为向量拼接。

     • ${\alpha }_{i,j}$$ \alpha_{i,j} $ 为节点$j$$ j $ 对于节点$i$$ i $ 的 attention 系数。它满足：$\sum _{j\in {\mathcal{N}}_i}{\alpha }_{i,j}=1.0,0<{\alpha }_{i,j}<1.0$$ \sum_{j\in \mathcal N_i} \alpha_{i,j} = 1.0,\quad 0\lt \alpha_{i,j}\lt 1.0 $ 。

     此外，GAT 利用 multi-head attention 来稳定学习过程。它使用$K$$ K $ 个独立的注意力机制来计算 hidden state，然后将这$K$$ K $ 个 hidden state 拼接起来（或均值聚合），从而得到以下两种形式的 representation：

     $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_i^{\prime }=|{|}_{k=1}^K\sigma \left(\sum _{j\in {\mathcal{N}}_i}{\alpha }_{i,j}^{(k)}{\mathbf{W}}^{(k)}{\overrightarrow{\mathbf{h}}}_j^{(k)}\right)\\ {\overrightarrow{\mathbf{h}}}_i^{\prime }=\sigma \left(\frac{1}{K}\sum _{k=1}^K\sum _{j\in {\mathcal{N}}_i}{\alpha }_{i,j}^{(k)}{\mathbf{W}}^{(k)}{\overrightarrow{\mathbf{h}}}_j^{(k)}\right)\end{array}$$

     其中${\alpha }_{i,j}^{(k)}$$ \alpha_{i,j}^{(k)} $ 为第$k$$ k $ 个 attention计算到的注意力系数。

     GAT 的注意力架构具有几个特点：

     • 节点-邻居 pair 对的计算是可并行的，因此计算效率很高。
     • 通过为邻域指定不同的权重，因此可以应用于不同 degree 的节点。
     • 可以轻松地应用于 inductive learning。

   • GANN：除了 GAT 之外，Gated Attention Network:GAAN 也是用 multi-head 注意力机制。但是，它使用 self-attention 机制从不同的 head 收集信息，而不是像 GAT 那样拼接或者取平均。即每个 head 的重要性不同。

5. Skip connection：很多应用application 会堆叠多层神经网络从而预期获得更好的结果。因为更多的层，比如$K$$ K $ 层，可以使得每个节点从其$K$$ K $ 阶邻域中收集到更多的信息。但是，很多实验发现更深层的模型无法提高性能甚至表现更差。这主要是因为更深的层也可以指数级地传播噪音信息。

   可以从计算机视觉社区找到一种直接的解决方案，即残差网络 residual network 。但是，即便使用残差连接，在很多数据集上具有多层的 GCN 的性能也不如 2 层 GCN 更好。

   • Highway GCN：

     《Semi-supervised user geolocation via graph convolutional networks》 提出 Highway GCN ，它使用类似于 highway networks 的 layer-wise gate 。layer 的输出和layer 的输入加权累加，权重由门控给出：

     $$\begin{array}{c}\overrightarrow{\mathbf{T}}\left({\overrightarrow{\mathbf{h}}}^{(t)}\right)=\sigma ({\mathbf{W}}^{(t)}{\overrightarrow{\mathbf{h}}}^{(t)}+{\overrightarrow{\mathbf{b}}}^{(t)})\\ {\overrightarrow{\mathbf{h}}}^{(t+1)}\leftarrow {\overrightarrow{\mathbf{h}}}^{(t+1)}\odot \overrightarrow{\mathbf{T}}\left({\overrightarrow{\mathbf{h}}}^{(t)}\right)+{\overrightarrow{\mathbf{h}}}^{(t)}\odot (1-\overrightarrow{\mathbf{T}}\left({\overrightarrow{\mathbf{h}}}^{(t)}\right))\end{array}$$

     通过增加 higthway gate， 4层的 Higthway GCN 在某些特定问题上性能最佳。

     论文 《Column networks for collective classification》 提出的 Column Network:CLN 也使用 highway network，但是它使用不同的函数来计算门控权重。

   • JK-Net：

     《Representation learning on graphs with jumping knowledge networks》 研究了邻域聚合方案的特点以及邻域聚合导致的缺陷。该论文提出了 Jump Knowledge Network:JK-Net，它可以学习自适应adaptive 的 、结构感知structure-aware的representation`。

     JK-Net 将节点的每一层中间 representation 跳跃到最后一层，并在最后一层对这些中间 representation 进行自适应地选择，从而使得模型可以根据需要自适应地调整每个节点的有效邻域大小。

     JK-Net 在实验中使用了三种聚合方式来聚合信息：拼接、最大池化、LSTM-attention 。它也可以和 Graph Convolutional Network, GraphSAGE, Graph Attention Network 等模型结合，从而提升后者的性能。

6. Hierarchical Pooling：在计算机视觉领域，卷积层之后通常跟着池化层从而获得更加泛化的特征。和视觉领域的池化层相似，有很多工作集中在图上的层次池化层 hierarchical pooling layer 。复杂的大型图通常带有丰富的层次结构，这对于 node-level 和graph-level任务非常重要。

   • 为了探索这种内部特征 inner features，Edge-Conditioned Convolution:ECC 设计了具有递归下采样操作的池化模块。下采样方法通过拉普拉斯矩阵的最大特征向量的符号将图划分为两个分量。

   • DIFFPOOL 通过对每一层训练一个 assignment 矩阵，从而提出了一个可学习的层次聚类模块：

     $${\mathbf{S}}^{(l)}=\text{softmax}\left({\text{GNN}}_{l,\text{pool}}({\mathbf{A}}^{(l)},{\mathbf{X}}^{(l)})\right)$$

     其中：${\mathbf{X}}^{(l)}$$ \mathbf X^{(l)} $ 为节点在$l$$ l $ 的 feature 矩阵，${\mathbf{A}}^{(l)}$$ \mathbf A^{(l)} $ 为第$l$$ l $ 层的粗化邻接矩阵 coarsened adjacency matrix 。

c. Training Methods

1. 原始的图卷积神经网络在训练和优化方法上存在缺陷：

   • 首先，GCN 需要完整的图拉普拉斯算子，这对于大型图来讲计算量太大。
   • 其次，在第$L$$ L $ 层单个节点计算 embedding 时需要该节点邻域所有节点在第$L-1$$ L-1 $ 层的 embedding 。因此，单个节点的感受野相对于层数呈指数型增长，因此计算单个节点的梯度的代价很大。
   • 最后，GCN 针对给定的图训练，这缺乏 inductive learning 能力。

2. Sampling：

   • GraphSAGE：GraphSAGE 是原始 GCN 的全面改进。为解决上述问题，GraphSAGE 用可学习的聚合函数替换了完整的图拉普拉斯算子，这是执行消息传递和泛化到未见过节点的关键：

     $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{(l)}={\text{AGG}}^{(l)}\left(\{{\overrightarrow{\mathbf{h}}}_u^{(l-1)},\mathrm{\forall }u\in {\mathcal{N}}_v\}\right)\\ {\overrightarrow{\mathbf{h}}}_v^{(l)}=\sigma \left({\mathbf{W}}^{(l)}[{\overrightarrow{\mathbf{h}}}_v^{(l-1)}||{\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{(l)}]\right)\end{array}$$

     GraphSAGE 首先聚合邻域 embedding，然后和目标节点的 embedding 拼接，最后传播到下一层。

     通过可学习的邻域聚合函数和消息传播函数，GraphSAGE 可以泛化到未见过的节点。

     此外，GraphSAGE 使用邻域采样来缓解感受野的扩张 expansion 。

   • PinSage：PinSage 提出了基于重要性的采样方法。通过模拟从目标节点开始的随机游走，该方法选择了归一化访问次数 top$T$$ T $ 个节点。

   • FastGCN：FastGCN 进一步改善了采样算法。FastGCN 不会为每个节点采样邻居，而是直接为每层采样整个感受野。

     FastGCN 也使用重要性采样，但是其重要性因子为：

     $$q(v)\propto \frac{1}{|{\mathcal{N}}_v|}\sum _{u\in {\mathcal{N}}_v}\frac{1}{|{\mathcal{N}}_u|}$$

   • 和上面固定的采样方法相反，论文 《Adaptive sampling towards fast graph representation learning》 引入了一个参数化、且可训练的采样器来执行以前一层为条件的逐层采样。此外，该自适应采样器可以找到最佳采样重要性并同时减少采样方差。

   • SSE：遵循强化学习，论文 《Learning steady-states of iterative algorithms over graphs》 提出SSE，它采用 Stochastic Fixed-Point Gradient Descent 用于 GNN 的训练。

     该方法将 embedding 更新视为值函数 value function。在训练期间，该算法将对节点进行采样以更新 embedding， 对标记节点采样以更新参数，二者交替进行。

3. Receptive Field Control：《Stochastic training of graph convolutional networks with variance reduction》 通过利用节点的历史激活作为控制变量control variate ，提出了一种基于控制变量的 GCN 随机近似算法。该方法限制了一阶邻域中的感受野，但使用历史 hidden state 从而作为一个可接受的近似值。

4. Data Augmentation：《Deeper insights into graph convolutional networks for semi-supervised learning》 聚焦于 GCN 的局限性，其中包括 GCN 需要许多额外的标记数据用于验证集，并且还遭受卷积滤波器的局部性。为解决这些限制，作者提出了 Co-Training GCN 以及 Self-Training GCN 来扩大训练集。前者寻找训练标记样本的最近邻居，后者遵循类似 boosting 的方法。

5. Unsupervised training：GNN 通常用于监督学习或半监督学习，最近有一种趋势是将自编码器 auto-encoder:AE 扩展到图领域。图自编码器旨在通过无监督学习获取节点的低维 representation 。

   • GAE：

     论文 《Variational graph auto-encoders》 提出了Graph Auto-Encoder: GAE 。GAE 是首次使用 GCN 对图中的节点进行编码，然后它使用简单的解码器重构邻接矩阵，并根据原始邻接矩阵和重构邻接矩阵之间的相似度来评估损失：

     $$\begin{array}{c}\mathbf{Z}=\text{GCN}(\mathbf{X},\mathbf{A})\\ \tilde{\mathbf{A}}=\rho \left(\mathbf{Z}{\mathbf{Z}}^{\mathrm{\top }}\right)\end{array}$$

     论文也以变分的方式训练 GAE 模型，称作变分图自编码器variational graph autoencoder:VGAE 。

     此外，graph convolutional matrix completion:GC-MC 也使用 GAE 并应用于推荐系统中。在 MovieLens 数据集上，GC-MC 性能优于其它 baseline 模型。

   • ARGA：

     Adversarially Regularized Graph Auto-encoder:ARGA 使用生成对抗网络 generative adversarial network:GAN 来正则化 GCN-based 的 GAE 从而遵循先验分布。

   • 也有几种图自编码器，例如 NetRA, DNGR, SDNE, DRNE，但是它们的架构中未使用 GNN 。

2.2 通用框架

1. 除了图神经网络的不同变体之外，人们还提出了一些通用框架，旨在将不同的模型整合到一个框架中。

   • 《Neural message passing for quantum chemistry》 提出了消息传递神经网络 message passing neural network: MPNN ，它统一了各种图神经网络和图卷积网络方法。
   • 《Non-local neural networks》 提出了非局部神经网络 non-local neural network: NLNN ，它统一了集中 self-attention 风格的方法。
   • 《Relational inductive biases, deep learning, and graph networks》 提出了一种图网络 graph network: GN，它统一了 MPNN、NLNN 以及许多其它变体，例如 Interaction Network、 Neural Physics Engine 、CommNet、structure2ve、GGNN、Relation Network、Deep Sets、Point Net 。

2.2.1 MPNN

1. MPNN 框架总结了几种最流行的图模型之间的共性，如graph convolution network, gated graph neural network, interaction network, molecular graph convolution, deep tensor neural network 等等。

2. MPNN 包含两个阶段：消息传递阶段、readout 阶段 。

   • 消息传递阶段（也称作传播阶段）执行$T$$ T $ 个时间步，并根据消息函数$M_t$$ M_t $ 和节点更新函数$U_t$$ U_t $ 来定义。

     令节点$v$$ v $ 在时刻$t$$ t $ 收到的消息为${\overrightarrow{\mathbf{m}}}_v^{(t)}$$ \mathbf{\vec m}_v^{(t)} $ ，在时刻$t$$ t $ 的 hidden state 为${\overrightarrow{\mathbf{h}}}_v^{(t)}$$ \mathbf{\vec h}_v^{(t)} $ ，则有：

     $$\begin{array}{c}{\overrightarrow{\mathbf{m}}}_v^{(t+1)}=\sum _{w\in {\mathcal{N}}_v}{M}_t({\overrightarrow{\mathbf{h}}}_v^{(t)},{\overrightarrow{\mathbf{h}}}_w^{(t)},{\overrightarrow{\mathbf{e}}}_{v,w})\\ {\overrightarrow{\mathbf{h}}}_v^{(t+1)}=U_t({\overrightarrow{\mathbf{h}}}_v^{(t)},{\overrightarrow{\mathbf{m}}}_v^{(t+1)})\end{array}$$

     其中${\overrightarrow{\mathbf{e}}}_{v,w}$$ \mathbf{\vec e}_{v,w} $ 为节点$v,w$$ v,w $ 之间边的特征。

   • readout 阶段使用 Readout 函数$R(\cdot )$$ R(\cdot) $ 来计算整个图的特征向量：

     $$\widehat{\overrightarrow{\mathbf{y}}}=R\left(\{{\overrightarrow{\mathbf{h}}}_v^{(T)}\mid v\in \mathcal{V}\}\right)$$

     其中 T 表示总的时间步。

3. 消息函数$M_t$$ M_t $ 、节点更新函数$U_t$$ U_t $ 、readout 函数$R$$ R $ 可以有不同的设置，因此 MPNN 框架可以通过不同的配置来概括几种不同的模型。

   这里我们以 GGNN 为例，其它模型的示例参考原始论文。针对 GGNN 模型的函数配置为：

   $$\begin{array}{c}{M}_t({\overrightarrow{\mathbf{h}}}_v^{(t)},{\overrightarrow{\mathbf{h}}}_w^{(t)},{\overrightarrow{\mathbf{e}}}_{v,w})={\mathbf{A}}_{e_{v,w}}{\overrightarrow{\mathbf{h}}}_w^{(t)}\\ U_t({\overrightarrow{\mathbf{h}}}_v^{(t)},{\overrightarrow{\mathbf{m}}}_v^{(t+1)})=\text{GRU}({\overrightarrow{\mathbf{h}}}_v^{(t)},{\overrightarrow{\mathbf{m}}}_v^{(t+1)})\\ R\left(\{{\overrightarrow{\mathbf{h}}}_v^{(T)}\mid v\in \mathcal{V}\}\right)=\sum _{v\in \mathcal{V}}\sigma \left({\mathcal{F}}_i({\overrightarrow{\mathbf{h}}}_v^{(T)},{\overrightarrow{\mathbf{h}}}_v^{(0)})\right)\odot \left({\mathcal{F}}_j\left({\overrightarrow{\mathbf{h}}}_v^{(T)}\right)\right)\end{array}$$

   其中：

   • ${\mathbf{A}}_{e_{v,w}}$$ \mathbf A_{e_{v,w}} $ 为邻接矩阵，对于每一个edge label 采用不同的邻接矩阵。
   • GRU 为 Gated Recurrent Unit 。
   • ${\mathcal{F}}_i(\cdot ,\cdot ),{\mathcal{F}}_j(\cdot )$$ \mathcal F_i(\cdot,\cdot),\mathcal F_j(\cdot) $ 为$R$$ R $ 中的神经网络，$\odot$$ \odot $ 为逐元素乘法。

2.2.2 NLNN

1. NLNN 用户捕获深度神经网络的长程依赖。

   non-local 操作是计算机视觉中经典的 non-local 均值操作的推广。non-local 操作将某个位置的 response 计算为所有位置的特征的加权和，位置可以为空间位置、时间位置、或者时空位置。因此，NLNN可以视为不同的 self-attention 方式的统一。

2. 我们首先介绍 non-local 操作的一般定义。遵从 non-local 均值操作，推广的 non-local 操作定义为：

   $${\overrightarrow{\mathbf{h}}}_i^{\prime }=\frac{1}{{\mathcal{C}}_i(\mathbf{H})}\sum _{\mathrm{\forall }j}f({\overrightarrow{\mathbf{h}}}_i,{\overrightarrow{\mathbf{h}}}_j)\times g\left({\overrightarrow{\mathbf{h}}}_j\right)$$

   其中：

   • $i$$ i $ 为输出位置索引，$j$$ j $ 遍历所有可能的输入位置索引。
   • $f({\overrightarrow{\mathbf{h}}}_i,{\overrightarrow{\mathbf{h}}}_j)\in \mathbb{R}$$ f\left(\mathbf{\vec h}_i,\mathbf{\vec h}_j\right)\in \mathbb R $ 是位置$i$$ i $ 和位置$j$$ j $ 之间的一个标量函数，表示它们之间的关系。
   • $g\left({\overrightarrow{\mathbf{h}}}_j\right)$$ g\left(\mathbf{\vec h}_j\right) $ 表示输入${\overrightarrow{\mathbf{h}}}_j$$ \mathbf{\vec h}_j $ 的变换，并使用因子$\frac{1}{{\mathcal{C}}_i(\mathbf{H})}$$ \frac{1}{\mathcal C_i(\mathbf H)} $ 来归一化结果。
   • $\mathbf{H}$$ \mathbf H $ 为所有${\overrightarrow{\mathbf{h}}}_j$$ \mathbf{\vec h}_j $ 拼接而成的向量，${\mathcal{C}}_i(\mathbf{H})$$ \mathcal C_i(\mathbf H) $ 表示针对输出$i$$ i $ 的归一化分母。

   有几种不同的$f(\cdot ,\cdot )$$ f(\cdot,\cdot) $ 和$g(\cdot )$$ g(\cdot) $ 的配置，为简单起见 NLNN 使用线性变换作为$g(\cdot )$$ g(\cdot) $ 函数。这意味着$g\left({\overrightarrow{\mathbf{h}}}_j\right)={\mathbf{W}}_g{\overrightarrow{\mathbf{h}}}_j$$ g\left(\mathbf{\vec h}_j\right) = \mathbf W_g\mathbf{\vec h}_j $ ，其中${\mathbf{W}}_g$$ \mathbf W_g $ 为可学习的权重矩阵。接下来我们讨论$f(\cdot ,\cdot )$$ f(\cdot,\cdot) $ 函数的选择。

3. 高斯Gaussian 函数：高斯函数是根据非局部均值 non-local mean （论文 《A non-local algorithm for image denoising》）和双边滤波器 bilateral filter （论文 《Bilateral filtering for gray and color images》）的自然选择：

   $$f({\overrightarrow{\mathbf{h}}}_i,{\overrightarrow{\mathbf{h}}}_j)=\exp ({\overrightarrow{\mathbf{h}}}_i\cdot {\overrightarrow{\mathbf{h}}}_j)$$

   其中，${\overrightarrow{\mathbf{h}}}_i\cdot {\overrightarrow{\mathbf{h}}}_j$$ \mathbf{\vec h}_i\cdot \mathbf{\vec h}_j $ 是点积相似性 dot-product similarity 。并且：

   $${\mathcal{C}}_i(\mathbf{H})=\sum _{j}f({\overrightarrow{\mathbf{h}}}_i,{\overrightarrow{\mathbf{h}}}_j)$$

4. Embedded Gaussian 函数：很自然地通过计算 embedding 空间中的相似性来扩展高斯函数。即：

   $$f({\overrightarrow{\mathbf{h}}}_i,{\overrightarrow{\mathbf{h}}}_j)=\exp (\theta \left({\overrightarrow{\mathbf{h}}}_i\right)\cdot \varphi \left({\overrightarrow{\mathbf{h}}}_j\right))$$

   其中：

   $$\theta \left({\overrightarrow{\mathbf{h}}}_i\right)={\mathbf{W}}_{\theta }{\overrightarrow{\mathbf{h}}}_i,\varphi \left({\overrightarrow{\mathbf{h}}}_j\right)={\mathbf{W}}_{\varphi }{\overrightarrow{\mathbf{h}}}_j,{\mathcal{C}}_i(\mathbf{H})=\sum _{j}f({\overrightarrow{\mathbf{h}}}_i,{\overrightarrow{\mathbf{h}}}_j)$$

   可以发现 《Attention is all you need》 提出的 self-attention 是 Embedded Gaussian 函数的特例。对于给定的$i$$ i $ ，$\frac{1}{{\mathcal{C}}_i(\mathbf{H})}\sum _{\mathrm{\forall }j}f({\overrightarrow{\mathbf{h}}}_i,{\overrightarrow{\mathbf{h}}}_j)$$ \frac{1}{\mathcal C_i(\mathbf H)} \sum_{\forall j} f\left(\mathbf{\vec h}_i,\mathbf{\vec h}_j\right) $ 成为沿着维度$j$$ j $ 的 softmax。因此有：

   $${\overrightarrow{\mathbf{h}}}^{\prime }=\text{softmax}\left({\mathbf{H}}^{\mathrm{\top }}{\mathbf{W}}_{\theta }^{\mathrm{\top }}{\mathbf{W}}_{\varphi }\mathbf{H}\right)g\left(\mathbf{H}\right)$$

   这就是 self-attention 的形式。

5. 点积函数：$f(\cdot ,\cdot )$$ f(\cdot,\cdot) $ 可以是简单的点积相似性 dot-product similarity，即：

   $$f({\overrightarrow{\mathbf{h}}}_i,{\overrightarrow{\mathbf{h}}}_j)=\theta \left({\overrightarrow{\mathbf{h}}}_i\right)\cdot \varphi \left({\overrightarrow{\mathbf{h}}}_j\right)$$

   其中：

   $$\theta \left({\overrightarrow{\mathbf{h}}}_i\right)={\mathbf{W}}_{\theta }{\overrightarrow{\mathbf{h}}}_i,\varphi \left({\overrightarrow{\mathbf{h}}}_j\right)={\mathbf{W}}_{\varphi }{\overrightarrow{\mathbf{h}}}_j,{\mathcal{C}}_i(\mathbf{H})=N$$

   其中$N$$ N $ 为节点数量。

6. 拼接函数：$f(\cdot ,\cdot )$$ f(\cdot,\cdot) $ 可以为简单的向量拼接：

   $$f({\overrightarrow{\mathbf{h}}}_i,{\overrightarrow{\mathbf{h}}}_j)=\text{ReLU}({\overrightarrow{\mathbf{w}}}_f\cdot [\theta \left({\overrightarrow{\mathbf{h}}}_i\right)||\varphi \left({\overrightarrow{\mathbf{h}}}_j\right)])$$

   其中：${\overrightarrow{\mathbf{w}}}_f$$ \mathbf{\vec w}_f $ 是一个权重向量，${\mathcal{C}}_i(\mathbf{H})=N$$ \mathcal C_i(\mathbf H) = N $ ，$N$$ N $ 为节点数量。

7. NLNN 将上述 non-local 操作包装到一个 non-local block 中：

   $$\begin{array}{c}{\overrightarrow{\mathbf{z}}}_i={\mathbf{W}}_z{\overrightarrow{\mathbf{h}}}_i^{\prime }+{\overrightarrow{\mathbf{h}}}_i\\ {\overrightarrow{\mathbf{h}}}_i^{\prime }=\frac{1}{{\mathcal{C}}_i(\mathbf{H})}\sum _{\mathrm{\forall }j}f({\overrightarrow{\mathbf{h}}}_i,{\overrightarrow{\mathbf{h}}}_j)g\left({\overrightarrow{\mathbf{h}}}_j\right)\end{array}$$

   其中$+{\overrightarrow{\mathbf{h}}}_i$$ + \mathbf{\vec h}_i $ 为残差连接。因此，non-local block 可以插入任何预训练模型 pre-trained model 中，这使得该 block 适用性更好。

2.2.3 GN

1. Graph Network:GN 框架概括并扩展了各种图神经网络、MPNN 、以及 NLNN 方法。我们首先介绍图的定义，然后描述 GN 块、GN 核心计算单元、计算步骤。

2. 在 GN 框架内，图被定义为三元组$\mathcal{G}=(\overrightarrow{\mathbf{u}},\mathcal{V},\mathcal{E})$$ \mathcal G = \left(\mathbf{\vec u},\mathcal V, \mathcal E\right) $ ，其中：

   • $\overrightarrow{\mathbf{u}}$$ \mathbf{\vec u} $ 为全局属性，比如它代表全局的万有引力场。
   • $\mathcal{V}=\{{\overrightarrow{\mathbf{v}}}_i{\}}_{i=1}^{N_v}$$ \mathcal V = \{\mathbf{\vec v}_i\}_{i=1}^{N_v} $ 代表节点属性的集合，$N_v$$ N_v $ 为节点数量，${\overrightarrow{\mathbf{v}}}_i$$ \mathbf{\vec v}_i $ 为节点$i$$ i $ 的属性向量。
   • $\mathcal{E}=\{({\overrightarrow{\mathbf{e}}}_k,r_k,s_k){\}}_{k=1}^{N_e}$$ \mathcal E = \{(\mathbf{\vec e}_k, r_k,s_k)\}_{k=1}^{N_e} $ 为边的集合，$N_e$$ N_e $ 为边数量，${\overrightarrow{\mathbf{e}}}_k$$ \mathbf{\vec e}_k $ 为边的属性，$r_k$$ r_k $ 为 receiver 节点，$s_k$$ s_k $ 为 sender 节点。

3. 一个 GN 块包含三个更新函数$\varphi$$ \phi $ ，以及三个聚合函数$\rho$$ \rho $ ：

   $$\begin{array}{c}{\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}})\\ {\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }={\rho }^{(e\to v)}\left({\mathcal{E}}_i^{\prime }\right)\\ {\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}})\\ {\overline{\overrightarrow{\mathbf{e}}}}^{\prime }={\rho }^{(e\to u)}\left({\mathcal{E}}^{\prime }\right)\\ {\overrightarrow{\mathbf{u}}}^{\prime }={\varphi }^{(u)}({\overline{\overrightarrow{\mathbf{e}}}}^{\prime },{\overline{\overrightarrow{\mathbf{v}}}}^{\prime },\overrightarrow{\mathbf{u}})\\ {\overline{\overrightarrow{\mathbf{v}}}}^{\prime }={\rho }^{(v\to u)}\left({\mathcal{V}}^{\prime }\right)\end{array}$$

   其中：

   $${\mathcal{E}}_i^{\prime }={\left\{({\overrightarrow{\mathbf{e}}}_k^{\prime },r_k,s_k)\right\}}_{r_k=i,k=1,\cdots ,N_e},{\mathcal{E}}^{\prime }={\left\{({\overrightarrow{\mathbf{e}}}_k^{\prime },r_k,s_k)\right\}}_{k=1,\cdots ,N_e},{\mathcal{V}}^{\prime }={\left\{{\overrightarrow{\mathbf{v}}}_i^{\prime }\right\}}_{i=1,\cdots ,N_v}$$

   其物理意义为：

   • ${\varphi }^{(e)}$$ \phi^{(e)} $ 根据每条边的属性${\overrightarrow{\mathbf{e}}}_k$$ \mathbf{\vec e}_k $ 、全局属性$\overrightarrow{\mathbf{u}}$$ \mathbf{\vec u} $ 、以及 sender 节点属性${\overrightarrow{\mathbf{v}}}_{s_k}$$ \mathbf{\vec v}_{s_k} $ 、receiver节点属性${\overrightarrow{\mathbf{v}}}_{r_k}$$ \mathbf{\vec v}_{r_k} $ 来更新对应边的属性${\overrightarrow{\mathbf{e}}}_k^{\prime }$$ \mathbf{\vec e}_k^\prime $ 。
   • ${\varphi }^{(v)}$$ \phi^{(v)} $ 根据每个节点的属性${\overrightarrow{\mathbf{v}}}_i$$ \mathbf{\vec v}_i $ 、全局属性$\overrightarrow{\mathbf{u}}$$ \mathbf{\vec u} $ 、以及 receiver为当前节点的所有边的属性（更新后的边属性）的聚合值${\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }$$ \bar{\mathbf{\vec e}}_i^\prime $ 来更新对应节点的属性${\overrightarrow{\mathbf{v}}}_i^{\prime }$$ \mathbf{\vec v}_i^\prime $ 。
   • ${\varphi }^{(u)}$$ \phi^{(u)} $ 根据全局属性$\overrightarrow{\mathbf{u}}$$ \mathbf{\vec u} $ 、所有节点的属性（更新后）的聚合值${\overline{\overrightarrow{\mathbf{v}}}}^{\prime }$$ \bar{\mathbf{\vec v}}^\prime $ 、全局属性、所有边的属性（更新后）的聚合值${\overline{\overrightarrow{\mathbf{e}}}}^{\prime }$$ \bar{\mathbf{\vec e}}^\prime $ 来更新全局属性${\overrightarrow{\mathbf{u}}}^{\prime }$$ \mathbf{\vec u}^\prime $ 。它仅更新一次。
   • 每个$\rho$$ \rho $ 函数使用一个集合作为输入，然后聚合为单个结果代表聚合后的信息。最重要的是：$\rho$$ \rho $ 函数必须是排列无关的 permutation invariant，并且应该采用可变数量的自变量。一些典型的例子包括：逐元素求和、均值池化、最大值池化等。

   $\varphi (\cdot )$$ \phi(\cdot) $ 和$\rho (\cdot )$$ \rho(\cdot) $ 函数不一定是神经网络，但是本文中我们仅关注神经网络的实现。

4. GN 块的计算步骤：

   • 通过执行${\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}})$$ \phi^{(e)}\left(\mathbf{\vec e}_k, \mathbf{\vec v}_{r_k}, \mathbf{\vec v}_{s_k},\mathbf{\vec u}\right) $ 得到每条边更新后的属性${\overrightarrow{\mathbf{e}}}_k^{\prime }$$ \mathbf{\vec e}_k^\prime $ 。

     • 更新后，边的集合为${\mathcal{E}}^{\prime }={\left\{({\overrightarrow{\mathbf{e}}}_k^{\prime },r_k,s_k)\right\}}_{k=1,\cdots ,N_e}$$ \mathcal E^\prime = \left\{\left(\mathbf{\vec e}_k^\prime, r_k, s_k\right)\right\}_{k=1,\cdots,N_e} $
     • 更新后，节点$i$$ i $ 相关的边的集合为${\mathcal{E}}_i^{\prime }={\left\{({\overrightarrow{\mathbf{e}}}_k^{\prime },r_k,s_k)\right\}}_{r_k=i,k=1,\cdots ,N_e}$$ \mathcal E_i^\prime = \left\{\left(\mathbf{\vec e}_k^\prime, r_k, s_k\right)\right\}_{r_k=i,k=1,\cdots,N_e} $ 。这里节点$i$$ i $ 为 receiver 。

   • 执行${\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }={\rho }^{(e\to v)}\left({\mathcal{E}}_i^{\prime }\right)$$ \bar{\mathbf{\vec e}}_i^\prime = \rho^{(e\rightarrow v)}\left(\mathcal E_i^\prime\right) $ 从而得到每个节点对应边的聚合信息。

   • 通过执行${\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}})$$ \mathbf{\vec v}_i^\prime = \phi^{(v)}\left(\bar{\mathbf{\vec e}}_i^\prime, \mathbf{\vec v}_{i},\mathbf{\vec u}\right) $ 得到每个节点更新后的属性。

     更新后，所有节点的属性集合为${\mathcal{V}}^{\prime }={\left\{{\overrightarrow{\mathbf{v}}}_i^{\prime }\right\}}_{i=1,\cdots ,N_v}$$ \mathcal V^\prime = \left\{\mathbf{\vec v}_i^\prime\right\}_{i=1,\cdots,N_v} $ 。

   • 通过执行${\overline{\overrightarrow{\mathbf{e}}}}^{\prime }={\rho }^{(e\to u)}\left({\mathcal{E}}^{\prime }\right)$$ \bar{\mathbf{\vec e}}^\prime = \rho^{(e\rightarrow u)}\left(\mathcal E^\prime \right) $ 对所有边进行聚合得到${\overline{\overrightarrow{\mathbf{e}}}}^{\prime }$$ \bar{\mathbf{\vec e}}^\prime $ 。

   • 通过执行${\overline{\overrightarrow{\mathbf{v}}}}^{\prime }={\rho }^{(v\to u)}\left({\mathcal{V}}^{\prime }\right)$$ \bar{\mathbf{\vec v}}^\prime = \rho^{(v\rightarrow u)}\left(\mathcal V^\prime\right) $ 对所有节点进行聚合得到${\overline{\overrightarrow{\mathbf{v}}}}^{\prime }$$ \bar{\mathbf{\vec v}}^\prime $ 。

   • 通过执行${\overrightarrow{\mathbf{u}}}^{\prime }={\varphi }^{(u)}({\overline{\overrightarrow{\mathbf{e}}}}^{\prime },{\overline{\overrightarrow{\mathbf{v}}}}^{\prime },\overrightarrow{\mathbf{u}})$$ \mathbf{\vec u}^\prime = \phi^{(u)}\left(\bar{\mathbf{\vec e}}^\prime, \bar{\mathbf{\vec v}}^\prime,\mathbf{\vec u}\right) $ 来更新图的全局属性。

   尽管这里我们给出了计算步骤的顺序，但是并不是严格地根据这个顺序来执行。例如，可以先更新全局属性、再更新节点属性、最后更新边属性。

5. 设计原则：Graph Network 的设计基于三个基本原则：灵活的representation、可配置的块内结构 within-block structure 、可组合的多块架构 multi-block architecture 。

   • 灵活的representation：GN 框架支持属性的灵活representation，以及不同的 graph 结构。

     • 全局属性、节点属性和边属性可以使用任意的表示格式，但实值向量和张量是最常见的。
     • 就graph 结构而言，GN 框架既可以应用于图结构明确的结构性场景，也可以应用于需要推断关系结构 relational structure 的非结构性场景。

   • 可配置的块内结构：一个 GN 块内的函数及其输入可以有不同的设置，因此 GN 框架在块内结构配置方面提供了灵活性。基于不同的结构和函数设置，各种模型（如 MPNN 、NLNN和其他变体）都可以由GN 框架表达。

   • 可组合的多块架构：GN 块可以被组合从而构建复杂的架构。任意数量的GN 块可以用共享参数或不共享参数的方式来堆叠式地组合。也可以采用一些其他技术来构建 GN-based 架构，如 skip connection、LSTM-style 门控机制、GRU-style 门控机制，等等。

2.3 应用

1. 图神经网络已经在监督学习、半监督学习、无监督学习、强化学习等领域广泛应用。这里我们将应用分为三类：

   • 数据具有明确关系结构的结构性场景，如物理系统 physical system 、分子结构molecular structure 、知识图谱knowledge graph 。
   • 关系结构不明确的非结构性场景，包括图像image 、文本text 等。
   • 其它应用场景，如生成模型generative model、组合优化问题combinatorial optimization problem 。

   下表给出这些场景的一个总结：

   

2.3.1 结构化的场景

1. 物理学：对现实世界的物理系统进行建模是理解人类智能的最基本方面之一。通过将物体表示为节点，将关系表示为边，我们可以用一种简化但有效的方式对物体、关系和物理学进行 GNN-based 的推理。

2. 分子学和生物学：

   • 分子指纹 molecular fingerprint 计算：分子指纹是一个代表分子的特征向量，主要用于计算机辅助药物设计。传统的分子指纹是手工制作和固定的，通过将 GNN 应用于分子图，我们可以获得更好的分子指纹。
   • 蛋白质交互预测：蛋白质交互预测任务是一个具有挑战性的问题，在药物发现和设计中有着重要的应用。

3. 知识图谱：《Knowledge transfer for out-of-knowledge-base entities : A graph neural network approach》 使用 GNN ，从而在 knowledge base completion: KBC 中解决 out-of-knowledge-base: OOKB 实体问题。

   《Cross-lingual knowledge graph alignment via graph convolutional networks》 使用 GCN 解决跨语言的知识图谱 knowledge graph 的对齐问题。

2.3.2 非结构化的场景

1. 图像：

   • 分类任务：几项工作利用图神经网络在图像分类中纳入结构的信息。

     • 首先，知识图谱可以作为额外的信息来指导 zero-shot 分类。
     • 其次， 除了知识图谱之外，数据集中的图像之间的相似性也有助于few-shot learning。

   • 视觉推理任务：计算机视觉系统通常需要通过纳入空间信息和语义信息来进行推理。因此，为推理任务生成 graph 是很自然的。一个典型的视觉推理任务是视觉问题回答 visual question answering: VQA 。视觉推理的其他应用包括目标检测、交互检测和区域分类。

   • 语义分割：语义分割任务是为图像中的每一个像素分配一个标签（或类别）。然而，分割区域 region 往往不是 grid-like 并且需要 non-local 信息，这导致了传统 CNN的失败。一些工作利用了图结构数据来处理该任务。

2. 文本：

   • 文本分类： 有一些工作把文档或句子看作是一个由 word 节点组成的图，还有一些工作依靠文档引用关系来构建图，还有一些工作将文档和词视为构建语料库 graph 的节点（因此是异质图）。
   • 序列标注：由于 GNN中的每个节点都有其隐状态 hidden state ，如果我们把句子中的每个词都看作是一个节点，我们就可以利用隐状态来解决序列标注问题。
   • 神经机器翻译neural machine translation: NMT ：GNN 的一个流行应用是将句法信息或语义信息纳入神经机器翻译任务中。

2.3.3 其它场景

1. 生成式模型：现实世界的图的生成模型因其重要的应用而引起了极大的关注，包括建模社交互动、发现新的化学结构、以及构建知识图谱。由于深度学习方法具有学习图的隐含分布的强大能力，最近神经图生成模型neural graph generative model 出现了一个高潮。
2. 组合优化 combinatorial optimization：图上的组合优化问题是一组 NP-hard 问题，吸引了所有领域的科学家的关注。一些具体的问题，如旅行推销员问题（traveling salesman problem: TSP ）和最小生成树（minimum spanning tree: MST），已经得到了各种启发式的解决方案。最近，使用深度神经网络来解决这类问题成为一个热点，其中一些解决方案由于其图结构而进一步利用了图神经网络。

2.4 悬而未决的问题

1. 尽管 GNN 在不同领域取得了重大成功，但是 GNN 仍然还有一些尚未解决的问题：

   • 浅层结构Shallow Structure：传统的深度神经网络可以堆叠数百层从而获得更好的性能，因为更深的结构具有更多的参数从而显著提高表达能力。但是图神经网络总是很浅，大多数不超过三层。

     实验表明，堆叠多个 GCN层将导致过度平滑，即所有节点都收敛到相同的值。尽管一些研究人员设法解决了该问题，但是它仍然是GNN 的最大局限。

   • 动态图 Dymaic Graph：另一个挑战是如何处理具有动态结构的图。

     静态图是稳定的，因此可以对其进行建模。而动态图引入了变化的结构，当边或节点出现或消失时，GNN无法自适应地调整。

   • 非结构化场景Non-Structural Scenario：没有很好的方法从原始的、非结构的数据生成图结构。如果找到最佳的图构建方法，则可以使得 GNN 应用范围更广。

   • 可扩展性Scalability：GNN 的扩展很困难，因为许多关键步骤在大规模数据下消耗大量的计算资源。例如：

     • 图数据不是规则的欧几里得结构，每个节点都有自己的邻域结构，因此无法进行 batch 处理。
     • 当有数百万个节点、边时，计算图拉普拉斯算子是不可行的。

     此外，我们必须指出：可扩展性决定了算法能否应用于实际工作中。