🤖 machine learning

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory

Dieser Beitrag schlägt einen neuartigen Ansatz zur Unsicherheitsschätzung für heterophile Graphen vor, der informationstheoretische Methoden nutzt, um nachzuweisen, dass Knotenrepräsentationen unterschiedlicher Tiefen distinkte Informationen liefern, was zu einem state-of-the-art-Post-hoc-Dichteschätzer im gemeinsamen Knoten-Embedding-Raum führt, der auf heterophilen Graphen bestehende Methoden übertrifft und gleichzeitig die Leistung auf homophilen Graphen beibehält.

Ursprüngliche Autoren: Dominik Fuchsgruber, Tom Wollschläger, Johannes Bordne, Stephan Günnemann

Veröffentlicht 2026-05-12

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Dominik Fuchsgruber, Tom Wollschläger, Johannes Bordne, Stephan Günnemann

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Problem: Wenn „Freunde" dich anlügen

Stell dir vor, du versuchst zu erraten, was der Lieblingsfilm einer Person ist. In der Welt des maschinellen Lernens verwenden wir oft Graph Neural Networks (GNNs). Denk an ein GNN als einen Detektiv, der ein Rätsel löst, indem er die Nachbarn des Verdächtigen befragt.

Der alte Weg (Homophilie): Normalerweise gehen diese Detektive davon aus, dass „Gleich und Gleich sich gerne findet". Wenn deine Nachbarn alle Action-Filme lieben, geht der Detektiv davon aus, dass du es wahrscheinlich auch tust. Das funktioniert großartig, wenn Freunde ähnlich sind.
Das neue Problem (Heterophilie): Aber was, wenn du in einer Gruppe bist, in der jeder unterschiedlich ist? Vielleicht lieben deine Nachbarn Horror, Comedy und Sci-Fi, aber du liebst Action. In diesem „heterophilen" Setting gerät der alte Detektiv in Verwirrung. Wenn er einfach nur das Mittel aus dem zieht, was seine Nachbarn sagen, könnte er „Action" raten (weil es der Mittelweg ist) oder völlig den Überblick verlieren. Sie werden übermäßig zuversichtlich bei einer falschen Antwort, was in hochriskanten Situationen gefährlich ist.

Das Paper fragt: Wie können wir diese KI-Detektive lehren, zu sagen: „Ich bin mir nicht sicher", wenn ihre Nachbarn sie verwirren?

Die Kernidee: Die ganze Geschichte hören, nicht nur die Schlagzeile

