acceptodds
Under review as a conference paper at ICLR 2027

Beyond Trained Models: Compiling GNNs for a Sound Explainer Benchmark

Abstract

Explainers for Graph Neural Networks (GNNs) are commonly evaluated by their *plausibility*, i.e., how well their explanations recover a predefined ground truth, such as a motif planted in the data. This protocol implicitly assumes that a GNN trained on such data relies on the intended motif. Although prior work has questioned this assumption, plausibility remains widespread. First, we show that the assumption is violated on several widely used benchmarks, where, e.g., degree statistics alone suffice to solve the task. Then, we remove this confounder by replacing training with *compilation*. We achieve this by introducing , the first compiler translating graded modal logic formulas into GNN weights, yielding models that replicate the behaviour of the corresponding formulas. Since the behaviour of the model is now known by construction, we can define its ground truth explanation formally and compute it exactly. Building on this, we introduce , a benchmark of compiled GNNs for the evaluation of explainers against this exact ground truth. Experiments on eleven explainers across six tasks show its effectiveness for fine-grained diagnostic evaluation: notably, we discover that most explainers are not robust to indirect influences or alternative implementations of the same formula. These results position as a novel, rigorous evaluation setting for graph post-hoc explainability. Code is available in the supplement.

Primary area:
interpretability and explainable AI
Keywords:
Graph Neural Networks, Explainability, Benchmarking, Formal Explainability

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_UJHhOpenReview ↗
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
  1. 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.

  2. 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.

  3. 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.

  4. Clarity: the paper is well written and easy to follow. The limitations are discussed openly.

Critical weaknesses
  1. 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.

  2. 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.

  3. 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.

  4. 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
AuthorsOpenReview ↗

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:

  • Gradient methods (except IG), GNNExplainer, and LRP worsen in F1
  • IG, GNNExplainer, FlowX, and GraphSVX remain reliable, and the latter two even improve results

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

ExplainerCompiled PCompiled RCompiled F1Compiled F1 RankGIN PGIN RGIN F1GIN F1 Rank
IG0.96±0.011.00±0.000.97±0.0110.95±0.010.99±0.000.97±0.011
FlowX0.91±0.010.95±0.010.92±0.0150.94±0.010.98±0.010.96±0.012
GNNExplainer0.96±0.010.99±0.000.97±0.0110.92±0.010.96±0.050.93±0.033
GuidedBP1.00±0.000.87±0.020.92±0.0150.92±0.040.87±0.110.88±0.084
Saliency1.00±0.000.87±0.020.92±0.0150.76±0.070.94±0.040.82±0.045
GraphSVX0.56±0.020.74±0.020.61±0.0280.56±0.010.80±0.030.65±0.026
LRP1.00±0.000.89±0.020.93±0.0140.83±0.090.60±0.310.60±0.227
PGM-Explainer0.30±0.020.83±0.010.41±0.0190.31±0.010.79±0.020.41±0.028
Deconvolution0.94±0.021.00±0.000.96±0.0131.00±0.000.19±0.010.31±0.029
GraphMask0.02±0.010.78±0.120.03±0.01100.01±0.000.72±0.090.03±0.0110

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

it is not clear what an 'ideal explanation' should be

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 is criticised for not sparsifying redundant edges

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.

I think it would help to report whether explanations contain at least one complete PI

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!

AuthorsOpenReview ↗

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 f↑f_{\uparrow} in Eq. 4 is built to verify whether a given subgraph is sufficient, it is enough to feed the provided hard explanation to f↑f_{\uparrow}. 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 f↑f_{\uparrow} requires hard subgraphs. Using the threshold maximizing the F1F_1 – 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 K∈20,40,60,80,100K \in \\{20, 40, 60, 80, 100 \\}, 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 [0.20,1.00][0.20, 1.00], where:

  • 1.001.00 means explanations are sufficient at every tested KK
  • 0.200.20 means sufficient only at K=100K=100\\%

Final scores are reported below, where results are averaged over instances and random seeds, and bold entries represent the best explainer per task.

