图神经网络表达能力：WL测试的局限性与新视角

概述

Weisfeiler-Lehman（WL）测试长期以来是评估图神经网络（GNN）表达能力的主要理论框架¹²。然而，最新的研究表明，这一框架存在显著的理论缺陷和实践盲点³⁴。本章深入分析WL测试的局限性，并介绍表达能力研究的新方向——消息传递复杂性（Message Passing Complexity）。

WL测试基础回顾

1-WL算法

1-WL（也称为颜色细化）是最常用的同构性测试算法：

输入：图 G = (V, E)
初始化：每个节点v分配初始颜色c₀(v)

迭代直到收敛：
    对于每个节点v：
        计算多重集 M(v) = {cₜ(u) : u ∈ N(v)}
        更新 cₜ₊₁(v) = hash(cₜ(v), M(v))

输出：最终颜色划分

WL测试与GNN的关系

G消息传递神经网络（MPNN）的表达能力被WL测试界定：

$$\text{Expressivity}(GNN)\le \text{Expressivity}(1-WL)$$

定理（Xu et al., 2019）：如果1-WL无法区分两个图，则任何使用1-WL界定的GNN也无法区分它们。

WL测试的局限性

1. 二元性判断的粗糙性

WL测试给出的是二元判断（能区分/不能区分），无法量化区分能力³：

图对	WL结果	实际区分难度	差异
$C_6$ vs $C_6$+噪声	相同	困难	❌
$C_6$ vs $C_6$	相同	容易	❌
规则图 vs 规则图	相同	可变	❌

问题：所有规则图（如两个$C_6$）在WL测试下都是等价的，但它们的”相似程度”可能差异巨大。

2. 理想化假设的脱离实际

WL理论基于两个不现实的假设³：

1. 无限表达能力：假设节点嵌入可以区分任意多个不同颜色
2. 完美聚合：假设邻居聚合可以完美保留所有信息

实际情况：

• 嵌入维度 $d$ 是有限的
• 数值精度限制了可区分的颜色数
• 训练过程引入近似误差

3. 无法捕获计算复杂性

WL测试关注图同构（isomorphism），但实际任务关心的是计算复杂性（computational complexity）⁵：

考虑图属性检测任务：

• 三角计数：1-WL无法完成，但计算简单
• 最短路径：需要更深层网络
• 图连通性：计算复杂度高

WL测试无法区分这些问题对GNN的难度差异。

4. 与实践能力的脱节

研究发现⁴：

“WL测试的表达能力评估与GNN在真实任务上的性能相关性较弱”

实验证据：

• 在分子性质预测任务上，WL等价的GNN可能性能差异巨大
• 某些WL表达能力较低的架构在实践中表现更好
• 图级别任务（graph-level tasks）受节点级别表达能力影响有限

消息传递复杂性：新视角

核心思想

消息传递复杂性（Message Passing Complexity, MPC）框架³提出：

不是问”GNN能区分哪些图”，而是问”区分特定图对需要多少消息传递步骤”

MPC的形式化定义

对于图 $G$ 和目标节点 $v$，定义：

$$\text{MPC}(G,v)=\text{最小消息传递步数，使节点 }v\text{ 获得足够信息}$$

对于图对 $(G_1,G_2)$：

$$\text{MPC}(G_1,G_2)=\underset{v_1\in V_1,v_2\in V_2}{\min }\max (\text{MPC}(G_1,v_1),\text{MPC}(G_2,v_2))$$

MPC的优势

方面	WL测试	MPC
输出类型	二元（区分/不区分）	连续值（复杂度）
考虑计算成本	否	是
实际任务相关性	低	高
区分相似图	不能	能

MPC的应用示例

示例1：正则图的区分

考虑两个正则图：

图A：六边形环 C₆
图B：两个三角形 K₃ ⊕ K₃（不连通并）

WL分析：两者都是3-正则图，1-WL无法区分。

MPC分析：

图	中心节点MPC	边节点MPC
C₆	3	2
K₃⊕K₃	1	0

MPC成功区分了这两个图！

示例2：分子性质预测

在分子性质预测任务中：

性质：分子是否有芳香环
图结构：苯环 vs 脂肪环

WL：两者都是环，区分困难
MPC：芳香环需要"闻到"整个环结构 → 更高MPC

示例3：图同构测试

对于实际同构性检测任务⁵：

$$\text{Isomorphism}(G_1,G_2)\propto \text{MPC差异}(G_1,G_2)$$

MPC提供了比WL更精细的度量。

超越WL：表达能力的多维评估

表达能力的多维度

维度	WL度量	实际影响
区分能力	同构测试	图级任务性能
计算效率	无	所需网络深度
记忆容量	无	子图模式存储
泛化能力	无	分布外性能

新表达能力度量

1. 子图计数能力

GNN可以计数特定子图模式⁶：

$${\text{Count}}_{\text{pattern}}(G)=\text{GNN的输出}$$

研究显示：

• 1-WL GNN → 计数同构类
• 2-WL GNN → 计数连通子图
• 更高WL → 计数更复杂的子图

2. 拓扑距离度量

基于图拉普拉斯谱的拓扑距离：

$$d_{\text{spec}}(G_1,G_2)=\Vert \lambda (G_1)-\lambda (G_2){\Vert }_2$$

其中 $\lambda (G)$ 是图拉普拉斯矩阵的特征值。

3. 计算复杂性边界

GNN的计算复杂性（complexity class）⁷：

