Invariant-Stratified Propagation for Expressive Graph Neural Networks

Cet article présente l'Invariance-Stratifiée de Propagation (ISP), un cadre théorique et pratique qui surpasse les limites des réseaux de neurones graphiques standards en stratifiant les nœuds selon des invariants pour capturer l'hétérogénéité structurelle et améliorer l'expressivité au-delà du test 1-WL.

L'essentiel

Imaginez que vous essayez de comprendre une grande ville en regardant uniquement la liste des rues où chaque personne habite. C'est un peu ce que font les réseaux de neurones graphiques classiques (les GNN) lorsqu'ils analysent des réseaux sociaux, des molécules chimiques ou des systèmes de recommandation.

Le problème ? Deux personnes peuvent habiter dans des rues très différentes, mais avoir exactement le même nombre de voisins immédiats. Pour l'ordinateur classique, ces deux personnes sont identiques, même si l'une est un maire très influent et l'autre un simple résident. C'est comme si l'ordinateur ne voyait que le nombre de portes dans une maison, sans jamais regarder à quoi ressemble le quartier.

Voici l'histoire de la nouvelle méthode proposée par les auteurs : la Propagation Stratifiée par Invariants (ISP).

1. Le Problème : La "Cécité" des Voisins

Les méthodes actuelles sont comme un photographe qui ne prendrait que des photos de la porte d'entrée de chaque maison. Si deux maisons ont le même nombre de fenêtres et la même couleur de porte, le photographe dit : "Ce sont les mêmes".
Mais dans la réalité, une maison peut être au centre d'un quartier animé (un "hub"), tandis que l'autre est isolée dans une impasse. Les méthodes classiques ratent ces détails cruciaux. Elles sont limitées par une règle mathématique appelée "test 1-WL", qui est un peu comme une règle de trois : si le nombre de voisins est le même, c'est pareil.

2. La Solution : Le Système de "Niveaux" (Stratification)

Les auteurs ont eu une idée brillante : au lieu de traiter tout le monde en même temps, pourquoi ne pas organiser les gens par niveaux d'importance ou de rôle structural ?

Imaginez que vous organisez une grande fête.

• L'ancienne méthode : Tout le monde entre dans la salle en même temps et se mélange. On ne sait pas qui parle à qui.
• La méthode ISP : On invite les gens par groupes, du plus "périphérique" au plus "central".
  • D'abord, on fait entrer les gens qui sont au bord de la fête (les feuilles de l'arbre).
  • Ensuite, on fait entrer ceux qui sont un peu plus au centre.
  • Enfin, on fait entrer les organisateurs et les célébrités au cœur de la fête.

C'est ce qu'on appelle la stratification. Chaque personne reçoit une "étiquette" (un invariant) basée sur sa position réelle dans le réseau (son nombre de connexions, son rôle dans des groupes de trois, etc.).

3. Le Détecteur de "Triangles" (L'Analogie du Trio)

Pour comprendre pourquoi une personne est importante, il ne suffit pas de regarder ses voisins, il faut regarder qui sont les amis de ses amis.

Dans la vie, si vous êtes ami avec deux personnes qui ne se connaissent pas, c'est différent de si vous êtes ami avec deux personnes qui sont elles-mêmes très proches.

• L'ancienne méthode : Elle dit "J'ai deux amis". Point.
• La méthode ISP : Elle regarde le "triangle" formé par vous et vos deux amis. Elle mesure l'écart entre votre niveau et le leur.
  • Exemple : Si vous êtes un "chef" (niveau 10) et que vous parlez à deux "stagiaires" (niveau 2), le décalage est énorme.
  • Si vous êtes un "stagiaire" (niveau 2) et que vous parlez à deux autres "stagiaires" (niveau 2), le décalage est nul.

La méthode ISP calcule ces écarts (les "gaps") pour créer une empreinte digitale unique pour chaque personne, même si elles ont le même nombre de voisins.

4. Pourquoi c'est génial ? (Les Avantages)

• Plus intelligent sans être plus lent : Habituellement, pour être plus intelligent, il faut faire des calculs énormes (comme essayer de lire tous les livres de la bibliothèque). Ici, l'astuce permet d'être très intelligent tout en restant rapide, comme un détective qui sait exactement où regarder.
• Pas de confusion en profondeur : Quand on empile trop de couches de calcul (comme dans un gâteau trop haut), les informations finissent par se mélanger et tout devient gris (on appelle ça le "sur-lissage"). ISP agit comme une ancre. Même si le gâteau devient très haut, l'ancre (l'information de base sur le rôle de la personne) reste visible et empêche tout de se confondre.
• Adaptatif : La méthode peut apprendre à choisir elle-même quels critères utiliser pour classer les gens, selon la tâche à accomplir (prédire une maladie, analyser un réseau social, etc.).

