GNN 综述

一、Deep Learning On Graph[2018]

1. 将传统深度学习框架应用于图数据存在一些挑战：

   • 图的不规则结构：和网格结构的图像、音频、文本数据不同，图数据具有不规则的结构，因此很难将一些基础的数学算子推广到图上。如，为图数据定义卷积、池化算法并不简单。这个问题通常被称作几何深度学习问题 geometric deep learning problem 。
   • 图的异质性heterogeneity 和多样性diversity：图本身可能很复杂，包含各种类型和属性。如，图可以是异质的或同质的、加权的或者不加权的、有向的或无向的。此外，图任务也有很大不同，包括 node-level 任务（如节点分类）、graph-level 任务（如图分类）。这些不同的类型、属性、任务需要不同的模型架构来解决特定的问题。
   • 大型图：大数据时代，真实的图很容易拥有数百万甚至数十亿个节点和边。一些著名的例子是社交网络和电商网络。因此如何设计可扩展 scalable 的模型非常关键。
   • 融合跨学科知识：图通常和其它学科联系在一起，如生物学、化学、社会科学。这种跨学科的性质带来了机遇和挑战：可以利用领域知识来解决特定问题，但是融合领域知识可以使得模型设计复杂化。如，当生成分子图时，目标函数和化学约束通常是不可微的，因此基于梯度的训练方法不容易应用。

   为了应对这些挑战，人们在这一领域做出了巨大努力，诞生了很多有关论文和方法。论文 《Deep Learning on Graphs: A Survey》 试图通过全面回顾图的深度学习方法来系统性总结不同方法之间的差异和联系。

   如下图所述，论文根据现有的模型架构和训练策略将这些方法分为五类：

   • 图递归神经网络 graph recurrent neural networks: Graph RNN 。
   • 图卷积网络 graph convolutional networks: GCN。
   • 图自编码器 graph autoencoders: GAE 。
   • 图强化学习 graph reinforcement learning: Graph RL。
   • 图对抗方法graph adversarial methods 。

   

   论文在下表中总结了这些方法之间的一些主要特点：

   • Graph RNN 通过在 node-level 或者 graph-level 对状态建模从而捕获图的递归模式 recursive pattern 或者序列模式 sequential pattern 。
   • GCN 在不规则图结构上定义卷积和 readout 操作，从而捕获常见的局部结构模式和全局结构模式。
   • GAE 假设 low-rank 图结构，并采用无监督方法进行节点 representation learning 。
   • Graph RL 定义了 graph-based 动作和奖励，从而在遵循约束的同时获得图任务的反馈。
   • 图对抗方法采用对抗训练技术来提升 graph-based 模型的泛化能力，并通过对抗攻击测试其鲁棒性。

   

2. 相关工作：

   • 之前的一些调综述与我们的论文有关：

     • 《Geometric deep learning: going beyond euclidean data》 总结了一些早期的 GCN 方法以及流形上的CNN，并通过几何深度学习geometric deep learning对其进行了全面的研究。
     • 《Relational inductive biases, deep learning, and graph networks》 总结了如何使用 GNN 和 GCN 进行关系推理，使用了一个统一的框架，即 graph network 。
     • 《Attention models in graphs: A survey 》 回顾了图的注意力模型。
     • 《Graph convolutional networks: Algorithms, applications and open challenges》 总结了一些 GCN 模型。
     • 《Adversarial attack and defense on graph data: A survey》 简要综述了图的对抗性攻击。

     我们的工作与之前的这些工作不同，我们系统地、全面地回顾了图上不同的深度学习架构，而不是专注于一个特定的分支。

     与我们的工作同时，《Graphneural networks: A review of methods and applications》和 《A comprehensive survey on graph neural networks》从不同的角度和分类对这个领域进行了综述。具体来说，他们的工作都没有考虑图强化学习或图对抗方法，而这些都是本文所涉及的。

   • 另一个密切相关的主题 graph embedding ，目的是将节点嵌入到低维向量空间中。 graph embedding 和本文之间的主要区别是：我们专注于不同的深度学习模型如何应用于图，而 graph embedding 可以被认作是使用其中一些模型的具体应用实例。另外，graph embedding 也可能使用非深度学习方法。

3. 论文最后附录还给出了所有这些方法的源码地址、在公开数据集上的效果、时间复杂度。

1.1 基本概念

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}\in \mathcal{V}\times \mathcal{V}$$\mathcal E\in \mathcal V\times \mathcal V$ ， $N=|\mathcal{V}|$$N=|\mathcal V|$ 为节点数量， $M=|\mathcal{E}|$$M = |\mathcal E|$ 为边数量。

   • 每个节点 $v_i\in \mathcal{V}$$v_i\in \mathcal V$ 关联一个特征向量 ${\overrightarrow{\mathbf{f}}}_i^{\mathcal{V}}$$\mathbf{\vec f}_i^{\mathcal V}$，所有节点的特征向量构成节点特征矩阵 ${\mathbf{F}}^{\mathcal{V}}$$\mathbf F^{\mathcal V}$ 。

   • 每条边 $e_{i,j}\in \mathcal{E}$$e_{i,j}\in \mathcal E$ 关联一个特征向量 ${\overrightarrow{\mathbf{f}}}_{i,j}^{\mathcal{E}}$$\mathbf{\vec f}_{i,j}^{\mathcal E}$，所有边的特征向量构成边特征矩阵 ${\mathbf{F}}^{\mathcal{E}}$$\mathbf F^{\mathcal E}$ 。

   • 定义 $\mathbf{A}\in {\mathbb{R}}^{N\times N}$$\mathbf A\in \mathbb R^{N\times N}$ 为邻接矩阵，其中第 $i$$i$ 行记作 $\overrightarrow{A}(i,:)$$\vec A(i,:)$ ，第 $j$$j$ 列记作 $\overrightarrow{A}(:,j)$$\vec A(:,j)$ ，第 $i$$i$ 行 $j$$j$ 列元素为 $A(i,j)$$A(i,j)$ 。

   • 图可以为有向的或者无向的，可以为带权图或者无权图。

     • 如果是有向图则 $\mathbf{A}$$\mathbf A$ 不是对称矩阵；如果是无向图则 $\mathbf{A}$$\mathbf A$ 是对称矩阵。
     • 如果是带权图则 $A(i,j)$$A(i,j)$ 可以是任何数值；如果是不带权图则 $A(i,j)\in \{0,1\}$$A(i,j)\in \{0,1\}$ 。

   • 无向图的拉普拉斯矩阵定义为 $\mathbf{L}=\mathbf{D}-\mathbf{A}$$\mathbf L = \mathbf D - \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 矩阵。

     定义拉普拉斯矩阵的特征分解 eigen decomposition 为：

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

     其中：

     • $\mathbf{\Lambda }=\text{diag}({\lambda }_1,\cdots ,{\lambda }_N)$$\mathbf\Lambda = \text{diag}(\lambda_1,\cdots,\lambda_N)$ 为 $\mathbf{L}$$\mathbf L$ 的特征值eigenvalue组成的对角矩阵。
     • $\mathbf{Q}\in {\mathbb{R}}^{N\times N}$$\mathbf Q \in \mathbb R^{N\times N}$ 为对应特征向量eigenvector 组成的矩阵 。

   • 定义转移概率矩阵为 $\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$ 的概率。

   • 定义 $v_i$$v_i$ 的 k-step 邻域为：

     $${\mathcal{N}}_k(i)=\{j\mid \text{dist}(i,j)\le k\}$$

     其中 dist(i,j) 表示节点 $v_i,v_j$$v_i,v_j$ 之间的最短距离。为了简化讨论，对于一阶邻域我们记作 $\mathcal{N}(i)={\mathcal{N}}_1(i)$$\mathcal N(i) = \mathcal N_1(i)$ 。

2. 对于深度学习方法，我们使用上标来区分不同的层 layer，如 ${\mathbf{H}}^{(l)}$$\mathbf H^{(l)}$ 。我们用 $d_l$$d_l$ 来表示第 $l$$l$ 层的 representation 维度。

   通用的非线性激活函数记作 $\rho (\cdot )$$\rho(\cdot)$，其中 sigmoid 激活函数记作 $\sigma (x)=1/(1+\exp (-x))$$\sigma(x) = 1/(1+\exp(-x))$、relu 激活函数记作 $\text{ReLU}(x)=max(0,x)$$\text{ReLU}(x) = \max(0,x)$ 。

   除非另有说明，否则我们假设所有函数都是可微的，从而允许使用反向传播算法并使用常用的优化器和训练技术来学习模型参数。

   如果使用采样技术，则采样大小记作 $s$$s$ 。

3. 图上的深度学习任务大致可以分为两类：

   • node-level 任务：这些任务和图中的各个节点有关，如节点分类、链接预测、节点推荐。
   • graph-level 任务：这些任务和整个图有关，如图分类、图属性预估、图生成。

1.2 Graph RNN

1. 诸如 gated recurrent units: GRU 或者 long short-term memory: LSTM 之类的循环神经网络是建模序列数据的事实标准。这里我们总结了可捕获图的递归和序列模式的 Graph RNN 。

   Graph RNN 大致可以分为两类：node-level RNN 和 graph-level RNN 。主要区别是通过节点状态对 node-level 模式建模，还是通过公共的图状态对 graph-level 模型建模。下表给出了这些方法的主要特点。

   

1.2.1 node-level RNN

