对齐引导的最大表格重叠大小估计

# 对齐引导的最大表格重叠规模估计

来源：https://arxiv.org/html/2607.03049 (2018)

###### 摘要

快速估计表格间最大重叠的大小，能够在大型表格存储库中实现阻塞和基于查询表的检索。首个且最先进的估计器 Armadillo 通过独立嵌入每个表格并利用嵌入相似度近似重叠率来提高效率。然而，在异构存储库中的准确估计仍受三个挑战所限：(C1) 重叠依赖于行列结构，即每个匹配单元格必须在两个表格的联合对齐下保持其行和列隶属关系，但现有编码使这种结构需要间接推断；(C2) 独立编码未提供显式的表间对齐信号通道，使得预测偏向全局相似度；(C3) 朴素的数值编码过拟合于语料特定分布，导致跨域性能退化。因此，我们提出 ALORE，一种可扩展且领域鲁棒的重叠率估计器，它基于三个原则：(P1) 显式表示行列结构；(P2) 在训练期间暴露表间对齐信号，而不需要昂贵的对齐搜索；(P3) 降低对语料特定值分布的敏感性。ALORE 通过双视图行列超图编码器、带有廉价交互信号的对齐引导目标以及领域鲁棒的值映射来实例化这些原则。在多个跨领域和跨规模的数据集（包括一个超越先前基准的大型真实语料库）上的实验表明，ALORE 优于现有技术水平。ALORE 总体上将 MAE 降低了最高 55%，在零样本迁移中降低了 69%，同时实现了最高 89 倍的加速。我们进一步验证了它在基于查询表检索中的有效性。

††copyright:acmlicensed
††journalyear:2018
††doi:XXXXXXX.XXXXXXX
††conference:请从您的权利确认邮件中输入正确的会议标题；2018年6月03-05日，纽约州伍德斯托克
††isbn:978-1-4503-XXXX-X/2018/06

## 1. 引言

我们研究*表格重叠率估计* (Pugnaloni et al., 2025)：给定两个表格，估计其*最大重叠的规模*。直观上，这是两个表格在数值上能够精确共享的最大公共矩形子表中的单元格数量。该子表通过单射（一对一）的行和列对齐来重新排列行和列而得。我们将这个规模（除以较小表格的单元格数）称为*重叠率*。

考虑一个在房产销售表格存储库中进行的搜索与整理工作流。用户提供一个目标表格（房产销售记录），并请求系统从一个从公共机构、列表门户和归档快照收集的大型存储库中查找重复或近乎重复的表格。大多数候选表格是不相关的，尽管许多可能表面上相似。相关候选表格可能包含相同的销售记录（行和列顺序重排），或者仅覆盖目标表格的一个子集（因为提取的时间窗口不同），或者存在缺失和不一致的标题。仅通过元数据很难识别这些候选表格，而对所有候选表格进行精确计算代价太高。因此，系统需要一个快速的过滤步骤，以保留可能的重排副本和部分提取，同时在进行昂贵的精确验证之前丢弃不相关的表格。

上述例子说明了为什么重叠率估计是大型表格存储库中的一个有用原语 (Pugnaloni et al., 2025)。一个快速的估计器可以将非常大的候选空间缩减为一小组包含大量共同内容的候选表格。这些候选表格随后可以由更昂贵的下游处理来处理，例如精确重叠计算 (Zecchini et al., 2024)、表格回收 (Fan et al., 2024)、去重 (Koch et al., 2023) 或相关表格发现 (Sarma et al., 2012)。相同的估计支持基于查询表的检索 (Bleifuß et al., 2021a, b; Hulsebos et al., 2023)，其中用户提供查询表，系统按重叠率检索或过滤表格。它还有助于通过量化跨快照的内容变化来进行版本控制和演化分析 (Zecchini et al., 2024; Bleifuß et al., 2021a)。关键的是，这些场景不能假设有可靠的模式线索、元数据或预先对齐的行/列组织：标题经常不一致或缺失 (Adelfio and Samet, 2013; Cafarella et al., 2008)，大约 20% 的 Web 表格缺少可识别的标题 (Pimplikar and Sarawagi, 2012)。图 1 总结了这三个用例。

