acceptodds
Under review as a conference paper at ICLR 2027

Sufficient Reasons for Explaining GNNs

Abstract

Explanations of graph neural network (GNN) predictions are almost universally subgraphs of the input (or soft masks over it), judged by fidelity, asking whether keeping or removing the subgraph preserves or changes the prediction. Yet the real reason behind a GNN prediction routinely involves more than what is present—a missing edge, a negative condition on every neighbor, the absence of a motif. No subgraph can express such non-monotone reasons, though one may still pass every fidelity test. We propose sufficient reasons for GNNs: inclusion-minimal sets of (positive and negative) facts about the input such that every graph of the same size satisfying them receives the same prediction. The explanation is thus a certificate rather than a score. Analysing GNN decision classes in the counting logic C, we show that they can be stratified by graph size, which fixes the context in which explanations are valid. Since checking every graph consistent with a candidate explanation is generally infeasible, we give a randomized algorithm that, with PAC guarantees, returns an -sufficient reason from which no fact can be removed. In controlled synthetic experiments with GNN-expressible target properties, our method finds an -sufficient explanation for every instance, while existing subgraph explainers do so only for a minority of instances, seldom for non-monotone properties, and with larger explanations whenever they succeed.

Primary area:
interpretability and explainable AI
Keywords:
graph neural network, explainability, fidelity, sufficient reason, logic C2, PAC guarantees

Reviews

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

The paper asks which graph facts are enough to preserve a GNN prediction, including facts about missing edges. It gives a logical characterization and randomized search algorithms with probabilistic guarantees, then tests them on controlled graph tasks.

Critical strengths

The examples worked well for me. They show why selecting a plausible subgraph can miss something important about the prediction, particularly when missing edges matter. The guarantees also make clear what the explanation is supposed to establish.

Critical weaknesses
  1. The runtime is my main concern. Several minutes for a ten-node graph is a lot, even with the faster algorithm. The authors acknowledge this, but it is still hard to see how far the current method can scale.
  2. The theory allows data-dependent completions, but the experiments only test uniform ones. I am left wondering how the explanations would change when the sampled graphs have to resemble real data.
Questions for authors
  1. How is the single-run confidence guarantee adjusted when the smallest explanation is selected across multiple restarts?
  2. Could a worked comparison with LogicXGNN make the distinction discussed in Section 7 clearer?
1 comment
AuthorsOpenReview ↗

Response to Reviewer zc83

Thank you for the review, we appreciate your comments.

Ad W1: The runtime is primarily the price for the ε-sufficiency certificate (PAC guarantee), which other methods do not provide. The cost is then dominated by the tolerance threshold ε, which can be tuned; e.g., setting it to ε = 0.1 instead of 0.01 makes the (strict) test about five times faster while keeping the reason sizes almost the same. Yet we agree that our work is currently mostly conceptual, and we do not claim scalability to large graphs yet (with the option outlined in future work). Please find our (more detailed) response to Reviewer Cpkv/Weakness 1 regarding the same concern.

Ad W2: Thank you for the suggestion; we newly added exactly this for real molecular data (see the top-level note and the new Section 6.1), where, besides the (previous) uniform completions, we also evaluate on chemically valid completions from the given data domain. The resulting effect is a substantial improvement of our method, with our reasons shrinking by half, since most of the negative facts that we had to certify become implied by the data domain constraints (e.g., an atom with a full valence cannot gain further bonds, hence all the respective ‘non-edges’ disappear). Conversely, the baselines drop to almost zero sufficiency, as the uniform completions produced mostly dense, unrealistic molecules that the model classifies as mutagens, almost irrespective of the structure; hence these (implausible) positive predictions were certified “for free” in this way, and under the realistic completions only explanations containing the actual reason survive. This already shows how much the choice of the data support matters, with further narrowing, e.g. to a learned generative model over the input distribution (mentioned in future work), possibly leading to further improvements.

Ad Q1: Each restart is certified independently with 1-δ confidence, so, by the union bound, selecting the smallest of R certified reasons therefore holds with at least 1-Rδ confidence. Hence, to keep the same confidence for every restart, one needs to divide δ by the number of restarts R beforehand (a small, logarithmic increase in sampled completions), or recertify the selected reason afterward (a single run).

