💻 computer science

GRAFT: Graph-Matched Retrieval and Fusion of Tables in Data Lakes

The paper proposes GRAFT, a novel framework that models table retrieval in data lakes as a graph matching problem using an IGMS objective and an implicit Q-learning-based subgraph generation process to effectively integrate joinable and unionable tables, thereby significantly outperforming existing baselines in retrieval accuracy and evidence sufficiency.

Original authors: Daomin Ji, Hui Luo, Zhifeng Bao, Shane Culpepper, Shazia Sadiq

Published 2026-07-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Daomin Ji, Hui Luo, Zhifeng Bao, Shane Culpepper, Shazia Sadiq

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but your clues aren't in a single notebook. Instead, they are scattered across thousands of different filing cabinets in a massive, chaotic library called a "Data Lake." Some cabinets have lists of names, others have lists of numbers, and some have maps. To solve your case, you can't just grab the cabinet that looks most like your question; you need to find a specific chain of cabinets that can be snapped together like Lego bricks to build the full picture.

This is the problem GRAFT (Graph-Matched Retrieval and Fusion of Tables) tries to solve. The authors, a team of researchers from RMIT, University of Wollongong, and The University of Queensland, argue that old ways of searching these data lakes are like trying to solve a jigsaw puzzle by only looking at the color of the pieces, ignoring the shape.

The Old Way: The "Lonely Clue" Mistake

Previous methods acted like a lonely detective who picks up the single file that has the most matching words to their question. If you ask, "Who are the Computer Science professors?", the old system might grab a file full of professor names but miss the file that links them to their departments, or the file that lists the different types of professors.

The paper explicitly argues against two common strategies:

Point-wise retrieval: Picking tables one by one based on how well they match the words in your question. The authors show this often returns a pile of disconnected files that can't be joined together.
Greedy expansion: Starting with one file and just adding the next file that seems most related to the previous one. The paper suggests this is like following a breadcrumb trail that leads you in circles, missing the crucial bridge that connects two distant parts of the puzzle.

In a test using real-world datasets (called Spider and BIRD), these old methods often failed to find the "bridge" tables needed to connect the dots, leading to incomplete or wrong answers.

The New Way: GRAFT's "Master Blueprint"

GRAFT changes the game by treating the search like a graph matching problem. Instead of just reading words, it builds a "Master Blueprint" (called an Intent Graph) from your question. This blueprint maps out exactly what you need: the entities (like "Professor"), the attributes (like "Name"), and the invisible connections (like "works in Department") that must exist.

Then, it looks at the Data Lake as a giant, messy map of tables. It tries to find a path through this map that fits the blueprint perfectly.

To do this, GRAFT uses a clever scoring system called IGMS (Information-theoretic Graph Matching Score). Think of IGMS as a "usefulness meter" that checks three things at once:

Relevance: Does this file actually talk about what I asked?
Connectivity: Can this file actually be snapped onto the others I've already found?
Diversity: Is this file adding new information, or is it just a copy of what I already have?

The paper proves mathematically that this scoring system is "submodular," which is a fancy way of saying it's smart about avoiding redundancy. It ensures you don't get two files that say the exact same thing, which would just clutter your evidence.

The "Self-Teaching" Detective

Here is where it gets really cool. The Data Lake doesn't come with a "Answer Key" telling the computer which tables are the right ones. So, how does GRAFT learn to find them?

The authors created a self-teaching loop. They built a robot that generates its own practice problems. It grabs a random chunk of the Data Lake, shrinks it down into a fake "question" (an intent graph), and then tries to rebuild the original chunk from that question. By doing this millions of times, the system learns a "value function"—basically, a gut feeling about which path through the data lake is most likely to lead to the right answer.

They used a technique called Implicit Q-learning (IQL) to train this gut feeling. In their experiments, they generated 200,000 of these self-made practice trajectories. The paper suggests that this self-generated training data is crucial because it allows the system to learn without needing humans to manually label thousands of examples.

The Results: Faster and Smarter

When the researchers tested GRAFT against the old methods, the results were measured and specific:

