Resumo Técnico: AutoGrable

Declaração do Problema

O aprendizado em grafos, particularmente via Redes Neurais de Grafos de Passagem de Mensagem (MPNNs), pressupõe a existência de uma estrutura de grafo. No entanto, os formatos de dados dominantes na aprendizagem automática aplicada — tabelas únicas e bancos de dados relacionais ligados por chaves estrangeiras — não possuem inerentemente uma representação de grafo. Aplicar MPNNs a esses dados requer uma fase de construção onde se deve decidir quais entidades se tornam nós, quais se conectam e através de quais relações.

As abordagens atuais para este problema são limitadas:

1. Aprender um grafo: Inferir adjacência suave a partir de características conjuntamente com o modelo. Isso assume que a estrutura implica proximidade geométrica, o que as tabelas não fornecem (sua relação nativa é o valor categórico compartilhado).
2. Construir um grafo: Fixar um esqueleto de esquema ou pontuar atributos com base na precisão de um modelo treinado. Isso é circular (exigindo uma execução de treinamento por candidato), computacionalmente caro e falha em explicar por que uma construção específica ajuda o aprendiz.

O artigo aborda a questão fundamental: Quando um grafo não é dado, o que constitui um "bom" grafo para uma tabela, e como ele pode ser construído sem treinar um modelo?

Metodologia

Fundamentação Teórica: 1-WL e Alinhamento de Partição

Os autores fundamentam sua abordagem nos limites de poder expressivo das MPNNs, que são limitadas pelo teste de Weisfeiler–Leman de uma dimensão (refinamento de cores) 1-WL. Para uma GNN, um grafo construído a partir de uma tabela efetivamente ordena as linhas da tabela em classes de cores 1-WL. O modelo não consegue distinguir entre linhas atribuídas à mesma cor.

Portanto, uma construção de grafo é "boa" para uma tarefa se a partição induzida das linhas se alinha com os rótulos da tarefa:

• Linhas com rótulos diferentes devem cair em classes de cores diferentes.
• Linhas com o mesmo rótulo não devem ser divididas desnecessariamente (evitando a sobrefragmentação).

Este critério de alinhamento pode ser avaliado antes de qualquer treinamento de modelo ocorrer.

O Score de Alinhamento ($J$)

Para operacionalizar este critério, o artigo propõe um score livre de treinamento $J$ para um subconjunto candidato de atributos $S$. O score equilibra dois fatores concorrentes:

1. Ganho Preditivo (Alinhamento): Medido pelo erro de validação de um "preditor de bloco" simples ($\hat{h}_S$) que é constante nas células definidas por $S$. Este preditor utiliza a distribuição empírica de rótulos das linhas de treinamento dentro de cada célula.
2. Penalidade de Fragmentação ($\Omega$): Uma medida de quão esparsamente as células são populadas. É definida como $\frac{1}{n_{tr}} \sum \sqrt{N_{S,u}}$, onde $N_{S,u}$ é o número de linhas em uma célula. A alta fragmentação (muitas células pequenas) aumenta o erro de estimativa e gera risco de memorização.

O score é formulado como:
$$J(\pi_S) = \widehat{\text{Risk}}_{\text{val}}(\hat{h}_S) + \lambda \Omega(T_{tr}, \pi_S)$$
onde $\lambda \geq 0$ controla o equilíbrio. Minimizar $J$ seleciona a partição que melhor se alinha com os rótulos enquanto mantém suporte suficiente para a generalização. $\Omega$ provê um limite para o erro de estimativa em um limite de generalização para classificadores constantes por célula.

Algoritmo: AUTOGRABLE

Os autores introduzem o AUTOGRABLE, um algoritmo que busca o subconjunto de atributos ótimo $S^*$ para minimizar $J$.

• Estratégia de Busca: Como encontrar o minimizador exato é NP-completo (redutível ao problema de Cobertura de Teste), o AUTOGRABLE emprega uma busca local gananciosa (Seleção de Coluna Estrutural, SCS).
• Direções: Suporta busca direta (partindo de um conjunto vazio) e busca reversa (partindo do conjunto completo).
• Codificação: Suporta duas assinaturas para pontuação:
  • Codificação de valor: Pontuações baseadas em valores específicos rastreando o rótulo.
  • Codificação de frequência: Pontuações baseadas no padrão de multiplicidade (o quão raro ou compartilhado é um valor), independente da identidade do valor específico.
