Résumé Technique : FROG – Apprentissage de Structure de Graphes en Résolution Complète et Optimisable pour l'Apprentissage Profond Relationnel

1. Énoncé du Problème

L'Apprentissage Profond Relationnel (RDL) vise à effectuer une modélisation prédictive de bout en bout sur des Bases de Données Relationnelles (RDB) en les représentant sous forme de graphes et en appliquant des Réseaux de Neurones à Graphes (GNN). Cependant, les méthodes RDL existantes adhèrent généralement à un pipeline séquentiel : elles construisent d'abord un Graphe d'Entités Relationnelles (REG) basé sur un Graphe de Schéma Fixe, puis entraînent un GNN sur cette structure statique.

Les auteurs identifient une limitation critique dans ce paradigme : fixer le graphe de schéma contraint les informations accessibles lors du passage de messages, risquant de masquer des relations implicites, d'ordre supérieur ou spécifiques à la tâche. Cela soulève la question centrale : "La Fixation des Graphes de Schéma est-elle Nécessaire ?"

Le défi réside dans l'optimisation de la structure du graphe sans violer deux propriétés fondamentales des RDB :

1. Propriété de Résolution Complète : Le graphe doit encoder fidèlement chaque entité et chaque lien de clé étrangère dans la RDB. Les méthodes traditionnelles d'Apprentissage de Structure de Graphes (GSL) qui élaguent ou ajoutent des arêtes violent cette propriété car elles perdent les informations nécessaires pour récupérer de manière unique l'état original de la RDB.
2. Dépendances Fonctionnelles (FD) : Les RDB contiennent des contraintes intrinsèques où une entité détermine de manière unique une autre (par exemple, un ID d'avis détermine de manière unique un ID client). Les approches GSL standard ignorent souvent ces contraintes sémantiques, conduisant à des représentations qui violent l'intégrité logique de la base de données.

Les tentatives actuelles, telles que RDB2G, explorent différentes constructions de graphes de schéma mais reposent sur une sélection de rôles discrets et une comparaison empirique plutôt que sur une optimisation de bout en bout.

2. Méthodologie : Le Cadre FROG

Les auteurs proposent FROG (Full-Resolution and Optimizable Graph Structure Learning), un cadre qui traite l'apprentissage de la structure du graphe comme un problème de modélisation de rôles de tables apprenable. Au lieu de modifier directement les arêtes, FROG optimise les rôles que jouent les tables (en tant que nœuds ou arêtes) au sein du graphe de schéma.

2.1. Résolution Complète via les Rôles de Tables

FROG réinterprète l'apprentissage de la structure du graphe en permettant aux tables de fonctionner soit comme des nœuds, soit comme des arêtes dans le Graphe de Schéma.

• Garantie Théorique : Les auteurs prouvent (Théorème 4.1) qu'une cartographie adaptative, où les tables sont assignées soit au rôle "Table-Comme-Nœud", soit au rôle "Table-Comme-Arête", satisfait la propriété de résolution complète. Cela s'explique par le fait que la cartographie préserve tous les attributs, les directions des clés étrangères et les types d'entités, permettant la récupération unique de la RDB originale à partir du graphe.
• Avantage Théorique de l'Information : L'article démontre (Théorème 4.2) que modéliser une table comme une arête (Table-Comme-Arête) peut retenir strictement plus d'informations sur les entités sources que la modéliser comme un nœud (Table-Comme-Nœud). Dans un scénario Table-Comme-Nœud, l'information doit passer par deux étapes d'agrégation ($u \to v \to w$), risquant d'introduire une perte d'information. Dans un scénario Table-Comme-Arête, la table intermédiaire agit comme une arête directe, permettant à la cible d'accéder aux informations sources en une seule étape ($u \xrightarrow{v} w$), évitant ainsi les goulots d'étranglement d'agrégation intermédiaires.

2.2. Passage de Messages Piloté par les Relations

Pour gérer la complexité des tables agissant comme des arêtes, FROG introduit des mécanismes spécifiques de passage de messages pour deux paradigmes relationnels :

1. Co-occurrence ($u \leftarrow v \rightarrow w$) : Modélise des rôles symétriques où $u$ et $w$ apparaissent ensemble dans $v$ (par exemple, Utilisateur $\leftarrow$ Avis $\rightarrow$ Produit). Le message agrège les caractéristiques de $u$, $v$ et $w$ pour capturer la co-occurrence conjointe.
2. Complétion ($u \rightarrow v \rightarrow w$) : Modélise une relation médiatisée où $v$ module l'influence de $u$ sur $w$ (par exemple, Classement $\rightarrow$ Course $\rightarrow$ Circuit). Le message utilise un mécanisme de porte (gating) pour moduler l'influence de l'entité intermédiaire.

Un modèle de porte conscient du rôle ($M_{att}$) est employé pour équilibrer de manière adaptative le flux d'information provenant des chemins Table-Comme-Nœud et Table-Comme-Arête. Cette porte est lissée à l'aide d'une Moyenne Mobile Exponentielle (EMA) pour stabiliser l'entraînement, permettant au modèle d'apprendre le rôle optimal pour chaque table sous des relations spécifiques.

2.3. Contraintes de Dépendance Fonctionnelle (FD)

Pour garantir que les représentations apprises respectent les contraintes sémantiques de la RDB, FROG introduit une Perte de Dépendance Fonctionnelle ($\mathcal{L}_{FD}$) optimisée de manière alternée avec le GNN. Cette perte opère à deux niveaux :

• Niveau Table ($\mathcal{L}_{emb}$) : Régularise l'espace d'incrustation (embedding) en imposant que les vecteurs de différence entre les entités liées par la même relation de table résident dans un sous-espace de faible dimension partagé. Cela capture des motifs de transformation cohérents à travers la table.
• Niveau Entité ($\mathcal{L}_{pair}$) : Utilise un objectif contrastif (InfoNCE) pour s'assurer que les paires d'entités satisfaisant une dépendance fonctionnelle (paires positives) sont notées plus haut que celles qui ne le font pas (paires négatives).

La perte totale est définie comme $\mathcal{L}_{main} = \mathcal{L}_{task} + \beta\mathcal{L}_{emb} + \gamma\mathcal{L}_{pair}$.

3. Contributions Clés

1. Apprentissage de Structure de Graphes en Résolution Complète : Cet article est le premier à introduire le GSL dans le RDL tout en préservant strictement la propriété de résolution complète. Il formalise cela d'un point de vue théorique de l'information et prouve que l'élagage ou l'ajout d'arêtes viole cette propriété, tandis que l'optimisation des rôles de tables ne le fait pas.
2. Modélisation Adaptative des Rôles de Tables : Le cadre optimise les rôles de tables (Nœud vs Arête) de manière apprenable et continue plutôt que par sélection discrète. Il fournit une base théorique expliquant pourquoi la modélisation Table-Comme-Arête peut être supérieure pour retenir les dépendances à long terme.
3. Espace d'Incrustation Contraint par les FD : La conception de la perte FD ($\mathcal{L}_{FD}$) garantit que les représentations de graphes apprises respectent intrinsèquement les dépendances fonctionnelles et les contraintes structurelles de la RDB sous-jacente.
4. Validation Empirique Complète : Des expériences extensives sur le benchmark RelBench (6 jeux de données, 23 tâches) démontrent que FROG surpasse les bases de référence existantes, y compris les méthodes statistiques, LightGBM et les modèles RDL de pointe comme RelGNN.

4. Résultats Expérimentaux

Les auteurs ont évalué FROG sur 23 tâches en aval à travers 6 jeux de données réels (par exemple, rel-avito, rel-event, rel-hm, rel-trial).

• Performance : FROG a obtenu des résultats de pointe ou compétitifs sur les tâches de Classification d'Entités, de Régression et de Recommandation. Par exemple, sur la tâche user-repeat (rel-event), FROG a atteint un ROC-AUC de 79,11, surpassant RelGNN (78,15) et RDL (75,90).
• Études d'Ablation :
  • Modélisation des Rôles : L'étude a confirmé que le rôle optimal (Nœud vs Arête) varie selon la tâche et le jeu de données. Cependant, l'approche d'apprentissage adaptatif a constamment surpassé les stratégies fixes (tout-nœud ou tout-arête), validant la nécessité de l'optimisation de la structure.
  • Contraintes FD : La suppression des composantes de perte FD ($\mathcal{L}_{emb}$ et $\mathcal{L}_{pair}$) a entraîné une dégradation des performances dans la plupart des tâches, confirmant que l'imposition des dépendances fonctionnelles améliore la qualité de la représentation.
• Insights Structurels : L'analyse des structures apprises a révélé que les tables intermédiaires dans les paradigmes de Co-occurrence tendent à être modélisées comme des nœuds pour la classification/régression mais comme des arêtes pour la prédiction de liens. De plus, les structures apprises ont montré une transférabilité entre les tâches, suggérant que le modèle capture des caractéristiques structurelles partagées.

5. Signification et Revendications

L'article revendique offrir une nouvelle perspective sur la construction de graphes pour le RDL. En remettant en question la nécessité des graphes de schéma fixes, FROG démontre que les structures de graphes peuvent et doivent évoluer conjointement avec les représentations GNN pour mieux capturer les sémantiques relationnelles.

Les auteurs soulignent que leur approche n'est pas simplement une amélioration des performances mais un changement méthodologique :

• Elle résout la tension entre l'optimisation de la structure du graphe et la préservation de l'intégrité des données (résolution complète et FD).
• Elle fournit une base théorique pour la modélisation Table-Comme-Arête, montrant son avantage théorique de l'information par rapport à l'agrégation basée sur les nœuds traditionnelle.
• Elle offre un cadre où le "schéma" n'est plus une entrée statique mais un composant apprenable qui s'adapte aux motifs relationnels spécifiques requis par les tâches en aval.

L'ouvrage conclut que, bien que FROG engendre des coûts de calcul plus élevés en raison des calculs de chemins à deux sauts, les gains dans la modélisation de dépendances relationnelles complexes justifient cette surcharge, en particulier pour les tâches impliquant des interactions multi-sauts.