Technische Samenvatting: Pair-Centric Graph Rewiring voor Over-Squashing via Optimal Transport-Guided Communication Alignment

1. Probleemstelling

Message-passing neurale netwerken (MPNNs) hebben moeite wanneer taakrelevante informatie verspreid is over verre regio's van een graaf. Dit fenomeen, bekend als over-squashing, treedt op omdat lokale propagatie signalen uit verre gebieden moet comprimeren door beperkte structurele interfaces, wat leidt tot attenuatie of verlies van informatie. Hoewel graph rewiring als een structurele oplossing is voortgekomen om over-squashing te verzachten, vertrouwen bestaande methoden primair op:

• Edge-level metrieken: Lokale geometrische aanwijzingen (bijv. kromming) of bottleneck-scores.
• Graph-level surrogaten: Globale connectiviteitsmaten (bijv. spectrale expansie, effectieve weerstand).

Het artikel betoogt dat deze benaderingen een kritieke kloof laten: onder een beperkt rewiring-budget is het onduidelijk welke specifieke pairwise communicaties het meest dringend structurele ondersteuning vereisen. Verbeteringen op graafniveau kunnen de geaggregeerde connectiviteit versterken zonder de meest beperkte node-paar interacties aan te pakken, terwijl edge-level reparaties de bredere distributie van communicatiebehoeften kunnen missen.

2. Methodologie: PairAlign

De auteurs stellen PairAlign voor, een pair-centric graph rewiring framework dat expliciet mikt op het "tekort aan vraag en ondersteuning" tussen node-paren. De methodologie bestaat uit drie kerncomponenten:

A. Formulering van Pairwise Communication Shortage

PairAlign definieert het risico op over-squashing als een ratio tussen structurele vraag en propagatie-ondersteuning:

• Vraag ($\omega$): Gedefinieerd door de kortste-pad afstand op de originele graaf ($d_G(u, v)$), verheven tot een macht $p$. Dit vangt de inherente moeilijkheid van communicatie tussen verre nodes op.
• Ondersteuning ($s$): Gedefinieerd door de finite-hop propagatie-massa op de huidige computationele graaf, berekend als een gewogen som van machten van de rij-genormaliseerde propagatiematrix $P$.
• Shortage Score ($S$): De ratio $S(u, v) = \omega(u, v) / (s(u, v) + \epsilon)$.
  • Theoretische basis: Het artikel bewijst dat deze berekenbare shortage score dient als een proxy voor de Jacobian-gebaseerde shortage (de genormaliseerde invloed van node $u$ op node $v$). Specifiek biedt $S$ een ondergrens en een constante-factor equivalentie aan de Jacobian-gebaseerde metriek onder Lipschitz-aannames, waardoor de onhandelbare Jacobian-analyse haalbaar wordt via de graafstructuur.

B. Edge Insertion Dynamics

Het framework erkent dat het toevoegen van een edge niet monotoon voordelig is. Een nieuwe edge creëert nuttige walks, maar verdunt tegelijkertijd de transitie-massa van bestaande buren door rij-normalisatie.

• First-Order Analyse: De auteurs leiden de eerste-orde verandering in ondersteuning ($g_e$) af voor een doel-paar wanneer een edge wordt ingevoegd.
• Selectiecriterium: Een edge is alleen nuttig als de "toegevoegde pad-bijdrage" de "normalisatie-verlies" overstijgt. PairAlign herberekent de shortage dynamisch tijdens het rewiring-proces om te garanderen dat geselecteerde edges daadwerkelijk de shortage score verminderen.

C. Optimal Transport (OT)-Guided Allocation

Om een eindig edge-budget te beheren, vermijdt PairAlign de gulzige (greedy) lokale selectie, die de neiging heeft edges te concentreren op gemakkelijk te repareren paren terwijl ernstige tekorten onbedekt blijven. In plaats daarvan formuleert het de allocatie als een Optimal Transport probleem:

• Bron: De distributie van kandidaat-toegevoegde edges ($q$).
• Doel: De distributie van hoog-shortage node-paren ($p$), afgeleid door de originele shortage scores te centreren om ernstige tekorten te benadrukken.
• Transportkosten ($C$): Encodeert de structurele compatibiliteit tussen een kandidaat-edge en een doel-paar, rekening houdend met:
  1. Endpoint Alignment: De afstand tussen de endpoints van de edge en de nodes van het doel-paar.
  2. Bridge Suitability: Of de span van de edge overeenkomt met de afstand van het doel-paar.
