acceptodds
Under review as a conference paper at ICLR 2027

RDS-Explainer: Random-Reference Dual Score for Size-Adaptive GNN Explanation

Abstract

Understanding why a graph neural network (GNN) makes a prediction is important for trustworthy graph learning. Many post-hoc GNN explainers identify important nodes or edges, but isolated importance values do not reveal which elements together form the prediction-relevant structure. A concrete explanatory subgraph makes this structure explicit, but its size is difficult to determine: too small may omit important evidence, whereas too large may include irrelevant structure, and the appropriate size varies across graphs. To address this problem, we propose RDS-Explainer (Random-Reference Dual-Score Explainer), which evaluates candidate subgraphs against references constructed from random subgraphs of different sizes. The resulting support and dispensability scores form the Dual Score, which identifies just-sufficient explanations by encouraging sufficient predictive evidence within the candidate subgraph and suppressing residual evidence outside it, without requiring a predefined explanation size. To search the exponential edge-subset space, Cooperative Edge Pruning removes multiple edges per step and coordinates parallel node-level pruning decisions through graph-level feedback. Once trained, the pruning policy applies directly to unseen graphs without per-instance optimization, enabling millisecond-level explanation generation. Across four molecular benchmarks, RDS-Explainer achieves the highest Charact and GEA, even when six baselines receive privileged ground-truth size information. Code will be publicly available after acceptance.

Primary area:
interpretability and explainable AI
Keywords:
Graph Neural Networks, Explainable Artificial Intelligence, Post-hoc Explanation, Size-Adaptive Explanation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_2QxyOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes RDS-Explainer. It is a post-hoc explainer for graph neural networks. The method selects the explanatory subgraph and its size together. It does not take the size as input.

A Dual Score compares a candidate subgraph against size-matched references. The references come from random connected subgraphs. A reinforcement-learning policy then searches candidates. The policy removes several edges per step under graph-level feedback.

The authors benchmark the method against six post-hoc explainers and two size-adaptive explainers. They use four molecular datasets from GraphXAI with frozen GIN target models.

Critical strengths

The paper explores the new direction of integrating size into GNN graph classification explanation.

Critical weaknesses
  • The code is not available, hence no reproduction is possible. The paper states only that "code will be publicly available after acceptance" (p1).

  • Since explanation size is the proposed new dimension, the two main metrics and the main experiments should be based on an accuracy/size trade-off. That is not the case. GEA gives accuracy and Sparsity gives size, but the abstract leads with Charact, which carries no size penalty and is maximised by the full computational graph.

The trade-off comparison is confined to Appendix E.2, Figure 5. There the proposed method adapts its size to each graph, while every baseline is held at one global fraction from 0.1 to 0.9. I anticipate the answer that adaptive sizing is the contribution, so adaptive against fixed is the intended comparison. My objection is that the baselines could adapt too, at negligible cost. GNNExplainer and PGExplainer emit continuous edge mask scores, so a per-graph score threshold, an elbow rule on the score curve, or the proposed Dual Score applied to their own ranking would each give them a per-graph size. None is tried.

The paper also already owns a protocol in which the baselines receive per-graph sizes. The lower block of Table 1 gives every method the size the proposed method selected, and there the advantage largely disappears: GEA loses on FluorideCarbonyl, 55.29 against RCExplainer's 63.22; it is last of seven on AlkaneCarbonyl, 4.25 against 16.57; Charact ties GraphEXT on AlkaneCarbonyl; and both Mutagenicity margins fall inside the reported seed variance. So the fixed-fraction protocol is not the only one available, and the protocol that removes the size advantage is the one that goes worse for the method.

  • The idea to integrate size is interesting; however, it is insufficiently explored. The authors propose one criterion and one search procedure for this task, and compare no alternative realisation of either.

  • The formalism, if not incorrect, does not show command of the notation. Why use a joint distribution to denote the prediction of the GNN in Section 3? The model is frozen and the graph is fixed, so nothing is being conditioned on. The consequence reaches the central definition: Φ(ES)\Phi(\mathcal{E}_S), and Problem 1 then maximises over ES\mathcal{E}_S, so the argmax runs over the slot to the right of the bar.

