acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
interpretability and explainable AI
Keywords:
Graph Neural Networks, Explainability, Cooperative game theory, Interpretability

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_vp5wOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes PARSE to explain GNN based on Shapley values and pairwise Shapley interactions. After calculating those values, the method creates partition graphs and searches for high-fidelity node sets as explanations. Experiments on controlled tasks and real-world datasets show that PARSE achieves stronger explanation fidelity than baselines.

Critical strengths
  1. PARSE provides interaction-aware explanations for GNNs and can capture pairwise interactions between nodes even when they are far away in the graph. The method is model-agnostic, requiring only model queries, which makes it broadly applicable to different GNN architectures.

  2. The experiments on real-world datasets are extensive. PARSE demonstrates consistently strong performance across multiple fidelity metrics.

Critical weaknesses
  1. The method relies on several approximations with fixed computational budgets (e.g. 50 permutations for estimating Shapley values and pairwise interactions, steps for partitioning, and local search for large explanation spaces). However, the paper provides limited analysis of their trade-offs between approximation and computation. Particularly, sampling too few node orderings in phase 1 will probably yield unreliable estimated interaction, given the huge combinatory amount of such interactions. A sensitivity analysis varying budgets against interaction recovery, fidelity, and runtime or model query times would substantially strengthen the evaluation.

  2. While the method shows consistently strong fidelity results, it is unclear how much of the improvement comes from the proposed interaction-aware partitioning versus the fidelity-driven search in phase 4. PARSE directly searches for node sets with high H-Fidelity and additionally calibrates its partition hyperparameters on validation data using an objective involving a large overlap with the reported evaluation metrics. In contrast, the baselines mostly use their default configurations, and their outputs are converted to fixed-budget node sets without an analogous fidelity-based refinement. Although the strong performance on Fid alpha that is not used for calibration or search partially alleviates this concern, an important test would be to apply the same phase 4 fidelity refinement to strong baselines.

Questions for authors
  1. GNN-LRP (Schnake et al., 2022) is discussed in the related work (line 97) but is not included in the experimental comparison. Since GNN-LRP can capture higher-order interactions, it would be an important baseline for evaluating PARSE's interaction-aware explanations. Similarly, sGNN-LRP (Xiong et al., 2022), which extends this idea to subgraph explanations with higher-order interactions, would be an important baseline to consider, particularly given that modeling interactions is a central motivation of PARSE.

  2. Can the proposed framework capture interactions involving three or more nodes?

  3. In phase 4, the interaction-based partition is only one of four starting sets for the H-Fidelity search (line 270). Could the authors compare full PARSE against phase 4 without the interaction-based partition? This would help clarify whether the improvements on the benchmark are due to the proposed interaction-aware partitioning or primarily the H-Fidelity optimization.

Reviewer_vEKcOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes PARSE, a post-hoc GNN explainer that estimates node Shapley values and pairwise Shapley Interaction Indices (SII) using shared random permutations. It constructs connected groups through greedy merging and simulated annealing, then searches for high-H-Fidelity explanation sets. Additional rankings identify interacting groups and important nodes.

Experiments cover 13 datasets and 11 baselines, reporting 58 wins across 65 dataset–metric comparisons. Controlled AND, OR, and XOR tasks demonstrate strong interaction-sign recovery and motif localization.

Critical strengths
  1. Meaningful problem and explanation design. PARSE moves beyond node importance to capture interactions among connected substructures, including distant groups without requiring intermediate path nodes in the explanation.

  2. Broad and thoughtful evaluation. The paper includes diverse datasets, extensive baselines, statistical analyses, masking sensitivity checks, and computational cost measurements. The controlled tasks also align planted interaction rules with learned model behavior through masked training examples.

