🤖 machine learning

TN-SHAP-G: Graph-Structured Tensor Network Surrogates for Shapley Values and Interactions

Das Papier stellt TN-SHAP-G vor, ein Framework, das graphen-ausgerichtete Tensornetzwerk-Surrogate nutzt, um exakte Shapley-Werte und höherwertige Interaktionen für graphenstrukturierte Eingaben effizient zu berechnen und dabei die exponentielle Komplexität sowie die Stichprobenvarianz herkömmlicher Methoden zu überwinden.

Ursprüngliche Autoren: Farzaneh Heidari, Guillaume Rabusseau

Veröffentlicht 2026-06-02

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Farzaneh Heidari, Guillaume Rabusseau

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

Stellen Sie sich vor, Sie besitzen eine komplexe Black-Box-Maschine, die ein Bild eines Moleküls (einen Graphen aus Atomen und Bindungen) entgegennimmt und vorhersagt, ob es gefährlich oder sicher ist. Sie möchten wissen: Welche spezifischen Atome sind für diese Vorhersage verantwortlich? Und noch wichtiger: Arbeiten bestimmte Gruppen von Atomen zusammen, um dieses Ergebnis zu erzeugen?

Hier kommen Shapley-Werte ins Spiel. Betrachten Sie sie als eine faire Methode, um den „Anteil“ an der Vorhersage unter allen Spielern (Atomen) aufzuteilen. Die Berechnung dieses Anteils ist jedoch ein Albtraum. Um genau zu wissen, wie viel ein Atom beiträgt, muss man jede mögliche Kombination von Atomen testen (einige behalten, andere ausblenden), um zu sehen, wie sich die Vorhersage verändert. Wenn Sie 20 Atome haben, gibt es über eine Million Kombinationen. Wenn Sie 50 haben, ist die Zahl so gewaltig, dass es länger als das Alter des Universums dauern würde, sie alle zu überprüfen.

Aktuelle Methoden versuchen, die Antwort durch das Stichprobenverfahren zufälliger Kombinationen zu erraten, was jedoch langsam, verrauscht ist und oft die subtile Teamarbeit zwischen den Atomen übersieht.

TN-SHAP-G ist eine neue Methode, die dies löst, indem sie wie ein intelligenter Übersetzer und eine Abkürzung fungiert. So funktioniert es, erklärt anhand einfacher Analogien:

1. Das „Schattenspiel“ (Der Surrogate)

Anstatt die Black-Box-Maschine zu bitten, Millionen von Tests durchzuführen, bittet TN-SHAP-G sie, nur ein paar hundert Tests durchzuführen (wie das Probieren einer Suppe mit verschiedenen Zutaten, um das Rezept zu erraten).

Es erstellt dann eine vereinfachte „Schattenspiel“-Version der Maschine. Dies ist keine zufällige Vermutung, sondern eine mathematische Struktur, die ein Tensor-Netzwerk genannt wird.

Die Analogie: Stellen Sie sich das Molekül wie eine Stadtkarte vor. Die Black-Box-Maschine ist ein komplexes Verkehrssystem. TN-SHAP-G erstellt ein vereinfachtes Modell dieser Stadt, in dem die Straßen (Verbindungen zwischen den Atomen) erhalten bleiben, aber die Verkehrsregeln in eine kompakte, leicht berechenbare Karte vereinfacht werden.
Der Schlüssel: Diese vereinfachte Karte ist so gebaut, dass sie exakt der Form des Moleküls entspricht. Wenn das Molekül eine Ringform hat, hat auch das mathematische Modell eine Ringform. Dies ermöglicht es, wie Atome ihre Nachbarn beeinflussen zu erfassen, ohne das gesamte Universum simulieren zu müssen.

2. Die „Magische Formel“ (Deterministische Rekonstruktion)

Sobald dieser vereinfachte „Schattenspiel“-Modell trainiert ist, geschieht die Magie. Da das Modell mit einer speziellen Art von Mathematik (multilinearen Polynomen) aufgebaut ist, haben die Autoren eine geschlossene Formel gefunden, um den exakten Anteil für jedes Atom zu berechnen.

