Résumé Technique : PostDeg : Le placement l'emporte sur la paramétrisation dans les GNN avec LayerNorm

Énoncé du Problème

De nombreuses politiques d'apprentissage sur graphes pour des tâches d'optimisation combinatoire — telles que la maximisation de l'influence, le démantèlement de réseaux et l'ensemble indépendant maximal (MIS) — reposent sur le classement des nœuds en fonction de signaux topologiques comme le degré, la centralité ou le k-core. L'architecture de deep learning dominante pour ces tâches consiste à empiler des blocs GAT (Graph Attention Network) avec une LayerNorm. Cependant, la LayerNorm, bien qu'elle stabilise l'entraînement, efface par inadvertance les signaux topologiques mêmes dont ces politiques ont besoin. Des observations empiriques dans des travaux antérieurs (ex. : GraphNorm, PairNorm) indiquent que les normalisateurs de statistiques de caractéristiques ne parviennent pas à préserver les contrastes de magnitude basés sur le degré nécessaires à la sélection de nœuds, pourtant la littérature n'a pas identifié le mécanisme ou l'emplacement spécifique au sein du bloc résiduel où ce processus d'effacement se produit.

Méthodologie

L'article étudie le « placement » de multiplicateurs scalaires positifs par nœud (représentant des signaux topologiques comme le degré) par rapport à l'opération de LayerNorm au sein d'un bloc résiduel de GNN.

Le Diagnostic de Placement

Les auteurs exploitent l'identité d'absorption de la LayerNorm. Pour un scalaire positif $a_i$ et une représentation de nœud $z_i$ :
$$\text{LN}(a_i z_i) \approx \text{LN}(z_i)$$
Cette approximation est valable jusqu'à un terme stabilisateur $\epsilon_{\text{LN}}$. Plus précisément, le résidu relatif est borné par $\epsilon_{\text{LN}} / (a_i^2 \sigma^2)$, où $\sigma^2$ est la variance des caractéristiques. L'article démontre que si un scalaire topologique est inséré avant la LayerNorm, il est effectivement divisé (absorbé), laissant la magnitude de la représentation inchangée. Inversement, si ce même scalaire est inséré après la LayerNorm, il survit en tant que magnitude de la représentation atteignant la tête de score.

L'Opérateur PostDeg

Sur la base de ce diagnostic, les auteurs proposent PostDeg, un opérateur sans paramètre qui occupe l'emplacement post-LayerNorm. Il applique une échelle inverse du degré à la représentation normalisée :
$$\hat{h}_i = (b c_i + \epsilon)^{-1/2} \cdot \text{LN}(h_i)$$
où $b c_i$ est le degré normalisé (borné pour éviter la division par zéro), et $\epsilon$ est un petit stabilisateur. Cette opération restaure un contraste de magnitude monotone en $1/d_i$, permettant au scoreur en aval de classer les nœuds par topologie.

Conception Expérimentale et Falsifiabilité

Pour isoler le « placement » de la « paramétrisation », l'étude utilise une grille expérimentale contrôlée :

1. Backbone : Un GAT à 3 couches fixe avec LayerNorm.
2. Variable : Seul l'emplacement de la normalisation post-bloc est modifié.
3. Falsificateurs : Quatre contrôles pré-enregistrés ont été conçus pour rejeter la règle de placement s'ils réussissaient :
   • GraphScalar : Un scalaire spectral au niveau du graphe (teste si le gain provient de propriétés spectrales globales plutôt que du degré par nœud).
   • Extra LayerNorm : Une couche de normalisation supplémentaire (teste si le gain provient d'une normalisation de caractéristiques supplémentaire).
   • Variantes Apprises (PostDeg-L-FG/Adaptive) : Des opérateurs appris dans le même emplacement (teste si une capacité expressive est requise).
   • Backbone PNA : Ajouter PostDeg à un backbone PNA (qui injecte le degré lors de l'agrégation) (teste si le gain est indépendant du backbone).

Résultats Clés

Les expériences ont été menées sur quatre tâches de sélection de nœuds (InfluMax, Dismantle, Epidemic, MIS) et une tâche de classification de graphes (DD).

• Gains de Performance : PostDeg a surpassé le backbone standard LayerNorm de +3,5 % sur InfluMax, +2,5 % sur le démantèlement de réseau et de +5,6 % sur MIS. Ces gains ont été constants sur les 10 graines (seeds) appariées (10/10 victoires).
• Placement vs Paramétrisation : Les variantes apprises (PostDeg-L-FG et PostDeg-L-Adaptive) étaient statistiquement équivalentes à la version sans paramètre PostDeg (équivalence TOST à $\pm 1 \%$). Cela confirme que le gain est piloté par le placement du scalaire, et non par la capacité apprenable de l'opérateur.
• Résultats des Falsificateurs : Aucun des quatre falsificateurs n'a rejeté la règle de placement :
  • GraphScalar et Extra LayerNorm ont montré des gains négligeables ou négatifs.
  • Les variantes apprises n'ont offert aucun avantage sur le PostDeg fixe.
  • L'ajout de PostDeg à un backbone PNA (qui traite déjà le degré dans l'agrégation) a entraîné une équivalence appariée, indiquant que le gain disparaît lorsque le canal de degré est déjà présent dans l'étape d'agrégation.
• Conditions Limites : Le gain s'est atténué sur les tâches présentant une faible hétérogénéité de degré (jeu de données DD) ou lorsque la récompense n'était pas alignée sur la magnitude du degré (confinement épidémique), ce qui est cohérent avec la prédiction théorique que l'effet repose sur la variance du degré.
• Effondrement DD : Les normalisateurs annulant la variance (PairNorm, InstanceNorm, BatchNorm) se sont effondrés vers une prédiction de classe majoritaire sur le jeu de données DD, tandis que PostDeg maintenait environ 80 % de précision, démontrant que PostDeg ne souffre pas du même effondrement que les normalisateurs de statistiques de caractéristiques.

Signification et Revendications

L'article affirme avoir localisé le mécanisme précis par lequel la LayerNorm efface les signaux topologiques dans les GNN et fournit une solution simple et sans paramètre.

• Placement plutôt que Paramétrisation : La principale conclusion est que le placement, et non la paramétrisation, porte le gain. Une simple vérification d'invariance (placer le scalaire après la LayerNorm) est suffisante pour récupérer les signaux topologiques sans apprendre de poids.
• Généralisabilité : L'étude affirme que le diagnostic se généralise à tout scalaire topologique positif (ex. : PageRank, k-core) dans n'importe quelle pile résiduelle normalisée.
• Contribution Théorique : Ce travail formalise l'identité d'absorption de la LayerNorm pour les scalaires positifs et établit une « règle de placement » qui dicte où la magnitude topologique doit être injectée pour être visible par le scoreur.
• Modestie : Les auteurs limitent explicitement leurs revendications aux scalaires positifs et aux blocs résiduels à une seule couche. Ils ne prétendent pas que la méthode résout les effets de cumul multi-couches, les variantes RMSNorm ou les multiplicateurs changeant de signe, précisant que cela sort de leur champ d'application. Le gain est présenté comme un correctif spécifique pour les tâches de sélection de nœuds sensibles au degré où les GNN standards avec LayerNorm échouent à utiliser la magnitude topologique.