Thank you for pointing out this omission; it is now added in Section 6.

Ad Q2: LogicXGNN returns a global DNF rule (tree) over “grounded predicates” derived from the receptive fields of the input graph nodes by fitting a decision tree to the GNN model predictions across the dataset. The rule derivation is driven by a (“data grounded”) fidelity score, which, as argued throughout our paper, is often misleading in identifying the true explanation reason. Moreover, our theorems in Section 4 show why such a global rule cannot be compact (readable) and exact in general. Hence, such a rule provides a heuristic of what the model “mostly” does across “most” instances, limited to the dictionary of (WL) features observed in the training data, and with no guarantees.

In contrast, our sufficient reason is not a global rule but an instance-level certificate, which is exact for every completion of it, scored by sufficiency. We have briefly expanded on this distinction in Section 7.

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

This paper proposes sufficient reasons as a new notion of local explanation for GNNs. Instead of a subgraph of the input, an explanation is an inclusion-minimal set of presence/absence of edges or node features. Building on the link between message-passing GNNs and the counting logic C2, they demonstrate different theorems. Since the exact verification is infeasible, they propose two randomised greedy deletion algorithms. Experiments on eight synthetic C2 target properties over graphs with 10 nodes show that the method always returns sufficient reasons while the baselines rarely do.

Critical strengths
  1. Clear and convincing motivation: Figure 1 nicely shows that subgraph explanations can pass fidelity tests without containing the actual reason for the prediction.

  2. Principled notion of explanation: allowing negative literals and fixing the size context is well motivated. Furthermore, the connection to sufficient reasons for fixed-dimension inputs makes the contribution easy to position.

  3. Simple algorithm with guarantees: the deletion algorithms are easy to understand, and the PAC guarantees are clearly stated and proven.

Critical weaknesses
  1. Scalability and practical applicability: all experiments use graphs with only 10 nodes. From the reported results, the soft variant needs about 70-115 minutes per instance on a single GPU. Considering the size of small real-world graphs (e.g., molecules with 20-50 atoms), how would the runtime scale with graph size? I believe that for larger graphs, the number of literals would be infeasible to compute.

  2. Only synthetic data: the evaluation considers only synthetic C2 properties which are unrealistic and match exactly the assumptions of the method. Thus, it is unclear how the method would work on standard graph classification benchmarks where the decision rule of the GNN is unknown. I believe that at least one experiment with a real dataset would strengthen the paper. Could you please elaborate on this?

  3. Baseline comparison: GNNExplainer and GraphMask are designed to return subgraphs (present edges and features), and they are evaluated with a criterion that, for non-monotone properties, they cannot satisfy by construction. Furthermore, it seems that the top-k of the baselines is aligned to the size of your own explanation which is not in their favour. I think a comparison with methods that can express negative information (e.g., some counterfactual method), or with your algorithm restricted to positive literals one would make the comparison more informatice.

  4. Theoretical contribution: the results in Section 4 are mostly obtained with standard arguments. Could you please clarify which parts you consider technically novel?

Overall, I lean towards weakly rejecting the paper. The idea is interesting and well motivated, but the experimental evaluation is limited to small synthetic graphs, and the practical applicability of the method remains unclear. I am willing to raise my score if my concerns are addressed.

Questions for authors

See above.

3 comments
AuthorsOpenReview ↗

Response to Reviewer Cpkv (1/2)

Thank you for the detailed review and openness in your assessment. Please find the top-level note and the revised PDF version for the real-world experiment (small molecules, exactly as you suggested). We address the four weaknesses below.

Ad W1: The runtime is primarily the price for the ε-sufficiency certificate (PAC guarantee), which other methods do not provide. The number of literals and cost are polynomial in the size of the graph. With N = O(n²) literals, a run makes O(N) tests of O(ln(N/δ)/ε) completions each – hence is dominated by the tolerance ε, not graph size ‘n’.

On the Mutagenicity, the strict test certifies a molecule at ε=0.1 in a few minutes (rather than dozens) with reasons of almost the same size as at ε=0.01, and the runtime is further tunable, e.g. with the (newly) introduced literal ordering (Appendix B.4) further reducing the search (without touching the guarantees).