ExplainerRedBlueLeafRedundancyCompRed
Saliency0.80 ± 0.001.00 ± 0.000.70 ± 0.00
IG0.80 ± 0.001.00 ± 0.001.00 ± 0.00
Deconvolution0.20 ± 0.001.00 ± 0.000.70 ± 0.00
Guided BP0.80 ± 0.001.00 ± 0.000.70 ± 0.00
GNNExplainer0.80 ± 0.001.00 ± 0.000.70 ± 0.00
GraphMask0.20 ± 0.000.91 ± 0.070.62 ± 0.10
PGMExplainer0.22 ± 0.050.99 ± 0.001.00 ± 0.00
GraphSVX0.80 ± 0.001.00 ± 0.001.00 ± 0.00
FlowX0.80 ± 0.001.00 ± 0.001.00 ± 0.00
LRP0.80 ± 0.001.00 ± 0.000.70 ± 0.00
Random0.20 ± 0.000.97 ± 0.010.81 ± 0.05
All edges0.20 ± 0.000.94 ± 0.000.70 ± 0.00
Oracle (undirected)0.80 ± 0.001.00 ± 0.001.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 K∈20,40,60,80,100K \in \\{20, 40, 60, 80, 100 \\} (in % of edges) such that the explanation keeping the top-K% edges contains a complete PI. Values range in [20,100][20, 100], where lower is better:

  • 2020 means explanations are already sufficient with the top-20% edges
  • 100100 means sufficient only at K=100K=100\\%.
ExplainerRBLRedundancyCompRed
Saliency40.0 ± 0.020.0 ± 0.049.7 ± 0.3
IG40.0 ± 0.020.0 ± 0.020.0 ± 0.0
Deconvolution100.0 ± 0.020.0 ± 0.049.7 ± 0.3
Guided BP40.0 ± 0.020.0 ± 0.049.7 ± 0.3
GNNExplainer40.0 ± 0.020.0 ± 0.049.7 ± 0.3
GraphMask99.8 ± 0.229.3 ± 6.857.9 ± 10.2
PGMExplainer97.5 ± 5.420.5 ± 0.520.2 ± 0.3
GraphSVX40.0 ± 0.020.0 ± 0.020.0 ± 0.0
FlowX40.0 ± 0.020.0 ± 0.020.0 ± 0.0
LRP40.0 ± 0.020.0 ± 0.049.7 ± 0.3
Random100.0 ± 0.023.1 ± 0.938.9 ± 4.6
All edges99.9 ± 0.026.2 ± 0.349.7 ± 0.3
Oracle (undirected)40.0 ± 0.020.0 ± 0.020.0 ± 0.0

Thanks once again for helping improve the paper!

Reviewer_UJHhOpenReview ↗

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.

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

This paper argues that the common practice of evaluating GNN explainers by plausibility is flawed, because a trained GNN may not actually use the planted motif treated as ground truth. The authors first show evidence of such shortcuts in several popular benchmarks, such as degree statistics being enough to solve BaShapes and BaMultiShapes. To get around this, they introduce Gracr, a compiler that turns graded modal logic formulas directly into GNN weights, so the model’s behaviour is known exactly rather than learned. They define the ground-truth explanation as the union of all prime implicants and compute it exactly using ROBDDs, with a correctness proof. Using this setup, they build GracrBench and evaluate eleven explainers on six synthetic tasks. They find that only IG, FlowX and GraphSVX hold up consistently, while many others break down under redundancy, under logically equivalent rewrites of the same formula, or when relevant edges influence the prediction indirectly through two-hop paths.

Critical strengths

The paper tackles a real, long-standing problem, and the survey of 155 papers shows that plausibility-only evaluation is still common practice. Compiling a logic formula directly into a GNN, instead of training one, removes the uncertainty about whether the model learned the intended pattern. The ROBDD-based extraction is provably correct (Theorem 1) and runs fast compared with the explainers themselves. The authors are transparent about limitations and about their changes to explainer implementations, and they release code, which makes the work easy to reproduce and extend.

