Résumé Technique : AutoGrable

Énoncé du Problème

L'apprentissage sur graphes, particulièrement via les réseaux de neurones sur graphes à passage de messages (MPNN), présuppose l'existence d'une structure de graphe. Cependant, les formats de données dominants dans l'apprentissage automatique appliqué — tables uniques et bases de données relationnelles liées par des clés étrangères — ne possèdent pas intrinsèquement de représentation de graphe. Appliquer des GNN à ces données nécessite une phase de construction où l'on doit décider quels entités deviennent des nœuds, lesquels connecter, et à travers quelles relations.

Les approches actuelles pour résoudre ce problème sont limitées :

1. Apprendre un graphe : Inférer une adjacence "douce" à partir des caractéristiques conjointement avec le modèle. Cela suppose que la structure implique une proximité géométrique, ce que les tables ne fournissent pas (leur relation native est basée sur des valeurs catégorielles partagées).
2. Construire un graphe : Fixer un squelette de schéma ou évaluer les attributs en fonction de la précision d'un modèle entraîné. C'est un processus circulaire (nécessitant un cycle d'entraînement par candidat), coûteux en calcul, et qui échoue à expliquer pourquoi une construction spécifique aide l'apprenant.

Le papier traite de la question fondamentale suivante : Lorsqu'un graphe n'est pas donné, qu'est-ce qui constitue un "bon" graphe pour une table, et comment peut-il être construit sans entraîner de modèle ?

Méthodologie

Fondement Théorique : 1-WL et Alignement de Partition

Les auteurs fondent leur approche sur les limites de puissance expressive des MPNN, qui sont bornées par le test de Weisfeiler–Leman unidimensionnel (1-WL, raffinement de couleurs). Pour un GNN, un graphe construit à partir d'une table revient effectivement à trier les lignes de la table en classes de couleurs 1-WL. Le modèle ne peut pas distinguer les lignes assignées à la même couleur.

Par conséquent, une construction de graphe est "bonne" pour une tâche si la partition induite des lignes s'aligne avec les étiquettes de la tâche :

• Les lignes ayant des étiquettes différentes doivent tomber dans des classes de couleurs différentes.
• Les lignes ayant la même étiquette ne doivent pas être divisées inutilement (éviter la sur-fragmentation).

Ce critère d'alignement peut être évalué avant tout entraînement de modèle.

Le Score d'Alignement ($J$)

Pour opérationnaliser ce critère, le papier propose un score $J$ sans entraînement pour un sous-ensemble d'attributs candidats $S$. Le score équilibre deux facteurs concurrents :

1. Gain Prédictif (Alignement) : Mesuré par la perte de validation d'un "prédicteur de bloc" simple ($\hat{h}_S$) qui est constant sur les cellules définies par $S$. Ce prédicteur utilise la distribution empirique des étiquettes des lignes d'entraînement au sein de chaque cellule.
2. Pénalité de Fragmentation ($\Omega$) : Une mesure de la minceur de la population des cellules. Elle est définie par $\frac{1}{n_{tr}} \sum \sqrt{N_{S,u}}$, où $N_{S,u}$ est le nombre de lignes dans une cellule. Une fragmentation élevée (nombreuses petites cellules) augmente l'erreur d'estimation et risque la mémorisation.

Le score est formulé comme suit :
$$J(\pi_S) = \widehat{\text{Risk}}_{\text{val}}(\hat{h}_S) + \lambda \Omega(T_{tr}, \pi_S)$$
où $\lambda \geq 0$ contrôle le compromis. Minimiser $J$ permet de sélectionner la partition qui s'aligne le mieux avec les étiquettes tout en maintenant un support suffisant pour la généralisation. L'analyse théorique montre que $\Omega$ borne l'erreur d'estimation dans une borne de généralisation pour les classificateurs constants par cellule.

Algorithme : AUTOGRABLE

Les auteurs introduisent AUTOGRABLE, un algorithme qui recherche le sous-ensemble d'attributs optimal $S^*$ pour minimiser $J$.

• Stratégie de Recherche : Puisque trouver le minimiseur exact est NP-complet (réductible au problème du Test Cover), AUTOGRABLE emploie une recherche locale gourmande (Structural Column Selection, SCS).
• Directions : Il supporte la recherche vers l'avant (en partant d'un ensemble vide) et la recherche vers l'arrière (en partant de l'ensemble complet).
• Encodage : Il supporte deux signatures pour le scoring :
  • Encodage de valeur : Scores basés sur des valeurs spécifiques suivant l'étiquette.
  • Encodage de fréquence : Scores basés sur le motif de multiplicité (combien une valeur est rare ou partagée), indépendamment de l'identité de la valeur elle-même.
