arXiv:2607.03049v1 [cs.CL] 3 Jul 2026
Alignment-Guided Largest Table Overlap Size Estimation Ge Lee∗
Shixun Huang
Zhifeng Bao
RMIT University Melbourne, Australia [email protected]
University of Wollongong Wollongong, Australia [email protected]
The University of Queensland Brisbane, Australia [email protected]
Shazia Sadiq
Yanchang Zhao
The University of Queensland Brisbane, Australia [email protected]
Data61, CSIRO Canberra, Australia [email protected]
Abstract Fast estimation of the size of the largest overlap between tables enables blocking and query-by-table retrieval in large table repositories. The first and the state-of-the-art estimator Armadillo improves efficiency by embedding each table independently and approximating overlap ratio via embedding similarity. However, accurate estimation in heterogeneous repositories remains limited by three challenges: (C1) overlap depends on row–column structure, i.e., each matched cell must preserve both its row and column membership under a joint alignment of the two tables, but existing encodings leave this structure to be inferred indirectly; (C2) independent encoding provides no explicit channel for inter-table alignment signals, biasing prediction toward global similarity; (C3) naïve value encodings overfit to corpus-specific distributions, causing cross-domain degradation. Hence, we propose ALORE, a scalable and domain-robust overlap ratio estimator built on three principles: (P1) explicitly represent row–column structure; (P2) expose inter-table alignment signals during training without expensive alignment search; (P3) reduce sensitivity to corpus-specific value distributions. ALORE instantiates these principles with a Two-View Row–Column Hypergraph encoder, alignment-guided objectives with inexpensive interaction signals, and a domain-robust value mapping. Experiments on multiple datasets spanning diverse domains and scales, including a large real-world corpus beyond prior benchmarks, show that ALORE outperforms the state of the art. ALORE reduces MAE by up to 55% overall and 69% in zero-shot transfer, while achieving up to 89× speedup. We further validate its effectiveness for query-by-table retrieval.
1
Introduction
We study table overlap ratio estimation [43]: given two tables, estimate the size of their largest overlap. Intuitively, this is the number of cells in the largest common rectangular subtable that the two tables can share exactly in value. This subtable is obtained by reordering rows and columns through injective (one-to-one) row and column alignments. We refer to this size, normalized by the number of cells in the smaller table, as the overlap ratio. Consider a workflow of repository search and curation over tables of property sales. A user provides a target table of property sale records and asks the system to find duplicate or near-duplicate tables in a large repository collected from public agencies, listing ∗ This work was done while the author was a visiting student at The University of Queensland and affiliated with Data61, CSIRO.
portals, and archived snapshots. Most candidates are unrelated, even though many may appear superficially similar. Relevant candidates may contain the same sale records with rows and columns reordered, cover only a subset of the target because they were extracted over different time windows, or have missing and inconsistent headers. These candidates are difficult to identify from metadata alone, and exact computation over all candidates is too expensive. The system therefore needs a fast filtering step that retains likely reordered copies and partial extracts, while discarding unrelated tables before expensive exact verification. The above illustrates why overlap ratio estimation is a useful primitive in large table repositories [43]. A fast estimator can reduce a very large candidate space to a small set of candidate tables that share substantial content. These candidates can then be handled by more expensive downstream processing, such as exact overlap computation [58], table reclamation [20], deduplication [31], or related table discovery [47]. The same estimate supports queryby-table retrieval [6, 7, 26], where a user provides a query table and the system retrieves or filters tables by overlap ratio. It also facilitates versioning and evolution analysis by quantifying content changes across snapshots [7, 58]. Crucially, these settings cannot assume reliable schema cues, metadata, or pre-aligned row/column organization: headers are frequently inconsistent or missing [2, 10], and about 20% of Web tables lack identifiable headers [42]. Figure 1 summarizes these three use cases. Existing Solutions and Open Challenges. Computing exact overlap ratio requires finding the largest overlap, a combinatorial row/column alignment problem that is NP-hard [58]. Sloth [58] solves it exactly but is prohibitively slow at scale, taking days for 100k pairs and hours per query over 10k tables [43, 58]. Motivated by this, Armadillo [43] is the first work that proposes a learning-based estimator and remains the state of the art. Essentially, it encodes each table as a graph, embeds them independently, and estimates overlap ratio from the similarity between the two embeddings. By replacing expensive alignment search with embedding similarity, Armadillo improves efficiency drastically. In practice, however, overlap ratio estimation must work in heterogeneous repositories. Tables come from diverse sources with different layouts, distributions, and noise. Obtaining overlap labels for new table pairs is expensive because it requires solving combinatorial alignments. Consequently, retraining for every new corpus is often impractical. This makes overlap ratio estimation challenging. We want an estimator to remain accurate not only in-domain, but also when deployed on unseen repositories, without
Ge Lee, Shixun Huang, Zhifeng Bao, Shazia Sadiq, and Yanchang Zhao
discrete buckets and train ALORE to be invariant to random relabelings of bucket indices via a consistency regularizer. This reduces reliance on corpus-specific value frequencies while preserving exact value equality within each table pair. Our contributions are as follows:
Figure 1: Use cases of overlap ratio estimation. requiring new labels. To meet these requirements, an estimator must (i) represent the alignment-dependent row–column structure that defines overlap. We use row–column structure to refer to the organization of cells by their row and column memberships, together with the requirement that valid overlap must preserve both memberships under a joint row and column alignment. It must also (ii) incorporate pair-specific correspondence signals without expensive alignment search, and (iii) remain robust across repositories with different content. Motivated by this setting, we identify three open challenges: • C1: Standard graphs underexpress joint row–column structure. Overlap depends on a joint row–column alignment, but Armadillo’s graph connects rows and columns to cells through pairwise edges, leaving this joint structure to be inferred indirectly. • C2: Independent encoding biases the model toward global similarity. Embedding tables independently provides no explicit channel to model which parts of 𝑇1 should align to which parts of 𝑇2 . • C3: Value distribution shift causes cross-domain degradation. Value vocabularies and frequencies vary across corpora, and naïve encoding overfits to corpus-specific patterns (over 3.7× higher error in zero-shot transfer in Section 7.3).
Our Solution. To address C1–C3, we propose ALORE (ALignmentguided Overlap Ratio Estimator), an interaction-aware model for scalable and domain-robust overlap ratio estimation. ALORE is designed around three principles: • P1: Structure-expressive encoding. To make row–column structure explicit (C1), we model each table as a Two-View Row– Column Hypergraph with row and column hyperedges over cell nodes. We then encode this with a structure-aware encoder to produce embeddings that preserve these structural constraints. • P2: Inter-table alignment-guided learning. To expose correspondence signals that independent encoding misses (C2), we introduce a multi-granularity alignment regularizer that encourages row- and column-level correspondences during training, alongside the overlap regression loss. At prediction time, we fuse the learned embeddings with lightweight interaction features that capture pairspecific overlap signals, while keeping inference efficient. • P3: Domain-robust value mapping. To improve zero-shot transfer under value distribution shift (C3), we map cell values into
• We identify three challenges for overlap ratio estimation: underexpressed row–column structure, missing inter-table alignment signals under independent encoding, and value distribution shift across domains (Section 3.1). These observations motivate three design principles that shape ALORE (Section 3.2). • We propose a Two-View Row–Column Hypergraph with a dedicated encoder that produces structure-preserving embeddings capturing joint row–column structure (Sections 4.1 and 4.2). • We develop an Interact-Encode-Predict pipeline with alignmentguided objectives that incorporate inter-table interaction signals without requiring exact alignment: Interact computes pairwise signals, Encode produces hypergraph-based representations, and Predict fuses them to regress overlap ratio. (Section 5.1). • We introduce stochastic bucket permutations and a consistency regularizer to improve domain robustness (Sections 4.3 and 5.2). • We provide theoretical analysis showing that ALORE (i) is invariant to row and column permutations, as required by the overlap definition; (ii) captures full row and column context efficiently within each encoder layer; and (iii) provides domain robustness by enforcing invariance to index relabeling (Section 6). • We evaluate on three datasets spanning multiple domains and scales, including a large real-world corpus beyond prior benchmarks. Across in-domain and cross-domain settings, ALORE consistently outperforms the state of the art, reducing MAE by up to 55% overall and 69% in zero-shot transfer, while achieving up to 89× speedup. We further validate its effectiveness for query-by-table retrieval under both ranking and threshold-based retrieval (Section 7).
2
Preliminaries
We begin by introducing the definitions of table overlap and overlap ratio, followed by the formal definition of the overlap ratio estimation task. Then, we briefly review the current state of the art.
2.1
Problem Formulation
A table 𝑇 is a two-dimensional structure with 𝑚 rows and 𝑛 columns. Let 𝐼 = {1, . . . , 𝑚} and 𝐽 = {1, . . . , 𝑛} be the sets of row and column indices, respectively. The value stored in the cell located at row 𝑖 ∈ 𝐼 and column 𝑗 ∈ 𝐽 is denoted by 𝑐𝑖, 𝑗 . The size of the table is |𝑇 | = 𝑚𝑛. For two tables 𝑇1 and 𝑇2 , we use 𝑐𝑖,(1)𝑗 and 𝑐𝑖,(2)𝑗 to denote cell values in 𝑇1 and 𝑇2 , respectively. Overlap Between Two Tables. A key property of tables is that their semantics are invariant to row and column order. Accordingly, overlap is defined with respect to an alignment between their indices [58]. Consider two tables 𝑇1 and 𝑇2 . An alignment A between 𝑇1 and 𝑇2 is a pair of injective mappings 𝜇 : 𝐼 1′ → 𝐼 2′ , 𝜈 : 𝐽1′ → 𝐽2′ , where 𝐼 1′ ⊆ 𝐼 1, 𝐼 2′ ⊆ 𝐼 2 and 𝐽1′ ⊆ 𝐽1, 𝐽2′ ⊆ 𝐽2 satisfy |𝐼 1′ | = |𝐼 2′ | and |𝐽1′ | = |𝐽2′ |. Intuitively, 𝜇 selects and reorders a subset of rows of 𝑇1 to match a subset of rows of 𝑇2 , and 𝜈 does the same for columns respectively. Given A = (𝜇, 𝜈), the overlap induced by A is the set
Alignment-Guided Largest Table Overlap Size Estimation
of matched cells with identical values, i.e., the same string, number, or null: 𝑂 A = (𝑖, 𝑗) ∈ 𝐼 1′ × 𝐽1′ 𝑐𝑖,(1)𝑗 = 𝑐 𝜇(2) . The cardinality (𝑖 ), 𝜈 ( 𝑗 ) |𝑂 A | is the overlap size under A. Our overlap definition is based on exact cell equality. Thus, a pair of null values is counted as a match, just as two identical strings or numbers are. In some applications, however, overlap may be defined only over observed values, in which case pairs of null values should be excluded. More refined definitions are possible when nulls have different meanings. For example, a null may denote an inapplicable attribute, where matching nulls is reasonable. In other cases, it may indicate the value is unknown, where matching nulls may be misleading. Distinguishing these cases requires dataset-specific null semantics and labeling rules, which are beyond the scope of this paper. Largest Overlap. Let A ∗ be an optimal alignment that maximizes the number of matched cells, i.e., A ∗ ∈ arg max A |𝑂 A |. We define the largest overlap as the corresponding overlap 𝑂 ∗ = 𝑂 A ∗ . Intuitively, 𝑂 ∗ is a maximum-size common subtable obtainable between 𝑇1 and 𝑇2 after optimally reordering their rows and columns. Overlap Ratio. To compare tables of differing sizes, we normalize the size of the largest overlap by the area of the smaller table [43]. The resulting overlap ratio 𝜃 is defined as 𝜃 (𝑇1, 𝑇2 ) = |𝑂 ∗ | min( |𝑇1 |, |𝑇2 | ) , 𝜃 ∈ [0, 1]. Problem Definition. We now formalize overlap ratio estimation as a regression problem. Definition 1 (Overlap Ratio Estimation). Given two tables 𝑇1 and 𝑇2 , let 𝜃 be their ground-truth overlap ratio. The task is to learn a parameterized model 𝑀𝜙 that predicts 𝜃ˆ = 𝑀𝜙 (𝑇1,𝑇2 ) to approximate 𝜃 . Given a training set of labeled pairs D = {(𝑇1,𝑇2, 𝜃 )}, the learning objective is to obtain parameters 𝜙 ∗ that minimize the prediction Í error, i.e., 𝜙 ∗ = arg min𝜙 (𝑇1 ,𝑇2 ,𝜃 ) ∈ D ℓ 𝑀𝜙 (𝑇1,𝑇2 ), 𝜃 , where ℓ (·, ·) measures the error between 𝜃ˆ and 𝜃 .
2.2
State of the Art
The state of the art in learning-based overlap ratio estimation is Armadillo [43]. It learns table embeddings whose cosine similarity approximates the overlap ratio, thereby addressing the scalability limitations of exact solver. Armadillo follows a design paradigm that we characterize as the Encode-Compare paradigm: (1) Encode. Each table is independently mapped to a tripartite graph with row, column, and cell nodes. Undirected edges connect cell nodes to their row and column nodes. A graph neural network (GNN), GraphSAGE [25], is employed to refine the node embeddings and a mean pooling readout produces a single embedding vector as the final table representation. (2) Compare. Given two tables, the model approximates their overlap ratio by computing the cosine similarity between their respective embeddings. This similarity score is treated as the predicted overlap ratio 𝜃ˆ. This architecture allows for efficient estimation, as embedding a table requires only linear-time graph construction, and the final estimation reduces to a simple vector similarity computation.
3
Design Rationale for Overlap Ratio
The overlap ratio is defined by the optimal joint alignment of rows and columns across two tables. This makes overlap ratio estimation fundamentally different from global table similarity. Under this definition, two tables share content only when subsets of rows and columns can be jointly aligned into a common subtable. However, prevailing Encode-Compare estimator embeds each table independently and compares the resulting embeddings, which biases learning toward global similarity rather than alignment evidence. Figure 2 provides the roadmap for this section: the left panel summarizes the three challenges that follow from this mismatch (Section 3.1), the middle panel distills the corresponding design principles (Section 3.2), and the right panel shows how ALORE, our overlap ratio estimator, realizes them end-to-end (Section 3.3).
3.1
Challenges
As illustrated in Figure 2 (left), the Encode-Compare paradigm induces a bias toward global similarity, whereas overlap is driven by whether subsets of rows and columns can be aligned into correspondence. In particular, its tripartite graph representation and independent encoding make row–column structure and pair-specific correspondences only indirectly observable. This gap is amplified in cross-domain settings, where value distributions shift substantially. We next characterize three concrete challenges that follow. Challenge 1: Tripartite graphs underexpress joint row–column structure. Armadillo represents a table as a tripartite graph. While this faithfully captures tabular adjacency and separate row and column membership signals, it does not make joint row–column structure explicit. A cell contributes to the largest overlap only when its row and column can both be aligned across two tables. In the tripartite graph, this joint row–column dependency must be inferred indirectly through multi-hop message passing. This indirect inference creates a learning challenge. Each row and column node aggregates information from all of its incident cells. As tables grow, many distinct row–column contexts are blended into shared row and column embeddings. It becomes increasingly difficult for the encoder to preserve which specific row–column combinations consistently co-occur with the same values and could jointly participate in an overlapping region. The resulting representation captures how rows and columns behave individually, but it is not designed to preserve the higher-order row–column structure that determines which subsets of rows and columns can be permuted into a large aligned subtable. Challenge 2: Independent encoding biases the model toward global similarity. Armadillo embeds each table independently and derives overlap ratio through a similarity function. As a result, the model never sees the two tables jointly, and thus cannot adapt its representations to the specific alignment between them. This has two consequences: (i) No explicit value correspondences. The model does not observe which value occurrences across the two tables tend to participate in optimal permutations; (ii) Limited structural compatibility signals. The model cannot directly assess whether subsets of rows and columns in one table are compatible with subsets in the other, because each encoding is computed in isolation. True overlap is defined by a maximal aligned structure. This depends on localized correspondences (e.g., a subset of matching
Ge Lee, Shixun Huang, Zhifeng Bao, Shazia Sadiq, and Yanchang Zhao
Figure 2: Overview of ALORE: challenges in overlap estimation (left), design principles (middle), ALORE architecture (right).
rows/columns), not just global similarity. Under independent encoding with global pooling, such fine-grained evidence is diluted. For example, a single highly overlapping column may dominate the true overlap, yet its signal is averaged with many unrelated cells when forming a single table embedding. Conversely, two tables may appear globally similar in value statistics but have incompatible row—column arrangements, leading to small true overlap despite high embedding similarity. This behavior mirrors a well-known limitation of bi-encoders in retrieval and matching tasks [45], in contrast to cross-encoders that perform interaction across pairs [30, 50]. Armadillo therefore tends to emphasize global content similarity, whereas overlap ratio estimation requires alignment-aware evidence about which parts of the two tables can be put into correspondence. Challenge 3: Value distribution shift causes cross-domain degradation. Armadillo initializes cell features using SHA-256 hashing of raw cell values, and then refines them via GraphSAGE layers. In principle, hashing is domain-agnostic. Equal values map to equal hashes, and the semantics of the value do not matter for overlap. In practice, the learned embeddings capture the distribution of the training corpus. Different corpora often exhibit distinct distributions (e.g., tables dominated by strings or floats). When hashed values are propagated and aggregated via global pooling, the encoder inevitably learns these corpus-specific distributions. As a result, the learned embedding space becomes specific to the training domain rather than capturing domain-invariant signals needed for alignment-based overlap ratio estimation. Empirically, this manifests as substantial cross-domain degradation. When trained on one corpus and evaluated on the other, Armadillo’s MAE triples, and in some settings it is outperformed by simple Jaccard-based baselines that ignore tabular structure. This suggests that the model conflates overlap with corpus-specific value distributions instead of focusing on domain-invariant structural and relational cues.
3.2
Design Principles
Figure 2 (middle) summarizes three principles that address Challenges 1–3, which we detail next.
Principle 1: Structure-Expressive Encoding via a Two-View Hypergraph. Challenge 1 shows that the tripartite graph exposes row and column information only as separate, pairwise signals, leaving joint row–column structure to be reconstructed indirectly. We therefore introduce a Two-View Row–Column Hypergraph, in which each row and each column is modeled as a hyperedge over cell nodes. Row and column hyperedges form two complementary “views” of the same set of cells. This design follows the broader insight that hypergraph neural networks more naturally capture higher-order group structure than pairwise GNNs [12, 22, 56], but we specialize it to overlap ratio estimation. Our two-view row– column hypergraph preserves the multi-cell behavior of rows and columns that is stable under permutations, so that the encoder can more easily identify combinations of rows and columns that can support a joint alignment between tables. Principle 2: Inter-Table Alignment-Guided Learning. Challenge 2 stems from the Encode-Compare paradigm, since encoding each table independently and comparing only at the end deprives the encoder of any inter-table alignment signals. Motivated by this, we move from Encode-Compare to an Interact-EncodePredict paradigm and make the encoder explicitly alignmentguided. We retain an efficient per-table encoder (the Row–Column Hypergraph Encoder), but train it on table pairs with an overlap regression loss and a multi-granularity alignment regularizer. These pairwise objectives evaluate how well rows, columns, and shared values across the two tables can be aligned and send gradients back through the encoder. At prediction time, an overlap fusion head combines the two table embeddings with a small set of inter-table signals before regressing the overlap ratio. In combination, this introduces lightweight inter-table interaction while preserving biencoder efficiency, directly addressing the structural limitation of the original Encode-Compare’s design. Principle 3: Domain-Robust Value Mapping. Challenge 3 shows that value representations should preserve exact equality without overfitting to corpus-specific value distributions. Inspired by domain randomization and invariant learning [3, 41, 48], we treat cell values as symbolic identities: equal values must remain equal, since overlap is defined by exact cell value matches, but the model
Alignment-Guided Largest Table Overlap Size Estimation
should not learn that particular values are characteristic of a training corpus. We therefore hash values into embedding indices and randomly relabel these indices during training. Each relabeling preserves equality within a table pair, so exact matches remain observable, while preventing any index from carrying domainspecific information. A consistency regularizer further encourages predictions to remain stable under such relabelings. Together, these mechanisms discourage memorization of training-domain value distributions and bias the model toward row/column co-occurrence and alignment patterns that are more stable under domain shift.
3.3
Overview of ALORE
Procedure 1: Training Step of ALORE : A pair of tables (𝑇1 ,𝑇2 ), a ground-truth overlap ratio 𝜃 , the number of hash buckets 𝐵, a gating threshold and exponent (𝜅, 𝛾 ), and a set of weights (𝜆RC , 𝜆val , 𝜆ctx , 𝜆cons ) Output : Training loss Ltotal 1 Forward(𝑇1 ,𝑇2 , 𝐼, 𝜋 ): 2 (𝐻 1 , 𝑍 1 ) ← Encode(𝑇1 , 𝜋 ); // with stochastic value mapping 3 (𝐻 2 , 𝑍 2 ) ← Encode(𝑇2 , 𝜋 ); 4 𝜃ˆ ← Predict( |𝑍 1 − 𝑍 2 |, 𝐼 ); ˆ 𝐻 1 , 𝐻 2 , 𝑍 1 , 𝑍 2 ); 5 return (𝜃, Input
TrainStep(𝑇1 ,𝑇2 , 𝜃 ): 𝜋1 ← UniformRandomPerm( {0, . . . , 𝐵−1} ); 8 𝜋2 ← UniformRandomPerm( {0, . . . , 𝐵−1} ); 9 𝐼 ← [ 𝑆 (𝑇1 ,𝑇2 ) ∥ 𝐽 (𝑇1 ,𝑇2 ) ]; // interaction features 10 (𝜃ˆ1 , 𝐻 1 , 𝐻 2 , 𝑍 1 , 𝑍 2 ) ← Forward(𝑇1 ,𝑇2 , 𝐼, 𝜋1 ); 11 (𝜃ˆ2 , _, _, _, _) ← Forward(𝑇1 ,𝑇2 , 𝐼, 𝜋2 ); // for consistency 12 Lmain ← |𝜃ˆ1 − 𝜃 |; 𝛾 −𝜅 13 𝑊gate ← max 0, 𝜃1−𝜅 ; 6
7
Figure 2 (right) instantiates Principles 1–3 in ALORE. In contrast to the Encode-Compare paradigm designed for global similarity, we organize ALORE as an Interact-Encode-Predict pipeline tailored to overlap ratio estimation. This clarifies where inter-table interaction enters: through inexpensive interaction features at input time and through alignment-guided objectives during training, while inference remains a bi-encoder-style forward pass. (1) Interact. We introduce inter-table interaction through lightweight features computed from the raw table pair, including a Jaccard-based value overlap score and size–shape descriptors derived from table dimensions. These features provide heuristic guidance for predicting the overlap ratio, while the alignment-guided objectives in the Predict stage provide complementary interaction during training, without computing an explicit alignment. (2) Encode. Each table is transformed to a Two-View Row–Column Hypergraph. A shared Row–Column Hypergraph Encoder then processes this structure using stacked dual hyperedge convolution layers and a multi-scale table readout, producing a table embedding from each encoder layer. A domain-robust value mapping initializes cell embeddings using hash-based indices and stochastic permutations during training, encouraging the encoder to focus on structural compatibility rather than corpus-specific value identities. (3) Predict. An overlap fusion head combines the two multiscale table embeddings with the interaction features. Finally, an overlap ratio regressor outputs the final estimated overlap ratio. Training uses an overlap regression loss as the main objective, a multi-granularity alignment regularizer that sends pairwise alignment signals back into the encoder, and a consistency regularizer that stabilizes predictions under randomized value mappings. We instantiate these principles by formalizing hypergraph encoding with domain-robust value mapping (Section 4) and interactionaware prediction with alignment-guided objectives (Section 5).
4
Domain-Robust Hypergraph Encoding
Figure 2 (right) summarizes ALORE’s architecture. Procedure 1 presents the end-to-end training step as a roadmap for Sections 4 and 5. This section explains the Encode stage through its three main components: 1) the Two-View Row–Column Hypergraph that represents each table; 2) the shared Row–Column Hypergraph Encoder that produces structure-aware embeddings; 3) the domainrobust value mapping used to initialize cell features and improve generalization across corpora. Section 5 then presents the Interact and Predict stages, including the pairwise interaction features, prediction head, and alignment-guided training objectives.
23
Lalign ← 0; if 𝑊gate > 0 then LRC ← RowColumnAlign(𝐻 1 , 𝐻 2 ); Lval ← ValueAlign(𝐻 1 , 𝐻 2 ); Lctx ← ContextAlign(𝐻 1 , 𝐻 2 , 𝑍 1 , 𝑍 2 ); Lalign ← 𝑊gate (𝜆RC LRC + 𝜆val Lval + 𝜆ctx Lctx ); Lcons ← ∥ 𝜃ˆ1 − 𝜃ˆ2 ∥ 22 ; Ltotal ← Lmain + Lalign + 𝜆cons Lcons ; Update parameters using ∇ Ltotal ; return Ltotal ;
4.1
Two-View Row–Column Hypergraph
14 15 16 17 18 19 20 21 22
A central challenge in overlap ratio estimation is to capture how subsets of rows and columns can be permuted into an aligned subtable. To expose this higher-order structure explicitly, we model each table 𝑇 with 𝑚 rows and 𝑛 columns as a Two-View Row–Column Hypergraph H (𝑇 ) = (V, Erow ∪ Ecol ), where nodes correspond to individual cells and hyperedges correspond to entire rows and columns, as part of the encode step in Procedure 1 (lines 2–3). Nodes and Features. Each cell 𝑐𝑖, 𝑗 is mapped to a node 𝑣𝑖 𝑗 ∈ V. We apply SHA-256 to the raw cell value 𝑐𝑖, 𝑗 to initialize node feature. This feature is used only as an identity surrogate. Unlike semantic word embeddings [15, 35], this hashing scheme is content-agnostic and preserves exact equality, matching the definition of overlap. Row/Column Hyperedges. To expose the inherent two-dimensional groupings of rows and columns, we introduce two families of hyperedges: the row hyperedges Erow = {𝑒𝑖𝑟 | 𝑒𝑖𝑟 = {𝑣𝑖,1, . . . , 𝑣𝑖,𝑛 }} and the column hyperedges Ecol = {𝑒 𝑐𝑗 | 𝑒 𝑐𝑗 = {𝑣 1,𝑗 , . . . , 𝑣𝑚,𝑗 }}. Each row hyperedge 𝑒𝑖𝑟 connects all cells in row 𝑖, and each column hyperedge 𝑒 𝑐𝑗 connects all cells in column 𝑗. As a result, every cell node participates in exactly two hyperedges, one row and one column, which exposes joint row–column structure explicitly. This construction gives the encoder direct access to full rowand column-level context within a single hypergraph convolution, rather than reconstructing it from multiple hops over cell–row and cell–column binary edges. It also matches the inductive bias
Ge Lee, Shixun Huang, Zhifeng Bao, Shazia Sadiq, and Yanchang Zhao
of overlap. Permuting rows or columns does not change Erow or Ecol , so the hypergraph topology is preserved under any reordering consistent with the overlap definition. Combined with symmetric hypergraph convolutions and permutation-invariant pooling in the Row–Column Hypergraph Encoder (Section 4.2), the resulting table embedding is invariant to row and column permutations. Finally, the dual membership of each cell enables efficient propagation along both axes. A single Dual Hyperedge Convolution layer can pass information across all rows and columns, enabling the encoder to capture row–column combinations associated with consistent value patterns. In contrast, exposing the same signal with a tripartite graph typically requires several hops of pairwise message passing and is more susceptible to oversmoothing [33, 55]. Complexity. Constructing H (𝑇 ) requires a single pass over all cells to create nodes, compute hashes, and assign hyperedge memberships. The resulting time and space complexity is O (|𝑇 |), comparable to building Armadillo’s tripartite graph while offering a structure more conducive to alignment. The resulting incidence structure can be stored in sparse format for efficient batching.
4.2
Row–Column Hypergraph Encoder
ALORE employs a Row–Column Hypergraph Encoder to learn structure-aware cell embeddings from the two-view hypergraph (lines 2–3). The encoder is shared between the two tables, forming a Siamese architecture [9]. Crucially, this does not require crossattention between all cell pairs, which would be computationally prohibitive for large tables. Unlike previous approaches that inject interaction signals directly into the encoding process, we maintain a pure structural encoder to learn domain-invariant features. Dual Hyperedge Convolution Layer. The encoder stacks 𝐿 dual hyperedge convolution layers. Let 𝐻 (𝑙 ) ∈ R | V | ×𝑑 denote the node embeddings after layer 𝑙, where 𝑑 is the embedding dimension. Given 𝐻 (𝑙 −1) , the 𝑙-th layer applies two independent hypergraph (𝑙 ) (𝑙 ) convolutions [23] to obtain 𝐻 row = HConv(𝐻 (𝑙 −1) , Erow ) and 𝐻 col = (𝑙 −1) (𝑙 ) HConv(𝐻 , Ecol ). The two views are then fused: 𝐻 = (𝑙 ) (𝑙 ) ReLU LayerNorm Linear [𝐻 row ∥ 𝐻 col ] , where [· ∥ ·] denotes concatenation. This design ensures that each cell update is informed by both its row and column context. The layer is permutationinvariant to row/column orderings and runs in time linear in the number of cell–hyperedge incidences. Multi-Scale Table Readout. To capture structure at different depths, the encoder exposes a multi-scale table readout. At each layer 𝑙 ∈ 1, . . . , 𝐿, an inner projection first applies a lightweight MLP to the node embeddings 𝐻 (𝑙 ) . We then aggregate the projected nodes with permutation-invariant global sum pooling to (𝑙 ) obtain a layer-wise table vector 𝑧 pool . An outer projection finally (𝑙 ) refines 𝑧 pool via another MLP, yielding the readout 𝑧 (𝑙 ) . We use sum pooling since it preserves multiplicities and yields a more expressive multiset readout than averaging [55]. The final table representation concatenates all layer-wise vectors and normalizes them, i.e., 𝑍 = LayerNorm([𝑧 (1) ∥ · · · ∥ 𝑧 (𝐿) ]). This multi-scale representation serves two roles. First, the final-layer embedding dominates the main prediction task, giving the overlap fusion head access to a rich summary. Second, the intermediate embeddings
𝐻 (1) , . . . , 𝐻 (𝐿) together with readouts 𝑧 (𝑙 ) parameterize our multigranularity alignment regularizer (Section 5.2), which enforces alignment at row, column, and value levels. Complexity. Each dual hyperedge convolution layer processes every cell once in its row hyperedge and once in its column hyperedge, so the cost per layer is O (|𝑇 |𝑑) for embedding dimension 𝑑. With 𝐿 layers, the Row–Column Hypergraph Encoder runs in O (𝐿|𝑇 |𝑑) time and O (|𝑇 |𝑑) space, matching the asymptotic order of GNNs on Armadillo’s tripartite graph.
4.3
Domain-Robust Value Mapping
Even with symbolic hashing, a fixed embedding table can leak corpus-specific frequency patterns into the learned space. This hurts transfer because the estimator may partially rely on which hashed buckets are common in the training corpus rather than on alignment-relevant structure. Principle 3 addresses this by randomizing the association between hashed values and embedding indices during training, while preserving exact value equality within each forward pass. Bucketization and Stochastic Permutation. Let 𝐵 denote the number of hash buckets, which fixes the size of the value-embedding table. Each hashed feature 𝑥𝑖,𝑗 is mapped into a fixed index range [0, 𝐵 − 1] via a modulo operation idx𝑖,𝑗 = 𝑥𝑖,𝑗 mod 𝐵, which defines a bounded embedding table. In Forward, the encoder uses a supplied permutation 𝜋 and performs embedding lookup with the permuted indices 𝜋 (idx𝑖,𝑗 ) during encoding (lines 2–3). During training, TrainStep draws two independent random permutations over {0, . . . , 𝐵 − 1} for the two forward passes (lines 7–8). This mechanism preserves the equality relation within a training step: two cells share an embedding if and only if they share the same hashed value and thus the same permuted index. At the same time, it breaks any stable association between a specific index and its global distribution across training epochs. The encoder cannot memorize that a particular index corresponds to a corpus-specific keyword. Therefore, it must instead rely on structural patterns, such as how the same value appears in compatible rows and columns across the two tables. At inference time, the permutation is disabled and embeddings are looked up directly using idx𝑖,𝑗 . The mapping remains deterministic and efficient while the model has already learned to be insensitive to the absolute positions of embedding indices. Size–Shape Normalization Features. Value embeddings alone do not adjust for distribution shifts in table sizes and aspect ratios. We therefore complement the node-level mapping with size–shape features that capture relative shape and scale rather than absolute magnitudes. For a table pair (𝑇1, 𝑇2 ), we compute a 7-dimensional vector 𝑆 (𝑇1, 𝑇2 ) from the log-transformed row and column counts of both tables log 𝑚 1 , log 𝑛 1 , log 𝑚 2 , log 𝑛 2 , the log of the smaller table area log(min(|𝑇1 |, |𝑇2 |)), and the ratios between row and colmin(𝑚 1 ,𝑚 2 ) min(𝑛 1 ,𝑛 2 ) umn counts max(𝑚 , . These features are then fed into 1 ,𝑚 2 ) max(𝑛 1 ,𝑛 2 ) the overlap fusion head after a scaling and mixing step. They stabilize the representation across corpora with different table size distributions. Together, the stochastic value mapping and size–shape features decouple identity from distributional context. The permutation mechanism forces the encoder to treat value identities as purely
Alignment-Guided Largest Table Overlap Size Estimation
symbolic rather than tying them to persistent embeddings associated with corpus-specific distributions. The size–shape features, in turn, factor out absolute table magnitudes and anchor the model on relative shape- and size-related signals that transfer across corpora. As a result, the learned representation retains equality information needed for overlap while reducing sensitivity to domain-specific value or size distributions. Finally, during training we couple this randomized mapping with a consistency regularizer (Section 5.2) that enforces stable predictions across independently sampled permutations (lines 10–11, 20). This encourages invariance to bucketindex relabeling rather than memorization of bucket identities.
regressor, a two-layer MLP that outputs the predicted overlap ratio 𝜃ˆ ∈ [0, 1]. This allows the predictor to combine fine-grained structural similarity with inter-table interaction signals (line 4).
Complexity. Bucketization and stochastic permutation operate in O (|𝑇 |) time per table, plus O (𝐵) time per batch to generate a new permutation. Computing 𝑆 (𝑇1, 𝑇2 ) requires only simple scalar operations on row and column counts and is negligible compared to hypergraph encoding.
ALORE is trained with a primary overlap regression loss and two regularizers. The multi-granularity alignment regularizer injects row-, column-, and value-level correspondence signals into the shared encoder without requiring discrete alignment supervision. The consistency regularizer enforces prediction stability under the stochastic value permutations of domain-robust value mapping. Both regularizers are used only during training, so inference remains a single bi-encoder forward pass.
5
Alignment-Guided Prediction
Section 4 describes how ALORE encodes each table into a structureaware and domain-robust representation. We now turn to the pairwise components that make these representations predictive of alignment-dependent overlap. As shown in Figure 2 (right), ALORE (i) augments the encoded table representations with inexpensive interaction features computed directly from the raw pair, and (ii) trains the shared encoder with alignment-guided objectives that expose correspondence signals without requiring explicit row–column alignments. We first describe the interaction-aware regressor, and then present the training losses and regularizers, following the prediction and loss computation steps in Procedure 1.
5.1
Interaction-Aware Regressor
The Predict stage combines (i) structure-aware embeddings produced by the shared encoder and (ii) lightweight interaction features computed directly from the raw pair. This design injects cheap inter-table signals without quadratic cross-attention over tables. Inter-Table Interaction Features. For a table pair (𝑇1, 𝑇 2 ), we construct a compact interaction feature vector 𝐼 (𝑇1, 𝑇2 ) = 𝑆 (𝑇1, 𝑇2 ) ∥ 𝐽 (𝑇1, 𝑇2 ) . Here, 𝑆 (𝑇1, 𝑇2 ) is the 7-dimensional size–shape descriptor defined earlier (from log-transformed table dimensions and row/column ratios), and 𝐽 (𝑇1, 𝑇2 ) is a Jaccard anchor defined as the Jaccard similarity between the sets of cell values of 𝑇1 and 𝑇2 . These interaction features do not attempt to reconstruct the optimal permutation. Instead, they serve as signals about value co-occurrence and relative table shape and size. These help the predictor to estimate plausible overlap ratios without relying solely on the learned structural embeddings (line 9). Overlap Fusion Head and Overlap Ratio Regressor. Let 𝑍 1 and 𝑍 2 be the multi-scale table embeddings produced by the Row–Column Hypergraph Encoder and multi-scale table readout. We first form a structural difference feature 𝑍 diff = 𝑍 1 − 𝑍 2 . We pass the interaction vector 𝐼 (𝑇1, 𝑇2 ) through a small interaction feature encoder (a linear projection with normalization and non-linearity) to obtain a hidden vector 𝐼 hid (line 4). The overlap fusion head concatenates structural and interaction representations 𝑍 diff ∥ 𝐼 hid and feeds them into the overlap ratio
Complexity. Computing 𝐽 (𝑇1,𝑇2 ) is near-linear in |𝑇1 | + |𝑇2 | using batched hash-based set operations, whereas computing 𝑆 (𝑇1,𝑇2 ) is constant time. The interaction feature encoder and Overlap Fusion Head operate on low-dimensional vectors and have cost O (𝑑) per pair, independent of table size.
5.2
Alignment-Guided Objectives
Overlap Regression Loss. The main objective is the overlap regression loss, an L1 loss between the predicted overlap ratio and the ground truth (line 12): Lmain = 𝜃ˆ(𝑇1,𝑇2 ) − 𝜃 (𝑇1,𝑇2 ) . Multi-Granularity Alignment Regularizer. The multi-granularity alignment regularizer encourages the encoder to produce embeddings that admit the inter-table alignments needed for overlap, without requiring explicit row or column match labels. It provides complementary alignment signals at the row, column, and value levels, including constraints that account for how shared values participate in each table’s row–column structure. The regularizer comprises three components and combines them with a gating factor derived from the ground-truth overlap to avoid enforcing alignments on pairs with negligible overlap. (i) RowColumn-Align. RowColumn-Align first summarizes celllevel embeddings into row proxies and column proxies by mean pooling over the corresponding row and column hyperedges. It then encourages the two tables to admit a consistent row and column correspondence using entropic optimal transport (OT) [13]. Concretely, for the row proxies of 𝑇1 and 𝑇2 , we compute a soft matching matrix 𝑃 with non-negative entries. The matrix is normalized so that each row proxy distributes a fixed total amount of matching weight across the other table, yielding a stable “soft assignment”. A Sinkhorn-like normalization computes 𝑃 efficiently [13]. Using 𝑃, we reconstruct each row proxy of 𝑇1 as a weighted combination of row proxies from 𝑇2 , and vice versa. The row alignment loss is the mean-squared reconstruction error from these two reconstructions. We apply the same procedure to the column proxies to obtain a column alignment loss, and combine the two as LRC = Lrow + Lcol . From an optimization viewpoint, this OT-based construction replaces discrete row and column permutation search with a continuous soft matching that remains differentiable end-to-end. When the two proxy sets have equal size and uniform normalization, the feasible soft matchings include the classical doubly-stochastic relaxations of permutation matrices (a standard convex relaxation of assignments) [37]. In contrast, Sloth optimizes directly over discrete permutations. RowColumn-Align therefore biases the encoder
Ge Lee, Shixun Huang, Zhifeng Bao, Shazia Sadiq, and Yanchang Zhao
toward representations for which a low-cost row and column correspondence exists, while avoiding combinatorial optimization. (ii) Value-Align. Value-Align enforces identity consistency for values shared across the two tables. Let V∩ denote the set of hashed values that appear in both 𝑇1 and 𝑇2 . For each 𝑣 ∈ V∩ , we construct a value proxy ℎ 𝑣(𝑘 ) by mean pooling the embeddings of all cell nodes in 𝑇𝑘 whose value equals 𝑣. We then penalize the squared Euclidean Í discrepancy between the two proxies: Lval = 𝑣 ∈ V∩ ∥ℎ 𝑣(1) − ℎ 𝑣(2) ∥ 22 . This term encourages identical values to be encoded compatibly across tables despite differences in local neighborhoods. (iii) Context-Align. Value identity alone can be misleading when the same cell value appears in both tables but serves different roles. Context-Align therefore enforces role consistency by comparing each shared value’s relationship to the global table embedding. Let 𝑍 1 and 𝑍 2 be the global embeddings of 𝑇1 and 𝑇2 . For each 𝑣 ∈ V∩ , we compare the distance from the value proxy to the corresponding table embedding and penalize discrepancies: Lctx = Í (1) (2) 𝑣 ∈ V∩ ∥ℎ 𝑣 − 𝑍 1 ∥ 2 − ∥ℎ 𝑣 − 𝑍 2 ∥ 2 . Intuitively, truly overlapping cell values tend to occur in comparable contexts, so their distances to the corresponding global embeddings should be similar. When a shared value appears in mismatched contexts, these distances diverge. Thus, Context-Align penalizes the mismatch and discourages the model from over-relying on coincidental value matches that lack structural correspondence. Let LRC , Lval , and Lctx denote the three terms. Their combination is gated by the ground-truth overlap ratio using an alignment
row/column permutation, (ii) full row and column context per encoder layer, and (iii) invariance to bucket-index relabeling. We also summarize end-to-end inference time and space complexity.
6.1
Row/Column Permutation Invariance
Key Result. Our encoder matches the symmetry of the overlap definition. Reordering rows or columns only permutes cell-level representations, while the pooled table embedding and the final prediction remain unchanged. Let 𝑇 be a table with 𝑚 rows and 𝑛 columns. Let 𝜎 ∈ 𝑆𝑚 and 𝜌 ∈ 𝑆𝑛 be permutations of rows and columns, inducing a permutation of cell indices (𝑖, 𝑗) ↦→ (𝜎 (𝑖), 𝜌 ( 𝑗)). Let 𝑃𝜎,𝜌 be the corresponding permutation matrix acting on cell-node embeddings (ordered by any fixed enumeration of the 𝑚𝑛 cells). Let H (𝑇 ) = (V, Erow ∪Ecol ) be the Two-View Row–Column Hypergraph, where each cell is a node 𝑣𝑖,𝑗 ∈ V, each row is a hyperedge 𝑒𝑖𝑟 = {𝑣𝑖,1, . . . , 𝑣𝑖,𝑛 }, and each column is a hyperedge 𝑒 𝑐𝑗 = {𝑣 1,𝑗 , . . . , 𝑣𝑚,𝑗 }. Assumption 1 (Permutation-equivariant message passing). In each Dual Hyperedge Convolution layer, the row-view and columnview hypergraph convolutions aggregate within row and column hyperedges using a symmetric function (sum) and apply the same node-wise transform to every node. Global pooling is sum over cell nodes. Theorem 1 (Encoder Eqivariance). Let 𝐻 (𝑙 ) (𝑇 ) ∈ R | V | ×𝑑 be the node embedding matrix after 𝑙 Dual Hyperedge Convolution layers. Under Assumption 1 and value features that depend only on cell contents, for any 𝜎, 𝜌, 𝐻 (𝑙 ) (𝑇 𝜎,𝜌 ) = 𝑃𝜎,𝜌 𝐻 (𝑙 ) (𝑇 ) for all 𝑙 = {0, . . . , 𝐿}.
𝛾
−𝜅 gating threshold 𝜅 ∈ [0, 1): 𝑊gate = max 0, 𝜃1−𝜅 , and Lalign = 𝑊gate (𝜆RC LRC + 𝜆val Lval + 𝜆ctx Lctx ). Pairs with small true overlap (i.e., 𝜃 < 𝜅) do not contribute to alignment, preventing the model from forcing alignments where none exist (lines 13–19).
Consistency Regularizer. The consistency regularizer enforces stability under stochastic value permutations [46, 54]. For each batch, the model performs two forward passes with independently sampled permutations in the domain-robust value mapping (lines 7– 11). This results in two predictions 𝜃ˆ1 and 𝜃ˆ2 . The regularizer is Lcons = ∥𝜃ˆ1 − 𝜃ˆ2 ∥ 22 . This term encourages the prediction to focus on value equality, instead of particular embedding index permutation and corpus-specific distributions (line 20). Total Objective. The final training loss is a weighted sum Ltotal = Lmain + Lalign + 𝜆cons Lcons . The alignment and consistency terms are omitted at inference for efficiency (line 21). Complexity. The overlap regression loss is negligible compared to encoding. The alignment regularizer adds a term that is O ((𝑚 2 + 𝑛 2 )𝑑) per pair due to soft row and column alignments. However, this is evaluated only during training and on tables with modest sizes. The consistency regularizer requires an additional forward pass per batch during training. At inference time, since both regularizers are disabled, the prediction cost is identical to a single forward pass of the encoder and overlap fusion head.
6
Theoretical Analysis
In this section, we show that ALORE is aligned with the symmetries and structure of table overlap. We establish (i) invariance to
Proof. We prove the claim by induction on 𝑙. Base case 𝑙 = 0. Node features are computed from cell values only (hashing and embedding lookup). Permuting rows and columns reorders the cells but does not change their values. Therefore, the initial node feature matrix satisfies 𝐻 (0) (𝑇 𝜎,𝜌 ) = 𝑃𝜎,𝜌 𝐻 (0) (𝑇 ). Inductive step. Assume 𝐻 (𝑙 −1) (𝑇 𝜎,𝜌 ) = 𝑃𝜎,𝜌 𝐻 (𝑙 −1) (𝑇 ). Consider the row-view HConv at layer 𝑙. Each node update is formed by aggregating messages from the row hyperedge and applying nodewise transforms. Under the permutation (𝜎, 𝜌), the row hyperedges are relabeled, and the multiset of node embeddings inside each hyperedge is permuted. By Assumption 1, the hyperedge aggregation result is unchanged up to the same node reordering 𝑃𝜎,𝜌 . The same holds for the node aggregation over incident hyperedges. All subsequent transforms are applied node-wise and thus commute with 𝑃𝜎,𝜌 . Hence, the row-view output satisfies (𝑙 ) (𝑙 ) 𝐻 row (𝑇 𝜎,𝜌 ) = 𝑃𝜎,𝜌 𝐻 row (𝑇 ). The argument for the column-view out(𝑙 ) (𝑙 ) (𝑙 ) put 𝐻 col is identical. Concatenation [𝐻 row ∥ 𝐻 col ], followed by Linear, LayerNorm and ReLU, preserves equivariance because these operations are applied per node. Therefore, 𝐻 (𝑙 ) (𝑇 𝜎,𝜌 ) = 𝑃𝜎,𝜌 𝐻 (𝑙 ) (𝑇 ). This completes the induction. □ Theorem 2 (Table Embedding Invariance). Let 𝑍 (𝑇 ) be the table embedding obtained by pooling and concatenating layer-wise readouts, followed by LayerNorm. Under Assumption 1, for any 𝜎, 𝜌, 𝑍 (𝑇 𝜎,𝜌 ) = 𝑍 (𝑇 ). Proof. We fix any layer 𝑙. The pooled readout has the form 𝑧 (𝑙 ) = MLPout (Pool(MLPin (𝐻 (𝑙 ) ))), where Pool is sum or mean over nodes. By Theorem 1, 𝐻 (𝑙 ) (𝑇 𝜎,𝜌 ) = 𝑃𝜎,𝜌 𝐻 (𝑙 ) (𝑇 ). Node-wise
Alignment-Guided Largest Table Overlap Size Estimation
MLPs commute with 𝑃𝜎,𝜌 . Symmetric pooling satisfies Pool(𝑃𝜎,𝜌 𝑋 ) = Pool(𝑋 ). Hence, 𝑧 (𝑙 ) (𝑇 𝜎,𝜌 ) = 𝑧 (𝑙 ) (𝑇 ) for every 𝑙. Concatenation over 𝑙 and LayerNorm on the resulting vector preserve equality. □
Proof. Let 𝑋 = 𝑦ˆ𝜋 and 𝑌 = 𝑦ˆ𝜋 ′ . Since 𝑋 and 𝑌 are i.i.d., E[(𝑋 − 𝑌 ) 2 ] = E[𝑋 2 ] + E[𝑌 2 ] − 2E[𝑋 ]E[𝑌 ] = 2(E[𝑋 2 ] − (E[𝑋 ]) 2 ) = 2 Var(𝑋 ). □
Since our inter-table interaction features 𝑆 and 𝐽 are also invariant to row/column reorderings, the full predictor 𝜃ˆ(𝑇1,𝑇2 ) is invariant to independent permutations applied to 𝑇1 and 𝑇2 .
Therefore, minimizing the consistency loss directly suppresses Var𝜋 [𝑦ˆ𝜋 ], making predictions insensitive to the particular bucket indices assigned to values. Intuitively, because bucket identities are randomized across training steps, the model cannot attach stable semantics to any specific index and is pushed to rely on indexinvariant signals.
6.2
Full Row/Column Context per Layer
Key Result. A single dual row–column hypergraph convolution layer lets each cell aggregate from all cells in both its row and column. This yields full row and column context per layer without multi-hop message passing through explicit row/column nodes. Consider the row view. Let |𝑇 | = 𝑚𝑛 be the number of cells. Let 𝐻𝑟 ∈ {0, 1} |𝑇 | ×𝑚 be the cell-row incidence matrix, where (𝐻𝑟 )𝑣,𝑖 = 1 iff cell-node 𝑣 belongs to row 𝑖. We define 𝐷 𝑣 and 𝐷𝑒 as the diagonal degree matrices of nodes and hyperedges in the incidence bipartite graph. A standard mean aggregation hypergraph propagation can be written as 𝑋 ′ = 𝐷 𝑣−1 𝐻𝑟 𝐷𝑒−1 𝐻𝑟⊤𝑋𝑊 , for node embedding matrix 𝑋 ∈ R |𝑇 | ×𝑑 and a learnable linear map 𝑊 . The column view uses the analogous incidence matrix 𝐻𝑐 . Proposition 3 (Two-Hop Eqivalence). Let B𝑟 be the bipartite incidence graph between cell nodes and row-hyperedge nodes. The linear operator 𝐻𝑟 𝐷𝑒−1 𝐻𝑟⊤ aggregates information along length-2 walks in B𝑟 (cell → row → cell). Therefore, one row-HConv updates each cell using information from all cells in its row in a single layer. The same holds for the column view.
6.4
7 Proof. A length-2 walk in B𝑟 from a cell node 𝑢 to a cell node 𝑣 exists iff 𝑢 and 𝑣 share a row hyperedge. The matrix 𝐻𝑟 𝐻𝑟⊤ has (𝑢, 𝑣) entry equal to the number of shared incident row hyperedges, which is 1 if 𝑢 and 𝑣 are in the same row and 0 otherwise. Multiplication by 𝐻𝑟 𝐷𝑒−1 𝐻𝑟⊤ therefore computes a degree normalized sum or mean over cells in the same row. □ Thus, a dual row–column layer provides full receptive fields for both row and column contexts in one encoder layer.
6.3
Index Relabeling Invariance
Key Result. The stochastic bucket-index permutation and the consistency regularizer make the predictor insensitive to the arbitrary identities of bucket indices. The consistency loss equals twice the prediction variance over index relabelings, and minimizing it drives invariance to bucket-index permutations. Stochastic relabeling. Each value is hashed and bucketized to an index in {0, . . . , 𝐵 − 1}. During training, we sample a random permutation 𝜋 ∈ 𝑆 𝐵 and perform embedding lookup using 𝜋 (idx). For a fixed table pair (𝑇1,𝑇2 ), we define the prediction under 𝜋 as 𝑦ˆ𝜋 = 𝑓Θ (𝜋 ◦ idx(𝑇1 ), 𝜋 ◦ idx(𝑇2 )). The Consistency Regularizer samples 𝜋, 𝜋 ′ independently and penalizes (𝑦ˆ𝜋 − 𝑦ˆ𝜋 ′ ) 2 . Theorem 4 (Consistency loss eqals prediction variance over index relabelings). For any fixed input pair (𝑇1,𝑇2 ), with 𝜋, 𝜋 ′ sampled independently and uniformly from 𝑆 𝐵 , E𝜋,𝜋 ′ [(𝑦ˆ𝜋 − 𝑦ˆ𝜋 ′ ) 2 ] = 2Var𝜋 [𝑦ˆ𝜋 ].
End-to-End Complexity
We analyze the end-to-end cost of a deployed estimation from raw tables to predicted overlap ratio 𝜃ˆ. Encoding a table 𝑇 with 𝑚 rows, 𝑛 columns, and |𝑇 | = 𝑚𝑛 cells costs O (𝐿|𝑇 |𝑑) time and O (|𝑇 |𝑑) space, dominated by the Row–Column Hypergraph Encoder. For a table pair (𝑇1, 𝑇2 ), interaction feature computation is linear in |𝑇1 | + |𝑇2 |, and the overlap fusion head with overlap ratio regressor are O (𝑑) in the embedding dimension and independent of table size. Thus, for fixed 𝐿 and 𝑑, ALORE achieves linear encoding and pairwise inference, matching the asymptotic behavior of Armadillo, while avoiding exponential search over row and column permutations in Sloth. The alignment and consistency regularizers are used only during training. Hence, inference retains the same linear time as a standard bi-encoder, making ALORE suitable for large-scale discovery and matching workloads over millions of tables.
Experiments
This section presents a comprehensive evaluation of our proposed method. We begin by outlining the experimental setup (Section 7.1). We then study effectiveness in three settings: accuracy of overlap ratio estimation (Section 7.2), domain-robust generalization (Section 7.3), and query-by-table retrieval using overlap ratio estimates (Section 7.4). Finally, we report efficiency (Section 7.5) and ablations of key components (Section 7.6).
7.1
Experimental Setup
Datasets. We evaluate on three datasets. Two are benchmark corpora released by Armadillo [43]: Wiki and Git. They are derived from the Wikipedia table corpus [6, 7] and GitHub repositories [26], containing 128 620 and 256 834 tables, respectively. We use the provided pairs and splits: Wiki has 500k/60k/60k train/validation/test pairs, and Git has 500k/100k/100k. In both datasets, pairs are balanced across ten overlap-ratio bins ∈ [0, 1]. The third is RealEstate, derived from 2.1 million property records collected over time [32], containing 20 000 tables and 10 000 evaluation pairs. These datasets differ in both table scale and value distributions. Figure 3 shows the distributions of table dimensions: Wiki and Git consist of small-to-medium web tables, while RealEstate lies at a much larger scale, with orders-of-magnitude larger areas. Table 1 profiles cell values at the table level for each dataset. The profiles show clear domain differences: Wiki has the highest value diversity and is mostly textual, Git contains substantially more floating-point values than the others, and RealEstate has the lowest value diversity with lower variation across tables. We include RealEstate as a
Ge Lee, Shixun Huang, Zhifeng Bao, Shazia Sadiq, and Yanchang Zhao Wiki
CDF (Proportion)
1.0
Row Count Distribution
Git
RealEstate
Column Count Distribution
Table 2: MAE (↓) for overlap ratio estimation. Dark blue and light blue highlight the best and second-best performers. “oot” indicates out of time.
Area Distribution
0.8 0.6
Method
Wiki
Git
0.223 0.231 0.278 0.115 ± 0.0027 0.097 ± 0.0049 0.207 ± 0.0009 0.135 ± 0.0045 0.101 ± 0.0042 0.229 ± 0.0637 0.199 ± 0.0035 0.372 ± 0.0002 0.069 ± 0.0006 0.040 ± 0.0018
0.151 0.157 0.173 0.269 ± 0.0115 0.127 ± 0.0036 0.163 ± 0.0035 0.225 ± 0.0185 0.128 ± 0.0058 0.137 ± 0.0007 0.275 ± 0.0117 oot 0.066 ± 0.0011 0.030 ± 0.0004
0.4
Jaccard Jaccard-BU Jaccard-BN BERT-R BERT-T BERT-HT RoBERTa-R RoBERTa-T RoBERTa-HT TURL EmbDI Armadillo ALORE
0.2 0.0 0 10
10
1
10
2
10
3
10
4
Number of Rows
10
0
10
1
10
2
10
3
10
4
Number of Columns
10
0
10
1
10
2
10
3
10
4
Table Area (Rows × Cols)
Figure 3: Cumulative distribution function of table dimensions across the three datasets.
Table 1: Profiles of cell-value distributions across the three datasets. “Distinct” is the fraction of distinct values among non-missing cells. “Missing”, “Text”, “Int”, and “Float” are fractions over all cells in the table. Each entry reports the mean and standard deviation of these per-table percentages within each dataset. Value Profile
Value Type
Dataset
Wiki Git RealEstate
• Armadillo [43] embeds each table as a tripartite graph using GraphSAGE and estimates overlap via cosine similarity. • ALORE is our alignment-guided overlap ratio estimator.
Distinct
Missing
Text
Int
Float
65.5 ± 24.7 51.0 ± 24.4 37.1 ± 12.1
7.3 ± 14.8 11.4 ± 14.8 12.0 ± 6.4
56.4 ± 29.6 41.0 ± 26.3 50.7 ± 11.3
35.2 ± 30.6 32.3 ± 24.1 26.6 ± 8.8
1.0 ± 4.3 15.2 ± 18.4 10.8 ± 5.1
zero-shot target to evaluate transfer beyond the two prior benchmark corpora, and describe its pairing procedure in Section 7.3. We exclude RealEstate from training due to the substantial overhead of training on much larger tables. Methods for Comparison. We compare ALORE with the state of the art, Armadillo [43], and its baselines, including exact and heuristic methods (Sloth, Jaccard) and learned table embedding models (BERT, RoBERTa, TURL, EmbDI, Armadillo). We exclude LLM baselines because table serialization makes inference prohibitively expensive at our scale, and they do not naturally capture the injective row–column alignments that define overlap. • Sloth [58] computes ground-truth overlap ratios. We run its exact solver with a 60 s timeout and fall back to the greedy approximation on timeout. • Jaccard variants measure value-level overlap between tables 𝑇1 and 𝑇2 . Let S(𝑇 ) be the set of distinct cell values in 𝑇 , and let B (𝑇 ) be the multiset of values including duplicates. We 1 )∩S (𝑇2 ) | report: (i) set-based Jaccard: || SS (𝑇 (𝑇1 )∪S (𝑇2 ) | , (ii) bag-union vari)∩B (𝑇2 ) | ant (-BU): |2|BB(𝑇(𝑇1 )1 |+| B (𝑇2 ) | , and (iii) bag-normalized variant (-BN): | B (𝑇1 )∩B (𝑇2 ) | min( |𝑇1 |,|𝑇2 | ) .
• BERT/RoBERTa [15, 35] are adapted via table-to-text serialization, each with three variants: (i) Row (-R) encodes each row as a sentence by concatenating cell values, then averages row embeddings to form a table vector; (ii) Table (-T) serializes the entire table into a single text sequence by joining rows and averages token embeddings; and (iii) Hashed-Table (-HT) applies the Table variant after replacing each cell value with its SHA-256 hash. • TURL [14] learns contextualized cell representations via a cellfilling objective and averages them into a table embedding. • EmbDI [11] adapts node2vec [24] to a tripartite graph. Its table representations are pair-dependent and cannot be precomputed.
Evaluation Metrics. For pairwise prediction, we report mean absolute error (MAE) between predicted and ground-truth overlap ratio. For retrieval, we rank candidate tables by predicted overlap ratio and report nDCG@𝑘 [28]. For threshold-based filtering, we vary the overlap ratio threshold 𝜏 and treat a candidate as relevant if its ground-truth overlap ratio satisfies 𝜃 ≥ 𝜏. We report Selection Rate (proportion of tables returned), Recall, Precision, and F1. These metrics match those in Armadillo [43]. Specifically, Selection Rate is the complement of the Reduction Ratio, and Recall is equivalent to Pair Completeness [18, 38]. Throughout the paper, ↓ indicates that lower values are better and ↑ indicates that higher values are better. We repeat each learning-based experiment five times with different random seeds and report mean ± standard deviation. Training Details. ALORE is optimized using Adam with a learning rate of 10−3 . We train for up to 100 epochs with early stopping, using batch sizes of 512 on Wiki and 64 on Git. On a single GPU, training takes 30 hours on Wiki and 92 hours on Git. We set hash bucket size 𝐵 = 2 × 106 with embedding dimension of 𝑑 = 256. The model uses 𝐿 = 2 layers and a hidden dimension of 𝑑ℎ = 64. We minimize MAE with alignment regularization (𝜆RC = 0.1, 𝜆val = 0.05, 𝜆ctx = 0.05) and consistency regularization (𝜆cons = 1.0). For all learning-based baselines, we follow the training configuration described in [43]. Implementation. All experiments were conducted on a Linux server with Intel Xeon E5 CPUs (56 cores), 512 GB of RAM and an NVIDIA Tesla P100 GPU (16 GB VRAM). The implementation, developed in Python and PyTorch, is available at [1].
7.2
Accuracy of Overlap Ratio Estimation
We first evaluate how accurately each method estimates overlap ratios between individual pairs of tables using the MAE. All methods are tested on held-out pairs from the same dataset. For learningbased approaches, models are trained and tested on disjoint splits, while non-learning baselines are directly applied to the same test pairs for comparability. Table 2 shows that ALORE achieves the lowest MAE on both datasets. EmbDI exceeds the runtime of the exact solver on Git and is therefore marked as “oot”. ALORE improves over Armadillo
Alignment-Guided Largest Table Overlap Size Estimation
Jaccard
RoBERTa-T
TURL
Armadillo
Wiki
ALORE
Git
0.5
Table 3: MAE (↓) for cross-domain evaluation. Results are grouped by target domain (test set) for models trained on different source domains (training set).
MAE
0.4 0.3 0.1 0.0
.2 .3 .4 .5 .6 .7 .8 .9 .0 .1 .2 .3 .4 .5 .6 .7 .8 .9 .0 .1 0-0 0.1-0 0.2-0 0.3-0 0.4-0 0.5-0 0.6-0 0.7-0 0.8-0 0.9-1 0-0 0.1-0 0.2-0 0.3-0 0.4-0 0.5-0 0.6-0 0.7-0 0.8-0 0.9-1
Figure 4: MAE (↓) of overlap ratio estimation across different ranges of overlap ratio 𝜃 . from 0.069 to 0.040 on Wiki and from 0.066 to 0.030 on Git, indicating that the gain is not limited to a single corpus. Compared with set-based baselines, Jaccard remains competitive on Git but degrades substantially on Wiki, where ignoring row–column structure leads to large errors. Transformer-based table embeddings (e.g., BERT-T/RoBERTa-T/TURL) provide mixed benefits and are less reliable across datasets, suggesting that semantic priors are not consistently aligned with the strictly equality-based overlap definition. Figure 4 further breaks down MAE by overlap ratio interval. The largest gaps appear in the low-to-mid overlap range, where accurate estimation requires recovering partial row–column correspondences rather than detecting near-duplicates. In these intervals, ALORE consistently achieves the lowest error on both Wiki and Git. As 𝜃 approaches 1, all methods improve because highly overlapping pairs are closer to duplication and are easier to distinguish.
7.3
Target: Wiki
Target: Git
Source: Git
Source: Wiki
Source: Wiki
Target: RealEstate Source: Git
0.362 ± 0.0013 0.306 ± 0.0018 0.294 ± 0.0019 0.354 ± 0.0011 0.319 ± 0.0023 0.305 ± 0.0009 0.354 ± 0.0065 0.211 ± 0.0116 0.208 ± 0.0101
0.395 ± 0.0007 0.296 ± 0.0018 0.304 ± 0.0022 0.392 ± 0.0022 0.300 ± 0.0027 0.328 ± 0.0576 0.320 ± 0.0019 0.247 ± 0.0092 0.154 ± 0.0148
0.470 ± 0.0001 0.297 ± 0.0037 0.244 ± 0.0114 0.467 ± 0.0002 0.290 ± 0.0020 0.251 ± 0.0194 0.241 ± 0.0009 0.465 ± 0.0022 0.183 ± 0.0345
0.471 ± 0.0001 0.331 ± 0.0035 0.266 ± 0.0106 0.467 ± 0.0004 0.271 ± 0.0029 0.293 ± 0.0144 0.265 ± 0.0025 0.462 ± 0.0120 0.144 ± 0.0315
Method
0.2
Domain-Robust Generalization
To assess generalization, learning-based methods are trained on one dataset and evaluated on another. This is a strict zero-shot setting where no target-domain fine-tuning is performed. Beyond Wiki and Git, we include RealEstate as a target domain with different value distributions and much larger tables (Table 1 and Figure 3). RealEstate is derived from 2.1 million property sale records: each table is a time-bounded transaction snapshot, where rows are properties and columns include address, sale date, and price. We form pairs by sampling two snapshots that partially share properties, simulating integration or deduplication across extracts (e.g., different months). For shared properties, attributes like sale date and price may differ due to repeated sales and evolving listings, yielding partial overlaps between snapshots. We construct 10 000 such pairs from 20 000 tables. The RealEstate dataset is available at [1]. Table 3 shows that ALORE transfers more reliably than other methods across the evaluated source–target domain pairs. Relative to Armadillo, ALORE yields consistent improvements across all source–target pairs, with the largest gains on RealEstate as the target domain (up to 69%) and a substantial improvement for Wiki→Git (38%). Notably, ALORE remains strong when transferring from a smaller source domain to a larger or more heterogeneous target, including Wiki→Git/RealEstate and Git→RealEstate. In contrast, semantic table encoders are inconsistent across targets. TURL is competitive on RealEstate but still trails ALORE. Overall, these results match our design goal of domain robustness. By avoiding reliance on corpus-specific value identities and emphasizing
BERT-R BERT-T BERT-HT RoBERTa-R RoBERTa-T RoBERTa-HT TURL Armadillo ALORE
Table 4: Ranking performance on Git-Query measured by nDCG@k (↑). Method
nDCG@1
nDCG@10
nDCG@50
nDCG@100
Jaccard Jaccard-BU Jaccard-BN BERT-R BERT-T BERT-HT RoBERTa-R RoBERTa-T RoBERTa-HT TURL Armadillo ALORE
0.858 0.839 0.782 0.809 ± 0.003 0.796 ± 0.004 0.698 ± 0.009 0.803 ± 0.007 0.817 ± 0.003 0.701 ± 0.005 0.719 ± 0.007 0.765 ± 0.014 0.881 ± 0.006
0.811 0.813 0.821 0.761 ± 0.004 0.760 ± 0.002 0.680 ± 0.003 0.762 ± 0.004 0.763 ± 0.002 0.681 ± 0.003 0.709 ± 0.004 0.732 ± 0.003 0.870 ± 0.004
0.807 0.808 0.853 0.719 ± 0.008 0.749 ± 0.001 0.694 ± 0.003 0.729 ± 0.004 0.735 ± 0.004 0.695 ± 0.002 0.693 ± 0.003 0.708 ± 0.005 0.878 ± 0.004
0.790 0.794 0.861 0.680 ± 0.012 0.716 ± 0.002 0.672 ± 0.003 0.695 ± 0.004 0.702 ± 0.005 0.680 ± 0.002 0.672 ± 0.004 0.675 ± 0.008 0.862 ± 0.003
permutation-invariant structural signals, ALORE better preserves accuracy under the evaluated zero-shot domain shifts.
7.4
Query-by-Table Retrieval
We evaluate how overlap ratio estimation supports retrieval over a large table repository. This setting corresponds to the table querying scenario in [43], where given a query table, the system retrieves overlapping tables either by ranking candidates (Section 7.4.1) or by filtering with an overlap threshold (Section 7.4.2). Setup. The setting consists of a repository of 10 000 tables and a query set of 100 tables, sampled from the test split of Git [43] (we denote this benchmark as Git-Query). For each query, each method predicts overlap ratios for all 10 000 candidates and ranks them by the predicted scores. The data are highly skewed, where most query– candidate pairs have near-zero overlap, with only a small fraction exhibiting moderate-to-high overlap (distributions are plotted in Appendix A.1). As a result, retrieval quality depends on separating a few truly overlapping tables from many near-zero candidates. We also evaluate on the TP-TR (small) benchmark [20]: the query set contains 26 TP-TR tables, and the candidate set consists of Wiki plus another 32 TP-TR tables. The results are deferred to Appendix A.2. 7.4.1 Ranking evaluation. We measure ranking quality using nDCG at cutoff 𝑘 [28], which evaluates how well the predicted ranking matches the ideal ranking at the top of the list. Table 4 reports nDCG at multiple cutoffs 𝑘. Small 𝑘 is included because the query– candidate overlap distribution is highly skewed, as shown in Appendix Figure 7, and top-ranked results are the main focus in practice.
Ge Lee, Shixun Huang, Zhifeng Bao, Shazia Sadiq, and Yanchang Zhao
3
0.6
0.7
0.8
0.9
0.0
0.2 0.6
0.7
0.8
0.9
0.0
0.2 0.6
0.7
0.8
0.9
0.0
2
10
1
10
0
10
1
10
2
0.6
0.7
0.8
0.9
Figure 5: Threshold-based retrieval performance on GitQuery across overlap ratio thresholds 𝜏. We report Selection Rate (↓), Recall (↑), Precision (↑), and F1 Score (↑). Overall, ALORE achieves the best ranking quality across all 𝑘, indicating that it more effectively promotes truly high-overlap tables to the top. Simple Jaccard variants are strong baselines, consistent with prior observations that many high-overlap cases correspond to duplicate or containment relationships where structural modeling is less critical than capturing shared values [43]. Despite this, ALORE still improves the top-𝑘 ordering, suggesting that its structure-aware encoding and alignment-guided training better resolve the fine-grained score differences that matter for retrieval. 7.4.2 Threshold-based retrieval. Beyond ranking, many pipelines require filtering candidates by a minimum overlap to obtain a small, high-quality candidate subset. This candidate subset can then be passed to expensive downstream processing such as exact overlap computation [58], table reclamation [20], related table discovery [47], or deduplication [31]. We therefore also report threshold-based retrieval curves (Figure 5) by varying the overlap threshold 𝜏 and measuring how effectively each method prunes the candidate set while retaining tables with 𝜃 ≥ 𝜏. We focus on 𝜏 ∈ {0.6, 0.7, 0.8, 0.9} because (i) most query-candidate pairs have small overlaps (Figure 7), where low thresholds make filtering less discriminative; and (ii) practical use cases emphasize highly overlapping tables, where compact high-overlap candidate subsets reduce verification cost and user effort. Across all thresholds, ALORE achieves the lowest selection rate, returning the smallest candidate subset per query. It also consistently attains the highest precision for every 𝜏 and the best F1 for 𝜏 ∈ {0.6, 0.7, 0.8}, demonstrating a strong effectiveness–cost trade-off. The baselines achieve higher recall by selecting larger candidate subsets, but this comes with correspondingly lower precision, which increases downstream cost. Thus, Figure 5 should be interpreted as a trade-off among selection rate, recall, and precision in threshold-based retrieval. ALORE is most suitable when downstream cost favors compact and precise candidate sets, whereas recall-first blocking pipelines may prefer a less selective method such as Armadillo. This trade-off can occur despite ALORE’s strong overall estimation accuracy because hard-threshold filtering is sensitive to score calibration near the cutoff 𝜏. Small underestimation around the threshold can turn relevant tables into false negatives. Thus, low global regression error does not necessarily imply the highest recall at every threshold. Adapting ALORE for recall-first filtering would require less selective filtering near the cutoff, for example by favoring recall in threshold tuning or by adding a stronger penalty
OOT
0.4
3
10
RE
0.2 10
0.4
0.6
4
10
RealEstate
S Ja Jac loth c c Ja card ard cc -B ard U BE -BN B RTB ER R Ro ER T-T B T Ro ER -HT Ro BE Ta-R BE RT RT a-T aTUHT E R Ar mb L m DI ALadillo O
0.4
0.6
10
Git
RE
0.6
5
OOT
0.8
6
10
RE
0.8
10
S Ja Jac loth c c Ja card ard cc -B ar U BEd-BN B RTBEERT R Ro R -T B T R ER -HT Ro oBE Ta-R BE RT RT a-T aTUHT E R Ar mb L m DI ALadillo O
0.8
Total Runtime (s)
1.0
Wiki
ALORE
Armadillo
S Ja Jac loth c c Ja card ard cc -B ar U BEd-BN B RTBEERT R Ro R -T B T R ER -HT Ro oBE Ta-R BE RT RT a-T aTUHT E R Ar mb L ma DI AL dillo O
2
TURL 1.0
F1 Score
10
BERT-T 1.0
Precision
10
Recall
Selection Rate (log)
Jaccard-BN 1
Figure 6: End-to-end runtime summed over all pairs in seconds (↓). Sloth exact times out on 15% (Wiki), 28% (Git), and 1.3% (RealEstate) of pairs and falls back to greedy.
Table 5: Mean runtime breakdown in milliseconds (↓). Graph construction (Graph) and embedding generation (Embed) are averaged per table. Inference (Infer) is averaged per pair. Wiki
RealEstate†
Git
Method Graph Embed Infer
Graph Embed
Infer
Graph Embed Infer
Sloth – – 919.76 – – 1 905.39 – – 3 646.46 Jaccard – – 0.08 – – 0.77 – – 21.92 Jaccard-BU – – 0.27 – – 33.35 – – 2 774.64 Jaccard-BN – – 0.27 – – 33.35 – – 2 774.64 BERT-R – 127.7 0.13 – 668.6 0.14 – 2 541.9 0.19 BERT-T – 14.5 0.13 – 76.6 0.13 – 189.3 0.19 BERT-HT – 97.2 0.13 – 701.6 0.14 – 3 566.0 0.20 RoBERTa-R – 146.9 0.13 – 643.5 0.14 – 2 566.6 0.21 RoBERTa-T – 13.2 0.13 – 48.9 0.14 – 150.6 0.20 RoBERTa-HT – 49.0 0.13 – 154.8 0.14 – 711.0 0.19 TURL – 30.9 0.13 – 1 876.9 0.13 – 11.9 0.34 EmbDI 388.6 2 149.5 0.17 oot oot oot oot oot oot Armadillo 7.3 1.3 0.10 173.2 1.1 0.11 5 666 12.0 0.13 ALORE 1.7 5.0 0.07 28.4 3.5 0.06 53 11.0 0.11 † All learning models evaluated on RealEstate are trained on Git.
for false negatives near the target threshold. This limitation is specific to hard-threshold filtering. For ranking-based retrieval, ALORE remains strong and achieves the best ranking quality across all 𝑘. At 𝜏 = 0.9, Jaccard-BN achieves slightly higher F1, consistent with prior observations that these high-overlap pairs are near duplicates where shared values alone provide a strong signal [43]. However, it does so by returning a much larger subset (an order of magnitude larger than ALORE), whereas ALORE remains more cost-effective by keeping the subset compact.
7.5
Efficiency Analysis
Figure 6 shows the total end-to-end runtime (log scale) summed over all test pairs. ALORE is up to 89× faster than the state-of-the-art learning-based estimator Armadillo. Across all datasets, ALORE is consistently faster than learning-based methods, with orders of magnitude gains over several baselines. For Sloth, we set a longer timeout for the exact solver than the default (60 s vs. 3 s). Even with this larger budget, the exact phase times out on 15% of Wiki pairs, 28% of Git pairs and 1.3% of RealEstate pairs, triggering the greedy approximation. Table 5 decomposes the end-to-end runtime into three components: (i) graph/hypergraph construction, (ii) embedding generation, and (iii) inference. They are reported as averages per pair and per table. For embedding-based methods, graph/hypergraph construction and embedding generation can be precomputed once per table and reused across many pair queries. The breakdown
Alignment-Guided Largest Table Overlap Size Estimation
shows that embedding generation dominates the cost of learningbased baselines, while graph construction becomes the primary bottleneck for Armadillo due to its tripartite graph with explicit row, column, and cell nodes. By contrast, ALORE maintains low cost in both graph construction and embedding generation, reflecting the linear-time Two-View Row–Column Hypergraph construction and the scalable Row–Column Hypergraph Encoder. Inference cost is negligible for all learning-based methods, and ALORE incurs the smallest overhead since prediction reduces to a compact fusion head over fixed-size representations.
7.6
Ablation Study
We ablate major components of ALORE while training on Wiki and evaluating on Wiki (in-domain) and on Git/RealEstate (crossdomain). Table 6 shows that most removals increase MAE, with several effects more pronounced on cross-domain targets. Removing inter-table interaction feature 𝐼 = [𝑆 ∥ 𝐽 ] degrades performance most strongly on RealEstate, from 0.183 to 0.304, showing that these coarse pairwise features are useful under stronger domain shift. However, the interaction-only variant, which uses only 𝐼 without the structural encoder, performs much worse than both the full model and the no-interaction variant, reaching 0.242 on Git and 0.332 on RealEstate. Thus, inter-table interaction feature 𝐼 acts as a useful calibration signal rather than a shortcut. It complements the learned structural representation with coarse value-overlap and size–shape signals for the final predictor, but it is not sufficient without the structure-aware encoder, alignment-guided training, and domain-robust value mapping. We further decompose 𝐼 to examine which interaction signal contributes more. Within 𝐼 , removing the Jaccard anchor 𝐽 has a larger effect than removing size–shape features 𝑆, especially on Git and RealEstate. For the encoder, both row and column hyperedges contribute, while removing the multi-scale readout is the most detrimental encoder ablation on RealEstate. Regarding alignment, removing the regularizer Lalign increases MAE on all targets, with Context-Align Lctx showing the largest impact on RealEstate. Similarly, removing the consistency regularizer Lcons worsens cross-domain performance, notably on RealEstate. Finally, disabling stochastic permutations 𝜋 improves Wiki but worsens Git and RealEstate, indicating a trade-off between in-domain fit and cross-domain robustness.
8
Related Work
Table Overlap. The closest work to ours is Armadillo [43], which embeds each table as a graph and estimates overlap ratio through embedding similarity. Our work follows the same overlap definition, but develops an estimator that more directly models inter-table row/column interactions that determine overlap ratio. The overlap definition is formalized by Sloth [58], which defines the largest overlap through an attribute mapping between column subsets and measures overlap as the area of the induced common subtable. Sloth provides exact and greedy algorithms, but its combinatorial search is expensive at scale, which motivates overlap ratio estimation. Other related work studies duplicate tables across Wikipedia snapshots to track table evolution [7] and lake deduplication under exact match and containment [31].
Table 6: Ablation study of ALORE trained on Wiki, in MAE (↓). Method
Target: Wiki Target: Git Target: RealEst Source: Wiki Source: Wiki Source: Wiki
ALORE (Full model)
0.040 ± 0.0018
0.154 ± 0.0148
0.183 ± 0.0345
Inter-Table Interaction No interaction 𝐼 No size-shape 𝑆 No Jaccard 𝐽 Only interaction 𝐼
0.064 ± 0.0026 0.057 ± 0.0018 0.058 ± 0.0020 0.074 ± 0.0029
0.190 ± 0.0040 0.174 ± 0.0010 0.183 ± 0.0171 0.242 ± 0.0192
0.304 ± 0.0266 0.204 ± 0.0167 0.222 ± 0.0087 0.332 ± 0.0954
Hypergraph & Encoder No column hyperedges Ecol No row hyperedges Erow No multi-scale readout†
0.056 ± 0.0035 0.053 ± 0.0009 0.062 ± 0.0027
0.206 ± 0.0084 0.172 ± 0.0220 0.195 ± 0.0131
0.220 ± 0.0724 0.201 ± 0.0699 0.259 ± 0.0362
Inter-Table Alignment No alignment regularizer Lalign No RowColumn-Align LRC No Value-Align Lval No Context-Align Lctx No gating 𝑊gate
0.057 ± 0.0026 0.051 ± 0.0012 0.051 ± 0.0008 0.047 ± 0.0008 0.053 ± 0.0019
0.168 ± 0.0282 0.161 ± 0.0023 0.168 ± 0.0068 0.163 ± 0.0055 0.158 ± 0.0082
0.210 ± 0.0859 0.211 ± 0.1333 0.193 ± 0.0301 0.239 ± 0.0560 0.295 ± 0.1555
Domain Robustness No consistency regularizer Lcons 0.052 ± 0.0034 0.036 ± 0.0001 No permutation 𝜋 (and Lcons )
0.169 ± 0.0139 0.179 ± 0.0262
0.223 ± 0.0071 0.256 ± 0.0281
† No multi-scale readout uses only the last layer pooled embedding 𝑧 (𝐿) .
Table Representation Learning. Table encoders have been widely studied for table understanding, search, and similarity. Transformerbased models such as TaBERT [57] and TURL [14] learn contextualized representations for tabular content. Structure-aware methods incorporate row/column structure, such as StruBERT [49] and the hypergraph-enhanced tabular language model HyTrel [12]. EmbDI [11] learns graph embeddings from relational data for integration tasks. These methods target general purpose semantic representations, whereas we tailor representations and objectives to overlap ratio estimation with inter-table alignment signals and row/column permutation invariances. Schema Matching and Entity Resolution. Schema matching aligns semantically equivalent attributes across tables [4, 16, 36], while entity resolution matches tuples referring to the same realworld entity [52, 53]. Both typically rely on schema metadata, entity features, domain knowledge, or textual semantics, and their outputs are matchings over attributes or entities. Our task instead predicts the overlap ratio derived from the largest common subtable. Related-Table Discovery. Data discovery in data lakes [8, 39, 47, 51, 59] is framed as unionable or joinable table search. Unionable search focuses on semantic column compatibility [21, 29, 40], while joinable search focuses on key and value overlap with scalable indexing or hashing [17, 19, 61]. In contrast, overlap ratio estimation is defined by the largest common subtable and depends on row– column structure beyond key overlap or semantic relatedness. Graph Similarity and Matching. Our setting is loosely connected to graph similarity and matching, which compares structured objects via graph edit distance (GED) or learned similarity. Representative methods include Graph Matching Networks [34] and SimGNN [5]. More recent work improves similarity prediction via hierarchical matching or explicit alignment regularization, including H2MN [60] and ERIC [62], and GED formulations such as GREED [44] and GraphEdX [27]. These methods target graph similarity, while overlap ratio estimation is defined on tables with row–column structure and supervision from the overlap ratio.
Ge Lee, Shixun Huang, Zhifeng Bao, Shazia Sadiq, and Yanchang Zhao
9
Conclusion and Future Work
We study the table overlap ratio estimation problem. Existing estimators remain limited by underexpressed joint row–column structure, missing inter-table alignment signals under independent encoding, and sensitivity to value distribution shift across domains. We propose ALORE, which addresses these challenges with a structureaware hypergraph representation, inter-table alignment-guided learning, and domain-robust value handling. Experiments across multiple datasets show that ALORE improves accuracy, especially in zero-shot transfer, while remaining efficient. Future work includes extending overlap beyond exact matching to tolerate noise and semantic equivalence, developing stronger retrieval-oriented training and indexing for query-by-table at larger scales, and reducing label dependence via weak supervision or self-training to cover new domains.
Alignment-Guided Largest Table Overlap Size Estimation
References [1] 2026. Source code for ALORE. https://github.com/DataAutonomyLab/ALORE. [2] Marco D. Adelfio and Hanan Samet. 2013. Schema Extraction for Tabular Data on the Web. PVLDB 6, 6 (2013), 421–432. [3] Martín Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. 2019. Invariant Risk Minimization. CoRR abs/1907.02893 (2019). [4] David Aumueller, Hong Hai Do, Sabine Massmann, and Erhard Rahm. 2005. Schema and ontology matching with COMA++. In SIGMOD. ACM, 906–908. [5] Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. 2019. SimGNN: A Neural Network Approach to Fast Graph Similarity Computation. In WSDM. ACM, 384–392. [6] Tobias Bleifuß, Leon Bornemann, Dmitri V. Kalashnikov, Felix Naumann, and Divesh Srivastava. 2021. The Secret Life of Wikipedia Tables. In SEA-Data@VLDB (CEUR Workshop Proceedings, Vol. 2929). CEUR-WS.org, 20–26. [7] Tobias Bleifuß, Leon Bornemann, Dmitri V. Kalashnikov, Felix Naumann, and Divesh Srivastava. 2021. Structured Object Matching across Web Page Revisions. In ICDE. IEEE, 1284–1295. [8] Alex Bogatu, Alvaro A. A. Fernandes, Norman W. Paton, and Nikolaos Konstantinou. 2020. Dataset Discovery in Data Lakes. In ICDE. IEEE, 709–720. [9] Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. 1993. Signature Verification Using a Siamese Time Delay Neural Network. In NIPS. Morgan Kaufmann, 737–744. [10] Michael J. Cafarella, Alon Y. Halevy, Daisy Zhe Wang, Eugene Wu, and Yang Zhang. 2008. WebTables: exploring the power of tables on the web. PVLDB 1, 1 (2008), 538–549. [11] Riccardo Cappuzzo, Paolo Papotti, and Saravanan Thirumuruganathan. 2020. Creating Embeddings of Heterogeneous Relational Datasets for Data Integration Tasks. In SIGMOD Conference. ACM, 1335–1349. [12] Pei Chen, Soumajyoti Sarkar, Leonard Lausen, Balasubramaniam Srinivasan, Sheng Zha, Ruihong Huang, and George Karypis. 2023. HyTrel: Hypergraphenhanced Tabular Data Representation Learning. In NeurIPS. [13] Marco Cuturi. 2013. Sinkhorn Distances: Lightspeed Computation of Optimal Transport. In NIPS. 2292–2300. [14] Xiang Deng, Huan Sun, Alyssa Lees, You Wu, and Cong Yu. 2022. TURL: Table Understanding through Representation Learning. SIGMOD Rec. 51, 1 (2022), 33–40. [15] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In NAACL-HLT (1). Association for Computational Linguistics, 4171–4186. [16] Hong Hai Do and Erhard Rahm. 2002. COMA - A System for Flexible Combination of Schema Matching Approaches. In VLDB. Morgan Kaufmann, 610–621. [17] Yuyang Dong, Kunihiro Takeoka, Chuan Xiao, and Masafumi Oyamada. 2021. Efficient Joinable Table Discovery in Data Lakes: A High-Dimensional SimilarityBased Approach. In ICDE. IEEE, 456–467. [18] Mohamed G. Elfeky, Ahmed K. Elmagarmid, and Vassilios S. Verykios. 2002. TAILOR: A Record Linkage Tool Box. In ICDE. IEEE Computer Society, 17–28. [19] Mahdi Esmailoghli, Jorge-Arnulfo Quiané-Ruiz, and Ziawasch Abedjan. 2022. MATE: Multi-Attribute Table Extraction. PVLDB 15, 8 (2022), 1684–1696. [20] Grace Fan, Roee Shraga, and Renée J. Miller. 2024. Gen-T: Table Reclamation in Data Lakes. In ICDE. IEEE, 3532–3545. [21] Grace Fan, Jin Wang, Yuliang Li, Dan Zhang, and Renée J. Miller. 2023. Semanticsaware Dataset Discovery from Data Lakes with Contextualized Column-based Representation Learning. PVLDB 16, 7 (2023), 1726–1739. [22] Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. 2019. Hypergraph Neural Networks. In AAAI. AAAI Press, 3558–3565. [23] Yue Gao, Yifan Feng, Shuyi Ji, and Rongrong Ji. 2023. HGNN+ : General Hypergraph Neural Networks. IEEE Trans. Pattern Anal. Mach. Intell. 45, 3 (2023), 3181–3199. [24] Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In KDD. ACM, 855–864. [25] William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In NIPS. 1024–1034. [26] Madelon Hulsebos, Çagatay Demiralp, and Paul Groth. 2023. GitTables: A LargeScale Corpus of Relational Tables. PACMMOD 1, 1 (2023), 30:1–30:17. [27] Eeshaan Jain, Indradyumna Roy, Saswat Meher, Soumen Chakrabarti, and Abir De. 2024. Graph Edit Distance with General Costs Using Neural Set Divergence. In NeurIPS. [28] Kalervo Järvelin and Jaana Kekäläinen. 2002. Cumulated gain-based evaluation of IR techniques. ACM Trans. Inf. Syst. 20, 4 (2002), 422–446. [29] Aamod Khatiwada, Grace Fan, Roee Shraga, Zixuan Chen, Wolfgang Gatterbauer, Renée J. Miller, and Mirek Riedewald. 2023. SANTOS: Relationship-based Semantic Table Union Search. PACMMOD 1, 1 (2023), 9:1–9:25. [30] Omar Khattab and Matei Zaharia. 2020. ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT. In SIGIR. ACM, 39–48. [31] Maximilian Koch, Mahdi Esmailoghli, Sören Auer, and Ziawasch Abedjan. 2023. Duplicate Table Discovery with Xash. In BTW (LNI, Vol. P-331). Gesellschaft für Informatik e.V., 367–390.
[32] Mingzhao Li, Zhifeng Bao, Timos Sellis, Shi Yan, and Rui Zhang. 2018. HomeSeeker: A visual analytics system of real estate data. J. Vis. Lang. Comput. 45 (2018), 1–16. [33] Qimai Li, Zhichao Han, and Xiao-Ming Wu. 2018. Deeper Insights Into Graph Convolutional Networks for Semi-Supervised Learning. In AAAI. AAAI Press, 3538–3545. [34] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. 2019. Graph Matching Networks for Learning the Similarity of Graph Structured Objects. In ICML (Proceedings of Machine Learning Research, Vol. 97). PMLR, 3835–3845. [35] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019. RoBERTa: A Robustly Optimized BERT Pretraining Approach. CoRR abs/1907.11692 (2019). [36] Yurong Liu, Eduardo Peña, Aécio S. R. Santos, Eden Wu, and Juliana Freire. 2025. Magneto: Combining Small and Large Language Models for Schema Matching. PVLDB 18, 8 (2025), 2681–2694. [37] Gonzalo E. Mena, David Belanger, Scott W. Linderman, and Jasper Snoek. 2018. Learning Latent Permutations with Gumbel-Sinkhorn Networks. In ICLR (Poster). OpenReview.net. [38] Matthew Michelson and Craig A. Knoblock. 2006. Learning Blocking Schemes for Record Linkage. In AAAI. AAAI Press, 440–445. [39] Renée J. Miller. 2018. Open Data Integration. PVLDB 11, 12 (2018), 2130–2139. [40] Fatemeh Nargesian, Erkang Zhu, Ken Q. Pu, and Renée J. Miller. 2018. Table Union Search on Open Data. PVLDB 11, 7 (2018), 813–825. [41] Xue Bin Peng, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. 2018. Sim-to-Real Transfer of Robotic Control with Dynamics Randomization. In ICRA. IEEE, 1–8. [42] Rakesh Pimplikar and Sunita Sarawagi. 2012. Answering Table Queries on the Web using Column Keywords. PVLDB 5, 10 (2012), 908–919. [43] Francesco Pugnaloni, Luca Zecchini, Matteo Paganelli, Matteo Lissandrini, Felix Naumann, and Giovanni Simonini. 2025. Table Overlap Estimation through Graph Embeddings. PACMMOD 3, 3 (2025), 228:1–228:25. [44] Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan T. Chakaravarthy, Yogish Sabharwal, and Sayan Ranu. 2022. GREED: A Neural Framework for Learning Graph Distance Functions. In NeurIPS. [45] Nils Reimers and Iryna Gurevych. 2019. Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. In EMNLP/IJCNLP (1). Association for Computational Linguistics, 3980–3990. [46] Mehdi Sajjadi, Mehran Javanmardi, and Tolga Tasdizen. 2016. Regularization With Stochastic Transformations and Perturbations for Deep Semi-Supervised Learning. In NIPS. 1163–1171. [47] Anish Das Sarma, Lujun Fang, Nitin Gupta, Alon Y. Halevy, Hongrae Lee, Fei Wu, Reynold Xin, and Cong Yu. 2012. Finding related tables. In SIGMOD. ACM, 817–828. [48] Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojciech Zaremba, and Pieter Abbeel. 2017. Domain randomization for transferring deep neural networks from simulation to the real world. In IROS. IEEE, 23–30. [49] Mohamed Trabelsi, Zhiyu Chen, Shuo Zhang, Brian D. Davison, and Jeff Heflin. 2022. StruBERT: Structure-aware BERT for Table Search and Matching. In WWW. ACM, 442–451. [50] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is All you Need. In NIPS. 5998–6008. [51] Qiming Wang and Raul Castro Fernandez. 2023. Solo: Data Discovery Using Natural Language Questions Via A Self-Supervised Approach. Proc. ACM Manag. Data 1, 4 (2023), 262:1–262:27. [52] Runhui Wang, Yuliang Li, and Jin Wang. 2023. Sudowoodo: Contrastive Selfsupervised Learning for Multi-purpose Data Integration and Preparation. In ICDE. IEEE, 1502–1515. [53] Renzhi Wu, Sanya Chaba, Saurabh Sawlani, Xu Chu, and Saravanan Thirumuruganathan. 2020. ZeroER: Entity Resolution using Zero Labeled Examples. In SIGMOD. ACM, 1149–1164. [54] Qizhe Xie, Zihang Dai, Eduard H. Hovy, Thang Luong, and Quoc Le. 2020. Unsupervised Data Augmentation for Consistency Training. In NeurIPS. [55] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In ICLR. OpenReview.net. [56] Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha P. Talukdar. 2019. HyperGCN: A New Method For Training Graph Convolutional Networks on Hypergraphs. In NeurIPS. 1509–1520. [57] Pengcheng Yin, Graham Neubig, Wen-tau Yih, and Sebastian Riedel. 2020. TaBERT: Pretraining for Joint Understanding of Textual and Tabular Data. In ACL. Association for Computational Linguistics, 8413–8426. [58] Luca Zecchini, Tobias Bleifuß, Giovanni Simonini, Sonia Bergamaschi, and Felix Naumann. 2024. Determining the Largest Overlap between Tables. PACMMOD 2, 1 (2024), 48:1–48:26. [59] Yi Zhang and Zachary G. Ives. 2020. Finding Related Tables in Data Lakes for Interactive Data Science. In SIGMOD. ACM, 1951–1966.
Ge Lee, Shixun Huang, Zhifeng Bao, Shazia Sadiq, and Yanchang Zhao
[60] Zhen Zhang, Jiajun Bu, Martin Ester, Zhao Li, Chengwei Yao, Zhi Yu, and Can Wang. 2021. H2MN: Graph Similarity Learning with Hierarchical Hypergraph Matching Networks. In KDD. ACM, 2274–2284. [61] Erkang Zhu, Dong Deng, Fatemeh Nargesian, and Renée J. Miller. 2019. JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes. In SIGMOD. ACM, 847–864. [62] Wei Zhuo and Guang Tan. 2022. Efficient Graph Similarity Computation with Alignment Regularization. In NeurIPS.
Alignment-Guided Largest Table Overlap Size Estimation
Appendix A Additional Details for Query-by-Table Retrieval
Table 7: Ranking performance on TP-TR measured by nDCG@k (↑). Method
nDCG@1
nDCG@10
nDCG@50
nDCG@100
Jaccard Jaccard-BU Jaccard-BN BERT-R BERT-T BERT-HT RoBERTa-R RoBERTa-T RoBERTa-HT TURL Armadillo ALORE
0.720 0.652 0.781 0.577 ± 0.025 0.542 ± 0.009 0.521 ± 0.011 0.594 ± 0.021 0.588 ± 0.021 0.560 ± 0.021 0.615 ± 0.021 0.735 ± 0.066 0.792 ± 0.021
0.609 0.596 0.777 0.560 ± 0.004 0.515 ± 0.007 0.495 ± 0.006 0.572 ± 0.026 0.565 ± 0.026 0.540 ± 0.026 0.585 ± 0.026 0.702 ± 0.025 0.789 ± 0.026
0.499 0.551 0.746 0.488 ± 0.002 0.468 ± 0.006 0.440 ± 0.004 0.525 ± 0.029 0.518 ± 0.029 0.492 ± 0.029 0.535 ± 0.029 0.665 ± 0.010 0.765 ± 0.029
0.476 0.541 0.753 0.453 ± 0.003 0.425 ± 0.006 0.412 ± 0.008 0.499 ± 0.032 0.495 ± 0.032 0.475 ± 0.032 0.510 ± 0.032 0.630 ± 0.018 0.772 ± 0.032
Figure 7: Kernel density estimation of overlap ratio distributions for 10 representative query tables on Git-Query.
Figure 9: Threshold-based retrieval performance on TP-TR across overlap ratio thresholds 𝜏. We report Selection Rate (↓), Recall (↑), Precision (↑), and F1 Score (↑). Figure 8: Kernel density estimation of overlap ratio distributions for 10 representative query tables on TP-TR.
A.1
Data Distributions
Figures 7 and 8 visualize the ground-truth overlap ratio distributions between each query and its candidates for Git-Query and TP-TR datasets (10 representative queries shown). In both datasets, overlaps are highly concentrated between 0 and 0.3, with only a small tail of moderate-to-high overlap. This reflects the typical large-corpus setting where most tables are dissimilar, and retrieval performance depends on separating a few truly overlapping tables from many near-zero candidates.
A.2
Experimental Results on TP-TR Dataset
We additionally evaluate query-by-table retrieval on the TP-TR (small) benchmark [20], following the setup where the query set contains 26 TP-TR tables and the candidate set consists of Wiki plus 32 additional TP-TR tables. For each query, each method estimates overlap ratios for all candidates and uses the scores for both ranking and threshold-based filtering. Table 7 reports nDCG@𝑘 at multiple cutoffs, where ALORE achieves the best ranking quality across all 𝑘, consistently improving over the baselines, which indicates that ALORE better prioritizes highly overlapping tables at the top of the ranked list. Figure 9 further evaluates thresholdbased retrieval by varying 𝜏 ∈ {0.6, 0.7, 0.8, 0.9} and reporting selection rate, recall, precision, and F1. Overall, ALORE provides the strongest effectiveness-cost trade-off, maintaining higher recall, precision, and F1 while keeping the selected candidate subset compact, whereas baselines including BERT-T and TURL typically return slightly larger subsets to achieve similar recall and Jaccard-BN can be overly conservative on this dataset.