We agree, though, that the method is not yet a tool for large graphs, for which e.g. restricting the completions to the input neighborhood (as mentioned in the Conclusion/future work), would be a natural next step.

Ad W2: Please see the added real-world experiments on Mutagenicity (top-level note and Section 6.1). With the decision rule unknown, the method still behaves as on the synthetic targets, with every prediction certified and the baselines sufficient for only a minority, or not at all.

Moreover, it reveals an interesting aspect that the classifier might be non-monotone even when the (chemical) concept is – a positive existential concept such as “contains NO2 group” (a commonly known mutagen alert) is monotone (adding bonds cannot break it), yet the trained GNN model changes its prediction when a bond is added next to it, so the true reason for a positive prediction must forbid such bonds. And, likewise, for the negative class (“no NO2 group”), which is inherently about absence (since adding bonds can create it). Under uniform completions, most of the true (certified) reason is therefore about absent bonds, which a subgraph explanation cannot state. Under chemically valid completions, these negative facts become implied, reducing the size of our reasons by half, while showing a near-complete failure of the baselines in finding the true explanation reasons.

As a side note on the unrealistic assumptions – the C2 is not some peculiar restriction of our method, but the language characterizing the GNN expressiveness, with the laws underlying the common application domains, such as molecular chemistry, being naturally expressible in it (the valence bonds, which atom types may bond, and other laws of chemistry are exactly such small C2 sentences); hence, our synthetic C2 targets are actually a natural case for the GNNs, with the only advantage of the ground truth being known, enabling controlled experiments with better conceptual analysis.

Ad W4: We agree that the proofs of Theorems 4.1, 4.2, and 4.6 in Section 4 are mostly standard model-theoretic arguments. The technical contribution lies in the results and their use. Primarily, the stratification Theorem 4.2 is the underlying reason that an explanation (in the form of a conjunction of literals) must be a statement about a fixed size, which, to our knowledge, no previous GNN explanation method has made explicit. The normal form for C2 sentences w.r.t. a fixed size (4.3) and the resulting axiomatization for C2-equivalence classes are novel results. Overall, the theory in Section 4 further explains why global rule explainers can hardly be exact in general. The C2 abstraction of a reason (4.5-4.6) then introduces a new concept that captures the part of an instance-level certificate the GNN can see.

AuthorsOpenReview ↗

Response to Reviewer Cpkv (2/2): positive-only variant

Ad W3: We agree with the premise that a subgraph cannot satisfy the criterion whenever the reason involves absence, which the experiments are designed to measure rather than assume.

Nevertheless, the positive classes of the positive-existential targets (Table 1) already provide the comparison you ask for, as the explanations there can be based solely on positive literals, and the subgraph search certifies almost all of these (and mostly no others).

The main tables then report both the size-aligned sufficiency and the calibrated size, i.e. the smallest size at which a baseline becomes sufficient, which is in their favour.

Additionally, we measured, as you suggested, a version of our algorithm restricted to positive literals, judged by the same test (see the extended Table 1 below). This is instructive to separate the effect of the literal space from that of the search itself: for the positive classes of the monotone patterns (and a few others whose verdict can be witnessed by present facts alone) the search finds a reason at sizes close to our original/full one, and well below the calibrated baselines. For most of the other classes (including negative predictions of a monotone pattern), no such reason exists; hence, no search over present facts can find it.

Regarding counterfactual methods (mentioned in Section 7) – these generally report which present properties or edges to delete to change the model’s prediction, which still captures merely the necessity of the present facts rather than the absence; hence, they cannot certify a prediction that depends on it either.

Table 1 of the paper (soft test, ε=δ=0.01, five seeds), extended by positive only: our method deleting only the instance's positive literals (same test, R=10). Per method (cell = suff. / size / rel.): ε-sufficiency (%), size (mean ± std, sufficient only), and rel. size (% of the method's own literal space). Positive only: sufficiency = share of instances with an explanation from positive literals. Mask baselines: sufficiency at our size, size of the smallest sufficient top-k (–: none). ⋆: positive class of a monotone target.

