Conformal Graph Prediction with Z-Gromov Wasserstein Distances

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een chemisch laboratorium runt en je moet een onbekend molecuul identificeren op basis van een ingewikkelde spectrumpatroon. Of stel je voor dat je een kunstwerk bekijkt en moet raden welk netwerk van verbindingen erachter zit. Dit zijn voorbeelden van "voorspelling van grafieken": in plaats van een simpel getal of een woord te voorspellen, moet een computer een heel complex netwerk (een grafiek) met knopen en lijnen voorspellen.

Het probleem? De meeste slimme computers zijn heel goed in het voorspellen van één antwoord, maar ze zijn vaak heel slecht in het zeggen: "Hoe zeker ben je eigenlijk?" Als de computer zegt: "Dit is het molecuul!", maar hij is eigenlijk maar 50% zeker, kan dat in de echte wereld (bijvoorbeeld in de geneeskunde) rampzalig zijn.

Deze paper introduceert een slimme nieuwe manier om die zekerheid te meten, zelfs voor deze complexe netwerken. Hier is hoe het werkt, vertaald naar alledaags taal:

1. Het Probleem: De "Gok" van de Computer

Stel je voor dat je een raadsel oplost. De computer geeft je één oplossing. Maar wat als er tien andere oplossingen zijn die bijna even goed zijn?

Huidige methode: De computer zegt: "Het is deze ene oplossing!" (Zonder te zeggen dat er twijfel is).
Nieuwe methode: De computer zegt: "Ik denk dat het deze oplossing is, maar hier is een lijstje met 5 mogelijke opties. De echte oplossing zit er zeker tussen!"

Dit lijstje noemen ze een "Conformal Set". Het is een veilige net dat de echte oplossing nooit laat vallen, zelfs als de computer het niet helemaal snapt.

2. De Uitdaging: Netwerken zijn lastig te vergelijken

Grafieken (netwerken) zijn lastig. Stel je twee moleculen voor die exact dezelfde atomen en bindingen hebben, maar de atomen zijn net andersom genummerd. Voor een mens zijn het hetzelfde molecuul, maar voor een computer zijn het twee verschillende lijsten met getallen.

Om te weten of een voorspelling goed of slecht is, moet je de voorspelling kunnen vergelijken met de echte oplossing, ongeacht hoe de onderdelen zijn genummerd.

De Oplossing: De "Z-Gromov-Wasserstein" (Z-GW) afstand
Dit klinkt als een onmogelijk woord, maar het is eigenlijk een slimme meetlat.

Stel je voor dat je twee verschillende kaarten van een stad hebt. Op de ene kaart staan de straten in het Nederlands, op de andere in het Frans. De straten heten anders, maar het patroon is hetzelfde.
Een gewone meetlat zou zeggen: "Deze straten heten anders, dus de kaarten zijn totaal verschillend!"
De Z-GW-maatstaf is een slimme meetlat die zegt: "Ik kijk niet naar de namen, maar naar de structuur. Deze twee kaarten zijn eigenlijk hetzelfde, zelfs als de namen anders zijn."

Met deze maatstaf kan de computer zeggen: "Mijn voorspelling lijkt qua structuur heel erg op de echte oplossing, dus ik ben er zeker van." Of: "Mijn voorspelling lijkt totaal niet op de echte oplossing, dus ik moet een groter lijstje met opties geven."

3. De Innovatie: "Score Conformalized Quantile Regression" (SCQR)

In het begin dachten de onderzoekers: "Laten we voor iedereen hetzelfde lijstje maken." Maar dat werkt niet goed.

Soms is een raadsel heel makkelijk (de computer weet het bijna zeker).
Soms is het raadsel heel moeilijk (de computer twijfelt).

Als je voor een makkelijk raadsel een lijstje van 100 opties maakt, is dat zonde (te veel rommel). Als je voor een moeilijk raadsel maar 1 optie geeft, is dat gevaarlijk (te weinig zekerheid).

De Oplossing: Een slimme, aanpasbare maatstaf
De auteurs bedachten SCQR. Dit is als een slimme leraar die kijkt naar de moeilijkheidsgraad van de vraag:

Is de vraag makkelijk? Dan geeft de leraar je maar 1 of 2 mogelijke antwoorden.
Is de vraag moeilijk? Dan geeft de leraar je een groter lijstje met opties, zodat je zeker weet dat het juiste antwoord erbij zit.

