- 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: , and Problem 1 then maximises over , so the argmax runs over the slot to the right of the bar.
Questions for authors
See weaknesses.
3 comments
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.
| Dataset | Method | Sparsity ↓ | Charact ↑ | GEA ↑ | Target Probability Ratio |
|---|---|---|---|---|---|
| Benzene | GNNExplainer | 12.73±0.21 | 4.54±0.50 | 3.98±0.25 | 0.070 |
| PGExplainer | 25.55±1.14 | 18.21±2.55 | 14.81±1.14 | 0.285 | |
| RCExplainer | 41.00±2.52 | 85.22±4.63 | 65.34±4.39 | 0.947 | |
| RDS-Explainer | 41.78±1.03 | 94.84±1.46 | 74.33±0.52 | - | |
| FluorideCarbonyl | PGExplainer | 7.48±0.33 | 42.98±4.53 | 27.59±1.45 | 0.710 |
| RCExplainer | 6.21±0.25 | 19.30±5.49 | 24.69±1.08 | 0.351 | |
| RDS-Explainer | 23.56±1.72 | 79.21±4.05 | 55.29±8.06 | - | |
| AlkaneCarbonyl | GNNExplainer | 25.31±1.44 | 81.64±2.67 | 2.75±0.29 | 1.079 |
| GraphEXT | 6.59±0.06 | 61.64±0.00 | 1.80±0.61 | 1.116 | |
| RCExplainer | 11.21±3.08 | 80.82±10.39 | 2.97±6.64 | 1.116 | |
| RDS-Explainer | 34.07±1.73 | 100.00±0.00 | 4.25±1.67 | - | |
| Mutagenicity | PGExplainer | 9.00±0.08 | 53.78±0.84 | 40.56±0.31 | 0.983 |
| GraphEXT | 8.81±0.17 | 56.00±0.66 | 39.42±0.86 | 0.998 | |
| RCExplainer | 12.33±1.25 | 62.81±1.42 | 36.97±1.57 | 0.971 | |
| RDS-Explainer | 26.08±2.16 | 93.78±2.26 | 67.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.
| Dataset | Method | Sparsity ↓ | Charact ↑ | GEA ↑ |
|---|---|---|---|---|
| Benzene | RCExplainer | 51.37±1.15 | 99.98±0.04 | 68.38±1.25 |
| RDS-Explainer | 41.78±1.03 | 94.84±1.46 | 74.33±0.52 | |
| FluorideCarbonyl | GraphEXT | 9.69±0.55 | 69.65±3.51 | 21.44±0.85 |
| RCExplainer | 16.30±1.89 | 78.42±5.99 | 49.63±6.56 | |
| RDS-Explainer | 23.56±1.72 | 79.21±4.05 | 55.29±8.06 | |
| AlkaneCarbonyl | GNNExplainer | 26.08±1.31 | 82.47±0.61 | 3.02±0.67 |
| GraphEXT | 4.36±0.00 | 52.05±0.00 | 0.00±0.00 | |
| RDS-Explainer | 34.07±1.73 | 100.00±0.00 | 4.25±1.67 | |
| Mutagenicity | PGExplainer | 7.56±0.10 | 49.19±0.66 | 29.97±0.20 |
| GraphEXT | 7.31±0.18 | 49.63±0.91 | 27.55±0.81 | |
| RCExplainer | 12.34±2.11 | 57.78±1.89 | 26.54±1.55 | |
| RDS-Explainer | 26.08±2.16 | 93.78±2.26 | 67.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.
| Dataset | Target GNN | Graphs | Annotated motif Charact | Same prediction with motif only | Prediction flipped after motif removal |
|---|---|---|---|---|---|
| AlkaneCarbonyl | GIN | 73 | 24.66 | 95.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.
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.
- Linear edge-count penalty (Table 16).
- 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 times the edge count, and select on the validation set for each dataset (★).
| Dataset | Criterion or | Sparsity ↓ | Charact ↑ | GEA ↑ |
|---|---|---|---|---|
| Benzene | 0.05 ★ | 45.32 | 97.79 | 74.10 |
| Dual Score | 42.07 | 95.77 | 74.48 | |
| FluorideCarbonyl | 0.10 ★ | 36.64 | 91.67 | 58.22 |
| 0.35 | 25.82 | 86.84 | 48.90 | |
| Dual Score | 26.06 | 74.56 | 43.38 | |
| AlkaneCarbonyl | 0.05 ★ | 38.14 | 98.63 | 0.35 |
| Dual Score | 33.25 | 100.00 | 3.43 | |
| Mutagenicity | 0.02 ★ | 26.22 | 94.81 | 68.06 |
| Dual Score | 26.42 | 93.33 | 67.98 |
The linear penalty is a competitive alternative: the validation-selected setting achieves higher Charact on three of the four datasets, and adjusting on FluorideCarbonyl also improves both quality metrics at a similar Sparsity. However, the appropriate explanation size is typically unknown in advance, and each candidate 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.
| Dataset | Method | Sparsity ↓ | Charact ↑ | GEA ↑ | Fallback Rate (%) |
|---|---|---|---|---|---|
| Benzene | Direct generation, fixed threshold | 10.59 ± 13.91 | 16.79 ± 37.53 | 20.66 ± 35.94 | 80.00 |
| Direct generation, validation threshold | 10.77 ± 14.31 | 17.23 ± 38.52 | 20.74 ± 36.11 | 80.00 | |
| RDS-Explainer | 41.78 ± 1.03 | 94.84 ± 1.46 | 74.33 ± 0.52 | - | |
| FluorideCarbonyl | Direct generation, fixed threshold | 4.63 ± 0.01 | 13.07 ± 5.66 | 12.88 ± 4.42 | 99.74 |
| Direct generation, validation threshold | 4.62 ± 0.00 | 13.07 ± 5.66 | 12.87 ± 4.43 | 100.00 | |
| RDS-Explainer | 23.56 ± 1.72 | 79.21 ± 4.05 | 55.29 ± 8.06 | - | |
| AlkaneCarbonyl | Direct generation, fixed threshold | 21.52 ± 3.08 | 99.73 ± 0.61 | 0.00 ± 0.00 | 0.00 |
| RDS-Explainer | 34.07 ± 1.73 | 100.00 ± 0.00 | 4.25 ± 1.67 | - | |
| Mutagenicity | Direct generation, fixed threshold | 30.20 ± 34.57 | 57.93 ± 52.91 | 31.00 ± 33.05 | 39.85 |
| RDS-Explainer | 26.08 ± 2.16 | 93.78 ± 2.26 | 67.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 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, . Both the model and the predicted class of the original graph remain fixed. Problem 1 optimizes over the candidate edge set , which determines the subgraph fed into the GNN.
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.
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. 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.
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.
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.