Technische Samenvatting: Kwantielvrije Onzekerheidskwantificatie in Graph Neural Networks

1. Probleemstelling

Onzekerheidskwantificatie (UQ) in Graph Neural Networks (GNN's) is cruciaal voor toepassingen met hoge risico's, zoals gezondheidszorg en strafrecht, maar blijft een aanzienlijke uitdaging. Bestaande GNN's produceren doorgaans deterministische puntenschattingen en slagen er niet in de betrouwbaarheid van voorspellingen te vangen. Bovendien kunnen standaard berichtdoorgeefmechanismen data-biasen voortplanten en versterken, waardoor de risico's voor besluitvorming toenemen.

Huidige UQ-benaderingen voor GNN's staan voor drie primaire beperkingen:

1. Bayesiaanse Methoden: Hoewel ze principieel zijn, lijden ze vaak aan schaalbaarheidsproblemen en gevoeligheid voor specificaties van a-priori verdelingen.
2. Resampling en Post-hoc Kalibratie: Frequentistische benaderingen zoals Conformal Prediction (CP) of ensemble-methoden vertrouwen op herhaalde inferentie of aparte kalibratiesets. Deze zijn computatieel kostbaar en zijn vaak afhankelijk van sterke aannames, zoals uitwisselbaarheid (vaak vereenvoudigd als i.i.d.), die bij grafdata door structurele afhankelijkheden (bijv. hubs, heterofielie) vaak worden geschonden.
3. Beperkingen van Kwantielregressie (QR): Standaard QR vereist expliciete invoer op kwantielniveau (bijv. $\tau = 0.05$) of aparte modellen voor elk kwantiel. Wanneer dit op GNN's wordt toegepast, verweven deze ontwerpen knooprepresentaties, wat leidt tot problemen zoals kwantielaanloop, oversmoothing en slecht gekalibreerde intervallen.

Het artikel betoogt dat er behoefte is aan een frequentistisch kader dat sterke aannames vermijdt, de noodzaak voor kwantielinvoer of nabewerking elimineert en computationeel praktisch blijft voor grafgestructureerde data.

2. Methodologie: QpiGNN

De auteurs stellen Quantile-free Prediction Interval GNN (QpiGNN) voor, een kader dat is ontworpen om gekalibreerde en compacte voorspellingsintervallen voor regressie op knoopniveau te genereren zonder kwantielinvoer, resampling of post-hoc kalibratie.

2.1. Dual-Head Architectuur

QpiGNN maakt gebruik van een dual-head architectuur om de voorspelling van de doelwaarde te ontkoppelen van de schatting van onzekerheid.

• Encoder: Een standaard GNN (bijv. GraphSAGE) aggregeert buurtinformatie om knoop-embeddings $H$ te produceren.
• Voorspellingshead: Een lineaire laag voorspelt het doelgemiddelde $\hat{y} = W_{pred}H + b_{pred}$.
• Onzekerheidshead: Een aparte lineaire laag voorspelt de halve breedte van het interval $\hat{d} = \text{Softplus}(W_{diff}H + b_{diff})$. De Softplus-activatie zorgt ervoor dat $\hat{d} > 0$.
• Output: Het voorspellingsinterval voor knoop $v$ wordt gedefinieerd als $[\hat{y}_v - \hat{d}_v, \hat{y}_v + \hat{d}_v]$.

Deze scheiding voorkomt representatieve conflicten en gradiëntinterferentie tussen nauwkeurigheid en onzekerheidsschatting, en vermindert de oversmoothing-problemen die gebruikelijk zijn in single-head GNN's.

2.2. Kwantielvrije Gezamenlijke Loss

In plaats van te optimaliseren voor specifieke kwantielen, wordt QpiGNN end-to-end getraind met een gezamenlijke loss-functie $\mathcal{L}_{total}$ die direct optimaliseert voor dekking en intervallengte:

$$\mathcal{L}_{total} = \mathcal{L}_{coverage} + \lambda_{width} \cdot \mathcal{L}_{width}$$

• Dekkingsterm ($\mathcal{L}_{coverage}$): Deze term straft afwijkingen van de gewenste dekkingsrate $(1-\alpha)$ af. Deze omvat een kwadratische foutterm $(\hat{c} - (1-\alpha))^2$ en een schendingverlies $\hat{\ell}_{viol}$ dat fijnmazige feedback geeft wanneer ware doelen buiten de voorspelde grenzen vallen.
  • $\hat{c}$ is het empirische dekkingsaandeel.
  • $\hat{\ell}_{viol}$ straft de omvang van de schending af wanneer $y_v < \hat{y}^{low}_v$ of $y_v > \hat{y}^{up}_v$.
• Breedteterm ($\mathcal{L}_{width}$): Deze term minimaliseert de gemiddelde intervallengte $\mathbb{E}[\hat{y}^{up}_v - \hat{y}^{low}_v]$ met behulp van een $L_1$-straf om stabiliteit tegen uitschieters te garanderen.
• Afweging: De hyperparameter $\lambda_{width}$ balanceert de afweging tussen het handhaven van de gewenste dekking en het minimaliseren van de intervallengte (compactheid).

Dit ontwerp stelt het model in staat adaptieve, knoopspecifieke intervallen direct te leren uit labeltoezicht, waardoor de noodzaak voor expliciete kwantielinvoer of kalibratiesets wordt vermeden.

3. Theoretische Waarborgen

Het artikel biedt theoretische rechtvaardigingen voor QpiGNN onder milde aannames (begrensde ruis, zwakke afhankelijkheid tussen knopen en convergentie van voorspelde gemiddelden/breedtes):

• Asymptotische Dekking: Onder de Zwakke Wet van de Grote Getallen (WLLN) convergeert de empirische dekking $\hat{c}$ in waarschijnlijkheid naar het gewenste niveau $1-\alpha$ naarmate het aantal knopen $N \to \infty$.
• Finite-Sample Grenzen: Met behulp van concentratieongelijkheden (McDiarmid en Hoeffding) toont het artikel aan dat voor moderate $N$, de afwijking van de empirische dekking van het doel begrensd is door $O(1/\sqrt{N})$, zelfs in aanwezigheid van graf-afhankelijke afhankelijkheden.
• Optimale Breedte: De gezamenlijke loss wordt geïnterpreteerd als een Lagrangiaanse relaxatie van een geconstrueerd optimalisatieprobleem. Wanneer aan de dekking wordt voldaan, prioriteert het model breedtereductie, wat resulteert in bijna optimale intervallengtes.
• Convergentie: De niet-convexe gezamenlijke loss blijkt te convergeren naar een stationair punt onder standaard omstandigheden voor stochastische optimalisatie.

4. Experimentele Resultaten

De auteurs hebben QpiGNN geëvalueerd op 19 datasets, bestaande uit 9 synthetische grafen (bijv. BA, ER, Grid, Tree) en 10 real-world benchmarks (bijv. data van Amerikaanse county's, Twitch, Wikipedia-grafen).

4.1. Prestatiemetrics

De primaire metrics waren Prediction Interval Coverage Probability (PICP) en Mean Prediction Interval Width (MPIW).

• Dekking: QpiGNN bereikte een gemiddelde 22% hogere dekking dan concurrerende baselines (SQR-GNN, RQRadj.-GNN, CF-GNN, BayesianNN, MC Dropout).
• Compactheid: QpiGNN produceerde intervallen die gemiddeld 50% smaller waren terwijl ze een geldige dekking behielden.
• Vergelijking:
  • BayesianNN verzekerde dekking maar produceerde buitensporig brede intervallen.
  • MC Dropout produceerde smalle intervallen maar leed aan ernstige onderdekking.
  • SQR-GNN en RQRadj.-GNN vertoonden vaak instabiliteit, kwantielaanloop of slechte kalibratie op heterofiele grafen.
  • CF-GNN (geconformaliseerd) vereiste kalibratiesets en produceerde bredere intervallen dan QpiGNN.

4.2. Robuustheid en Generalisatie

• Perturbaties: QpiGNN bleef robuust tegen ruis in features, ruis in doelen en edge dropout, en behield een geldige dekking waar baselines faalden of aanzienlijk bredere intervallen vereisten.
• Structurele Verschuivingen: Bij out-of-distribution (OOD) tests waarbij modellen getraind op het ene graftype op andere werden getest, generaliseerde QpiGNN getraind op expressieve grafen (BA, ER) goed, terwijl modellen getraind op eenvoudige structuren (Tree, Basic) faalden om doelen op complexe grafen te dekken.
• Uitwisselbaarheid: QpiGNN behield prestaties onder niet-uitwisselbare splits (bijv. splitsen op knoopgraad of gemeenschap), wat robuustheid aantoont tegen schendingen van de i.i.d.-aanname.

4.3. Efficiëntie

QpiGNN deelt dezelfde computationele complexiteit $O(Ed + Nd^2)$ als lichtgewicht baselines zoals SQR-GNN. In tegenstelling tot MC Dropout (dat meerdere forward passes vereist) of CF-GNN (dat een apart kalibratiemodule vereist), voert QpiGNN onzekerheidsschatting uit in één enkele pass tijdens inferentie.

5. Belangrijkste Bijdragen

1. Kwantielvrij UQ-kader: QpiGNN is het eerste kader dat gekalibreerde, compacte onzekerheidskwantificatie op knoopniveau in GNN's mogelijk maakt zonder kwantielniveau-invoer, resampling of nabewerking.
2. Architectuur en Loss-ontwerp: De introductie van een dual-head architectuur gekoppeld aan een kwantielvrije gezamenlijke loss die voorspelling en onzekerheid ontkoppelt, wat oversmoothing mitigeert en stabiele training mogelijk maakt.
3. Theoretische en Empirische Validatie: Het artikel biedt theoretische waarborgen voor asymptotische en finite-sample dekking onder milde aannames en toont superieure prestaties over 19 diverse benchmarks aan, met significante verbeteringen in zowel dekking als intervallengte in vergelijking met state-of-the-art baselines.

6. Betekenis

Het artikel stelt dat QpiGNN de kritieke kloof in betrouwbare GNN-toepassingen aanpakt door een computationeel efficiënte, robuuste en aannames-arme methode voor onzekerheidskwantificatie te bieden. Door de sterke uitwisselbaarheid-aannames die nodig zijn voor Conformal Prediction en de computationele overhead van Bayesiaanse methoden te vermijden, biedt QpiGNN een praktische oplossing voor domeinen met hoge risico's waar betrouwbare voorspellingsintervallen essentieel zijn. De auteurs merken op dat de methode robuust blijft, zelfs wanneer theoretische aannames (zoals symmetrie of onafhankelijkheid) slechts bij benadering worden voldaan in real-world grafdata.

Toekomstig werk zoals voorgesteld door de auteurs omvat het uitbreiden van QpiGNN naar graf-niveau en link-predictietaken, het ontkoppelen van aleatorische en epistemische onzekerheid, en het toepassen van het kader op dynamische of evoluerende grafen.