patternshare (%)Suff. reasonspositive onlyGNNExplainerGraphMaskSubgraph search
∃≥3P+ ⋆77.3100 / 7.3 ± 0.8 / 1197 / 9.5 ± 1.9 / 290 / 24.4 ± 10.5 / 570 / 34.2 ± 6.9 / 8097 / 13.6 ± 7.8 / 42
∃≥3P−22.7100 / 20.5 ± 4.8 / 320 / – / –0 / – / –0 / – / –0 / – / –
∃≥2∃≥3P+ ⋆75.9100 / 8.0 ± 0.7 / 12100 / 10.0 ± 1.6 / 340 / 27.2 ± 10.6 / 650 / 32.8 ± 7.8 / 79100 / 18.3 ± 5.2 / 61
∃≥2∃≥3P−24.1100 / 20.5 ± 6.3 / 320 / – / –0 / 23.0 ± 0.0 / 610 / 18.0 ± 0.0 / 470 / – / –
∃≥3¬P+77.3100 / 8.9 ± 1.3 / 140 / – / –0 / 30.1 ± 7.5 / 700 / 34.8 ± 7.3 / 800 / – / –
∃≥3¬P−22.7100 / 14.2 ± 4.5 / 2222 / 8.0 ± 0.0 / 220 / 28.7 ± 5.6 / 660 / 31.5 ± 9.7 / 750 / – / –
∃≥4¬E+59.7100 / 11.3 ± 5.4 / 174 / 9.7 ± 0.5 / 270 / 43.0 ± 0.8 / 960 / 41.3 ± 1.9 / 931 / 27.0 / 69
∃≥4¬E−40.3100 / 17.4 ± 12.2 / 270 / – / –0 / 36.3 ± 7.2 / 820 / 35.2 ± 9.9 / 790 / – / –
∀∃P+73.6100 / 11.1 ± 0.6 / 1781 / 13.2 ± 4.6 / 390 / 37.0 ± 4.7 / 840 / 36.7 ± 6.5 / 8311 / 39.6 ± 3.8 / 100
∀∃P−26.4100 / 11.0 ± 2.8 / 170 / – / –0 / – / –0 / – / –0 / – / –
∃∀¬P+34.4100 / 10.8 ± 0.5 / 170 / – / –0 / – / –0 / – / –0 / – / –
∃∀¬P−65.6100 / 11.8 ± 1.6 / 1852 / 10.8 ± 0.4 / 290 / 29.4 ± 9.0 / 620 / 37.8 ± 8.8 / 8020 / 37.8 ± 9.0 / 91
∃≥7E+ ⋆55.7100 / 7.0 ± 0.0 / 11100 / 8.8 ± 3.4 / 240 / 37.0 ± 1.5 / 800 / 30.0 ± 8.5 / 65100 / 27.4 ± 2.3 / 74
∃≥7E−44.3100 / 15.3 ± 0.5 / 240 / – / –0 / – / –0 / – / –0 / – / –
∃≥3∃≥6E+ ⋆44.7100 / 14.5 ± 0.5 / 22100 / 15.2 ± 0.7 / 440 / 37.4 ± 0.5 / 832 / 31.2 ± 8.4 / 69100 / 30.1 ± 2.7 / 86
∃≥3∃≥6E−55.3100 / 14.0 ± 0.0 / 220 / – / –0 / – / –0 / – / –0 / – / –

Thank you for considering our response and for raising your score. We hope the added experiments and clarifications addressed your concerns.

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

The paper argues that by focusing on subgraphs currently explainability approaches cannot model what a GNN learns, as that includes negations of features / edges. They introduce the notion of sufficient reasons that also accomodate negative facts, and propose an approximate algorithm to find tham with epsilon sufficient guarantees.

Critical strengths

The paper addresses a mostly ignored aspect of explaianability in GNNs, namely the absence of a certain feature or pattern. Given the correspondence between GNNs and the C2 fraction of logic, this is substantially undermining the effectiveness of explainability methods.

The paper is formally solid, well explained, and directly tackles the obvious problem with the proposed type of explanations, namely the cost of finding them.

Critical weaknesses

