Question

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 的强概念。

1.4 Graph AutoEncoder

1. 自编码器 autoencoder:AE 及其变体已经被广泛应用到无监督学习任务中，它适用于学习图的节点 representation。其背后隐含的假设是：图具有固有 inherent 的、潜在potentially 的非线性低秩结构。

   这里我们首先介绍图自编码器graph autoencoder:GAE ，然后介绍图变分自编码器graph variational autoencoder 以及其它改进。下表总结了 GAE 的主要特点，其中 TC 表示时间复杂度。

   

1.4.1 图自编码器

1. 图自编码器起源于稀疏自编码器 sparse autoencoder:SAE，其基本思想是：将邻接矩阵或其变体视为节点的原始特征，然后利用自编码器作为降维技术来学习节点 representation。

   具体而言，SAE 使用了如下的$L_2$$ L_2 $ 重构损失函数：

   $$\begin{array}{c}\underset{\mathrm{\Theta }}{min}{\mathcal{L}}_2=\sum _{i=1}^N{\Vert \mathbf{P}(i,:)-\hat{\mathbf{P}}(i,:)\Vert }_2\\ \hat{\mathbf{P}}(i,:)=G({\overrightarrow{\mathbf{h}}}_i),{\overrightarrow{\mathbf{h}}}_i=F(\mathbf{P}(i,:))\end{array}$$

   其中：

   • $\mathbf{P}$$ \mathbf P $ 是转移矩阵，$\hat{\mathbf{P}}$$ \hat{\mathbf P} $ 为重构的转移矩阵。
   • ${\overrightarrow{\mathbf{h}}}_i\in {\mathbb{R}}^d$$ \mathbf{\vec h}_i\in \mathbb R^d $ 为节点$v_i$$ v_i $ 的低维 representation 向量，$d\ll N$$ d\ll N $ 为节点 representation 向量维度。
   • $F(\cdot )$$ F(\cdot) $ 为编码器，$G(\cdot )$$ G(\cdot) $ 为解码器，$\mathrm{\Theta }$$ \Theta $ 为模型参数。通常编码器和解码器都是具有多个隐层的 MLP 。

   换句话讲，SAE 通过编码器将$\mathbf{P}(i,:)$$ \mathbf P(i,:) $ 的信息压缩为低维向量${\overrightarrow{\mathbf{h}}}_i$$ \mathbf{\vec h}_i $ ，然后利用解码器从该向量重构原始特征。

   另外，还可以在损失函数中添加一个正则化项。

   在获得低维 representation${\overrightarrow{\mathbf{h}}}_i$$ \mathbf{\vec h}_i $ 之后，可以使用 k-means 算法来用于节点聚类。

   实验表明：SAE 优于非深度学习 baseline。但是，SAE 是基于不正确incorrect 的理论分析，其有效性的底层机制仍然无法解释。

2. Structure deep network embedding:SDNE 解决了这个问题。SDNE 表明：${\mathcal{L}}_2=\sum _{i=1}^N{\Vert \mathbf{P}(i,:)-\hat{\mathbf{P}}(i,:)\Vert }_2$$ \mathcal L_2 = \sum_{i=1}^N \left\| \mathbf P(i,:) - \hat {\mathbf P}(i,:)\right\|_2 $ 重构损失实际上对应于节点之间的二阶邻近度second-order proximity 。即，如果两个节点共享相似的邻域，则它们应该具有相似的潜在表示。这是 network science 中被深入研究的概念，被称作协同过滤或三角闭合 triangle closure 。

   由于 network embedding 方法表明一阶邻近度也很重要，因此 SDNE 通过添加另一个拉普拉斯特征图 Laplacian Eigenmap 项来调整目标函数：

   $$\underset{\mathrm{\Theta }}{min}{\mathcal{L}}_2+\alpha \sum _{i,j=1}^{N}A(i,j){\Vert {\overrightarrow{\mathbf{h}}}_i-{\overrightarrow{\mathbf{h}}}_j\Vert }_2$$

   即：如果两个节点直连，则它们也共享相似的潜在表示。

   作者还通过使用邻接矩阵来修改${\mathcal{L}}_2$$ \mathcal L_2 $ 重构损失，其中零元素和非零原始赋予不同的权重：

   $${\mathcal{L}}_2=\sum _{i=1}^N{\Vert (\mathbf{A}(i,:)-G({\overrightarrow{\mathbf{h}}}_i))\odot {\overrightarrow{\mathbf{b}}}_i\Vert }_2$$

   其中：

   • ${\overrightarrow{\mathbf{h}}}_i=F(\mathbf{A}(i,:))$$ \mathbf{\vec h}_i = F(\mathbf A(i,:)) $
   • 当$A(i,j)=0$$ A(i,j)=0 $ 时$b_{i,j}=1$$ b_{i,j}=1 $ ，否则$b_{i,j}=\beta >1$$ b_{i,j} = \beta\gt 1 $ 。其中$\beta$$ \beta $ 是另外一个超参数。

   SDNE 整体架构如下图所示，它通过 deep autoencoder 来保持节点之间的一阶邻近度和二阶邻近度。

   

