长程图神经网络与图Transformer

概述

图神经网络（Graph Neural Network，GNN）在处理图结构数据方面取得了巨大成功，但传统基于消息传递范式的GNN存在一个根本性限制：每层只能聚合1跳邻居的信息。这使得模型难以捕获图中节点之间的长程依赖关系（Long-Range Interactions，LRI）。¹

本文系统性地介绍长程图神经网络的理论基础、现有解决方案、Graph Transformer架构以及评估基准。

---

问题定义

消息传递范围的局限性

标准GNN的消息传递机制可以表示为：

$${\mathbf{h}}_v^{(k)}=aggregator\left(\left\{{\mathbf{h}}_v^{(k-1)}\right\}\cup \left\{{\mathbf{h}}_u^{(k-1)}:u\in \mathcal{N}(v)\right\}\right)$$

其中 $\mathcal{N}(v)$ 表示节点 $v$ 的1跳邻居。

经过 $L$ 层消息传递后，节点的感受野（Receptive Field）被限制在 $L$ 跳范围内：

$$\text{ReceptiveField}(v)=\{u:d(u,v)\le L\}$$

过挤压问题（Over-Squashing）

过挤压是导致长程依赖难以学习的关键因素。当图中存在”瓶颈”结构时，来自远距离节点的信息在传播过程中必须经过大量中间节点的信息压缩，导致有效信息丢失。²

具体而言，节点 $v$ 在 $t$ 时刻接收到的来自源节点 $s$ 的累积信息量与路径上的信息压缩系数成正比：

$$I_{s\to v}(t)\propto \prod _{(i,j)\in \text{path}(s,v)}{\alpha }_{ij}$$

其中 ${\alpha }_{ij}$ 表示边 $(i,j)$ 的压缩系数。当图中存在大量节点共享少量中间节点时，信息压缩尤为严重。

过平滑问题（Over-Smoothing）

与过挤压相关的另一个问题是过平滑：随着消息传递层数增加，节点表示趋于收敛到相似的值，导致节点可区分性下降。

设 $L$ 层消息传递后的节点表示为 ${\mathbf{H}}^{(L)}$，过平滑可以形式化为：

$$\underset{L\to \infty }{\lim }{\mathbf{h}}_v^{(L)}=\mathbf{c},\forall v\in \mathcal{V}$$

即所有节点表示趋近于同一个常数向量 $\mathbf{c}$。

为什么长程依赖重要

许多实际应用需要捕获远距离节点之间的关系：

应用场景	长程依赖示例
分子性质预测	药物分子中相距较远的原子基团可能决定整体药效
蛋白质结构	远距离氨基酸残基形成三维折叠结构
代码理解	程序中相隔很远的语句可能存在依赖关系
社交网络	信息传播路径上的间接影响
交通网络	远端路况对当前路径规划的影响

---

长程依赖的现有解决方法

图重连（Graph Rewiring）

图重连通过预处理修改图结构，使远距离节点之间建立直接连接或更短的路径。

基于随机游走的重连

随机游走嵌入（Random Walk Positional Encoding，RWPE）将随机游走概率作为节点的位置编码：

$$[{\mathbf{p}}_v^{\text{RW}}{]}_t={\left({\mathbf{A}}^t\right)}_{v,\text{start}}/d_{\text{start}}^t$$

其中 $\mathbf{A}$ 为邻接矩阵，$t$ 为随机游走步数。

代表性工作包括：

• DeepWalk / Node2Vec：通过随机游走生成节点序列，学习嵌入向量³
• LINE：保留一阶和二阶邻近性的图嵌入方法

基于扩散的重连

图扩散（Graph Diffusion）通过扩散过程增强图的全局连通性：

$$\mathbf{S}=\sum _{t=0}^{\infty }{\alpha }_t{\mathbf{T}}^t$$

其中 $\mathbf{T}$ 是转移矩阵，$\{{\alpha }_t\}$ 是扩散系数。常用的扩散核包括：

