图神经网络的结构保持与逻辑表达力

# 结构保持与图神经网络的逻辑表达能力  
来源：https://arxiv.org/html/2606.17882  

\declaretheorem\[name=Theorem\]thm  

Przemysław Andrzej Wałęga  
Queen Mary University of London  
p\.walega@qmul\.ac\.uk  

&Bernardo Cuenca Grau  
University of Oxford  
bernardo\.grau@cs\.ox\.ac\.uk  

###### 摘要  

图神经网络与逻辑形式主义之间的桥梁已通过固定架构选择（如聚合、组合和激活函数的类型）建立。这些选择定义了受限的 GNN 类别，通过证明逻辑公式可以翻译为等价的 GNN，反之亦然，从而获得了与逻辑形式主义之间的紧密对应关系。本文采取语义视角，通过确定在结构保持性质（嵌入（扩展）、单射同态和同态）下保持的 GNN 分类器类别的逻辑表达能力。我们证明，对于每个这样的性质，都存在一个分级模态逻辑片段来刻画该 GNN 类别。具体而言，嵌入保持对应存在分级模态逻辑，单射同态保持对应其存在正片段，同态保持对应存在正模态逻辑。这些结果刻画了广泛 GNN 类别的表达能力，且与特定架构选择无关，但我们也展示了这些类别中的每一个都承认一个具有相同表达能力的 GNN 架构。从技术上讲，我们的方法利用了有界高度树的一个新的良拟序结果，从而得到展开不变类别的有限表示。  

## 1 引言  

图神经网络（GNNs）Gilmer et al. (2017\) 是设计为直接在可变大小的图上操作的模型，同时确保模型预测在图同构下保持不变。在聚合-组合范式中，每个节点维护一个向量表示，该表示通过聚合来自其邻居的信息进行迭代更新。这种设计引入了强烈的结构偏差：具有 L 层的 GNN 在同构下保持不变，并且本质上是局部的，因为节点表示仅取决于该节点的 L 跳邻域。这两个性质使得 GNN 与逻辑形式主义（特别是模态逻辑）非常接近，后者也是局部的且在同构下不变 Barceló et al. (2020\); Hauke and Wałęga (2026\); Cuenca Grau et al. (2026\)。建立这种联系是有益的，因为逻辑为分析表达能力和启用符号化的验证与解释方法提供了原则性工具。  

这些联系已被广泛研究。特别是在 GNN 与逻辑之间，通过固定架构选择（如聚合、组合和激活函数）建立了桥梁。这些选择定义了受限的 GNN 分类器家族，并获得了与逻辑形式主义之间的精确对应关系。先前的工作已经识别出这样的家族，它们对应于带计数项的一阶逻辑扩展 Grohe (2024\); Nunn et al. (2024\) 和 Presburger 量化 Benedikt et al. (2024\)，以及基于规则的知识表示形式主义如 Datalog Tena Cucala et al. (2025, 2023\)。  

在本文中，我们通过基于结构保持性质的语义框架来补充这些以架构驱动的刻画，这些性质对分类器施加了比图同构不变性严格更强的约束，即嵌入保持、单射同态保持和同态保持。我们证明，对于每个这样的性质，相应的 GNN 分类器类别具有与分级模态逻辑片段相同的表达能力（第 4.5 节）：  

- 在嵌入下保持的 GNN 分类器类别与存在分级模态逻辑 \(\exists\mathcal{GML}\) 具有相同的表达能力；  
- 在单射同态下保持的 GNN 分类器类别与存在正分级模态逻辑 \(\exists^{+}\mathcal{GML}\) 具有相同的表达能力；  
- 在同态下保持的 GNN 分类器类别与存在正模态逻辑 \(\exists^{+}\mathcal{ML}\) 具有相同的表达能力。  

我们的方法受到有限模型理论的启发，其中保持定理将结构性质与逻辑可定义性联系起来 Libkin (2004\); Rosen (2002\); Grädel et al. (2007\); Rosen (1997\); Abramsky and Reggio (2024\)。经典结果包括 van Benthem–Rosen 定理 Rosen (1997\)——将模态逻辑刻画为一阶逻辑的互模拟不变片段，以及 Rossman 定理 Rossman (2008\)——将存在正一阶逻辑刻画为同态下保持的片段。我们将这种方法论适应到 GNN 设置中。由于现有的保持定理并不直接适用于该设置，我们开发了针对 GNN 计算所诱导的图结构的新结果。  

