Résumé Technique : Réexamen des GNN Pré-Propagation

1. Énoncé du Problème

Les Réseaux de Neurones à Graphes Pré-Propagation (PP-GNN) offrent une alternative évolutive aux GNN à Passage de Messages traditionnels (MP-GNN) en découplant la propagation des caractéristiques de leur transformation. Dans les PP-GNN, la diffusion du graphe est effectuée une seule fois comme étape de prétraitement pour générer des caractéristiques multi-sauts, permettant à la phase d'entraînement ultérieure d'utiliser des transformations denses et mini-lotables sans dépendances inter-nœuds. Bien que cette conception améliore l'efficacité et corresponde aux accélérateurs matériels modernes optimisés pour le calcul dense, les PP-GNN présentent un écart de performance significatif par rapport aux MP-GNN, en particulier sur les graphes hétérophiles (où les nœuds connectés ont souvent des étiquettes différentes).

Les auteurs identifient deux limitations de conception principales contribuant à cet écart :

1. Limitations des Opérateurs de Diffusion : Les PP-GNN standards reposent sur des opérateurs simples (par exemple, adjacence normalisée, marches aléatoires) qui agissent comme des filtres passe-bas. Ceux-ci sont sous-optimaux pour les graphes hétérophiles, qui nécessitent souvent des composantes de plus haute fréquence ou passe-bande. De plus, les bases de diffusion monomiales standards (puissances de la matrice de diffusion) sont souvent mal conditionnées et produisent des caractéristiques fortement corrélées, limitant la qualité de l'approximation.
2. Propagation en Une Seule Fois : Les PP-GNN propagent les caractéristiques d'entrée brutes uniquement une fois. Contrairement aux MP-GNN, qui entrelacent itérativement la propagation avec des transformations non linéaires pour affiner des représentations adaptées à la tâche, les PP-GNN ne peuvent pas mettre à jour les caractéristiques propagées en fonction des états cachés évolutifs durant l'entraînement.

2. Méthodologie

L'article propose une série d'améliorations pour combler l'écart de précision tout en préservant l'efficacité d'entraînement des PP-GNN. L'approche se compose de trois composants principaux :

A. Opérateurs de Diffusion Robustes

Pour remédier aux limitations des bases de diffusion standard, les auteurs introduisent deux bases de diffusion orthogonales et mieux conditionnées pour l'étape de prétraitement :

• Base de Polynômes de Jacobi : Au lieu d'utiliser des monômes $\Phi^k$, les auteurs exploitent les polynômes de Jacobi $P_k^{(\alpha, \beta)}(\tilde{L})$, où $\tilde{L}$ est un Laplacien décalé. Les paramètres $(\alpha, \beta)$ sont calibrés en une seule étape de prétraitement légère, basée sur la densité spectrale du graphe (en utilisant des moments de Tchebychev stochastiques) pour allouer la résolution là où le spectre du graphe se concentre. Cela crée une base orthogonale qui réduit la corrélation des caractéristiques.
• Base de Sous-espace de Lanczos/Krylov : Pour capturer le contenu spectral spécifique aux canaux, les auteurs construisent un sous-espace de Krylov pour chaque canal de caractéristiques en utilisant l'itération de Lanczos. Cela génère un ensemble de vecteurs et de valeurs de Ritz formant une banque de diffusion orthogonale et alignée sur le signal. Cette méthode décompose les caractéristiques en composantes décorrélatées, fournissant un système de coordonnées plus stable pour l'agrégation sous un budget de saut fixe.

B. Re-Propagation des États Cachés (HRP)

Pour surmonter la limitation de la « propagation en une seule fois », les auteurs introduisent la Re-Propagation des États Cachés (HRP). Ce mécanisme réassocie la propagation des caractéristiques aux représentations apprises :

• Mécanisme : L'entraînement est divisé en plusieurs étapes. À la fin de chaque étape, la meilleure représentation cachée (avant la projection de sortie finale) est sélectionnée et détachée. Cet état caché est ensuite re-propagé à travers l'opérateur de diffusion pour générer un nouvel ensemble de caractéristiques multi-sauts.
• Intégration : Ces caractéristiques cachées re-propagées sont mélangées avec les caractéristiques précalculées originales pour former l'entrée de l'étape d'entraînement suivante.
• Distinction : Les auteurs contrastent explicitement la HRP avec la réutilisation basée sur les étiquettes (par exemple, l'utilisation de logits ou d'étiquettes one-hot comme caractéristiques). Ils soutiennent que la re-propagation d'états cachés de haute dimension porte des informations relationnelles complémentaires au-delà des probabilités de classe, tandis que la propagation d'étiquettes peut introduire des raccourcis ou du bruit, en particulier sur les graphes hétérophiles.

C. Agrégateur de Sauts Basé sur RNN

Comme amélioration optionnelle de l'efficacité, les auteurs proposent de remplacer les agrégateurs à Têtes Multiples d'Attention (MHA) (utilisés dans des modèles comme HOGA) par un Réseau de Neurones Récurrent (RNN) pour traiter la séquence de caractéristiques de saut. Cela réduit la surcharge computationnelle et l'utilisation de la mémoire tout en maintenant une précision comparable.