3. DNGR 使用 positive pointwise mutual information: PPMI 代替转移概率矩阵$\mathbf{P}$$ \mathbf P $ ，这样原始特征就可以和图的某些随机游走概率相联系。但是，构造输入矩阵的时间复杂度为$O(N^2)$$ O(N^2) $ ，无法扩展到大型图。

4. GC-MC 采用了不同的方法，它使用 GCN 来作为编码器：

   $$\mathbf{H}=\text{GCN}({\mathbf{F}}^{\mathcal{V}},\mathbf{A})$$

   然后使用一个简单的 bilinear 函数作为解码器：

   $$\hat{\mathbf{A}}(i,j)={\overrightarrow{\mathbf{h}}}_i{\mathrm{\Theta }}_{de}{\overrightarrow{\mathbf{h}}}_j^{\mathrm{\top }}$$

   其中${\mathrm{\Theta }}_{de}$$ \Theta_{de} $ 为解码器参数。

   通过这种方式，可以很自然地融合节点特征。对于没有节点特征的图，可以使用节点 ID 的 one-hot 向量。作者证明了 GC-MC 在二部图推荐问题上的有效性。

5. DRNE 并没有重构邻接矩阵或其变体，而是提出了另一种思路：通过LSTM 聚合邻域信息来直接重构低维节点 embedding 向量。具体而言，DRNE 采用以下目标函数：

   $$\mathcal{L}=\sum _{i=1}^N\Vert {\overrightarrow{\mathbf{h}}}_i-\text{LSTM}\left(\{{\overrightarrow{\mathbf{h}}}_j\mid j\in \mathcal{N}(i)\}\right)\Vert$$

   由于 LSTM 要求输入为序列，因此作者建议根据邻域内每个邻居节点的 degree 对邻居节点进行排序。作者还对具有较大degree 的节点采用邻域采样技术，从而防止序列太长。

   作者证明：DRNE 可以保留 regular equivalence，以及节点的很多 centrality measure，如 PangeRank 。