Critical weaknesses
  1. The final explanation directly maximizes H-Fidelity through exhaustive or multi-start local search, with the interaction-based partition providing only one of four initializations. It is unclear how much of the improvement comes from interaction modeling and partitioning rather than the final search. Ablations retaining the same search procedure, along with baselines receiving comparable fidelity-based post-processing, are essential to establish the claimed contributions.

  2. The controlled AND, OR, and XOR experiments demonstrate strong motif recovery but lack direct comparisons with relevant interaction explainers such as MAGE and GraphSHAP-IQ. Moreover, the additional group and node rankings use validation-set motif annotations for parameter selection. While this is not test leakage, the dependence of the results on such supervision remains unclear.

  3. With 50 random permutations, each node pair is observed only (100/n) times in expectation. This raises concerns about interaction-estimation variance and partition stability on larger graphs. Although Appendix E.3 reports fidelity by graph-size groups, the effects of sampling budget and random seeds on interaction quality remain insufficiently studied.

  4. Some baseline outputs require padding, truncation, or conversion to node rankings, potentially affecting their original structural explanations. The alternative-masker analysis also evaluates fixed explanations rather than regenerating them. These choices warrant clarification when interpreting the comparisons.

Questions for authors
  1. How much performance is retained when interaction information or partition-based initialization is removed while keeping the same Phase 4 search? Does the advantage persist when strong baselines receive comparable H-Fidelity search post-processing?

  2. What fraction of instances use exhaustive search? For the remaining instances, how often does partition-based initialization outperform the other three starts?

  3. How does PARSE compare with existing interaction explainers on the controlled tasks? How sensitive are the results to the use of ground-truth motif annotations during validation?

  4. How do permutation count and graph size affect interaction accuracy, partition stability, runtime, and memory? Additionally, how frequently do baseline budget adaptations alter their original explanations?

Reviewer_gUKWOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper presents PARSE, a Shapley-based post-hoc explanation method for Graph Neural Networks (GNNs). PARSE operates by partitioning a graph into connected subgraphs and measuring pairwise interactions between them to generate explanations. Across test graphs from 13 public datasets evaluated against 11 baseline explainers, the paper report that PARSE achieves the highest fidelity in 58 out of 65 (dataset, metric) evaluation pairs.

Critical strengths

S1. The paper develops a new algorithm to explain GNN predictions for graph classification tasks. GNN explainability is a well-studied problem. The proposed method outperforms most baselines considered in the paper.

S2. Utilizing pairwise Shapley values to capture higher-order interactions between subgraphs represents an interesting and promising research direction that has not been widely explored in the GNN explainability literature.

S3. The experimental design is comprehensive, benchmarking the proposed approach against 11 baseline methods across 13 datasets using 5 distinct evaluation metrics.

Critical weaknesses

W1. In general, the paper is difficult to follow. Sentences are unnecessarily connected by semicolons and colons (for example: “The explanation is the output of one search that maximizes H-Fidelity; the partition supplies one of its starting sets.” In Section 4.4). I found some common symptoms of LLM writing.

W2. The paper optimizes its parameters for H-Fidelity and then compares with other explanation methods based on H-Fidelity. This would lead to unfair comparisons. For example, other baseline methods (like GNNExplainer, GradxInput, or SubgraphX) do not optimize Fidelity directly during training/search. They instead optimize mutual information, gradients, or game-theoretic Shapley values, etc.

W3. The proposed method differs from instance-level optimization methods (like GNNExplainer or SubgraphX), which run on-the-fly for a single node or graph without training data. Hence, the usability of the proposed method on an unseen graph could be limited. Is there a way to report uncalibrated results? The authors mentioned that fidelity_alpha enters neither PARSE’s calibration objective nor its search. I am not sure how this works.

W4. GCN and GIN work by message passing on k-hop neighbors. Hence, it is not clear why disconnected pairs were considered at all.

W5. It is not clear why uniform sampling was used. For example, GraphSVX and GNNShap showed that non-uniform sampling usually works better for Shapley-based explanations.

Questions for authors

Q1. (W2) Why is it fair to optimize for fidelity and then use it as a comparison metric against other baselines?

Q2. (W3) Can we use the proposed method on a graph without calibration? For example, if we treat the GNN as a black box, we do not know how the model is trained. In this case, it is impossible to find calibration data.

Q3. (W4) Why not use connected pairs (edges) for pairwise Shapley calculations? Also, why should we consider nodes that are outside of the three-hop neighborhood for a three-layer GCN? Should not we sample from the computational graphs?

Q4. (W4) What is the benefit of uniform sampling as opposed to other sampling methods?

Q5. It is not clear what the differences are between Pre_r(i) and T_r(I,j). Do they represent the same set of nodes?

Q6. Is the M matrix sparse?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.