图神经网络

图神经网络（Graph Neural Networks，简称GNNs）是一类专门设计用于输入为图的人工神经网络。

图神经网络的典型应用如分子药物设计，每个输入样本都是一个分子的图表示，其中原子形成节点，原子之间的化学键形成边。除了图表示之外，输入还包括每个原子的已知化学性质。因此，数据集样本的长度可能不同，这反映了分子中原子数量的变化以及它们之间键的数量的变化。该网络的最终任务是预测给定分子在特定医疗应用中的功效，例如消除大肠杆菌（E. coli）。

GNN的关键设计元素是使用“成对消息传递（pairwise message passing）”机制，通过这种方式，图节点通过与它们的邻居交换信息来迭代地更新其表示。目前已经提出了几种GNN架构，实现了不同形式的消息传递，这些架构的最初形式包括递归或卷积构造。是否有可能定义“超越”消息传递的GNN架构，或者是否每个GNN都可以建立在适当定义的图上的消息传递之上，仍是一个未解的开放问题。

<image>

在更广泛的“几何深度学习”主题中，某些现有的神经网络架构可以被解释为在适当定义的图上运行的GNN。在计算机视觉的背景下，一个卷积神经网络层可以被认为是一个应用于图的GNN，该图的节点是像素，并且在图中只有相邻的像素由边连接。在自然语言处理中，一个Transformer层可以被认为是一个应用于完全图的GNN，该完全图的节点是一段自然语言文本中的单词或词元。

GNN的相关应用领域包括自然语言处理、社交网络、引文网络、分子生物学、化学、物理学和NP-hard组合优化问题。

实现GNN的开源库包括PyTorch Geometric（PyTorch）、TensorFlow GNN（TensorFlow）、Deep Graph Library（框架无关）、jraph（Google JAX），以及GraphNeuralNetworks.jl/GeometricFlux.jl（Julia，Flux）等。

## 架构

通用GNN的架构实现了以下基本的层：

- 排列等变（Permutation equivariant）：排列等变层将图的表示映射为同一图的更新表示。在文献中，排列等变层是通过图节点之间的成对消息传递来实现的。直观地说，在消息传递层中，节点通过“聚合（aggregating）”从其直接邻居接收到的“消息（messages）”来“更新（update）”其表示。因此，每个消息传递层都会使GNN的感受野增加一跳。
- 局部池化（Local pooling）：局部池化层通过降采样使图粗粒化。局部池化用于增加GNN的感受野，其方式类似于卷积神经网络中的池化层。示例包括k-最近邻池化、top-k池化和自注意力池化。
- 全局池化（Global pooling）：全局池化层，也称为“读出（readout）”层，提供整个图的固定大小表示。全局池化层必须是排列不变的，以使图节点和边的排序排列不会改变最终输出，例如逐元素求和、平均值或最大值。

事实证明，GNN的表达能力无法超越Weisfeiler-Lehman图同构测试。在实践中，这意味着存在GNN无法区分的不同图结构（例如，具有相同原子但不同键的分子）。可以设计在更高维几何结构（如单纯复形）上运行的更强大的GNN。未来的架构是否能克服消息传递基元仍是一个开放的研究问题。

<image>

## 消息传递层

<image>

消息传递层是排列等变层，将图映射为同一图的更新表示。形式上，它们可以表示为消息传递神经网络（MPNN）。

令$G = (V,E)$为图，其中$V$是节点集，$E$是边集。令$N_u$为某个节点$u \in V$的邻域。此外，令$\mathbf{x}_u$为节点$u \in V$的特征，$\mathbf{e}_{uv}$为边$(u, v) \in E$的特征。一个MPNN层可以表示如下：

$$\mathbf{h}_u = \phi \left( \mathbf{x}_u, \bigoplus_{v \in N_u} \psi(\mathbf{x}_u, \mathbf{x}_v, \mathbf{e}_{uv}) \right)$$

其中$\phi$和$\psi$是可微函数（例如，人工神经网络），而$\bigoplus$是一个排列不变的聚合算子，可以接受任意数量的输入（例如，逐元素求和、平均值或最大值）。特别地，$\phi$和$\psi$分别被称为“更新（update）”和“消息（message）”函数。直观地说，在一个MPNN计算块中，图节点通过“聚合”从其邻居接收到的“消息”来“更新”其表示。

一个或多个MPNN层的输出是图中每个节点$u \in V$的节点表示$\mathbf{h}_u$。节点表示可以用于任何下游任务，例如节点/图的分类或边预测。