6. 与上述将节点映射为低维向量的工作不同，Graph2Gauss:G2G 提出将每个节点编码为高斯分布${\overrightarrow{\mathbf{h}}}_i=\mathcal{N}(\mathbf{M}(i,:),\text{diag}(\mathrm{\Sigma }(i,:)))$$ \mathbf{\vec h}_i = \mathcal N\left(\mathbf M(i,:),\text{diag}(\Sigma(i,:))\right) $ 来捕获节点的不确定性。

   具体而言，作者使用从节点属性到高斯分布的均值、方差的深度映射作为编码器：

   $$\begin{array}{c}\mathbf{M}(i,:)=F_M\left({\overrightarrow{\mathbf{f}}}_i^{\mathcal{V}}\right)\\ \mathrm{\Sigma }(i,:)=F_{\mathrm{\Sigma }}\left({\overrightarrow{\mathbf{f}}}_i^{\mathcal{V}}\right)\end{array}$$

   其中$F_M(\cdot ),F_{\mathrm{\Sigma }}(\cdot )$$ F_M(\cdot), F_\Sigma(\cdot) $ 都是待学习的函数。

   然后，它们使用 pairwise 约束来学习模型，而不是使用显式的解码器函数：

   $$\text{KL}({\overrightarrow{\mathbf{h}}}_j||{\overrightarrow{\mathbf{h}}}_i)<\text{KL}({\overrightarrow{\mathbf{h}}}_{j^{\prime }}||{\overrightarrow{\mathbf{h}}}_i),\mathrm{\forall }i,\mathrm{\forall }j,\mathrm{\forall }{j}^{\prime }s.t.d(i,j)<d(i,j^{\prime })$$

   其中：

   • $d(i,j)$$ d(i,j) $ 为节点$v_i$$ v_i $ 到$v_j$$ v_j $ 之间的最短距离。
   • $KL(q(\cdot )||p(\cdot ))$$ KL(q(\cdot)||p(\cdot)) $ 为$q(\cdot )$$ q(\cdot) $ 和$p(\cdot )$$ p(\cdot) $ 之间的 Kullback-Leibler: KL 距离。

   换句话讲，约束条件确保node representation之间的 KL 距离和图中节点之间距离保持相同的相对顺序。

   但是，由于上式难以优化，因此作者采用基于能量的损失函数作为松弛：

   $$\mathcal{L}=\sum _{(i,j,j^{\prime })\in \mathcal{D}}(E_{i,j}^2+{\exp }^{-E_{i,j^{\prime }}})$$

   其中：

   • $\mathcal{D}=\{(i,j,j^{\prime })\mid d(i,j)<d(i,j^{\prime })\}$$ \mathcal D = \left\{(i,j,j^\prime)\mid d(i,j) \lt d(i,j^\prime)\right\} $ 为训练三元组，它保持$d(i,j)<d(i,j^{\prime })$$ d(i,j) \lt d(i,j^\prime) $ 的关系。
   • $E_{i,j}=\text{KL}({\overrightarrow{\mathbf{h}}}_j||{\overrightarrow{\mathbf{h}}}_i)$$ E_{i,j} = \text{KL}\left(\mathbf{\vec h}_j||\mathbf{\vec h}_i\right) $ 为 KL 距离。

   作者进一步提出了无偏的采样策略，从而加快训练过程。

1.4.2 变分自编码器

1. 与上述自编码器不同，变分自编码器 variational autoencoders:VAE 是将降维技术和生成模型结合在一起的另一种深度学习方法。它的潜在优点包括对噪声容忍、以及能够学习平滑的 representation 。

2. VAE 首次被引入图数据是在 VAGE，其中解码器是简单的线性内积：

   $$p(\mathbf{A}\mid \mathbf{H})=\prod _{i,j=1}^N\sigma \left({\overrightarrow{\mathbf{h}}}_i{\overrightarrow{\mathbf{h}}}_j^{\mathrm{\top }}\right)$$

   其中节点 representation 假设服从高斯分布：

   $$q({\overrightarrow{\mathbf{h}}}_i\mid \mathbf{M},\mathrm{\Sigma })=\mathcal{N}({\overrightarrow{\mathbf{h}}}_i\mid \mathbf{M}(i,:),\text{diag}(\mathrm{\Sigma }(i,:)))$$

   作者使用 GCN 作为均值和方差的编码器：

   $$\begin{array}{c}\mathbf{M}={\text{GCN}}_M({\mathbf{F}}^{\mathcal{V}},\mathbf{A})\\ \log \mathrm{\Sigma }={\text{GCN}}_{\mathrm{\Sigma }}({\mathbf{F}}^{\mathcal{V}},\mathbf{A})\end{array}$$

   然后通过最小化变分下界 variational lower bound 来学习模型参数：

   $$\mathcal{L}={\mathbb{E}}_{q(\mathbf{H}\mid {\mathbf{F}}^{\mathcal{V}},\mathbf{A})}[\log p(\mathbf{A}\mid \mathbf{H})]-\text{KL}(q(\mathbf{H}\mid {\mathbf{F}}^{\mathcal{V}},\mathbf{A})||p(\mathbf{H}))$$

   但是该方法需要重构完整的图，因此时间复杂度为$O(N^2)$$ O(N^2) $ 。