• 热核（Heat Kernel）：${\alpha }_t=e^{-t}\frac{t^k}{k!}$
• PPR（Personalized PageRank）：${\alpha }_t=\alpha (1-\alpha {)}^t$

有效电阻重连（ERR）

最近的工作提出基于有效电阻（Effective Resistance）进行图重连：

$$R_{ij}^{\text{eff}}={\left({\mathbf{e}}_i-{\mathbf{e}}_j\right)}^{\top }{\mathbf{L}}^{†}\left({\mathbf{e}}_i-{\mathbf{e}}_j\right)$$

有效电阻越小，表示两节点之间的信息传递越高效。ERR方法通过降低高有效电阻边的影响来缓解过挤压问题。⁴

K跳消息传递

自适应感受野

PNA（Principal Neighbourhood Aggregation）通过组合多种聚合算子增强表达能力：

$$\text{PNA}({\mathbf{h}}_v)=\text{Concat}\left(\underset{d\in \{\text{mean},\text{max},\text{std}\}}{⨁}\underset{s\in S}{⨁}{\mathbf{m}}_{s,d}(\mathcal{N}(v))\right)$$

其中 $S$ 是不同尺度邻居的集合。

DIFFPOOL与分层聚合

DIFFPOOL通过层次化池化生成不同粒度的图表示：

$${\mathbf{Z}}^{(l)}={\text{GNN}}_l({\mathbf{A}}^{(l)},{\mathbf{X}}^{(l)})$$ $${\mathbf{X}}^{(l+1)}={\mathbf{Z}}^{(l{)}^{\top }}{\mathbf{H}}^{(l)},{\mathbf{A}}^{(l+1)}={\mathbf{Z}}^{(l{)}^{\top }}{\mathbf{A}}^{(l)}{\mathbf{Z}}^{(l)}$$

基于微分方程的GNN

GRAND：图神经扩散

GRAND（Graph Neural Diffusion）将图上的深度学习建模为连续扩散过程：

$$\frac{\partial \mathbf{h}(t)}{\partial t}=(\mathbf{L}+\alpha \mathbf{I})\mathbf{h}(t)$$

其中 $\mathbf{L}$ 是归一化拉普拉斯矩阵，$\alpha$ 是自连接权重。通过求解此ODE，可以获得任意时间点的节点表示，从而实现灵活的感受野控制。⁵

import torch
import torch.nn as nn
 
class GRANDLayer(nn.Module):
    """GRAND的单层实现"""
    def __init__(self, dim, alpha=1.0, theta=1.0):
        super().__init__()
        self.alpha = alpha
        self.theta = theta
        self.linear = nn.Linear(dim, dim)
    
    def forward(self, h, L):
        """
        h: 节点特征 (N, d)
        L: 归一化拉普拉斯矩阵 (N, N)
        """
        dhdt = self.alpha * h + self.theta * L @ self.linear(h)
        return dhdt
 
class GRANDModel(nn.Module):
    """GRAND模型，使用Euler法求解ODE"""
    def __init__(self, num_layers, dim, alpha=1.0, theta=1.0, step_size=0.1):
        super().__init__()
        self.num_layers = num_layers
        self.step_size = step_size
        self.layers = nn.ModuleList([
            GRANDLayer(dim, alpha, theta) for _ in range(num_layers)
        ])
        self.L = None
    
    def set_laplacian(self, L):
        self.L = L
    
    def forward(self, h):
        t = 0
        for layer in self.layers:
            h = h + self.step_size * layer(h, self.L)  # Euler步进
            t += self.step_size
        return h

Neural Graph Differential Equations

Neural GDE将GNN层视为ODE的离散化：

$${\mathbf{h}}^{\prime }(t)=f(\mathbf{h}(t),\mathbf{A}),\mathbf{h}(0)=\mathbf{x}$$

通过调整ODE的求解精度，可以控制信息传播的范围和效率。

虚拟边

虚拟边（Virtual Edges）通过添加全连接边增强图的连通性：

$$\tilde{\mathbf{A}}=\mathbf{A}+\beta \mathbf{J}$$

其中 $\mathbf{J}$ 是全1矩阵，$\beta$ 是虚拟边的权重。这种方法本质上与完全连接Transformer类似。

