Résumé Technique : CoRe-GNN : Passage de Messages Multi-niveaux sur des Graphes Grossiers

Énoncé du Problème

L'entraînement des réseaux de neurones sur graphes (GNN) sur des graphes à grande échelle est fondamentalement contraint par le coût de mémoire requis pour stocker les représentations intermédiaires des nœuds à travers les couches. Dans les architectures de passage de messages standard, la représentation d'un nœud à une couche $l$ dépend de son voisinage à $l$-sauts. Pour les grands graphes, ce voisinage croît de manière exponentielle avec la profondeur, entraînant des goulots d'étranglement de mémoire qui saturent la mémoire GPU lors de l'entraînement et de l'inférence.

Les approches de mise à l'échelle existantes se répartissent généralement en deux catégories, qui souffrent toutes deux de limitations complémentaires :

1. Grossissement de Graphe (Graph Coarsening) : Les méthodes comme Coarsen-GNN projettent les nœuds originaux vers des « super-nœuds » pour créer un graphe plus petit. Bien que cela permette une propagation efficace et offre des garanties spectrales, cela force tous les nœuds au sein d'un super-nœud à partager la même représentation. Cette « uniformité » limite la discriminabilité par nœud, particulièrement dans les contextes hétérophiles où les nœuds adjacents peuvent avoir des étiquettes différentes.
2. Restriction Basée sur des Clusters (Cluster-Based Restriction) : Les méthodes comme Cluster-GCN restreignent le passage de messages uniquement aux connexions intra-clusters, abandonnant ainsi les arêtes inter-clusters. Cela permet un batching efficace en traitant les clusters comme des sous-graphes indépendants. Cependant, la rupture des connexions inter-clusters élimine les dépendances à longue portée, dégradant les performances sur les tâches nécessitant l'agrégation d'informations sur de nombreux sauts.

Les deux approches reposent sur une décomposition du graphe en groupes de nœuds mais échouent à équilibrer le compromis entre la préservation de la structure à longue portée et le maintien de la discriminabilité locale des nœuds.

Méthodologie : CoRe-GNN

Les auteurs proposent CoRe-GNN (Coarsen and Restore), une architecture conçue pour traiter simultanément le plafond de précision du grossissement de graphe et l'aveuglement à longue portée de Cluster-GCN.

Formulation Matricielle Unifiée

Le papier établit d'abord une perspective unifiée sur les GNN de graphes compressés en les considérant comme des modifications structurées de la matrice de propagation standard $S$.

• Coarsen-GNN remplace $S$ par $\Pi S \Pi$, où $\Pi = QP$ est un opérateur à constante par bloc qui projette les nœuds vers des super-nœuds et vice versa.
• Cluster-GCN remplace $S$ par $S_{intra}$, une matrice bloc-diagonale ne conservant que les arêtes intra-clusters.

L'Architecture CoRe-GNN

CoRe-GNN effectue deux propagations parallèles à chaque couche, couplant l'espace grossi et l'espace des nœuds originaux :

1. Propagation Inter-Cluster (Grossie) : Un terme $S_{inter}^c$ opère sur le graphe grossi (super-nœuds). Il capture efficacement l'information structurelle à longue portée.
2. Propagation Intra-Cluster (Locale) : Un terme $S_{intra}$ opère sur l'espace des nœuds originaux, préservant la discriminabilité par nœud au sein des clusters.

La règle de mise à jour pour la couche $l$ est :
$$H^{(l)} = Q \sigma(S_{inter}^c P H^{(l-1)} \theta_c^{(l)}) + \sigma(S_{intra} H^{(l-1)} \theta^{(l)})$$
Ici, $P$ et $Q$ sont les matrices de réduction et de levage dérivées de la partition du graphe. L'architecture maintient deux états parallèles : $H_c^{(l)}$ dans l'espace grossi et $H^{(l)}$ dans l'espace des nœuds originaux. Les poids $\theta^{(l)}$ et $\theta_c^{(l)}$ sont indépendants, permettant au réseau d'apprendre des transformations distinctes pour les interactions locales et à longue portée.

Schéma de Batching

Pour passer à l'échelle sur des graphes de millions de nœuds, CoRe-GNN introduit une stratégie de batching naturelle :

• Terme inter-cluster : Calculé sur tous les $n$ super-nœuds (où $n \ll N$) à chaque étape, ce qui est peu coûteux en termes de calcul.
• Terme intra-cluster : Calculé uniquement pour les clusters présents dans le batch actuel $B$. Pour les super-nœuds non inclus dans le batch, le terme intra-cluster est approximé par un proxy de boucle de self-loop dans l'espace grossi pendant l'entraînement.
  Cette approche réduit la complexité de la mémoire à $O(K(n+b)d)$, indépendamment du nombre total de nœuds $N$, permettant l'entraînement sur des graphes qui dépasseraient autrement la mémoire GPU.