3. Contributions Clés

1. Adaptation de Bases de Diffusion Robustes : L'article adapte les bases de diffusion de polynômes de Jacobi et de sous-espaces de Krylov au régime de prétraitement des PP-GNN. Ces bases améliorent le conditionnement des caractéristiques précalculées et permettent des réponses spectrales plus riches sous un budget de saut fixe.
2. Re-Propagation des États Cachés (HRP) : Un mécanisme léger qui affine itérativement les PP-GNN en re-propagant des états cachés intermédiaires, comblant efficacement l'écart entre la propagation en une seule fois et le passage de messages itératif sans sacrifier l'évolutivité.
3. Agrégation Efficace : Un agrégateur de sauts basé sur RNN servant d'alternative moins coûteuse en calcul à l'agrégation basée sur l'attention.
4. Validation Empirique : Des expériences approfondies sur 12 jeux de données (6 hétérophiles, 6 homophiles) et 4 architectures de PP-GNN (SIGN, HOGA, GAMLP, GARNN).

4. Résultats Expérimentaux

Les méthodes proposées ont été évaluées sur des benchmarks hétérophiles et homophiles :

• Graphes Hétérophiles : Sur six jeux de données hétérophiles (incluant Roman-Empire, Minesweeper et Pokec), les PP-GNN améliorés ont considérablement réduit l'écart de précision avec les MP-GNN.
  • L'amélioration moyenne de la précision de test par rapport aux PP-GNN de base était de +2,18 % sur les jeux de données hétérophiles.
  • Les modèles améliorés ont surpassé de solides bases de MP-GNN (par exemple, GraphSAGE, GAT) sur 4 des 6 graphes hétérophiles.
  • Sur le jeu de données Roman-Empire, l'écart de précision entre les MP-GNN et les PP-GNN a été réduit d'environ 11 % à une quasi-égalité.
• Graphes Homophiles : Les améliorations se sont également transférées aux jeux de données homophiles (par exemple, Cora, Citeseer, OGBN-Arxiv), avec une amélioration moyenne de +1,96 %. Les PP-GNN améliorés ont surpassé les MP-GNN sur 3 des 6 jeux de données homophiles.
• Études d'Ablation :
  • Les opérateurs de diffusion robustes seuls ont fourni un gain moyen d'environ 2,09 % (validation) / 1,99 % (test).
  • La HRP a apporté un gain supplémentaire d'environ 1,54 % (validation) / 1,61 % (test).
  • La HRP a nettement surpassé les stratégies d'entrée par étiquettes et de propagation d'étiquettes, en particulier sur les graphes hétérophiles où la régularité des étiquettes est faible.
• Efficacité :
  • L'opérateur de Lanczos ajoute un coût comparable à quelques étapes de diffusion standard.
  • La HRP introduit un petit nombre d'étapes (généralement < 4, maximum 7), la diffusion de re-propagation ne représentant qu'environ 2 % du temps total d'entraînement.
  • L'agrégateur basé sur RNN (GARNN) a atteint une précision similaire à HOGA mais avec un temps d'entraînement considérablement réduit (2,4 s/époque contre 8,4 s/époque sur Pokec).
  • Globalement, les PP-GNN améliorés atteignent un compromis favorable précision-temps d'exécution, rapprochant la famille des PP-GNN de la frontière de Pareto des MP-GNN.

5. Signification et Revendications

L'article revendique que le cadre proposé résout avec succès les limitations d'expressivité des GNN Pré-Propagation sans revenir aux goulots d'étranglement computationnels du passage de messages itératif.

• Évolutivité vs Expressivité : Le travail démontre que les PP-GNN ne sacrifient pas intrinsèquement l'expressivité pour l'évolutivité ; l'écart provient plutôt d'opérateurs de diffusion sous-optimaux et de l'absence de raffinement itératif. En utilisant des bases de diffusion robustes et la HRP, les PP-GNN peuvent égaler ou dépasser la précision des MP-GNN tout en conservant leur efficacité d'entraînement et leurs capacités de mini-lots.
• Applicabilité Générale : Bien que motivées par les défis de l'hétérophilie, les méthodes se sont révélées bénéfiques à la fois sur les structures de graphes hétérophiles et homophiles.
• Impact Pratique : L'approche offre une voie pour déployer des GNN hautement évolutifs sur des graphes à grande échelle (par exemple, réseaux sociaux, systèmes de recommandation) avec des performances compétitives par rapport aux modèles de passage de messages de l'état de l'art, réduisant potentiellement les coûts computationnels et la consommation d'énergie pour l'apprentissage de graphes à grande échelle.

Les auteurs adoptent une position modeste, notant que si les méthodes améliorent les performances, elles n'introduisent pas de nouvelles modalités de données ni ne préviennent intrinsèquement les risques éthiques downstream associés à l'apprentissage sur graphes (tels que l'amplification des biais), soulignant la nécessité de pratiques responsables en ML lors du déploiement.