Critical weaknesses
  • Graded modal logic cannot express cycles, houses or grids, the very motifs used in the benchmarks the paper criticizes. So GracrBench can’t directly replace those benchmarks, and it’s unclear whether its findings transfer to them.
  • Directed-edge ground truth caps node-based explainers like GraphSVX, PGMExplainer and SubgraphX at about 50% precision by construction. GraphMask also appears to be scored over the full graph rather than the receptive field, which would explain its near-zero precision.
  • The runtime experiment uses a monotone function, for which the expensive EXTEND step does no real work, so it understates worst-case cost.
  • The compiler largely follows Barceló et al.’s construction, and computing prime implicants with BDDs is standard in formal XAI. The main contribution is combining these into a benchmark.
  • For every explainer except IG, the authors replace the activation’s true derivative with a custom one (Eq. 9). The gradient-based, LRP and GNNExplainer results therefore partly reflect this design choice rather than the explainers themselves. This weakens the implementation-invariance and GNNExplainer sparsity claims in particular.
Questions for authors

See weaknesses.

2 comments
AuthorsOpenReview ↗

Answer to Reviewer

Thank you for your review and for recognizing that we tackle a long-standing problem. We address your concerns below.

W1: GML Expressivity

Indeed, graded modal logic cannot express cycles and complex substructures, but the same holds for standard message-passing GNNs [1,2], including those tested in previous motif-based benchmarks. This means that previous motif-based benchmarks were evaluating explainers based on motifs that GNNs could not reliably learn, which represents another concern about the reliability of previous benchmarks and confirms that our Assumption 1 may not hold for previous benchmarks

On the contrary, GracrBench makes sure that this ambiguity does not arise and that the ground-truth motifs are expressible by the GNN, as they both originate from the same formula

[1] How Powerful are Graph Neural Networks? ICLR 2019

[2] Generalization and Representational Limits of Graph Neural Networks. ICML 2020

W2

Directed ground truth

We consider directed ground truth explanations because GNNs operate by exchanging directed messages. Hence, we consider the inability to tell which direction carries the information as a limitation of node-level explainers rather than of the evaluation. We already discussed this partially in Appx H.1, but we made it clearer in lines 355-360 of the revised PDF.

Furthermore, to better understand the performance of node-level explainers relative to this intrinsic limitation, we added a new baseline in Tables 2-3 that reports the results of an oracle scoring undirected edges, i.e., the best results an explainer that scores both directions the same can achieve. Results indicate that, for instance, GRAPHSVX consistently scores close to this oracle, confirming our original insight that it is reliable across tasks. We added this new insight in Section 5.2.2.

GraphMask scored over full graph

All explainers are always scored over the full graph; we clarified this in line 370 of the revised PDF. GraphMask achieves almost zero precision because it tends to score every edge the same, whereas other explainers – including the random baseline – give zero importance outside of the receptive field. To confirm this, we added the AllEdges baseline to Tables 2-3, assigning an importance of 11 to every edge, which scores close to GraphMask.

W3: runtime cost Following your remark, and to make the analysis more complete, we complemented Table 12 with the cost analysis for the non-monotone formula Φ′=∃[0,0]u.◊=1⊤\Phi' = \exists^{[0,0]} u.\Diamond_{=1} \top, see Appx. D.4 for the details. The picture is roughly the same as the original monotone formula.

Besides Table 12, Table 13 already reports the cost for the practical formulas we used in our experiments, which include non-monotone tasks, and shows that the runtime for practically useful formulas is feasible.

W4: novelty As we acknowledge in the paper, our compiler indeed follows the theoretical insights of Barceló et al. (2020), and the use of BDDs for computing prime implicants is standard in logic-based XAI. Still, our work has several key novelty aspects:

  • The proof of Barceló et al. (2020) was never transformed into a practical and useful tool, and the technical challenges of such an implementation were never addressed. For instance, we added graph-level readouts and a comparative operator compiled at constant depth
  • BDDs were never used to improve the evaluation of graph XAI, nor to extract prime implicants for GNNs
  • We combined these two components in an original way (as acknowledged by rev. UJHh), allowing us to tackle a “real, long-standing problem” (as acknowledged by you)

Overall, by addressing the problem of XAI evaluation in a principled and formal manner, our contribution brings rigor to the XAI evaluation literature, which we believe can help further develop the field and establish new connections between graph XAI and formal methods.

