Résumé Technique : Modèle Fondamental de Graphes Centrée sur la Structure via des Bases Géométriques

1. Énoncé du Problème

Les Modèles Fondamentaux de Graphes (GFMs) visent à apprendre des représentations transférables à travers divers domaines de graphes. Cependant, les approches existantes rencontrent deux limitations principales :

1. Hétérogénéité Structurelle : Les graphes varient considérablement en topologie, échelle et métriques induites d'un domaine à l'autre. Contrairement au texte ou aux images, les graphes sont des objets relationnels définis uniquement à isomorphisme près, dépourvus d'une référence géométrique partagée.
2. Incompatibilité des Caractéristiques : Les espaces de caractéristiques des nœuds diffèrent souvent en dimensionnalité et en sémantique d'un jeu de données à l'autre. Les GFMs actuels imposent généralement des dimensions de caractéristiques fixes via des projections spécifiques aux jeux de données, du remplissage (padding) ou des adaptateurs. Bien que cela aligne les espaces de caractéristiques, cela échoue à aligner les structures de graphes sous-jacentes, conduisant à des représentations qui reflètent mal la similarité intrinsèque des graphes et limitant le transfert inter-domaine.

Les alternatives existantes, telles que la tokenisation de graphes, imposent des ordonnancements artificiels sur des structures intrinsèquement non ordonnées, violant l'invariance par permutation et échouant à capturer la géométrie intrinsèque du graphe.

2. Méthodologie : SCGFM

Les auteurs proposent des Modèles Fondamentaux de Graphes Centrés sur la Structure (SCGFM), qui traitent la topologie du graphe comme la source principale de connaissances transférables. L'idée centrale consiste à modéliser les graphes comme des espaces métriques mesurés (espaces mm) et à apprendre un système de coordonnées structurelles partagé.

2.1. Perspective Géométrique

SCGFM suppose que les graphes réels se situent dans un sous-ensemble totalement borné de l'espace des espaces mm. Sur la base du théorème de compacité de Gromov, tout graphe peut être approximé par ses distances à un ensemble fini de motifs géométriques canoniques (bases).

2.2. Composantes Principales

Le cadre se compose de deux étapes : Pré-entraînement des Bases Géométriques et Projection en Aval.

A. Bases Géométriques Apprenables

SCGFM apprend un ensemble fini de $K$ bases géométriques $\{B_k\}_{k=1}^K$. Chaque base $B_k$ est définie comme un espace mm fini $( [M], d_k, \mu_k )$ :

• Métrique ($d_k$) : Représentée par une matrice symétrique et creuse apprenable $B_k \in [0, 1]^{M \times M}$, paramétrant les poids des arêtes d'une structure de graphe canonique avec $M$ nœuds.
• Mesure ($\mu_k$) : Fixée à une distribution uniforme pour assurer des couplages bien définis.

Ces bases forment collectivement un système de coordonnées structurelles partagé.

B. Alignement Structurel via Gromov–Wasserstein (GW)

Les graphes d'entrée $G$ sont alignés sur les bases en utilisant les distances de Gromov–Wasserstein (GW). Pour assurer l'évolutivité, la méthode emploie la Gromov–Wasserstein Tranchée (SGW), qui réduit la complexité computationnelle de $O(N^3)$ à quasi-linéaire $O(N \log N)$ en projetant les structures métriques sur des tranches 1D.

Pour un graphe $G$, l'écart structurel par rapport à chaque base $B_k$ est calculé comme $\delta_k = d_{GW}(G, B_k)$. Ces distances sont converties en un vecteur de coordonnées structurelles $w$ (poids) via une fonction softmax :
$$w_k = \frac{\exp(-\delta_k / \tau)}{\sum_j \exp(-\delta_j / \tau)}$$
Ce vecteur $w$ sert de représentation du graphe dans l'espace géométrique partagé.

C. Réencodage des Caractéristiques

Pour résoudre l'incompatibilité des caractéristiques sans supposer de dimensions fixes, SCGFM emploie un mécanisme de réencodage des caractéristiques conscient de la structure :

1. Plan de Transport : Le plan de transport optimal $T_{ik}$ obtenu lors du calcul GW mappe les nœuds du graphe d'entrée vers la base géométrique.
2. Projection : Les caractéristiques des nœuds sont agrégées et projetées sur les bases en utilisant $T_{ik}$, aboutissant à une matrice de caractéristiques unifiée $H(G)$.
3. Unification : Ce processus unifie les représentations de nœuds ancrées à la structure, restant agnostique à la dimensionnalité originale des caractéristiques.

D. Objectifs d'Entraînement

L'objectif de pré-entraînement minimise une somme pondérée de trois pertes :

1. Perte de Reconstruction GW ($L_{gw}$) : Minimise la distance entre le graphe d'entrée et un surrogate linéaire du barycentre GW (une combinaison pondérée de bases).
2. Perte de Reconstruction Statistique ($L_{rec}$) : Un décodeur $f(\cdot)$ reconstruit les statistiques au niveau du graphe (histogramme des degrés, clustering, motifs) à partir de $w$ pour assurer la fidélité structurelle.
3. Régularisation de Diversité ($L_{div}$) : Impose une séparation paire-à-paire entre les bases pour éviter l'effondrement et garantir qu'elles couvrent l'espace structurel.

