同构 GNN 知识点整理

Transductive & Inductive

按照不同应用场景，可以进一步从Transductive和Inductive两个角度对 GNN 模型的学习能力进行评估。

• Transductive：推理式学习，指从结构固定的图中学习节点表征的能力，相关的场景/问题有 节点分类、图分类 等；
• Inductive：归纳式学习，指从结构不固定的图中学习节点表征，并将其推广到新加入的节点的能力，相关的场景/问题有 推荐系统的用户冷启动问题、蛋白质结构与性质预测 等。

相比之下，Inductive的学习是更难、更具有挑战性的，同时也有着广的实际应用场景。

Spectral Graph Convolution 谱图卷积

谱图卷积将 CNN 中的卷积思想结合信号处理领域的傅里叶变换，并应用到了非规则数据的拓扑空间中来。

计算

谱图卷积

最原始的谱图卷积可表示如下：

其中：

• 为待学习的参数， 为图上的特征信号， 为 的滤波器（一个基于 的对角矩阵）；
• 对于图拉普拉斯矩阵 （ 为邻接矩阵， 为度数对角矩阵， 为单位矩阵），对其特征分解 可得到特征向量 和特征值 ， 则是针对图上信号 的傅里叶变换；
• 因此， 可以被理解成一个处理 的特征值 的函数，即 可以被理解成 ；

这种图谱卷积可以理解成：先通过图拉普拉斯矩阵 进行特征分解，再基于特征分解得到的特征向量 和特征值 与图信号 进行矩阵运算，得到输出。

存在计算性能过低的问题：

• 矩阵特征分解对于大图的复杂度很高；
• 与特征向量 的矩阵乘法复杂度也是 ；

切比雪夫多项式近似优化

为解决计算性能过低的问题，通过 阶截断的切比雪夫多项式（Chebyshev Polynomials，每一项只截断考虑其前两项的计算） 对 进行近似：

其中：

• 为切比雪夫多项式的系数；

• 表示缩放后的特征值， 为 特征值 中的最大值；

• 阶截断的切比雪夫多项式可以迭代计算得到：

  

此时的谱图卷积可表示为：

如此，相当于考虑了拉普拉斯矩阵 的 阶多项式，起到了对每一个节点聚合其 阶邻居的效果，此时的复杂度为 的。

论文相关描述 ^[1]

Note that this expression is now -localized since it is a -order polynomial in the Laplacian, i.e. it depends only on nodes that are at maximum steps away from the central node (-order neighborhood).

细节

• 切比雪夫多项式近似的意义：解决特征值分解以及相关矩阵操作计算性能过低的问题；
• 非线性计算：在 时， ，其计算是非线性的（即使 , 也是平方的非线性项）；

References

1. Semi-supervised Classification with Graph Convolutional Networks
2. Wavelets on graphs via spectral graph theory

GCN

在谱图卷积的基础上，进一步进行近似和优化。

计算

第一步优化：线性化计算

假设 以去掉 计算中的系数（模型在训练过程中能通过学习调整来适应这个假设的缩放），并令 让每一层卷积仅聚合 1 阶邻居：

此时，卷积的计算变成了 的线性函数，其效果有：

• 通过多层卷积的叠加依旧能学习到丰富的特征（复杂特征的学习能力不会降低）；
• 避免了切比雪夫多项式的显式参数化（固定了模型结构，避免了对 的调参）；
• 降低了计算复杂度的同时，起到了防止过拟合的效果（简化了基本模型单元的计算操作）；。

原论文相关描述 ^[1]

In this way, we can still recover a rich class of convolutional filter functions by stacking multiple such layers, but we are not limited to the explicit parameterization given by, e.g., the Chebyshev polynomials. We intuitively expect that such a model can alleviate the problem of overfitting on local neighborhood structures for graphs with very wide node degree distributions, such as social networks, citation networks, knowledge graphs and many other real-world graph datasets.

第二步优化：减少参数并正则化

在第一步优化的基础上，通过令 简化参数，以达到减少参数量防止过拟合问题、提高计算的效率的目的：

同时在前面的计算中，我们已经假设 ，即 的特征值的值域为 ，此时堆叠多层卷积核容易导致梯度爆炸/梯度消失，因此进一步对该项进行正则化得到 ：

即在邻接矩阵 中加入自环得到 ，并基于 重新计算对角度矩阵得到 。这个正则化的操作可以被理解为：将原本在拉普拉斯矩阵计算后加上单位矩阵的操作，放到了计算拉普拉斯矩阵之前。最终的效果是 的值域为 ，从而消除了梯度的问题。

最终 GCN 的计算可以被描述为：

其中： 和 分别是特征信号矩阵和参数矩阵， 是卷积后输出的信号矩阵。

细节

• GCN 相比于谱图卷积的优化主要在于：
  • 通过固定切比雪夫多项式的 ，线性化模型的计算；
  • 合并了多项的权重参数 ，减少模型参数。
• GCN 的复杂度为 ，其中 为卷积层数， 为特征维度，这意味着：
  • GCN 的复杂度和层数是线性的关系；
  • GCN 的计算是基于边的，复杂度和点数量无关。
• GCN 通过来自邻接矩阵的拉普拉斯矩阵进行聚合，一定程度上也起到了“给不同邻居分配不同权重”的效果，只不过这种权重是无法学习的，这也导致一些度数比较高的节点会固定地获得较高的权重分数无论其是否对任务有帮助。
• 在具体实现中，对于图结构无变化的Transductive任务，可以通过缓存 供给多层 GCN 使用，来避免重复计算，提高计算效率 ^[2]。