W5: replacing derivatives The custom backward rule was introduced to avoid issues with the flat gradients of Eq. 2. To show that our main claims are robust to this choice, we added an ablation analysis of the backward rule in Table 9, where we report the performance of explainers using the original, unmodified backward rule. The results show that several explainers, especially those using gradients, fall to random-level performance, as expected. Our key insights, however, remain valid as IG, FLOWX, and GRAPHSVX are still the most robust explainers, and Majority2Hop is still harder than Majority1Hop. Our original claim about the sparsity of GNNExplainer recovers existing empirical and theoretical insights which are independent of our custom backward rule (see Sec. 5.2.1), and is therefore unaffected by this design choice. See Appx C.4 for more discussion.

Overall, our results should indeed be interpreted in conjunction with the model configuration. We have acknowledged this in the paper, but emphasize that the same also applies to trained models.

AuthorsOpenReview ↗

Follow-up to Reviewer

Dear reviewer,

Thank you again for your comments. We would like to know if we have fully addressed your concerns. If not, we remain available for further clarification.

Reviewer_XcZQOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies a problem with evaluating GNN explainers against an expected motif: the trained model may actually use a different rule. A survey of 155 papers finds that roughly a quarter use plausibility alone to evaluate explanations. The benchmark analyses in Appendix B give examples of why this can be misleading.

The authors address this by compiling logical formulas into GNNs instead of training the benchmark models. The compiled GNN uses sum aggregation and truncated ReLU, and follows the formula by construction. The paper defines the ground-truth explanation as the union of all prime implicants (UPI) and computes it exactly using an ROBDD. The reported mean extraction times reach about 0.15 seconds per instance on the benchmark tasks (Table 13).

The benchmark evaluates eleven explainers on six tasks. Only IG, FlowX, and GraphSVX stay above the random baseline across the six main task settings. Changing the compilation or formula formulation can greatly change some explainers' scores, sometimes from random-level to perfect (Tables 10–11). The paper also examines GNNExplainer's failure to remove redundant edges and Deconv's tendency to highlight irrelevant edges (Figs. 3–4).

Critical strengths

The paper gives concrete evidence of a problem with current evaluation. The survey shows that plausibility-only evaluation is common, and Appendix B shows why matching an expected motif does not necessarily mean an explanation reflects what the model uses. This is a useful reason to reconsider how explainers are tested.

The framework lets researchers control the compilation and compare explanations against an exactly computed UPI. The large score changes in Tables 10–11 show why this is useful. Such comparisons are harder to interpret on trained models when their decision rules and ground-truth explanations are unknown.

Critical weaknesses
  1. The effect of the backward rule is not fully tested. At the original binary inputs, the authors' implementation gives zero gradients through the truncated ReLU, including at the non-differentiable points 0 and 1. The authors therefore use the alternative derivative σ̃′(z) = 1{z > 0} in Eq. 9 for all explainers except IG. IG keeps the original backward rule to preserve Completeness (Appendix C.4).

    The paper explains how the modified derivative in Eq. 9 affects the results in Table 10 (p. 27, including footnote 6), and Table 9 compares the two backward rules for IG. Five tasks are unchanged, while Majority2Hop F1 drops from 0.97 to 0.92. What is still missing is a comparison of backward rules for the affected non-IG methods, with the forward computation unchanged. Without this, it is hard to tell how much their relative performance depends on the chosen rule. This does not make the experiments invalid, but the conclusions should be limited to the tested setup.

  2. Table 11 does not establish the equivalence needed for its invariance claim. The two RedBlueLeaf models give the same labels and UPI on the dataset (p. 28). However, this does not establish that they give the same output values on soft edge masks or interpolated inputs queried by explainers. Implementation invariance concerns models that compute the same function, not just models that match on the dataset.

    If the models differ on those perturbed inputs, this could partly explain the different scores. If they agree throughout the relevant input domain, the score changes show a failure of invariance for the evaluated methods under the modified backward rule. That alone would not show that the original, unmodified explainers fail invariance. The paper should make this distinction clear when interpreting Table 11.

The authors’ response addresses my main concerns, as explained in my follow-up comment. I have updated my rating from weak acceptance to clear acceptance.