1. 图的 node-level RNN，也称作图神经网络 graph neural networks: GNNs，其背后思想很简单：每个节点 $v_i$$v_i$ 都由一个低维状态向量 ${\overrightarrow{\mathbf{s}}}_i$$\mathbf{\vec s}_i$ 来表示，从而编码图结构信息。

   受递归神经网络启发，GNN 采用了状态的递归定义：

   $${\overrightarrow{\mathbf{s}}}_i=\sum _{j\in \mathcal{N}(i)}\mathcal{F}({\overrightarrow{\mathbf{s}}}_i,{\overrightarrow{\mathbf{s}}}_j,{\overrightarrow{\mathbf{f}}}_i^{\mathcal{V}},{\overrightarrow{\mathbf{f}}}_j^{\mathcal{V}},{\overrightarrow{\mathbf{f}}}_{i,j}^{\mathcal{E}})$$

   其中 $\mathcal{F}(\cdot )$$\mathcal F(\cdot)$ 为待学习的函数。该公式也被称作状态方程。

   一旦得到 ${\overrightarrow{\mathbf{s}}}_i$$\mathbf {\vec s}_i$ ，则可以应用输出函数 $\mathcal{O}(\cdot )$$\mathcal O(\cdot)$ 来得到最终输出：

   $${\hat{y}}_i=\mathcal{O}({\overrightarrow{\mathbf{s}}}_i,{\overrightarrow{\mathbf{f}}}_i^{\mathcal{V}})$$

   对于graph-level 任务，作者建议添加一个具有唯一属性的特殊节点来代表整个图。

   为学习模型参数，作者使用以下半监督方法：

   • 使用 Jacobi 方法将状态方程（即定义 ${\overrightarrow{\mathbf{s}}}_i$$\mathbf{\vec s}_i$ 的方程）递归求解到不动点 stable point。
   • 使用 Almeida-Pineda 算法执行一个梯度下降 step 。
   • 最小化 task-specific 目标函数，如针对回归任务的平方损失。
   • 重复上述过程直到模型收敛。

   GNN 通过上述两个简单方程，发挥了两个重要作用：

   • GNN 统一了一些处理图数据的早期方法，如 RNN 和马尔科夫链。
   • GNN 的基本概念具有深远启发，许多最新的 GCN 实际上都有类似于状态方程的公式。

   尽管 GNN 在概念上很重要，但是它仍然存在一些缺陷：

   • 为确保状态方程具有唯一解， $\mathcal{F}(\cdot )$$\mathcal F(\cdot)$ 必须是一个收缩映射 contraction map。即，$\mathrm{\exists }\mu ,0\le \mu <1$$\exist\mu, 0\le \mu\lt 1$ ，使得：

     $$||\mathcal{F}(\overrightarrow{\mathbf{x}})-\mathcal{F}(\overrightarrow{\mathbf{y}})||\le \mu ||\overrightarrow{\mathbf{x}}-\overrightarrow{\mathbf{y}}||,\mathrm{\forall }\overrightarrow{\mathbf{x}},\overrightarrow{\mathbf{y}}$$

     直观地看，收缩映射要求任意两个点之间的距离在经过 $\mathcal{F}(\cdot )$$\mathcal F(\cdot)$ 映射之后必须减小，这严重地限制了模型的能力。

   • 在梯度下降的 step 之间，需要多轮迭代才能够收敛到不动点，因此 GNN 的计算量很大。

   由于存在这些缺陷，并且当时算力不高（GPU 在当时并未被广泛应用于深度学习），以及缺乏研究兴趣，当时 GNN 并未成为研究重点。

2. 对 GNN 的显著改进是 gated graph sequence neural networks:GGS-NNs 。在 GGS-NNs 中，作者使用 GRU 替代了状态方程中的递归定义，因此移除了收缩映射的约束，并支持了现代优化技术。

   具体而言，状态方程修改为：

   $${\overrightarrow{\mathbf{s}}}_i^{(t)}=(1-{\overrightarrow{\mathbf{z}}}_i^{(t)})\odot {\overrightarrow{\mathbf{s}}}_i^{(t-1)}+{\overrightarrow{\mathbf{z}}}_i^{(t)}\odot {\stackrel{\mathbf{~}}{\overrightarrow{\mathbf{s}}}}_i^{(t)}$$

   其中 ${\overrightarrow{\mathbf{z}}}_i^{(t)}$$\mathbf{\vec z}_i^{(t)}$ 是通过更新门来计算，${\widetilde{\overrightarrow{\mathbf{s}}}}_i^{(t)}$$\tilde{\mathbf{\vec s}}_i^{(t)}$ 为状态更新信息， $t$$t$ 为时间。

   然后作者提出依次使用若干个这种网络，从而产生序列输出，表明这种方法可以应用于序列任务。

3. SSE 采用了类似于 GGS-NNs 的方法，但是并未使用 GRU ，而是采用随机固定点梯度下降 stochastic fixed-point gradient descent ，从而加快训练过程。

   这种方案基本上是在使用局部邻域计算不动点状态、优化模型参数之间交替进行。这两种计算都是在 mini-batch 中进行的。

1.2.2 graph-level RNN

1. 在 Graph-level RNN 中，不是将单个 RNN 应用于每个节点以学习节点状态，而是将单个 RNN 应用于整个图从而对图状态进行编码。

2. 《GraphRnn:Generating realistic graphs with deep auto-regressive models》 将 Graph RNN 用于图生成问题。具体而言，他们采用两种 RNN：一种用于生成新节点，另一种用于以自回归的方式为新添加的节点生成边。

   他们表明：这种层次 hierarchical 的 RNN 体系结构比传统的、基于规则的图生成模型更有效地从输入图中学习，同时具有合理的时间复杂度。

3. 为捕获动态图的时间信息，DGNN 使用时间感知 time-aware的 LSTM 来学习node representation 。

   当建立新的边时，DGNN 使用 LSTM 更新这条边的两个交互节点以及它们直接邻居的 representation，即考虑一阶传播效果。作者表明：time-aware LSTM 可以很好地建模边生成的顺序 establishing order 和时间间隔time interval ，从而有助于一系列图的应用。

4. Graph RNN 也可以和其它架构（如 GCN/GAE ）组合。

   • 如，为解决稀疏性问题，RMGCNN 将 LSTM 应用于 GCN 的结果，从而逐渐重建 reconstruct 图。通过使用 LSTM ，来自图不同部分的信息不需要很多 GCN 层就可以传递到很远的距离。
   • Dynamic GCN 使用 LSTM 来聚合动态网络中不同时间片的 GCN 结果，从而捕获时空图 spatial and temporal graph 的信息。

1.3 GCN

1. 类似 CNN， 现代 GCN 通过精心设计的卷积函数和 readout 函数来学习图的常见局部结构模式和全局结构模式。

   由于大多数 GCN 可以使用 task-specific 损失函数（只有少数例外，如无监督学习方法），并通过反向传播进行训练。因此这里我们仅讨论体系结构。

   下表给出了我们总结的 GCN 的主要特征。

   

1.3.1 卷积操作

1. 卷积操作可以分为两类：

   • 谱域卷积spectral convolution：卷积操作通过使用图傅里叶变换将node representation转换到谱域 spectral domain 中进行卷积。
   • 空域卷积 spatial convolution：卷积操作使用邻域节点进行卷积。

   注意，这两种卷积可以重叠 overlap，如使用多项式谱域卷积核 polynomial spectral kernel 时。

a. 谱域卷积

1. 卷积是 CNN 中最基本的操作，但是用于图像或文本的标准卷积算子无法直接应用于图，因为图没有网格结构。

2. 《Spectral networks and locally connected networks on graph》 首先使用图拉普拉斯矩阵 $\mathbf{L}$$\mathbf L$ 引入了谱域的图卷积，这种图卷积在信号处理中起着和傅里叶基 basis 相似的作用。

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

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

   其中 ${\overrightarrow{\mathbf{u}}}_1,{\overrightarrow{\mathbf{u}}}_2\in {\mathbb{R}}^N$$\mathbf{\vec u}_1,\mathbf{\vec u}_2\in \mathbb R^N$ 为定义在图 $G$$G$ 所有节点上的两个信号， $\mathbf{Q}$$\mathbf Q$ 为图拉普拉斯矩阵 $\mathbf{L}$$\mathbf L$ 的特征向量 eigenvector 组成的矩阵 ，$\odot$$\odot$ 为逐元素乘法。

   简而言之：

   • 通过左乘 ${\mathbf{Q}}^{\mathrm{\top }}$$\mathbf Q^\top$ ，信号 ${\overrightarrow{\mathbf{u}}}_1,{\overrightarrow{\mathbf{u}}}_2$$\mathbf{\vec u}_1,\mathbf{\vec u}_2$ 被转换到谱域 spectral domain ，即图傅里叶变换 Graph Fourier Transform 。
   • 通过左乘 $\mathbf{Q}$$\mathbf Q$ ，谱域信号又被转换到空域 spatial domain，即傅里叶逆变换。

   该定义的有效性基于卷积定理，即卷积运算的傅里叶变换是其傅里叶变换的逐元素乘积。

   定义谱域卷积核为 $\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{u}}\in {\mathbb{R}}^N$$\mathbf{\vec u}\in \mathbb R^N$ 的卷积运算为：

   $${\overrightarrow{\mathbf{u}}}^{\prime }=\mathbf{Q}\mathbf{K}{\mathbf{Q}}^{\mathrm{\top }}\overrightarrow{\mathbf{u}}$$

   其中 ${\overrightarrow{\mathbf{u}}}^{\prime }$$\mathbf{\vec u}^\prime$ 为输出信号。这里每个信号 $\overrightarrow{\mathbf{u}}$$\mathbf{\vec u}$ 表示所有节点某个维度的标量值拼接而成。

   通过将不同的卷积核应用于不同的 input-output 信号来定义卷积层，即：

   $${\overrightarrow{\mathbf{u}}}_j^{(l+1)}=\rho \left(\sum _{i=1}^{d_l}\mathbf{Q}{\mathbf{K}}_{i,j}^{(l)}{\mathbf{Q}}^{\mathrm{\top }}{\overrightarrow{\mathbf{u}}}_i^{(l)}\right),j=1,2,\cdots ,d_{l+1}$$

   其中：

   • $l$$l$ 表示第 $l$$l$ 层卷积层， $d_l$$d_l$ 为第 $l$$l$ 层的 hidden representation 的维度。
   • ${\overrightarrow{\mathbf{u}}}_i^{(l)}$$\mathbf{\vec u}_i^{(l)}$ 为第 $l$$l$ 层所有节点的 hidden representation 向量在第 $i$$i$ 维的取值拼接而成的 ${\mathbb{R}}^N$$\mathbb R^N$ 向量，也可以视为第 $i$$i$ 个输入通道。
   • ${\mathbf{K}}_{i,j}^{(l)}$$\mathbf K_{i,j}^{(l)}$ 为第 $l$$l$ 层针对第 $i$$i$ 个输入通道、第 $j$$j$ 个输出通道的可训练的卷积核。

   上式背后的思想和传统的卷积类似：它使输入信号通过一组可学习的滤波器，从而聚合信息，然后进行一些非线性变换。通过使用节点特征矩阵 ${\mathbf{F}}^{\mathcal{V}}$$\mathbf F^{\mathcal V}$ 作为输入层，并堆叠多个卷积层，模型整体架构类似于 CNN。理论分析表明：图卷积运算的这种定义可以模拟 CNN 的某些几何特性。

   但是，直接使用上式需要学习 $O(N)$$O(N)$ 的参数，这在实践中不可行。此外，谱域中的滤波器可能不是空间局部性的 localized in the spatial domain，即在谱域卷积中，每个节点都会受到全局所有节点的影响（而不是仅受到局部邻域节点的影响）。为缓解这些问题 《Spectral networks and locally connected networks on graphs》 建议使用以下平滑滤波器 smoothing filters：

   $${\mathbf{K}}_{i,j}^{(l)}={\alpha }_{i,j}^{(l)}\mathcal{K}$$

   其中 $\mathcal{K}$$\mathcal K$ 为一个固定的插值核 fixed interpolation kernel， ${\alpha }_{i,j}^{(l)}$$\alpha_{i,j}^{(l)}$ 为可学习的插值系数。

   但是还有两个基本问题尚未解决：

   • 首先，每次计算都需要拉普拉斯矩阵的完整特征向量 eigenvectors ，因此每次前向传播、反向传播的时间复杂度至少为 $O(N^2)$$O(N^2)$ ，更不必说计算特征分解所需的 $O(N^3)$$O(N^3)$ 的复杂度。这意味着这种方法无法扩展到大型图。
   • 其次，由于滤波器取决于图的傅里叶基 basis $\mathbf{Q}$$\mathbf Q$ ，因此无法在不同图之间共享参数。

