Resumo Técnico: GRAFT: Recuperação e Fusão de Tabelas Baseadas em Grafos para Data Lakes

1. Definição do Problema

O artigo aborda a Recuperação de Tabelas Sensível à Estrutura em data lakes tabulares. Diferente de corpora de texto ou imagens não estruturados, os data lakes tabulares consistem em tabelas fragmentadas e heterogêneas, onde responder a consultas analíticas complexas muitas vezes exige a integração de múltiplas tabelas via operações de join (junção) e union (união).

Os métodos de recuperação existentes enfrentam duas limitações primárias:

1. Recuperação ponto a ponto (Point-wise): Pontua tabelas independentemente em relação a uma consulta, retornando candidatas que são semanticamente relevantes, mas estruturalmente desconectadas (ex: faltando tabelas de ponte necessárias para os joins).
2. Expansão gananciosa (Greedy expansion): Adiciona iterativamente tabelas com base na relevância para a consulta ou para a última tabela selecionada, mas falha em garantir compatibilidade estrutural (capacidade de join/union) ou diversidade de evidências.
3. Complexidade: O espaço de busca para um conjunto de $L$ tabelas interconectadas cresce exponencialmente ($O(M \cdot N^{L-1})$), tornando a enumeração exaustiva intratável.

O objetivo é identificar um conjunto de tabelas interconectadas que satisfaçam coletivamente a intenção de linguagem natural (NL) de um usuário, equilibrando relevância semântica, compatibilidade estrutural e diversidade de evidências (suprimindo redundâncias).

2. Metodologia

2.1 Formulação de Grafo

Os autores modelam o problema como uma tarefa de correspondência de grafos (graph matching) entre dois grafos tipados:

• Grafo do Data Lake ($G_D$): Um grafo heterogêneo contendo nós para tabelas, colunas e valores. As arestas representam contenção (tabela-coluna-valor) e relações estruturais (capacidade de join e union).
• Grafo de Intenção ($G_I$): Uma floresta de "árvores de intenção" destiladas da consulta NL usando um LLM. Cada árvore representa uma necessidade de dados coerente (hierarquia entidade-atributo-valor). Arestas entre árvores representam joins necessários, frequentemente através de tabelas de ponte não explicitamente nomeadas na consulta.

A tarefa de recuperação é reformulada como encontrar um subgrafo conectado em $G_D$ que admita um homomorfismo tipado de $G_I$.

2.2 A Métrica IGMS (Pontuação de Correspondência de Grafo Informacional)

Para enfrentar o desafio do design de utilidade unificada, o artigo propõe a IGMS, uma função de recompensa de determinante logarítmico que acopla três desideratos em um único objetivo:

1. Relevância Semântica: Medida via uma matriz de suporte $M_\Phi$ que combina similaridade de cosseno e compatibilidade de tipo entre átomos de intenção e unidades de evidência.
2. Compatibilidade Estrutural: Garantida pelo mapeamento de arestas de intenção para caminhos válidos em $G_D$ (caminhos de join/union).
3. Diversidade de Evidências: Modelada via uma matriz de covariância $C_\Phi$ baseada na similaridade de Jaccard de conjuntos de colunas para penalizar evidências redundantes.

O objetivo é definido como:
$$U_{IGMS}(Q, \Phi) = \frac{1}{a} \log \det(I_a + M_\Phi^\top C_\Phi^{-1} M_\Phi)$$
Esta formulação é derivada da informação mútua em processos gaussianos, fornecendo uma medida fundamentada de ganho de informação. Os autores provam que a IGMS é monotônica e submodular, oferecendo uma garantia de aproximação de $(1 - 1/e)$ para seleção gananciosa.

2.3 Busca Eficiente via Aprendizado de Valor Offline

Como a otimização exata é intratável, os autores tratam a geração de subgrafos como um Processo de Decisão de Markov (MDP) e utilizam Aprendizado Q Implícito Offline (IQL).