En Résumé

Imaginez que vous essayez de résoudre un mystère.

• Les détectives classiques regardent juste : "Qui a rencontré qui ?"
• Les détectives ISP regardent : "Qui a rencontré qui, et quel est le statut social de chacun dans cette rencontre ?"

Grâce à cette approche, l'ordinateur ne se contente plus de compter les voisins. Il comprend la structure, la hiérarchie et les rôles cachés dans le réseau. C'est comme passer d'une photo en noir et blanc floue à une vidéo en haute définition où chaque personnage a son propre costume et son propre rôle dans l'histoire.

Les tests ont montré que cette méthode bat les records précédents pour classer des molécules, prédire l'influence dans les réseaux sociaux et comprendre des structures complexes, le tout sans ralentir l'ordinateur. C'est une avancée majeure pour donner aux machines une véritable "intelligence structurelle".

Résumé technique

1. Problématique et Contexte

Les Réseaux de Neurones sur Graphes (GNN) basés sur le mécanisme de passage de messages (Message Passing) souffrent de limitations fondamentales en matière d'expressivité et de capacité à capturer l'hétérogénéité structurelle :

• Limitation du test 1-WL : Les GNN standards sont bornés par le test de Weisfeiler-Leman de dimension 1 (1-WL). Ils ne peuvent distinguer des graphes que par leurs séquences de degrés locaux. Deux nœuds ayant des motifs locaux identiques reçoivent des représentations indistinguables, même si leurs rôles globaux diffèrent.
• Coût computationnel des méthodes expressives : Les méthodes visant à dépasser le 1-WL (comme les variantes $k$-WL ou l'énumération de sous-graphes) offrent une meilleure expressivité mais engendrent des coûts computationnels prohibitifs qui ne scalent pas bien sur les grands graphes.
• Hétérogénéité structurelle ignorée : Les GNN standards agrègent l'information de manière uniforme depuis tous les voisins. Ils échouent à capturer comment les nœuds occupent des positions structurelles différentes au sein de motifs d'ordre supérieur (comme les triangles), traitant des interactions où les participants ont des rôles très différents de la même manière.
• Encodage statique : Les méthodes actuelles utilisent souvent des encodages structurels fixes (positionnels, géométriques) qui ne s'adaptent pas dynamiquement aux exigences spécifiques d'une tâche ou aux caractéristiques des données.

2. Méthodologie : ISP (Invariant-Stratified Propagation)

Les auteurs proposent un cadre unifié nommé ISP, composé d'un variant du test WL (ISP-WL) et de son implémentation neuronale efficace (ISP-GNN). L'idée centrale est la stratification des nœuds basée sur des invariants de graphes.

A. Le Concept de Stratification

Au lieu de traiter tous les nœuds de manière synchrone, ISP classe les nœuds en couches hiérarchiques (strates) selon la valeur de leurs invariants de graphes (ex: degré, nombre de cœur, décomposition oignon, centralité).

• Invariants : Ce sont des fonctions $\mu: V \to \mathbb{R}$ invariantes par isomorphisme de graphe.
• Stratification ($\phi$) : Les nœuds sont ordonnés selon la valeur de leurs invariants, créant $L$ couches distinctes.

B. ISP-WL (Algorithme de Raffinement de Couleurs)

C'est une variante du test 1-WL qui intègre la stratification :

1. Flux WL : Suit le raffinement standard 1-WL.
2. Flux ISP : Traite les nœuds couche par couche (de $\ell=1$ à $L$).
   • Lorsqu'un nœud $v$ est traité à sa couche $\phi(v)$, son "couleur ISP" est calculée une seule fois et reste fixe par la suite (propriété d'assignation unique).
   • Encodage de l'Hétérogénéité Hiérarchique : Pour chaque interaction d'ordre supérieur (triangle $(v, u, w)$), le calcul prend en compte les écarts de rangs entre les nœuds :
     • $\delta_1$ : Écart maximal entre le centre et ses voisins (rôle de hub vs périphérique).
     • $\delta_2$ : Écart minimal (proximité structurelle).
     • $\delta_3$ : Écart entre les deux voisins (homogénéité des voisins).
   • Ces écats permettent de distinguer des triangles structurellement différents même si les degrés sont identiques.

C. ISP-GNN (Implémentation Neuronale)

C'est l'architecture de réseau de neurones qui implémente les principes d'ISP-WL de manière différentiable :