Inférence Exacte : Bien que le schéma de batching d'entraînement utilise une approximation, les auteurs dérivent une procédure d'inférence exacte non triviale qui évite ce goulot d'étranglement. Dans ce mode, le terme inter-cluster est calculé sur tous les super-nœuds sur le GPU, tandis que le terme intra-cluster est calculé cluster par cluster, chargeant les blocs du CPU vers le GPU à la demande et les supprimant immédiatement. Cela permet une inférence exacte sur de très grands graphes sans conserver l'intégralité du graphe de calcul à travers les couches.

Garanties Théoriques

Les auteurs prouvent que CoRe-GNN hérite de garanties d'approximation similaires au grossissement de graphe. Plus précisément, ils bornent l'erreur entre le passage de messages sur le graphe original et CoRe-GNN en utilisant la constante de l'Approximation Spectrale Restreinte (RSA). La borne théorique pour CoRe-GNN dépend des propriétés du sous-graphe inter-cluster ($S_{inter}$) plutôt que du graphe complet, suggérant qu'à mesure que le ratio de grossissement augmente, les bornes d'erreur peuvent s'améliorer par rapport au grossissement standard.

Contributions Clés

1. Perspective Unifiée : Le papier fournit une formulation matricielle montrant que le grossissement de graphe et Cluster-GCN sont des modifications structurées complémentaires de la matrice de propagation, clarifiant leurs limitations respectives.
2. Architecture CoRe-GNN : Une nouvelle architecture qui couple les propagations inter-clusters (grossies) et intra-clusters (locales) en parallèle, atténuant la perte de discriminabilité du grossissement et la perte d'informations à longue portée du clustering.
3. Batching Scalable : Un schéma de batching naturel qui permet à CoRe-GNN de s'entraîner sur des graphes de millions de nœuds, couplé à une procédure d'inférence exacte qui évite l'approximation.
4. Analyse Théorique : Dérivation des garanties de propagation, montrant que le modèle préserve les signaux lisses avec des constantes dépendant de la structure inter-cluster.
5. Validation Empirique : Évaluation complète sur des benchmarks homophiles, hétérophiles, à grande échelle et à longue portée.

Résultats Expérimentaux

Les auteurs ont évalué CoRe-GNN sur un ensemble diversifié de jeux de données, incluant :

• Homophiles : Cora, CiteSeer, PubMed.
• Hétérophiles : Chameleon, Squirrel, Amazon Ratings.
• Grande échelle : ogbn-arxiv, Reddit, ogbn-products.
• Longue portée : Réseaux routiers de Paris et Londres.

Principaux Résultats :

• Performance : CoRe-GNN surpasse systématiquement les modèles de base Coarsen-GNN et Cluster-GCN dans toutes les catégories.
• Tâches à Longue Portée : Sur les jeux de données de Paris et Londres, CoRe-GNN atteint la précision la plus élevée, démontrant sa capacité à capturer les dépendances à longue portée que Cluster-GCN manque et la discriminabilité que le pur Coarsen-GNN ne possède pas.
• Hétérophilie : Sur les jeux de données hétérophiles (ex: Squirrel), CoRe-GNN surpasse significativement Coarsen-GNN, qui peine lorsque les nœuds d'un même super-nœud ont des étiquettes différentes.
• Scalabilité : Sur des jeux de données à grande échelle comme Reddit et ogbn-products, le GCN standard et le CoRe-GNN non-batché provoquent des erreurs de mémoire (OOM). La variante batchée de CoRe-GNN parvient à s'entraîner et atteint une précision compétitive ou supérieure à celle de Cluster-GCN.
• Ablation : Les expériences confirment que l'utilisation de poids indépendants pour les deux branches et l'utilisation de la matrice de propagation spécifique à l'inter-cluster ($S_{inter}^c$) plutôt que la matrice grossie complète produit de meilleures performances.

Signification et Revendications

Le papier affirme que CoRe-GNN réussit à unifier les avantages du grossissement de graphe et de la restriction basée sur des clusters. En effectuant des propagations parallèles, il surmonte les « échecs complémentaires » des méthodes de mise à l'échelle existantes : la perte de détail au niveau du nœud dans le grossissement et la rupture des dépendances à longue portée dans le clustering.

Les auteurs soulignent que CoRe-GNN fournit un cadre qui :

1. Maintient les garanties spectrales pour la propagation de signaux lisses.
2. Préserve la discriminabilité par nœud dans les contextes hétérophiles.
3. Capture les dépendances à longue portée essentielles pour les tâches de graphes complexes.
4. Passe à l'échelle sur des millions de nœuds via un schéma de batching efficace en mémoire.

Ce travail suggère que la décomposition d'un graphe en groupes ne doit pas être un arbitrage entre précision et scalabilité ; au contraire, une approche multi-niveaux peut atteindre les deux. Les auteurs notent que le cadre est actuellement limité aux GNN avec des matrices de propagation fixes (excluant les mécanismes d'attention) et que les travaux futurs pourraient explorer des extensions vers les connexions résiduelles et les scénarios d'apprentissage fédéré asynchrone.