**现有解决方案与开放挑战。** 计算精确重叠率需要找到*最大重叠*，这是一个组合性的行/列对齐问题，属于 NP-难问题 (Zecchini et al., 2024)。Sloth (Zecchini et al., 2024) 可以精确求解，但规模过大时速度极慢，处理 10 万对表格需要数天，而针对 1 万个表格的查询需要数小时 (Zecchini et al., 2024; Pugnaloni et al., 2025)。受此启发，Armadillo (Pugnaloni et al., 2025) 是第一个提出基于学习的估计器的工作，并且仍然是当前最先进的技术。本质上，它将每个表格编码为一个图，独立嵌入它们，然后根据两个嵌入之间的相似度来估计重叠率。通过用嵌入相似度替代昂贵的对齐搜索，Armadillo 大大提高了效率。然而在实践中，重叠率估计必须在异构存储库中工作。表格来自不同来源，具有不同的布局、分布和噪声。为新的表格对获取重叠标签代价高昂，因为这需要解决组合对齐问题。因此，对每个新语料库重新训练常常不切实际。这使得重叠率估计颇具挑战性。我们希望估计器不仅在领域内准确，而且在部署到未见过的存储库时也能保持准确，且无需新标签。为了满足这些要求，估计器必须 (i) 表示定义重叠的依赖于对齐的*行列结构*。我们用行列结构来指代单元格按其行和列隶属关系的组织，以及有效重叠必须在联合的行和列对齐下保持两种隶属关系的要求。它还必须 (ii) 在不进行昂贵对齐搜索的情况下纳入特定于对的相关信号，以及 (iii) 在具有不同内容的存储库中保持鲁棒。受此场景启发，我们识别出三个开放挑战：

- **C1：标准图未能充分表达联合行列结构。** 重叠依赖于*联合*的行-列对齐，但 Armadillo 的图通过成对边连接行和列到单元格，使得这种联合结构需要间接推断。
- **C2：独立编码使模型偏向全局相似度。** 独立嵌入表格没有提供显式的通道来建模 T1 的哪些部分应该与 T2 的哪些部分对齐。
- **C3：值分布偏移导致跨域性能退化。** 不同语料库的值词汇和频率各不相同，朴素编码会过拟合于语料特定的模式（在第 7.3 节中，零样本迁移的误差高出 3.7 倍以上）。

![参见说明文字](图 1：重叠率估计的用例。)

**我们的解决方案。** 为了解决 C1–C3，我们提出 ALORE（对齐引导的重叠率估计器），一种用于可扩展和领域鲁棒的重叠率估计的交互感知模型。ALORE 围绕三个原则设计：

- **P1：结构表达性编码。** 为了显式化行列结构 (C1)，我们将每个表格建模为一个双视图行列超图，其中行和列超边连接单元格节点。然后我们使用结构感知编码器对其进行编码，以生成保留这些结构约束的嵌入。
- **P2：表间对齐引导学习。** 为了暴露独立编码所遗漏的对应信号 (C2)，我们引入了一个多粒度对齐正则化器，在训练期间鼓励行级和列级的对应关系，同时结合重叠回归损失。在预测时，我们将学习的嵌入与轻量级交互特征融合，这些特征捕获特定于对的重叠信号，同时保持推理高效。
- **P3：领域鲁棒的值映射。** 为了改善值分布偏移下的零样本迁移 (C3)，我们将单元格值映射到离散桶中，并通过一致性正则化器训练 ALORE 对桶索引的随机重标号保持不变性。这减少了对语料特定值频率的依赖，同时保留了每个表格对内精确的值相等性。

我们的贡献如下：

