Résumé Technique : Réparation de Graphe Gaussienne Sensible à la Topologie pour des Réseaux de Neurones sur Graphes Robustes

1. Énoncé du Problème

Les réseaux de neurones sur graphes (GNN) dépendent fortement de la qualité de la topologie du graphe observé pour propager l'information efficacement. Dans les applications du monde réel, les graphes observés sont souvent imparfaits, souffrant de deux formes principales de corruption structurelle :

1. Arêtes Spacieuses (Bruit) : Des nœuds sans rapport sont connectés, provoquant la propagation d'informations non pertinentes ou trompeuses.
2. Arêtes Manquantes (Incomplétude) : Des nœuds sémantiquement liés manquent de connexions, empêchant l'information utile d'atteindre les nœuds cibles.

Les approches existantes de l'apprentissage de graphes robustes entrent généralement dans deux catégories :

• Dénouage/Suppression d'Arêtes : Les méthodes comme DropEdge ou PTDNet suppriment les arêtes suspectes. Bien qu'efficaces contre le bruit, elles ne peuvent pas récupérer les chemins de propagation manquants et peuvent affaiblir davantage la connectivité dans les graphes incomplets.
• Apprentissage de la Structure du Graphe : Les méthodes comme LDS, Pro-GNN ou JNSGSL apprennent ou reconstruisent la structure du graphe conjointement avec l'entraînement du GNN. Bien qu'expressives, ces approches introduisent souvent une complexité de calcul significative, nécessitent un scoring d'arêtes par paires dense, une optimisation bilatérale ou des générateurs de graphes entraînables supplémentaires, ce qui les rend moins extensibles et plus difficiles à intégrer aux architectures GNN standards.

L'article pose que l'apprentissage robuste de GNN ne devrait pas se limiter à la suppression d'arêtes ou à la reconstruction complète de la structure. Il propose plutôt la réparation de graphe : construire un graphe de passage de messages creux qui préserve la topologie observée fiable, compense les connexions manquantes et réduit l'influence des arêtes peu fiables, tout en restant compatible avec les architectures GNN standard.

2. Méthodologie : Réparation Gaussienne Sensible à la Topologie (TAGR)

TAGR est un cadre de réparation de graphe léger en pré-entraînement qui construit une matrice d'adjacence creuse réparée $\tilde{A}$ avant l'entraînement du GNN. Il ne cherche pas à apprendre une matrice d'adjacence dense ni à introduire un générateur de graphe entraînable. La méthode combine deux composants complémentaires :

A. Réparation de Voisinage de Caractéristiques Gaussienne Adaptative

Ce composant traite les arêtes manquantes en introduisant des connexions auxiliaires entre des nœuds qui sont similaires dans l'espace des caractéristiques mais non connectés dans le graphe observé.

• Mécanisme : Pour chaque nœud $v_i$, TAGR calcule la similitude cosinus avec les autres nœuds dans un espace de caractéristiques normalisé.
• Largeur de Bande Adaptative : Pour gérer les densités de caractéristiques variables, chaque nœu se voit assigner une largeur de bande locale $\sigma_i$ basée sur sa distribution de caractéristiques locale (spécifiquement, la $\sigma_k$-ième plus petite distance vers les voisins).
• Noyau Gaussien : Un score de similitude gaussienne adaptatif est calculé : $K_{ij} = \exp(-\delta_{ij}^2 / (\sigma_i \sigma_j))$.
• Sparsité : Au lieu d'un graphe de similitude dense, TAGR ne sélectionne que les $k$ meilleurs candidats non-voisins pour chaque nœud. Les arêtes observées existantes sont exclues de cette sélection pour éviter la redondance.
• Sortie : Un graphe de voisinage de caractéristiques gaussien, creux et non-orienté ($A_{GFN}$) qui restaure les chemins de propagation cohérents avec les caractéristiques.

B. Repondération Résiduelle Sensible à la Topologie

Ce composant traite les arêtes spécieuses en affinant les poids du graphe observé sans supprimer entièrement les arêtes.

• Mécanisme : Pour chaque arête observée $(i, j)$, un score d'arête local est calculé sur la base de la cohérence des caractéristiques et de la structure :
  • Accord des caractéristiques (similitude cosinus).
  • Cohérence structurelle (coefficient de Jaccard des voisinages, nombre de voisins communs, coefficients de regroupement et déséquilibre de degré).
• Scoring : Ces statistiques sont standardisées et combinées en un score $q_{ij}$. Un multiplicateur résiduel borné $r_{ij}$ est dérivé à l'aide d'une fonction tangente hyperbolique et d'un écrêtage pour garantir que les poids restent dans une plage stable (par exemple, $[0.5, 1.5]$).
• Sortie : La matrice d'adjacence $A$ observée est multipliée élément par élément par la matrice de multiplicateur résiduel $R_\lambda$ pour produire un graphe repondéré ($A_{TAR}$). Cela préserve la topologie originale tout en diminuant le poids des arêtes peu fiables et en augmentant celui des arêtes cohérentes.

C. Construction Finale