---

Graph Transformer

概述：为什么用Transformer处理图数据

Transformer通过自注意力机制实现任意位置之间的直接交互，天然适合建模长程依赖：

$$\text{Attention}(\mathbf{Q},\mathbf{K},\mathbf{V})=\text{softmax}\left(\frac{\mathbf{Q}{\mathbf{K}}^{\top }}{\sqrt{d}}\right)\mathbf{V}$$

然而，直接将标准Transformer应用于图数据存在挑战：

1. 位置编码：序列有天然的位置顺序，而图节点无固定顺序
2. 结构信息：序列数据假设相邻元素相关，图数据的关系更复杂
3. 计算复杂度：$O(N^2)$ 的注意力计算在大图上难以承受

四类架构分类

根据2025年的Graph Transformer综述⁶，现有架构可分为四大类：

a）多层次图分词（Multi-level Graph Tokenization）

将图的不同粒度作为Transformer的输入token。

方法	分词策略	特点
Edge Direction	边作为token	显式建模边特征
Subgraph	子图作为token	捕获局部结构
Graphormer	全图+节点	层次化表示

Graphormer的tokenization策略：

$${\mathbf{X}}_{\text{input}}=\text{MLP}\left({\mathbf{X}}_{\text{node}}\right)+{\text{PE}}_{\text{deg}}+{\text{PE}}_{\text{edge}}+{\text{PE}}_{\text{spatial}}$$

import torch
import torch.nn as nn
import math
 
class GraphormerEmbedding(nn.Module):
    """Graphormer的嵌入层"""
    def __init__(self, num_nodes, d_model, max_path_len=128):
        super().__init__()
        self.node_embed = nn.Embedding(num_nodes, d_model)
        self.degree_embed = nn.Embedding(num_nodes, d_model)  # 度编码
        self.path_len_embed = nn.Embedding(max_path_len, d_model)  # 最短路径编码
        
        self.x_embed_proj = nn.Linear(d_model, d_model)
    
    def forward(self, x, degree, shortest_path):
        """
        x: 节点特征
        degree: 节点度数
        shortest_path: 节点对之间的最短路径长度
        """
        h = self.x_embed_proj(x)
        h = h + self.degree_embed(degree)
        h = h + self.path_len_embed(shortest_path.clamp(0, 127))
        return h

b）结构位置编码（Structural Positional Encoding）

通过图的结构属性生成位置编码。

拉普拉斯位置编码（Laplacian PE）利用拉普拉斯特征向量：

$$\mathbf{L}=\mathbf{I}-{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}=\mathbf{U\Lambda }{\mathbf{U}}^{\top }$$

取前 $k$ 个最小特征值对应的特征向量作为位置编码：

$${\mathbf{PE}}_{\text{Laplacian}}(v)=\left[{\mathbf{U}}_{v,1},{\mathbf{U}}_{v,2},\dots ,{\mathbf{U}}_{v,k}\right]$$

随机游走位置编码（RWPE）：

$$[{\mathbf{PE}}_{\text{RWPE}}{]}_t=\frac{1}{t!}{\mathbf{D}}^{-1}{\mathbf{A}}^{t}1$$

c）结构感知注意力机制

在注意力计算中引入图结构信息。

SAN（Spectral Attention Network）的注意力机制：

$$e_{ij}=\frac{({\mathbf{W}}_Q{\mathbf{h}}_i{)}^{\top }({\mathbf{W}}_K{\mathbf{h}}_j)}{\sqrt{d}}+{\mathbf{b}}_{[{\lambda }_i-{\lambda }_j]}$$

其中 ${\lambda }_i$ 是拉普拉斯特征值，$\mathbf{b}$ 是可学习的偏置。

import torch
import torch.nn as nn
import torch.nn.functional as F
 