References

1. Semi-supervised Classification with Graph Convolutional Networks
2. torch_geometric.nn.conv.GCNConv

GAT

经典的 Attention 在同构图上的应用，其结构如下：

• 不同颜色边表示互相独立的 Attention Head

计算

1. 首先按照边所连接的两个节点特征，计算当前这条边的 Attention Coefficients，这个 Attention 模块可通用地表示为：

   

   其中：

   • 是一个共享的 Attention 参数；
   • 表示的是 的特征对于 的重要性；
   • 相比于其他的 Attention 会忽略点之间的连接关系直接对所有节点计算 Attention 分数，这里只按照边进行计算；

   实际上模型中使用的是：

   

   即，对 和 进行线性变换后连接，再乘以一个 Attention 参数 ，最后再使用 LeakyReLU 进行激活。

2. 然后，使用 softmax 进行对 Attention Coefficient 进行归一化：

   

   1-2 描述的是 GAT 中单个 head 的计算过程。

3. 最后，使用 个 head 的 Attention 进行计算，并使用均值聚合 Multi-head Attention：

   

细节

• GAT 中在计算前会添加自环边，用于学习自己对自己的 Attention；

• GAT 中的 Attention 是 edge-wise 的，而非 格式 ^[2]^，其作用范围仅限于 1 阶邻居节点，而非对图中所有节点都进行计算。

  原论文相关描述 ^[1]

  In its most general formulation, the model allows every node to attend on every other node, dropping all structural information. We inject the graph structure into the mechanism by performing masked attention—we only compute for nodes , where is some neighborhood of node i in the graph. In all our experiments, these will be exactly the first-order neighbors of (including ).

优缺点

优点：将 Attention 机制适配到了图结构中，从而优化了 GCN 中简单地通过度数区分节点重要性的方法，提高了模型的学习能力。

References

1. Graph attention networks
2. Attention Is All You Need

GraphSAGE

此前的 GNN 主要致力于直推式（Transductive）的学习，无法对学习到的模式泛化于未知的节点。GraphSAGE 的主要优势在于又拥有优良的推理（Inductive）学习能力。

原论文相关描述 ^[1]

most existing approaches require that all nodes in the graph are present during training of the embeddings; these previous approaches are inherently transductive and do not naturally generalize to unseen nodes.

计算

采样

在实际的算法中，会均匀地对每个节点采样固定数量的邻居，而非使用全部的邻居，并也将其表示为 。

原论文相关表述 ^[1]

In this work, we uniformly sample a fixed-size set of neighbors, instead of using full neighborhood sets in Algorithm 1, in order to keep the computational footprint of each batch fixed.

影响采样到的节点数的参数主要有两个：

1. GraphSAGE 的层数 ；
2. 第 层（对应着第 阶邻居）所采样的节点数 ；

此时，每个节点聚合操作的最坏的计算复杂度从 降低为 ，论文中推荐的参数配置为 。

计算

1. 前向传播：使用 Aggregator 聚合节点 所采样到邻居 的特征，并基于此更新节点 的特征；

   

2. 使用基于图的无监督 Loss，指导模型学习到的点特征满足邻近节点特征相似、不相邻节点特征有区分度：

   

   其中：

   • 表示是模型通过邻近节点生成的节点特征（不是直接 Transductive 学习得到的，可应用于图中有新增节点的场景）;

     原论文相关表述 ^[1]^

     the representations that we feed into this loss function are generated from the features contained within a node’s local neighborhood, rather than training a unique embedding for each node (via an embedding look-up).

   • 是被采样到的 的邻近节点， 是负样本数量， 是负采样的概率分布。

3. 多种候选Aggregator：

   • Mean Aggregator：对 以及 中的所有节点特征求均值，所以不需要再执行第 5 行的连接操作；
   • LSTM Aggregator：将 中所有节点随机排序输入 LSTM 进行学习；
   • Pooling Aggregator：针对 中的点，使用可学习的全连接层对特征进行处理后，使用逐元素的 Max或者 Mean 进行池化。

细节

• 在每一次节点特征聚合后，会进行一次缩放（Algorithm 1 第 7 行）；

• LSTM Aggregator 会对所有采样到的邻居随机排序；

• 使用 Mean 的Pooling Aggregator和Mean Aggregator的主要区别在于聚合时是否考虑自身节点、以及聚合器本身是否可学习；

• 对于没有Inductive需求的任务场景，其损失函数可以被替换为其他函数；

• 其采样过程是“倒过来”的，第 层采样 阶的 个邻居：如第 层采样的是 阶的 个邻居，第 层采样 阶的 个邻居，……，第 层采样 阶的 个邻居 ，其实际用的采样如下：

  

  原论文附录相关表述 ^[2]

  In particular, if we use total iterations with sample sizes and then this means that we sample nodes during iteration of Algorithm 1 and nodes during iteration , and—from the perspective of the “target” nodes in B that we want to generate representations for after iteration —this amounts to sampling of their immediate neighbors and of their 2-hop neighbors.

优缺点

优点：

• 通过采样，降低了模型计算的复杂度；
• 通过无监督损失函数的设计，提高了模型 Inductive 的学习能力；
• 由于对于每个节点而言仅使用了有限数量的邻居进行聚合，因此相比于 GCN 在稠密图上的计算性能更优，也有着更好的实际落地应用意义。

References

1. Inductive representation learning on large graphs
2. Inductive representation learning on large graphs - arXiv版本（含附录）
3. GraphSAGE: GCN落地必读论文 - 知乎专栏

总结

纵观 GNN 模型的发展变革如下：