Dit zorgt ervoor dat het lijstje altijd de juiste grootte heeft: niet te groot (omdat je niet wilt zoeken in een berg rommel) en niet te klein (omdat je het juiste antwoord niet wilt missen).

4. Wat hebben ze getest?

Ze hebben hun methode getest op twee dingen:

Een synthetisch spel: Waar je een afbeelding moet vertalen naar een gekleurd netwerk. Hier werkte het perfect.
Echt molecuulonderzoek: Waar ze spectra (een soort vingerafdruk van een molecuul) moesten vertalen naar de daadwerkelijke chemische structuur.
- Resultaat: Hun methode gaf een lijstje met moleculen waar de echte oplossing altijd in zat (90% van de tijd), maar het lijstje was veel kleiner dan de totale lijst met alle mogelijke moleculen. Ze filterden dus de rommel weg en hielden alleen de serieuze kandidaten over.

Samenvatting in één zin

Deze paper geeft computers een manier om te zeggen: "Ik weet niet zeker wat het antwoord is, maar ik kan je een klein, veilig lijstje geven waar het antwoord zeker in zit, en ik pas de grootte van dat lijstje aan op basis van hoe moeilijk de vraag is."

Dit is een enorme stap voorwaarts voor het veilig toepassen van kunstmatige intelligentie in complexe gebieden zoals chemie en biologie, waar fouten maken duur of gevaarlijk kan zijn.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het artikel "Conformal Graph Prediction with Z-Gromov Wasserstein Distances" in het Nederlands.

Probleemstelling

Het artikel adresseert het probleem van toezicht op grafvoorspelling (Supervised Graph Prediction - SGP), waarbij de uitkomsten gestructureerde grafen zijn (bijvoorbeeld moleculen in de chemie of scènes in computer vision). Hoewel er methoden bestaan om grafen te voorspellen, ontbreekt er een robuuste manier om de onzekerheid van deze voorspellingen te kwantificeren. Bestaande methoden leveren vaak slechts een enkele voorspelling, wat riskant is wanneer experimentele validatie kostbaar is.

De uitdagingen bij het toepassen van onzekerheidskwantificatie op grafen zijn:

Gestructureerde uitruim: Grafen leven in een niet-Euclidische, combinatorische ruimte.
Permutatie-invariantie: Grafen zijn gedefinieerd tot op een permutatie van knopen; twee grafen met dezelfde structuur maar verschillende knooplabels moeten als identiek worden beschouwd.
Heteroscedasticiteit: De onzekerheid varieert vaak per invoer (sommige invoeren zijn makkelijker te voorspellen dan andere), maar standaard methoden gebruiken vaak één globale drempel.

Methodologie

De auteurs stellen een raamwerk voor dat Conformal Prediction (CP) combineert met Z-Gromov-Wasserstein (Z-GW) afstanden om voorspellende sets te genereren die gegarandeerd de waarheid bevatten met een bepaalde waarschijnlijkheid, zonder aannames over de onderliggende data-verdeling.

1. Z-Gromov-Wasserstein Afstand als Niet-Conformiteits Score

Om de discrepantie tussen een voorspelde graaf en een kandidaat-graaf te meten, gebruiken de auteurs de Z-Gromov-Wasserstein (Z-GW) afstand.

Grafen als Z-netwerken: Grafen worden gemodelleerd als "Z-netwerken", waarbij knopen en randen attributen hebben die worden vergeleken via een metriek in een ruimte $Z$ .
Permutatie-invariantie: De Z-GW afstand is per definitie invariant onder knoop-permutaties. Dit betekent dat de afstand tussen twee grafen niet afhangt van hoe de knopen zijn genummerd, wat essentieel is voor geldige conformale voorspelling in de quotiëntruimte van grafen (waar grafen worden geïdentificeerd tot op isomorfisme).
Praktische implementatie: In de experimenten wordt de Fused Gromov-Wasserstein (FGW) afstand gebruikt, die zowel de structuur van de graaf (bijv. adjacency matrix) als knoop- en randattributen combineert.

2. Conformal Graph Prediction Framework

Niet-conformiteits score: $s(x, y) = GW_Z^p(f_\theta(x), y)$ , waarbij $f_\theta$ de voorspeller is en $y$ een kandidaat-graaf.
Geldigheid: Het artikel bewijst dat, omdat de score invariant is onder permutaties, de conformale voorspellingsset geldig is in de quotiëntruimte van grafen. Dit garandeert dat de kans dat de ware graaf in de set zit, minimaal $1-\alpha$ is.
Beperking tot kandidaatbibliotheken: Omdat de ruimte van alle mogelijke grafen te groot is om te enumereren, intersecteert het framework de impliciete conformale set met een invoer-afhankelijke kandidaatbibliotheek $L(x)$ (bijv. een database van moleculen die overeenkomen met een massaspectrum).

