一句话总结

北京大学与北京智源人工智能研究院的研究者提出同态可表达性，这是一种通过在同态下计数图来衡量 GNN 表达能力的量化框架，克服了 Weisfeiler-Lehman 层级粗糙且定性的局限，并统一了不变架构与等变架构之间的表达能力比较。

核心贡献

• 提出同态可表达性，作为一种通过衡量图神经网络在同态下计数图的能力来评估其表达能力的量化框架，提供超越定性 Weisfeiler-Lehman 层级的完整表达能力比较。

• 为四种代表性 GNN 家族在不变与等变设定下推导出精确的同态可表达性描述，建立模型层级、图级、节点级和边级子图计数能力，并解决若干开放问题。

• 大量合成与真实世界实验支持理论结果，并显示经验性 GNN 性能与同态可表达性指标相关。

引言

图神经网络广泛用于图结构数据，但其区分不同图结构的能力常常受限。衡量这种局限的常用方式是 Weisfeiler-Lehman 层级，尤其是消息传递 GNN 的 1-WL 界限。然而这一标尺对于实际模型而言过于粗糙：高阶方法可能代价高昂，而基于 1-WL 的证明结果可能依赖小型示例图，无法解释真实世界性能。作者利用同态计数研究 GNN 能够编码哪些图子结构，并给出 MPNN、Subgraph GNN、Local GNN 和 Folklore-type GNN 表达能力的精确描述，同时扩展到节点级、边级和高阶变体。

方法

该方法建立一个统一分析框架，通过同态计数度量图神经网络架构的表达能力。对于具有表示 $\chi_G^M(\cdot)$χGM​(⋅) 的图表示模型 $M$M，核心思想是精确刻画哪些子结构对模型不可见。定义图家族 $\mathcal{F}^M$FM 为一个极大带标号图家族，使得两个图获得相同表示当且仅当来自 $\mathcal{F}^M$FM 中所有图的同态计数都相同。形式上，等价条件写为：

$$\chi_G^M(G)=\chi_H^M(H) \quad\Longleftrightarrow\quad \mathsf{hom}(F,G)=\mathsf{hom}(F,H) \quad \forall F\in\mathcal{F}^M.$$χGM​(G)=χHM​(H)⟺hom(F,G)=hom(F,H)∀F∈FM.

极大性意味着，如果图 $F$F 不在 $\mathcal{F}^M$FM 中，则存在图 $G$G 与 $H$H，它们在模型 $M$M 下表示相同，但来自 $F$F 的同态计数不同。这使得 $\mathcal{F}^M$FM 成为完整的量化可表达性度量。比较两个模型 $M_1$M1​ 与 $M_2$M2​ 归结为比较家族：如果 $\mathcal{F}^{M_2}\subsetneq \mathcal{F}^{M_1}$FM2​⊊FM1​，则 $M_1$M1​ 严格更具表达能力，且差距由家族差 $\mathcal{F}^{M_1}\setminus \mathcal{F}^{M_2}$FM1​∖FM2​ 给出。

推导这些家族的核心模块是嵌套耳分解框架。对于一个图，分解将边集划分为称为耳的简单路径。初始耳对应连通分量的不相交起始路径。后续耳必须嵌套在较早的耳上，意味着新耳的一个或两个端点连接到较早的耳，而内部顶点是新的。当两个端点都连接到同一个父耳时，父耳中的相应子路径定义一个嵌套区间。全局结构可视为一个耳森林，其中每个耳通过其嵌套关系具有一个父耳。该结构的变体对应不同模型类别：

• 端点共享嵌套耳分解要求所有具有非空嵌套区间的耳共享一个端点。
• 强嵌套耳分解要求同一父耳的子区间按包含关系嵌套。
• 近似强嵌套耳分解通过仅考虑长度大于一的子区间来弱化该条件。

耳的组织方式、父子关系和嵌套区间在下图中展示。

利用这些分解变体，该框架给出主要 GNN 架构的精确刻画。MPNN 可以计数森林，Subgraph GNN 对应具有端点共享嵌套耳分解的图，Local 2-GNN 对应强嵌套耳分解，Local 2-FGNN 对应近似强嵌套耳分解，而 2-FGNN 对应一般嵌套耳分解。Subgraph GNN 的等价描述是：如果删除一个合适的顶点后剩余图为森林，则该图属于其表达家族。