There is no experiment on real-world dataset, all results concern synthetic datasets constructed from target C2 formulas. While this allows to compare explanations with the ground truth, an experimental evaluation on real world datasets would substantially strengthen the contribution (e.g., using standard fidelity metrics + explanation size as performance measures).

While the extracted explanations are correct in terms of the notion of sufficient reason, they tend to be poorly understandable whenever the underlying concept includes negative facts. I am wondering how useful would such explanations be for a user, and how these could be presented to improve utility.

Questions for authors

Can you clarify how an explanation like the one you extract could be used, given it's complexity (especially for negated facts)?

How restrictive is the need to focus on graphs of the same size as the graph to be evaluated? is there a way to leverage this restriction, by e.g. allowing extensions not directly connected to the explanation itself?

Do I understand correctly that if the graph in Fig 1 had other green nodes not connected to a, the sufficient reason should include the lack of edges between a and each of these nodes?

3 comments
AuthorsOpenReview ↗

Response to Reviewer rA71

Thank you for the careful review. Please see the revised PDF version for the real-world experiment you asked for, with individual responses below.

Ad W1: We added experiments with a real-world dataset on Mutagenicity. It shows that the findings from the paper hold on real data, too. Our method certifies every prediction (100% ε-sufficiency), while the baselines certify only a minority under the (original) uniform completions, and none under the (new) chemically valid ones, where our reasons shrink by half, while the baselines, calibrated to sufficiency, need much bigger explanations.

We report sufficiency, size, and the EST rather than fidelity, as it evaluates the model on a single completion (the explanation with everything else removed for Fid-) which, as the paper argues, can lead to very misleading interpretations (additionally, removing part of a molecule may not yield a chemically plausible group).

Ad W2 & Q1: Firstly, a sufficient reason is a certificate that exactly names the present/absent facts the prediction relies on, which can be checked and that no importance score-based explanation offers. For positive-only explanations, the presentation form of our explanation, e.g. via visualization, can be made equivalent to the existing methods. To improve the presentation of the negative facts, one could, e.g., use the presented C2-abstraction to state the reason in the model’s own terms, such as “the witness node ‘a’ has no green neighbor” (or “no further bond at atom 7” for the molecules) instead of drawing all the individual “non-edges”.

Importantly, the negative facts are not an artefact of our method, but a true property of the GNN models and their reasons – an explanation that omits them might be easier to read but can be wrong.

Interestingly, in the real-world experiment with the molecules, most of the negative facts are absorbed by the domain knowledge (valence constraints), and the reasons shrink to what a domain expert (chemist) would naturally read and understand (new molecular figures in the paper).

Ad Q2: Importantly, the same-size graphs define only the context in which the explanation certificate holds. The graphs themselves can be of arbitrary size (e.g., the Mutagenicity molecules have ~10-40 atoms). Each input graph is explained relative to completions on its own vertex set. One could enlarge that context to include graphs obtained by adding/removing vertices, including disconnected vertices, when the certificate remains sufficient there. However, such an enlargement cannot be guaranteed for every classifier. Consider a C2-definable rule that predicts 1 when a graph has at most five vertices and contains a red vertex, or when it has more than five vertices and contains a green vertex; it predicts 0 otherwise. Let G have five vertices, including a red vertex ‘a’, and no green vertices. Within the five-vertex context, {Red(a)} is a sufficient reason. But adding one isolated, non-green vertex produces a graph H with prediction 0 while preserving every literal about the original vertices. Thus, if the enlarged context contains both G and H, no set of literals from G can certify its prediction. Disconnected extensions can therefore be admitted in particular cases, but they do not support a general existence guarantee for certificates in our language.

Ad Q3: Yes. For every such green node not adjacent to ‘a’, the reason must contain the respective "non-edge" fact; otherwise a completion could attach them and falsify the property. Note that this is exactly the 11 (n+1) facts in the respective ∃∀¬P+ pattern (Table 1), which the above-mentioned C2-based presentation could compress to a simple/understandable "‘a’ has no green neighbor".

Reviewer_rA71OpenReview ↗

rebuttal answer