3. Score Conformalized Quantile Regression (SCQR)

Om de beperking van een enkele globale drempel te overwinnen, introduceren de auteurs SCQR.

Adaptiviteit: In plaats van één globale drempel te gebruiken, past SCQR de drempel lokaal aan op basis van invoer-afhankelijke kenmerken $\omega(x)$ (zoals de grootte van de kandidaatset of een embedding van de invoer).
Werking: Het model schat eerst de conditionele quantiel van de niet-conformiteits scores gegeven $\omega(x)$ via kwantielregressie. Vervolgens wordt een residu berekend en wordt de conformale set bepaald door deze adaptieve drempel. Dit leidt tot smaller voorspellende sets voor "makkelijke" invoeren en bredere sets voor "moeilijke" invoeren, terwijl de marginale dekking behouden blijft.

Belangrijkste Bijdragen

Raamwerk voor Conformal Graph Prediction: Een nieuw raamwerk dat Z-Gromov-Wasserstein afstanden gebruikt om geldige, permutatie-invariante voorspellende sets te genereren voor graf-uitkomsten.
Theoretische Geldigheid: Een wiskundig bewijs dat de methode geldige dekking garandeert in de quotiëntruimte van grafen (waar grafen worden geïdentificeerd tot op isomorfisme).
SCQR: Een lokaal adaptieve variant van Conformal Prediction die de efficiëntie verbetert door rekening te houden met heteroscedasticiteit in gestructureerde uitruim.
Empirische Validatie: Uitgebreide experimenten op synthetische data (image-to-graph) en een reëel probleem (metabolietidentificatie uit massaspectrometrie).

Resultaten

De methode werd getest op twee taken:

Synthetische "Coloring" Taak: Het voorspellen van een graaf uit een afbeelding.
- Zowel CP als SCQR behaalden een empirische dekking van ~90% (doel: 90%).
- SCQR, gekalibreerd op de grootte van de kandidaatset, leverde vergelijkbare resultaten op als standaard CP, met een mediane setgrootte van 1 en een reductie van de kandidaatset van >95%.
Metabolietidentificatie (MassSpecGym): Het identificeren van moleculen uit massaspectra.
- Dekking: Beide methoden behaalden een dekking van ~89-90%.
- Efficiëntie: SCQR toonde hier een aanzienlijke verbetering. Door de drempel te conditioneren op de DREAMS-embedding (een leerzame representatie van het spectrum) in plaats van alleen de setgrootte, daalde de gemiddelde grootte van de conformale set van 24 (bij standaard CP) naar 15.
- Dit resulteerde in een hogere reductie van de kandidaatset (van 77% naar 85%) zonder verlies aan dekking.
- SCQR verminderde ook het "heavy-tail" effect, waarbij sommige voorspellingen extreem grote sets opleverden.

Betekenis en Conclusie

Dit werk is significant omdat het een brug slaat tussen de wiskundige theorie van optimale transport (Gromov-Wasserstein) en de praktische behoefte aan betrouwbare onzekerheidskwantificatie in gestructureerde machine learning.

Voor de chemie en bio-informatica: Het biedt een veilige manier om moleculen te identificeren door niet één "beste" kandidaat te geven, maar een gegarandeerd kleine set van waarschijnlijke moleculen. Dit bespaart tijd en geld in het laboratorium.
Algemene toepasbaarheid: Het raamwerk is model-onafhankelijk en kan worden toegepast op elke taak waarbij de uitkomst een gestructureerd object is (zoals netwerken, meshes of puntswolken) dat als een Z-netwerk kan worden gemodelleerd.
Adaptiviteit: De introductie van SCQR voor gestructureerde uitkomsten toont aan dat het mogelijk is om lokale onzekerheid te benutten om voorspellende sets te verfijnen, zelfs in complexe, niet-Euclidische ruimtes.

Kortom, de auteurs bieden een wiskundig onderbouwde, praktische oplossing voor het probleem van "hoe zeker zijn we van onze grafvoorspelling?", wat een cruciale stap is voor de adoptie van AI in kritieke domeinen zoals drugontwikkeling.