• Extension Relationnelle : Pour les schémas multi-tables, l'algorithme matérialise une table aplatie via des jointures à gauche le long des chemins de clés étrangères (en réduisant les doublons et en pondérant les lignes) avant d'appliquer la logique de sélection. Les colonnes sélectionnées sont ensuite développées en un graphe d'incidence (un graphe biparti de lignes et de nœuds de valeurs).

Contributions Clés

1. L'Alignement comme Critère : Le papier établit que pour les apprenants bornés par 1-WL, la construction de graphe est équivalente à la conception d'une partition de lignes. Une construction est bonne si cette partition s'aligne avec les étiquettes, une propriété qui peut être vérifiée sans entraîner de GNN.
2. Score Sans Entraînement : Un score $J$ novateur qui évalue les graphes candidats uniquement sur la partition de lignes induite et un prédicteur de bloc simple, en pénalisant la fragmentation. Cela évite la circularité et le coût de l'entraînement d'un modèle pour chaque candidat.
3. AUTOGRABLE : Un algorithme gourmand pratique qui sélectionne le sous-ensemble de colonnes optimal pour construire un graphe d'incidence. Il s'applique aux tables uniques ainsi qu'aux schémas à clés étrangères et peut explicitement refuser de construire un graphe (en retournant un graphe trivial) si aucune construction n'améliore le score.

Résultats Expérimentaux

Les auteurs évaluent AUTOGRABLE sur trois questions de recherche :

1. Récupération de la Vérité de Terrain (Tâches Contrôlées) : Sur des tâches synthétiques utilisant le jeu de données Adult où les étiquettes sont générées à partir de sous-ensembles de colonnes spécifiques, AUTOGRLE récupère avec succès les colonnes génératrices.

   • L'encodage de valeur excelle dans les tâches locales aux lignes (conjonction, valeur unique).
   • L'encodage de fréquence excelle dans les tâches sensibles à l'extension (compte, doublon) où la structure de la répétition des valeurs importe plus que l'identité de la valeur elle-même.
   • Le paramètre de régularisation $\lambda$ filtre efficacement les colonnes non pertinentes, atteignant des taux de récupération "Exacte" élevés.

2. Corrélation avec la Performance Aval : Sur des benchmarks relationnels réels (RelBench), le score $J$ agit comme un filtre nécessaire. Bien qu'il ne soit pas un classificateur parfait, les scores $J$ faibles sont nécessaires pour obtenir un AUC élevé en aval. Le score parvient à écarter une grande partie des graphes candidats (par exemple, 80 % sur driver-top3) tout en conservant les plus performants.

3. Comparaison avec les Baselines : Sous un prédicteur GraphSAGE fixe, AUTOGRABLE surpasse :

   • Trivial ($\gamma_{triv}$) : Pas d'arêtes (MLP sur les caractéristiques).
   • Incidence Totale ($\gamma_{inc}$) : Utilisation de toutes les colonnes (conduit souvent à une sur-fragmentation).
   • Basé sur le Schéma (REG) : Utilisation du squelette brut des clés étrangères.
   • Sélection Aléatoire : Sélection de colonnes de manière uniforme.
   • Sensible à la Tâche (auGraph) : Une méthode qui évalue les attributs en utilisant des GNN entraînés.

Crucialement, sur les tâches où la structure est préjudiciable (ex: study-outcome dans RelBench ou les tâches i.i.d. de TabArena), AUTOGRABLE est la seule méthode capable de décliner correctement la construction d'un graphe, en retournant le graphe trivial et en évitant la dégradation de performance causée par une fragmentation inutile.

Signification et Revendications

Le papier prétend déplacer le paradigme de la construction table-vers-graphe de "dépendant de l'entraînement" vers "priorité à la structure". En exploitant la borne 1-WL, les auteurs soutiennent que la valeur d'une construction de graphe ne réside pas dans sa complexité brute, mais dans la manière dont elle regroupe les lignes.

La signification d'AUTOGRABLE est triple :

1. Efficacité : Il recherche l'espace des graphes candidats sans entraîner un seul GNN, rendant le processus de recherche peu coûteux et scalable.
2. Interprétabilité : Il fournit une explication fondée et non circulaire sur la raison pour laquelle un graphe est utile (alignement des partitions de lignes avec les étiquettes).
3. Adaptabilité : C'est la première méthode capable de reconnaître quand aucune construction de graphe n'est bénéfique, évitant ainsi la dégradation de performance qui survient lorsqu'on force des structures de graphes sur des données où des prédicteurs locaux aux lignes sont suffisants.

Les auteurs concluent que pour les apprenants bornés par 1-WL, la construction est une conception de partition, et que "plus fin n'est pas nécessairement meilleur". La construction optimale est celle qui expose juste assez de structure pour distinguer les types de lignes pertinents pour l'étiquette sans sacrifier le support statistique nécessaire à la généralisation.