MPNN中的图节点通过聚合其直接邻居的信息来更新其表示。因此，堆叠$n$个MPNN层意味着一个节点将能够与最多相距$n$“跳（hops）”的节点进行通信。原则上，为了确保每个节点都能接收到来自所有其他节点的信息，需要堆叠数量等于图直径的MPNN层。然而，堆叠许多MPNN层可能会导致过度平滑（oversmoothing）和过度挤压（oversquashing）等问题。过度平滑是指节点表示变得不可区分的问题。过度挤压是指将长程依赖关系压缩到固定大小的表示中而产生的瓶颈。跳跃连接（如在残差神经网络中）、门控更新规则和跳跃知识等对策可以缓解过度平滑。将最终层修改为全相邻层（即通过将图视为完全图），可以在需要长程依赖关系的问题中缓解过度挤压。

文献中已经开发了其他形式的MPNN，例如图卷积网络和图注意力网络，它们的定义可以用MPNN形式地来表达。

### 图卷积网络

图卷积网络（GCN）由Thomas Kipf和马克斯·威灵于2017年首次提出。

GCN层定义了图上局部谱过滤的一阶近似。GCN可以理解为卷积神经网络对图结构数据的推广。

GCN层的形式化表达式如下：

$$\mathbf{H} = \sigma\left(\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}} \mathbf{X} \mathbf{\Theta}\right)$$

其中$\mathbf{H}$是节点表示$\mathbf{h}_u$的矩阵，$\mathbf{X}$是节点特征$\mathbf{x}_u$的矩阵，$\sigma(\cdot)$是一个激活函数（例如ReLU），$\tilde{\mathbf{A}}$是添加了自环的图邻接矩阵，$\tilde{\mathbf{D}}$是添加了自环的图度矩阵，$\mathbf{\Theta}$是可训练参数矩阵。

特别地，令$\mathbf{A}$为图的邻接矩阵：那么，可以定义$\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I}$且$\tilde{\mathbf{D}}_{ii} = \sum_{j \in V} \tilde{A}_{ij}$，其中$\mathbf{I}$表示单位矩阵。这种归一化确保了$\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}}$的特征值限制在$[0, 1]$范围内，从而避免了数值不稳定性和梯度爆炸/消失问题。

GCN的一个局限性是它们不允许存在多维边特征$\mathbf{e}_{uv}$。然而，可以通过施加$A_{uv} = w_{uv}$来将标量权重$w_{uv}$关联到每条边，即通过将邻接矩阵中的每个非零项设置为等于相应边的权重。

### 图注意力网络

图注意力网络（GAT）由Petar Veličković等人于2018年提出。

图注意力网络是GNN和注意力层的结合。在图神经网络中实现注意力层有助于将注意力或焦点提供给数据中的重要信息，而不是关注整个数据。

多头（multi-head）GAT层可以表示如下：

$$\mathbf{h}_u = \overset{K}{\underset{k=1}{\Big\Vert}} \sigma \left(\sum_{v \in N_u} \alpha_{uv}^k \mathbf{W}^k \mathbf{x}_v\right)$$

其中$K$是注意力头的数量，$\Big\Vert$表示向量拼接，$\sigma(\cdot)$是一个激活函数（例如，ReLU），$N_{u}$是节点$u$的直接相邻节点的集合（包括节点$u$本身），$\alpha_{uv}^k$是第$k$个注意力头的注意力系数，$W^k$是第$k$个注意力头的可训练参数矩阵。

对于最终的GAT层，在应用激活函数之前，将每个注意力头的输出取平均值。形式上，最终的GAT层可以写成：

$$\mathbf{h}_u = \sigma \left(\frac{1}{K}\sum_{k=1}^K \sum_{v \in N_u} \alpha_{uv}^k \mathbf{W}^k \mathbf{x}_v\right)$$

机器学习中的注意力是一种模仿认知注意力的技术。在图学习的背景下，注意力系数$\alpha_{uv}$衡量了节点$v$对节点$u$的“重要程度”。

归一化的注意力系数计算如下：

$$\alpha_{uv} = \frac{\exp(\text{LeakyReLU}\left(\mathbf{a}^T [\mathbf{W} \mathbf{x}_u \Vert \mathbf{W} \mathbf{x}_v \Vert \mathbf{e}_{uv}]\right))}{\sum_{z \in N_u}\exp(\text{LeakyReLU}\left(\mathbf{a}^T [\mathbf{W} \mathbf{x}_u \Vert \mathbf{W} \mathbf{x}_z \Vert \mathbf{e}_{uz}]\right))}$$

其中$\mathbf{a}$是可学习权重的向量，$\cdot^T$表示转置，$\mathbf{e}_{uv}$是边特征（如果存在），$\text{LeakyReLU}$是一种修改的ReLU激活函数。然后通过softmax对注意力系数进行归一化，使其易于在不同节点之间进行比较。

GCN可以被看作是GAT的一个特例，其中注意力系数是不可学习的，而是固定且等于边权重$w_{uv}$。

