Technische Zusammenfassung: GRAPHLCP

Problemstellung

Graph-Neuronale Netze (GNN) werden zunehmend in hochriskanten Bereichen wie der Wirkstoffentwicklung, der Wettervorhersage und der Betrugserkennung eingesetzt, was eine zuverlässige Unsicherheitsquantifizierung (UQ) erfordert. Konformale Vorhersage (CP) bietet einen verteilungsfreien Rahmen, um mengenbasierte Vorhersagen mit Garantien für endliche Stichproben zu konstruieren. Die Anwendung von CP auf GNNs stellt jedoch einzigartige Herausforderungen dar:

1. Strukturelle Abhängigkeiten: Knoten in Graphen sind naturgemäß voneinander abhängig, was die für klassische CP erforderlichen Standardannahmen unabhängiger und identisch verteilter (i.i.d.) Daten verletzt.
2. Einschränkungen von Embeddings: Bestehende lokalisierte CP-Methoden für Graphen verlassen sich häufig auf die Nähe im Embedding-Raum (z. B. Kernel-Dichteschätzung auf GNN-Embeddings), um lokale Nachbarschaften zu definieren. Dieser Ansatz ist häufig unzuverlässig aufgrund von:
   • Überglättung: Tiefes Message Passing reduziert die Varianz von Ähnlichkeitsmaßen und macht Embeddings ununterscheidbar.
   • Überstauung: Topologische Engpässe beschränken den globalen Informationsfluss, insbesondere unter Heterophilie.
   • Untervertrauen: GNNs weisen oft eine unzureichende Trennschärfe in den gelernten Repräsentationen auf.
3. Ineffizienz bestehender Lösungen: Aktuelle graph-spezifische CP-Methoden verlassen sich entweder auf das Training zusätzlicher Modelle (was den Rechenaufwand erhöht) oder verwenden starre strukturelle Partitionen (z. B. harte Clusterung), die feingranulare lokale Heterophilie nicht erfassen können. Folglich liefern bestehende Methoden in komplexen Topologien oft übermäßig konservative oder schlecht lokalisierte Vorhersagemengen.

Methodik: GRAPHLCP

Die Autoren schlagen GRAPHLCP vor, ein proximitätsbasiertes Framework für lokalisierte Konformale Vorhersage, das entwickelt wurde, um Graph-Topologie und Knoten-zwischen-Knoten-Abhängigkeiten explizit in die Lokalisierungs- und Gewichtungsschritte zu integrieren. Die Methode arbeitet in einem transduktiven Setting, in dem das GNN vortrainiert und eingefroren ist. Das Framework besteht aus vier Schlüsselphasen:

1. Feature-bewusste Verdichtung

Um lokale Verzerrungen in spärlichen Graphen zu mindern und semantische Fernabhängigkeiten zu erfassen, führen die Autoren vor der Kernel-Berechnung einen Verdichtungsschritt ein.

• PCA-Projektion: Knoten-Embeddings werden zunächst mittels Hauptkomponentenanalyse (PCA) projiziert, um korrelierte Merkmalsdimensionen zu entkoppeln und den Raum zu kondensieren. Dies adressiert das durch Überglättung verursachte Rauschen und die Redundanz.
• Adaptiver anisotroper Kernel: Ein anisotroper Gauß-Kernel wird unter Verwendung der PCA-transformierten Embeddings konstruiert. Die Bandbreite wird basierend auf den Eigenwerten der Kovarianzmatrix angepasst, um unterschiedliche Skalen über die Dimensionen hinweg zu berücksichtigen.
• Kanten-Ergänzung: Neue Kanten werden zur Graph-Adjazenzmatrix hinzugefügt, wenn die Ähnlichkeit zwischen nicht verbundenen Knoten (berechnet via Gauß-Kernel) einen dynamischen Schwellenwert $\tau_d$ überschreitet. Dieser Schwellenwert wird automatisch basierend auf dem Homophilie-Verhältnis des Graphen angepasst, um die Hinzufügung informativer Kanten gegen die Einführung von Rauschen abzuwägen.

2. Personalisierter PageRank (PPR)-Kernel

Anstatt sich ausschließlich auf Embedding-Abstände zu verlassen, nutzt GRAPHLCP PPR, um strukturelle Nähe zu modellieren.

• Lokalisierung: PPR erfasst Multi-Hop-Einflüsse und bewahrt gleichzeitig die Lokalität über eine Neustartwahrscheinlichkeit ($\beta$). Es bietet ein weiches, probabilistisches Konzept der Nähe, das sich natürlich mit gewichteter CP in Einklang bringt.
• Sampling: Für einen Testknoten wird ein Ankerknoten aus der PPR-induzierten Verteilung, die um den Testknoten zentriert ist, gesampelt. Dies stellt sicher, dass nahegelegene Knoten einen größeren Einfluss auf die Quantilschätzung ausüben.
• Gewichtung: Kalibrations- und Testknoten werden entsprechend ihrer strukturellen Nähe zum gesampelten Anker gewichtet. Die Autoren nutzen die grad-normalisierte Symmetrie von PPR ($d_i H(u_i, u_j) = d_j H(u_j, u_i)$) aus, um Gewichte effizient zu berechnen, selbst wenn die Anzahl der Kalibrationsstichproben die Anzahl der Teststichproben übersteigt.

3. Integration von Randomized Localized Conformal Prediction (RLCP)