• Dados de Treinamento Autogerados: Para superar a falta de trajetórias de verdade fundamental (ground-truth) em data lakes, eles introduzem um operador de compressão canônico. Este operador inverte o homomorfismo: ele amostra um subgrafo de $G_D$ e o comprime em um grafo de intenção pseudo-$G_I$. Isso gera pares alinhados $(G_I, \text{subgrafo})$ sem necessidade de anotação humana.
• Treinamento: A função Q é treinada nessas trajetórias autogeradas usando IQL, que aprende uma função de valor para classificar ações de fronteira sem exigir restrições de política explícitas.
• Pipeline de Busca Online: Uma estratégia de poda em três estágios reduz o espaço de candidatos de exponencial para $O(B \cdot L)$:
  1. Alcance de Âncora (Anchor Reachability): Inicializa o espaço de busca usando os $K$ vizinhos mais próximos dos átomos de intenção.
  2. Admissibilidade de Predicado: Filtra ações que não podem satisfazer átomos de intenção não suportados dentro de um limite de saltos (hop limit).
  3. Monotonicidade de Recompensa: Utiliza uma fila de prioridade com avaliação preguiçosa (lazy evaluation) — explorando a monotonicidade da IGMS — para reclassificar candidatos usando a pontuação exata da IGMS apenas quando necessário.

3. Principais Contribuições

1. Formulação de Correspondência de Grafo: Reclassificação da recuperação de tabelas como a correspondência de um grafo de intenção derivado da consulta contra um grafo de data lake heterogêneo.
2. Métrica IGMS: Introdução de uma recompensa de determinante logarítmico que unifica relevância semântica, compatibilidade estrutural e diversidade, provada como submodular.
3. RL Offline com Autossupervisão: Desenvolvimento de um método para treinar funções de valor via IQL em trajetórias autogeradas derivadas de um operador de compressão canônico, eliminando a necessidade de dados anotados.
4. Busca Eficiente: Design de um pipeline de poda em três estágios que alcança alta eficiência de busca mantendo a consciência estrutural.

4. Resultados Experimentais

O método foi avaliado nos datasets Spider e BIRD adaptados para o cenário de data lake tabular, bem como em uma tarefa de Enriquecimento de Dados de Treinamento usando o corpus Open Data.

• Desempenho: O GRAFT superou as bases de comparação point-wise (DTR, Pneuma), greedy-expansion (MTR) e structure-aware (JAR) em todas as métricas (Recall, Precisão, F1 e Suficiência).
  • Ganhos Relativos: Alcançou um ganho relativo de 7,8% em F1 e 10,6% em Suficiência sobre a base mais forte (JAR).
  • Suficiência: O GRAFT reduziu significamente o problema da "omissão de ponte" (bridge omission), garantindo que todas as tabelas necessárias para o raciocínio de múltiplos saltos fossem recuperadas.
• Impacto Downstream: Em tarefas de enriquecimento de dados de treinamento, o GRAFT alcançou o menor RMSE (3.65) e a maior Acurácia (0.748), demonstrando que sua recuperação orientada à diversidade evita o overfitting a dados redundantes.
• Eficiência: O GRAFT completou consultas em 3,5 segundos, comparável aos métodos gananciosos (MTR em 4,0s) e substancialmente mais rápido que a base de MIP estrutural (JAR em 22,4s).
• Estudos de Ablação: Confirmaram que o objetivo de determinante logarítmico, o amostrador de trajetória consciente de centralidade e o extrator de intenção específico (GPT-5-mini) são componentes críticos. A remoção de qualquer componente degradou o desempenho.

5. Significância e Alegações

O artigo afirma que o GRAFT representa uma mudança da recuperação de tabelas isoladas para a recuperação e fusão estruturada. Sua significância reside em:

• Lidar com Fragmentação: Abordar com sucesso o desafio de recuperar tabelas desconectadas que devem ser unidas (join) ou combinadas (union) para responder a uma consulta.
• Consciência de Diversidade: Ir além da simples pontuação de relevância para suprimir explicitamente evidências redundantes, o que é crucial para a precisão analítica (ex: evitar a contagem dupla em agregações).
• Escalabilidade: Demonstrar que a recuperação complexa e consciente da estrutura pode ser realizada eficientemente usando funções de valor aprendidas e poda, evitando a intratabilidade da otimização exata ou de solvers MIP.
• Aprendizado Autossupervisionado: Mostrar que dados de treinamento de alta qualidade para agentes de recuperação em data lakes podem ser gerados algoritmicamente sem anotação manual.

Os autores concluem que o GRAFT fornece um framework robusto para agentes de dados autônomos resolverem consultas analíticas ao recuperar evidências que não são apenas relevantes, mas também estruturalmente integráveis e diversas.