我们方法背后的关键直觉是，除了图同构不变性之外，GNN 本质上是局部的：在具有 L 层的 GNN 中，节点的表示仅取决于其 L 跳邻域 Barceló et al. (2020\); Wang and Zhang (2022\); Morris et al. (2019b\)。这种局部性允许我们将 GNN 的分析简化为通过展开获得的树 Barceló et al. (2020\)。结合结构关系下的保持，这产生了上述逻辑刻画。  

主要的技术挑战是获得此类类别的有限表示。为了解决这个问题，我们展示了良拟序的一个新结果（第 4.4 节），该结果具有独立的研究价值：  

- 每个有界高度树类在嵌入关系下是**良拟序**的。  

由于 L 展开具有有界高度，并且良拟序只允许有限多个极小元，这通过极小树为每个类别提供了有限表示。在高层次上，每个极小树都可以用一个逻辑公式刻画，整个类别通过这样的公式的有限析取来定义。模态逻辑的片段由保持关系决定。  

除了语义刻画之外，我们还表明由保持性质定义的每个 GNN 分类器类别都可以被特定的架构捕获。特别地（第 5 节）：  

- 在单射同态下保持的 GNN 与单调 GNN 具有相同的表达能力；  
- 在同态下保持的 GNN 与使用 \(\mathrm{MAX}\) 作为聚合的单调 GNN 具有相同的表达能力；  
- 在嵌入下保持的 GNN 与具有额外层的单调 GNN 具有相同的表达能力，该层独立于邻居转换节点特征。  

此外，我们的结果揭示了先前工作中考虑的 GNN 架构的一个有趣性质，我们称之为正权重 GNN，其参数矩阵具有非负条目。特别地，可以推出，任何在单射同态下保持的 GNN（因此也包括任何单调 GNN）都可以转换为等价的正权重 GNN。因此，就表达能力而言，非负权重的语法限制在该类别内并不具有限制性。  

总而言之，我们的贡献如下。我们开发了一个基于结构保持性质来分析 GNN 表达能力的框架。我们建立了将这些性质与分级模态逻辑片段中的可定义性联系起来的保持定理，并由新的良拟序结果支持以确保有限表示。最后，我们提供了由保持性质定义的 GNN 类别的架构刻画。  

## 2 相关工作  

GNN 的表达能力已从多个角度得到研究。它们的*判别能力*衡量区分图的能力，众所周知消息传递 GNN 受限于 Weisfeiler–Lehman 图同构测试。因此，它们无法区分 WL 无法分离的图 Morris et al. (2019a\); Xu et al. (2019\)。关于 GNN 逻辑表达能力的研究将 GNN 视为计算图上的一元查询的节点分类器，并建立了 GNN 架构与逻辑形式主义之间的对应关系。特别地，GNN 的表达能力无法仅由一阶逻辑捕获，需要扩展以包含计数项、Presburger 量词或相关机制 Grohe (2024\); Benedikt et al. (2024\); Nunn et al. (2024\)。此外，与分级模态逻辑及相关片段的联系已被建立 Barceló et al. (2020\)。最近关于有界 GNN 的工作通过将带有界多重性的聚合方案与一阶逻辑的二变量片段相关联，细化了这些对应关系 Cuenca Grau et al. (2026\)。  

另一条互补的工作线研究 GNN 与基于规则的知识表示形式主义之间的联系，这些形式主义受到逻辑推理和可解释性的驱动。特别是，单调 GNN 已被引入以捕获 Datalog 中的基于规则推理 Tena Cucala et al. (2025, 2023\); Tena Cucala and Cuenca Grau (2024\); Morris and Horrocks (2025\); Morris et al. (2024\)。这些模型强制了结构保持性质，如同态保持或单射同态保持。这些性质通过架构约束来强制，包括非负权重、单调激活函数和受限制的聚合。虽然在实践中有效，但这些方法本质上是语法驱动的，因为期望的保持性质是通过设计选择间接强制而非以语义术语明确刻画的。  

