深度同态网络在关系数据库上的表达能力

# 深度同态网络在关系数据库上的表达能力

**来源：** https://arxiv.org/html/2605.22852  
**作者：** Balder ten Cate（阿姆斯特丹大学，[email protected]）& Maurice Funk（莱比锡大学，[email protected]）& Benny Kimelfeld（以色列理工学院 & RelationalAI，[email protected]）& Carsten Lutz（莱比锡大学，[email protected]）& Moritz Schönherr（莱比锡大学，[email protected]）& Arie Soeteman（阿姆斯特丹大学，[email protected]）

###### 摘要

消息传递图神经网络（GNN）的表达能力局限性催生了众多更强大的图学习架构。我们主张将深度同态网络（DHN）作为一种特别适合关系数据库学习的模型，原因在于它与 SQL 的重要片段（如合取查询）密切相关。通过将 DHN 与一阶逻辑（FO）的各种自然片段及其扩展联系起来，我们研究了 DHN 的精确表达能力。对于使用 `max`、`sum` 和 `mean` 聚合的 DHN，我们建立了它们与一元否定片段（UNFO）、UNFO 加上计数量词以及 UNFO 加上比率量词之间的关联。我们进一步将 `sum` 聚合的 DHN 与 FO 的一元量词交替片段以及扩展了表达能力计数功能的 FO 片段联系起来。通过 FO 与 SQL 之间的经典对应关系，这些结果也阐明了 DHN 与 SQL 之间的关系。它们还使我们能够研究 DHN 的基本静态分析问题（空性问题与包含性问题）的可判定性。我们通过实验证实，表达能力的差异会反映在合适的预测任务性能上。

## 1 引言

