- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper investigates the evaluation of post-hoc explainers for GNNs based on plausibility, i.e., how well an explanation recovers a predefined ground truth. The author argue that this protocol relies on the assumption that a trained GNN actually uses the intended patterns, and show that this assumption is violated on several popular benchmarks. To remove this confounder, they propose Gracr, a compiler that translates graded modal logic formulas into wrights of a sum-aggregation GNN. In this way, the behaviour of the model is known by construction. The authors also propose GracrBench, a benchmark of compiled GNNs to evaluate explainers on node- and graph- classification tasks.
Critical strengths
-
Important and well-motivated problem: the thorough literature review and the example in Figure 2 clearly show that plausibility is still widely used and can be misleading when the model does not rely on the intended pattern.
-
Original idea: using a compiler to remove the main confounder and make controlled experiments on the model (since the behaviour of the model is known by construction) is a clever and neat idea.
-
Informative findings: the experiments recover known results (e.e.g, GNNExplainer not sparsifying redundant edges) and reveal new ones (e.g., implementation invariance and indirect influences). I also like the fact the explainers are tuned on held-out data with a fixed-time budget.
-
Clarity: the paper is well written and easy to follow. The limitations are discussed openly.
Critical weaknesses
-
Transferability to trained GNNs: the compiled GNNs use many adjustments (e.g., binary embeddings, truncated ReLU activations, and so on) which make them very different from trained GNNs. Would your findings (i.e., only FlowX, GraphSVX, and IG reliable across tasks) hold also for trained GNNs? As mentioned in the conclusions, it would be interesting to see the results on compiled models after fine-tuning.
-
Ideal explanation definition: it is not clear what an 'ideal explanation' should be. For example, GNNExplainer is criticised for not sparsifying redundant edges although being in the well-performing explainers. Could you clarify which behaviour GracrBench is meant to reward? I think it would help to report, for instance, whether the explanations of each method contain at least one complete prime implicant.
-
Evaluation protocol: explanations are restricted to edges, but some explainers also score node features. This aspect is not evaluated. Furthermore, only positive instances are explained but, as a nice extension, it would be interesting to see explanations of negative predictions as well.
-
Results in Tables 2 and 3: it seems that many explainers have a recall equal to 1.00 and very low precision. This suggests that the explainers are probably selecting all edges, right? If yes, it would be helpful to report this 'select-all-edges' behaviour explicitly as a baseline, in addition to the random one.
Overall, i lean towards weakly accepting the paper. The idea of compiling GMMs to obtain exact ground truth is original and addresses a relevant problem in the evaluation of graph explainers. Furthermore, the paper is well organised and clearly written. However, I have some concerns and questions that I would invite the authors to take into consideration during the rebuttal.
Questions for authors
See above.
5 comments
Additional follow-up experiment
We thank the reviewer again.
I think it would help to report whether the explanations of each method contain at least one complete prime implicant.
After our initial response, we realized it is actually possible to do so efficiently by using our ROBDD-based algorithm. In particular, as in Eq. 4 is built to verify whether a given subgraph is sufficient, it is enough to feed the provided hard explanation to . We report this additional experiment below. Due to time constraints, the following results are preliminary, pertain to graph classification only, and do not consider SubgraphX. We will expand upon these results in the camera-ready version of the paper.
Experiment 1: We compute the percentage of instances whose explanations contain at least one complete PI. The main challenge of measuring this stems from the soft-to-hard conversion of explanations, as explainers return soft scores but requires hard subgraphs. Using the threshold maximizing the – as done for Tables 2-3 – is misleading here, because several explainers often cover the entire computational graph (recall 1.0), resulting in trivially sufficient explanations. Then, instead of relying on a single, custom threshold, we averaged the percentage above over , where the resulting hard explanation keeps the top-K% of the soft-scored edges and ties are broken at random. The final averaged scores range in , where:
- means explanations are sufficient at every tested
- means sufficient only at
Final scores are reported below, where results are averaged over instances and random seeds, and bold entries represent the best explainer per task.
| Explainer | RedBlueLeaf | Redundancy | CompRed |
|---|---|---|---|
| Saliency | 0.80 ± 0.00 | 1.00 ± 0.00 | 0.70 ± 0.00 |
| IG | 0.80 ± 0.00 | 1.00 ± 0.00 | 1.00 ± 0.00 |
| Deconvolution | 0.20 ± 0.00 | 1.00 ± 0.00 | 0.70 ± 0.00 |
| Guided BP | 0.80 ± 0.00 | 1.00 ± 0.00 | 0.70 ± 0.00 |
| GNNExplainer | 0.80 ± 0.00 | 1.00 ± 0.00 | 0.70 ± 0.00 |
| GraphMask | 0.20 ± 0.00 | 0.91 ± 0.07 | 0.62 ± 0.10 |
| PGMExplainer | 0.22 ± 0.05 | 0.99 ± 0.00 | 1.00 ± 0.00 |
| GraphSVX | 0.80 ± 0.00 | 1.00 ± 0.00 | 1.00 ± 0.00 |
| FlowX | 0.80 ± 0.00 | 1.00 ± 0.00 | 1.00 ± 0.00 |
| LRP | 0.80 ± 0.00 | 1.00 ± 0.00 | 0.70 ± 0.00 |
| Random | 0.20 ± 0.00 | 0.97 ± 0.01 | 0.81 ± 0.05 |
| All edges | 0.20 ± 0.00 | 0.94 ± 0.00 | 0.70 ± 0.00 |
| Oracle (undirected) | 0.80 ± 0.00 | 1.00 ± 0.00 | 1.00 ± 0.00 |
The general ranking of explainers in Tables 2-3 stands, as IG, FlowX, and GraphSVX are still among the best-performing explainers across all tasks.
Experiment 2: Other than the previous percentage of instances whose explanations contain at least one complete PI, it is also possible to report the smallest (in % of edges) such that the explanation keeping the top-K% edges contains a complete PI. Values range in , where lower is better:
- means explanations are already sufficient with the top-20% edges
- means sufficient only at .
| Explainer | RBL | Redundancy | CompRed |
|---|---|---|---|
| Saliency | 40.0 ± 0.0 | 20.0 ± 0.0 | 49.7 ± 0.3 |
| IG | 40.0 ± 0.0 | 20.0 ± 0.0 | 20.0 ± 0.0 |
| Deconvolution | 100.0 ± 0.0 | 20.0 ± 0.0 | 49.7 ± 0.3 |
| Guided BP | 40.0 ± 0.0 | 20.0 ± 0.0 | 49.7 ± 0.3 |
| GNNExplainer | 40.0 ± 0.0 | 20.0 ± 0.0 | 49.7 ± 0.3 |
| GraphMask | 99.8 ± 0.2 | 29.3 ± 6.8 | 57.9 ± 10.2 |
| PGMExplainer | 97.5 ± 5.4 | 20.5 ± 0.5 | 20.2 ± 0.3 |
| GraphSVX | 40.0 ± 0.0 | 20.0 ± 0.0 | 20.0 ± 0.0 |
| FlowX | 40.0 ± 0.0 | 20.0 ± 0.0 | 20.0 ± 0.0 |
| LRP | 40.0 ± 0.0 | 20.0 ± 0.0 | 49.7 ± 0.3 |
| Random | 100.0 ± 0.0 | 23.1 ± 0.9 | 38.9 ± 4.6 |
| All edges | 99.9 ± 0.0 | 26.2 ± 0.3 | 49.7 ± 0.3 |
| Oracle (undirected) | 40.0 ± 0.0 | 20.0 ± 0.0 | 20.0 ± 0.0 |
Thanks once again for helping improve the paper!
Response to rebuttal
I would like to thank the authors for their detailed response and for the additional experiments. The comparison with a trained GIN is helpful, although it shows that the ranking of some explainers changes considerably between compiled and trained models (e.g., Deconvolution and LRP). This suggests that the findings should be transferred to trained GNNs with care. I also appreciate the clarification on what constitutes an ideal explanation and the additional analysis on complete prime implicants, which nicely complements the precision/recall evaluation. Overall, I am keeping my positive assessment of the paper but not raising the score since the comparison with trained models is limited to a single task and partially confirms my concern about the transferability of the findings. I believe this remains an open question to be addressed in future work.
Answer to Reviewer
We thank the reviewer for the suggestions, which we address individually in the following.
W1: Transferability
Following your and reviewer XcZQ's suggestions, we compared the results obtained for compiled GNNs and a trained 2-layer GIN on the MAJORITY2Hop dataset. We observe the following:
Nonetheless, it is difficult to interpret these results, since it is hard to say whether the trained model reliably learns the correct classification rule exclusively, or if some confounders are present
Regarding your suggested additional fine-tuning experiments, we attempted some simple fine-tunings of compiled GNNs, but the models either remain the same or collapse. Additionally, a meaningful comparison requires verifying that the explanation target remains valid after updating the weights, so we leave a systematic study of this extension to future work, and treat these attempts as preliminary.
W2
We report precision and recall separately to distinguish two separate behaviours we wish to reward:
Case 1: an explainer may precisely highlight truly relevant edges but fail to recover alternative explanations, resulting in high precision but low recall;
Case 2: an explainer may precisely highlight many alternative explanations, resulting in both high precision and recall.
Which axis matters more depends on the use case: debugging may favour a focused, minimal reason, whilst auditing may prioritize a complete set of possible explanations. We clarified this in line 367 of the revised PDF.
GNNExplainer falls in case 2, and is therefore among the well-performing explainers. Our insight that it does not sparsify edges is not intended as a criticism per se, but rather as an observation that it contradicts its own training objective, as also noted in previous literature.
This is non-trivial, as checking whether a GNN explanation fulfills Def. 1 is computationally challenging, as discussed at the beginning of Section 4.3.
W3: Evaluation Protocol We agree with the reviewer that it would be interesting to explore in future work, but the extension is not trivial as it would require modifying the way ROBDDs are built. Also, although some graph explainers provide feature explanations, these are more rarely evaluated, and many recent explainers do not provide node feature explanations at all, such as FlowX.
Negative instances, instead, deserve a special distinction. In many tasks like Redundancy, a negative instance is not defined by the presence of a given substructure, but by the lack of it. In these cases, the correct explanation is therefore the empty explanation and plausibility is not well-defined, as discussed in [1,2,3]. Following this, although our ground truth extraction algorithm generalizes to negative instances (line 3 of Alg. 1), we do not evaluate on negative instances in our work.
[1] When Comparing to Ground Truth is Wrong: On Evaluating GNN Explanation Methods. KDD 2021
[2] Explaining the Explainers in Graph Neural Networks: A Comparative Study. ACM Comp. Surveys 2025
[3] Parameterized Explainer for Graph Neural Network. NeurIPS 2020
W4: Some explainers score all edges the same You are right, thank you for the observation. To show this, we added the suggested baseline to Tables 2-3, and we discussed this additional insight in Section 5.2.2 of the revised PDF.
Thanks for helping improve the paper!