### 门控图序列神经网络

门控图序列神经网络（GGS-NN）由Yujia Li等人于2015年提出。GGS-NN将Scarselli等人的GNN公式扩展为输出序列。消息传递框架被实现为对门控循环单元（GRU）单元的更新规则。

GGS-NN可以表示如下：

$$\mathbf{h}_u^{(0)} = \mathbf{x}_u \, \Vert \, \mathbf{0}$$

$$\mathbf{m}_u^{(l+1)} = \sum_{v \in N_u} \mathbf{\Theta} \mathbf{h}_v$$

$$\mathbf{h}_u^{(l+1)} = \text{GRU}(\mathbf{m}_u^{(l+1)}, \mathbf{h}_u^{(l)})$$

其中$\Vert$表示向量拼接，$\mathbf{0}$是零向量，$\mathbf{\Theta}$是可学习参数矩阵，$\text{GRU}$是GRU单元，$l$表示序列索引。在GGS-NN中，节点表示被视为GRU单元的隐藏状态。初始节点特征$\mathbf{x}_u^{(0)}$被零填充（zero-padded）到GRU单元的隐藏状态维度。同一个GRU单元用于更新每个节点的表示。

## 局部池化层

局部池化层通过降采样使图粗粒化。这里介绍了几种已提出的可学习局部池化策略。在这些策略中，输入是由节点特征矩阵$\mathbf{X}$表示的初始图，以及图的邻接矩阵$\mathbf{A}$。输出是新的节点特征矩阵$\mathbf{X}'$，以及新的图邻接矩阵$\mathbf{A}'$。

### Top-k池化

首先令

$$\mathbf{y} = \frac{\mathbf{X}\mathbf{p}}{\Vert\mathbf{p}\Vert}$$

其中$\mathbf{p}$是一个可学习的投影向量。投影向量$\mathbf{p}$为每个图节点计算一个标量投影值。

然后，top-k池化层可以如下表示：

$$\mathbf{X}' = (\mathbf{X} \odot \text{sigmoid}(\mathbf{y}))_{\mathbf{i}}$$

$$\mathbf{A}' = \mathbf{A}_{\mathbf{i}, \mathbf{i}}$$

其中$\mathbf{i} = \text{top}_k(\mathbf{y})$是具有前k个（top-k）最高投影分数的节点子集，$\odot$表示逐元素的矩阵乘法，$\text{sigmoid}(\cdot)$是S型函数。换句话说，具有前k个最高投影分数的节点保留在新的邻接矩阵$\mathbf{A}'$中。$\text{sigmoid}(\cdot)$操作使得投影向量$\mathbf{p}$可以通过反向传播进行训练，否则将产生离散的输出。

### 自注意力池化

首先令

$$\mathbf{y} = \text{GNN}(\mathbf{X}, \mathbf{A})$$

其中$\text{GNN}$是通用的排列等变GNN层（例如，GCN、GAT、MPNN）。

然后自注意力池化层可以如下表示：

$$\mathbf{X}' = (\mathbf{X} \odot \mathbf{y})_{\mathbf{i}}$$

$$\mathbf{A}' = \mathbf{A}_{\mathbf{i}, \mathbf{i}}$$

其中$\mathbf{i} = \text{top}_k(\mathbf{y})$是具有前k个最高投影分数的节点子集，$\odot$表示逐元素矩阵乘法。

自注意力池化层可以被视为top-k池化层的扩展。与top-k池化不同，在自注意力池化中计算的自注意力分数同时考虑了图特征和图拓扑。

## 异配图学习

同配性（Homophily）原则，即具有相同标签或相似属性的节点更有可能连接在一起，通常被认为是图神经网络（GNN）在图结构数据（尤其是节点级任务）上优于传统神经网络（NN）的主要原因。然而，最近的研究发现了一组并非微不足道的数据集，在这些数据集上，与NN相比，GNN的表现并不令人满意。异配性（Heterophily），即低同配性，被认为是这一经验观察结果的主要原因。人们已经开始在各种类型的图（例如，异构图、时序图和超图）的异配性场景中重新审视和重新评估现有的大多数图模型。此外，许多与图相关的应用被发现与异配性问题密切相关，例如图欺诈/异常检测、图对抗攻击与鲁棒性、隐私、联邦学习和点云分割、图聚类、推荐系统、生成模型、链路预测、图分类和着色等。在过去几年中，人们投入了大量精力来研究和解决图学习中的异配性问题。

## 可扩展性与分布式训练

在大型图上训练GNN所面临的计算挑战与其他神经网络架构有很大不同。出现了两大类问题设定：在单个超大图（例如具有数十亿节点的社交网络）上进行训练，以及在大型个体图的集合（例如需要高阶交互建模的分子系统）上进行训练。