• Objectief: De totale loss combineert de shortage reductie op de gewijzigde graaf en de OT alignment cost. Dit zorgt ervoor dat het budget globaal wordt verdeeld om de meest kritieke shortage targets te dekken, in plaats van lokaal te clusteren.

D. Optimalisatie

De methode gebruikt een continue relaxatie met logits voor kandidaat-edges, waarbij een straight-through estimator wordt gebruikt voor gradiëntpropagatie. Het werkt iteratief de edge-scores bij, evalueert de shortage opnieuw op de huidige gewijzigde graaf, en projecteert de definitieve scores naar een discrete set van toegevoegde edges.

3. Belangrijkste Bijdragen

1. Pair-Centric Formulering: Introduceert een demand-support shortage metriek die node-paren rangschikt op basis van het gebrek aan huidige graaf-ondersteuning ten opzichte van de originele structurele vraag. Theoretisch biedt dit een hanteerbare proxy voor de Jacobian-gebaseerde over-squashing.
2. OT-Guided Rewiring: Stelt een framework voor dat het beperkte edge-budget coördineert over shortage targets met behulp van Optimal Transport. Dit voorkomt budgetconcentratie op enkele targets en zorgt voor een bredere dekking van kritieke communicatie-bottlenecks.
3. Empirische Validatie: Toont aan dat PairAlign de prestaties verbetert over standaard graph benchmarks (node en graph classificatie) en diverse backbones (GCN, GIN, GAT), wat valideert dat pair-level reparatie een effectieve route is voor het verlichten van over-squashing.

4. Experimentele Resultaten

Het artikel evalueert PairAlign (PAR) tegen state-of-the-art rewiring methoden (SDRF, BORF, FoSR, GTR, LASER, etc.) op:

• Node Classificatie: Standaard datasets (Cora, Citeseer) en heterofiele benchmarks (Roman-Empire, Amazon-Ratings, etc.).
• Graph Classificatie: TUDatasets (ENZYMES, MUTAG, etc.).

Belangrijkste bevindingen:

• Prestaties: PairAlign behaalt de beste gemiddelde rangschikking over alle datasets en backbones. Zo verbeterde de nauwkeurigheid op de Texas-dataset met een GIN-backbone bijvoorbeeld van 53,5% naar 68,8%.
• Structurele Diagnostiek: PAR vertoont een superieure $\Delta$Shortage (reductie in communicatie-shortage) en Coverage@10 (fractie van de top shortage-paren die ondersteuning ontvangen) vergeleken met greedy baselines.
• Correlatie: De voorgestelde shortage score correleert sterk (Spearman $\rho \approx 0,93$) met pairwise effectieve weerstand, wat de validiteit ervan als bottleneck-diagnostiek bevestigt.
• Heterofilie: Op heterofiele grafen biedt PAR stabiele verbeteringen zonder de ongerichte vermenging die de klasse-relevante structuur schaadt, waarmee het beter presteert dan methoden die uitsluitend vertrouwen op feature-gelijkenis of community-structuur.

5. Betekenis en Claims

Het artikel claimt dat PairAlign een theoretisch gefundeerde en praktisch effectieve benadering van graph rewiring biedt door de focus te verschuiven van lokale edges of globale connectiviteit naar pairwise communicatie-compatibiliteit.

• Theoretisch Inzicht: Het overbrugt de kloof tussen de abstracte Jacobian-visie van over-squashing en praktische structurele modificatie, door te bewijzen dat het optimaliseren van de berekenbare shortage score effectief de Jacobian-gebaseerde bottleneck vermindert.
• Mechanisme: Het demonstreert dat Optimal Transport noodzakelijk is om beperkte structurele middelen te coördineren, wat ervoor zorgt dat rewiring-inspanningen worden verdeeld over de meest kritieke node-paren in plaats van te worden opgeëist door lokale greedy heuristieken.
• Generaliseerbaarheid: De methode wordt gepresenteerd als een structurele preprocessing-stap die compatibel is met diverse message-passing backbones, wat suggereert dat het verbeteren van het vermogen van de onderliggende graph-topologie om specifieke pairwise interacties te ondersteunen, een universele strategie is voor het mitigeren van over-squashing.

De auteurs concluderen dat hoewel de methode effectief is, toekomstig werk de taak-bewuste demand-modellering en expliciete lokaliteitsrestricties moet verkennen om de schaalbaarheid op zeer grote grafen te verbeteren.