I would like to thank the authors for the clarifications (the same-size graphs constraint limited to individual graphs is indeed pretty reasonable) and for running the extra experiment on real-world data. I agree with the authors that drawing "non-edges" is not the best solution in terms of human interpretability in most cases, and that a C2-abstraction is probably more appropriate. I encourage the authors to investigate how to best convey this information, because it is a crucial aspect of an effective explanation technique. This however goes beyond the scope of the current work, and I am glad to increase my score given the clarifications and improvements already made.

Thank you for the follow-up and the increased score. We're glad the clarifications and the added experiment were helpful.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Real-world experiments

We thank the reviewers for insightful comments. The two main concerns shared across the reviews were real-world data evaluation and runtime, which we now address in a revised PDF, including a new experiment on molecular mutagenicity (Section 6.1; details in the Appendix). All text changes in the revised PDF are marked in blue (new figures, tables and their captions are not).

Following the same protocol, we trained GIN on the data (4337 molecules, 55% mutagenic, 82% accuracy) and sampled 50 correctly classified test molecules (30 mutagens, 20 non-mutagens) for explanation, each containing 9-44 atoms and corresponding to 50-350 graph literals.

We used the strict test (δ=0.01, R=20, ε ∈ {0.01, 0.1}, i.e., m ≈ 850–1,050 resp. 86–105 completions) and, newly (inspired by Reviewer zc83), two completion distributions: the (previous) uniform distribution, and a new (data-driven) valence-respecting distribution, which adds a bond only where both atoms have a free valence slot, hence remaining chemically plausible.

Table: Mutagenicity (strict test, δ=0.01, 50 molecules over three seeds), uniform and valence-respecting completions (C 4, N 4, O 2, S 6, halogens 1): per-class results as in Table 1 of the paper. Per method: ε-sufficiency (%), size (mean ± std, sufficient only), and rel. size (%); class shares 55.4% (mutagen), 44.6% (non-mutagen). †: sufficient by construction. Mask baselines: sufficiency at our size, size of the smallest sufficient top-k (–: none).

completionsεclassSuff. reasonsGNNExplainerGraphMaskSubgraph search
suff. (%)sizerel. (%)suff. (%)sizerel. (%)suff. (%)sizerel. (%)suff. (%)sizerel. (%)
uniform0.01mutagen⁺100†62.0 ± 49.3262737.0 ± 30.826891.9 ± 24.565823.1 ± 6.467
uniform0.01non-mutagen⁻100†76.0 ± 53.038776.7 ± 37.1602101.6 ± 23.6830––
uniform0.1mutagen⁺100†54.1 ± 47.6233333.8 ± 31.724883.2 ± 26.1602219.8 ± 5.657
uniform0.1non-mutagen⁻100†71.2 ± 51.636772.2 ± 38.460395.6 ± 27.8770––
valence0.01mutagen⁺100†27.9 ± 10.4130104.5 ± 45.3760128.4 ± 25.5930––
valence0.01non-mutagen⁻100†40.3 ± 23.9220109.6 ± 29.3940110.1 ± 24.4950––
valence0.1mutagen⁺100†25.5 ± 9.711195.4 ± 43.1690122.7 ± 25.688211.0 ± 0.045
valence0.1non-mutagen⁻100†39.2 ± 24.0210107.1 ± 31.6910107.1 ± 25.7920––

As can be observed, our method still certifies every prediction under both distributions. Under uniform completions, the baselines certify a minority of the mutagens (and almost no non-mutagens), and under valence-respecting ones, almost none. There, when calibrated to sufficiency, they need most of the molecule, while our reasons further shrink by half, often to the nitro group (a known mutagen alert) and its surroundings. The further drop of the baselines is explained by the completions: uniform completions are dense, mostly implausible molecules that the GNN model evaluates as mutagenic almost regardless of their structure, so positive predictions could pass "for free", while realistic completions remove that free pass and only explanations containing the actual reason survive.

With either distribution, certifying a molecule takes 14–37 min at ε=0.01 (median wall-clock time) but can be freely reduced to 2–6 min at ε=0.1 with almost unchanged size, and possibly further.

Other individual points are then answered in the respective comments below (and reflected in Sections 4, 6 and 7).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.