- 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
- 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.
- 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
- How is the single-run confidence guarantee adjusted when the smallest explanation is selected across multiple restarts?
- Could a worked comparison with LogicXGNN make the distinction discussed in Section 7 clearer?
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.