Technische Samenvatting: PostDeg: Placement Beats Parameterization in LayerNorm GNNs

Probleemstelling

Veel graph-learning policies voor combinatorische optimalisatietaken—zoals influence maximization, network dismantling en maximum independent set (MIS)—relyen op het rangschikken van knopen op basis van topologische signalen zoals graad (degree), centraliteit of k-core. De dominante deep learning-architectuur voor deze taken bestaat uit het stapelen van Graph Attention Network (GAT) blokken met LayerNorm. Echter, LayerNorm, hoewel het de training stabiliseert, wist onbedoeld de zeer specifieke topologische signalen die deze policies vereisen. Empirische observaties in eerder werk (bijv. GraphNorm, PairNorm) geven aan dat normalisatoren van feature-statistieken er niet in slagen om de graad-gebaseerde magnitude-contrasten te behouden die nodig zijn voor node-selectie, maar de literatuur heeft nog niet de specifieke methode of locatie binnen het residu-blok geïdentificeerd waar deze uitwissing plaatsvindt.

Methodologie

Het onderzoek onderzoekt de "plaatsing" (placement) van positieve per-node scalaire multiplicatoren (die topologische signalen zoals graad vertegenwoordigen) ten opzichte van de LayerNorm-operatie binnen een GNN residu-blok.

De Placement Diagnostic

De auteurs maken gebruik van de LayerNorm-absorptie-identiteit. Voor een positieve scalaire $a_i$ en een node-representatie $z_i$:
$$\text{LN}(a_i z_i) \approx \text{LN}(z_i)$$
Deze benadering houdt stand tot een stabilisatorterm $\epsilon_{\text{LN}}$. Specifiek is de relatieve residu begrensd door $\epsilon_{\text{LN}} / (a_i^2 \sigma^2)$, waarbij $\sigma^2$ de feature-variantie is. Het paper demonstreert dat als een topologische scalaire vóór LayerNorm wordt ingevoegd, deze effectief wordt weggecijferd (geabsorbeerd), waardoor de representatie-magnitude onveranderd blijft. Omgekeerd, als dezelfde scalaire ná LayerNorm wordt ingevoegd, overleeft deze als de representatie-magnitude die de score-head bereikt.

De PostDeg Operator

Op basis van deze diagnostic stellen de auteurs PostDeg voor, een parameter-vrije operator die de post-LayerNorm slot bezet. Deze past een inverse-graad schaling toe op de genormaliseerde representatie:
$$\hat{h}_i = (b c_i + \epsilon)^{-1/2} \cdot \text{LN}(h_i)$$
waarbij $b c_i$ de genormaliseerde graad is (afgeklemd om deling door nul te voorkomen), en $\epsilon$ een kleine stabilisator is. Deze operatie herstelt een monotone-in-$1/d_i$ magnitude-contrast, waardoor de downstream scorer knopen kan rangschikken op basis van topologie.

Experimenteel Ontwerp en Falsifieerbaarheid

Om "plaatsing" te isoleren van "parameterisatie", gebruikt de studie een gecontroleerd experimenteel grid:

1. Backbone: Een vaste 3-laagse GAT met LayerNorm.
2. Variabele: Alleen de post-block normalisatie-slot wordt gewijzigd.
3. Falsifiers: Vier vooraf geregistreerde controles zijn ontworpen om de plaatsingsregel te verwerpen indien deze succesvol zou zijn:
   • GraphScalar: Een graaf-niveau spectrale scalaire (test of de winst voortkomt uit globale spectrale eigenschappen in plaats van per-node graad).
   • Extra LayerNorm: Een extra normalisatielaag (test of de winst voortkomt uit extra feature-normalisatie).
   • Learned Variants (PostDeg-L-FG/Adaptive): Geleerde operatoren in dezelfde slot (test of expressieve capaciteit vereist is).
   • PNA Backbone: Het toevoegen van PostDeg aan een PNA-backbone (die graad injecteert tijdens aggregatie) (test of de winst backbone-agnostisch is).

Belangrijkste Resultaten

De experimenten werden uitgevoerd op vier node-selectie taken (InfluMax, Dismantle, Epidemic, MIS) en één graaf-classificatie taak (DD).

• Prestatiewinst: PostDeg presteerde beter dan de standaard LayerNorm backbone met +3,5% op InfluMax, +2,5% op Network Dismantling, en +5,6% op MIS. Deze winsten waren consistent over alle 10 gepaarde seeds (10/10 overwinningen).
• Placement vs. Parameterization: De geleerde varianten (PostDeg-L-FG en PostDeg-L-Adaptive) waren statistisch equivalent aan de parameter-vrije PostDeg (TOST-equivalentie bij $\pm 1\%$). Dit bevestigt dat de winst wordt gedreven door de plaatsing van de scalaire, niet door de leerbare capaciteit van de operator.
• Falsifier Uitkomsten: Geen van de vier falsifiers verwierp de plaatsingsregel:
  • GraphScalar en Extra LayerNorm vertoonden verwaarloosbare of negatieve winsten.
  • Geleerde varianten boden geen voordeel boven de vaste PostDeg.
  • Het toevoegen van PostDeg aan een PNA-backbone (die de graad al afhandelt in de aggregatie) resulteerde in gepaarde-equivalentie, wat aangeeft dat de winst verdwijnt wanneer de graad-kanaal al aanwezig is in de aggregatiestap.
• Boundary Conditions: De winst nam af bij taken met een lage graad-heterogeniteit (DD dataset) of waar de beloning niet in lijn was met de graad-magnitude (Epidemic containment), wat consistent is met de theoretische voorspelling dat het effect afhangt van de graad-variantie.
• DD Collapse: Variantie-zeroënde normalisatoren (PairNorm, InstanceNorm, BatchNorm) stortten in tot meerderheidsklasse-voorspelling op de DD dataset, terwijl PostDeg ~80% nauwkeurigheid behield, wat aantoont dat PostDeg niet lijdt onder dezelfde collapse als feature-statistiek normalisatoren.

Betekenis en Claims

Het paper claimt de exacte methode te hebben gelokaliseerd waarmee LayerNorm topologische signalen in GNN's wist, en biedt een eenvoudige, parameter-vrije oplossing.

• Placement boven Parameterization: De belangrijkste conclusie is dat plaatsing, niet parameterisatie, de winst draagt. Een kleine invariantie-check (het plaatsen van de scalaire na LayerNorm) is voldoende om topologische signalen te herstellen zonder gewichten te leren.
• Generaliseerbaarheid: De diagnostic wordt beweerd te generaliseren naar elke positieve topologische scalaire (bijv. PageRank, k-core) in elke genormaliseerde residu-stack.
• Theoretische Bijdrage: Het werk formaliseert de LayerNorm-absorptie-identiteit voor positieve scalairen en stelt een "plaatsingsregel" vast die dicteert waar topologische magnitude moet worden geïnjecteerd om zichtbaar te zijn voor de scorer.
• Bescheidenheid: De auteurs beperken hun claims expliciet tot positieve scalairen en single-layer residu-blokken. Zij beweren niet dat de methode multi-layer cumulatieve effecten, RMSNorm-varianten of teken-veranderende multiplicatoren oplost, aangezien deze buiten de scope vallen. De winst wordt gepresenteerd als een specifieke fix voor graad-gevoelige node-selectie taken waar standaard LayerNorm GNN's falen om topologische magnitude te benutten.