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$ 维。

   换句话讲，