Questions for authors

See weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer 2Qxy (1/3): W1 and W2 (items 1–2)

Thank you for your insightful assessment of our work and for your detailed, constructive feedback. We’ve carefully revised the manuscript in response and marked the changes in blue. Below, we address the concerns you raised.

W1: Code availability

Response: Thank you for the suggestion. We’ve added an anonymous code link (https://anonymous.4open.science/r/rds-explainer/) to the abstract.

W2: Quality-size trade-offs and baseline size selection

Response: Thank you for the constructive suggestions. In the revised manuscript, we have expanded the main experiments to assess the trade-off between explanation quality and size. We added four comparisons in which baselines choose an explanation size for each graph, including the three you suggested.

  1. Score thresholds (Table 8).
  2. An elbow rule on the edge-score curve (Table 10).
  3. Dual Score applied to each baseline’s own edge ranking (Table 11).
  4. Size selection based on prediction probability (Table 3).

We also used these comparisons to analyze the gap at equal explanation sizes and added Table 6 to show how the GNN’s predictions change when the annotated carbonyl motif is removed.

  1. Analysis of the performance gap at equal explanation sizes and low GEA on AlkaneCarbonyl (Table 6).

1. Score thresholds (excerpt from Table 8)

For each dataset and baseline, we select a threshold on the validation set and retain edges with scores above it at test time. The resulting explanation size can vary across graphs.

DatasetMethodThresholdSparsity ↓Charact ↑GEA ↑Empty Explanations (%)
BenzeneGNNExplainer0.79744.05 ± 0.9639.15 ± 1.0716.36 ± 0.5739.2
PGExplainer0.00072.79 ± 25.9368.24 ± 30.5626.84 ± 8.9668.0
GraphEXT0.02965.67 ± 0.2885.56 ± 0.6251.60 ± 0.280.0
ProxyExplainer0.52775.33 ± 33.7891.45 ± 11.7151.51 ± 20.6760.1
RDS-Explainer-41.78 ± 1.0394.84 ± 1.4674.33 ± 0.52-
FluorideCarbonylPGExplainer0.00022.78 ± 4.7675.00 ± 5.4357.09 ± 4.870.4
IDEA0.00070.88 ± 39.9478.86 ± 29.1733.39 ± 15.640.0
RDS-Explainer-23.56 ± 1.7279.21 ± 4.0555.29 ± 8.06-
AlkaneCarbonylGNNExplainer0.76436.63 ± 0.7281.64 ± 2.676.56 ± 0.630.0
PGExplainer1.00020.83 ± 0.00100.00 ± 0.000.08 ± 0.000.0
GraphEXT0.16112.39 ± 2.3187.95 ± 3.270.26 ± 0.145.8
RDS-Explainer-34.07 ± 1.73100.00 ± 0.004.25 ± 1.67-
MutagenicityGNNExplainer0.63665.85 ± 2.7386.52 ± 0.3323.03 ± 0.6658.5
PGExplainer0.00030.74 ± 1.7594.96 ± 1.1050.74 ± 1.431.9
GraphEXT0.10023.37 ± 0.3088.59 ± 1.3560.16 ± 0.380.0
ProxyExplainer0.76729.87 ± 3.4990.52 ± 9.6564.82 ± 5.110.4
RDS-Explainer-26.08 ± 2.1693.78 ± 2.2667.49 ± 2.51-

No edges passed the threshold in 31.7% of the evaluated instances, illustrating the difficulty of choosing a single threshold for graphs with different score distributions. We also tested thresholds on per-graph normalized edge scores (Table 9 in the manuscript). This avoided empty explanations, but nearly uniform scores led to full-graph explanations in 14.2% of cases.

2. An elbow rule on the edge-score curve (excerpt from Table 10)

On each graph's score curve, we locate the point farthest from the line segment connecting the first and last points, and retain all edges in the ranking up to that point.

DatasetMethodSparsity ↓Charact ↑GEA ↑Degenerate Curves (%)
BenzenePGExplainer100.00 ± 0.00100.00 ± 0.0036.41 ± 0.00100.0
GraphEXT53.99 ± 1.6654.42 ± 2.3936.82 ± 0.610.0
IDEA6.14 ± 1.080.54 ± 1.102.46 ± 3.390.0
RDS-Explainer41.78 ± 1.0394.84 ± 1.4674.33 ± 0.52-
FluorideCarbonylPGExplainer19.14 ± 4.8671.84 ± 4.1053.26 ± 5.020.8
RDS-Explainer23.56 ± 1.7279.21 ± 4.0555.29 ± 8.06-
AlkaneCarbonylGNNExplainer43.58 ± 0.7193.15 ± 3.218.17 ± 0.430.0
PGExplainer20.88 ± 0.03100.00 ± 0.000.08 ± 0.000.0
IDEA14.47 ± 5.0180.00 ± 16.790.04 ± 0.050.0
RDS-Explainer34.07 ± 1.73100.00 ± 0.004.25 ± 1.67-
MutagenicityPGExplainer20.72 ± 0.5786.07 ± 1.5249.55 ± 1.000.7
IDEA16.79 ± 2.2561.48 ± 15.1942.74 ± 11.530.0
ProxyExplainer27.18 ± 5.4882.81 ± 21.7958.39 ± 10.890.1
RDS-Explainer26.08 ± 2.1693.78 ± 2.2667.49 ± 2.51-

Because the elbow rule selects explanation size from the shape of the score curve alone, the selected edges may not suffice to support the original prediction. When the score curve is flat, the rule can also return the full graph. In such cases, even a high Charact must be read alongside Sparsity to judge whether the explanation is compact.

AuthorsOpenReview ↗

Response to Reviewer 2Qxy (2/3): W2 (items 3–5)

W2 (continued)

Response:

3. Dual Score applied to each baseline’s own edge ranking (excerpt from Table 11)

We score prefixes of varying lengths along each baseline's edge ranking and select the prefix with the highest Dual Score.

DatasetMethodSparsity ↓Charact ↑GEA ↑Target Probability Ratio
BenzeneGNNExplainer12.73±0.214.54±0.503.98±0.250.070
PGExplainer25.55±1.1418.21±2.5514.81±1.140.285
RCExplainer41.00±2.5285.22±4.6365.34±4.390.947
RDS-Explainer41.78±1.0394.84±1.4674.33±0.52-
FluorideCarbonylPGExplainer7.48±0.3342.98±4.5327.59±1.450.710
RCExplainer6.21±0.2519.30±5.4924.69±1.080.351
RDS-Explainer23.56±1.7279.21±4.0555.29±8.06-
AlkaneCarbonylGNNExplainer25.31±1.4481.64±2.672.75±0.291.079
GraphEXT6.59±0.0661.64±0.001.80±0.611.116
RCExplainer11.21±3.0880.82±10.392.97±6.641.116
RDS-Explainer34.07±1.73100.00±0.004.25±1.67-
MutagenicityPGExplainer9.00±0.0853.78±0.8440.56±0.310.983
GraphEXT8.81±0.1756.00±0.6639.42±0.860.998
RCExplainer12.33±1.2562.81±1.4236.97±1.570.971
RDS-Explainer26.08±2.1693.78±2.2667.49±2.51-

Using the same Dual Score to choose explanation sizes from baseline rankings always selects a non-empty edge set, but the chosen edges can still retain very little predictive support. On Benzene, four of the six baselines retain only 7.0%–50.2% of the original predicted-class probability on average. Taken together across the three rules you suggested, some baselines match RDS-Explainer on one quality metric with a smaller explanation, yet no baseline simultaneously reaches both the Charact and GEA of RDS-Explainer at a lower Sparsity.

Because thresholds and the elbow rule encounter empty explanations or full-graph fallbacks, and Dual Score selection on the baselines' rankings sometimes retains little predictive support, we further compare the minimum number of edges each baseline needs when required to preserve most of the original prediction probability.

4. Size selection based on prediction probability (excerpt from Table 3)

Following each baseline's edge ranking, we take the shortest prefix that keeps the probability of the original predicted class at least 95% of its full-graph value. This ratio is fixed in advance and identical across all baselines.

DatasetMethodSparsity ↓Charact ↑GEA ↑
BenzeneRCExplainer51.37±1.1599.98±0.0468.38±1.25
RDS-Explainer41.78±1.0394.84±1.4674.33±0.52
FluorideCarbonylGraphEXT9.69±0.5569.65±3.5121.44±0.85
RCExplainer16.30±1.8978.42±5.9949.63±6.56
RDS-Explainer23.56±1.7279.21±4.0555.29±8.06
AlkaneCarbonylGNNExplainer26.08±1.3182.47±0.613.02±0.67
GraphEXT4.36±0.0052.05±0.000.00±0.00
RDS-Explainer34.07±1.73100.00±0.004.25±1.67
MutagenicityPGExplainer7.56±0.1049.19±0.6629.97±0.20
GraphEXT7.31±0.1849.63±0.9127.55±0.81
RCExplainer12.34±2.1157.78±1.8926.54±1.55
RDS-Explainer26.08±2.1693.78±2.2667.49±2.51

This uniform probability requirement directly compares how compact each baseline can make its explanation while preserving most of the predictive support. Across all four datasets, every baseline with a lower Sparsity than RDS-Explainer also has a lower mean Charact and a lower mean GEA than RDS-Explainer. This shows that when baselines select per-graph sizes from their own rankings, RDS-Explainer still maintains a competitive trade-off between explanation quality and size.

5. Analysis of the performance gap at equal explanation sizes and low GEA on AlkaneCarbonyl (Table 6).

When we directly provide baselines with the per-graph sizes selected by RDS-Explainer (lower block of Table 1), the baselines achieve higher GEA in 83/108 comparisons than when selecting sizes on their own above. Because the sizes chosen by RDS-Explainer benefit the baselines, the narrower performance gap in Table 1 is expected.

To examine the low GEA on AlkaneCarbonyl, we have added the diagnostic in Table 6.

DatasetTarget GNNGraphsAnnotated motif CharactSame prediction with motif onlyPrediction flipped after motif removal
AlkaneCarbonylGIN7324.6695.9%26.0%

After removing the annotated carbonyl motif, roughly 74% of the graphs still retain their original prediction, indicating that structures outside the annotation can also support the model's prediction.

We have added the above experiments and analyses to RQ2 in the main text and to the appendix, and we have revised the summary of experimental results in the abstract to more accurately reflect the trade-off between explanation quality and size.

AuthorsOpenReview ↗

Response to Reviewer 2Qxy (3/3): W3 and W4

W3: Alternative scoring and search methods

Response: Thank you for the suggestion. We added two comparisons to test alternatives to the Dual Score and cooperative pruning.

  1. Linear edge-count penalty (Table 16).
  2. Direct edge-mask generation (Table 17).

1. Linear edge-count penalty (excerpt from Table 16)

Keeping cooperative pruning fixed, we replace the Dual Score with the prediction response minus λ\lambda times the edge count, and select λ\lambda on the validation set for each dataset (★).

DatasetCriterion or λ\lambdaSparsity ↓Charact ↑GEA ↑
Benzene0.05 ★45.3297.7974.10
Dual Score42.0795.7774.48
FluorideCarbonyl0.10 ★36.6491.6758.22
0.3525.8286.8448.90
Dual Score26.0674.5643.38
AlkaneCarbonyl0.05 ★38.1498.630.35
Dual Score33.25100.003.43
Mutagenicity0.02 ★26.2294.8168.06
Dual Score26.4293.3367.98

The linear penalty is a competitive alternative: the validation-selected setting achieves higher Charact on three of the four datasets, and adjusting λ\lambda on FluorideCarbonyl also improves both quality metrics at a similar Sparsity. However, the appropriate explanation size is typically unknown in advance, and each candidate λ\lambda requires retraining the model. The Dual Score allows the model to choose per-graph explanation sizes after a single training run, avoiding dataset-by-dataset tuning of an edge-count penalty coefficient.

2. Direct edge-mask generation (excerpt from Table 17)

We train a model with a differentiable form of the same Dual Score to generate an edge mask in a single step. If no edge passes the threshold, we retain the single highest-scoring edge and record the instance as a fallback.

DatasetMethodSparsity ↓Charact ↑GEA ↑Fallback Rate (%)
BenzeneDirect generation, fixed threshold10.59 ± 13.9116.79 ± 37.5320.66 ± 35.9480.00
Direct generation, validation threshold10.77 ± 14.3117.23 ± 38.5220.74 ± 36.1180.00
RDS-Explainer41.78 ± 1.0394.84 ± 1.4674.33 ± 0.52-
FluorideCarbonylDirect generation, fixed threshold4.63 ± 0.0113.07 ± 5.6612.88 ± 4.4299.74
Direct generation, validation threshold4.62 ± 0.0013.07 ± 5.6612.87 ± 4.43100.00
RDS-Explainer23.56 ± 1.7279.21 ± 4.0555.29 ± 8.06-
AlkaneCarbonylDirect generation, fixed threshold21.52 ± 3.0899.73 ± 0.610.00 ± 0.000.00
RDS-Explainer34.07 ± 1.73100.00 ± 0.004.25 ± 1.67-
MutagenicityDirect generation, fixed threshold30.20 ± 34.5757.93 ± 52.9131.00 ± 33.0539.85
RDS-Explainer26.08 ± 2.1693.78 ± 2.2667.49 ± 2.51-

Under the same scoring criterion, cooperative pruning achieves higher Charact and GEA on three datasets. Direct generation frequently falls back to a single edge on Benzene and FluorideCarbonyl, and tuning the threshold on the validation set does not substantially improve explanation quality. On AlkaneCarbonyl, direct generation reaches a comparable Charact at a lower Sparsity, with a GEA of 0.

W4: Notation for GNN predictions

Response: Thank you for pointing out this notation issue. In Section 3, we have revised the notation to use pθ(GS)\mathbf{p}_{\theta}(\mathcal{G}_{S}) for the frozen GNN's class probabilities on a candidate subgraph and to express the prediction response as the log-probability of the original predicted class, Φ(ES)=log⁡[pθ(GS)]y^G\Phi(\mathcal{E}_S) = \log[\mathbf{p}_\theta(\mathcal{G}_S)]_{\hat{y}_{\mathcal{G}}}. Both the model and the predicted class of the original graph remain fixed. Problem 1 optimizes over the candidate edge set ES\mathcal{E}_{S}, which determines the subgraph fed into the GNN.

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

RDS-Explainer selects explanation subgraphs and their sizes using a Dual Score calibrated against random subgraphs of different sizes. A shared actor and centralized critic learn a sequence of cooperative edge-pruning decisions; inference returns the highest-scoring visited candidate. Experiments use four molecular datasets, primarily with GIN predictors, and compare fidelity, motif overlap, adaptive sizing, and runtime.

Critical strengths
  • Jointly selecting explanation structure and size addresses a practical limitation of fixed-budget explainers. The random-reference score provides a concrete way to compare candidates of different sizes without requiring a user-specified budget.
  • Size-matched comparisons, native adaptive baselines, ablations, and edge perturbations provide a reasonably thorough evaluation. The results on Benzene and Mutagenicity support the practical benefit of combining adaptive scoring with learned pruning.
Critical weaknesses
  • The claim that little predictive evidence remains outside the explanation needs qualification for redundant motifs. The score measures the response after retaining the candidate, rather than the complement's standalone predictive support.
  • The runtime breakdown should clarify whether test latency includes constructing random references for a new graph. This would make the efficiency claim easier to assess.
Questions for authors

Please see the weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer NDoK: W1 and W2

We sincerely thank the reviewer for the positive and thoughtful assessment of our work, as well as for the constructive feedback. Below, we address each concern and question in detail.

W1: Redundant motifs and dispensability

Response: Thank you for this feedback. The dispensability surplus evaluates the impact of removing the remaining edges on the original prediction while retaining the candidate explanation, thereby assessing redundancy indirectly rather than evaluating the complement in isolation. We have adopted more precise wording in the abstract and Section 4.2 to clarify that the Dual Score favors explanations where removing the edges outside the explanation causes a smaller prediction-response loss than the reference loss from removing an equal number of random edges.

W2: Test latency and random reference construction

Response: Thank you for the suggestion. We have added the time for constructing random references and listed reference construction and inference times separately in the note to Table 13. Their sum is the test latency of RDS-Explainer. We have also adjusted the efficiency statement in the abstract accordingly.

RDS-ExplainerMean Latency (ms/graph)
Constructing random references226.97
Inference73.00
Test latency (sum of both)299.97
Reviewer_ofniOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper tackles the issue of size of explanation sub-graph for graph explainability. It proposes RDS-Explainer which identifies explanation sub-graph without requiring a predefined explanation size.

The paper introduces a Random-Reference Dual Score, which evaluates candidate sub-graphs on support and dispensability.

And a Cooperative Edge Pruning which uses an actor-critic reinforcement learning framework to learn which edges to remove. The paper finally evaluates its method on molecular graph classification datasets.

Critical strengths
  • The paper targets a very important problem especially in graph modality, which is to find the optimal size of explanation sub-graph. The size of explanation sub-graph is a very frequently encountered implementation level issues and needs to be addressed.

  • The paper overcomes the issue of scalability by using actor and critic framework and directly learning to score edges for explanation.

Critical weaknesses
  • The necessity of using Dual Score is not very clear. Both the support and dispensability are calculated from prediction response. What complementary information the two surpluses capture beyond the size-dependent calibration of prediction confidence?

  • The need of using reinforcement learning is not motivated clearly. One ca use the same dual score but use a learned masked using dual score to do something similar, which to me feels more simpler and effective.

Questions for authors

Major

  1. Dual Score formulation and necessity. Equations (4) and (5) define both the support and dispensability surpluses by subtracting size-dependent reference terms from the same prediction response Φ(ES)\Phi(E_S). For any fixed graph and explanation size, these reference terms are constants, so both surpluses are monotonically dependent on the same prediction response. Consequently, the Dual Score does not independently evaluate predictive evidence in the excluded subgraph, despite this being part of the motivation. Could the authors clarify what complementary information the two surpluses capture beyond size-dependent calibration of prediction confidence?

    • Furthermore, why is the proposed dual formulation preferable to simpler size-regularized objectives, such as Φ(ES)−λ∣ES∣\Phi(E_S)-\lambda |E_S| ? Comparisons against these alternatives can help establish the necessity of the proposed formulation.
  2. Necessity of reinforcement learning. Why is the actor–critic framework necessary instead of a simpler learned mask generator trained using the same Dual Score? I am not motivated that why one needs to use reinforcement learning if standard mask based approaches could work.

  3. Need of more experiments across bigger datasets.

    • Current method only evaluates GIN on 4 small dataset and compare different GNN architectures just on Benzene dataset. How does the method perform across harder non molecular datasets. Also, a more robust comparison with different datasets is required to show effect of different architectures.

Minor

  • Absence based explanations are missing, if GNN learns a class based on absence of a subgraph then can the authors comment whether RDS-Explainer can still capture it. Like absence of benzene ring, GrphTrail[1] argues about these types of results, however they do it for global explainers.
  • Baselines are slightly old, and 1 definite missing comparison is BetaExplainer [2].
  • Request to report Fid+ and Fid- separately in appendix.

[1] B. Armgaan, M. Dalmia, S. Medya, and S. Ranu, “GraphTrail: Translating GNN Predictions into Human-Interpretable Logical Rules,” in Advances in Neural Information Processing Systems (NeurIPS), vol. 37, 2024.

[2] W. Sloneker, S. Patel, H.-J. Wang, L. Crawford, and R. Singh, “BetaExplainer: A Probabilistic Method to Explain Graph Neural Networks,” Journal of Statistical Theory and Applications, vol. 24, no. 2, pp. 469–488, 2025, doi: 10.1007/s44199-025-00118-x.

3 comments
AuthorsOpenReview ↗

Response to Reviewer ofni (1/2): W1 & Q1, W2 & Q2

Thank you for your thoughtful assessment of our work and for your suggestions for strengthening the evaluation. We’ve revised the manuscript in response and marked the changes in blue. Below, we address each of your concerns and questions.

W1 & Q1: Dual Score formulation and necessity

Response: Thank you for these questions. We clarified what the dispensability surplus measures in Section 4.2 and added a comparison with a linear edge-count penalty Φ(ES)−λ∣ES∣\Phi(E_{S}) - \lambda|E_{S}| (Table 16).

The ablations support combining the two surpluses. Tables 4 and 7 show that using support alone lowers Charact on all four datasets, while using dispensability alone raises Charact with higher Sparsity. We also compared the Dual Score with a linear edge-count penalty, as shown below.

Linear edge-count penalty (excerpt from Table 16)

Keeping cooperative pruning fixed, we replace the Dual Score with Φ(ES)−λ∣ES∣\Phi(E_{S}) - \lambda|E_{S}| in training and candidate scoring. ★ marks the λ\lambda selected on the validation set for each dataset.

DatasetCriterion or λ\lambdaSparsity ↓Charact ↑GEA ↑
Benzene0.05 ★45.3297.7974.10
Dual Score42.0795.7774.48
FluorideCarbonyl0.10 ★36.6491.6758.22
0.3525.8286.8448.90
Dual Score26.0674.5643.38
AlkaneCarbonyl0.05 ★38.1498.630.35
Dual Score33.25100.003.43
Mutagenicity0.02 ★26.2294.8168.06
Dual Score26.4293.3367.98

The validation-selected penalty achieves higher Charact on three datasets, with higher Sparsity on Benzene and FluorideCarbonyl. The appropriate explanation size varies across graphs and is usually unknown in advance, making it difficult to choose a penalty weight. Each value of λ\lambda also requires retraining. RDS-Explainer trains once and uses each graph’s own random references to compare candidates of different sizes and jointly select the explanation edges and their number.

W2 & Q2: Actor-critic pruning vs. direct edge-mask generation

Response: Thank you for the suggestion. We added an experiment comparing cooperative pruning with a direct edge-mask generator trained using a differentiable form of the same Dual Score (Table 17).

Direct edge-mask generation (excerpt from Table 17)

DatasetMethodSparsity ↓Charact ↑GEA ↑Fallback Rate (%)
BenzeneDirect generation, fixed threshold10.59 ± 13.9116.79 ± 37.5320.66 ± 35.9480.00
Direct generation, validation threshold10.77 ± 14.3117.23 ± 38.5220.74 ± 36.1180.00
RDS-Explainer41.78 ± 1.0394.84 ± 1.4674.33 ± 0.52-
FluorideCarbonylDirect generation, fixed threshold4.63 ± 0.0113.07 ± 5.6612.88 ± 4.4299.74
Direct generation, validation threshold4.62 ± 0.0013.07 ± 5.6612.87 ± 4.43100.00
RDS-Explainer23.56 ± 1.7279.21 ± 4.0555.29 ± 8.06-
AlkaneCarbonylDirect generation, fixed threshold21.52 ± 3.0899.73 ± 0.610.00 ± 0.000.00
RDS-Explainer34.07 ± 1.73100.00 ± 0.004.25 ± 1.67-
MutagenicityDirect generation, fixed threshold30.20 ± 34.5757.93 ± 52.9131.00 ± 33.0539.85
RDS-Explainer26.08 ± 2.1693.78 ± 2.2667.49 ± 2.51-

Cooperative pruning achieves substantially higher Charact and GEA on three datasets. The direct generator often selects no edges on Benzene and FluorideCarbonyl, and choosing its threshold on the validation set makes little difference to explanation quality. On AlkaneCarbonyl, the direct edge-mask generator achieves comparable Charact at lower Sparsity.

AuthorsOpenReview ↗

Response to Reviewer ofni (2/2): Q3–Q6

Q3: Larger datasets and different GNN architectures

Response: Thank you for suggesting a broader evaluation. We added experiments to complete the GIN, GCN, and GAT comparisons across all four molecular datasets and to evaluate RDS-Explainer on two non-molecular datasets.

  1. GCN and GAT on three additional molecular datasets (Table 18).
  2. Non-molecular comparisons on house_triangle and PowerGraph UK (Table 19).

In each comparison, all methods use the same number of explanation edges on a given graph.

1. GCN and GAT on three additional molecular datasets (Table 18)

DatasetTarget GNNRDS-Explainer Charact ↑Best Baseline Charact ↑RDS-Explainer GEA ↑Best Baseline GEA ↑
FluorideCarbonylGCN96.89 ± 1.6880.16 ± 8.66 (IDEA)51.71 ± 3.2644.16 ± 2.00 (IDEA)
GAT98.15 ± 1.1097.82 ± 1.27 (GraphEXT)39.77 ± 1.0135.75 ± 0.73 (GraphEXT)
MutagenicityGCN94.70 ± 1.3194.24 ± 2.31 (IDEA)62.33 ± 1.2362.00 ± 1.40 (IDEA)
GAT87.13 ± 7.3491.68 ± 2.05 (RCExplainer)58.21 ± 2.3760.72 ± 3.21 (IDEA)
AlkaneCarbonylGCN98.63 ± 0.00100.00 ± 0.00 (RCExplainer)0.83 ± 0.7023.93 ± 1.91 (RCExplainer)
GAT100.00 ± 0.00100.00 ± 0.00 (RCExplainer)0.00 ± 0.0020.11 ± 0.20 (RCExplainer)

On FluorideCarbonyl, RDS-Explainer achieves the highest Charact and GEA with both GCN and GAT. On Mutagenicity, it leads slightly with GCN and trails the best baseline with GAT. On AlkaneCarbonyl, RDS-Explainer achieves high Charact but low GEA with both GCN and GAT. Removing the annotated carbonyl motif leaves predictions unchanged in about 64% of cases for GCN and 100% for GAT (Table 6). Structures outside the motif can therefore sustain the prediction, so a faithful explanation can have low overlap with the annotation.

2. Non-molecular comparisons on house_triangle and PowerGraph UK (excerpt from Table 19)

We used a three-layer GIN on the synthetic house_triangle dataset (1,000 graphs) and the larger PowerGraph UK dataset (64,000 graphs, each with 29 nodes and an average of 97.76 transmission branches).

Methodhouse_triangle Charact ↑house_triangle GEA ↑PowerGraph UK Charact ↑PowerGraph UK GEA ↑
RDS-Explainer98.51 ± 0.3139.85 ± 0.1397.28 ± 0.574.87 ± 0.89
GraphEXT99.43 ± 0.0038.41 ± 0.2187.62 ± 4.755.01 ± 0.45
PGExplainer46.51 ± 0.510.02 ± 0.0441.57 ± 20.055.64 ± 0.60

On house_triangle, RDS-Explainer achieves the highest GEA and comes within one point of the highest Charact. On PowerGraph UK, it leads the best baseline by 9.66 points on Charact, while all methods score below 6 on GEA. This low GEA is consistent with the limited overlap between the annotated lines and the evidence used by GIN (Table 6).

Q4: Explaining predictions based on motif absence

Response: Thank you for raising this question. RDS-Explainer searches among the existing edges of the original graph for a subgraph that preserves the model's prediction. If the model's prediction relies on the absence of a benzene ring, the returned subgraph may still preserve the prediction, but it cannot express the absence of the benzene ring itself as the explanation. We have noted explicitly explaining motif absence as future work in the conclusion.

Q5: Comparison with BetaExplainer

Response: Thank you for the suggestion. We added a comparison with BetaExplainer on all four molecular datasets (Table 20). Both methods retain the same number of edges on each graph.

Comparison with BetaExplainer at equal explanation sizes (Table 20)

DatasetRDS-Explainer Charact ↑BetaExplainer Charact ↑RDS-Explainer GEA ↑BetaExplainer GEA ↑
Benzene94.8424.6074.3328.45
FluorideCarbonyl79.2133.5155.2915.39
AlkaneCarbonyl100.0098.634.2515.33
Mutagenicity93.7890.5267.4944.44

RDS-Explainer achieves higher mean Charact on all four datasets and higher mean GEA on three. On AlkaneCarbonyl, the two methods achieve comparable Charact, while BetaExplainer achieves higher GEA.

Q6: Reporting Fid+ and Fid− separately

Response: Thank you for the suggestion. We added separate Fid+ and Fid− results for all four molecular datasets in Appendix M, Table 21.

Reviewer_ofniOpenReview ↗

Response to the Rebuttal

Thank you authors for a detailed rebuttal. Most of my concerns are addressed in the rebuttal and I have increased my score accordingly.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.