Accuracy: GRAFT improved the F1 score (a measure of overall accuracy) by 7.8% and the Sufficiency (the ability to find all necessary pieces) by 10.6% compared to the strongest previous method (JAR).
Speed: Even though it's doing complex math, GRAFT is fast. It takes about 3.5 seconds to find the answer on the Spider dataset. This is much faster than the "structure-aware" competitor JAR, which took 22.4 seconds, and is on par with the faster but less accurate greedy methods.
Real-world impact: In a task called "training data enrichment" (where the goal is to find extra data to make a prediction model better), GRAFT helped lower the error rate (RMSE) to 3.65 and boosted accuracy to 0.748, outperforming all other methods.

What the Paper Does Not Claim

It's important to know what GRAFT doesn't do. The paper does not claim that GRAFT can solve every possible data problem instantly.

It does not claim to be a "magic bullet" that works without any setup; it requires building a graph of the data lake first.
It does not suggest that the "self-generated" training data is perfect; the authors note that the quality of the training depends on how well the "compression operator" (the robot that shrinks the data) works.
The paper explicitly rules out the idea that simply adding more tables (high recall) is enough. They show that if you add too many redundant tables, the prediction models actually get worse because they get confused by the noise. GRAFT specifically avoids this by penalizing duplicate information.

The Bottom Line

The authors suggest that by treating table retrieval as a puzzle-matching game rather than a word-search, and by teaching the computer to learn from its own generated practice runs, we can build autonomous data agents that are much better at finding the right evidence. In their tests, this approach consistently beat the competition, finding the right mix of tables to answer complex questions without getting lost in the noise. It's a step toward a future where your computer doesn't just find a file for you, but assembles the whole story for you.

Technical Summary: GRAFT: Graph-Matched Retrieval and Fusion of Tables in Data Lakes

1. Problem Definition

The paper addresses Structure-aware Table Retrieval in tabular data lakes. Unlike unstructured text or image corpora, tabular data lakes consist of fragmented, heterogeneous tables where answering complex analytical queries often requires integrating multiple tables via join and union operations.

Existing retrieval methods face two primary limitations:

Point-wise retrieval: Scores tables independently against a query, returning candidates that are semantically relevant but structurally disconnected (e.g., missing necessary bridge tables for joins).
Greedy expansion: Iteratively adds tables based on relevance to the query or the last selected table but fails to guarantee structural compatibility (joinability/unionability) or evidence diversity.
Complexity: The search space for a set of $L$ interconnected tables grows exponentially ( $O(M \cdot N^{L-1})$ ), making exhaustive enumeration intractable.

The goal is to identify a set of interconnected tables that collectively satisfy a user's natural language (NL) intent, balancing semantic relevance, structural compatibility, and evidence diversity (suppressing redundancy).

2. Methodology

2.1 Graph Formulation

The authors model the problem as a graph matching task between two typed graphs:

Data Lake Graph ( $G_D$ ): A heterogeneous graph containing nodes for tables, columns, and values. Edges represent containment (table-column-value) and structural relations (joinability and unionability).
Intent Graph ( $G_I$ ): A forest of "intent trees" distilled from the NL query using an LLM. Each tree represents a coherent data need (entity-attribute-value hierarchy). Cross-tree edges represent required joins, often through bridge tables not explicitly named in the query.

The retrieval task is reformulated as finding a connected subgraph in $G_D$ that admits a typed homomorphism from $G_I$ .

2.2 The IGMS Metric (Information-theoretic Graph Matching Score)

To address the challenge of unified utility design, the paper proposes IGMS, a log-determinant reward function that couples three desiderata into a single objective:

Semantic Relevance: Measured via a support matrix $M_\Phi$ combining cosine similarity and type compatibility between intent atoms and evidence units.
Structural Compatibility: Ensured by mapping intent edges to valid paths in $G_D$ (join/union paths).
Evidence Diversity: Modeled via a covariance matrix $C_\Phi$ based on column-set Jaccard similarity to penalize redundant evidence.

