When does distribution shift break graph neural networks calibration?

Technische Samenvatting: Distributieverschuiving en GNN-kalibratie

Probleemstelling
Graph Neural Networks (GNN's) worden steeds vaker ingezet in dynamische omgevingen waar de grafiekdistributie tijdens de testfase verschilt van de trainingsdistributie (bijv. evoluerende sociale netwerken, herbedrukte infrastructuur). Hoewel voorspellende nauwkeurigheid vaak wordt bestudeerd, blijft de kalibratie van GNN's—de overeenstemming tussen voorspellende zekerheid en werkelijke nauwkeurigheid—onvoldoende begrepen onder dergelijke distributieverschuivingen. Bestaande kalibratiemethoden (bijv. temperature scaling, CaGCN, GATS) vertrouwen doorgaans op gelabelde validatiedata uit de doelverdeling. In de praktijk is dergelijke gelabelde data echter niet beschikbaar, en standaard kalibratoren die zijn aangepast op brongegevens falen omdat de relatie tussen zekerheid en nauwkeurigheid verandert wanneer grafiekeigenschappen zoals homofilie of feature-ruis verschuiven. De centrale uitdaging is om te karakteriseren hoe distributieverschuiving de GNN-kalibratie beïnvloedt en om een methode te ontwikkelen voor herkalibratie zonder toegang tot doel-labels.

Methodologie en Theoretisch Kader
Het artikel benadert dit probleem door een gesloten theoretische karakterisering van GNN-kalibratie onder distributieverschuiving af te leiden. De analyse is gebaseerd op een Contextual Stochastic Block Model (CSBM) waarbij knopen Gaussische features hebben en randen worden gevormd op basis van klasse-homofilie. Het geanalyseerde model is een lineaire GNN (gemiddelde aggregatie of symmetrisch-genormaliseerde GCN) gevolgd door een lineaire classifier.

Het kerninzicht van de theorie is dat de relatie tussen de grootte van de logit $t$ van een model en de werkelijke nauwkeurigheid wordt beheerst door een enkele scalaire parameter, de kalibratie-helling $\kappa$:
$$\text{Zekerheid}(t) = \sigma(t) \quad \text{vs.} \quad \text{Nauwkeurigheid}(t) = \sigma(\kappa t)$$
waarbij $\sigma$ de sigmoid-functie is. Het artikel bewijst dat $\kappa$ expliciet wordt bepaald door de homofilieniveaus van de bron- ($h_s$) en doelgrafieken ($h_t$) en de signaal-ruisverhouding ($\rho$) van de features:
$$\kappa(h_t) = \frac{(2h_t - 1)(1 + 4h_s(1-h_s)\rho)}{(2h_s - 1)(1 + 4h_t(1-h_t)\rho)}$$
Belangrijke theoretische uitbreidingen zijn onder meer:

• Self-loop GCN's: De helling wordt aangepast om rekening te houden met self-loops, die ervoor zorgen dat het signaal standhoudt zelfs onder heterofilie ($h < 0.5$).
• Multi-klasse classificatie: De helling generaliseert via een signaalcoëfficiënt $c_K(h)$, wat aantoont dat een enkele globale temperatuur voldoende blijft voor $K$ klassen.
• Covariabele verschuiving: Toegenomen feature-ruis vermindert $\kappa$ monotoon, wat leidt tot overmatige zelfverzekerdheid (over-confidence).
• Expected Calibration Error (ECE) Bound: Een theoretische bovengrens voor ECE is afgeleid als $\frac{1}{4}|\kappa - 1| \mathbb{E}[|\delta|]$, wat de ernst van miskalibratie direct koppelt aan de afwijking van $\kappa$ van 1.

Belangrijkste Bijdragen

1. Gesloten vorm van de kalibratie-helling: Het artikel biedt de eerste analytische formule voor de kalibratie-helling $\kappa$ onder distributieverschuiving, die expliciet gekoppeld is aan structurele veranderingen (homofilie) en de kwaliteit van de features. Dit verklaart waarom en hoeveel een GNN overmatig zelfverzekerd wordt ($\kappa < 1$) of onderverzekerd wordt ($\kappa > 1$).
2. Optimaliteit van Globale Temperatuur: Een structurele corollary bewijst dat onder een homogene distributieverschuiving (waarbij de verschuiving alle knopen vergelijkbaar beïnvloedt), een enkele globale temperatuur $T^* = 1/\kappa$ theoretisch optimaal is. Dit impliceert dat complexe per-knoop kalibratiemethoden geen voordeel bieden in homogene scenario's, aangezien de populatie-optimale oplossing een constante functie is.
3. STAC (Structure-aware Test-time Adaptive Calibration): Voortbouwend op de theorie, stelt de auteur STAC voor, een bron-vrije en label-vrije herkalibratiemethode. STAC schat de doel-nauwkeurigheid $\hat{a}$ in van ongelabelde data met behulp van zekerheidsstatistieken en voorspellingsdiscrepantie onder perturbaties. Vervolgens stelt het een enkele globale temperatuur $T^* = 1/\hat{\kappa}$ in zodat de gemiddelde zekerheid overeenkomt met de geschatte nauwkeurigheid.
4. Identificatie van de Bottleneck: Het werk identificeert dat de primaire barrière voor praktische, label-vrije GNN-kalibratie niet de kalibratiemechanisme zelf is, maar de schatting van de doel-nauwkeurigheid op ongelabelde, verschoven grafieken.

Experimentele Resultaten

• Synthetische Validatie: Op synthetische CSBM-data komt de gesloten vorm van de helling $\kappa$ met hoge precisie overeen met empirische metingen ($r=0.99$). De voorspelde optimale temperatuur $T^*$ herstelt de kalibratie (vermindert ECE tot $\leq 0.02$) over variërende homofilie en signaal-ruisverhoudingen.
• Real-World Grafieken: De theorie houdt stand over vijf real-world datasets die een breed homofilie-spectrum beslaan ($h=0.05$ tot $0.84$) en variërende klassenaantallen ($K=2$ tot $18$).
  • Oracle Performance: Wanneer een "oracle" temperatuur (afgeleid van ware doel-labels) wordt toegepast, wordt kalibratie hersteld op alle datasets, wat de toereikendheid van de theorie bevestigt.
  • STAC Performance: STAC slaagt erin de kalibratiefoutkloof te halveren ten opzichte van bron-gepaste baselines bij synthetische verschuivingen. Echter, op real-world heterofiele grafieken (bijv. roman-empire, amazon-ratings), zijn de nauwkeurigheidsschattingen van STAC onbetrouwbaar (ze overschatten vaak de werkelijke nauwkeurigheid), wat leidt tot een verslechterde kalibratie. Dit bevestigt dat het theoretische kader solide is, maar dat huidige label-vrije nauwkeurigheidsschatters onvoldoende zijn voor complexe grafiekverschuivingen.
• Heterogene Verschuiving: Onder heterogene verschuivingen (waarbij verschillende knopen verschillende verschuivingen ervaren), kan de enkele globale temperatuur het model niet volledig corrigeren. Hoewel een per-knoop fase is getest, bood deze slechts marginale voordelen met de gebruikte structurele kenmerken, wat de theoretische claim ondersteunt dat per-knoop kalibratie alleen noodzakelijk is als de verschuiving heterogeen is.

Betekenis en Claims
Het artikel beweert de eerste gesloten theoretische verklaring te bieden voor GNN-kalibratie onder distributieverschuiving. De betekenis ligt in:

• Mechanistische Verklaring: Het gaat verder dan empirische observatie door de richting en omvang van miskalibratie te verklaren via de homofilie-afhankelijke helling $\kappa$.
• Geprincipeerde Vereenvoudiging: Het biedt een rigoureuze rechtvaardiging voor het gebruik van een enkele globale temperatuur in homogene verschuivingsscenario's, wat de noodzaak van complexe per-knoop kalibratoren in die context uitdaagt.
• Roadmap voor Toekomstig Werk: Door het probleem van label-vrije kalibratie te reduceren tot het subprobleem van label-vrije nauwkeurigheidsschatting, isoleert het artikel de specifieke technische hindernis die robuuste GNN-kalibratie in de praktijk belemmert. Het suggereert dat toekomstig onderzoek zich moet richten op het ontwikkelen van grafiek-native nauwkeurigheidsschatters die rekening houden met lokale homofilie en aggregatie-effecten, in plaats van het ontwerpen van complexere kalibratie-architecturen.

De auteur blijft bescheiden over de praktische inzetbaarheid van STAC en erkent dat, hoewel de theorie robuust is, de huidige staat van label-vrije nauwkeurigheidsschatting op complexe, heterofiele grafieken nog steeds de centrale onopgeloste uitdaging blijft.