Questions for authors
  1. Could you compare a small subset of the affected non-IG methods under another backward rule, keeping the forward computation unchanged? Alternatively, please clarify which findings you expect to hold beyond the particular rule in Eq. 9. The Table 10 analysis and the IG check in Table 9 are helpful, but they do not directly answer this for the affected non-IG methods.
  2. On one task, how would the explainer rankings compare between a trained GNN and the compiled GNN? I would treat this as extra context, since the trained model may learn a different rule. I do not consider this comparison a requirement for acceptance.
  3. For Table 11, do the two RedBlueLeaf models produce the same output values on the inputs queried by the explainers, including soft edge masks and interpolated inputs? Matching labels on the dataset is not enough to establish this. Could you clarify what is known about their equivalence and how this affects the implementation-invariance claim under your backward rule?
  4. Please make the edge-only scope more prominent in Sec. 5: the ground truth concerns structural changes while node and edge features are held fixed. Please also briefly summarize the node-to-edge conversion limits already discussed in Appendix H.1. For example, this conversion limits GraphSVX's precision to 50% on Majority1Hop, Redundancy, and CompetingRedundancy, with similar limits for PGMExplainer and SubgraphX. This would help readers interpret the comparisons.
  5. Is the bound n for the comparative operator ♦> set per graph or per dataset, and what values are used for Majority1Hop and Majority2Hop? Since the main results use the expansion in Eq. 6, please clarify how n is chosen to cover the maximum degree, as described in Appendix C.3.
  6. How was the SubgraphX runtime of 1904 ± 1805 seconds in Table 14 calculated under the 180-second per-explanation budget? The caption says the mean uses completed instances, so I am unsure how these numbers fit together. Table 3 explains the OOT and † markers, but a short discussion of the Majority2Hop timeout in the main text would also help.
  7. Please add a note to Tables 2–3 explaining that F1 is averaged over individual instances, as stated in Appendix E. It would also help to note that choosing the best threshold for each instance gives an optimistic score.
2 comments
AuthorsOpenReview ↗

Answer to Reviewer

Thank you for your detailed review and your valuable time. Below, we address your concerns

W1 & Q1: The custom backward rule was introduced to avoid issues with the flat gradients of Eq. 2. Following your suggestion, and to show that our main claims are robust to this choice, we added an ablation analysis of the backward rule in Table 9, where we report the performance of explainers using the original, unmodified backward rule. The results show that several explainers, especially those using gradients, fall to random-level performance, as expected. Our key insights, however, remain valid as IG, FLOWX, and GRAPHSVX are still the most robust explainers, and Majority2Hop is still harder than Majority1Hop. Our original claim about the sparsity of GNNExplainer recovers existing empirical and theoretical insights which are independent of our custom backward rule (see Sec. 5.2.1), and is therefore unaffected by this design choice. See Appx C.4 for a more detailed discussion.

Overall, our results should indeed be interpreted in conjunction with the model configuration. We have acknowledged this in the paper, but emphasize that the same also applies to trained models

Q2: Following your and reviewer UJHh's suggestion, we compared the results obtained for compiled GNNs and a trained 2-layer GIN on the MAJORITY2Hop dataset. We observe the following:

  • Gradient methods (except IG), GNNExplainer, and LRP worsen in F1
  • IG, GNNExplainer, FlowX, and GraphSVX remain reliable, and the latter two even improve results

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

ExplainerCompiled PCompiled RCompiled F1Compiled F1 RankGIN PGIN RGIN F1GIN F1 Rank
IG0.96±0.011.00±0.000.97±0.0110.95±0.010.99±0.000.97±0.011
FlowX0.91±0.010.95±0.010.92±0.0150.94±0.010.98±0.010.96±0.012
GNNExplainer0.96±0.010.99±0.000.97±0.0110.92±0.010.96±0.050.93±0.033
GuidedBP1.00±0.000.87±0.020.92±0.0150.92±0.040.87±0.110.88±0.084
Saliency1.00±0.000.87±0.020.92±0.0150.76±0.070.94±0.040.82±0.045
GraphSVX0.56±0.020.74±0.020.61±0.0280.56±0.010.80±0.030.65±0.026
LRP1.00±0.000.89±0.020.93±0.0140.83±0.090.60±0.310.60±0.227
PGM-Explainer0.30±0.020.83±0.010.41±0.0190.31±0.010.79±0.020.41±0.028
Deconvolution0.94±0.021.00±0.000.96±0.0131.00±0.000.19±0.010.31±0.029
GraphMask0.02±0.010.78±0.120.03±0.01100.01±0.000.72±0.090.03±0.0110

