Résumé Technique : Des Modèles à Passage de Messages aux Modèles de Séquences de Graphes Linéarisés

1. Énoncé du Problème

Les Réseaux de Neurones à Passage de Messages (MPNN) se sont imposés comme l'architecture dominante pour l'apprentissage sur des données structurées en graphes. Cependant, ils font face à des limitations fondamentales lors de la mise à l'échelle pour capturer des dépendances à longue portée. Dans les MPNN standards, la propagation de l'information (collecte d'informations depuis des nœuds distants) et le traitement non linéaire (transformation de ces informations) sont étroitement couplés ; chaque couche fait progresser l'information d'un saut tout en appliquant simultanément une transformation non linéaire.

Ce couplage crée deux problèmes critiques :

1. Écrasement excessif et perte d'information : À mesure que la profondeur du réseau augmente pour atteindre des nœuds distants, les représentations de nœuds de taille fixe doivent comprimer un champ récepteur croissant de manière exponentielle, entraînant une perte d'information et l'effondrement des représentations apprises.
2. Difficultés d'optimisation : L'empilement répété de non-linéarités dans les réseaux profonds conduit à des gradients qui s'évanouissent et à une instabilité, rendant l'entraînement des MPNN profonds difficile.

Bien que l'apprentissage profond moderne ait connu des avancées rapides dans la modélisation de séquences (par exemple, les Transformers, les Modèles d'Espace d'État comme Mamba) qui excellent dans la capture efficace des dépendances à longue portée, l'adaptation de ces modèles aux graphes n'est pas triviale. Les tentatives existantes peinent souvent à préserver les biais inductifs des graphes ou réintroduisent le problème même des non-linéarités accumulées en empilant des modules de manière séquentielle.

2. Méthodologie : Modèles de Séquences de Graphes Linéarisés (LGSM)

Les auteurs introduisent les Modèles de Séquences de Graphes Linéarisés (LGSM), un cadre qui reformule l'apprentissage sur graphes du point de vue de la modélisation de séquences en découplant explicitement deux dimensions fondamentales du calcul :

• Profondeur d'information : La distance sur laquelle l'information se propage à travers la topologie du graphe.
• Profondeur de traitement : Le nombre de transformations non linéaires appliquées aux données.

Architecture de Base

Contrairement aux MPNN standards où ces dimensions progressent de manière diagonale (simultanément), les LGSM linéarisent la propagation le long de l'axe de l'information. L'architecture se compose de quatre composants principaux :

1. Extraction de séquence : Les caractéristiques du graphe d'entrée $X$ et la matrice d'adjacence $A_G$ sont converties en une séquence d'encodages de nœuds $S^{(0)}_{in}, \dots, S^{(L-1)}_{in}$. Cette séquence représente l'état de l'information à différents "sauts" ou étapes de propagation.
2. Couche SSM : La séquence extraite est traitée par un Modèle d'Espace d'État (spécifiquement Mamba2). Crucialement, le SSM opère indépendamment sur la séquence de chaque nœud, permettant à l'information de circuler le long de la dimension de la séquence (profondeur d'information) via des calculs de balayage parallèle efficaces, sans accumuler de non-linéarités.
3. Réseau Feed-Forward (FFN) : Des transformations non linéaires sont appliquées aux éléments de la séquence après le traitement par le SSM, confinés à la dimension de la profondeur de traitement.
4. Mélange de graphe : Pour assurer un mélange d'information entre différents nœuds, les éléments de la séquence sont mis à jour avec des caractéristiques propagées par le graphe provenant de l'élément précédent avant le bloc suivant. Cette étape réintroduit un mélange topologique sans augmenter la profondeur d'information.

Le modèle empile $D$ tels blocs. La séparation permet d'utiliser des implémentations modernes de SSM pour gérer efficacement de longues séquences (grande profondeur d'information), tandis que les non-linéarités sont appliquées de manière contrôlée.

Mécanismes d'Extraction de Séquence

L'article analyse ce qui rend un mécanisme d'extraction de séquence efficace. Il identifie cinq propriétés souhaitables : l'efficacité, la stabilité, l'informativité, la sensibilité et l'influence relative.

• Puissances d'adjacence : L'utilisation des puissances de la matrice d'adjacence ($A_G^k$) est un choix naturel mais souffre de "retour en arrière" (traverser immédiatement une arête en sens inverse), ce qui introduit des informations redondantes et cause une instabilité numérique pour les longues séquences.
• Marches sans retour en arrière (NBT) : Les auteurs proposent d'utiliser la matrice sans retour en arrière $B_G$, qui compte les chemins qui ne reviennent pas immédiatement en arrière. L'analyse théorique montre que les séquences NBT maintiennent une influence relative plus forte pour les nœuds distants par rapport aux puissances d'adjacence, car elles évitent la décroissance exponentielle du signal causée par les chemins de retour en arrière redondants.

