TACENR: Task-Agnostic Contrastive Explanations for Node Representations

1. Problemstellung

Das Paper adressiert das Problem der mangelnden Interpretierbarkeit von Node-Representation-Learning (Lernen von Knotenrepräsentationen) in Graphen. Während Methoden wie Graph Neural Networks (GNNs) oder Random-Walk-basierte Ansätze (z. B. Node2Vec) erfolgreich latente Vektorräume für Knoten erzeugen, bleiben diese Darstellungen oft eine „Black Box".

Die bestehenden Erklärbarkeitsmethoden (Explainable AI, XAI) für Graphen weisen folgende Einschränkungen auf:

• Task-Spezifität: Die meisten Methoden erklären nur Vorhersagen für spezifische Downstream-Aufgaben (z. B. Klassifizierung), nicht aber die Repräsentation selbst.
• Dimensionale Zerlegung: Viele Ansätze erklären nur einzelne Dimensionen des Repräsentationsvektors, anstatt die gesamte Repräsentation als Ganzes zu betrachten.
• Unvollständigkeit: Bestehende Methoden fokussieren sich oft nur auf einen Aspekt (z. B. nur Nachbarschaftsstruktur oder nur Attribute), ignorieren aber die komplexe Interaktion aus Proximität (Nähe im Graph), Struktur (topologische Rolle) und Attributen (Knotenmerkmale).

2. Methodik: TACENR

Die Autoren schlagen TACENR (Task-Agnostic Contrastive Explanations for Node Representations) vor, eine lokale Erklärungsmethode, die die gesamte Knotenrepräsentation unabhängig von einer spezifischen Aufgabe erklärt.

Kernkomponenten:

• Ziel: Identifikation der Merkmale (Proximität, Struktur, Attribute), die den größten Beitrag zur Position eines Knotens im Repräsentationsraum leisten.
• Kontrastives Lernen: TACENR lernt eine Ähnlichkeitsfunktion im Repräsentationsraum. Für einen zu erklärenden Knoten $v$ werden zwei Mengen gebildet:
  • Affinitätsmenge ($S^+_v$): Die $k_{aff}$ Knoten mit der ähnlichsten Repräsentation.
  • Divergenzmenge ($S^-_v$): Die $k_{div}$ Knoten mit der unähnlichsten Repräsentation.
• Merkmalsvektor: Jeder Knoten wird durch einen kombinierten Vektor $h_{v,u}$ beschrieben, der folgende Komponenten enthält:
  • Attribute: Eingabe-Features des Knotens.
  • Proximitäts-Features: Metriken wie kürzeste Pfade oder Personalized PageRank (PPR).
  • Strukturelle Features: Topologische Rollen wie Grad, durchschnittlicher Nachbargrad, Clustering-Koeffizient und Anzahl der Dreiecke.
• Interpretierbares Modell: Ein einfacher Regressionsmodel (standardmäßig lineare Regression) wird trainiert, um die Ähnlichkeit $sim(z_v, z_u)$ zwischen den Repräsentationen basierend auf den Merkmalsunterschieden in $h_{v,u}$ vorherzusagen. Die Gewichte dieses Modells geben Aufschluss über die Wichtigkeit der einzelnen Merkmale.

Gewichtung der Ähnlichkeit (Similarity Measure):
Um die Erklärung zu verbessern, wird eine gewichtete Kosinus-Ähnlichkeit verwendet:

• Überwachte Szenarien: Gewichte werden basierend auf dem Gradienten der Vorhersagewahrscheinlichkeit berechnet (Dimensions, die stark zur Klassifizierung beitragen, erhalten höhere Gewichte).
• Unüberwachte Szenarien: Gewichte basieren auf der globalen Varianz jeder Dimension im Repräsentationsraum (Dimensionen mit hoher Varianz werden als informativer gewertet).

3. Hauptbeiträge

• Task-Agnostischer Ansatz: TACENR erklärt die Repräsentation an sich, nicht nur eine spezifische Vorhersage. Dies ermöglicht Einblicke in die zugrunde liegende Struktur des Modells unabhängig von der Anwendung.
• Ganzheitliche Erklärung: Als erste Methode, die Proximität, Struktur und Attribute gemeinsam betrachtet, um die gesamte Repräsentation zu erklären.
• Kontrastiver Rahmen: Die Nutzung von Affinitäts- und Divergenzmengen erlaubt es, zu lernen, welche Merkmale Knoten im Vektorraum zusammenbringen oder trennen.
• Anpassbare Gewichtung: Die Einführung von gewichteten Ähnlichkeitsmetriken, die sich an den Lernkontext (überwacht vs. unüberwacht) anpassen.

