PARSE: Partition-Based Shapley Explanation of Graph Neural Networks with Pairwise Interactions

Graph Neural Networks (GNNs) achieve strong predictive performance but remain difficult to interpret. Most explainers score single nodes or edges, which shows where a model looks but not how substructures act together. We propose PARSE (PARtition-based Shapley Explanation), which explains a GNN by partitioning the graph into connected substructures of interacting nodes and measuring the pairwise interactions (synergy or redundancy) between them. PARSE is grounded in cooperative game theory: from one set of random node orderings, it estimates, separately, each node's own contribution (its Shapley value) and the Shapley interaction index of every pair, which guide the partition and a search for the node sets of highest fidelity. On controlled tasks whose known interaction is synergy, redundancy, or exclusivity, PARSE's pairwise estimates between the two planted substructures have the sign of the planted interaction on every test graph that contains both, and its group ranking ranks first a pair of groups that holds both substructures on 37 to 41 of the 46 such graphs per task. On the test graphs of thirteen public datasets, against eleven explainers, PARSE is the most faithful method in 58 of 65 (dataset, metric) comparisons.