3. 受到 SDNE 和 G2G 启发，DVNE 为图数据提出了另一种 VAE，它也将每个节点表示为高斯分布。和现有的采用 KL 散度作为距离度量不同，DVNE 使用 Wasserstein 距离来保留节点相似度的传递性 transitivity 。

   和 SDNE 、G2G 相似，SVNE 在目标函数中保留了一阶邻近度和二阶邻近度：

   $$\underset{\mathrm{\Theta }}{min}\sum _{(i,j,j^{\prime })\in \mathcal{D}}(E_{i,j}^2+\exp (-E_{i,j^{\prime }}))+\alpha {\mathcal{L}}_2$$

   其中：

   • $E_{i,j}=W_2({\overrightarrow{\mathbf{h}}}_j||{\overrightarrow{\mathbf{h}}}_i)$$ E_{i,j} = W_2\left(\mathbf{\vec h}_j|| \mathbf{\vec h}_i\right) $ 为两个高斯分布${\overrightarrow{\mathbf{h}}}_j$$ \mathbf{\vec h}_j $ 和${\overrightarrow{\mathbf{h}}}_i$$ \mathbf{\vec h}_i $ 之间的二阶 Wasserstein 距离。
   • $\mathcal{D}=\{(i,j,j^{\prime })\mid j\in \mathcal{N}(i),j^{\prime }\ne \mathcal{N}(i)\}$$ \mathcal D = \{(i,j,j^\prime)\mid j\in \mathcal N(i), j^\prime \ne \mathcal N(i)\} $ 为三元组的集合，用于计算一阶邻近性的 ranking loss 。

   重构损失定义为：

   $${\mathcal{L}}_2=\underset{q(\mathbf{Z}\mid \mathbf{P})}{inf}{\mathbb{E}}_{p(\mathbf{P})}{\mathbb{E}}_{q(\mathbf{Z}\mid \mathbf{P})}{\Vert \mathbf{P}\odot (\mathbf{P}-G(\mathbf{Z}))\Vert }_2^2$$

   其中$\mathbf{P}$$ \mathbf P $ 为转移矩阵，$\mathbf{Z}$$ \mathbf Z $ 为从$\mathbf{H}$$ \mathbf H $ 中采样得到。整体架构如下图所示。

   通过这种方法，目标函数可以像传统VAE 中使用 reparameterization 技巧一样被最小化。

   

1.4.3 改进

