Technische Samenvatting: GRAPHLCP

Probleemstelling

Graph Neural Networks (GNN's) worden steeds vaker ingezet in hoog-risicodomeinen zoals geneesmiddelenontdekking, weersvoorspelling en fraudeopsporing, wat betrouwbare onzekerheidskwantificatie (UQ) vereist. Conformal Prediction (CP) biedt een distributie-vrij kader om verzameling-gebaseerde voorspellingen te construeren met garanties voor eindige steekproeven. Het toepassen van CP op GNN's stelt echter unieke uitdagingen:

1. Structurele Afhankelijkheden: Knopen in grafen zijn van nature afhankelijk, wat de standaard aannames van onafhankelijke en identiek verdeelde (i.i.d.) variabelen schendt die nodig zijn voor klassieke CP.
2. Beperkingen van Embeddings: Bestaande gelokaliseerde CP-methoden voor grafen vertrouwen vaak op nabijheid in de embedding-ruimte (bijvoorbeeld kernel-dichtheidsschatting op GNN-embeddings) om lokale buurten te definiëren. Deze aanpak is vaak onbetrouwbaar vanwege:
   • Over-verzachting: Diepe berichtdoorvoer vermindert de variantie van similariteitsmaten, waardoor embeddings indiscriminatiever worden.
   • Over-squashing: Topologische knelpunten beperken de globale informatiestroom, vooral onder heterofiele omstandigheden.
   • Onder-vertrouwen: GNN's vertonen vaak onvoldoende scheidbaarheid in de geleerde representaties.
3. Inefficiëntie van Bestaande Oplossingen: Huidige grafspecifieke CP-methoden vertrouwen ofwel op het trainen van auxiliary modellen (wat de rekenkosten verhoogt) of gebruiken rigide structurele partities (bijvoorbeeld harde clustering) die geen fijne lokale heterofiele patronen kunnen vangen. Bijgevolg leveren bestaande methoden vaak te conservatieve of slecht gelokaliseerde voorspellingsverzamelingen op in complexe topologieën.

Methodologie: GRAPHLCP

De auteurs stellen GRAPHLCP voor, een op nabijheid gebaseerd gelokaliseerd Conformal Prediction-kader dat expliciet graaf-topologie en inter-knoop-afhankelijkheden integreert in de lokalisatie- en wegingstappen. De methode werkt in een transductieve setting waarin de GNN vooraf getraind en bevroren is. Het kader bestaat uit vier kernfasen:

1. Feature-bewuste Verdichting

Om lokale bias in schaarse grafen te mitigeren en lange-afstand semantische afhankelijkheden te vangen, introduceren de auteurs een verdichtingstap voorafgaand aan de kernel-berekening.

• PCA-projectie: Knopen-embeddings worden eerst geprojecteerd via Principal Component Analysis (PCA) om gecorreleerde feature-dimensies te ontkoppelen en de ruimte te comprimeren, waarmee ruis en redundantie veroorzaakt door over-verzachting worden aangepakt.
• Adaptieve Anisotrope Kernel: Een anisotrope Gaussische kernel wordt geconstrueerd met behulp van de PCA-getransformeerde embeddings. De bandbreedte wordt aangepast op basis van de eigenwaarden van de covariantiematrix om rekening te houden met variërende schalen over dimensies heen.
• Edge-aanvulling: Nieuwe randen worden toegevoegd aan de graaf-adjacentiematrix als de similariteit tussen niet-verbonden knopen (berekend via de Gaussische kernel) een dynamische drempel $\tau_d$ overschrijdt. Deze drempel wordt automatisch afgestemd op basis van de homofiele ratio van de graaf om de toevoeging van informatieve randen in evenwicht te brengen met de introductie van ruis.

2. Gepersonaliseerde PageRank (PPR) Kernel

In plaats van uitsluitend te vertrouwen op embedding-afstanden, maakt GRAPHLCP gebruik van PPR om structurele nabijheid te modelleren.

• Lokalisatie: PPR vangt multi-hop-invloed terwijl het lokale aard behoudt via een restart-kans ($\beta$). Het biedt een zachte, probabilistische notie van nabijheid die van nature aansluit bij gewogen CP.
• Sampling: Voor een testknop wordt een ankerknop gesampled uit de PPR-geïnduceerde verdeling gecentreerd rond de testknop. Dit zorgt ervoor dat nabije knopen meer invloed uitoefenen op de kwantiel-schatting.
• Weging: Kalibratie- en testknopen worden gewogen volgens hun structurele nabijheid tot het gesamplede anker. De auteurs benutten de graad-genormaliseerde symmetrie van PPR ($d_i H(u_i, u_j) = d_j H(u_j, u_i)$) om gewichten efficiënt te berekenen, zelfs wanneer het aantal kalibratiestalen het aantal teststalen overtreft.

3. Integratie van Randomized Localized Conformal Prediction (RLCP)

GRAPHLCP past het RLCP-kader aan. Door een ankerknop $\tilde{u}_{n+1}$ te sample uit de PPR-verdeling van de testknop $u_{n+1}$, construeert de methode een voorspellingsverzameling op basis van een gewogen kwantiel van non-conformiteitscores. De gewichten worden afgeleid van de PPR-scores ten opzichte van het gesamplede anker, waardoor de methode zich kan aanpassen aan de lokale graafcontext.

4. Constructie van Voorspelling

De uiteindelijke voorspellingsverzameling $\hat{C}_n(u_{n+1})$ wordt geconstrueerd als de verzameling labels $y$ zodat de non-conformiteitscore $s(u_{n+1}, y)$ kleiner dan of gelijk is aan een gewogen kwantiel $\hat{q}_{1-\alpha}$. Dit kwantiel wordt berekend met behulp van de gewichten afgeleid van de PPR-kernel en de non-conformiteitscores van de kalibratieset.

Belangrijkste Bijdragen

1. Structure-bewuste Lokalisatie: Het artikel overbrugt de kloof tussen structurele en feature-gebaseerde lokalisatie door embedding-only nabijheid te vervangen door een op PPR gebaseerde kernel. Dit integreert expliciet graaf-topologie in het conformale wegingsproces.
2. Feature-bewuste Verdichting: Een nieuwe voorverwerkingstap die de graaf-topologie aanvult met behulp van embedding-similariteit (via PCA en adaptieve anisotrope kernels) om schaarsheid te mitigeren en lange-afstand afhankelijkheden te vangen zonder te vertrouwen op de potentieel ruisige continue weging van embeddings.
3. Efficiënt Wegingsschema: De methode biedt een efficiënte manier om op PPR gebaseerde gewichten te berekenen voor ongerichte grafen door gebruik te maken van graad-genormaliseerde symmetrie, waarmee de rekeninefficiëntie van het berekenen van volledige PPR-vectoren voor grote kalibratiestalen wordt vermeden.
4. Theoretische Validiteit: De aanpak behoudt de exchangeability-garanties die nodig zijn voor marginale dekking in transductieve settings, terwijl het streeft naar verbeterde relaxed test-voorwaardelijke dekking.

Experimentele Resultaten

De auteurs hebben GRAPHLCP geëvalueerd op zeven knop-regressie en acht knop-classificatie datasets (inclusief citatienetwerken, Amazon co-aankopen en geografische datasets).

• Marginale Dekking: Alle methoden, inclusief GRAPHLCP, voldeden aan de doelstelling voor misdekking ($\alpha = 0.1$), wat de validiteit van de aanpak bevestigt.
• Voorwaardelijke Dekking (WSC): In Worst-Case Slab (WSC)-diagnostiek, die adversariaal de minimale dekking over projectierichtingen zoekt, behaalde GRAPHLCP de beste of tweede beste resultaten op de meeste datasets, en presteerde het beter dan baselines zoals CalLCP, RLCP en SCP.
• Groep-gebaseerde Dekking: GRAPHLCP toonde superieure dekking over partities gebaseerd op homofiele, feature-clustering, clustering-coëfficiënt en knopgraad. De methode was bijzonder effectief in heterofiele regio's waar standaardmethoden worstelden.
• Voorspellende Efficiëntie: Waar CalLCP vaak te grote voorspellingsverzamelingen produceerde (over-dekking), behaalde GRAPHLCP gunstige genormaliseerde voorspellingslengtes, wat een betere afweging biedt tussen dekking en verzamelgrootte.
• Ablatiestudies:
  • Het vervangen van de PPR-kernel door een Gaussische kernel (GSS) resulteerde in lagere dekking en grotere voorspellingsverzamelingen, wat het belang van structure-bewuste lokalisatie bevestigt.
  • De verdichtingstap werd geïdentificeerd als het meest significante component, met name voor regressietaken.
  • PCA-projectie bleek cruciaal om de negatieve effecten van gecorreleerde embedding-features te mitigeren.

Betekenis en Claims

Het artikel claimt dat GRAPHLCP succesvol de beperkingen van bestaande graaf CP-methoden aanpakt door structurele afhankelijkheden expliciet te modelleren. Door gewichten te ontkoppelen van potentieel verlieslatende GNN-encoders en gebruik te maken van een op PPR gebaseerde kernel, creëert de methode een "ruisarmere residu-pijplijn" voor onzekerheidskwantificatie.

De auteurs stellen dat GRAPHLCP marginale dekking garandeert met eindige steekproeven terwijl het efficiënt gunstige test-voorwaardelijke dekking bereikt in diverse conditioneringsscenario's. Ze benadrukken dat de methode bijzonder robuust is in complexe topologieën waar op embedding gebaseerde similariteiten falen door over-verzachting of over-squashing. Het werk onderstreept de noodzaak van structure-bewuste lokalisatie voor effectieve UQ op grafen, en gaat voorbij aan de uitsluitende afhankelijkheid van feature-ruimte nabijheid. De auteurs merken bescheiden op dat toekomstige richtingen het uitbreiden van dit kader naar dynamische grafen met evoluerende topologieën omvatten.