GNN类型	表达能力
标准MPNN	$\subseteq$ TC⁰
带有读出函数	$\subseteq$ P
变分MPNN	可能达到NP

WL局限性的实践解决方案

1. 架构改进

针对WL局限性的改进方向：

┌─────────────────────────────────────────────────────────┐
│                    GNN架构改进                          │
├──────────────┬──────────────────────────────────────────┤
│ 瓶颈问题     │ 解决方案                                 │
├──────────────┼──────────────────────────────────────────┤
│ 过度平滑     │ DropEdge、PairNorm、Identity Mapping     │
│ 过度压缩     │ DAG聚合、跳连、图Transformers            │
│ 正则图区分难 │ 位置编码、虚拟节点、结构增强             │
│ 表达能力有限 │ 更高阶消息传递、彩色边、超图GNN          │
└──────────────┴──────────────────────────────────────────┘

2. 结构增强技术

虚拟节点注入

为每个图添加连接到所有节点的虚拟节点：

class VirtualNodeGNN(nn.Module):
    def __init__(self, input_dim, hidden_dim, output_dim):
        super().__init__()
        self.virtual_emb = nn.Parameter(torch.randn(1, hidden_dim))
        self.encoder = GCNConv(input_dim, hidden_dim)
        self.message_passing = GCNConv(hidden_dim, hidden_dim)
        self.decoder = GCNConv(hidden_dim, output_dim)
    
    def forward(self, x, edge_index):
        batch_size = x.shape[0]
        
        # 扩展虚拟节点到batch
        virtual_nodes = self.virtual_emb.expand(batch_size, -1, -1)
        
        # 拼接虚拟节点
        x_extended = torch.cat([x, virtual_nodes], dim=1)
        
        # 添加虚拟连接（每个节点连向虚拟节点）
        n_nodes = x.shape[1]
        virtual_edge = torch.tensor([[n_nodes]*batch_size, 
                                      list(range(n_nodes))])
        edge_index_extended = torch.cat([edge_index, virtual_edge], dim=1)
        
        # 消息传递
        h = F.relu(self.encoder(x_extended, edge_index_extended))
        h = F.relu(self.message_passing(h, edge_index_extended))
        
        # 读出（包含虚拟节点信息）
        out = self.decoder(h, edge_index_extended)
        
        return out

位置编码集成

使用图拉普拉斯位置编码（LAPE）：

$$PE(v)=\left[{\lambda }_1^{1/2}{\varphi }_1(v),{\lambda }_2^{1/2}{\varphi }_2(v),\dots ,{\lambda }_k^{1/2}{\varphi }_k(v)\right]$$

其中 ${\lambda }_i$ 和 ${\varphi }_i$ 是图拉普拉斯算子的特征对。

3. 超图神经网络

将图扩展到超图：

class HypergraphGNN(nn.Module):
    """
    超图GNN：超边可以连接多个节点
    表达能力 > 标准WL测试
    """
    def __init__(self, input_dim, hidden_dim, output_dim):
        super().__init__()
        self.node_encoder = nn.Linear(input_dim, hidden_dim)
        self.hyperedge_encoder = nn.Linear(input_dim * k, hidden_dim)  # k阶超边
        self.propagation = HyperedgeMessagePassing(hidden_dim)
        self.readout = Set2Set(hidden_dim, output_dim)
    
    def forward(self, x, hyperedges):
        # x: 节点特征
        # hyperedges: 超边列表，每个超边是节点索引列表
        h = self.node_encoder(x)
        
        # 超边级别消息传递
        h = self.propagation(h, hyperedges)
        
        return self.readout(h)

实践建议

选择GNN架构的指南

任务类型	推荐架构	理由
小图精确分类	2-WL+ GNN或彩色GNN	需要区分细粒度结构
大图模式检测	浅层GNN + 位置编码	避免过度平滑
图生成/预测	层次化GNN	捕获多尺度结构
分布外泛化	GNN + Invariant Learning	增强鲁棒性

评估指标建议

不要仅用WL表达能力评估GNN，建议同时使用：

1. 理论指标：计算复杂性、消息传递复杂度
2. 实验指标：下游任务性能、泛化能力
3. 诊断指标：子图计数准确率、结构检测率

总结

WL测试作为GNN表达能力的评估框架存在显著局限：

1. 二元判断：无法量化区分能力
2. 理想假设：脱离实际数值精度和计算限制
3. 任务脱节：与实际任务性能相关性低
4. 复杂性盲点：忽略计算复杂性差异

消息传递复杂性（MPC）框架提供了更精细的评估视角，能够：

• 量化区分特定图对的难度
• 预测实际任务性能
• 指导网络深度设计

未来研究方向：

• 统一的表达能力理论框架
• 任务自适应的架构选择
• 表达效率与计算效率的权衡

参考文献

Footnotes

1. Xu et al. (2019). “How Powerful are Graph Neural Networks?” ICLR 2019 ↩

2. Morris et al. (2019). ” Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks.” AAAI 2019 ↩

3. [NeurIPS 2025] “What Expressivity Theory Misses: Message Passing Complexity for Graph Neural Networks” ↩ ↩² ↩³ ↩⁴

4. [ICLR 2025] “Rethinking the Expressiveness of GNNs” ↩ ↩²

5. [OpenReview 2025] “On the Expressive Power of GNNs for Boolean Satisfiability” ↩ ↩²

6. [IEEE 2025] “The Expressive Power of Graph Neural Networks: A Survey” ↩

7. [arXiv 2410.01308] “Revisiting WL-Test Hardness and GNN Expressive Power” ↩