3. 有一些GCN 模型用于解决上述的第一个问题，即计算效率方向。

   • 为解决计算效率问题，ChebNet 提出使用多项式滤波器，即：

     $$\mathbf{K}=\text{diag}(g({\lambda }_1),\cdots ,g({\lambda }_N))=\sum _{k=0}^K{\theta }_k{\mathbf{\Lambda }}^k$$

     其中：

     • ${\theta }_0,\cdots ,{\theta }_K$$\theta_0,\cdots,\theta_K$ 为可学习的参数，表示多项式系数。$K$$K$ 为多项式最高阶数。
     • $\mathbf{\Lambda }=\text{diag}({\lambda }_1,\cdots ,{\lambda }_N)$$\mathbf \Lambda = \text{diag}(\lambda_1,\cdots,\lambda_N)$ 为拉普拉斯矩阵特征值组成的对角矩阵。

     然后作者使用切比雪夫多项式展开来代替矩阵的特征分解：

     $$\mathbf{K}=\sum _{k=0}^K{\theta }_k{\mathcal{T}}_k(\tilde{\mathbf{\Lambda }})$$

     其中：

     • $\tilde{\mathbf{\Lambda }}=2\mathbf{\Lambda }/{\lambda }_{max}-\mathbf{I}$$\tilde{\mathbf \Lambda} =2\mathbf \Lambda/\lambda_{\max} - \mathbf I$ 为重新缩放的特征值矩阵， ${\lambda }_{max}$$\lambda_\max$ 为最大的特征值， $\mathbf{I}\in {\mathbb{R}}^{N\times N}$$\mathbf I\in \mathbb R^{N\times N}$ 为单位矩阵。
     • ${\mathcal{T}}_k(x)$$\mathcal T_k(x)$ 为 $k$$k$ 阶切比雪夫多项式。

     由于切比雪夫多项式的正交基的要求，这里重新缩放是有必要的。

     根据 ${\mathbf{L}}^k=\mathbf{Q}{\mathbf{\Lambda }}^k{\mathbf{Q}}^{\mathrm{\top }}$$\mathbf L^k = \mathbf Q\mathbf\Lambda^k \mathbf Q^\top$ ，则有：

     $${\overrightarrow{\mathbf{u}}}^{\prime }=\mathbf{Q}\mathbf{K}{\mathbf{Q}}^{\mathrm{\top }}\overrightarrow{\mathbf{u}}=\sum _{k=0}^K{\theta }_k\mathbf{Q}{\mathcal{T}}_k(\tilde{\mathbf{\Lambda }}){\mathbf{Q}}^{\mathrm{\top }}\overrightarrow{\mathbf{u}}=\sum _{k=0}^K{\theta }_k{\mathcal{T}}_k(\tilde{\mathbf{L}})\overrightarrow{\mathbf{u}}=\sum _{k=0}^K{\theta }_k{\widetilde{\overrightarrow{\mathbf{u}}}}_k$$

     其中 ${\widetilde{\overrightarrow{\mathbf{u}}}}_k={\mathcal{T}}_k(\tilde{\mathbf{L}})\overrightarrow{\mathbf{u}}$$\tilde{\mathbf{\vec u}}_k = \mathcal T_k(\tilde{\mathbf L}) \mathbf{\vec u}$ ， $\tilde{\mathbf{L}}=2\mathbf{L}/{\lambda }_{max}-\mathbf{I}$$\tilde{\mathbf L} = 2\mathbf L/\lambda_\max - \mathbf I$ 。

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

     $$\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{u}}}}_k=2\tilde{\mathbf{L}}{\widetilde{\overrightarrow{\mathbf{u}}}}_{k-1}-{\widetilde{\overrightarrow{\mathbf{u}}}}_{k-2}\\ {\widetilde{\overrightarrow{\mathbf{u}}}}_0=\overrightarrow{\mathbf{u}},{\widetilde{\overrightarrow{\mathbf{u}}}}_1=\tilde{\mathbf{L}}\overrightarrow{\mathbf{u}}\end{array}$$

     现在仅需要计算稀疏矩阵 $\tilde{\mathbf{L}}$$\tilde{\mathbf L}$ 和某些向量的乘积，因此当使用稀疏矩阵的乘法时，时间复杂度为 $O(KM)$$O(KM)$ ，其中 $M$$M$ 为边的数量， $K$$K$ 为多项式的阶数。因此时间复杂度为边数量的线性函数。

     另外，也很容易看到这种多项式滤波器是严格地 $K$$K$ 阶局部化的：每次卷积时，节点 $v_i$$v_i$ 的 representation 仅受到它 $K$$K$ 阶邻域 ${\mathcal{N}}_K(i)$$\mathcal N_K(i)$ 的影响（因为切比雪夫多项式的最高阶次为 $K$$K$ 次）。

   • 《Semi-supervised classification with graph convolutional networks》 进一步仅使用一阶邻域来简化滤波器：

     $${\overrightarrow{\mathbf{h}}}_i^{(l+1)}=\rho \left(\sum _{j\in \tilde{\mathcal{N}}(i)}\frac{{\overrightarrow{\mathbf{h}}}_j^{(l)}{\mathbf{W}}^{(l)}}{\sqrt{{\tilde{d}}_i\times {\tilde{d}}_j}}\right)$$

     其中：

     • $\tilde{\mathcal{N}}(i)=\mathcal{N}(i)\cup \{i\}$$\tilde {\mathcal N}(i) = \mathcal N(i)\cup \{i\}$ 为添加自连接的一阶邻域， $\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$$\tilde {\mathbf A}=\mathbf A + \mathbf I$ 为添加自连接的邻接矩阵，${\tilde{d}}_i$$\tilde d_i$ 为添加自连接之后节点 $v_i$$v_i$ 的 degree 。
     • ${\overrightarrow{\mathbf{h}}}_i^{(l)}\in {\mathbb{R}}^{d_l}$$\mathbf{\vec h}_i^{(l)}\in \mathbb R^{d_l}$ 为节点 $v_i$$v_i$ 在第 $l$$l$ 层的 representation， $d_l$$d_l$ 为representation 向量的维度。

     将其写作矩阵形式为：

     $${\mathbf{H}}^{(l+1)}=\rho \left({\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)$$

     其中 $\tilde{\mathbf{D}}$$\tilde{\mathbf D}$ 为添加自连接的 degree 矩阵。

     作者表明：通过设置 $K=1$$K=1$ 以及一个微小的修改，ChebNet 滤波器等价于上式。作者认为，如下图所述堆叠足够多的卷积层具有类似于 ChebNet 的建模能力，并且会带来更好的效果。下图中，每个节点仅被它们的直接邻居所影响。

     

   • ChebNet 及其扩展方法的重要洞察 insight 是：它们将谱域图卷积和空间结构联系在一起。具体而言，它们表明：当谱域卷积为多项式时（一阶多项式也是一种多项式），谱域卷积等价于空间卷积。

     另外，卷积公式 ${\overrightarrow{\mathbf{h}}}_i^{(l+1)}=\rho \left(\sum _{j\in \tilde{\mathcal{N}}(i)}\frac{{\overrightarrow{\mathbf{h}}}_j^{(l)}{\mathbf{W}}^{(l)}}{\sqrt{{\tilde{d}}_i\times {\tilde{d}}_j}}\right)$$\mathbf{\vec h}_i^{(l+1)} = \rho\left(\sum_{j\in \tilde{\mathcal N}(i)}\frac{\mathbf{\vec h}_j^{(l)}\mathbf W^{(l)}}{\sqrt{\tilde d_i\times \tilde d_j}} \right)$ 和 GNN 中的状态定义 ${\overrightarrow{\mathbf{s}}}_i=\sum _{j\in \mathcal{N}(i)}F({\overrightarrow{\mathbf{s}}}_i,{\overrightarrow{\mathbf{s}}}_j,{\overrightarrow{\mathbf{f}}}_i^{\mathcal{V}},{\overrightarrow{\mathbf{f}}}_j^{\mathcal{V}},{\overrightarrow{\mathbf{f}}}_{i,j}^{\mathcal{E}})$$\mathbf{\vec s}_i = \sum_{j\in \mathcal N(i)} F\left(\mathbf{\vec s}_i, \mathbf{\vec s}_j, \mathbf{\vec f}_i^{\mathcal V},\mathbf{\vec f}_j^{\mathcal V},\mathbf{\vec f}_{i,j}^{\mathcal E} \right)$ 高度相似，不同之处在于用卷积定义代替了递归定义。从这个方面来看，GNN 可以被视为具有大量 identical layer （即层与层之间都相同的）以达到稳定状态的 GCN。例如， GNN 使用固定参数的固定函数来迭代更新节点的 hidden state，直到达到状态平衡为止。而 GCN 具有预设的层数，并且每层使用不同的参数。

   • 还有一些谱域方法解决效率问题。如 CayleyNet 并未使用切比雪夫多项式展开，而是采用 Cayley 多项式来定义图卷积：

     $$\mathbf{K}={\theta }_0+2\text{Re}\left\{\sum _{k=1}^K{\theta }_k{({\theta }_h\mathbf{\Lambda }-i\mathbf{I})}^k{({\theta }_h\mathbf{\Lambda }+i\mathbf{I})}^k\right\}$$

     其中 $i=\sqrt{-1}$$i=\sqrt{-1}$ 为单位虚数， ${\theta }_h$$\theta_h$ 为另一个谱域缩放参数。

     除了证明 CayLeyNet 的效率和 ChebNet 一样，作者还证明了 Caylay 多项式可以检测 narrow frequency bands of importance 从而获得更好的效果。

   • Graph wavelet neural network:GWNN 通过重写公式 ${\overrightarrow{\mathbf{u}}}_1{\ast }_G{\overrightarrow{\mathbf{u}}}_2=\mathbf{Q}(\left({\mathbf{Q}}^{\mathrm{\top }}{\overrightarrow{\mathbf{u}}}_1\right)\odot \left({\mathbf{Q}}^{\mathrm{\top }}{\overrightarrow{\mathbf{u}}}_2\right))$$\mathbf{\vec u}_1*_G \mathbf{\vec u}_2 = \mathbf Q \left(\left(\mathbf Q^\top \mathbf{\vec u}_1\right)\odot\left(\mathbf Q^\top \mathbf{\vec u}_2\right)\right)$，用图小波变换代替谱域滤波器中的傅里叶变换：

     $${\overrightarrow{\mathbf{u}}}_1{\ast }_G{\overrightarrow{\mathbf{u}}}_2=\psi (\left({\psi }^{-1}{\overrightarrow{\mathbf{u}}}_1\right)\odot \left({\psi }^{-1}{\overrightarrow{\mathbf{u}}}_2\right))$$

     其中 $\psi$$\psi$ 为图小波 graph wavelet 的基 bases。

     通过使用快速近似算法来计算 $\psi ,{\psi }^{-1}$$\psi,\psi^{-1}$，GWNN 的计算复杂度也是 $O(KM)$$O(KM)$ ，和边的数量成线性关系。

4. 有一些GCN 模型用于解决上述的第二个问题，即跨图的泛化。

   • Neural FPs 也提出一种使用一阶邻域的空间卷积方法：

     $${\overrightarrow{\mathbf{h}}}_i^{(l+1)}=\sigma \left(\sum _{j\in \tilde{\mathcal{N}}(i)}{\overrightarrow{\mathbf{h}}}_j^{(l)}{\mathbf{W}}_{\text{degree}(j)}^{(l)}\right)$$

     由于参数 ${\mathbf{W}}_{\text{degree}(j)}^{(l)}$$\mathbf W^{(l)}_{\text{degree}(j)}$ 可以在不同的图之间共享，并且和图大小无关，因此 Neural FP 可以处理任意大小的多个图。注意这里 ${\mathbf{W}}_{\text{degree}(j)}^{(l)}$$\mathbf W^{(l)}_{\text{degree}(j)}$ 根据节点的 degree 不同而不同。

     上式和 《Semi-supervised classification with graph convolutional networks》 提出的滤波器非常相似，区别在于：Neural FP 不是通过添加归一化项来考虑节点 degree 的影响，而是为不同 degree 的节点学习不同的参数。该策略对于较小的图（如分子图）效果很好，但是无法扩展到更大的图。

   • PATCHY-SAN 使用诸如 Weisfeiler-Lehman kernel 之类的图 labeling 过程为节点分配了唯一的节点顺序，然后使用这个预分配的顺序将节点邻居排列。

     然后 PATCHY-SAN 通过从节点的 $k$$k$ 阶邻域 ${\mathcal{N}}_k(i)$$\mathcal N_k(i)$ 中选择固定数量的节点，从而为每个节点 $v_i$$v_i$ 定义了一个感受野 receptive field 。

     最后，PATCHY-SAN 采用一个标准的、带适当 normalization 的一维 CNN 到这个感受野上。

     通过这种方式，不同的图中的节点都具有固定大小和顺序的感受野，因此 PATCHY-SAN 可以从多个图中学习，就像正常的 CNN 从多个图像中学习一样。

     这种方式的缺点是卷积在很大程度上依赖于图 labeling 过程，而图 labeling 过程是一个预处理步骤，它并不是学习的一部分（即没有可学习的参数）。

     • LGCN 进一步提出通过按字典顺序简化排序过程。即根据邻居在最后一层 hidden representation ${\mathbf{H}}^{(L)}$$\mathbf H^{(L)}$ 来排序。作者并没有使用一个单一的排序，而是分别对 ${\mathbf{H}}^{(L)}$$\mathbf H^{(L)}$ 的不同维度（即通道）进行排序。
     • SortPooling 采用了类似的方法，但是它并不是对每个节点的邻居进行排序，而是对所有节点进行排序。即所有节点的所有邻域的排序都相同。

     尽管这些方法之间存在差异，但是对于图来说，强制采用一维节点顺序可能不是很自然的选择。

   • GCNN 采用 diffusion-basis 来代替图卷积中的 eigen-basis ，即节点的邻域由节点之间的扩散转移概率 diffusion transition probability 来决定。

     具体而言，卷积定义为：

     $${\mathbf{H}}^{(l+1)}=\rho \left({\mathbf{P}}^K{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)$$

     其中 $\mathbf{P}={\mathbf{D}}^{-1}\mathbf{A}$$\mathbf P=\mathbf D^{-1}\mathbf A$ 为节点之间的一阶转移概率， ${\mathbf{P}}^K=\underset{K}{\underbrace{\mathbf{P}\cdots \mathbf{P}}}$$\mathbf P^K = \underbrace{\mathbf P \cdots\mathbf P}_{K}$ 为节点之间的 $K$$K$ 阶转移概率。$K$$K$ 为预设的扩散长度。${\mathbf{W}}^{(l)}$$\mathbf W^{(l)}$ 为可学习的参数矩阵，可以在任意大小的图之间共享。

     但是，计算 ${\mathbf{P}}^K$$\mathbf P^K$ 的时间复杂度为 $O(N^{2}K)$$O(N^2K)$ ，因此该方法无法扩展到大图。

   • DGCN 通过一个对偶图卷积 dual graph convolutional 框架来同时使用 diffusion base 和 adjacent base 。具体而言，DGCN 使用两个卷积：

     • 一个是邻接矩阵的形式：${\mathbf{H}}^{(l+1)}=\rho \left({\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)$$\mathbf H^{(l+1)} = \rho\left(\tilde{\mathbf D}^{-1/2} \tilde{\mathbf A}\tilde{\mathbf D}^{-1/2} \mathbf H^{(l)} \mathbf W^{(l)}\right)$ 。

     • 另一个是将转移概率中的邻接矩阵转换为 pointwise mutual information:PPMI ：

       $${\mathbf{Z}}^{(l+1)}=\rho \left({\mathbf{D}}_P^{-1/2}{\mathbf{M}}_P{\mathbf{D}}_P^{-1/2}{\mathbf{Z}}^{(l)}{\mathbf{W}}^{(l)}\right)$$

       其中 ${\mathbf{M}}_P$$\mathbf M_P$ 为 PPMI 矩阵：

       $$M_P(i,j)=max(\log \left(\frac{P(i,j)\sum _{i,j}P(i,j)}{\sum _{i}P(i,j)\sum _{j}P(i,j)}\right),0)$$

       $P(i,j)$$P(i,j)$ 为节点 $v_i,v_j$$v_i,v_j$ 之间的转移概率， $D_P(i,i)=\sum _j{M}_P(i,j)$$D_P(i,i) = \sum_j M_P(i,j)$ 为基于 ${\mathbf{M}}_P$$\mathbf M_P$ 的对角 degree 矩阵。

     然后 DGCN 通过最小化 $\mathbf{H}$$\mathbf H$ 和 $\mathbf{Z}$$\mathbf Z$ 之间的均方差来 ensemble 这两个卷积。

     DGCN 通过随机游走采样技术来加速转移概率的计算。实验表明：这种对偶卷积甚至对于单图问题single-graph problem也是有效的。

b. 空域卷积

1. 基于谱域卷积的工作，《Neural message passing for quantum chemistry 》提出了MPNNs 为图的空域卷积提出了一个统一的框架，它使用消息传递函数 message-passing function：

   $$\begin{array}{c}{\overrightarrow{\mathbf{m}}}_i^{(l+1)}=\sum _{j\in \mathcal{N}(i)}{F}^{(l)}({\overrightarrow{\mathbf{h}}}_i^{(l)},{\overrightarrow{\mathbf{h}}}_j^{(l)},{\overrightarrow{\mathbf{f}}}_{i,j}^{\mathcal{E}})\\ {\overrightarrow{\mathbf{h}}}_i^{l+1}=G^{(l)}({\overrightarrow{\mathbf{h}}}_i^{(l)},{\overrightarrow{\mathbf{m}}}_i^{(l+1)})\end{array}$$

   其中：

   • $F^{(l)}(\cdot )$$F^{(l)}(\cdot)$ 为第 $l$$l$ 层待学习的消息函数。
   • $G^{(l)}(\cdot )$$G^{(l)}(\cdot)$ 为第 $l$$l$ 层待学习的节点更新函数。
   • ${\overrightarrow{\mathbf{m}}}_i^{(l)}$$\mathbf{\vec m}_i^{(l)}$ 为第 $l$$l$ 层节点 $v_i$$v_i$ 的邻域和该节点之间传递的消息。

   从概念上讲MPNN 是一个框架，在该框架中，每个节点都根据其状态发送消息，并根据从直接邻居中收到的消息来更新节点状态。作者表明：上述框架已经包含了很多现代方法，如 GGSNNs、Neural FPs 等都是特例。

   另外，作者建议添加一个 master 节点，该节点连接图中所有其它节点从而加速长程消息传递。并且作者拆分 hidden representation 到不同的 tower 来提高泛化能力。作者表明：MPNNs 的特定变体可以在预测分子特性方面达到 state-of-the-art 性能。

2. GraphSAGE 采用类似 message-passing function 的思想，它使用聚合函数：

   $$\begin{array}{c}{\overrightarrow{\mathbf{m}}}_i^{(l+1)}={\text{AGG}}^{(l)}\left(\{{\overrightarrow{\mathbf{h}}}_j^{(l)},\mathrm{\forall }j\in \mathcal{N}(i)\}\right)\\ {\overrightarrow{\mathbf{h}}}_i^{(l+1)}=\rho \left({\mathbf{W}}^l[{\overrightarrow{\mathbf{h}}}_i^{(l)},{\overrightarrow{\mathbf{m}}}_i^{(l+1)}]\right)\end{array}$$

   其中 $[\cdot ,\cdot ]$$[\cdot,\cdot]$ 是向量拼接操作， AGG(.) 表示聚合函数。

   作者提出三个聚合函数：均值池化、LSTM 、最大池化。例如对于最大池化有：

   $${\text{AGG}}^{(l)}=max\{\rho ({\mathbf{W}}_{\text{pool}}{\overrightarrow{\mathbf{h}}}_j^{(l)}+{\overrightarrow{\mathbf{b}}}_{\text{pool}}),\mathrm{\forall }j\in \mathcal{N}(i)\}$$

   其中 ${\mathbf{W}}_{\text{pool}},{\overrightarrow{\mathbf{b}}}_{\text{pool}}$$\mathbf W_{\text{pool}}, \mathbf{\vec b}_{\text{pool}}$ 是待学习的参数，$max\{\cdot \}$$\max\{\cdot\}$ 为逐元素最大值函数。

   对于 LSTM 聚合函数，由于需要确定邻域顺序，因此作者采用了最简单的随机顺序。

3. Mixture model network:MoNet 也尝试使用 “模板匹配“template matching ” 将现有的 GCN 模型以及用于流形 manifold 的 CNN 模型统一到一个通用框架中：

   $$h_{i,k}^{l+1}=\sum _{j\in \mathcal{N}(i)}{F}_k^{(l)}(\overrightarrow{\mathbf{u}}(i,j))\cdot {\overrightarrow{\mathbf{h}}}_j^{(l)},k=1,\cdots ,d_{l+1}$$

   其中：

   • $\overrightarrow{\mathbf{u}}(i,j)$$\mathbf{\vec u}(i,j)$ 为节点 pair 对 $(v_i,v_j)$$(v_i,v_j)$ 的伪坐标 pseudo-coordinates ，定义为：

     $$\overrightarrow{\mathbf{u}}(i,j)=(\frac{1}{D(i,i)},\frac{1}{D(j,j)})$$

     其中 $D(i,i)$$D(i,i)$ 为节点 $v_i$$v_i$ 的 degree 。

   • $F_k^{(l)}(\overrightarrow{\mathbf{u}})$$F_k^{(l)}(\mathbf{\vec u})$ 为待学习的函数，它返回一个向量。

   • $h_{i,k}^{(l)}$$h_{i,k}^{(l)}$ 为 ${\overrightarrow{\mathbf{h}}}_i^{(l)}$$\mathbf{\vec h}_i^{(l)}$ 的第 $k$$k$ 维。

   换句话讲， $F_k^{(l)}(\overrightarrow{\mathbf{u}})$$F_k^{(l)}(\mathbf{\vec u})$ 作为组合邻域的加权 kernel 。然后 MoNet 采用以下高斯核：

   $$F_k^{(l)}(\overrightarrow{\mathbf{u}})=\exp (-\frac{1}{2}{(\overrightarrow{\mathbf{u}}-{\overrightarrow{\mu }}_k^{(l)})}^{\mathrm{\top }}{\left({\mathrm{\Sigma }}_k^{(l)}\right)}^{-1}(\overrightarrow{\mathbf{u}}-{\overrightarrow{\mu }}_k^{(l)}))$$

   其中 ${\overrightarrow{\mu }}_k^{(l)}$$\vec\mu_k^{(l)}$ 和 ${\mathrm{\Sigma }}_k^{(l)}$$\Sigma_{k}^{(l)}$ 为待学习的均值向量和对角方差矩阵。

4. Graph Network:GNs 提出了一个比 GCNs、GNNs 更通用的框架，它学习三组 representation ：

   $$\left\{{\overrightarrow{\mathbf{h}}}_i^{(l)}\right\},\left\{{\overrightarrow{\mathbf{e}}}_{i,j}^{(l)}\right\},\left\{{\overrightarrow{\mathbf{z}}}^{(l)}\right\}$$

   分别代表节点 embedding、边 embedding、整个图的 embedding 。

   这些 representation 通过三个聚合函数、三个更新函数来学习：

   $$\begin{array}{c}{\overrightarrow{\mathbf{m}}}_i^{(l)}=G^{\mathcal{E}\to \mathcal{V}}\left(\{{\overrightarrow{\mathbf{e}}}_{i,j}^{(l)},\mathrm{\forall }j\in \mathcal{N}(i)\}\right)\\ {\overrightarrow{\mathbf{m}}}_{\mathcal{V}}^{(l)}=G^{\mathcal{V}\to \mathcal{G}}\left(\{{\overrightarrow{\mathbf{h}}}_i^{(l)},\mathrm{\forall }{v}_i\in \mathcal{V}\}\right)\\ {\overrightarrow{\mathbf{m}}}_{\mathcal{E}}^{(l)}=G^{\mathcal{E}\to \mathcal{G}}\left(\{{\overrightarrow{\mathbf{e}}}_{i,j}^{(l)},\mathrm{\forall }(v_i,v_j)\in \mathcal{E}\}\right)\\ {\overrightarrow{\mathbf{h}}}_i^{(l+1)}=F^{\mathcal{V}}({\overrightarrow{\mathbf{m}}}_i^{(l)},{\overrightarrow{\mathbf{h}}}_i^{(l)},{\overrightarrow{\mathbf{z}}}^{(l)})\\ {\overrightarrow{\mathbf{e}}}_{i,j}^{(l+1)}=F^{\mathcal{E}}({\overrightarrow{\mathbf{e}}}_{i,j}^{(l)},{\overrightarrow{\mathbf{h}}}_i^{(l)},{\overrightarrow{\mathbf{h}}}_j^{(l)},{\overrightarrow{\mathbf{z}}}^{(l)})\\ {\overrightarrow{\mathbf{z}}}^{(l+1)}=F^{\mathcal{G}}({\overrightarrow{\mathbf{m}}}_{\mathcal{E}}^{(l)},{\overrightarrow{\mathbf{m}}}_{\mathcal{V}}^{(l)},{\overrightarrow{\mathbf{z}}}^{(l)})\end{array}$$

   其中：

   • $F^{\mathcal{V}}(\cdot ),F^{\mathcal{E}}(\cdot ),F^{\mathcal{G}}(\cdot )$$F^{\mathcal V}(\cdot), F^{\mathcal E}(\cdot), F^{\mathcal G}(\cdot)$ 对应于节点更函数、边更新函数、全图更新函数。
   • $G^{\cdot \to \cdot }(\cdot )$$G^{\cdot \rightarrow \cdot }(\cdot)$ 对应于消息传递函数，上标表示消息传递的方向。

   注意：消息传递函数都是以集合作为输入，因此它们的参数是可变数量的。因此这些消息传递函数对于输入的不同排列应该是不变的。一些排列不变的函数包括逐元素求和、均值池化、最大池化。

   和 MPNN 相比，GNs 引入了边的 representation 和全图 representation，从而使得框架更加通用。

5. 总而言之，卷积运算已经从谱域发展到频域，并从 k-hop 邻域发展到直接邻域。目前，从直接邻域收集消息，如 ${\mathbf{H}}^{(l+1)}=\rho \left({\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)$$\mathbf H^{(l+1)} = \rho\left(\tilde{\mathbf D}^{-1/2} \tilde{\mathbf A}\tilde{\mathbf D}^{-1/2} \mathbf H^{(l)} \mathbf W^{(l)}\right)$ ， 并遵循 message-passing function、GraphSAGE aggregating functions 、GNet aggretation/ update functions 是图卷积运算最常见的选择。

1.3.2 Readout 操作

1. 使用图卷积操作可以学到有效的节点 representation 从而解决 node-level 任务。但是，为处理 graph-level 任务，需要聚合节点信息来构成 graph-level representation 。在文献中，这种聚合过程被称作 readout 操作。

   基于规则的局部邻域，标准的 CNN 可以执行步长大于 1 的卷积或池化操作来逐渐降低分辨率，从而得到 graph-level representation 。而图缺乏网格结构，因此无法直接应用现有的这些方法。

2. 顺序不变性 order invariance：图的 readout 操作的关键要求是该操作不应依赖于节点顺序。即，如果我们改变节点编号和边的编号（编号改变意味着顺序改变），则整个图的 representation 不应改变。

   例如，一种药物是否可以治疗某些疾病取决于其固有结构，和我们对节点的编号顺序无关。如果我们采用不同的编号顺序，则应该得到相同的结果。

   注意：

   • 这个问题和图同构 isomorphism 问题有关，其中最著名的算法是拟多项式的 quasipolynomial ，所以我们只能找到多项式时间内 order-invariant 的函数。
   • 同构的两个图得到相同的 representation，反之不一定成立。即相同 representation 的两个图不一定是同构的 。

3. 统计量：最常见的顺序无关算子包括简单的统计量 statistics ，如求和、均值池化、最大池化：

   $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_{\mathcal{G}}=\sum _{i=1}^N{\overrightarrow{\mathbf{h}}}_i^{(L)}\\ {\overrightarrow{\mathbf{h}}}_{\mathcal{G}}=\frac{1}{N}\sum _{i=1}^N{\overrightarrow{\mathbf{h}}}_i^{(L)}\\ {\overrightarrow{\mathbf{h}}}_{\mathcal{G}}=max\{{\overrightarrow{\mathbf{h}}}_i^{(L)},\mathrm{\forall }{v}_i\in \mathcal{V}\}\end{array}$$

   其中： ${\overrightarrow{\mathbf{h}}}_G$$\mathbf{\vec h}_G$ 为图 $\mathcal{G}$$\mathcal G$ 的 representation ； ${\overrightarrow{\mathbf{h}}}_i^{(L)}$$\mathbf{\vec h}_i^{(L)}$ 为节点 $v_i$$v_i$ 在最后一层（第 $L$$L$ 层）的 representation 。

   这种一阶统计量虽然简单，但是不足以刻画不同的图结构。

   • 论文 《Molecular graph convolutions: moving beyond fingerprints》 建议通过使用模糊直方图 fuzzy histograms 来考虑节点 representation 的分布。

     模糊直方图背后的基本思想是：构建几个直方图分桶 histogram bins，然后计算 ${\overrightarrow{\mathbf{h}}}_i^{(L)}$$\mathbf{\vec h}_i^{(L)}$ 归属于哪个分桶。即，通过将节点 representation 作为样本，将它们和一些预定义的模板（每个模板代表一个分桶）进行匹配，最后返回最终直方图的拼接 concatenation 。通过这种方式，可以区分具有相同的 sum/average/maximum、但是具有不同节点分布的图。

   • 在论文 《Spectral networks and locally connected networks on graphs 》 中，作者采用了常用的一种方法：添加一个全连接层 FC 作为final layer ：

     $${\overrightarrow{\mathbf{h}}}_{\mathcal{G}}=\rho \left([{\overrightarrow{\mathbf{h}}}_1^{(L)},\cdots ,{\overrightarrow{\mathbf{h}}}_N^{(L)}]{\mathbf{W}}_{FC}\right)$$

     其中 $[\cdots ]$$[\cdots]$ 表示向量拼接， ${\mathbf{W}}_{FC}\in {\mathbb{R}}^{(N{d}_L)\times d_{out}}$$\mathbf W_{FC}\in \mathbb R^{(Nd_L)\times d_{out}}$ ， $d_{out}$$d_{out}$ 为输出向量维度。

     上式可以视为 node-level representation 的加权和。优点之一是该模型可以为不同节点学习不同的加权权重。但是，这种能力是以无法保证顺序不变性为代价的。

4. 层次聚类：实际上图具有丰富的层次结构，而不仅仅是 node-level、graph-level 这两层结构。可以通过层次聚类 hierarchical clustering 的方式来探索图的层次结构，如下图所示。

   

   • 《Spectral networks and locally connected networks on graphs》 使用了基于密度的 agglomerative 聚类，《Deep convolutional networks on graph-structured data》 使用了多分辨率谱聚类。ChebNet 和 MoNet 使用了另一种贪婪的层次聚类算法 Graclus 来一次合并两个节点，并采用了一种快速池化的方法将节点重新排列为平衡二叉树。ECC 通过执行特征分解来使用另一种层次聚类方法。

     但是，这些层次聚类方法都和图卷积无关，而是作为预处理步骤进行的，并且无法以端到端的方式进行训练。

   • 为解决这个问题，DiffPool 提出了一种与图卷积联合训练的、可微的层次聚类算法。具体而言，作者提出使用 hidden representation 来学习每个层次中的 soft cluster assignment 矩阵。

     $${\mathbf{S}}^{(l)}=F({\mathbf{A}}^{(l)},{\mathbf{H}}^{(l)})$$

     其中：

     • ${\mathbf{S}}^{(l)}\in {\mathbb{R}}^{N_l\times N_{l+1}}$$\mathbf S^{(l)}\in \mathbb R^{N_l\times N_{l+1}}$ 是 cluster assignment 矩阵，$N_l$$N_l$ 是层次中第 $l$$l$ 层的聚类簇的数量。
     • ${\mathbf{A}}^{(l)}$$\mathbf A^{(l)}$ 是层次中第 $l$$l$ 层的邻接矩阵。
     • ${\mathbf{H}}^{(l)}$$\mathbf H^{(l)}$ 是层次中第 $l$$l$ 层的 hidden representation 。
     • $F(\cdot )$$F(\cdot)$ 是待学习的函数。

     然后根据 ${\mathbf{S}}^{(l)}$$\mathbf S^{(l)}$ 取均值，可以得到粗化coarsened 图的node representation和新的邻接矩阵：

     $${\mathbf{H}}^{(l+1)}={\left({\mathbf{S}}^{(l)}\right)}^{\mathrm{\top }}{\hat{\mathbf{H}}}^{(l+1)},{\mathbf{A}}^{(l+1)}={\left({\mathbf{S}}^{(l)}\right)}^{\mathrm{\top }}{\mathbf{A}}^{(l)}{\mathbf{S}}^{(l)}$$

     其中 ${\hat{\mathbf{H}}}^{(l+1)}$$\hat{\mathbf H}^{(l+1)}$ 为对 ${\mathbf{H}}^{(l)}$$\mathbf H^{(l)}$ 应用一个图卷积层得到。

     因此，在 DiffPool 中每一层的卷积操作之后，图从 $N_l$$N_l$ 个节点被粗化到 $N_{l+1}$$N_{l+1}$ 个节点。初始图的节点数量为 $N_0=N$$N_0 = N$ ， 最终图的节点数量为 $N_L=1$$N_L = 1$ （即整个图只有单个节点）。因为 cluster assignment 操作是 soft 的，因此簇之间的连接并不是稀疏的，因此该方法的时间复杂度原则上为 $O(N^2)$$O(N^2)$ 。

5. 强加顺序：如前所述，PATCHY-SAN 和 SortPooling 采用强加节点顺序impose order的思想 ，然后像 CNN 一样采用标准的一维池化。这些方法是否可以保留顺序不变性，取决于强加顺序的方式，这是另一个研究领域。

   除了强加节点顺序之外，还有一些启发式方法。在 GNN 中，作者建议添加一个连接到所有节点的特殊节点从而代表整个图。同样地，GNs 提出通过从所有节点和所有边接收消息来直接学习整个图的 representation 。

6. MPNNs 采用 set2set，这是对 seq2seq 模型的修改。具体而言，set2set 使用 Read-Process-Write 模型，该模型同时接收所有输入，使用 attention 机制和 LSTM 计算内部状态，然后写入输出。

   和 seq2seq 的顺序敏感性不同，set2set 对于输入是顺序不变的。

7. 简而言之，诸如均值、求和之类的统计量是最简单的 Readout 操作，而通过图卷积联合训练的层次聚类算法更加先进、也更复杂。还有一些其它的方法，如添加虚拟节点来代表图、或强加节点顺序。

1.3.3 改进

1. 已有很多技术用于进一步改善 GCN。注意，其中一些方法是通用的，也可以应用于图上的其它深度学习模型。

2. attention 机制：上述 GCN 中，邻域节点以相等或预定义的权重进行聚合。但是邻域节点的影响力可能差异很大，因此应该在训练过程中学习它们，而不是预先确定。

   受注意力机制的启发，图注意力网络 graph attention network:GAT 通过修改 ${\overrightarrow{\mathbf{h}}}_i^{(l+1)}=\rho \left(\sum _{j\in \tilde{\mathcal{N}}(i)}\frac{{\overrightarrow{\mathbf{h}}}_j^{(l)}{\mathbf{W}}^{(l)}}{\sqrt{{\tilde{d}}_i\times {\tilde{d}}_j}}\right)$$\mathbf{\vec h}_i^{(l+1)} = \rho\left(\sum_{j\in \tilde{\mathcal N}(i)}\frac{\mathbf{\vec h}_j^{(l)}\mathbf W^{(l)}}{\sqrt{\tilde d_i\times \tilde d_j}} \right)$ ，从而将注意力机制引入 GCN：

   $${\overrightarrow{\mathbf{h}}}_i^{(l+1)}=\rho \left(\sum _{j\in \tilde{\mathcal{N}}(i)}{\alpha }_{i,j}^{(l)}{\overrightarrow{\mathbf{h}}}_j^{(l)}{\mathbf{W}}^{(l)}\right)$$

   其中 ${\alpha }_{i,j}^{(l)}$$\alpha^{(l)}_{i,j}$ 为第 $l$$l$ 层中，节点 $v_j$$v_j$ 对于节点 $v_i$$v_i$ 的注意力：

   $${\alpha }_{i,j}^{(l)}=\frac{\exp \left(\text{LeakyReLU}\left(F({\overrightarrow{\mathbf{h}}}_i^{(l)}{\mathbf{W}}^{(l)},{\overrightarrow{\mathbf{h}}}_j^{(l)}{\mathbf{W}}^{(l)})\right)\right)}{\sum _{k\in \hat{\mathcal{N}}(i)}\exp \left(\text{LeakyReLU}\left(F({\overrightarrow{\mathbf{h}}}_i^{(l)}{\mathbf{W}}^{(l)},{\overrightarrow{\mathbf{h}}}_k^{(l)}{\mathbf{W}}^{(l)})\right)\right)}$$

   其中 $F(\cdot ,\cdot )$$F(\cdot,\cdot)$ 为待学习的函数，如多层感知机 MLP 。

   可以看到 ${\alpha }_{i,j}^{(l)}$$\alpha^{(l)}_{i,j}$ 满足：$\sum _j{\alpha }_{i,j}^{(l)}=1.0,0.0<{\alpha }_{i,j}^{(l)}<1.0$$\sum_j \alpha_{i,j}^{(l)} = 1.0,\quad 0.0\lt \alpha_{i,j}^{(l)}\lt 1.0$ 。

   为提高模型的容量和稳定性，作者还提出使用多个独立的注意力，并将其结果进行合并。即下图所述的多头注意力机制 multi-head attention mechanism 。每种颜色代表不同的、独立的注意力向量。

   

   GaAN 进一步提出针对不同的 head 学习不同的权重，并将这种方法应用于交通预测问题。

   HAN 提出针对异质图的 two-level 注意力机制，即 node-level 注意力和 semantic-level 注意力。具体而言：

   • node-level 注意力机制类似于 GAT，但是也考虑了节点类型。因此它可以分配不同的权重来聚合 metapath-based 邻域。
   • 然后，semantic-level 注意力机制学习不同 metapath 的重要性，并输出最终结果。

3. 残差和跳跃连接：很多研究观察到，现有 GCN 最合适的深度通常非常有限，如 2 层或 3 层。这个问题可能是由于训练深层 GCN 时比较困难，或者过度平滑 over-smoothing 问题导致。过度平滑问题是指：深层GCN 中，所有节点都具有相同的 representation。

   为解决这些问题，可以考虑将类似 ResNet 的残差连接添加到 GCN 中。

   • 《Semi-supervised classification with graph convolutional networks》 在公式 ${\mathbf{H}}^{(l+1)}=\rho \left({\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)$$\mathbf H^{(l+1)} = \rho\left(\tilde{\mathbf D}^{-1/2} \tilde{\mathbf A}\tilde{\mathbf D}^{-1/2} \mathbf H^{(l)} \mathbf W^{(l)}\right)$ 中添加了残差连接 residual connection：

     $${\mathbf{H}}^{(l+1)}=\rho \left({\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)+{\mathbf{H}}^{(l)}$$

     他们通过实验表明：通过添加此类残差连接可以使得网络深度更深，这和 ResNet 结果类似。

   • Column network:CLN 采取了类似的思想，它使用以下具有可学习权重的残差连接：

     $$\begin{array}{c}{\widetilde{\overrightarrow{\mathbf{h}}}}_i^{(l+1)}=\rho \left(\sum _{j\in \tilde{\mathcal{N}}(i)}\frac{{\overrightarrow{\mathbf{h}}}_j^{(l)}{\mathbf{W}}^{(l)}}{\sqrt{{\tilde{d}}_i\times {\tilde{d}}_j}}\right)\\ {\overrightarrow{\mathbf{h}}}_i^{(l+1)}={\overrightarrow{\alpha }}_i^{(l)}\odot {\widetilde{\overrightarrow{\mathbf{h}}}}_i^{(l+1)}+(1-{\overrightarrow{\alpha }}_i^{(l)})\odot {\overrightarrow{\mathbf{h}}}_i^{(l)}\end{array}$$

     其中 ${\overrightarrow{\alpha }}_i^{(l)}$$\vec \alpha_i^{(l)}$ 为一组权重：

     $${\overrightarrow{\alpha }}_i^{(l)}=\rho ({\overrightarrow{\mathbf{b}}}_{\alpha }^{(l)}+{\mathbf{W}}_{\alpha ,1}^{(l)}{\overrightarrow{\mathbf{h}}}_i^{(l)}+{\mathbf{W}}_{\alpha ,2}^{(l)}\sum _{j\in \mathcal{N}(i)}{\overrightarrow{\mathbf{h}}}_j^{(l)})$$

     其中 ${\overrightarrow{\mathbf{b}}}_{\alpha }^{(l)},{\mathbf{W}}_{\alpha ,1}^{(l)},{\mathbf{W}}_{\alpha ,2}^{(l)}$$\mathbf{\vec b}_\alpha^{(l)}, \mathbf W_{\alpha,1}^{ (l)},\mathbf W_{\alpha,2}^{ (l)}$ 为模型参数。

     注意：${\overrightarrow{\mathbf{h}}}_i^{(l+1)}={\overrightarrow{\alpha }}_i^{(l)}\odot {\widetilde{\overrightarrow{\mathbf{h}}}}_i^{(l+1)}+(1-{\overrightarrow{\alpha }}_i^{(l)})\odot {\overrightarrow{\mathbf{h}}}_i^{(l)}$$\mathbf{\vec h}_i^{(l+1)} = \vec \alpha_i^{(l)}\odot \tilde{\mathbf{\vec h}}_i^{(l+1)} + (1-\vec \alpha_i^{(l)})\odot \mathbf{\vec h}_i^{(l)}$ 非常类似于 GGS-NNs 中的 GRU 。区别在于：这里的上标表示层数，不同的层包含不同的参数；在 GRU 中上标表示时间，并且跨不同时间步共享同一组参数。

   • 受到 personalized PageRank 启发，PPNP 定义如下的卷积层：

     $${\mathbf{H}}^{(l+1)}=(1-\alpha ){\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}{\mathbf{H}}^{(l)}+\alpha {\mathbf{H}}^{(0)}$$

     其中 ${\mathbf{H}}^{(0)}=F_{\theta }\left({\mathbf{F}}^{\mathcal{V}}\right)$$\mathbf H^{(0)} = F_\theta\left(\mathbf F^\mathcal V\right)$ ， $\alpha$$\alpha$ 为超参数。

     注意：PPNP 的所有参数都在 $F_{\theta }(\cdot )$$F_\theta(\cdot)$ 中，而不是在卷积层中。

   • JK-Net 提出另一种体系结构，它将网络的最后一层和所有较低的 hidden layer 相连，即通过将所有 representation 跳跃到最终输出，如下图所述。这样，模型可以自适应地学习利用来自不同层的信息。

     正式地，JK-Net 定义为：

     $${\overrightarrow{\mathbf{h}}}_i^{(\text{final})}=\text{AGG}({\overrightarrow{\mathbf{h}}}_i^{(0)},{\overrightarrow{\mathbf{h}}}_i^{(1)},\cdots ,{\overrightarrow{\mathbf{h}}}_i^{(L)})$$

     其中：

     • ${\overrightarrow{\mathbf{h}}}_i^{(\text{final})}$$\mathbf{\vec h}_i^{(\text{final})}$ 为节点 $v_i$$v_i$ 的最终 representation。
     • $\text{AGG}(\cdot )$$\text{AGG}(\cdot)$ 为聚合函数。JK-Net 使用三个类似于 GraphSAGE 的聚合函数：拼接 concatenation、最大池化 max-pooling、LSTM attention 。
     • $L$$L$ 为网络层数。

     实验结果表明：添加跳跃连接可以提高 GCN 的性能。

     

4. edge 特征：前面提到的 GCN 大多数聚焦于利用节点特征和图结构，这里我们讨论如何利用另一个重要的信息源：边特征。

   对于具有离散值（如边类型）的简单边特征，一种直接的方法是为不同的边类型训练不同的参数，然后对结果进行聚合。

   • Neural FPs 为不同 degree 的节点训练了不同的参数，这对应于分子图中不同化学键类型的隐式边特征，然后对结果进行求和。
   • CLN 在异质图中为不同的边类型训练不同的参数，然后对结果取均值。
   • Edge-conditioned convolution:ECC 也基于边类型训练了不同的参数，并将其应用于图分类。
   • Relational GCNs: R-GCNs 通过为不同的关系类型训练不同的权重，对知识图谱采用了类似的方法。

   但是这些方法仅适用于有限数量的、离散的边特征discrete edge feature 。

   • DCNN 将每条边转换为一个节点，该节点和该边的 head node, tail node 相连。进行转换之后，可以将边特征视为节点特征。

   • LGCN 构建一个线性图 line graph $\mathbf{B}\in {\mathbb{R}}^{2M\times 2M}$$\mathbf B\in \mathbb R^{2M\times 2M}$ 来融合边特征。线性图的 ”节点“ 是原始图中的边，如果信息流经原始图中的两条边，则它们在线性图中的 ”节点“ 是相连的。

     $$\begin{array}{c}{B}_{i\to j,i^{\prime }\to j^{\prime }}=\{\begin{array}{ll}1& \text{ if }j=i^{\prime }\text{ and }{j}^{\prime }\ne i\\ 0& \text{ else}\end{array}\end{array}$$

     即 $(i\to j)$$(i\rightarrow j)$ 和 $(i^{\prime }\to j^{\prime })$$(i^\prime \rightarrow j^\prime)$ 均为线性图中的节点。

     然后 LGCN 采用两个 GCN：一个位于原始图上、另一个位于线性图上。

   • 《Molecular graph convolutions: moving beyond fingerprints》 提出了一个使用 weave module 的架构。具体而言，他们学习了节点和边的representation，并使用四个不同的函数在每个 weave module 中交换它们之间的信息：节点到节点 node-to-node:NN、节点到边 node-to-edge:NE、边到边 edge-to-edge:EE、边到节点 edge-to-node:EN 。

     $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_i^{(l{)}^{\prime }}=F_{NN}({\overrightarrow{\mathbf{h}}}_i^{(0)},{\overrightarrow{\mathbf{h}}}_i^{(1)},\cdots ,{\overrightarrow{\mathbf{h}}}_i^{(l)})\\ {\overrightarrow{\mathbf{h}}}_i^{(l{)}^{\prime \prime }}=F_{EN}\left(\{{\overrightarrow{\mathbf{e}}}_{i,j}^{(l)}\mid j\in \mathcal{N}(i)\}\right)\\ {\overrightarrow{\mathbf{e}}}_{i,j}^{(l{)}^{\prime }}=F_{EE}({\overrightarrow{\mathbf{e}}}_{i,j}^{(0)},{\overrightarrow{\mathbf{e}}}_{i,j}^{(1)},\cdots ,{\overrightarrow{\mathbf{e}}}_{i,j}^{(l)})\\ {\overrightarrow{\mathbf{e}}}_{i,j}^{(l{)}^{\prime \prime }}=F_{NE}({\overrightarrow{\mathbf{h}}}_i^{(l)},{\overrightarrow{\mathbf{h}}}_j^{(l)})\\ {\overrightarrow{\mathbf{h}}}_i^{(l+1)}=F_{NN}({\overrightarrow{\mathbf{h}}}_i^{(l{)}^{\prime }},{\overrightarrow{\mathbf{h}}}_i^{(l{)}^{\prime \prime }})\\ {\overrightarrow{\mathbf{e}}}_{i,j}^{(l+1)}=F_{EE}({\overrightarrow{\mathbf{e}}}_{i,j}^{(l{)}^{\prime }},{\overrightarrow{\mathbf{e}}}_{i,j}^{(l{)}^{\prime \prime }})\end{array}$$

     其中：

     • ${\overrightarrow{\mathbf{e}}}_{i,j}^{(l)}$$\mathbf{\vec e}_{i,j}^{(l)}$ 为边 $(v_i,v_j)$$(v_i,v_j)$ 在第 $l$$l$ 层的 representation 。
     • $F(\cdot )$$F(\cdot)$ 为可学习的函数，其下标表示消息传递的方向。

     通过堆叠多个这样的 module ，信息可以在节点 representation 和边representation 之间交替传递。

     注意：在节点到节点的函数、边到边的函数中，隐式添加了 JK-Nets 相似的跳跃连接。

   • GNs 还提出了学习边的 representation，并通过消息传递函数来同时更新 node representation 和 edge representation 。这这一方面，weave module 是 GNs 的特例，这个特例并不学习整个图的representation 。

5. 采样：在大型图上训练 GCN 时，关键的瓶颈之一是计算效率。如前所述，许多 GCN 采用邻域聚合方案。但是，由于很多真实场景的图遵循幂律分布 power-low distribution，其中少量节点的 degree 非常大、大量节点的 degree 非常小，因此不同节点的邻域规模差异很大。

   为解决这个问题，已经提出两种类型的采用方法：邻域采样 neighborhood samplings 、逐层采样 layer-wise samplings 。如下图所示，其中蓝色节点表示一个 batch 的样本，箭头表示采样方向，B 中的红色节点表示历史采样样本。

   • 在邻域采样中，GCN 在计算期间对每个节点执行采样。

     • GraphSAGE 在训练期间为每个节点统一采样固定数量的邻居。
     • PinSage 提出在图上使用随机游走对邻域进行采样，同时还有一些实现方面的改进，包括 CPU 和 GPU 之间的协同、一个 map-reduce inference pipeline 等。PinSage 被证明能够处理真实的、十亿级的图。
     • StochasticGCN 进一步提出通过使用上一个 batch 的历史激活作为控制变量来降低采样方差，从而理论上保证可以使用任意小的采样数量。

   • FastGCN 并没有对节点的邻域进行采样，而是在每个卷积层中对所有节点进行采样，即 layer-wise 采样。FastGCN 将节点解释为独立同分布的样本，并将图卷积解释为概率测度下的积分变换。FastGCN 还显示：通过归一化 degree 来采样节点可以降低方差并提高模型性能。

     《Adaptive sampling towards fast graph representation learning》 进一步提出基于更高一层layer 为条件来采样更第一层 layer 的节点，从而更加自适应，并显著降低方差。

   

6. inductive learning：GCN 模型的一个重要特点是，它是否可以应用于 inductive learning 。即在一组节点或图上进行训练，并在另一组未见过的节点或图上进行测试。

   原则上，这个目标是通过学习给定特征上的映射函数来实现的，其中给定的特征不依赖于图结构，使得这个映射函数可以迁移到未见过的节点或图上。

   inductive learning 已经在 GraphSAGE、GAT、GaAN、FastGCN 中得到了验证。但是，现有的 inductive GCN 仅适用于具有显式特征的图，如何对没有显式特征的图（通常称作样本外问题 out-of-sample problem ）进行 inductive learning 仍然是悬而未决的。

1.3.4 理论分析

1. 为理解 GCN 的有效性，人们提出了一些理论分析，可以分为三类：node-level 任务、graph-level 任务、一般性分析。

2. node-level 任务：

   • 《Deeper insights into graph convolutional networks for semi-supervised learning》 首先通过使用特殊形式的拉普拉斯平滑分析了 GCN 的性能：拉普拉斯平滑使得同一个簇内的节点的 representation 相似。

     原始拉普拉斯平滑操作如下：

     $${\overrightarrow{\mathbf{h}}}_i^{\prime }=(1-\gamma ){\overrightarrow{\mathbf{h}}}_i+\gamma \sum _{j\in \mathcal{N}(i)}\frac{1}{d_i}{\overrightarrow{\mathbf{h}}}_j$$

     其中 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ 为节点 $v_i$$v_i$ 的原始representation ， ${\overrightarrow{\mathbf{h}}}_i^{\prime }$$\mathbf{\vec h}_i^\prime$ 为节点 $v_i$$v_i$ 的拉普拉斯平滑后的representation 。

     可以看到拉普拉斯平滑非常类似于卷积公式 ${\overrightarrow{\mathbf{h}}}_i^{(l+1)}=\rho \left(\sum _{j\in \tilde{\mathcal{N}}(i)}\frac{{\overrightarrow{\mathbf{h}}}_j^{(l)}{\mathbf{W}}^{(l)}}{\sqrt{{\tilde{d}}_i\times {\tilde{d}}_j}}\right)$$\mathbf{\vec h}_i^{(l+1)} = \rho\left(\sum_{j\in \tilde{\mathcal N}(i)}\frac{\mathbf{\vec h}_j^{(l)}\mathbf W^{(l)}}{\sqrt{\tilde d_i\times \tilde d_j}} \right)$ 。基于这种洞察，论文提出了 GCN 的 Co-Training 和 Self-Training 方法。

   • 最近 《Simplifying graph convolutional networks》 从信号处理的角度分析了 GCN。通过将节点特征视为图信号，他们表明公式 ${\overrightarrow{\mathbf{h}}}_i^{(l+1)}=\rho \left(\sum _{j\in \tilde{\mathcal{N}}(i)}\frac{{\overrightarrow{\mathbf{h}}}_j^{(l)}{\mathbf{W}}^{(l)}}{\sqrt{{\tilde{d}}_i\times {\tilde{d}}_j}}\right)$$\mathbf{\vec h}_i^{(l+1)} = \rho\left(\sum_{j\in \tilde{\mathcal N}(i)}\frac{\mathbf{\vec h}_j^{(l)}\mathbf W^{(l)}}{\sqrt{\tilde d_i\times \tilde d_j}} \right)$ 基本上是一个固定的低通滤波器。

     利用这一洞察，他们提出了 simplified graph convolution:SGC 方法，该方法消除所有非线性并将所有待学习的参数收缩 collapsing 到一个矩阵：

     $${\mathbf{H}}^{(L)}={\left({\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}\right)}^L{\mathbf{F}}^{\mathcal{V}}\mathbf{W}$$

     作者表明：这种 non-deeplearning 的 GCN 变体可以在很多任务上达到与现有 GCN 匹配的性能。

   • 《Revisiting graph neural networks: All we have is low-pass filters》 通过证明低通滤波操作并没有为 GCN 配备非线性流形学习能力来强化这一结果，并进一步提出 GFNN 模型来解决这个额外的难题，方法是在图卷积层之后添加一个 MLP 层。

3. graph-level 任务：

   • 《Semi-supervised classification with graph convolutional networks》 和 SortPooling 都考虑 GCN 和 graph kernel （如 Weisfeiler-Lehman:WL 的 kernel ）之间的联系，其中 graph kernel 广泛用于图同构测试 graph isomorphism tests 。

     他们表明：从概念上讲 GCN 是 WL kernel 的泛化，因为这两种方法都会迭代地聚合来自节点领域的信息。

   • 《How powerful are graph neural networks?》 通过证明 WL kernel 在区分图结构方面为 GCN 提供了上限，从而形式化了这一思想。

     基于该分析，他们提出了 graph isomorphism network:GIN ，并表明使用一个基于求和的 Readout 操作、一个 MLP 就可以实现最大判别能力，即在 graph classification 任务中具有最高的训练 accuracy 。

4. 一般性分析：

   • 《The vapnik–chervonenkis dimension of graph and recursive neural networks》 表明：具有不同激活函数的 GCN 的 VC-dim 具有与 RNN 相同的规模。

   • 《Supervised community detection with line graph neural networks》 分析了线性 GCN 的优化情况，并表明在某些简化下，任何局部极小值都接近于全局最小值。

   • 《Stability and generalization of graph convolutional neural networks》 分析了 GCN 的算法稳定性和泛化界。

     他们表明：如果图卷积滤波器的最大绝对特征值和图大小无关，则单层 GCN 会满足均匀稳定性 uniform stability 的强概念。