RAwR: Role-Aware Rewiring via Approximate Equitable Partition

Technische Samenvatting: RAwR: Rolbewuste Herbedrading via Benaderende Equivalente Partities

Probleemstelling
Graph Neural Networks (GNN's) hebben effectiviteit aangetoond bij taken voor knoopclassificatie die vertrouwen op lokale buurtinformatie. Hun prestaties verslechteren echter vaak wanneer voorspellingstaken afhankelijk zijn van interacties op lange afstand. Deze beperking wordt toegeschreven aan oversquashing, een fenomeen waarbij structurele knelpunten de signaalpropagatie over de netwerktopologie beperken, waardoor lange-afstandssignalen worden gecomprimeerd voordat ze de doelknoop bereiken. Hoewel bestaande methoden voor grafherbedrading (zoals Master Node, op kromme gebaseerde benaderingen en spectrale methoden) oversquashing proberen te verlichten door de globale signaalpropagatie te verbeteren, slagen ze er vaak niet in te onderscheiden welke communicatiepaden op lange afstand structureel relevant zijn voor specifieke downstream-taken. In heterofiele grafen of scenario's waarin knoopklassen structurele rollen weerspiegelen in plaats van directe nabijheid, kan ongedifferentieerde herbedrading suboptimaal zijn.

Methodologie
De auteurs introduceren RAwR (Role-Aware Rewiring), een computerefficiënt, modelonafhankelijk raamwerk dat de invoergraf verrijkt met een quotiëntgraf afgeleid van Benaderende Equivalente Partities (AEP's).

1. Benaderende Equivalente Partities (AEP's):

   • Een equivalente partitie groepeert knopen die hetzelfde aantal buren hebben in elk blok van de partitie. Dit induceert een quotiëntgraf dat rollen-tot-rollen-interacties exact samenvat.
   • RAwR maakt gebruik van een $\epsilon$-AEP, die exacte rol-equivalentie versoepelt via een tolerantieparameter $\epsilon$. Dit staat het groeperen van knopen met vergelijkbare (maar niet identieke) structurele rollen toe, waardoor de aanpak robuust is voor ruis in real-world grafen.
   • De partitie wordt efficiënt berekend met het $\epsilon$-BE-algoritme in polynomiale tijd.

2. Herbedradingvarianten:
   Gegeven een invoergraf $G=(V, E)$ en een $\epsilon$-AEP met indicatormatrix $R$ en quotiëntmatrix $Q$, construeert RAwR een verrijkte adjacentiematrix. Twee specifieke varianten worden voorgesteld:

   • RepNodes: Verbindt elke oorspronkelijke knoop met een enkele virtuele representatieve knoop (VN) die overeenkomt met zijn structurele rol. Dit creëert communicatiepaden van twee stappen tussen knopen die topologisch ver verwijderd zijn maar structureel vergelijkbaar. De quotiëntmatrix wordt op nul gezet ($Q=0$).
   • RepEdges: Naast het verbinden van knopen met hun vertegenwoordigers, verbindt deze variant de representatieve VN's met elkaar volgens het ongewogen quotiëntgraf ($\bar{Q}$), waardoor communicatie tussen interacterende rollen mogelijk wordt.

3. Theoretische Fundering (Leraar-Student-analyse):
   Het artikel hanteert een leraar-studentmodel van lineaire GNN's om de impact van herbedrading te analyseren.

   • Aanname: Ware labels worden gegenereerd door een "leraar"-GNN die opereert op een latente structuur (het RAwR-verrijkte graf), terwijl een "student"-GNN probeert te leren van de waargenomen graf.
   • Spectrale Rolheffing (SRL): De analyse leidt tot een bovengrens voor de fout van de student, wat leidt tot de formulering van SRL, een metriek gedefinieerd als $\text{SRL} = \rho \sum_{j=1}^k \omega_j \Delta_j^2$. Hierbij meet $\rho$ de energie van labels in de rolsubruimte, vertegenwoordigt $\Delta_j$ het verschil in rol-relevante eigenwaarden tussen de originele en de herbedrade graf, en zijn $\omega_j$ rolgewichten.
   • Heuristische Selectie: Een praktische heuristiek, SRL$^*$, wordt voorgesteld om de optimale tolerantieparameter $\epsilon$ te selecteren. Deze combineert SRL met de 2-hop Neighbor Class Similarity (2NCS)-metriek om rekening te houden met gevallen waarin labels niet strikt in de rolsubruimte resideerden.

Belangrijkste Bijdragen

1. RAwR-raamwerk: Een nieuwe herbedradingmethode die informatie routeert via structureel betekenisvolle paden (structurele rollen) in plaats van alleen de globale propagatie te verbeteren. Het herstelt de Master Node-techniek als een limietgeval (volledig ingestorte partitie), maar biedt controleerbare granulariteit via $\epsilon$.
2. Structureel Bewijs: Demonstratie dat RAwR de gemiddelde effectieve weerstand van de invoergraf verlaagt, wat structureel bewijs levert dat het knelpunten voor lange-afstandspropagatie verlicht, onafhankelijk van de downstream-GNN-architectuur.
3. Theoretische Analyse: Een formele afleiding met behulp van een leraar-studentmodel die verduidelijkt hoe rollen-gebaseerde herbedrading het spectrale antwoord van message-passing-modellen wijzigt. Dit leidt tot de SRL-metriek voor het selecteren van optimale partities.
4. Complementariteit: Bewijs dat RAwR niet alleen concurrerend is met oplossingen op architectuurniveau (zoals GRAIN) die zijn ontworpen om oversquashing aan te pakken, maar ook complementair is, en de prestaties verder verbetert wanneer deze bovenop dergelijke modellen wordt toegepast.

Experimentele Resultaten
De auteurs hebben RAwR geëvalueerd op een diverse reeks benchmarks, waaronder homofiele (bijv. Cora, Citeseer), heterofiele (bijv. Chameleon, Squirrel) en synthetische datasets voor lange afstand (ECHO).

• Prestaties: RAwR behaalt de beste gemiddelde rang onder de vergeleken herbedradingmethoden (waaronder BORF, FOSR, SDRF, JDR, ComFy, TRIGON en Master Node) over taken voor knoopclassificatie.
• Winsten op Lange Afstand en Heterofiele Data: De meest significante verbeteringen worden waargenomen op heterofiele en lange-afstandsdatasets (bijv. ECHO), waar lokale message passing ontoereikend is. Bijvoorbeeld, op de ECHO "Caterpillar"-dataset zonder knoopkenmerken verbeterde de nauwkeurigheid van 38,82% (baseline) naar 76,47% met RepNodes.
• Ablatiestudies:
  • RepNodes vs. RepEdges: RepNodes presteert over het algemeen beter op real-world benchmarks, wat suggereert dat snelle intra-rolcommunicatie de primaire bron van verbetering is.
  • Willekeurige Partities: Het vergelijken van RAwR met willekeurige partities met hetzelfde aantal virtuele knopen toont aan dat de winsten worden gedreven door de toewijzing van structurele rollen, en niet louter door de toevoeging van virtuele knopen. RAwR presteert gemiddeld 3,66 procentpunten beter dan willekeurige controles.
  • SRL$^*$-heuristiek: De SRL$^*$-heuristiek selecteert effectief concurrerende $\epsilon$-waarden, vaak dicht bij de beste resultaten van grid-search, met name op real-world datasets.

Betekenis en Beperkingen
Het artikel stelt dat RAwR een kritieke kloof in grafherbedrading aanpakt door zich te concentreren op waar informatie moet worden gerouteerd, en niet alleen op hoe deze makkelijker kan worden gepropageerd. Door gebruik te maken van structurele rollen, maakt het efficiële communicatie mogelijk tussen topologisch ver verwijderde maar structureel vergelijkbare knopen, wat direct het fenomeen oversquashing aanpakt.

De auteurs handhaven een bescheiden toon met betrekking tot beperkingen:

• De huidige evaluatie is beperkt tot ongedirigeerde en ongewogen grafen, hoewel AEP's zijn gedefinieerd voor gerichte/gewogen gevallen.
• De SRL-afleiding gaat uit van lineaire GNN's die fungeren als polynoomfilters; de heuristiek kan minder informatief zijn voor architecturen zoals GAT of GIN die niet eenvoudig in dit model passen.
• De empirische focus ligt op knoopclassificatie; uitbreiding naar andere grafleertaken wordt overgelaten aan toekomstig werk.

Kortom, RAwR biedt een principiële, rollen-gebaseerde aanpak voor grafherbedrading die de prestaties van GNN's op taken met lange afstand en heterofiele data verbetert door de effectieve weerstand te verlagen en message passing af te stemmen op structurele rollen.