SAME: GNN-Black-Box-Entschlüsselung mit strukturaware Shapley-basierten Multipiece-Erklärungen

Post-hoc-Erklärungstechniken für Graph Neural Networks (GNNs) bieten wirtschaftliche Lösungen, um die Black-Box-Graphmodelle ohne Neutrainings zu entschlüsseln. Obwohl zahlreiche Varianten von GNN-Erklärungen auf einer Vielzahl von Benchmarks state-of-the-art-Erklärungsergebnisse erzielt haben, fehlt ihnen häufig eine theoretische Analyse ihrer inhärenten Eigenschaften und ihres Erklärungspotenzials. In dieser Arbeit stellen wir die Methode $underline{ ext{S}}$tructure-$underline{ ext{A}}$ware Shapley-basierte $underline{ ext{M}}$ultipiece $underline{ ext{E}}$xplanation (SAME) vor, um die Herausforderungen strukturawareer Merkmalsinteraktionen bei der Erklärung von GNNs anzugehen. Konkret nutzt SAME einen auf Erweiterungen basierenden Monte-Carlo-Baum-Suchalgorithmus, um mehrschalige, strukturaware verbundene Teilgraphen zu erkunden. Anschließend werden die Erklärungsergebnisse durch die Optimierung der Kombination verschiedener einzelner Teilgraphen so gestaltet, dass sie informativ hinsichtlich der graphischen Eigenschaften sind. Unter Berücksichtigung einer fairen Berücksichtigung von Merkmalsinteraktionen bei der Untersuchung mehrerer verbundener wichtiger Teilgraphen besitzt die von SAME gelieferte Erklärung das Potenzial, in polynomialer Zeit ebenso erklärend wie die theoretisch optimale Erklärung basierend auf dem Shapley-Wert zu sein. Umfangreiche Experimente auf realen und synthetischen Benchmarks zeigen, dass SAME die bisher beste Fidelitätsleistung unter denselben Testbedingungen um 12,9 % bei BBBP, 7,01 % bei MUTAG, 42,3 % bei Graph-SST2, 38,9 % bei Graph-SST5, 11,3 % bei BA-2Motifs und 18,2 % bei BA-Shapes verbessert. Der Quellcode ist unter https://github.com/same2023neurips/same verfügbar. Einreichungsnummer: 12143