• Extensão Relacional: Para esquemas de múltiplas tabelas, o algoritmo materializa uma tabela achatada via joins à esquerda ao longo de caminhos de chaves estrangeiras (colapsando duplicatas e ponderando linhas) antes de aplicar a lógica de seleção. As colunas selecionadas são então expandidas em um grafo de incidência (um grafo bipartido de linhas e nós de valor).

Principais Contribuições

1. Alinhamento como Critério: O artigo estabelece que, para aprendizes limitados por 1-WL, a construção de um grafo é equivalente a projetar uma partição de linhas. Uma construção é boa se esta partição se alinha com os rótulos, uma propriedade que pode ser verificada sem treinar uma GNN.
2. Score Livre de Treinamento: Um score $J$ inovador que avalia candidatos de grafos baseando-se apenas na partição de linhas induzida e em um preditor de bloco simples, penalizando a fragmentação. Isso evita a circularidade e o custo de treinar um modelo para cada candidato.
3. AUTOGRABLE: Um algoritmo ganancioso prático que seleciona o subconjunto de colunas para construir um grafo de incidência. Ele se aplica tanto a tabelas únicas quanto a esquemas de chaves estrangeiras e pode explicitamente declinar a construção de um grafo (retornando um grafo trivial) se nenhuma construção melhorar o score.

Resultados Experimentais

Os autores avaliam o AUTOGRABLE em três questões de pesquisa:

1. Recuperação da Verdade Fundamental (Tarefas Controladas): Em tarefas sintéticas usando o dataset Adult onde os rótulos são gerados a partir de subconjuntos de colunas específicas, o AUTOGRABLE recupera com sucesso as colunas geradoras.

   • A codificação de valor destaca-se em tarefas locais de linha (valor único, conjunção).
   • A codificação de frequência destaca-se em tarefas sensíveis à extensão (contagem, duplicata) onde a estrutura da repetição de valores importa mais do que a identidade do valor em si.
   • O parâmetro de regularização $\lambda$ filtra efetivamente colunas irrelevantes, alcançando altas taxas de recuperação "Exata".

2. Correlação com Desempenho de Jusante: Em benchmarks relacionais do mundo real (RelBench), o score $J$ atua como um filtro necessário. Embora não seja um classificador perfeito, scores baixos de $J$ são necessários para um alto AUC de jusante. O score descarta com sucesso uma grande fração de candidatos a grafos (ex: 80% em driver-top3), enquanto retém os melhores desempenhos.

3. Comparação com Baselines: Sob um preditor GraphSAGE fixo, o AUTOGRABLE supera:

   • Trivial ($\gamma_{triv}$): Sem arestas (MLP sobre características).
   • Incidência Total ($\gamma_{inc}$): Usando todas as colunas (frequentemente leva à sobrefragmentação).
   • Baseado em Esquema (REG): Usando o esqueleto bruto de chaves estrangeiras.
   • Seleção Aleatória: Selecionando colunas uniformemente ao acaso.
   • Consciente de Tarefa (auGraph): Um método que pontua atributos usando GNNs treinadas.

Crucialmente, em tarefas onde a estrutura é prejudicial (ex: study-outcome no RelBench ou tarefas i.i.d. do TabArena), o AUTOGRABLE é o único método que corretamente declina a construção de um grafo, retornando o grafo trivial e evitando a degradação de desempenho causada pela fragmentação desnecessária.

Significância e Alegações

O artigo alega mudar o paradigma da construção de tabela-para-grafo de "dependente de treinamento" para "foco na estrutura". Ao aproveitar o limite 1-WL, os autores argumentam que o valor de uma construção de grafo reside não em sua complexidade bruta, mas em como ela agrupa as linhas.

A significância do AUTOGRABLE é tripla:

1. Eficiência: Ele busca no espaço de candidatos a grafos sem treinar uma única GNN, tornando o processo de busca barato e escalável.
2. Interpretabilidade: Fornece uma explicação principista e não circular de por que um grafo ajuda (alinhamento das partições de linhas com os rótulos).
3. Adaptabilidade: É o primeiro método capaz de reconhecer quando nenhuma construção de grafo é benéfica, prevenindo a degradação de desempenho que ocorre ao forçar estruturas de grafos em dados onde preditores locais de linha são suficientes.

Os autores concluem que, para aprendizes limitados por 1-WL, a construção é o design de partição, e "mais fino não é necessariamente melhor". A construção ótima é aquela que expõe estrutura suficiente para distinguir tipos de linhas relevantes para o rótulo sem sacrificar o suporte estatístico necessário para a generalização.