The objective is defined as:
$U_{IGMS}(Q, \Phi) = \frac{1}{a} \log \det(I_a + M_\Phi^\top C_\Phi^{-1} M_\Phi)$
This formulation is derived from mutual information in Gaussian processes, providing a principled measure of information gain. The authors prove IGMS is monotone and submodular, offering a $(1 - 1/e)$ approximation guarantee for greedy selection.

2.3 Efficient Search via Offline Value Learning

Since exact optimization is intractable, the authors cast subgraph generation as a Markov Decision Process (MDP) and employ Offline Implicit Q-Learning (IQL).

Self-Generated Training Data: To overcome the lack of ground-truth trajectories in data lakes, they introduce a canonical compression operator. This operator inverts the homomorphism: it samples a subgraph from $G_D$ and compresses it into a pseudo-intent graph $G_I$ . This generates aligned $(G_I, \text{subgraph})$ pairs without human annotation.
Training: The Q-function is trained on these self-generated trajectories using IQL, which learns a value function to rank frontier actions without requiring explicit policy constraints.
Online Search Pipeline: A three-stage pruning strategy reduces the candidate space from exponential to $O(B \cdot L)$ $O (B \cdot L)$ :
1. Anchor Reachability: Initializes the search space using top- $K$ nearest neighbors of intent atoms.
2. Predicate Admissibility: Filters actions that cannot satisfy unsupported intent atoms within a hop limit.
3. Reward Monotonicity: Uses a priority queue with lazy evaluation (exploiting the monotonicity of IGMS) to rerank candidates using the exact IGMS score only when necessary.

3. Key Contributions

Graph-Matching Formulation: Recasting table retrieval as matching a query-derived intent graph against a heterogeneous data lake graph.
IGMS Metric: Introducing a log-determinant reward that unifies semantic relevance, structural compatibility, and diversity, proven to be submodular.
Offline RL with Self-Supervision: Developing a method to train value functions via IQL on self-generated trajectories derived from a canonical compression operator, eliminating the need for annotated data.
Efficient Search: Designing a three-stage pruning pipeline that achieves high search efficiency while maintaining structural awareness.

4. Experimental Results

The method was evaluated on Spider and BIRD datasets adapted for the tabular data lake setting, as well as a Training Data Enrichment task using the Open Data corpus.

Performance: GRAFT outperformed point-wise (DTR, Pneuma), greedy-expansion (MTR), and structure-aware (JAR) baselines across all metrics (Recall, Precision, F1, and Sufficiency).
- Relative Gains: Achieved a 7.8% relative gain in F1 and 10.6% in Sufficiency over the strongest baseline (JAR).
- Sufficiency: GRAFT significantly reduced the "bridge omission" problem, ensuring that all necessary tables for multi-hop reasoning were retrieved.
Downstream Impact: In training data enrichment tasks, GRAFT achieved the lowest RMSE (3.65) and highest Accuracy (0.748), demonstrating that its diversity-aware retrieval prevents overfitting to redundant data.
Efficiency: GRAFT completed queries in 3.5 seconds, comparable to greedy methods (MTR at 4.0s) and substantially faster than the structure-aware MIP baseline (JAR at 22.4s).
Ablation Studies: Confirmed that the log-determinant objective, the centrality-aware trajectory sampler, and the specific intent extractor (GPT-5-mini) are critical components. Removing any component degraded performance.

5. Significance and Claims

The paper claims that GRAFT represents a shift from isolated table retrieval to structured retrieval and fusion. Its significance lies in:

Handling Fragmentation: Successfully addressing the challenge of retrieving disconnected tables that must be joined or unioned to answer a query.
Diversity Awareness: Moving beyond simple relevance scoring to explicitly suppress redundant evidence, which is crucial for analytical accuracy (e.g., preventing double-counting in aggregations).
Scalability: Demonstrating that complex, structure-aware retrieval can be performed efficiently using learned value functions and pruning, avoiding the intractability of exact optimization or MIP solvers.
Self-Supervised Learning: Showing that high-quality training data for retrieval agents in data lakes can be generated algorithmically without manual annotation.

The authors conclude that GRAFT provides a robust framework for autonomous data agents to resolve analytical queries by retrieving evidence that is not only relevant but also structurally integrable and diverse.