1. 对抗训练：

   • ARGA 通过在 GAE 中添加一个额外的正则化项，从而引入了对抗训练 adversarial training。其总体架构如下图所示。

     具体而言，GAE 编码器用作生成器generator，而判别器discriminator 目标是区分潜在representation是来自生成器还是来自先验分布。通过这种方式，自编码器被迫匹配先验分布，这相当于是一个正则化。

     ARGA 的目标函数是：

     $$\underset{\mathrm{\Theta }}{min}{\mathcal{L}}_2+\alpha {\mathcal{L}}_{\text{GAN}}$$

     其中${\mathcal{L}}_2$$ \mathcal L_2 $ 对应于GAE 中的重构损失，而${\mathcal{L}}_{\text{GAN}}$$ \mathcal L_{\text{GAN}} $ 为：

     $${\mathcal{L}}_{\text{GAN}}=\underset{\mathcal{G}}{min}\underset{\mathcal{D}}{max}{\mathbb{E}}_{\overrightarrow{\mathbf{h}}\sim P_{\overrightarrow{\mathbf{h}}}}[\log \mathcal{D}(\overrightarrow{\mathbf{h}})]+{\mathbb{E}}_{\overrightarrow{\mathbf{z}}\sim \mathcal{G}({\mathbf{F}}^{\mathcal{V}},\mathbf{A})}[\log (1-\mathcal{D}(\overrightarrow{\mathbf{z}}))]$$

     其中：

     • $F({\mathbf{F}}^{\mathcal{V}},\mathbf{A})$$ F\left(\mathbf F^{\mathcal V}, \mathbf A\right) $ 为生成器，它使用VAGE 中的图卷积编码器。
     • $\mathcal{D}(\cdot )$$ \mathcal D(\cdot) $ 为基于交叉熵损失的判别器。
     • $P_{\overrightarrow{\mathbf{h}}}$$ P_{\mathbf{\vec h}} $ 为先验分布，论文采用简单的高斯先验。

     实验结果证明了对抗训练方案的有效性。

     

   • 同一时期，NetRA 也提出了一个生成对抗网络 generative adversarial network:GAN 来提升图自编码器的泛化能力。作者使用如下的目标函数：

     $$\underset{\mathrm{\Theta }}{min}{\mathcal{L}}_2+{\alpha }_1{\mathcal{L}}_{\text{LE}}+{\alpha }_2{\mathcal{L}}_{\text{GAN}}$$

     其中：

     • ${\mathcal{L}}_2$$ \mathcal L_2 $ 对应于GAE 中的重构损失。
     • ${\mathcal{L}}_{\text{LE}}$$ \mathcal L_{\text{LE}} $ 对应于拉普拉斯特征图损失。
     • ${\mathcal{L}}_{\text{GAN}}$$ \mathcal L_{\text{GAN}} $ 对应于生成对抗损失。

     此外，作者使用 LSTM 作为编码器，从而聚合邻域信息。NetRA 并没有像 DRNE 中那样仅对直接邻居进行采样并使用 degree 对直接邻居进行排序，而是使用了随机游走来生成输入序列。

     和 ARGA 相比，NetRA 认为 GAE 的 representation 是 ground-truth，并使用随机高斯噪声然后接一个 MLP 作为生成器。

2. inductive learning：和 GCN 相似，如果将节点属性融合到编码器中，则 GAE 可以应用于 inductive learning。 这可以通过使用 GCN 作为编码器来实现，如在 GC-MC, VGAE 中。

   也可以通过直接学习一个从节点特征到 embedding 的映射函数来实现，如 G2G 。由于仅在学习参数时才用到边信息，所以该模型也可以应用于训练期间未曾见过的节点。

   这些工作还表明，尽管 GCN 和 GAE 基于不同的架构，但是它们可以组合使用。我们认为这是未来一个有希望的方向。

3. 相似性度量：在 GAE 中已经采用了很多相似性度量，如：

   • 图自编码器：L2 重构损失、拉普拉斯特征图损失、ranking loss 。
   • 图变分自编码器：KL 距离、Wasserstein 距离。

   尽管这些相似性度量基于不同的动机，但是如何为特定的任务和模型体系结构选择合适的相似性度量仍然未被研究。需要更多的研究来了解这些度量指标之间的根本差异。

1.5 Graph RL

1. 众所周知，强化学习 reinforcement learning:RL 善于从反馈中学习，尤其是在处理不可微的目标和约束时。这里我们回顾了 Graph RL 方法，如下表所示。

   

2. GCPN 利用 RL 生成目标导向的 goal-directed 分子图，同时考虑了不可微的目标函数和约束。

   具体而言，它将图生成过程建模为添加节点和边的马尔可夫决策过程，并将生成模型视为在图生成环境中运行的 RL agent 。通过将 agent action 视为链接预测、使用 domain-specific 以及对抗性奖励、使用 GCN 来学习节点 representation，该方法可以使用策略梯度以端到端的方式训练 GCPN 。

3. 同一时期的 MolGAN 采用了类似的思想，即使用 RL 生成分子图。但是， MolGAN 提出不要通过一系列 action 来生成图，而是直接生成完整的图。这种方法对于小分子特别有效。