该刻画背后的证明流程本身是一种模块化方法。首先，展开树视角识别同态计数决定模型表示的图结构，得到基于树分解的下界家族。其次，将分解刻画翻译为嵌套耳分解语言，提供与实用 GNN 操作一致的紧凑描述。第三，通过构造对模型不可区分但在被排除结构的同态计数上不同的图对来证明极大性，并利用树分解、pebble games 以及特殊构造的不可区分图家族之间的联系。

该框架还扩展到节点级和边级表达能力。对于节点级分析，相关家族由连通有根图 $F^w$Fw 构成，其中 $F$F 中一个顶点被标记，并与输入图中的某个顶点进行比较。表示等价条件变为

$$\chi_G^M(u)=\chi_H^M(v) \quad\Longleftrightarrow\quad \mathsf{hom}(F^w,G^u)=\mathsf{hom}(F^w,H^v) \quad \forall F^w\in\mathcal{F}_{\mathfrak{n}}^M.$$χGM​(u)=χHM​(v)⟺hom(Fw,Gu)=hom(Fw,Hv)∀Fw∈FnM​.

对于 MPNN，节点级家族是树。对于 Subgraph GNN，当移除根后剩余图为森林时，有根图可表达。对于类 2-FGNN 模型，根必须是合适嵌套耳分解中第一耳的一个端点，而边级变体标记两个顶点，并对应第一耳的端点。

该方法自然推广到更高阶 GNN 家族。Subgraph $k$k-GNN 通过允许移除最多 $k$k 个顶点使剩余图为森林来刻画。Local $k$k-GNN 需要嵌套耳分解的高阶对应物。$k$k 阶耳由一个至多包含 $k$k 个顶点的小核心图以及 $k$k 条将该核心连接到外部端点的路径组成。随后在这些高阶耳上定义嵌套区间和强嵌套条件。这些高阶构建块及其嵌套区间结构的形状如下所示。

借助这些工具，该框架还得到完整的定性层级。基础家族满足严格包含：

$$\mathcal{F}^{\mathsf{MP}} \subsetneq \mathcal{F}^{\mathsf{Sub}} \subsetneq \mathcal{F}^{\mathsf{L}} \subsetneq \mathcal{F}^{\mathsf{LF}} \subsetneq \mathcal{F}^{\mathsf{F}}.$$FMP⊊FSub⊊FL⊊FLF⊊FF.

高阶变体将图景扩展为无限层级。Subgraph $k$k-GNN 的表达力随 $k$k 增强，Local $k$k-GNN 的表达力随 $k$k 增强，而 Local $(k+1)$(k+1)-GNN 位于 $k$k-FWL 与 $(k+1)$(k+1)-FWL 之间。当 $k>1$k>1 时，Subgraph $k$k-GNN 的表达能力通常与 $k$k-FWL 不可比较，但包含于 $(k+1)$(k+1)-FWL 中。所得架构层级概括如下。

该框架的一项重要应用是子图计数。子图计数不是直接的同态计数，但可以表示为目标模式在同态像上的同态计数的线性组合。给定模式 $F$F，令 $\mathsf{Spasm}(F)$Spasm(F) 表示其同态像，令 $\mathsf{Spasm}^{\neq}(F)$Spasm=(F) 为一组两两非同构的同态像的极大集合。则对任意图 $G$G，

$$\operatorname{sub}(F,G) = \sum_{\tilde{F}\in\mathsf{Spasm}^{\neq}(F)} \alpha(F,\tilde{F})\, \mathsf{hom}(\tilde{F},G),$$sub(F,G)=F~∈Spasm=(F)∑​α(F,F~)hom(F~,G),