Le graphe réparé final est la somme des deux composants :
$$\tilde{A} = A_{TAR} + A_{GFN}$$
Cette matrice est utilisée directement comme entrée pour les GNN de passage de messages standards (ex: GCN, GAT, GraphSAGE) sans modifier leurs architectures neuronales ou leurs objectifs d'entraînement.

3. Contributions Clés

1. Formulation : L'article cadre l'apprentissage robuste de GNN comme un problème de réparation de graphe, ciblant simultanément les arêtes spécieuses et manquantes, plutôt que de se concentrer uniquement sur le dénoisement ou l'apprentissage complet de la structure.
2. Cadre TAGR : Un cadre modulaire et léger qui construit une matrice d'adjacence réparée creuse utilisant des noyaux gausiens adaptatifs et une repondération résiduelle sensible à la topologie.
3. Réparation Gaussienne Adaptative : Un mécanisme pour restaurer les chemins de propagation cohérents avec les caractéristiques sans construire une matrice de similitude dense, évitant ainsi le coût de calcul de la similitude par paires de tous les nœuds.
4. Repondération Résiduelle Sensible à la Topologie : Un mécanisme déterministe pour affiner les arêtes observées en utilisant des preuves locales de caractéristiques et de structure, réduisant la dépendance aux connexions non fiables tout en préservant la topologie utile.
5. Évaluation Unifiée : Une évaluation complète de la robustesse à travers des réglages de réseaux de citations propres, d'ajout d'arêtes (bruit) et de suppression d'arêtes (incomplétude) sur des réseaux de citation de référence.

4. Résultats Expérimentaux

Les auteurs ont évalué TAGR sur quatre réseaux de citations (Cora, Citeseer, Cora-ML, Pubmed) dans un contexte de classification de nœuds semi-supervisée.

• Robustesse à la Corruption : TAGR a systématiquement amélioré la robustesse des GNN standards (particulièrement GCN) sous des perturbations d'ajout d'arêtes et de suppression d'arêtes. Par exemple, avec 90 % d'ajout d'arêtes sur Cora, le GCN classique chute à 67,9 %, tandis que le TAGR-GCN maintient 72,3 %.
• Analyse des Composants :
  • Réparation Gaussienne : La variante "uniquement Gaussienne" (G-GCN) a montré que la réparation du voisinage de caractéristiques est la source principale de robustesse, surpassant nettement les GNN classiques, surtout dans les scénarios d'arêtes manquantes.
  • Repondération Résiduelle : Le modèle complet TAGR a fourni une stabilité supplémentaire, particulièrement dans les contextes de graphes incomplets, en affinant la topologie observée.
• Comparaison avec les Baselines :
  • vs. Réparation Apprise (RS-GCN) : RS-GCN a performé exceptionnellement bien sous un bruit sévère d'ajout d'arêtes mais nécessitait des générateurs de graphes appris. TAGR est resté compétitif tout en étant plus léger et plus modulaire sur le plan computationnel.
  • vs. Apprentissage de Structure (JNSGSL) : JNSGSL était fort dans les contextes propres et modérément corrompus, mais a montré moins de stabilité sous des perturbations sévères par rapport à TAGR.
• Compatibilité du Backbone : TAGR a fourni les gains les plus significatifs pour GCN, qui dépend directement de la matrice d'adjacence. GAT et GraphSAGE ont également bénéficié de l'approche, bien que les gains soient modérés par leurs mécanismes d'agrégation internes (ex: attention).
• Courbes de Robustesse : À travers une plage continue de ratios de perturbation, le TAGR-GCN a obtenu le meilleur rang moyen, démontant une performance constante dans les régimes de bruit et d'incomplétude.

5. Signification et Revendications

L'article affirme qu'une robustesse efficace des GNN peut être obtenue via une réparation de graphe creuse et légère plutôt que par un apprentissage de structure de graphe dense.

• Simplicité et Modularité : TAGR évite la complexité de l'optimisation bilatérale, du scoring par paires dense et des modules de graphes entraînables supplémentaires. Il agit comme une couche de pré-traitement compatible avec n'importe quel backbone GNN standard.
• Interprétabilité : La réparation est pilotée par la proximité explicite des caractéristiques et les preuves topologiques locales (ex: voisins communs, regroupement) plutôt que par des générateurs appris opaques.
• Mécanismes Complémentaires : L'étude démontre que la robustesse provient de la synergie de deux mécanismes : la réparation gaussienne restaure les chemins sémantiques manquants, tandis que la repondération sensible à la topologie stabilise la contribution du graphe observé.
• Praticité : La méthode offre une alternative stable et interprétable pour les scénarios où le graphe observé contient à la fois du bruit et des données manquantes, fournissant des structures de passage de messages fiables sans le surcoût de l'apprentissage complet de la structure du graphe.

Les auteurs concluent que si l'apprentissage de structure dense a sa place, un opérateur de réparation creux et sensible à la topologie peut fournir un substrat fiable pour les GNN, équilibrant performance, efficacité et interprétabilité. Des travaux futurs sont suggérés pour explorer des variantes adaptatives, la robustesse face au bruit de caractéristiques, et des extensions aux contextes inductifs et hétérogènes.