4. Ergebnisse

Die Autoren evaluieren TACENR auf mehreren Datensätzen (Cora, CiteSeer, PubMed, PPI, synthetisches BA-Shapes) und mit verschiedenen Modellen (Node2Vec, Role2Vec, GCN, GAT, GraphSAGE).

• Erkenntnisgewinn:
  • Struktur vs. Attribute: Die relative Wichtigkeit der Merkmale variiert stark je nach Modellarchitektur und Datensatz.
  • Node2Vec: Wird stark von Proximitäts-Features (z. B. PPR) dominiert, da es auf Random Walks basiert.
  • GNNs: Werden stark von lokalen strukturellen Features (Durchschnittsgrad der Nachbarn, Clustering-Koeffizient) beeinflusst, was der Aggregationsmechanik von GNNs entspricht.
  • Synthetische Daten (BA-Shapes): TACENR erkennt korrekt, dass Knoten in „House-Motiven" durch lokale Struktur (Dreiecke, Grad) definiert sind, während Basis-Knoten durch globale PPR-Werte (Rolle als Hub) definiert werden.
• Vergleich mit Task-Spezifischen Methoden:
  • Im überwachten Setting wurde TACENR mit Methoden wie GNNExplainer, GraphLIME und GraphSVX verglichen.
  • AOPC-Metrik (Area Over the Perturbation Curve): TACENR zeigt in den meisten Fällen eine höhere AOPC, was bedeutet, dass das Entfernen der identifizierten Merkmale die Vorhersagegenauigkeit stärker beeinträchtigt als bei anderen Methoden.
  • Rausch-Filterung: TACENR fügt weniger irrelevante (rauschende) Features in die Top-K-Erklärungen ein als die Vergleichsmethoden.
• Ablationsstudie:
  • Gewichtung: Die gewichtete Ähnlichkeit verbessert die Erklärungsqualität signifikant, insbesondere bei überwachten Modellen (Gradient-basiert) und unüberwachten Modellen (Varianz-basiert).
  • Zusammensetzung der Mengen: Für überwachte Repräsentationen funktioniert ein hoher Anteil ähnlicher Knoten (Affinität) am besten. Für unüberwachte Repräsentationen ist ein höherer Anteil unähnlicher Knoten (Divergenz) notwendig, um Kontrast zu schaffen.
  • Modellwahl: Einfache lineare Regression erwies sich als robust und oft besser oder gleichwertig zu komplexeren Modellen (Ridge, Lasso, HSIC-Lasso), bei gleichzeitig maximaler Interpretierbarkeit.

5. Bedeutung und Fazit

TACENR schließt eine kritische Lücke im Bereich der Explainable AI für Graphen, indem es die Interpretierbarkeit von Knotenrepräsentationen selbst in den Mittelpunkt stellt, anstatt nur deren Anwendung auf Downstream-Aufgaben zu erklären.

• Verständnis von Algorithmen: Die Methode hilft Forschern und Praktikern zu verstehen, welche Aspekte eines Graphen (lokale Struktur, globale Rolle, Attribute) von einem bestimmten Lernalgorithmus priorisiert werden.
• Robustheit: Da die Methode task-agnostisch ist, kann sie auf beliebige Repräsentationsmodelle angewendet werden, ohne dass diese neu trainiert oder modifiziert werden müssen.
• Praxisrelevanz: Die Fähigkeit, sowohl überwachtes als auch unüberwachtes Lernen zu erklären, macht TACENR zu einem universellen Werkzeug für die Analyse von Graph-Embeddings in Bereichen wie Empfehlungssystemen, Bioinformatik und sozialen Netzwerkanalysen.

Zusammenfassend demonstriert das Paper, dass Proximität, Struktur und Attribute gemeinsam die Knotenrepräsentationen formen, wobei die Gewichtung dieser Faktoren stark von der Architektur des zugrunde liegenden Modells abhängt. TACENR bietet einen effektiven Weg, diese Zusammenhänge quantitativ und interpretierbar zu machen.