GRAPHLCP passt das RLCP-Framework an. Durch das Sampling eines Ankerknotens $\tilde{u}_{n+1}$ aus der PPR-Verteilung des Testknotens $u_{n+1}$ konstruiert die Methode eine Vorhersagemenge basierend auf einem gewichteten Quantil von Nicht-Konformitäts-Scores. Die Gewichte werden aus den PPR-Scores relativ zum gesampelten Anker abgeleitet, was der Methode ermöglicht, sich an den lokalen Graphkontext anzupassen.

4. Vorhersagekonstruktion

Die finale Vorhersagemenge $\hat{C}_n(u_{n+1})$ wird als die Menge der Labels $y$ konstruiert, für die der Nicht-Konformitäts-Score $s(u_{n+1}, y)$ kleiner oder gleich einem gewichteten Quantil $\hat{q}_{1-\alpha}$ ist. Dieses Quantil wird unter Verwendung der aus dem PPR-Kernel abgeleiteten Gewichte und der Nicht-Konformitäts-Scores des Kalibrationssatzes berechnet.

Hauptbeiträge

1. Strukturbewusste Lokalisierung: Die Arbeit schließt die Lücke zwischen struktureller und feature-basierter Lokalisierung, indem sie eine rein auf Embeddings beruhende Nähe durch einen PPR-basierten Kernel ersetzt. Dies integriert die Graph-Topologie explizit in den konformen Gewichtsprozess.
2. Feature-bewusste Verdichtung: Ein neuartiger Vorverarbeitungsschritt, der die Graph-Topologie unter Verwendung von Embedding-Ähnlichkeit (via PCA und adaptiver anisotroper Kernel) erweitert, um Spärlichkeit zu mindern und Fernabhängigkeiten zu erfassen, ohne sich auf die potenziell verrauschte kontinuierliche Gewichtung von Embeddings zu verlassen.
3. Effizientes Gewichtungsschema: Die Methode bietet einen effizienten Weg, PPR-basierte Gewichte für ungerichtete Graphen zu berechnen, indem sie die grad-normalisierte Symmetrie ausnutzt und so die rechnerische Ineffizienz der Berechnung vollständiger PPR-Vektoren für große Kalibrationsmengen vermeidet.
4. Theoretische Validität: Der Ansatz bewahrt die Austauschbarkeitsgarantien, die für marginale Abdeckung in transduktiven Settings erforderlich sind, und zielt gleichzeitig darauf ab, die relaxierte test-konditionale Abdeckung zu verbessern.

Experimentelle Ergebnisse

Die Autoren evaluierten GRAPHLCP auf sieben Knoten-Regression- und acht Knoten-Klassifizierungs-Datensätzen (einschließlich Zitationsnetzwerken, Amazon-Ko-Kauf-Daten und geografischen Datensätzen).

• Marginale Abdeckung: Alle Methoden, einschließlich GRAPHLCP, erfüllten die Ziel-Fehl-Abdeckungsrate ($\alpha = 0.1$), was die Validität des Ansatzes bestätigt.
• Konditionale Abdeckung (WSC): Bei Worst-Case-Slab (WSC)-Diagnostiken, die adversarisch die minimale Abdeckung über Projektionsrichtungen hinweg suchen, erzielte GRAPHLCP die besten oder zweitbesten Ergebnisse auf den meisten Datensätzen und übertraf Baselines wie CalLCP, RLCP und SCP.
• Gruppenbasierte Abdeckung: GRAPHLCP zeigte eine überlegene Abdeckung über Partitionen hinweg, die auf Homophilie, Feature-Clustering, Clustering-Koeffizient und Knotengrad basieren. Die Methode war insbesondere in heterophilen Regionen wirksam, in denen Standardmethoden Schwierigkeiten hatten.
• Vorhersageeffizienz: Während CalLCP oft übermäßig große Vorhersagemengen produzierte (Überabdeckung), erzielte GRAPHLCP günstige normalisierte Vorhersagelängen und bot einen besseren Kompromiss zwischen Abdeckung und Mengengröße.
• Ablationsstudien:
  • Der Ersatz des PPR-Kernels durch einen Gauß-Kernel (GSS) führte zu einer geringeren Abdeckung und größeren Vorhersagemengen, was die Bedeutung der strukturbewussten Lokalisierung bestätigt.
  • Der Verdichtungsschritt wurde als die bedeutendste Komponente identifiziert, insbesondere für Regressionsaufgaben.
  • Die PCA-Projektion erwies sich als entscheidend zur Minderung der negativen Effekte korrelierter Embedding-Features.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass GRAPHLCP die Einschränkungen bestehender graph-basierter CP-Methoden erfolgreich adressiert, indem es strukturelle Abhängigkeiten explizit modelliert. Durch die Entkopplung der Gewichte von potenziell verlustbehafteten GNN-Encodern und die Nutzung eines PPR-basierten Kernels schafft die Methode einen „lärmärmeren Residualpfad" für die Unsicherheitsquantifizierung.

Die Autoren behaupten, dass GRAPHLCP marginale Abdeckung mit endlichen Stichproben garantiert und gleichzeitig effizient eine günstige test-konditionale Abdeckung über verschiedene Konditionierungsszenarien hinweg erreicht. Sie heben hervor, dass die Methode insbesondere in komplexen Topologien robust ist, in denen auf Embeddings basierende Ähnlichkeiten aufgrund von Überglättung oder Überstauung versagen. Die Arbeit unterstreicht die Notwendigkeit einer strukturbewussten Lokalisierung für eine effektive UQ auf Graphen und geht über die reine Abhängigkeit von der Feature-Raum-Nähe hinaus. Die Autoren vermerken bescheiden, dass zukünftige Richtungen die Erweiterung dieses Frameworks auf dynamische Graphen mit sich entwickelnden Topologien umfassen.