技术摘要：关系结构的颜色细化

问题陈述

颜色细化（Color Refinement, CR），也称为朴素顶点分类或 1 维 Weisfeiler-Leman 算法，是一种通过迭代计算顶点着色来区分图的经典方法。众所周知，CR 当且仅当两个图可以被包含最多两个变量的带有计数量词的一阶逻辑句子（$C_2$）区分时，或者等价于它们在某些树的同态数量上存在差异时，才能区分这两个图。

虽然 CR 被广泛应用于同构测试、线性规划归约以及机器学习（作为图神经网络的等价物），但现有将其推广到任意关系结构（如超图）的方法存在局限性。例如，一些朴素方法，如在 Gaifman 图或关系结构的关联图中运行 CR，往往无法区分结构上不同的结构。例如，本文指出，对于某些结构，其 Gaifman 图是相同的，而其关联图在得到稳定着色后，无法区分底层的结构。

本文解决的核心问题是如何将颜色细化推广到任意有限关系结构，使得所得方法能够获得与已知图算法类似的组合与逻辑特征，特别是在关于无环结构和受保护逻辑片段方面的特征。

方法论

作者提出了关系颜色细化（Relational Color Refinement, RCR），这是一种对关系结构中的元组而非仅仅是其元素进行着色的方法。

RCR 算法

给定一个具有元组集 $\mathbf{A}$ 的 $\sigma$-结构 $\mathbf{A}$：

1. 初始着色： 对于每个元组 $\mathbf{a} \in \mathbf{A}$，其初始颜色 $\varrho_0(\mathbf{a})$ 由其原子类型（包含 $\mathbf{a}$ 的关系符号集合）及其相似类型（元组中索引对 $(i, j)$ 的集合，满足第 $i$ 个和第 $j$ 个条目相同）共同定义。
2. 迭代细化： 在每一轮迭代 $i$ 中，颜色 $\varrho_i(\mathbf{a})$ 的更新将包含前一轮颜色 $\varrho_{i-1}(\mathbf{a})$ 以及一个多重集（multiset）。该多重集由一对对组成，每对包含 $\mathbf{a}$ 与相邻元组 $\mathbf{b}$ 之间的相似类型（其中 $\mathbf{a}$ 与 $\mathbf{b}$ 至少共享一个元素），以及 $\mathbf{b}$ 的前一轮颜色。
   $$\varrho_i(\mathbf{a}) := (\varrho_{i-1}(\mathbf{a}), \{ \{ (\text{stp}(\mathbf{a}, \mathbf{b}), \varrho_{i-1}(\mathbf{b})) : \mathbf{b} \in \mathbf{A}, \text{stp}(\mathbf{a}, \mathbf{b}) \neq \emptyset \} \})$$
3. 区分： 如果在任何迭代中，两个结构之间的颜色多重集（考虑重数）存在差异，则 RCR 认为这两个结构是可区分的。

与图的联系

作者建立了从关系结构上的 RCR 到有色多重图上经典 CR 的归约。他们构造了一个有色多重图 $G_{\mathbf{A}}$，其中顶点代表 $\mathbf{A}$ 的元组，边代表元组之间的重叠（相似类型）。在 $G_{\mathbf{A}}$ 上运行 CR 会得到一个稳定着色，该着色等价于 $\mathbf{A}$ 上 RCR 的稳定着色。

核心贡献与结果

1. 组合特征 (定理 A)

论文证明，RCR 区分两个 $\sigma$-结构 $\mathbf{A}$ 和 $\mathbf{B}$，当且仅当存在一个无环且连通的 $\sigma$-结构 $\mathbf{C}$，使得从 $\mathbf{C}$ 到 $\mathbf{A}$ 的同态数量与从 $\mathbf{C}$ 到 $\mathbf{B}$ 的同构数量不同。

• 无环性定义： 作者使用了 $\alpha$-无环性（等价于具有 join-tree 或 hypertree width 为 1）的概念。对于关系结构而言，这比 Gaifman 图的无环性是一个更广泛且更自然的定义。
• 意义： 这推广了 Dvořák、Dell、Grohe 和 Rattan 的研究结果，后者利用树建立了类似的等价关系。

2. 逻辑特征 (定理 B)

论文引入了计数逻辑的受保护片段（Guarded Fragment of Counting Logic），记作 $GF(C)$。该逻辑扩展了一阶逻辑中的计数量词（$\exists^{\ge n}$），但将量化限制在由原子公式“保护”的范围内。
论文证明，RCR 区分 $\mathbf{A}$ 和 $\mathbf{B}$，当且仅当存在一个句子 $\varphi \in GF(C)$，使得 $\mathbf{A} \models \varphi$ 且 $\mathbf{B} \not\models \varphi$。

• 博弈特征： 这种逻辑等价性进一步与受保护博弈（Guarded-Game）（一种 Ehrenfeucht-Fraïssé 博弈的变体）相关联，在该博弈中，当且仅当 RCR 能够区分这两个结构时，破坏者（Spoiler）获胜。

3. 复杂度与实现 (定理 C)

作者提供了 RCR 的高效实现。

• 初始界限： 通过关联图或直接向有色多重图 $G_{\mathbf{A}}$ 进行转换的朴素实现，其运行时间为 $O((\|\mathbf{A}\| + \Gamma(\mathbf{A})) \cdot \log \|\mathbf{A}\|)$，其中 $\Gamma(\mathbf{A})$ 是凝聚度（cohesion，相对于结构大小可能是二次方的）。
• 优化界限： 通过引入一个新的图表示 $H_{\mathbf{A}}$，利用辅助“切片（slice）”节点来解决由重叠元组形成的团（cliques），作者将边的数量减少到与结构大小呈线性关系。
• 结果： 对于任何固定的关系签名，RCR 可以实现为 $O(\|\mathbf{A}\| \cdot \log \|\mathbf{A}\|)$ 的运行时间，其中 $\|\mathbf{A}\|$ 是元组的总数。

意义与主张

论文声称，RCR 成功地将经典颜色细化在图上的强大区分能力推广到了任意关系结构，同时保留了在图设定中发现的优雅理论特征。

• 理论统一： 该工作统一了关系结构中的逻辑（$GF(C)$）与组合（来自无环结构的同构计数）视角，镜像了图中的$C_2$/树等价性。
• 实际效率： $O(\|\mathbf{A}\| \cdot \log \|\mathbf{A}\|)$ 的运行时间确保了这种推广在计算上的可行性，使其成为同构测试及其他领域的有力候选方案。
• 基础作用： 作者指出，RCR 为推广高维 Weisfeiler-Leman 算法，以及潜在地将关于合式查询评估（conjunctive query evaluation）和图神经网络的结果提升到任意关系结构方面，提供了理论基础。

本文并未展示实验结果，也未呈现除这些理论推广及关于未来在查询评估和机器学习中用途的推测之外的具体新应用。