3. Contributions Clés

1. Introduction du cadre : La proposition des LGSM, qui découple la profondeur de propagation de l'information de la profondeur de traitement, permettant de reformuler les décisions architecturales fondamentales des graphes comme des choix de modélisation de séquences.
2. Analyse théorique : Une caractérisation théorique rigoureuse de la sensibilité des nœuds dans les LGSM. Les auteurs prouvent que la sensibilité de la sortie finale aux caractéristiques d'entrée dépend de la somme pondérée de tous les éléments de la séquence. Cela établit que l'apprentissage efficace repose sur le mécanisme d'extraction de séquence capturant les relations entre paires de nœuds, plutôt que uniquement sur la profondeur de l'empilement non linéaire.
3. Méthode d'extraction nouvelle : La proposition et la validation de séquences de marches sans retour en arrière, qui offrent théoriquement et empiriquement des propriétés supérieures pour la propagation d'information à longue portée par rapport aux puissances d'adjacence standards.
4. Validation empirique : Évaluation complète sur des benchmarks synthétiques et réels démontrant que les LGSM gèrent efficacement les tâches à longue portée.

4. Résultats Expérimentaux

Les auteurs ont évalué les LGSM sur le benchmark ECHO (ECHO-Synth et ECHO-Chem) et le Benchmark de Graphes LRIM.

• Tâches sur graphes synthétiques (ECHO-Synth) : Les LGSM ont démontré de fortes performances sur des tâches nécessitant un échange d'information à longue portée, telles que la prédiction du diamètre du graphe, de l'excentricité des nœuds et des plus courts chemins à source unique. Notamment, les LGSM ont nettement surpassé les MPNN standards (GCN, GIN) et d'autres baselines avancées (GPS, GRIT) dans la prédiction de l'excentricité, une tâche connue pour être difficile pour les MPNN profonds en raison de l'écrasement excessif.
• Prédiction de propriétés moléculaires (ECHO-Chem) : Sur des tâches de prédiction des charges partielles atomiques et de l'énergie moléculaire totale, les LGSM ont atteint de fortes performances, comparables ou supérieures aux baselines, démontrant leur applicabilité à des jeux de données réels nécessitant des interactions atomiques non locales.
• Benchmark LRIM : Sur le jeu de données LRIM-16-hard, conçu pour tester les interactions à longue portée prouvables, les LGSM ont dépassé les baselines à passage de messages et se sont approchés des performances des approches basées sur les Transformers, coûteuses en calcul.
• Études d'ablation : Les expériences ont confirmé que l'augmentation de la longueur de la séquence (profondeur d'information) améliore constamment les performances sur les tâches à longue portée, tandis que l'augmentation de la seule profondeur de traitement donne des rendements décroissants sans profondeur d'information suffisante. L'utilisation de séquences sans retour en arrière a constamment surpassé les puissances d'adjacence.
• Jeu de données Peptides : Sur les jeux de données Peptides LRGB, les LGSM ont performé de manière similaire aux méthodes de passage de messages standards. Les auteurs notent que cela est probablement dû au fait que les techniques récentes sur ces jeux de données atteignent déjà de fortes performances avec des architectures peu profondes, suggérant que les avantages spécifiques des LGSM sont les plus prononcés dans les scénarios nécessitant une propagation profonde de l'information.

5. Signification et Revendications

L'article revendique fournir un moyen principiel d'intégrer les avancées modernes de la modélisation de séquences dans l'apprentissage sur graphes basé sur le passage de messages. En séparant le traitement et la profondeur d'information, les LGSM reformulent les questions architecturales centrales (telles que la manière de gérer l'écrasement excessif) comme des choix de modélisation d'entrée (spécifiquement, la manière d'extraire la séquence).

Les auteurs soulignent que leur travail démontre comment cette séparation :

• Permet à l'information de circuler sur des distances de graphe arbitraires tout en confinant les transformations non linéaires à la dimension de traitement.
• Exploite le calcul parallèle efficace via les Modèles d'Espace d'État.
• Assure un flux d'information et de gradients approprié dans tout le réseau.
• Déplace le focus de la conception de l'apprentissage sur graphes vers la modélisation de l'extraction de séquence, offrant une alternative théoriquement fondée à l'empilement traditionnel de couches profondes de MPNN.

L'article conclut avec modestie, reconnaissant que bien que les LGSM soient conçus pour l'efficacité, les compromis computationnels spécifiques (par exemple, prétraitement vs temps d'exécution) n'étaient pas l'objectif principal, et que d'autres facteurs comme la régularisation impactent également les performances. Cependant, le cadre offre une nouvelle perspective pour comprendre et concevoir des réseaux de neurones graphiques.