Die Autoren untersuchten, wie diese KI-Modelle Information Schicht für Schicht verarbeiten. Sie verwendeten ein Konzept aus der Informationstheorie (die Mathematik darüber, wie viel „Nachricht" eine Botschaft trägt).

Die Analogie des Staffellaufs:
Stell dir das KI-Modell als einen Staffellauf vor.

Schicht 1: Der Läufer bekommt einen Stab (Daten) von den unmittelbaren Nachbarn.
Schicht 2: Der Läufer gibt ihn an die nächste Person weiter, die Informationen von Nachbarn der Nachbarn hinzufügt.
Schicht 3: Und so weiter.

In der alten Welt der „ähnlichen Freunde" bekommt der Stab immer wieder dieselbe Nachricht. Bis er das Ziel erreicht, ist die Nachricht klar, aber repetitiv.

In der Welt der „unterschiedlichen Freunde" (heterophil) ändert sich die Bedeutung des Stabs bei jedem Schritt.

Schicht 1 könnte dir etwas über den Geschmack deines unmittelbaren Nachbarn erzählen.
Schicht 2 könnte dir etwas über den Kontrast zwischen dir und diesem Nachbarn erzählen.
Schicht 3 könnte ein Muster über die ganze Gruppe enthüllen, das du aus nur einem Schritt Entfernung nicht erkennen könntest.

Der Fehler: Die meisten aktuellen Methoden schauen nur auf den letzten Läufer (die letzte Schicht), um zu entscheiden, ob die KI zuversichtlich ist. Sie werfen die Notizen der früheren Läufer weg.

Die Entdeckung des Papers: In verwirrenden (heterophilen) Situationen halten die früheren Läufer tatsächlich einzigartige, vitale Informationen, die der letzte Läufer vielleicht vergessen oder geglättet hat. Wenn du nur dem letzten Läufer zuhörst, verpasst du das Gesamtbild.

Die Lösung: JLDE (Der „Gruppenchat"-Ansatz)

Die Autoren schlagen eine neue Methode namens Joint Latent Density Estimation (JLDE) vor.

Die Metapher:
Anstatt nur den letzten Läufer zu fragen: „Bist du dir sicher?", fragt JLDE jeden im Staffelteam, seine Notizen aufzuschreiben, fasst alle diese Notizen in einem riesigen „Gruppenchat" zusammen und fragt dann: „Sieht diese kombinierte Geschichte wie die Geschichten aus, die wir zuvor gesehen haben?"

Wenn die kombinierte Geschichte wie eine typische Geschichte aus den Trainingsdaten aussieht, ist die KI zuversichtlich.
Wenn die kombinierte Geschichte seltsam aussieht oder nicht mit irgendetwas übereinstimmt, das sie gesehen hat, sagt die KI: „Ich bin mir nicht sicher" und markiert sie als unsicher.

Sie testeten dies mit einem einfachen „K-Nächste-Nachbarn"-Ansatz (im Grunde: „Finde die 5 ähnlichsten vergangenen Geschichten und sieh, wie nah diese hier dran ist").

Was sie herausfanden

Es funktioniert bei verwirrenden Graphen: Auf Graphen, bei denen die Nachbarn unterschiedlich sind (wie den Datensätzen „Amazon Ratings" oder „Römisches Reich"), war JLDE am besten darin, zu erkennen, wann die KI verwirrt war oder seltsame Daten betrachtete. Es übertraf alle anderen Methoden.
Es schadet einfachen Graphen nicht: Auf Graphen, bei denen die Nachbarn ähnlich sind (wie „CoraML"), funktionierte JLDE genauso gut wie die besten bestehenden Methoden. Es musste nicht „repariert" oder „geglättet" werden, um zu funktionieren; es handhabte einfach beide Arten von Graphen auf natürliche Weise.
Die „Alle-Schichten"-Regel: Die Experimente bewiesen, dass das Betrachten aller Schichten des Netzwerks (nicht nur der letzten) der Schlüssel zu einer genauen Unsicherheitsschätzung ist. Als sie versuchten, nur die letzte Schicht zu verwenden, sank die Leistung bei den verwirrenden Graphen erheblich.

Zusammenfassung in einem Satz

Um zu wissen, ob eine KI zuversichtlich ist, wenn ihre Nachbarn verwirrend sind, solltest du nicht nur ihre endgültige Schlussfolgerung anhören; du musst die einzigartigen Erkenntnisse aus jedem Schritt ihres Denkprozesses kombinieren, um das Gesamtbild zu erhalten.

Technische Zusammenfassung: Unsicherheitsschätzung für heterophile Graphen durch die Linse der Informationstheorie

Problemstellung

Die Unsicherheitsschätzung für Graph-Neuronale Netze (GNNs) hat erhebliche Aufmerksamkeit erhalten, doch die meisten bestehenden Methoden stützen sich stark auf die Annahme von Homophilie – die Tendenz von Knoten, sich mit anderen derselben Klasse zu verbinden. Diese Methoden setzen häufig Graphen-Diffusion oder Glättungskernel ein, um Unsicherheit zu propagieren, was effektiv ist, wenn semantisch ähnliche Knoten verbunden sind. In heterophilen Settings, in denen Knoten primär Nachbarn unterschiedlicher Klassen verbinden, verschlechtern sich diese Ansätze jedoch. Die reliance auf Glättung zur Propagation von (Un-)Sicherheit ist in heterophilen Graphen weniger gerechtfertigt, was zu schlechter Leistung bei der Erkennung von Out-of-Distribution (O.O.D.) und zur Unsicherheitsquantifizierung führt. Darüber hinaus haben frühere Arbeiten nicht systematisch untersucht, wie Unsicherheitsschätzer verhalten, wenn Homophilie-Annahmen verletzt werden, und es gab keinen dedizierten Ansatz für heterophile Graphen, der die explizite Ausnutzung von Homophilie vermeidet.

Methodik

Die Autoren nähern sich dem Problem aus einer informationstheoretischen Perspektive, indem sie Message Passing Neural Networks (MPNNs) analysieren, um zu verstehen, wie latente Knotenrepräsentationen durch die Schichten evolvierten.

1. Informationstheoretische Analyse von MPNNs

Inspiriert vom Informationsflaschenhals-Prinzip (Tishby & Zaslavsky, 2015) modellieren die Autoren den Informationsfluss in MPNNs. Im Gegensatz zu Standard-Neuronalen Netzen für unabhängige und identisch verteilte (i.i.d.) Daten, bei denen die Datenverarbeitungsungleichung (DPI) vorschreibt, dass Informationen über eine Zielvariable durch die Schichten nur abnehmen oder konstant bleiben können, leiten die Autoren eine Datenverarbeitungsgleichheit (DPE) für MPNNs her.

Zentrale theoretische Erkenntnisse umfassen:

Informationswiederherstellung und -gewinn: In MPNNs sind Informationen über die Label $Y$ eines Knotens nicht ausschließlich in den eigenen Merkmalen des Knotens enthalten, sondern über den Ego-Graphen verteilt. Die Autoren definieren einen Ego-Graphen $G_v$ , der in disjunkte Mengen $G_v^{(i)}$ basierend auf der Hop-Distanz zerlegt wird.
Die Gleichheit: Die gegenseitige Information $I(Y; Z^{(i+1)})$ , die von einer Repräsentation in Schicht $i+1$ gehalten wird, additiv zerfällt:
$I(Y; Z^{(i+1)}) = I(Y; Z^{(i)}) - \Delta_{(-)}^{(0:i)} + \Delta_{(+)}^{(i+1)}$
Hierbei repräsentiert $\Delta_{(-)}^{(0:i)}$ Informationsverlust (oder -wiederherstellung) bezüglich des bestehenden Ego-Graphen, und $\Delta_{(+)}^{(i+1)}$ repräsentiert den Informationsgewinn aus den neuen Nachbarn mit $i+1$ Hops.
Heterophilie vs. Homophilie:
- In homophilen Graphen teilen benachbarte Knoten ähnliche Semantik. Folglich nimmt der Informationsgewinn $\Delta_{(+)}^{(i+1)}$ mit zunehmender Tiefe ab, da tiefere Schichten keine neuen semantischen Informationen über das Ziel liefern.
- In heterophilen Graphen weisen benachbarte Knoten unterschiedliche Semantik auf. Der Informationsgewinn $\Delta_{(+)}^{(i+1)}$ kann groß und positiv sein, was bedeutet, dass tiefere latente Einbettungen einzigartige und distinkte Informationen über die Datenverteilung enthalten, die flachere Einbettungen verpassen.

2. Gemeinsame Latente Dichteschätzung (JLDE)

Basierend auf der Erkenntnis, dass heterophile Graphen die gemeinsame Betrachtung aller Knotenrepräsentationen erfordern, um die vollständige Datenverteilung zu erfassen, schlagen die Autoren die Gemeinsame Latente Dichteschätzung (Joint Latent Density Estimation, JLDE) vor.

Mechanismus: Anstatt die Dichte aus einer einzelnen finalen Schicht zu schätzen (wie es in i.i.d.-Settings üblich ist) oder Graphen-Diffusion zu verwenden, verkettet JLDE die latenten Einbettungen aus allen Schichten des MPNN ( $Z^{(0)}, Z^{(1)}, \dots, Z^{(L)}$ ).
Implementierung: Ein einfacher post-hoc K-Nächste-Nachbarn (KNN)-Dichteschätzer wird auf diesen verketteten gemeinsamen Einbettungsraum angewendet. Die epistemische Unsicherheit $u_{epi}(v)$ wird als negative Log-Likelihood der gemeinsamen Repräsentation des Knotens innerhalb der Trainingsverteilung berechnet.
Designprinzip: Dieser Ansatz nutzt Homophilie nicht explizit durch Nachbearbeitung (z. B. Glättung) aus und ist auf jeden MPNN-Backbone anwendbar.

Hauptbeiträge

Theoretischer Rahmen: Die Arbeit leitet ein neuartiges Analogon zur Datenverarbeitungsungleichung für MPNNs her und beweist, dass Informationen in heterophilen Settings mit der Modelltiefe zunehmen können, aufgrund der einzigartigen semantischen Informationen, die Nachbarn in unterschiedlichen Distanzen bereitstellen.
Informationsbasierte Homophilie-Definition: Die Autoren führen eine Definition von Homophilie ein, die auf gegenseitiger Information basiert und zwischen geteilter Information, die für das Ziel-Label relevant ist, und irrelevantem Rauschen unterscheidet.
JLDE-Methode: Sie schlagen die Gemeinsame Latente Dichteschätzung vor, ein einfaches post-hoc-Designprinzip, das alle latenten Repräsentationen gemeinsam modelliert. Diese Methode ist die erste, die explizit die Unsicherheitsquantifizierung in heterophilen Graphen ohne reliance auf Homophilie-Annahmen anvisiert.
Empirische Validierung: Die Methode wird über mehrere Datensätze, Verteilungsverschiebungen und Backbone-Architekturen hinweg evaluiert und zeigt State-of-the-Art-Leistung.

Experimentelle Ergebnisse

Die Autoren evaluieren JLDE auf sechs Datensätzen (vier heterophil: Amazon Ratings, Roman Empire, Chameleon, Squirrel; zwei homophil: CoraML, PubMed) unter drei Arten von Verteilungsverschiebungen: Leave-Out-Class (LoC), Nahe Merkmalsstörungen und Ferne Merkmalsstörungen.

Leistung bei Heterophilie: Auf heterophilen Datensätzen erzielt JLDE konsistent State-of-the-Art-epistemische Unsicherheit (gemessen durch O.O.D.-Erkennung AUC-ROC und AUC-PR). Sie übertrifft Methoden, die auf Graphen-Diffusion (z. B. GPN, GEBM) oder Standard-Ensemble-Methoden basieren, signifikant, insbesondere in Szenarien, in denen Informationen aus tieferen Schichten kritisch sind.
Leistung bei Homophilie: Auf homophilen Datensätzen schneidet JLDE wettbewerbsfähig mit anderen modellagnostischen Schätzern ab und erreicht die Leistung von Methoden, die explizit für Homophilie entwickelt wurden, obwohl sie keine Homophilie-ausnutzende Nachbearbeitung verwendet.
Ablationsstudien: Experimente bestätigen, dass für heterophile Graphen die Verwendung nur der finalen Schicht oder das Mitteln schichtweiser Dichten im Vergleich zur gemeinsamen Verkettung aller Schichten zu unterlegenen Ergebnissen führt. Umgekehrt performt der gemeinsame Ansatz auf homophilen Graphen genauso gut wie die Verwendung nur der finalen Schicht, was die Theorie validiert, dass tiefere Schichten in diesen Settings keine neuen Informationen hinzufügen.
Backbone-Agnostizismus: Die Methode wird post-hoc auf verschiedene Backbones angewendet (Res-GCN, Res-GAT-Sep, Res-GATE, GPRGNN) und rangiert konsistent als bester oder zweitbester Schätzer über verschiedene Architekturen hinweg.

Bedeutung und Behauptungen

Die Arbeit beansprucht, das theoretische Fundament für die Weiterentwicklung der Unsicherheitsschätzung auf Graphen jenseits der Homophilie-Annahme zu liefern. Indem sie aufdeckt, dass in heterophilen Graphen jede Einbettungsschicht einzigartige Informationen über die Datenverteilung liefert, etablieren die Autoren ein Schlüssel-Designprinzip: Unsicherheitsschätzung muss alle Knotenrepräsentationen gemeinsam betrachten.

Die Autoren betonen, dass ihre Arbeit:

eine Lücke in der Literatur adressiert, in der keine vorherige Arbeit explizit heterophile Graphen für die Unsicherheitsquantifizierung anvisiert hat.
demonstriert, dass bestehende Schätzer oft versagen, wenn Homophilie-Annahmen verletzt werden.
eine einfache, effektive und modellagnostische Lösung (JLDE) bietet, die State-of-the-Art-Ergebnisse erzielt, ohne komplexe architektonische Änderungen oder explizite Homophilie-Ausnutzung zu erfordern.
zur Entwicklung zuverlässiger und vertrauenswürdiger KI beiträgt, insbesondere in Hochrisikobereichen, in denen das Verständnis der Modellunsicherheit in nicht-homophilen Daten kritisch ist.

Die Autoren bleiben hinsichtlich des Umfangs bescheiden und stellen fest, dass JLDE zwar die epistemische Unsicherheit verbessert, aber die aleatorische Unsicherheit oder die Modellkalibrierung nicht inhärent verbessert, was weiterhin orthogonale Wege für zukünftige Arbeiten darstellt. Sie vermuten zudem, dass ausgefeiltere Dichtemodelle ihre einfache KNN-basierte Realisierung weiter verbessern könnten.