Die Analogy: Normalerweise würde man, um die Durchschnittsgeschwindigkeit eines Autos zu finden, es vielleicht 1.000 Mal stoppen und den Durchschnitt bilden (Sampling). TN-SHAP-G ist wie das Besitzen eines perfekten Bauplans des Automotors. Man muss das Auto nicht 1.000 Mal fahren; man steckt den Bauplan einfach in einen Taschenrechner, und er sagt einem sofort die exakte Geschwindigkeit.
Das Ergebnis: Sob einer das Modell trainiert ist, kann es die Wichtigkeit jedes einzelnen Atoms und jedes Paares von Atomen sofort und perfekt ausspucken – ohne jegliches Raten oder Zufall.

3. Warum es besser ist (Der „Teamwork“-Vorteil)

Die meisten Methoden haben Schwierigkeiten zu verstehen, wie zwei Atome zusammenarbeiten (Interaktionen). Sie sind wie der Versuch, einen geheimen Handschlag zu erraten, indem man Menschen beim zufälligen Händeschütteln beobachtet.

TN-SHAP-G ist wie das Beobachten des Handschlags in Zeitlupe auf einem Bauplan. Es kann exakt berechnen, wie viel „Synergie“ zwischen zwei Atomen existiert (z. B. „Stickstoff und Sauerstoff zusammen sind 10-mal gefährlicher als jeder für sich allein“), ohne zusätzliche Tests zu benötigen.
Effizienz: Während andere Methoden vielleicht 5.000 oder 50.000 Abfragen an die Black-Box-Maschine benötigen, um ein ordentliches Ergebnis zu erhalten, liefert TN-SHAP-G oft eine nahezu perfekte Antwort mit nur 50 bis 100 Abfragen.

4. Was getestet wurde

Die Autoren haben dies an Molekülen (wie Medikamenten und Proteinen) getestet.

Kleine Moleküle: Sie verglichen es mit dem „Goldstandard“ (das Überprüfen jeder einzelnen Kombination). TN-SHAP-G entsprach dem Goldstandard fast perfekt (über 99 % Genauigkeit), tat dies jedoch tausendfach schneller.
Große Moleküle: Sie testeten es auf riesige Proteinstrukturen, bei denen andere Methoden einfach abstürzen oder zu lange brauchen würden. TN-SHAP-G bewältigte diese reibungslos und skalierte hoch auf Graphen mit Hunderten von Knoten.

Zusammenfassung

TN-SHAP-G ist ein Werkzeug, das eine kompakte, formbewusste „Spickzettel“-Version davon lernt, wie ein Black-Box-Modell Entscheidungen trifft. Sobald es diesen Spickzettel besitzt, kann es sofort und perfekt berechnen, welche Teile eines Graphen (wie eines Moleküls) wichtig sind und wie sie zusammenarbeiten, ohne die Black-Box-Maschine nach Millionen von Antworten fragen zu müssen. Es verwandelt ein Problem, das normalerweise einen Supercomputer und ein Leben voller Warten erfordert, in etwas, das in Sekundenschnelle auf einem Standardcomputer lösbar ist.

Technisches Resümee: TN-SHAP-G

Problemstellung

Die Erklärung von Vorhersagen durch Black-Box-Graph-neuronale Netze (GNNs) erfordert die Zuweisung von Wichtigkeit zu einzelnen Knoten und deren Interaktionen. Während Shapley-Werte und Interaktionsindizes höherer Ordnung prinzipielle, axiomatische Attribuierungen bieten, ist deren exakte Berechnung für Graphen unpraktikabel, da sie mit $O(2^n)$ skaliert, wobei $n$ die Anzahl der Knoten ist. Bestehende Approximationsmethoden stehen vor erheblichen Zielkonflikten: architekturspezifische Erklärer (z. B. GNNExplainer) lassen sich nicht auf allgemeine Black-Box-Modelle anwenden, während sampling-basierte Ansätze (z. B. GraphSVX, SHAP-IQ) tausende Modell-Evaluierungen erfordern und eine hohe Varianz aufweisen, insbesondere bei Interaktionen höherer Ordnung. Darüber hinaus scheitern diese Sampling-Methoden oft bei der Skalierung auf größere Graphen, bei denen eine exakte Enumeration unmöglich ist.

Methodik: TN-SHAP-G

Die Autoren schlagen TN-SHAP-G vor, ein Framework, das die strukturellen Eigenschaften von graphenstrukturierten Eingaben ausnutzt, um Shapley-Werte und Interaktionen effizient und deterministisch zu berechnen. Die Kernidee besteht darin, einen kompakten, graphen-ausgerichteten Tensor-Netzwerk-Surrogaten (TN) zu lernen, der das Verhalten des maskierten Inputs des Prädiktors approximiert.

1. Das maskierte Graph-Spiel