4. GTPN 采用 RL 预测化学反应产物。具体而言，该 agent 的 action 是选择分子图中的节点 pair 对，然后预测它们新的化学键的类型。根据预测是否正确，从而对 agent 进行实时奖励以及最终奖励。

   GTPN 使用 GCN 来学习节点 representation，以及一个 RNN 来记住 memorize 预测序列。

5. GAM 通过使用随机游走将 RL 应用于图分类。作者将随机游走建模为部分可观测的马尔可夫决策过程 partially observable Markov decision process:POMDP 。

   agent 执行了两项操作：

   • 首先，它预测了图的标签。
   • 然后，它选择随机游走中的下一个节点。

   奖励的确定仅取决于 agent 是否对图进行了正确的分类：

   $$\mathcal{J}(\theta )={\mathbb{E}}_{P(S_{1:T};\theta )}\sum _{t=1}^T{r}_t$$

   其中：$S_t$$ S_t $ 为环境；$T$$ T $ 为总的时间步 time step；$r_t=1$$ r_t=1 $ 表示正确的预测，否则$r_t=-1$$ r_t=-1 $ 。

6. DeepPath 和 MINERVA 都是采用 RL 对知识图谱 knowledge graph: KG 进行推理。

   具体而言，DeepPath 的目标是寻找路径，即在两个目标节点之间找到信息量最大的路径；而 MINERVA 则处理问答任务，即在给定问题节点和关系的情况下找到正确的答案节点。

   这两种方法中，RL agent 都需要在每个 step 中预测路径中的下一个节点，并在 KG 中输出推理路径。如果路径正确地到达了目的地，则 agent 获得奖励。

   DeepPath 还添加了正则化项来鼓励路径多样性。

1.6 Graph Adversarial

1. 这里我们介绍如何将对抗方法 adversarial method 应用到图，下表给出了图对抗方法的主要特点：

   

1.6.1 对抗训练

1. GAN 的基本思想是建立两个相关联的模型：判别器 discriminator 和生成器 generator 。

   • 生成器的目标是通过生成假数据来 ”欺骗“ 判别器。
   • 判别器的目标是区分样本是来自于真实数据还是由生成器生成的。

   然后，两个模型通过使用 minmax game 进行联合训练而彼此受益。

   对抗训练已被证明在生成模型中有效，并提高了判别模型的泛化能力。在前文中，我们分别回顾了如何在 GAE 和 Graph RL 中使用对抗训练方案，这里我们详细回顾了图上的其它几种对抗训练Adversarial Training方法。