其中 $\alpha(F,\tilde{F})$α(F,F~) 是仅依赖于 $F$F 和 $\tilde{F}$F~ 而不依赖于 $G$G 的非零常数。因此，只要每个同态像 $\tilde{F}\in\mathsf{Spasm}(F)$F~∈Spasm(F) 都属于模型的同态可表达性家族，模型就可以对 $F$F 进行子图计数。反之，如果某个同态像不在该家族中，则可以构造一对模型表示相同但子图计数不同的图。这给出图级、节点级和边级的完整计数准则。循环模式的同态像分解如下所示。

同一刻画也与多项式表达能力相关。属于 $\mathcal{F}^M$FM 或 $\mathcal{F}_{\mathfrak{n}}^M$FnM​ 与 $\mathcal{F}_{\mathfrak{e}}^M$FeM​ 决定了模型能否计算与模式或有根模式相关联的不变或等变图多项式。这使嵌套耳分解框架成为推理不同架构可用哪些结构多项式的实用工具，包括标准消息传递、基于子图、局部高阶和全局高阶变体。

实验

实验在匹配的 GIN 基础设计下评估 MPNN、Subgraph GNN、Local 2-GNN 和 Local 2-FGNN，以在合成子结构计数、循环计数和真实世界图基准上检验所提出的同态可表达性理论。结果显示，模型能力大体遵循理论层级，Local 2-FGNN 始终编码更多结构、更有效地计数多种循环，并在实际数据集上取得最强性能。总体而言，这些发现支持如下结论：更强的同态可表达性会转化为受控和实际图学习任务中的可测量优势。

该示例刻画不同 GNN 架构在图级、节点级和边级能够计数的循环与路径。更强的模型扩展了可计数结构的类别，其中 MPNN 表现出最强局限，而 Local 2-(F)GNN 模型显示更强的循环计数能力。MPNN 只能计数很短的简单路径，且无法在所示层级计数任何循环；Subgraph GNN 和 Local 2-(F)GNN 模型扩展了循环与路径计数能力，其中 Local 2-(F)GNN 模型与最强实际循环计数性能一致。

结果表明，具有更强局部子图处理能力的模型在计数同态信息时通常达到更低的归一化测试误差。Local 2-FGNN 在图级、节点级和边级任务上始终准确，而 MPNN 无法捕获任何测试子结构。Subgraph GNN 在部分情形表现良好，但不如 Local 2-GNN 和 Local 2-FGNN 稳定，尤其在较难的子结构上。Local 2-FGNN 在所有测试的同态计数任务上保持低误差。MPNN 的性能明显劣于基于子图的模型。Local 2-GNN 相较 Subgraph GNN 有所提升，并提供更一致的低误差。性能趋势与所比较 GNN 模型之间的预期表达能力排序一致。

真实世界基准结果表明，理论上更具表达能力的模型在化学图任务上通常表现更好。在所评估的 GNN 变体中，随着架构从 MPNN 演进到 Subgraph GNN 再到 Local 2-GNN，性能逐步提升。Local 2-FGNN 在所有报告任务上取得最佳结果，表明其表达能力优势可以转化为实际收益。表达能力的提升与 ZINC 和 Alchemy 任务上更低的基准误差相关。Local 2-FGNN 始终优于 MPNN、Subgraph GNN 和 Local 2-GNN。

循环计数结果表明，在模型规模和训练预算匹配的情况下，所比较的 GNN 架构之间存在清晰的表达能力层级。MPNN 误差最大，且无法可靠计数边级循环；Subgraph GNN 有显著改进，但仍难以处理若干较长的弦循环。Local 2-GNN 和 Local 2-FGNN 达到一致更低的误差，其中 Local 2-FGNN 在图级、节点级和边级整体性能最强。MPNN 在各层级均无法有效计数循环，尤其在边级。Local 2-FGNN 在相近计算成本下取得最佳或接近最佳的循环计数误差。

实验在匹配的模型规模和训练预算下，比较 GNN 架构在合成循环与路径计数、同态计数以及化学基准任务上的表现。这些结果验证了更强的局部子图处理会扩展可计数结构的类别并提升实际性能。MPNN 最受限，Subgraph GNN 带来部分增益，而 Local 2-GNN 和 Local 2-FGNN 始终能以更低误差计数更复杂的循环与路径。这些结果显示，理论表达能力会转化为图级、节点级和边级更准确且更稳定的性能。