- 我们识别了重叠率估计的三个挑战：未充分表达的行列结构、独立编码下缺失的表间对齐信号，以及跨域的值分布偏移（第 3.1 节）。这些观察形成了塑造 ALORE 的三个设计原则（第 3.2 节）。
- 我们提出了一个双视图行列超图及其专用编码器，产生保留结构的嵌入，捕获联合行列结构（第 4.1 和 4.2 节）。
- 我们开发了一个**交互-编码-预测**流水线，带有对齐引导的目标，在不要求精确对齐的情况下纳入表间交互信号：**交互**计算成对信号，**编码**生成基于超图的表示，**预测**融合它们以回归重叠率（第 5.1 节）。
- 我们引入了随机桶排列和一致性正则化器以提高领域鲁棒性（第 4.3 和 5.2 节）。
- 我们提供了理论分析，表明 ALORE (i) 对行和列排列具有不变性，符合重叠定义的要求；(ii) 在每个编码器层内高效捕获完整的行和列上下文；(iii) 通过强制对索引重标号的不变性提供领域鲁棒性（第 6 节）。
- 我们在三个数据集上进行了评估，涵盖多个领域和规模，包括一个超越先前基准的大型真实语料库。在领域内和跨域设置中，ALORE 始终优于现有技术，总体上将 MAE 降低了最高 55%，在零样本迁移中降低了 69%，同时实现了最高 89 倍的加速。我们进一步验证了它在基于排名和基于阈值的检索中的有效性（第 7 节）。

## 2. 预备知识

我们首先介绍表格重叠和重叠率的定义，然后正式定义重叠率估计任务。接着，我们简要回顾当前的最新技术。

### 2.1. 问题形式化

一个*表格* T 是具有 m 行和 n 列的二维结构。设 I = {1, ..., m} 和 J = {1, ..., n} 分别是行和列索引的集合。位于第 i∈I 行、第 j∈J 列的单元格的值记为 c_{i,j}。表格的大小为 |T| = mn。

对于两个表格 T1 和 T2，我们使用 c_{i,j}^{(1)} 和 c_{i,j}^{(2)} 分别表示 T1 和 T2 中的单元格值。

**两个表格之间的重叠。** 表格的一个关键特性是其语义对行和列顺序不变。因此，重叠是相对于它们索引之间的一个*对齐*来定义的 (Zecchini et al., 2024)。考虑两个表格 T1 和 T2。T1 与 T2 之间的一个*对齐* A 是一对单射映射 μ: I1′ → I2′, ν: J1′ → J2′，其中 I1′⊆I1, I2′⊆I2 且 J1′⊆J1, J2′⊆J2 满足 |I1′| = |I2′| 且 |J1′| = |J2′|。直观上，μ 选择并重新排序 T1 的行子集以匹配 T2 的行子集，ν 对列做同样的事。给定 A = (μ, ν)，由 A 诱导的*重叠*是具有*相同值*（相同字符串、数字或空值）的匹配单元格的集合：
O_A = { (i, j) ∈ I1′ × J1′ | c_{i,j}^{(1)} = c_{μ(i), ν(j)}^{(2)} }。
基数 |O_A| 是在 A 下的重叠大小。我们的重叠定义基于精确的单元格相等。因此，一对空值被视为匹配，就像两个相同字符串或数字一样。然而，在某些应用中，重叠可能仅针对观测值定义，此时应排除空值对。当空值具有不同含义时，更精细的定义是可能的。例如，空值可能表示不适用属性，此时匹配空值是合理的。在其他情况下，它可能表示值未知，此时匹配空值可能具有误导性。区分这些情况需要数据集特定的空值语义和标注规则，这超出了本文的范围。

**最大重叠。** 设 A* 是一个最大化匹配单元格数量的最优对齐，即 A* ∈ argmax_A |O_A|。我们将*最大重叠*定义为相应的重叠 O* = O_{A*}。直观上，O* 是在 T1 与 T2 之间通过最优重新排序其行列后可以获得的*最大规模公共子表*。

**重叠率。** 为了比较不同大小的表格，我们将最大重叠的规模标准化为较小表格的面积 (Pugnaloni et al., 2025)。得到的*重叠率* θ 定义为：
θ(T1, T2) = |O*| / min(|T1|, |T2|), θ ∈ [0, 1]。

**问题定义。** 我们现在将重叠率估计形式化为一个回归问题。

###### 定义 0 (重叠率估计)。 给定两个