消息传递图神经网络（GNN）是一类重要的图学习模型，已在包括社交网络分析 [Guo and Wang (2021)](https://arxiv.org/html/2605.22852#bib.bib38)、分子性质预测 [Sun et al. (2022)](https://arxiv.org/html/2605.22852#bib.bib37)、推荐系统 [Sharma et al. (2024)](https://arxiv.org/html/2605.22852#bib.bib36) 以及关系数据库数据分析 [Fey et al. (2024)](https://arxiv.org/html/2605.22852#bib.bib25) 在内的广泛领域展现出高效性。然而，众所周知，标准 GNN 模型的表达能力受限于一维 Weisfeiler–Leman 测试。这是一个严重的局限性：本质上，GNN 只能检测树形图属性，而像三角形、团和固定长度环这样的简单常见结构则超出了其表达能力。因此，越来越多的研究工作致力于设计更具表达能力的图神经架构，包括高阶 GNN [Morris et al. (2019)](https://arxiv.org/html/2605.22852#bib.bib11)、子图 GNN [Qian et al. (2022)](https://arxiv.org/html/2605.22852#bib.bib31)；[You et al. (2021)](https://arxiv.org/html/2605.22852#bib.bib30)；[Zeng et al. (2023)](https://arxiv.org/html/2605.22852#bib.bib32) 以及分层自我中心 GNN [Soeteman and Cate (2025)](https://arxiv.org/html/2605.22852#bib.bib9)。这些架构在诸多任务上展现出改进的性能，例如预测分子受限溶解度（如 ZINC 基准 [Irwin et al. (2012)](https://arxiv.org/html/2605.22852#bib.bib33) 中），其中三角形和环等子结构特征高度相关。

一种重要且实用的提高 GNN 表达能力（摆脱其树形限制）的方法，是提供计数来自选定图模式的同态的能力。这通常通过特征增强来实现：每个顶点都附加上同态计数，以捕获局部图结构，例如该顶点所在的三角形数量 [Bao et al. (2025)](https://arxiv.org/html/2605.22852#bib.bib42)；[Barceló et al. (2021)](https://arxiv.org/html/2605.22852#bib.bib2)；[Jin et al. (2024)](https://arxiv.org/html/2605.22852#bib.bib43)；[Nguyen and Maehara (2020)](https://arxiv.org/html/2605.22852#bib.bib41)；[Wolf et al. (2023)](https://arxiv.org/html/2605.22852#bib.bib40)。然而，同态计数也可以更深入地集成到 GNN 架构中，将 GNN 标准的基于边的消息传递机制替换为沿复杂模式的更一般的消息传递形式。后一种更强大的方法正是最近引入的深度同态网络（DHN）[Maehara and NT (2024)](https://arxiv.org/html/2605.22852#bib.bib10) 所采用的。如本文所示，即使标准 GNN 经过同态计数特征增强，DHN 仍提供了严格更高的表达能力。此外，我们认为 DHN 还有另一个重要优势：它们提供了与关系数据库的自然联系。事实上，海量数据存储在关系系统中，分析这些数据是 GNN 的一个重要应用，通常通过先将数据库转换为图 [Fey et al. (2024)](https://arxiv.org/html/2605.22852#bib.bib25)；[Chen et al. (2025a)](https://arxiv.org/html/2605.22852#bib.bib28)；[Tönshoff et al. (2023)](https://arxiv.org/html/2605.22852#bib.bib27)；[Wang et al. (2024)](https://arxiv.org/html/2605.22852#bib.bib29)] 来实现。对于 DHN，这样的转换是不必要的，因为它们的定义可以优雅地从图扩展到数据库。更重要的是，模式同态本质上就是合取查询（CQ）的另一种表示形式，而 CQ 可以说是关系数据库系统最重要的查询语言。我们记得，CQ 对应于 SQL 中的 select-project-join 片段，实际上很大一部分 SQL 查询都属于这个片段 [Chaudhuri (1998)](https://arxiv.org/html/2605.22852#bib.bib39)。因此，DHN 为数据库属性提供了一种自然形式的表达能力，同时也开启了利用数十年关于 CQ 高效评估研究成果的可能性。

**我们的贡献。** 本文旨在对作为顶点分类器的 DHN 的精确表达能力进行仔细分析，特别关注它们与一阶逻辑（FO）自然片段及其扩展之间的关系。由于 SQL 的一个重要核心恰对应于 FO，这也有助于阐明哪些 SQL 查询可由 DHN 表达，哪些则不能。此外，这使我们能够获得关于 DHN 静态分析的结果。我们研究了**空性问题**，即询问给定的 DHN 是否定义了空顶点集，从而指示模型中的潜在缺陷，以及相关的**包含性问题**，即询问一个给定 DHN 实现的顶点分类器是否被另一个 DHN 实现的分类器所包含。我们的逻辑刻画还使我们能够证明，DHN 严格优于 Barceló 等人提出的初始同态计数特征增强的 GNN [Barceló et al. (2021)](https://arxiv.org/html/2605.22852#bib.bib2)。

我们研究了使用 `max`、`sum` 和 `mean` 聚合的 DHN。对于 `max`-DHN，我们得到了一个完整且统一的逻辑刻画：`max`-DHN 可表达的数据库属性恰好是那些可由 FO 的一元否定片段（UNFO）[Segoufin and ten Cate (2013)](https://arxiv.org/html/2605.22852#bib.bib1) 定义的属性。根据已知结果，这意味着 `max`-DHN 的空性和包含性问题是可判定的。对于 `sum`-DHN，我们的结果提供了一个广泛但不完整的图景。我们证明，对于连通模式，在有界度数据库上的表达能力恰好是 UNFOC（UNFO 加上计数量词的扩展）的表达能力。这也给出了在 GNN 文献中常研究的非均匀设置下的刻画，其中不同图大小可以使用不同的 GNN [Grohe (2021)](https://arxiv.org/html/2605.22852#bib.bib21)]。连通性限制对于绕过关于具有全局读出功能的 GNN 表达能力的一个开放问题至关重要 [Barceló et al. (2020)](https://arxiv.org/html/2605.22852#bib.bib20)；[Hauke and Walega (2026)](https://arxiv.org/html/2605.22852#bib.bib16)]。然后我们证明，`sum`-DHN 的空性和包含性问题在无限制度图和有界度图上都是不可判定的。在有界度图上，当所有模式都是连通时，这些问题变为可判定。相反，在温和假设下，`sum`-GNN 的相同问题是可判定的 [Benedikt et al. (2024)](https://arxiv.org/html/2605.22852#bib.bib24)]。然而，关于 `sum`-DHN 还有更多可说的。虽然我们没有获得它们在无限制度数据库上表达能力的精确逻辑刻画，但我们能够将它们夹在两个逻辑形式化之间，这两个形式化提供了有意义的下界和上界。对于下界，我们定义了 FO 的一个新片段 UQAFO，它基于一元量词交替并允许不等式，从而允许计数。我们证明 UQAFO 严格比 UNFOC 更具表达能力，同时又不比 `sum`-DHN 更具表达能力。这一视角也激发了 DHN 的一个自然变体——深度嵌入网络（DEN），其中同态被嵌入所取代。使用 Lovász 同态计数定理，我们证明 `sum`-DEN 与 `sum`-DHN 具有相同的表达能力，并且我们还表明它们严格比 UQAFO 更具表达能力。简短地转入 `max` 聚合，我们进一步观察到 `max`-DEN 严格比 `max`-DHN 更具表达能力。对于上界，我们提出了一种基于同态的逻辑，灵感来自描述复杂性中研究的一阶逻辑与计数 [Immerman (2012)](https://arxiv.org/html/2605.22852#bib.bib34)]。基于最近的进展 [Grohe (2024)](https://arxiv.org/html/2605.22852#bib.bib19)]，我们证明该逻辑至少与 `sum`-DHN 一样具有表达能力。我们仅简要讨论 `mean` 聚合的情况。我们的主要结果是，在有界度数据库上且针对连通模式，`mean`-DHN 具有与 UNFOC 的一个变体相同的表达能力，其中计数量词被比率量词替换，这与最近关于使用 `mean` 聚合的 GNN 表达能力的研究精神一致 [Schönherr and Lutz (2026)](https://arxiv.org/html/2605.22852#bib.bib15)]。我们指出，上述所有结果在关系数据库和图上都成立，只是对于不可判定性结果需要温和的额外假设，即存在顶点颜色。我们还提供了实验，这些实验在实践上证实了我们在表达能力方面的理论发现。特别地，它们证实了我们的两个主要分离结果。详细的证明在附录中提供。

## 2 预备知识

#### 数据库、同态、嵌入。

对于向量 \(\bar{x} \in \mathbb{R}^k\)，我们用 \(x_1, \ldots, x_k\) 来指代其分量。固定一个可数无穷的值集 \(\mathbf{V}\)。**模式** \(\mathbf{S}\) 是一个有限的关系符号 \(R\) 的集合，每个关系符号关联一个元数 \(\mathsf{ar}(R) \ge 0\)。一个 \(\mathbf{S}\)**-事实**是一个形如 \(R(\bar{v})\) 的表达式，其中 \(R \in \mathbf{S}\) 且 \(\bar{v}\) 是一个来自 \(\mathbf{V}\) 的 \(\mathsf{ar}(R)\) 元组。一个 \(\mathbf{S}\)**-数据库**是一个有限的 \(\mathbf{S}\)-事实集合。我们用 \(\mathsf{adom}(D)\) 表示数据库 \(D\) 的**活动域**，即 \(D\) 中使用的值的集合。\(D\) 的**度**是 \(D\) 中任何值出现的事实的最大数目。

我们的 DHN 运行在数据库上，而在原始论文中 [Maehara and NT (2024)](https://arxiv.org/html/2605.22852#bib.bib10)，DHN 应用于无向图。通过选择**图模式** \(\mathbf{S} = \{E\}\) 且 \(\mathsf{ar}(E)=2\)，我们可以捕获有向图的设置。无向图需要附加约束所有输入是反自反且对称的。

一个**带标志点的 \(\mathbf{S}\)-数据库** 是一个对 \((D, v)\)，其中 \(D\) 是一个 \(\mathbf{S}\)-数据库且 \(v \in \mathsf{adom}(D)\)。如果 \(v\) 的具体身份不重要，我们通常将 \((D, v)\) 写为 \(D^v\) 或 \(D^\bullet\)。对于 \(d \ge 1\)，一个 \(\mathbb{R}^d\)**-嵌入的 \(\mathbf{S}\)-数据库** 是一个对 \((D, \lambda)\)，其中 \(D\) 是一个 \(\mathbf{S}\)-数据库且 \(\lambda: \mathsf{adom}(D) \to \mathbb{R}^d\) 是一个嵌入函数。嵌入数据库也存在带标志点的版本，定义是预期的。

从带标志点的数据库 \(F^v\) 到带标志点的数据库 \(D^u\) 的一个**同态**是一个函数 \(h: \mathsf{adom}(F) \to \mathsf{adom}(D)\)，使得 \(h(v)=u\)，并且若 \(R(\bar{v}) \in F\) 则 \(R(h(\bar{v})) \in D\)，其中 \(h(\bar{v})\) 表示 \(h\) 的分量级应用。我们用 \(\mathsf{Hom}(F^\bullet, D^\bullet)\) 表示从 \(F^\bullet\) 到 \(D^\bullet\) 的所有同态的集合。从 \(F^\bullet\) 到 \(D^\bullet\) 的一个同态是一个**嵌入**，如果它是单射的，并且另外，若 \(R(h(\bar{v})) \in D\) 则 \(R(\bar{v}) \in F\)。嵌入也被称为部分同构或诱导子结构同构。以下引理是广为人知的，图版本可见例如 [Lovász, 2012, Chapter 5.2.3](https://arxiv.org/html/2605.22852#bib.bib12)。针对数据库的证明在附录中。

###### 定理 1. [Lovász 同态计数定理] 设 \(\mathbf{S}\) 是一个模式。对于带标志点的 \(\mathbf{S}\)-数据库 \(F^\bullet, D^\bullet\)，从 \(F^\bullet\) 到 \(D^\bullet\) 的嵌入数量 \(k\) 由从所有值数量不超过 \(|\mathsf{adom}(F)|\) 的 \(\mathbf{S}\)-数据库到 \(D^\bullet\) 的同态数量唯一确定。此外，\(k\) 可以写成这些同态计数的线性组合。当同态和嵌入的角色互换时，同样成立。

#### 深度同态网络。

集合 \(X\) 上的一个**有限多重集**是一个函数 \(M: X \to \mathbb{N}\)，使得对于仅有限多的 \(x \in X\) 有 \(M(x)>0\)。一个**聚合函数**是从 \(\mathbb{R}\) 上的有限多重集到 \(\mathbb{R}\) 的函数，例如 sum、算术 mean 和 max。根据约定，我们设 \(\mathsf{mean}(\emptyset) = \mathsf{max}(\emptyset) = 0\)。我们经常将聚合函数应用于来自 \(\mathbb{R}^d\) 的向量。这些应用总是分量级的。

###### 定义 2（同态查询）。设 \(\mathbf{S}\) 是一个模式。一个在 \(\mathbf{S}\) 上具有输入维度 \(d \ge 0\) 和输出维度 \(d' > 0\) 的**同态查询**是一个三元组 \((F^\bullet, \mu, \mathsf{agg})\)，其中 \(F^\bullet\) 是一个带标志点的 \(\mathbf{S}\)-数据库，\(\mu\) 为 \(F\) 中的每个值标记一个从 \(\mathbb{R}^d\) 到 \(\mathbb{R}^{d'}\) 的函数 \(\mu_v\)（称为**转换函数**），而 \(\mathsf{agg}\) 是一个聚合函数。

在 \(\mathbb{R}^d\)-嵌入的带标志点 \(\mathbf{S}\)-数据库 \((D^\bullet, \lambda)\) 上评估 \((F^\bullet, \mu, \mathsf{agg})\) 的**结果**是 \(\mathbb{R}^{d'}\)-向量：

\[
\mathsf{eval}((F^\bullet, \mu, \mathsf{agg}), (D^\bullet, \lambda)) := \mathsf{agg}\{\{ \prod_{v \in \mathsf{adom}(F)} \mu_v(\lambda(h(v))) \mid h \in \mathsf{Hom}(F^\bullet, D^\bullet) \}\}
\]