Conformal Graph Prediction with Z-Gromov Wasserstein Distances

Die Autoren schlagen einen konformen Vorhersagerahmen für graphenbasierte Ausgaben vor, der mithilfe des Z-Gromov-Wasserstein-Abstands und der Score Conformalized Quantile Regression (SCQR) eine verteilungsfreie Unsicherheitsquantifizierung für strukturierte Graphen wie Moleküle ermöglicht.

Das Wesentliche

Stell dir vor, du bist ein Detektiv, der versuchen muss, ein vermisstes Objekt zu identifizieren. In der Welt der künstlichen Intelligenz (KI) ist das oft eine chemische Verbindung (ein Molekül), die aus einem Spektrogramm (einer Art „Fingerabdruck" aus Licht und Energie) rekonstruiert werden muss.

Das Problem: Die KI kann oft nicht ein einziges Molekül nennen, das zu 100 % passt. Sie ist unsicher. Wenn sie sich irrt, kann das in der Chemie teuer oder gefährlich werden.

Dieser Paper beschreibt eine neue Methode, um dieser Unsicherheit gerecht zu werden. Statt nur eine „best guess"-Antwort zu geben, sagt die KI: „Hier ist eine Liste von 10 möglichen Kandidaten, und ich garantiere dir, dass das richtige Molekül mit 90 % Wahrscheinlichkeit dabei ist."

Hier ist die einfache Erklärung der drei wichtigsten Ideen, wie ein Detektiv, der mit einem neuen Werkzeug arbeitet:

1. Das Problem: Vergleiche von „Lego-Bauten"

Stell dir vor, du hast zwei Lego-Modelle. Sie sehen gleich aus, aber bei einem sind die Steine anders durcheinander gewürfelt (die Reihenfolge der Steine ist anders).

• Das alte Problem: Herkömmliche Computerprogramme vergleichen oft Steine an Steinen. Wenn der rote Stein bei Modell A an Position 1 ist und bei Modell B an Position 5, denken sie, es sind zwei völlig verschiedene Modelle. Das ist falsch! Es ist dasselbe Modell, nur anders „beschriftet".
• Die Lösung (Z-Gromov-Wasserstein): Die Autoren nutzen eine spezielle mathematische Methode (den Z-Gromov-Wasserstein-Abstand), die wie ein kluger Architekt funktioniert. Dieser Architekt schaut nicht auf die Nummern der Steine, sondern auf die Beziehungen zwischen ihnen.
  • Analogie: Es ist wie beim Vergleich von zwei Freundesgruppen. Es ist egal, ob du die Leute in alphabetischer Reihenfolge oder nach Alter auflistest. Der Architekt schaut nur: „Wer kennt wen?" und „Wer sitzt wo?". Wenn die Struktur der Freundschaften gleich ist, sind die Gruppen identisch, egal wie sie benannt sind.

2. Der Sicherheitsgürtel: Konforme Vorhersage

Normalerweise gibt eine KI eine Zahl oder ein Bild aus und hofft, dass es stimmt. Diese Methode fügt einen Sicherheitsgürtel hinzu.

• Das alte System: Ein Wetterbericht sagt: „Morgen wird es 20 Grad." (Keine Unsicherheit).
• Das neue System (Konforme Vorhersage): Der Bericht sagt: „Es wird zwischen 18 und 22 Grad."
• Der Trick: Die KI berechnet für jede neue Aufgabe eine „Unsicherheits-Schwelle". Sie schaut sich ihre Fehler in der Vergangenheit an und sagt: „Okay, um zu 90 % sicher zu sein, muss ich meine Antwortliste so groß machen, dass das richtige Ergebnis fast immer dabei ist."
• Das Ergebnis: Die KI gibt dir keine einzelne, riskante Antwort, sondern einen Korb mit Kandidaten. Wenn der Korb groß genug ist, ist die Garantie mathematisch bewiesen, dass das Richtige drin ist.

3. Der intelligente Korb: Adaptive Größe (SCQR)

Hier wird es noch cleverer. Nicht alle Aufgaben sind gleich schwer.

• Das alte System: Ein Sicherheitsgürtel, der für alle gleich dick ist. Bei einer leichten Aufgabe (einfaches Molekül) ist der Korb unnötig riesig (zu viele Kandidaten). Bei einer schweren Aufgabe (komplexes Molekül) ist der Korb vielleicht zu klein, um das Richtige zu fangen.
• Die neue Lösung (SCQR): Die KI nutzt einen intelligenten Korb, der sich anpasst.
  • Analogie: Stell dir vor, du packst einen Koffer für eine Reise.
    • Für einen kurzen Tagesausflug (einfache Aufgabe) nimmst du nur einen kleinen Rucksack (kleine Kandidatenliste).
    • Für eine Weltreise um die Welt (schwere Aufgabe) nimmst du einen riesigen Koffer (große Kandidatenliste).
  • Die Methode SCQR erkennt, wie schwierig die aktuelle Aufgabe ist (basierend auf den Eingabedaten), und passt die Größe des „Korbs" dynamisch an. So vermeidet sie, den Nutzer mit hunderten unnötigen Möglichkeiten zu überfluten, wenn nur wenige nötig wären.

Zusammenfassung: Was bringt das?

Die Autoren haben ein Werkzeug gebaut, das:

1. Strukturen versteht: Es vergleicht komplexe Formen (wie Moleküle) richtig, ohne sich von der Reihenfolge der Teile täuschen zu lassen.
2. Ehrlich ist: Es gibt keine falsche Sicherheit. Es sagt offen: „Ich bin mir nicht zu 100 % sicher, aber hier ist eine Liste, in der das Richtige mit hoher Wahrscheinlichkeit steckt."
3. Effizient ist: Es passt die Größe dieser Liste automatisch an die Schwierigkeit der Aufgabe an.

Warum ist das wichtig?
In der Medizin oder Chemie ist es besser, 5 mögliche Medikamente zu testen, als sich auf ein falsches zu verlassen, das die KI „für sicher" hielt. Diese Methode hilft Wissenschaftlern, kostspielige Experimente zu planen, indem sie ihnen sagt: „Suche in diesen 10 Kandidaten, das ist der sicherste Weg."

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Conformal Graph Prediction with Z-Gromov-Wasserstein Distances" auf Deutsch:

1. Problemstellung

Das Paper adressiert das Problem der überwachten Graph-Vorhersage (Supervised Graph Prediction, SGP). Bei dieser Aufgabe wird ein Eingabewert beliebiger Modalität (z. B. Text, Bild, Spektren) auf einen Zielgraphen beliebiger Größe abgebildet. Solche Aufgaben sind in Bereichen wie der molekularen Identifizierung (Chemie) oder dem Szenenverständnis (Computer Vision) von zentraler Bedeutung.

Das Hauptproblem besteht darin, dass bestehende Methoden zur Graph-Vorhersage zwar präzise Punktvorhersagen liefern können, aber keine quantifizierbare Unsicherheit bieten. In kritischen Anwendungen, wo experimentelle Validierungen kostspielig sind (z. B. Synthese neuer Moleküle), ist es jedoch essenziell, Konfidenzmengen (Sets von plausiblen Graphen) statt eines einzelnen Graphen zu liefern.

Herausforderungen bei der Unsicherheitsquantifizierung für Graphen sind:

• Der Output-Raum ist hochdimensional, nicht-euklidisch und kombinatorisch strukturiert.
• Graphen sind bis auf Knotenpermutationen definiert (Isomorphie), was eine Permutationsinvarianz der Bewertungsmetriken erfordert.
• Herkömmliche konforme Vorhersage (Conformal Prediction, CP) ist in solchen Räumen schwer anwendbar, da keine natürlichen Ordnungen existieren und die Dimensionalität hoch ist.

2. Methodik

Die Autoren schlagen einen konformen Vorhersagerahmen (Conformal Prediction Framework) vor, der distributionfreie Garantien für die Abdeckung (Coverage) in strukturierten Output-Räumen bietet.

A. Z-Gromov-Wasserstein-Distanz (Z-GW) als Nicht-Konformitäts-Score

Um die Diskrepanz zwischen einem vorhergesagten Graphen und einem Kandidaten-Graphen zu messen, definieren die Autoren einen Nicht-Konformitäts-Score basierend auf der Z-Gromov-Wasserstein-Distanz.

• Z-Netzwerke: Graphen werden als endliche Z-Netzwerke modelliert, die sowohl die Struktur (Kanten) als auch Knotenattribute (Features) in einer gemeinsamen Metrik erfassen.
• Permutationsinvarianz: Die Z-GW-Distanz ist invariant gegenüber Knoten-Umbenennungen. Dies ist entscheidend, da sie im Quotientenraum der Graphen (bis auf Isomorphie) operiert.
• Praktische Umsetzung: In der Praxis wird die Distanz oft als Fused Gromov-Wasserstein (FGW) Distanz implementiert, die Struktur und Features kombiniert.
• Theoretische Fundierung: Das Paper beweist, dass die konforme Vorhersage auf dem Quotientenraum (Äquivalenzklassen von Graphen) gültig bleibt, solange die Daten austauschbar (exchangeable) sind.

B. Score Conformalized Quantile Regression (SCQR)

Standard-CP verwendet einen globalen Schwellenwert, was implizit eine homogene Unsicherheit über alle Eingaben annimmt. Um dies zu überwinden, führen die Autoren SCQR ein:

• Lokale Anpassung: Anstatt eines globalen Schwellenwerts wird der Schwellenwert konditional auf Eingabe-Attribute $\omega(x)$ angepasst (z. B. Größe des Kandidaten-Sets oder spektrale Einbettungen).
• Mechanismus: Es wird eine Quantilregression trainiert, um das $(1-\alpha)$-Quantil des Nicht-Konformitäts-Scores basierend auf den Eingabe-Attributen vorherzusagen. Die Residuen werden dann kalibriert, um einen adaptiven Schwellenwert zu erhalten.
• Vorteil: SCQR liefert lokal adaptive Konfidenzmengen, die bei „einfachen" Eingaben kleiner (effizienter) und bei „schwierigen" Eingaben größer sind, während die marginale Abdeckungsgarantie erhalten bleibt.

C. Praktische Einschränkung (Candidate Sets)

Da der Raum aller möglichen Graphen kombinatorisch riesig ist, kann die konforme Menge nicht explizit enumeriert werden. Daher wird die implizite konforme Menge mit einer eingabeabhängigen Kandidatenbibliothek $L(x)$ (z. B. eine Datenbank von Molekülen, die zum Massenspektrum passen) geschnitten. Die Vorhersagemenge besteht aus allen Graphen in $L(x)$, deren Score unter dem kalibrierten Schwellenwert liegt.

3. Wichtige Beiträge

1. Framework für konforme Graph-Vorhersage: Ein neuartiger Ansatz, der Z-Gromov-Wasserstein-Distanzen nutzt, um konforme Mengen für Graphen mit kategorischen Knotenattributen zu definieren. Der Rahmen ist modellagnostisch und gilt für beliebige Graphen-Prädiktoren.
2. Theoretische Gültigkeit: Beweis der Gültigkeit der konformen Abdeckung im Quotientenraum der Graphen (bis auf Permutation), was die mathematische Grundlage für den Umgang mit Isomorphie legt.
3. SCQR (Score Conformalized Quantile Regression): Eine Erweiterung der CQR für komplexe Output-Räume, die lokale Unsicherheiten berücksichtigt und effizientere Vorhersagemengen ermöglicht.
4. Empirische Validierung: Anwendung auf synthetischen Daten (Image-to-Graph) und einem realen Problem (Metaboliten-Identifizierung aus Massenspektren).

4. Ergebnisse

Die Methode wurde auf zwei Datensätzen evaluiert:

1. Synthetischer „Coloring"-Datensatz: Bilder werden auf Graphen mit Knotenfarben abgebildet.
2. MassSpecGym (Metaboliten-Identifizierung): Massenspektren werden auf molekulare Graphen abgebildet.

Ergebnisse im Überblick:

• Abdeckungsgarantie: Beide Methoden (Standard-CP und SCQR) erreichen eine empirische Abdeckung von ca. 90 % (bei einem nominalen Niveau von 90 %), was die theoretische Gültigkeit bestätigt.
• Effizienz (Größe der Mengen):
  • Auf dem synthetischen Datensatz zeigte SCQR ähnliche Ergebnisse wie Standard-CP, da die Unsicherheit hier weniger stark variiert.
  • Auf dem Metaboliten-Datensatz war SCQR überlegen. Durch Konditionierung auf spektrale Einbettungen (DREAMS) konnte die durchschnittliche Größe der Konfidenzmengen von 24 (bei CP) auf 15 reduziert werden, während die Abdeckung erhalten blieb. Dies entspricht einer Steigerung der Reduktion der Kandidatenmenge von 77,1 % auf 84,8 %.
• Verteilung der Mengen: SCQR reduziert das „Heavy-Tail"-Verhalten (sehr große Mengen bei wenigen schwierigen Fällen) und liefert insgesamt kompaktere Mengen.
• Z-GW Varianten: Die Verwendung von FGW (Fused GW), die sowohl Struktur als auch Features nutzt, führte zu kleineren und präziseren Mengen als reine GW-Distanzen (nur Struktur).

5. Bedeutung und Ausblick

Dieses Paper schließt eine wichtige Lücke im Bereich des maschinellen Lernens für strukturierte Daten, indem es Unsicherheitsquantifizierung für Graphen auf ein solides, distributionfreies Fundament stellt.

• Praktische Relevanz: Besonders in der Chemie (Metaboliten-Identifizierung) ermöglicht der Ansatz, die Anzahl der zu validierenden Kandidaten drastisch zu reduzieren, ohne die Zuverlässigkeit zu opfern.
• Allgemeine Anwendbarkeit: Der Rahmen ist nicht auf Graphen beschränkt, sondern lässt sich auf andere strukturierte Output-Räume übertragen, die als Z-Netzwerke darstellbar sind (z. B. Punktwolken, Meshes, Verteilungen).
• Zukunft: Die Kombination von optimaler Transport-Theorie (OT) mit konformer Vorhersage eröffnet neue Wege für robuste KI-Systeme in wissenschaftlichen Entdeckungsprozessen.

Zusammenfassend bietet das Paper eine robuste, theoretisch fundierte und praktisch effiziente Lösung für das Problem, wie man bei Graph-Vorhersagen nicht nur den „besten" Graphen, sondern eine verlässliche Menge möglicher Lösungen liefert.