class SpectralAttention(nn.Module):
    """SAN的光谱注意力实现"""
    def __init__(self, d_model, num_heads, num eigenvecs):
        super().__init__()
        self.num_heads = num_heads
        self.d_k = d_model // num_heads
        self.eigenvalue_embed = nn.Embedding(100, num_heads)  # 特征值嵌入
        
        self.W_q = nn.Linear(d_model, d_model)
        self.W_k = nn.Linear(d_model, d_model)
        self.W_v = nn.Linear(d_model, d_model)
        self.W_o = nn.Linear(d_model, d_model)
    
    def forward(self, h, eigenvalue_idx):
        """
        h: 节点特征 (N, d_model)
        eigenvalue_idx: 特征值索引 (N,)
        """
        batch_size = h.size(0)
        
        # 线性变换并分头
        Q = self.W_q(h).view(batch_size, -1, self.num_heads, self.d_k).transpose(1, 2)
        K = self.W_k(h).view(batch_size, -1, self.num_heads, self.d_k).transpose(1, 2)
        V = self.W_v(h).view(batch_size, -1, self.num_heads, self.d_k).transpose(1, 2)
        
        # 基础注意力分数
        scores = torch.matmul(Q, K.transpose(-2, -1)) / math.sqrt(self.d_k)
        
        # 光谱偏置
        eig_bias = self.eigenvalue_embed(eigenvalue_idx)  # (N, num_heads)
        scores = scores + eig_bias.unsqueeze(2) - eig_bias.unsqueeze(1)  # 对角线偏置
        
        # 归一化和加权求和
        attn_weights = F.softmax(scores, dim=-1)
        output = torch.matmul(attn_weights, V)
        
        # 合并多头
        output = output.transpose(1, 2).contiguous().view(batch_size, -1, self.num_heads * self.d_k)
        return self.W_o(output)

d）模型集成（GNN + Transformer混合）

结合GNN的局部建模能力和Transformer的全局交互能力。

常见架构模式：

模式	结构	特点
并行混合	GNN + Transformer并联	各自独立处理，输出融合
串行混合	GNN → Transformer	GNN捕获局部，Transformer捕获全局
层次混合	多层GNN + 全局Transformer	层次化信息聚合

import torch
import torch.nn as nn
from torch_geometric.nn import GCNConv
 
class GNNTransformerHybrid(nn.Module):
    """GNN与Transformer的串行混合架构"""
    def __init__(self, in_channels, hidden_channels, out_channels, num_heads=4):
        super().__init__()
        # GNN层：捕获局部结构
        self.gnn1 = GCNConv(in_channels, hidden_channels)
        self.gnn2 = GCNConv(hidden_channels, hidden_channels)
        
        # Transformer层：捕获全局依赖
        self.self_attn = nn.MultiheadAttention(hidden_channels, num_heads, batch_first=True)
        self.norm1 = nn.LayerNorm(hidden_channels)
        self.ffn = nn.Sequential(
            nn.Linear(hidden_channels, hidden_channels * 4),
            nn.GELU(),
            nn.Linear(hidden_channels * 4, hidden_channels)
        )
        self.norm2 = nn.LayerNorm(hidden_channels)
    
    def forward(self, x, edge_index):
        # GNN层
        x = self.gnn1(x, edge_index)
        x = torch.relu(x)
        x = self.gnn2(x, edge_index)
        
        # Transformer层
        h = self.norm1(x)
        h, _ = self.self_attn(h, h, h)
        x = x + h
        
        h = self.norm2(x)
        h = self.ffn(h)
        x = x + h
        
        return x

代表性模型

Graphormer

Graphormer由微软研究院提出，是首个在OGB（Open Graph Benchmark）上取得SOTA的Transformer模型。⁷

核心创新：

1. 中心性编码（Centrality Encoding）：编码节点度数
2. 空间编码（Spatial Encoding）：基于最短路径距离
3. 边编码（Edge Encoding）：编码边属性

SAN：光谱注意力网络

SAN（Spectral Attention Network）利用拉普拉斯光谱作为位置编码：

• 学习拉普拉斯特征向量的嵌入
• 将光谱信息注入注意力偏置
• 理论上可区分1-WL测试无法区分的图

GPS：图位置编码Transformer