对于单个大图的设定，基于采样的方法通过在子图而不是全图上进行操作来降低内存要求。Cluster-GCN使用图划分算法将图划分为子图，按顺序在每个划分上训练模型。相比之下，GraphSAINT在训练期间随机采样图，为全图损失构建无偏估计量。DistDGL等分布式框架将训练扩展到多机环境，管理当图的节点分布在多台机器上时，邻域聚合所需的机器间通信。

对于诸如原子模拟等任务，出现了不同的瓶颈：对原子三元组或四元组之间的高阶相互作用进行建模的GNN架构在单个图级别上占用大量内存，使得标准的数据并行（即每个GPU处理一个单独的样本）在单个图超出单设备内存时显得力不从心。图并行（Graph Parallelism）通过将单个输入图分布在多个GPU上，在设备之间划分节点和边而不是在设备之间分配样本来解决这个问题。这种方法使得具有数亿甚至数十亿参数的GNN能够在原本会超出单设备内存的原子系统上进行训练，并已被应用于大规模通用原子间势的开发中。

## 应用

### 蛋白质折叠

图神经网络是AlphaFold的主要组成部分之一，这是由Google的DeepMind开发的人工智能程序，用于解决生物学中的蛋白质折叠问题。AlphaFold在多项CASP竞赛中拔得头筹。

### 社交网络

社交网络是GNN的一个主要应用领域，因为它们天然地表示为社交图谱。GNN被用于开发基于社会关系和物品关系的推荐系统。

### 组合优化

GNN被用作几种组合优化算法的基础构建模块。例如，计算给定图的最短路径或欧拉回路，得出优于人工设计或与之竞争的芯片布局，以及改进分支定界中专家设计的分支规则。

### 网络安全

当将计算机网络视为图时，可以使用GNN对其进行分析以检测异常。溯源图（provenance graphs）中的异常通常与网络中的恶意活动相关。GNN已被用于识别各个节点上的这些异常以及路径内的恶意进程，或者在边级别上检测网络横向移动。

### 供水管网

供水系统可以被建模为图，因此可以直接应用GNN。此类算法已被应用于用水需求预测，互连独立计量区（DMA）以提高预测能力。该算法在配水建模中的另一个应用是开发元模型（metamodels）。

### 计算机视觉

为了将图像表示为图结构，首先将图像划分为多个补丁（patches），每个补丁被视为图中的一个节点。然后根据空间或特征相似性，通过将每个节点连接到其最近的邻居来形成边。这种基于图的表示形式能够将图学习模型应用于视觉任务。关系结构有助于增强特征提取并提高图像理解的性能。

### 文本与自然语言处理

基于图的文本表示有助于捕捉单词之间更深层的语义关系。许多研究使用图网络来提高各种文本处理任务的性能，如文本分类、问答、神经机器翻译（NMT）、事件抽取、事实核查等。

### 原子模拟与材料科学

GNN已成为在计算化学和材料科学中对原子相互作用进行建模的主要工具，在这些领域中，分子和晶体结构自然地表示为图，其中原子作为节点，化学键或空间接近度作为边。与密度泛函理论（DFT）等传统量子化学方法相比，其主要优势在于计算成本从O(n³)降低到O(n)，从而使得在以前不切实际的规模上进行模拟成为可能。

该领域早期的GNN架构包括SchNet（2017），它引入了连续滤波器卷积层用于在3D分子结构上进行学习，以及DimeNet（2020），它结合了原子之间的角度信息以提高几何表达能力。随后的等变架构（如NequIP和MACE），尊重了物理系统的旋转和平移对称性，在包括QM9、MD17和Materials Project在内的标准基准上实现了显著的精度提升。

大型开放数据集推动了该领域的快速进展。Open Catalyst 2020（OC20）数据集包含超过2.6亿次吸附物-催化剂表面相互作用的DFT计算，为与催化剂发现相关的能量和力预测任务建立了一个广泛使用的基准。Materials Project和Alexandria数据库同样为训练通用原子间势提供了大规模晶体结构数据。包括OMat24和OMol25在内的最新数据集已经将覆盖范围扩展到了更大计算规模的有机分子和复杂材料。

这些数据集促进了通用机器学习原子间势（MLIPs）的开发——这些模型跨越不同的化学领域进行训练，而不是基于特定系统的数据。例子包括CHGNet、 M3GNet、 MACE-MP，以及Meta FAIR的Universal Models for Atoms（UMA），后者在涵盖分子、材料和催化剂的约5亿个原子结构上进行了训练。由Google DeepMind开发的GNoME应用GNN来预测晶体结构的稳定性，报告称确定了数百万种新的稳定候选材料。