This paper addresses the problem of explaining the prediction results of graph neural networks (GNNs). It points out that attributing the predictions of GNNs to specific edges or features is computationally very expensive, and especially emphasizes the difficulty of identifying important edges among millions of candidate edges during the classification process of nodes with many neighbors. To address this problem, this paper proposes DistShap, a parallel algorithm that distributes Shapley value-based explanations across multiple GPUs. DistShap samples subgraphs in a distributed environment, runs GNN inference in parallel on GPUs, and computes edge importance scores by solving a distributed least-squares problem. Experimental results show that DistShap outperforms most existing GNN explanation methods and scales to GNN models with millions of features using up to 128 GPUs on the NERSC Perlmutter supercomputer.