GPS（Graph GPS）结合了消息传递和全局注意力的优势：

$${\mathbf{h}}_v^{(l)}=\text{TransformerLayer}\left({\mathbf{h}}_v^{(l-1)}+\text{MP}({\mathbf{h}}^{(l-1)})\right)$$

Graph Transformer vs 传统GNN

维度	传统GNN	Graph Transformer
感受野	局部（$L$跳）	全局（所有节点）
计算复杂度	$O(E\cdot d)$	$O(N^2\cdot d)$
位置编码	隐式学习	显式设计
表达能力	受限于WL测试	理论更强
适用场景	局部结构重要	全局依赖关键

---

评估基准

LRGB：长程图基准

LRGB（Long-Range Graph Benchmark）由Dwivedi等人于2022年提出，专门评估模型的长程依赖建模能力。¹

数据集构成

数据集	任务类型	节点数	特点
PascalVOC-SP	节点分类	~5K	长程语义依赖
COCO-SP	节点分类	~12K	视觉场景理解
PCQM-Contact	链接预测	~18K	分子接触预测
Peptides-func	图分类	~15K	肽功能预测
Peptides-struct	图回归	~15K	肽结构预测

评估指标

• 节点分类：F1分数
• 链接预测：Hits@K、MRR
• 图分类：平均精度/AP
• 图回归：MAE、RMSE

ECHO基准

ECHO（Equivariant Chemical Graph mOdels）是另一个评估图模型在分子任务上表现的基准，侧重于分子的物理化学性质预测。

其他长程基准

• ZINC：分子性质回归
• MOL-HIV：分子属性分类
• CodeXGLUE：代码理解任务

---

实际应用

分子性质预测

分子性质（如溶解度、毒性、药代动力学）往往由分子中相距较远的原子基团共同决定。

PCQM4K数据集要求模型理解分子图中的全局结构关系。

蛋白质结构预测

蛋白质的三维结构由氨基酸序列的远程相互作用决定：

• AlphaFold使用注意力机制建模氨基酸之间的空间关系
• Graphormer在蛋白质接触预测任务上表现优异

代码理解

代码的语义理解需要捕获跨越多行的依赖关系：

# 示例：长距离依赖
class Model(nn.Module):
    def __init__(self):
        self.layer1 = None  # 初始化
        self.layer2 = None  # 定义
        self.layer3 = None  # 结构
        # ...
    
    def forward(self, x):
        # 使用
        x = self.layer1(x)  # 依赖很远
        return self.layer3(self.layer2(x))  # 调用

代码的AST（抽象语法树）中，节点之间的边可能跨越很长的距离。

---

总结与展望

当前进展

1. Graph Transformer已在大规模图数据集上展示出优于传统GNN的性能
2. 图重连技术为缓解过挤压问题提供了有效途径
3. 微分方程方法提供了连续化的建模框架

开放问题

1. 计算效率：全注意力机制在大图上的可扩展性
2. 理论理解：Graph Transformer的表达能力界限尚不清楚
3. 最优架构：如何自动选择合适的位置编码和注意力机制

未来方向

• 高效Transformer：稀疏注意力、近似方法
• 预训练图模型：大规模图数据的自监督预训练
• 多模态融合：结合分子结构、文本描述等信息

---

参考

Footnotes

1. Dwivedi et al., “Long Range Graph Benchmark”, NeurIPS 2022 Datasets and Benchmarks Track ↩ ↩²

2. Topping et al., “Understanding over-squashing and over-smoothing on graphs”, ICLR 2022 ↩

3. Perozzi et al., “DeepWalk: Online Learning of Social Representations”, KDD 2014 ↩

4. Gutteridge et al., “Towards more efficient graph rewiring via effective resistance”, arXiv 2024 ↩

5. Chamberlain et al., “GRAND: Graph Neural Diffusion”, ICML 2021 ↩

6. Yuan et al., “A Survey of Graph Transformers: Architectures, Theories and Applications”, arXiv 2025 ↩

7. Ying et al., “Do Transformers Really Perform Badly for Graph Representation?”, NeurIPS 2021 ↩