我们的工作也与有限模型理论中的保持定理相关，这些定理以结构保持性质和不变性条件来刻画逻辑片段。经典结果如 Łoś–Tarski、Lyndon 和同态保持定理分别建立了一阶逻辑片段与嵌入保持、满射同态保持和同态保持之间的对应关系 Łoś and Suszko (1955\); Lyndon (1959\); Hodges (1997\)。尽管许多此类结果在有限结构（因此也在图）上失效，但 Rossman 定理表明同态保持在有限设置中仍然成立 Rossman (2008\)。在模态逻辑中，保持结果与局部性和互模拟不变性相关。Van Benthem 定理及其有限变体（归功于 Rosen）将互模拟不变的一阶性质刻画为模态逻辑中可定义的性质 Andréka et al. (1998\); Rosen (1997\)。最近的工作已将保持结果扩展到分级模态逻辑及相关设置 Abramsky and Reggio (2024\)。我们在良拟序方面的结果与最近在类似方向的工作有关 Lopez (2023\)，然而这些技术依赖于额外的结构假设，例如在子结构下的封闭性，而这些在我们的设置中并不成立。  

## 3 背景  

#### 图与图关系  

我们考虑有限、无向、简单、带节点标签的图 \(G=(V,E,\lambda)\)，其中 \(V\) 是有限的节点集，\(E\) 是无自环的无向边集，\(\lambda:V\to\{0,1\}^d\) 为每个节点分配一个固定维度 \(d\) 的二进制向量。直观地，\(d\) 表示可能的标签（命题特征）的数量，标签 \(i\in[d]\) 下 \(\lambda_i(v)=1\) 表示节点 \(v\) 具有标签 \(i\)；集合 \(\{1,\dots,n\}\) 表示为 \([n]\)。我们用粗体书写向量，例如 \(\mathbf{x},\mathbf{y},\mathbf{z}\)，并用 \(x_i\) 表示 \(\mathbf{x}\) 的第 \(i\) 个分量。对于向量 \(\mathbf{x},\mathbf{y}\in\mathbb{R}^d\)，如果对所有 \(i\in[d]\) 有 \(x_i\leq y_i\)，则记 \(\mathbf{x}\leq\mathbf{y}\)。这种离散的标签设置使得与逻辑形式主义能够直接连接 Barceló et al. (2020\); Benedikt et al. (2024\)。  

一个*带标点图*是一个对 \((G,v)\)，包含一个图和一个被区分的节点。一棵*树*是一个连通无环图。一棵*有根树*是一个带标点图 \((G,v)\)，其中 \(G\) 是一棵树且 \(v\) 是它的根。在一个有根树中，节点 \(u\) 的*深度*是从根到 \(u\) 的唯一路径的长度，树 \(G\) 的*高度*是任何节点的最大深度。  

设 \((G,w)\) 和 \((H,v)\) 为带标点图，其中 \(G=(V,E,\lambda)\)，\(H=(V',E',\lambda')\)。我们将考虑以下从 \(V\) 到 \(V'\) 的映射 \(f\) 的定义，且 \(f(w)=v\)。  

- **同构**：\(f\) 是双射，\(\lambda(u)=\lambda'(f(u))\)，并且 \(\{u,z\}\in E\) 当且仅当 \(\{f(u),f(z)\}\in E'\)。  
- **嵌入**：\(f\) 是从 \((G,w)\) 到由 \(f(V)\) 诱导的 \(H\) 的子图的同构。  
- **同态**：\(f\) 满足对所有 \(u\in V\) 有 \(\lambda(u)\leq\lambda'(f(u))\)，并且 \(\{u,z\}\in E\) 蕴含 \(\{f(u),f(z)\}\in E'\)。如果 \(f\) 也是单射的，则称为*单射同态*。  

直观上，这些映射捕获了一个图嵌入另一个图的不同方式：同构保留了整个结构，嵌入精确地保留了一个子图，而同态允许标签扩展和节点合并（除非映射是单射的）。这些关系的示例见图 1。