• Architecture Dual-Stream : Maintient deux flux de caractéristiques : un flux WL (standard) et un flux ISP (structurel).
• Mécanisme de Gating (Porte) : Un mécanisme de porte assure que les caractéristiques ISP d'un nœud sont assignées exactement une fois, à la couche correspondant à son invariant, évitant le sur-écritage.
• Invariants Apprenables : Le cadre permet d'utiliser des invariants prédéfinis (fixes) ou d'apprendre une stratification adaptative ($\phi_{learn}$) via un MLP combinant plusieurs invariants de base, optimisée par rétropropagation.
• Résistance au Sur-lissage (Oversmoothing) : Grâce à la persistance des caractéristiques ISP (une fois assignées, elles ne changent plus), le modèle maintient la distinguabilité des nœuds même dans des réseaux profonds, évitant l'effondrement des représentations.

3. Contributions Clés

1. Cadre ISP : Une méthode unifiée qui surpasse le 1-WL tout en restant computationnellement efficace sur les graphes clairsemés (complexité similaire au 1-WL pour les graphes à dégénérescence bornée).
2. Encodage de l'Hétérogénéité Structurelle : Une nouvelle méthode pour quantifier les différences de positions structurelles dans les motifs d'ordre supérieur (triangles), distinguant les interactions hétérogènes des interactions uniformes.
3. Théorie Solide :
   • Preuve que ISP-WL est strictement plus expressif que le 1-WL.
   • Garanties de convergence (au plus $\max(K_{WL}, L)$ itérations).
   • Preuve de résistance au sur-lissage grâce aux embeddings structurels invariants en profondeur.
4. Flexibilité : Support des invariants prédéfinis et apprenables, permettant une découverte adaptative des structures pertinentes pour la tâche.

4. Résultats Expérimentaux

Les auteurs ont évalué ISP-GNN sur une large gamme de tâches et de jeux de données :

• Classification de Graphes : Sur 9 benchmarks (TU Dataset, OGB), ISP-GNN surpasse systématiquement les architectures standards (GIN, GCN) et les méthodes expressives de l'état de l'art (ID-GNN, DropGNN, etc.). La variante avec invariants apprenables ($ISP\text{-}GNN^\dagger$) obtient les meilleures performances sur la majorité des jeux de données.
• Estimation d'Influence : Sur des réseaux sociaux réels, le modèle capture mieux la dynamique de cascade (modèles IC, LT, SIS) que les méthodes spécialisées, grâce à l'encodage hiérarchique des structures.
• Classification de Nœuds : Des améliorations significatives sont observées, en particulier sur les graphes hétérophiles (où les voisins ont souvent des labels différents), là où les GNN standards échouent.
• Analyse de Sur-lissage : Les expériences montrent que ISP-GNN maintient ses performances sur des architectures très profondes (jusqu'à 64 couches), là où les modèles de base (GCN, GAT) s'effondrent.
• Évolutivité (Scalability) : Sur le jeu de données massif ogbg-molpcba (437k graphes), ISP-GNN reste tractable. La variante basée sur le degré ajoute seulement 26% de surcharge par rapport à GIN, tandis que les variantes plus complexes (K-Core, Onion) offrent un compromis entre coût et expressivité.
• Expressivité Théorique : Sur le benchmark BREC, ISP-WL distingue plus de paires de graphes que le 1-WL et le SPD-WL, avec un temps de calcul bien inférieur à celui du 3-WL.

5. Signification et Impact

Ce travail est significatif car il résout le compromis classique entre expressivité et efficacité computationnelle dans les GNN.

• Au-delà du 1-WL sans coût exponentiel : ISP offre une expressivité supérieure au 1-WL (capable de distinguer des graphes isospectraux ou ayant les mêmes séquences de degrés) sans recourir à l'énumération coûteuse de sous-graphes ou aux calculs de $k$-WL ($k>1$).
• Interprétabilité Structurelle : En stratifiant les nœuds, le modèle devient capable de "comprendre" la hiérarchie et les rôles structurels (cœur, périphérie, ponts) de manière explicite et apprenable.
• Robustesse : La capacité à éviter le sur-lissage rend cette architecture particulièrement adaptée aux graphes profonds et complexes.
• Unification : Le cadre unifie diverses approches existantes (encodage de position, énumération de motifs, méthodes géométriques) sous une seule bannière basée sur les invariants, permettant une combinaison flexible selon les besoins de la tâche.

En résumé, Invariant-Stratified Propagation représente une avancée majeure pour les GNN, permettant de capturer des structures complexes et hétérogènes avec une efficacité computationnelle proche des méthodes standards, ouvrant la voie à des applications plus robustes dans la chimie, les réseaux sociaux et l'analyse de systèmes complexes.