Sintesi Tecnica: AutoGrable

Definizione del Problema

L'apprendimento su grafi, in particolare tramite le Reti Neurali su Grafi a Passaggio di Messaggi (MPNN), presuppone l'esistenza di una struttura a grafo. Tuttavia, i formati di dati dominanti nell'apprendimento automatico applicato — tabelle singole e database relazionali collegati da chiavi esterne — non possiedono intrinsecamente una rappresentazione a grafo. Applicare le GNN a tali dati richiede una fase di costruzione in cui si deve decidere quali entità diventano nodi, quali connettere e attraverso quali relazioni.

Gli approcci attuali a questo problema sono limitati:

1. Imparare un grafo: Inferire una vicinanza "soft" dalle caratteristiche insieme al modello. Ciò presuppone che la struttura implichi una prossimità geometrica, cosa che le tabelle non forniscono (la loro relazione nativa è il valore categorico condiviso).
2. Costruire un grafo: Fissare uno scheletro di schema o valutare gli attributi in base all'accuratezza di un modello addestrato. Questo è circolare (richiede un ciclo di addestramento per ogni candidato), computazionalmente costoso e non spiega perché una specifica costruzione aiuti l'apprendente.

Il documento affronta la domanda fondamentale: Quando un grafo non è dato, cosa costituisce un "buon" grafo per una tabella, e come può essere costruito senza addestrare un modello?

Metodologia

Fondamento Teorico: 1-WL e Allineamento delle Partizioni

Gli autori fondano il loro approamo nei limiti del potere espressivo delle MPNN, che sono vincolate dal test di Weisfeiler–Leman unidimensionale (1-WL, color refinement). Per una GNN, un grafo costruito da una tabella effettivamente ordina le righe della tabella in classi di colore 1-WL. Il modello non può distinguere tra righe assegnate allo stesso colore.

Pertanto, una costruzione di grafo è "buona" per un compito se la partizione indotta delle righe si allinea con le etichette del compito:

• Le righe con etichette diverse dovrebbero appartenere a classi di colore diverse.
• Le righe con la stessa etichetta non dovrebbero essere separate inutilmente (evitando la sovra-frammentazione).

Questo criterio di allineamento può essere valutato prima di qualsiasi addestramento del modello.

Il Punteggio di Allineamento ($J$)

Per operazionalizzare questo criterio, il documento propone un punteggio $J$ privo di addestramento per un sottoinsieme candidato di attributi $S$. Il punteggio bilancia due fattori competitivi:

1. Guadagno Predittivo (Allineamento): Misurato dalla perdita di validazione di un semplice "predittore a blocchi" ($\hat{h}_S$) che è costante sulle celle definite da $S$. Questo predittore utilizza la distribuzione empirica delle etichette delle righe di training all'interno di ogni cella.
2. Penalità di Frammentazione ($\Omega$): Una misura di quanto sottilmente siano popolate le celle. È definita come $\frac{1}{n_{tr}} \sum \sqrt{N_{S,u}}$, dove $N_{S,u}$ è il numero di righe in una cella. L'alta frammentazione (molte piccole celle) aumenta l'errore di stima e rischia la memorizzazione.

Il punteggio è formulato come:
$$J(\pi_S) = \widehat{\text{Risk}}_{\text{val}}(\hat{h}_S) + \lambda \Omega(T_{tr}, \pi_S)$$
dove $\lambda \geq 0$ controlla il compromesso. Minimizzare $J$ seleziona la partizione che meglio si allinea con le etichette mantenendo al contempo un supporto sufficiente per la generalizzazione. L'analisi teorica mostra che $\Omega$ limita l'errore di stima in un limite di generalizzazione per classificatori costanti sulle celle.

Algoritmo: AUTOGRABLE

Gli autori introducono AUTOGRABLE, un algoritmo che cerca il sottoinsieme di attributi ottimale $S^*$ per minimizzare $J$.

• Strategia di Ricerca: Poiché trovare l'esatto minimizzatore è NP-completo (riducibile al problema del Test Cover), AUTOGRABLE impiega una ricerca locale greedy (Structural Column Selection, SCS).
• Direzioni: Supporta la ricerca in avanti (partendo da un insieme vuoto) e la ricerca all'indietro (partendo dall'insieme completo).
• Codifica: Supporta due firme per il punteggio:
  • Codifica dei valori (Value encoding): Punteggi basati su valori specifici che tracciano l'etichetta.
  • Codifica delle frequenze (Frequency encoding): Punteggi basati sul pattern di molteplicità (quanto un valore è raro o condiviso), indipendentemente dall'identità del valore specifico.