W2 & Q3: Thank you for spotting this. The two variants of RedBlueLeaf are indeed not functionally equivalent, and our wording was imprecise. We fixed it in line 474 and Appx C.5 by making it clear that the two formulas are different, and that this is an ablation of alternative rather than equivalent formulas.

Still, our main claim stands, as the experiment on CompetingRedundancy allows us to test the robustness of explainers over equivalent models.

Q4: We clarified our scope and introduced the gap between node- and edge-wise explainers in lines 348-360. To help interpret the results, we also included a new baseline in Tables 2-3 that reports the results of an oracle scoring undirected edges, i.e., the best results an explainer that scores both directions the same can achieve. This helps determine how much of their gap to a perfect score stems from the conversion from node to edge masks rather than from a failure to localise relevant items. E.g., GRAPHSVX is always close to this oracle, confirming our original insight that it is reliable across tasks.

Q5: Thank you for spotting this inaccuracy! App. C.2–C.3 were imprecise, and we corrected them.

In fact, the bound nn needs only to be at least half of the maximum degree in our tasks, and not at least the maximum degree as we initially wrote. This is because the operator for \\# \psi < \\# \phi holds iff there exists 1≤m≤n1 \le m \le n such that \\# \psi < m \le \\# \phi, so it can only fail when \\# \psi ≥ n and \\# \phi > \\# \psi. In Majority2Hop and Majority1Hop, ϕ\phi and ψ\psi are mutually exclusive, so failure requires degree >2n=100> 2n = 100. Then, in our experiments, nn is fixed to 5050 for both tasks, as the maximum degree is 8686.

Q6 & Q7: We enforce per-explanation budgets by timing at least one explanation per seed. If an explanation exceeds 180s, we drop the seed’s remaining instances only after it finishes. On Majority2Hop, SubgraphX exceeded the budget on the first or second instance of every seed, so the reported time is computed over 6 instances. Then, plausibility scores are averaged only over seeds that ran to completion, which is why SubgraphX is marked OOT in Table 3. We made this clearer in the new Experimental setup in Section 5 and in Table 14

We also updated Tables 2-3 to explain how we compute F1.


Thanks for improving our paper!

Thank you for the additional experiments and clarifications. The backward-rule ablation and revised interpretation of the RedBlueLeaf comparison address my main concerns. The evaluation details also help. It makes sense to me that the robustness findings should be interpreted within the tested model configurations. With these concerns addressed, I am raising my rating from weak acceptance to acceptance.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of main changes

We thank all reviewers for their valuable time and constructive feedback, and for acknowledging that:

  • The paper is well motivated (XcZQ, UJHh) and tackles a long-standing problem (J6Pm).
  • Compiling formulas into GNNs is an original (UJHh) approach that removes the uncertainty about what the model learned, with provably correct ground truth (J6Pm).
  • The findings are informative and useful (UJHh, XcZQ).

We summarize the major changes we made to the paper below, and we highlight them in red in the revised PDF. None of them affect our main claims, and the core of the paper remains unchanged.

  • Backward-rule ablation: we now report all explainers under the unmodified backward rule in Table 9, showing that our key insights are robust to this design choice.
  • New baselines: we added an AllEdges and an OracleUndirected baseline in Tables 2–3 to better interpret the current results.
  • Trained vs. compiled GNNs: we performed a preliminary comparison of plausibility between compiled and trained GNNs; see our answers to UJHh and XcZQ for the details.
  • Expanded the runtime analysis of Alg. 1: we added a non-monotone formula to Table 12, confirming that the runtime of our algorithm is feasible even for more complex settings.
  • Clarifications and corrections:
    • we included a new Experimental setup paragraph that explains the timeout protocol and how F1 is computed (Sec. 5)
    • we corrected the bound on nn for the comparative operator (Appx. C.2–C.3)
    • we clarified that the two RedBlueLeaf tasks are alternative, and not equivalent (Sec. 5.2.2)

Thanks again for reviewing our manuscript. We remain available to provide further clarifications.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.