Graph Neural Networks/zh
| Article | |
|---|---|
| Topic area | deep-learning |
| Prerequisites | Neural Network, Graph Theory |
概述
图神经网络（GNN）是一类专为图结构数据设计的神经网络，其输入由通过边连接的节点构成，而不是规则的网格或序列。与利用图像或文本规则拓扑结构的卷积或循环架构不同，GNN 学习的表示尊重任意的连接模式，并且对节点顺序的置换保持不变。它们已成为关系结构具有信息量的问题的标准工具，包括分子性质预测、社交网络分析、推荐系统、交通预测和知识图谱推理。几乎所有现代 GNN 变体背后的统一思想是消息传递：每个节点通过聚合来自其邻居的信息来迭代更新其表示，从而使局部特征能够在图中传播，并产生同时捕获节点属性和结构上下文的嵌入。[1]
直觉与动机
图 $ G = (V, E) $ 由节点集 $ V $、边 $ E \subseteq V \times V $ 以及可选的附加在每个节点和边上的特征组成。许多现实世界的系统天然具有关系性：分子中的原子、社交网络中的用户、道路地图中的交叉口，或知识图谱中的实体。将标准的多层感知机应用于此类数据需要将图展平为固定大小的向量，这会丢弃连接性信息。应用卷积神经网络则需要规则网格，而图缺乏这种结构。GNN 通过将节点嵌入计算为每个节点局部邻域的函数来回避这两个问题，然后堆叠层，使每增加一层就将感受野扩展一跳。
有两个属性使其在实践中可行。第一，置换等变性：重新排序节点索引会以相同的方式重新排序输出，但不会改变其值，这是无序邻居集合的正确对称性。第二，局部性：节点的更新仅依赖于其直接邻居，因此相同的参数可以在整个图上重复使用，与图的大小无关。这两个属性共同赋予 GNN 对关系数据的强归纳偏置，正如平移等变性赋予 CNN 对图像的强偏置。
消息传递的形式化
占主导地位的抽象是消息传递神经网络（MPNN）框架。[2] 设 $ h_v^{(l)} $ 表示节点 $ v $ 在第 $ l $ 层的嵌入，$ \mathcal{N}(v) $ 表示其邻居。单层应用三个步骤：
$ {\displaystyle m_v^{(l+1)} = \mathrm{AGG}^{(l)}\big(\{h_u^{(l)} : u \in \mathcal{N}(v)\}\big)} $
$ {\displaystyle h_v^{(l+1)} = \mathrm{UPD}^{(l)}\big(h_v^{(l)}, m_v^{(l+1)}\big)} $
聚合函数 $ \mathrm{AGG} $ 必须是置换不变的——典型选择包括求和、平均、最大值或注意力加权求和。更新函数 $ \mathrm{UPD} $ 通常是一个小型 MLP 或门控单元。经过 $ L $ 层之后，每个节点嵌入都包含来自其 $ L $ 跳邻域的信息。对于图级任务，最终的读出会将所有节点嵌入汇集为单个向量，通常通过求和、平均或学习得到的注意力池化来完成。
常见架构
图卷积网络（GCN）将一层定义为邻接矩阵的对称归一化，然后是线性变换和非线性：[3]
$ {\displaystyle H^{(l+1)} = \sigma\!\left(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} H^{(l)} W^{(l)}\right)} $
其中 $ \tilde{A} = A + I $ 包含自环，$ \tilde{D} $ 是其度矩阵，$ \sigma $ 是诸如 ReLU 之类的非线性函数。GCN 本质上是带有基于度的加权的均值聚合器，可作为谱图卷积的一阶近似导出。
GraphSAGE 将全邻域聚合替换为固定大小的采样，从而允许在内存放不下的大图上进行归纳学习，并能处理之前未见过的节点。[4]
图注意力网络（GAT）通过注意力机制为每个邻居分配可学习的权重，使得信息量大的邻居比信息量小的邻居贡献更多：[5]
$ {\displaystyle \alpha_{vu} = \mathrm{softmax}_u\!\left(\mathrm{LeakyReLU}\big(a^\top [W h_v \,\|\, W h_u]\big)\right)} $
图同构网络（GIN）使用求和聚合配合单射的 MLP 更新，可证明地匹配Weisfeiler-Leman 图同构测试的判别能力，这是标准消息传递 GNN 所能达到的最强表达能力。[6]
训练与推理
GNN 使用标准的基于梯度的优化器（如 Adam）配合任务特定的损失函数进行训练：节点分类使用交叉熵，回归使用均方误差，链接预测使用对比损失或间隔损失。常见的任务范式有三类：
- 节点级：为每个节点预测标签（例如，引文网络中的类别）。半监督设置（仅有少量标注节点）较为典型。
- 边级：预测两个节点是否应该连接，用于推荐和知识图谱补全。
- 图级：预测整个图的某种属性，例如分子毒性或溶解度。
扩展到大型图时需要谨慎。全批次训练会将所有节点嵌入存储在内存中，这在超过几百万个节点时是不可行的。常见替代方案包括邻居采样（GraphSAGE 风格）、子图采样（Cluster-GCN、GraphSAINT），以及以陈旧度换内存的历史嵌入缓存。在推理时，当架构参数化的是局部特征的函数而非节点身份时，GNN 是归纳的，这允许将其应用于未见过的图。
表达能力与局限性
标准的消息传递GNN在区分图方面的能力至多与 1-Weisfeiler-Leman 测试相当，这意味着存在没有任何 MPNN 能够区分的非同构图。这促使了更高阶的变体，例如 $ k $-WL GNN、用结构标识符增强节点特征的子图 GNN，以及在图上的等变Transformer。
两种众所周知的病态现象影响深层 GNN：
- 过平滑：随着深度增加，重复聚合会驱使节点嵌入趋向无法区分的值，从而损害准确率。残差连接、归一化和 PairNorm 风格的正则化器可以缓解这一现象，但无法完全解决。
- 过挤压：来自远处节点的信息会通过狭窄的瓶颈被压缩，因此在瓶颈集较小的图中难以捕获长程依赖。图重连和图 Transformer 通过添加捷径边或用全局注意力取代局部消息传递来尝试解决这一问题。
GNN 同样继承了深度学习的常见缺陷：对分布偏移敏感、依赖高质量的节点特征，以及对图结构的对抗扰动的鲁棒性有限。
与其他模型的比较
与卷积神经网络相比，GNN 将卷积操作推广到了不规则域；CNN 可以视为带有平移不变滤波器的、作用在规则网格图上的 GNN。与循环神经网络相比，GNN 作用于邻居集合而非有序序列，但迭代的消息传递可以展开为循环计算。Transformer 与之密切相关：自注意力等价于在完全连接图上运行的 GNN，而最新的图 Transformer架构将局部消息传递与全局注意力以及结构化位置编码相结合，以同时捕获归纳偏置和长程依赖。
应用
GNN 在结构比绝对特征更重要的领域取得了最先进的成果。在化学和材料科学中，它们预测分子性质、加速密度泛函理论计算，并提出合成路径。在药物发现中，它们对结合亲和力进行评分并筛选候选分子。在推荐中，它们以生产规模建模用户-物品交互图。在物理学中，它们已经学会了粒子和流体动力学的模拟器。在代码分析中，它们对抽象语法树和数据流图进行推理。消息传递抽象的多功能性，加上关系数据的普遍存在，已经使 GNN 成为现代机器学习的核心工具。