Die Methode formalisiert die Graph-Erklärung als ein kooperatives Spiel, das durch Knoten-Maskierung induziert wird. Für einen fixen Eingabegraphen $G=(V, E)$ mit Merkmalen $X$ und einer Baseline $X^0$ definiert eine Koalition $S \subseteq V$ eine maskierte Merkmalsmatrix $X_S$ , bei der Knoten in $S$ ihre ursprünglichen Merkmale behalten und Knoten außerhalb von $S$ durch Baseline-Merkmale ersetzt werden. Der Spielwert ist $\nu(S) = f(G, X_S)$ , wobei $f$ der Black-Box-Prädiktor ist.

2. Multilineare Erweiterung und Tensor-Kontraktion

Die direkte Berechnung von Shapley-Werten erfordert die Summation über $2^n$ Koalitionen. Die Autoren nutzen die multilineare Erweiterung $\hat{\nu}(z)$ , eine kontinuierliche Relaxation des diskreten Spiels, definiert auf $z \in [0, 1]^n$ .

Tensor-Formulierung: Die multilineare Erweiterung kann exakt als Tensor-Kontraktion ausgedrückt werden: $\hat{\nu}(z) = \sum_{s \in \{0,1\}^n} T_s \prod_{v=1}^n b_v(z_v)^{s_v}$ , wobei $T$ der Koalitions-Tensor und $b_v(z_v)$ Bernoulli-Selektor-Vektoren sind.
Deterministische Rekonstruktion: Shapley-Werte und Interaktionsindizes entsprechen den Integralen der partiellen Ableitungen von $\hat{\nu}$ entlang der Diagonale $z = t\mathbf{1}$ . Da $\hat{\nu}$ multilinear ist, sind diese Ableitungen univariante Polynome vom Grad höchstens $n-1$ . Somit können exakte Attribuierungen über Vandermonde-Interpolation aus einer geringen Anzahl von Probenpunkten rekonstruiert werden, was die Monte-Carlo-Varianz eliminiert.

3. Graphen-ausgerichteter Tensor-Netzwerk-Surrogat

Da der vollständige Koalitions-Tensor $T$ $2^n$ Einträge besitzt, lernt TN-SHAP-G einen graphen-ausgerichteten Tensor-Netzwerk-Surrogaten $\hat{\nu}$ , um die multilineare Erweiterung zu approximieren.

Topologie: Die TN-Topologie spiegelt den Eingabegraphen $G$ wider. Jeder Knoten $v$ entspricht einem Kerntensor $A^{(v)}$ mit einem physischen Index (der die Koalitionsmitgliedschaft kodiert) und Bond-Indizes, die mit Nachbarn verbunden sind.
Expressivität: Die Bond-Dimension $\chi$ steuert die Kapazität des Informationsflusses über Graph-Separatoren hinweg. Die Autoren belegen, dass dieser graphen-ausgerichtete Aufbau für Spiele mit geringem Cut-Rank über Graph-Separatoren (eine Eigenschaft vieler lokaler Abhängigkeitsmuster in GNNs) eine höhere Expressivität mit weniger Parametern erreicht als kettenbasierte Faktorisierungen wie Tensor-Trains (TT), die bei zyklischen oder komplexen Graphen unter Rank-Inflation leiden.
Training: Der Surrogat wird mittels empirischer Risikominimierung auf einer kleinen Menge gesampelter Koalitionen ( $M \ll 2^n$ ) trainiert. Theoretische Garantien zeigen, dass das erforderliche Query-Budget für Graphen mit beschränktem Grad nahezu linear mit der Anzahl der Knoten skaliert.

4. Inferenz

Einmal trainiert, ermöglicht der Surrogat die deterministische Berechnung von:

Erster Ordnung Shapley-Werten: Über die 1D-Integration der Diagonal-Ableitung.
Höherer Ordnung Interaktionen: Über gemischte partielle Ableitungen und Integration.
Alle Größen werden aus dem einzelnen trainierten Surrogaten berechnet, ohne zusätzliche Abfragen an das Black-Box-Modell.

Zentrale Beiträge

