Explainable Graph Neural Networks via Structural Externalities
This addresses the explainability challenge for GNN users in graph-related tasks, offering a novel method for capturing node interactions, though it is incremental in improving existing Shapley-based approaches.
The paper tackles the problem of explaining Graph Neural Networks (GNNs) by proposing GraphEXT, a framework that uses cooperative game theory and social externalities to quantify node importance based on structural interactions, and it shows improved fidelity over baselines on synthetic and real-world datasets.
Graph Neural Networks (GNNs) have achieved outstanding performance across a wide range of graph-related tasks. However, their "black-box" nature poses significant challenges to their explainability, and existing methods often fail to effectively capture the intricate interaction patterns among nodes within the network. In this work, we propose a novel explainability framework, GraphEXT, which leverages cooperative game theory and the concept of social externalities. GraphEXT partitions graph nodes into coalitions, decomposing the original graph into independent subgraphs. By integrating graph structure as an externality and incorporating the Shapley value under externalities, GraphEXT quantifies node importance through their marginal contributions to GNN predictions as the nodes transition between coalitions. Unlike traditional Shapley value-based methods that primarily focus on node attributes, our GraphEXT places greater emphasis on the interactions among nodes and the impact of structural changes on GNN predictions. Experimental studies on both synthetic and real-world datasets show that GraphEXT outperforms existing baseline methods in terms of fidelity across diverse GNN architectures , significantly enhancing the explainability of GNN models.