2.3. Représentation en Aval

L'embedding final du graphe $z(G)$ est une concaténation de :

1. Coordonnées structurelles $w$.
2. Statistiques reconstruites $f(w)$.
3. Caractéristiques projetées $vec(H(G))$.

Cet embedding unifié est utilisé pour des tâches en aval (classification de nœuds ou de graphes) via un encodeur figé et un classifieur léger (par exemple, un Réseau Prototypique).

3. Contributions Clés

1. GFM Centrée sur la Structure : Un cadre novateur permettant le transfert à travers des jeux de données de graphes hétérogènes sans architectures spécifiques aux jeux de données ni prétraitement des caractéristiques, reposant plutôt sur un système de coordonnées géométriques partagé.
2. Bases Géométriques et Espace Latent : L'introduction de bases géométriques apprenables qui induisent un espace latent aligné géométriquement. Les auteurs démontrent que les distances dans cet espace corrèlent fortement avec la géométrie intrinsèque des graphes GW.
3. Flexibilité des Caractéristiques : Un mécanisme pour unifier des caractéristiques de nœuds hétérogènes par alignement structurel, éliminant le besoin de dimensions de caractéristiques fixes ou de prétraitement spécifique au domaine.
4. Garanties Théoriques : Preuve que les coordonnées structurelles apprises et les statistiques reconstruites sont lipschitziennes par rapport à la distance GW, assurant la stabilité.

4. Résultats Expérimentaux

Les auteurs ont évalué SCGFM sur 12 jeux de données couvrant 5 domaines (Molécules, Réseaux Sociaux, Académique, E-commerce, Synthétique) pour la classification au niveau du graphe et au niveau du nœud selon un protocole d'apprentissage par quelques exemples (5-shot).

• Performance : SCGFM a systématiquement surpassé des bases de référence solides, incluant des GNNs classiques (GCN, GIN, GAT), des méthodes auto-supervisées (GraphCL, GraphMAE) et des GFMs existantes (GCOPE, RiemannGFM, GIT).
  • Classification de Graphes : A atteint une précision supérieure en domaine et hors domaine, particulièrement sur le jeu de données COLORS-3 où les bases de référence se sont dégradées à des niveaux proches du hasard en raison de grands décalages structurels.
  • Classification de Nœuds : A démontré un comportement quasi-indépendant de la source. Par exemple, sur le jeu de données Reddit, la performance est restée élevée (~84 %) quel que soit le domaine de pré-entraînement, attribué à la capacité du modèle à projeter des caractéristiques sémantiques de haute dimension dans un espace où la séparabilité linéaire est garantie (Théorème de Cover).
• Évolutivité : SCGFM a évolué de manière fluide jusqu'à des graphes de 5 millions de nœuds, maintenant la consommation de mémoire de pointe la plus faible (~12 Go) parmi toutes les méthodes. Les méthodes concurrentes (GAT, GIT) ont rencontré des erreurs de mémoire insuffisante à des échelles inférieures.
• Études d'Ablation :
  • Sur des jeux de données dominés par les caractéristiques (par exemple, Cora), les caractéristiques projetées $vec(H)$ étaient critiques ; leur suppression a provoqué une chute catastrophique des performances.
  • Sur des jeux de données dominés par la structure (par exemple, PROTEINS, MUTAG), les coordonnées géométriques $w$ étaient les principaux moteurs de la performance.
  • Les pertes de reconstruction et de diversité étaient toutes deux essentielles pour un entraînement stable sur toutes les modalités.
• Interprétabilité : Les visualisations ont montré que les bases apprises se spécialisaient dans des motifs géométriques distincts (par exemple, clusters denses, motifs en anneau et queue) et évoluaient de motifs non structurés vers des primitives topologiques nettes au cours de l'entraînement.
• Isométrie : Les distances euclidiennes latentes ont montré une forte corrélation linéaire ($\rho \approx 0,70$) avec les vraies distances GW, confirmant que l'embedding préserve la géométrie intrinsèque du graphe.

5. Signification et Revendications

L'article revendique que SCGFM offre une alternative fondée sur des principes à la tokenisation de graphes et aux GFMs dépendantes du domaine. En modélisant les graphes comme des espaces métriques mesurés et en utilisant les distances GW, SCGFM découple avec succès la topologie de la sémantique.

Les auteurs soulignent que leur approche :

• Généralise de manière robuste à travers des domaines disparates sans modifications architecturales.
• Fournit une stabilité théorique grâce aux garanties de continuité lipschitzienne.
• Évolue efficacement vers des graphes massifs, surmontant les goulots d'étranglement computationnels du calcul GW exact via l'approximation SGW.
• S'adapte à la modalité de données, exploitant efficacement soit les signaux structurels, soit les signaux sémantiques selon les caractéristiques du jeu de données.

Ce travail se positionne comme une étape vers un paradigme unifié et centré sur la structure pour les modèles fondamentaux de graphes, surmontant les limitations des approches centrées sur les caractéristiques et basées sur des tokens.