2. GraphGAN 提出使用 GAN 来提升具有以下目标函数的graph embedding 方法：

   $$\underset{\mathcal{G}}{min}\underset{\mathcal{D}}{max}\sum _{i=1}^N({\mathbb{E}}_{v\sim P_{graph}(\cdot \mid v_i)}[\log \mathcal{D}(v,v_i)]+{\mathbb{E}}_{v\sim \mathcal{G}(\cdot \mid v_i)}[\log (1-\mathcal{D}(v,v_i)))$$

   其中：

   • 判别器$\mathcal{D}(\cdot )$$ \mathcal D(\cdot) $ 定义为：

     $$\mathcal{D}(v,v_i)=\sigma ({\overrightarrow{\mathbf{d}}}_v\cdot {\overrightarrow{\mathbf{d}}}_{v_i})$$

     ${\overrightarrow{\mathbf{d}}}_v$$ \mathbf{\vec d}_v $ 为节点$v$$ v $ 在判别器中的低维 embedding 向量。

   • 生成器$\mathcal{G}(\cdot )$$ \mathcal G(\cdot) $ 定义：

     $$\mathcal{G}(v\mid v_i)=\frac{\exp ({\overrightarrow{\mathbf{g}}}_v\cdot {\overrightarrow{\mathbf{g}}}_{v_i})}{\sum _{v^{\prime }\ne v_i}\exp ({\overrightarrow{\mathbf{g}}}_{v^{\prime }}\cdot {\overrightarrow{\mathbf{g}}}_{v_i})}$$

     ${\overrightarrow{\mathbf{g}}}_v$$ \mathbf{\vec g}_v $ 为节点$v$$ v $ 在生成器中的低维 embedding 向量。

   结合以上等式，判别器实际上有两个目标：原始图中的节点 pair 对应该具有较大的相似性，生成器生成的节点 pair 对应该具有较小的相似性。

   该架构和 graph embedding 方法（如 LINE）相似，除了negative node pair 是由生成器$\mathcal{G}(\cdot )$$ \mathcal G(\cdot) $ 生成的而不是随机采样的之外。

   作者表明，该方法提升了节点 embedding 向量的 inference 能力。

3. Adversarial network embedding:ANE 也采用对抗训练方案来改进网络 embedding 方法。

   类似 ARGA，ANE 将 GAN 作为现有网络 embedding 方法（如 DeepWalk）的额外正则化项，通过将先验分布作为真实数据 real data 并将 embedding 向量视为生成样本。

4. GraphSGAN 使用 GAN 来提升图的半监督学习。具体而言，作者观察到：应该在子图之间的稠密间隙density gap 中生成伪节点，从而削弱现有模型在不同 cluster 之间的传播效果。

   为实现该模型，作者设计了一个新的优化目标，该目标具有精心设计的损失项，从而确保生成器在稠密间隙中生成样本。

5. NetGAN 为图生成任务采用了 GAN 。具体而言，作者将图生成视为一个学习有偏随机游走分布的任务，并采用 GAN 框架使用 LSTM 来生成和区分这些随机游走序列。

   实验表明，使用随机游走也可以学习全局网络模式。

1.6.2 对抗攻击

1. 对抗攻击Adversarial attack是另一类对抗方法，旨在通过向数据添加较小的扰动来故意 “欺骗“ 目标方法。

   研究对抗攻击可以加深我们对现有模型的理解，并启发更强大的体系结构。

2. Nettack 是首次提出通过修改图结构和节点属性来攻击节点分类模型（如 GCN）的方法。

   假设目标节点为$v_0$$ v_0 $ ，其真实类别为$c_{\text{true}}$$ c_{\text{true}} $ ，目标模型为$F(\mathbf{A},{\mathbf{F}}^{\mathcal{V}})$$ F(\mathbf A,\mathbf F^{\mathcal V}) $ ，损失函数为${\mathcal{L}}_{\mathcal{F}}(\mathbf{A},{\mathbf{F}}^{(V)})$$ \mathcal L_\mathcal F(\mathbf A, \mathbf F^{(V)}) $ ， 则该模型使用以下目标函数：

   $$\begin{array}{c}\arg \underset{({\mathbf{A}}^{\prime },{\mathbf{F}}^{{\mathcal{V}}^{\prime }})\in \mathcal{P}}{max}\underset{c\ne c_{\text{true}}}{max}\log {\mathbf{Z}}_{v_0,c}^{\ast }-\log {\mathbf{Z}}_{v_0,c_{\text{true}}}^{\ast }\\ s.t.{\mathbf{Z}}^{\ast }=F_{{\theta }^{\ast }}({\mathbf{A}}^{\prime },{\mathbf{F}}^{{\mathcal{V}}^{\prime }}),{\theta }^{\ast }=\arg \underset{\theta }{min}{\mathcal{L}}_F({\mathbf{A}}^{\prime },{\mathbf{F}}^{{\mathcal{V}}^{\prime }})\end{array}$$

   其中：

   • ${\mathbf{A}}^{\prime },{\mathbf{F}}^{{\mathcal{V}}^{\prime }}$$ \mathbf A^\prime, \mathbf F^{\mathcal V'} $ 为修改的邻接矩阵和节点特征矩阵。
   • $\mathbf{Z}$$ \mathbf Z $ 表示通过$F(\cdot )$$ F(\cdot) $ 预测的节点类别概率矩阵。
   • $\mathcal{P}$$ \mathcal P $ 为attack 约束定义的空间。

   简而言之，优化的目标是在图结构和节点属性中找到最佳的合法修改，使得$v_0$$ v_0 $ 被错误地分类。

   ${\theta }^{\ast }$$ \theta^* $ 表示攻击是有因果关系的 causative ，即攻击是在训练目标模型之前发生的。

   作者还提出一些针对攻击的约束条件，最重要的约束条件是：攻击应该是 ”微小的“， 即应该仅仅进行很小的修改。具体而言，作者提出保留诸如节点 degree 分布和特征共现之类的数据特点。

   作者还提出了两种攻击方式：直接攻击direct attack （直接攻击$v_0$$ v_0 $ ）、影响力攻击 influence attack （仅攻击其它节点），并提出了几种放宽措施以便优化过程易于处理。

3. 同一时期，《Adversarial attack on graph structured data》 研究了类似于 Nettack 的目标函数。但是，他们关注仅更改图结构的情况。他们并没有假设攻击者拥有所有信息，而是考虑了几种情况，每种情况提供了不同数量的信息。

   最有效的策略 RL-S2V 采用 structure2vec 来学习节点和图的 representation，并使用强化学习来解决优化问题。实验结果表明，这些攻击对于节点和图分类任务均有效。

4. 前面提到的两种攻击都是针对性的，即它们旨在引起某些目标节点$v_0$$ v_0 $ 的错误分类。《Adversarial attacks on graph neural networks via meta learning》 率先研究了非目标攻击，这些攻击旨在降低整体模型的性能。

   他们将图结构视为要优化的超参数，并在优化过程中采用了元梯度meta-gradient ，同时还采用了几种逼近元梯度的技术。

1.7 讨论和总结

1. 应用：除了诸如节点分类、图分类之类的标准的图 inference 任务之外，基于图的深度学习方法也应用于多种学科，包括建模社会影响力、推荐、化学和生物学等等。由于这些应用多种多样，对其进行彻底的回顾超出了本文的范围，但是我们列出了一些关键的灵感：

   • 首先，在构建图或者选择架构时，将领域知识纳入模型非常重要。

     例如，基于 relative distance 构建的图可能适用于交通预测问题，但可能不适用于地理位置也很重要的天气预报问题。

   • 其次，基于图的模型通常可以在其它体系结构之上构建，而不是作为独立模型构建。如

     例如，计算机视觉社区通常采用 CNN 来检测对象，然后将基于图的深度学习用作推理模块。

   这些应用还表明：基于图的深度学习不仅可以挖掘现有图数据背后的丰富价值，还有助于将关系型数据自然地建模为图，从而极大地扩展了基于图的深度学习模型的适用性。

2. 未来方向：

   • 新模型用于未研究过的图结构：由于图数据的结构各种各样，因此现有方法不适合所有图结构。

     例如，大多数方法集中于同质图，很少研究异质图。

   • 现有模型的组合：可以集成很多现有架构，如将GCN 用作GAE 或 Graph RL 中的一层。

     除了设计新的构建 block 之外，如何系统性地组合这些体系结构也是未来一个有趣的方向。

   • 动态图：现有大多数方法都关注于静态图，而实际上很多图本质上是动态的，图的节点、边、特征都可以随时间变化。

     例如社交网络中，人们可能建立新的社交关系、删除旧的社交关系，并且他们的特征（如兴趣爱好职业）会随着时间改变。新用户可以加入社交网络、现有用户也可以离开。

     如何对动态图的不断变化的特点进行建模，以及如何支持对模型参数的增量更新仍是悬而未决的。

   • 可解释性和鲁棒性：由于图通常和其它风险敏感 risk-sensitive 的场景相关，因此深度学习模型结果的可解释能力对于决策问题至关重要。

     例如，在医学或与疾病相关的问题中，可解释性对于将计算机实验转化为临床应用至关重要。

     但是，基于图的深度学习的可解释性甚至比其它黑盒模型更具挑战性，因为图的节点和边通常紧密相连。

     此外，正如对抗攻击所示，许多现有的图深度学习模型对于对抗攻击都很敏感，因此提升现有方法的鲁棒性是另一个重要问题。