Sintesi Tecnica: PostDeg: Il Posizionamento Prevale sulla Parametrizzazione nelle GNN con LayerNorm

Problema

Molte policy di apprendimento su grafi per compiti di ottimizzazione combinatoria — come l'influenza massima (influence maximization), lo smantellamento di reti (network dismantling) e l'insieme indipendente massimo (MIS) — si basano sul ranking dei nodi basandosi su segnali topologici come il grado, la centralità o il k-core. L'architettura di deep learning dominante per questi compiti prevede l'impilamento di blocchi Graph Attention Network (GAT) con LayerNorm. Tuttavia, la LayerNorm, pur stabilizzando l'addestramento, cancella involontariamente proprio i segnali topologici richiesti da queste policy. Osservazioni empiriche in lavori precedenti (ad es. GraphNorm, PairNorm) indicano che i normalizzatori delle statistiche delle feature non riescono a preservare i contrasti di magnitudo basati sul grado necessari per la selezione dei nodi, eppure la letteratura non ha identificato il meccanismo o la posizione specifica all'interno del blocco residuo in cui avviene questa cancellazione.

Metodologia

Il documento investiga il "posizionamento" di moltiplicatori scalari positivi per nodo (che rappresentano segnali topologici come il grado) rispetto all'operazione di LayerNorm all'interno di un blocco residuo GNN.

Il Diagnostico di Posizionamento

Gli autori sfruttano l'identità di assorbimento della LayerNorm. Per uno scalare positivo $a_i$ e una rappresentazione del nodo $z_i$:
$$\text{LN}(a_i z_i) \approx \text{LN}(z_i)$$
Questa approssimazione è valida fino a un termine stabilizzatore $\epsilon_{\text{LN}}$. Nello specifico, il residuo relativo è limitato da $\epsilon_{\text{LN}} / (a_i^2 \sigma^2)$, dove $\sigma^2$ è la varianza delle feature. Il documento dimostra che se uno scalare topologico viene inserito prima della LayerNorm, viene efficacemente diviso (assorbito), lasciando invariata la magnitudo della rappresentazione. Al contrario, se lo stesso scalare viene inserito dopo la LayerNorm, esso sopravvive come magnitudo della rappresentazione che raggiunge la testa di scoring (score head).

L'Operatore PostDeg

Sulla base di questo diagnostico, gli autori propongono PostDeg, un operatore privo di parametri che occupa la posizione post-LayerNorm. Esso applica una scala inversa al grado alla rappresentazione normalizzata:
$$\hat{h}_i = (b c_i + \epsilon)^{-1/2} \cdot \text{LN}(h_i)$$
dove $b c_i$ è il grado normalizzato (limitato per evitare la divisione per zero) e $\epsilon$ è un piccolo stabilizzatore. Questa operazione ripristina un contrasto di magnitudo monotono rispetto a $1/d_i$, permettendo allo scorer a valle di classificare i nodi per topologia.

Design Sperimentale e Falsificabilità

Per isolare il "posizionamento" dalla "parametrizzazione", lo studio impiega una griglia sperimentale controllata:

1. Backbone: Un GAT a 3 strati con LayerNorm fisso.
2. Variabile: Solo la posizione di normalizzazione post-blocco viene modificata.
3. Falsificatori: Quattro controlli pre-registrati sono stati progettati per rigettare la regola del posizionamento se questa avesse avuto successo:
   • GraphScalar: Uno scalare spettrale a livello di grafo (testa se il guadagno derivi da proprietà spettrali globali piuttosto che dal grado per nodo).
   • Extra LayerNorm: Un ulteriore strato di normalizzazione (testa se il guadagno derivi da un ulteriore normalizzazione delle feature).
   • Varianti Apprese (PostDeg-L-FG/Adaptive): Operatori appresi nella stessa posizione (testa se sia necessaria la capacità espressiva).
   • Backbone PNA: Aggiunta di PostDeg a un backbone PNA (che inietta il grado all'interno dell'aggregazione) (testa se il guadagno sia agnostico rispetto al backbone).

Risultati Chiave

Gli esperimenti sono stati condotti su quattro compiti di selezione dei nodi (InfluMax, Dismantle, Epidemic, MIS) e un compito di classificazione dei grafi (DD).

• Guadagni di Performance: PostDeg ha superato lo standard della backbone con LayerNorm di +3,5% su InfluMax, +2,5% su Network Dismantling e +5,6% su MIS. Questi guadagni sono stati costanti attraverso tutti i 10 seed accoppiati (10/10 vittorie).
• Posizionamento vs. Parametrizzazione: Le varianti apprese (PostDeg-L-FG e PostDeg-L-Adaptive) sono state statisticamente equivalenti alla versione priva di parametri PostDeg (equivalenza TOST a $\pm 1\%$). Ciò conferma che il guadagno è guidato dal posizionamento dello scalare, non dalla capacità apprendibile dell'operatore.
• Esiti dei Falsificatori: Nessuno dei quattro falsificatori ha rigettato la regola del posizionamento:
  • GraphScalar e Extra LayerNorm hanno mostrato guadagni trascurabili o negativi.
  • Le varianti apprese non hanno offerto vantaggi rispetto a PostDeg.
  • L'aggiunta di PostDeg a un backbone PNA (che gestisce già il grado nell'aggregazione) ha portato all'equivalenza accoppiata, indicando che il guadagno svanisce quando il canale del grado è già presente nel passaggio di aggregazione.
• Condizioni al Limite: Il guadagno si è attenuato in compiti con bassa eterogeneità del grado (dataset DD) o dove la ricompensa non era allineata con la magnitudo del grado (Epidemic containment), coerentemente con la previsione teorica che l'effetto dipenda dalla varianza del grado.
• Collasso DD: I normalizzatori che azzerano la varianza (PairNorm, InstanceNorm, BatchNorm) sono collassati sulla predizione della classe maggioritaria sul dataset DD, mentre PostDeg ha mantenuto circa l'80% di accuratezza, dimostrando che PostDeg non soffre dello stesso collasso dei normalizzatori delle statistiche delle feature.

Significato e Rivendicazioni

Il documento sostiene di aver individuato il meccanismo preciso attraverso il quale la LayerNorm cancella i segnali topologici nelle GNN e fornisce una soluzione semplice e priva di parametri.

• Posizionamento sopra la Parametrizzazione: La conclusione principale è che il posizionamento, non la parametrizzazione, porta il guadagno. Un piccolo controllo di invarianza (posizionare lo scalare dopo la LayerNorm) è sufficiente per recuperare i segnali topologici senza apprendere pesi.
• Generalizzabilità: Si afferma che il diagnostico si generalizza a qualsiasi scalare topologico positivo (ad es. PageRank, k-core) in qualsiasi stack residuo normalizzato.
• Contributo Teorico: Il lavoro formalizza l'identità di assorbimento della LayerNorm per gli scalari positivi e stabilisce una "regola di posizionamento" che dicta dove la magnitudo del grado deve essere iniettata per essere visibile allo scorer.
• Modestia: Gli autori limitano esplicitamente le loro rivendicazioni agli scalari positivi e ai blocchi residui a singolo strato. Non affermano che il metodo risolva gli effetti di compounding multi-strato, le varianti RMSNorm o i moltiplicatori che cambiano segno, dichiarandoli fuori ambito. Il guadagno è presentato come una correzione specifica per compiti di selezione dei nodi sensibili al grado dove le GNN standard con LayerNorm falliscono nell'utilizzare la magnitudo topologica.