• Estensione Relazionale: Per schemi multi-tabella, l'algoritmo materializza una tabella piatta tramite left join lungo i percorsi di foreign-key (collassando i duplicati e pesando le righe) prima di applicare la logica di selezione. Le colonne selezionate vengono poi espanse in un incidenza grable (un grafo bipartito di righe e nodi di valore).

Contributi Chiave

1. L'Allineamento come Criterio: Il documento stabilisce che per gli apprendenti vincolati da 1-WL, la costruzione del grafo è equivalente al design di una partizione delle righe. Una costruzione è buona se questa partizione si allinea con le etichette, una proprietà che può essere verificata senza addestrare una GNN.
2. Punteggio Training-Free: Un nuovo punteggio $J$ che valuta i candidati grafi esclusivamente sulla base della partizione delle righe indotta e di un semplice predittore a blocchi, penalizzando la frammentazione. Ciò evita la circolarità e il costo di addestrare un modello per ogni candidato.
3. AUTOGRABLE: Un algoritmo greedy pratico che seleziona il sottoinsieme di colonne ottimale per costruire un incidenza grable. Si applica sia a tabelle singole che a schemi a chiavi esterne e può esplicitamente rifiutarsi di costruire un grafo (restituendo un grafo banale) se nessuna costruzione migliora il punteggio.

Risultati Sperimentali

Gli autori valutano AUTOGRABLE su tre domande di ricerca:

1. Recupero della Verità Fondamentale (Compiti Controllati): Su compiti sintetici utilizzando il dataset Adult, dove le etichette sono generate da specifici sottoinsiemi di colonne, AUTOGRABLE recupera con successo le colonne generatrici.

   • La codifica dei valori eccelle nei compiti locali della riga (singolo valore, congiunzione).
   • La codifica delle frequenze eccelle nei compiti sensibili all'estensione (conteggio, duplicato) dove la struttura della ripetizione del valore conta più dell'identità del valore stesso.
   • Il parametro di regolarizzazione $\lambda$ filtra efficacemente le colonne irrilevanti, raggiungendo alti tassi di recupero "Esatto".

2. Correlazione con le Prestazioni a Valle: Su benchmark relazionali reali (RelBench), il punteggio $J$ agisce come un filtro necessario. Sebbene non sia un ranker perfetto, i bassi punteggi $J$ sono necessari per un alto AUC a valle. Il punteggio scarta con successo una grande frazione di grafi candidati (ad esempio, l'80% su driver-top3) pur mantenendo quelli con le migliori prestazioni.

3. Confronto con i Baseline: Sotto un predittore GraphSAGE fisso, AUTOGRABLE supera:

   • Trivial ($\gamma_{triv}$): Nessun arco (MLP sulle caratteristiche).
   • Full Incidence ($\gamma_{inc}$): Utilizzo di tutte le colonne (spesso porta alla sovra-frammentazione).
   • Schema-based (REG): Utilizzo dello scheletro originale delle foreign-key.
   • Random Selection: Selezione delle colonne uniformemente a caso.
   • Task-Aware (auGraph): Un metodo che valuta gli attributi utilizzando GNN addestrate.

Fondamentalmente, nei compiti in cui la struttura è deleteria (ad esempio, study-outcome in RelBench o compiti i.i.d. di TabArena), AUTOGRABLE è l'unico metodo che rifiuta correttamente di costruire un grafo, restituendo il grafo banale ed evitando il degrado delle prestazioni causato dalla frammentazione non necessaria.

Significato e Rivendicazioni

Il documento sostiene che sposti il paradigma della costruzione da tabella-a-grafo da "dipendente dall'addestramento" a "orientato alla struttura". Sfruttando il limite 1-WL, gli autori sostengono che il valore di una costruzione non risiede nella sua pura complessità, ma nel modo in cui raggruppa le righe.

La significatività di AUTOGRABLE è triplice:

1. Efficienza: Cerca nello spazio dei grafi candidati senza addestrare una singola GNN, rendendo il processo di ricerca economico e scalabile.
2. Interpretabilità: Fornisce una spiegazione non circolare e basata su principi del perché un grafo aiuti (allineamento delle partizioni delle righe con le etichette).
3. Adattabilità: È il primo metodo capace di riconoscere quando nessuna costruzione di grafo è benefica, evitando il degrado delle prestazioni che si verifica forzando strutture grafiche su dati dove i predittori locali della riga sono sufficienti.

Gli autori concludono che per gli apprendenti vincolati da 1-WL, la costruzione è design di partizione, e che "più fine non è necessariamente meglio". La costruzione ottimale è quella che espone la struttura minima necessaria per distinguere i tipi di riga rilevanti per l'etichetta senza sacrificare il supporto statistico necessario per la generalizzazione.