Multi-scale Explainer for Graph Neural Networks

Explainability for graph neural networks (GNNs) aims to unveil the complex decision logic of learned models by identifying the most influential structures in the input graph, thereby improving transparency and trustworthiness. Existing post-hoc explainers typically extract a sparse key subgraph at a single scale as the explanation. However, a single-scale view often fails to capture multi-level semantics, and the optimization procedure may degenerate into a local search that is sensitive to initialization and noise, leading to unstable explanations and compromising their reliability. To address these issues, we propose MSExplainer, a multi-scale explainer for GNNs. MSExplainer couples multi-scale subgraph consistency guidance with single-scale adaptive subgraph learning under a parameter-sharing design. It simultaneously extracts multi-scale key subgraphs and complementary subgraphs, yielding a hierarchical decomposition of the original graph that covers semantics at different granularities and improves the stability of subgraph extraction. Experiments on six benchmark datasets show that MSExplainer generally outperforms prior methods in explanation accuracy and fidelity. Moreover, we theoretically prove the upper bound advantage of the multi-scale strategy in representation consistency, and derive that it achieves the same-order computational complexity as single-scale methods under the parameter-sharing mechanism, thus ensuring the high fidelity of key subgraphs while maintaining computational efficiency.

Graph neural networks can make predictions on graph-structured data, such as molecules and networks, but it is often hard to understand which parts of a graph led to a prediction. This lack of clarity can make these models difficult to trust in important applications. We propose MSExplainer, a method that explains a model’s decision by identifying important graph structures at multiple levels of detail instead of using only one fixed view. By combining broader structural information with more detailed local information, MSExplainer produces explanations that are more accurate and stable. Experiments on several standard datasets show that this method can better reveal why a graph neural network makes a prediction while keeping the computational cost efficient.