Prinzipielle graphen-ausgerichtete Repräsentation: Einführung eines Tensor-Netzwerk-Surrogaten, der die exponentielle Koalitions-Wert-Tabelle in eine niedrigdimensionale, graphen-ausgerichtete multilineare Repräsentation komprimiert. Dies richtet den induktiven Bias des Surrogaten an den lokalen Abhängigkeitsmustern in Graph-Prädiktoren aus.
Amortisierte deterministische Berechnung: Nutzung der multilinearen Struktur zur Berechnung von Shapley-Werten und Interaktionen via geschlossener Vandermonde-Interpolation. Dies erfordert nur $O(n)$ Surrogat-Evaluierungen und führt zu keiner Monte-Carlo-Varianz. Ein einziger Surrogat amortisiert die Berechnung aller Indizes erster und höherer Ordnung.
Theoretische Garantien:
- Beweis, dass der gelernte Surrogat die multilineare Erweiterung eindeutig bestimmt, was eine exakte Rekonstruktion der Attribuierungen auf dem Surrogaten sicherstellt.
- Charakterisierung der Expressivität via Cut-Rank-Argumente, womit bewiesen wird, dass graphen-ausgerichtete TNs kettenbasierte Faktorisierungen (wie TT) für graphstrukturierte Spiele übertreffen.
- Nahezu lineare Teacher-Query-Komplexitäts-Bounds für Graphen mit beschränktem Grad.
- Stabilitätsgarantien, die den Approximationsfehler des Spiels mit dem Shapley-Fehler verknüpfen.
Empirische Leistung: Nachgewiesen durch hohe Genauigkeit auf molekularen Benchmarks, wobei eine Cosinus-Ähnlichkeit von $>0,99$ zu exakten Shapley-Werten mit nur 50 Modell-Evaluierungen erreicht wurde (10–100 $\times$ weniger als die Baselines).

Experimentelle Ergebnisse

Die Autoren evaluierten TN-SHAP-G auf molekularen Benchmarks (Mutagenicity, Benzene) und Protein-Graphen (PROTEINS).

Korrektheit: Auf kleinen Graphen ( $n \le 20$ ) stimmt TN-SHAP-G eng mit exakten Shapley-Werten (O1) und Interaktionsindizes (O2) überein und übertrifft GraphSVX und Permutations-Sampling sowohl in der Genauigkeit als auch in der Varianz signifikant.
Query-Effizienz: TN-SHAP-G erreicht eine hohe Attributionsgenauigkeit mit 10–100 $\times$ weniger Modell-Queries als Sampling-basierte Schätzer (SHAP-IQ, GraphSVX).
Skalierbarkeit: Die Methode skaliert effizient auf Graphen mit bis zu 600 Knoten unter Verwendung einer Coarsening-basierten Surrogat-Architektur, während exakte Enumeration und Sampling-basierte Methoden unpraktikabel werden.
Struktur-Ablation: Graphen-ausgerichtete TNs übertreffen konsistent TT-Surrogate unter parameter-identischen Bedingungen, was den theoretischen Vorteil topologie-ausgerichteter Faktorisierungen bestätigt.
Fidelity-Proxy: Es wurde eine starke Korrelation zwischen dem Test- $R^2$ des Surrogaten und der Cosinus-Ähnlichkeit der rekonstruierten Shapley-Werte beobachtet, was die Validität von $R^2$ als praktischen Proxy für die Attributionsgenauigkeit bestätigt.

Bedeutung und Ansprüche

Das Paper behauptet, dass TN-SHAP-G den Stand der Technik in der Graph-Erklärbarkeit vorantreibt, indem es einen prinzipiellen, modellagnostischen Rahmen bietet, der die exponentielle Komplexität der Shapley-Berechnung überwindet. Durch die Ausnutzung der Low-Rank-Struktur, die in graphstrukturierten kooperativen Spielen inhärent ist, ermöglicht die Methode eine deterministische, varianzfreie Attribuierung mit nahezu linearer Query-Komplexität.

Die Autoren betonen, dass dieser Ansatz den Zugang zu rigorosen Erklärungsmethoden für Praktiker mit begrenzten Rechenressourcen demokratisiert, insbesondere in hochsensiblen Bereichen wie der Wirkstoffforschung und der Vorhersage molekularer Eigenschaften. Das Framework ist flexibel, unterstützt verschiedene Spiel-Semantiken (z. B. Knoten-Maskierung, Knoten-Entfernung, Myerson-Werte) und verschiedene Feature-Typen, und lässt sich über Standard-Message-Passing-GNNs hinaus auf andere Graph-Prädiktoren erweitern. Die Arbeit positioniert Tensor-Netzwerke nicht nur als Kompressionstools, sondern als fundamentalen Mechanismus für die handhabbare spieltheoretische Analyse auf strukturierten Daten.