- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes GRACE, a framework for discovering behaviors and their associated circuits in trained graph-classification GNNs. It clusters graph embeddings within predicted classes, characterizes each cluster using discriminative subgraph signatures, and constructs clean/corrupted executions by dampening matched node features and messages. It then applies EAP-IG and a greedy circuit-extraction procedure to identify relevant internal connections. The paper provides theoretical results for signature selection and budgeted circuit extraction. Experiments on six datasets and four GNN architectures evaluate circuit sufficiency and necessity against size-matched random circuits, with additional molecular examples and analysis of shared hidden units.
Critical strengths
- GRACE connects input-level structural patterns with internal circuit analysis in graph classifiers. Automating the construction of behavioral hypotheses and aligned clean/corrupted executions is a useful direction when the target behavior is not specified in advance.
- The experiments cover six datasets and four architectures, and evaluate both sufficiency and necessity against size-matched random circuits. The molecular examples and clustering ablations provide additional evidence beyond a single illustrative case.
Critical weaknesses
- The first roadblock and the validity of the discovered behaviors are insufficiently established. The lack of explanatory or mechanistic ground truth is not specific to graph learning. GRACE addresses the absence of behavior annotations by treating embedding clusters and their discriminative subgraphs as candidate behaviors, but representation similarity and statistical discrimination do not establish that the model uses the selected structures as distinct behaviors. The molecular examples and clustering ablations provide partial evidence, but do not independently validate this assumption. In particular, Appendix L reports different PROTEINS signatures under different clustering choices despite strong circuit-faithfulness scores. This limits how confidently the results can be interpreted as discovery of behavior-specific mechanisms.
- The second roadblock does not sufficiently distinguish the availability of graph perturbations from their behavioral selectivity, leaving the methodological novelty and scope unclear. Feature masking, soft edge/message masking, and other graph augmentation or perturbation approaches provide alternatives to node deletion that can preserve node identities and activation alignment. Section 3.2 should explain why these alternatives are insufficient and what additional capability is provided by the proposed multiplicative node-feature and message dampening. These operations alone do not guarantee that non-target behaviors remain intact. The within-behavior sufficiency and necessity tests and random-circuit baseline do not establish that property or isolate the benefit of the proposed front end. Finally, the broad framing concerns GNNs, whereas evaluation is limited to graph classification with four message-passing architectures; the scope of the claims should be narrowed or supported more broadly.
Questions for authors
- Behavior validation: What evidence distinguishes a discovered signature that the model actually uses from a correlated pattern that merely characterizes an embedding cluster? How should the differing PROTEINS signatures in Appendix L be interpreted when the resulting circuits all receive strong faithfulness scores?
- Perturbation and controls: What property does the proposed dampening provide beyond existing feature and edge/message masking? Can the authors quantify its effect on non-target behaviors, in addition to the existing within-behavior sufficiency and necessity tests? Comparisons with class-level circuits without clustering and matched-size non-signature perturbations would help determine the value of the behavior-discovery stage.
- Scope clarification: Which parts of the framework are expected to transfer to node classification or graph transformers, and which would require redesign? Evaluation on these settings would strengthen generality; this is an extension suggestion rather than a claim that such experiments are required for a narrowly scoped graph-classification contribution.
8 comments
Q1a and W1 continued
GraphTrail (Armgaan et al., 2024). We also tested a global explainer that takes a different approach: it neither clusters nor uses prototypes. GraphTrail explains each class with a boolean formula over the computation trees most important to the model’s prediction (see App. N for details). It does not split a class into clusters, so each class serves as a single behaviour, explained by its formula. We used it as a drop-in replacement and left everything downstream unchanged. Its Kernel-SHAP step, which scores each computation tree’s contribution to the prediction, is computationally expensive, so within the rebuttal period we ran it on a GCN for three datasets (cycles, MUTAG and Mutagenicity). The results are shown in the tables below.
Table: Advantage of GRACE's circuits over a size-matched random baseline, AUC(GRACE-X) - AUC(random), on GCN when the circuit search is fed GraphTrail's behaviours. Mean over the behaviours of each dataset, std in small type. Higher is better.
| Sufficiency | cycles | MUTAG | Mutagenicity |
|---|---|---|---|
| GRACE-Orig | 0.31 ± 0.01 | 0.48 ± 0.09 | 0.45 ± 0.15 |
| GRACE-GraphTrail | 0.37 ± 0.01 | 0.48 ± 0.07 | 0.44 ± 0.09 |
| Necessity | cycles | MUTAG | Mutagenicity |
|---|---|---|---|
| GRACE-Orig | 0.39 ± 0.01 | 0.51 ± 0.03 | 0.43 ± 0.11 |
| GRACE-GraphTrail | 0.36 ± 0.01 | 0.47 ± 0.01 | 0.38 ± 0.04 |
Table: Agreement and flip rates when the circuit search is fed GraphTrail's behaviours (higher is better).
| Agreement | cycles | MUTAG | Mutagenicity |
|---|---|---|---|
| GRACE-Orig | 0.943 | 1.000 | 1.000 |
| GRACE-GraphTrail | 0.947 | 0.956 | 0.948 |
| Flip | cycles | MUTAG | Mutagenicity |
|---|---|---|---|
| GRACE-Orig | 1.000 | 1.000 | 1.000 |
| GRACE-GraphTrail | 0.997 | 1.000 | 1.000 |
In both cases (PAGE, GraphTrail), the circuit search runs unchanged and yields circuits that are sufficient and necessary for the behaviours it is given. This supports treating behaviour identification as a plug-and-play component: GRACE's results do not depend on a particular explainer, and any method that identifies behaviours and groups graphs accordingly can be used.
We have added this discussion and the results above to App. N of the revised paper.
References
- Shin, Yong-Min et al. "PAGE: Prototype-based model-level explanations for graph neural networks." In IEEE transactions on pattern analysis and machine intelligence, 2024.
- Armgaan, Burouj, et al. "GraphTrail: Translating gnn predictions into human-interpretable logical rules." In NeurIPS 2024.
Q1b and W1
How should the differing PROTEINS signatures in Appendix L be interpreted when the resulting circuits all receive strong faithfulness scores?
This is not a conflicting result. The PROTEINS data contains more than one behaviour, as HDBSCAN shows by keeping both sub-clusters corresponding to these behaviors. Agglomerative and spectral clustering each recover only one of these clusters, and not the same one. Hence, the overlap between their behaviours is low; they are describing different things rather than disagreeing about the same thing. Each circuit is nonetheless faithful to the behaviour it captured, which is why both of them receive strong faithfulness scores. This is already explained in App. L:
"The one exception, agglomerative and spectral clustering, is not a disagreement: each retains a single behavior, and they turn out to have locked onto two different sub-clusters that HDBSCAN also keeps separate, so the two behaviors share almost no graphs and pairwise agreement has nothing to compare."
More generally, low behaviour overlap combined with high faithfulness scores indicates that the choice of clustering technique matters for the specific dataset, and there are several ways to respond: the algorithms could be tuned to recover more of the behaviours, they could be replaced by a method based on the geometry of the embedding space, or the circuits from both clustering techniques could be used together.
This aspect is already discussed in our Limitations section, which recommends comparing candidate algorithms on clustering diagnostics and final results:
App A: A second limitation is that GRACE must commit to a clustering algorithm, and how much that commitment matters is decided by the embedding space rather than by the algorithm. Clustering algorithms differ in what they take a cluster to be: -means and Ward favor compact, convex groups, spectral clustering follows connectivity, and HDBSCAN looks for dense regions separated by sparse ones. Where the model's embeddings hold well-separated groups these notions coincide, the algorithms agree, and the behaviors GRACE reports are a property of the model rather than of the clustering; where they do not, the same embeddings admit several defensible partitions and the choice shapes which behaviors, and hence which circuits, are reported...
Q1a and W1
The reviewer is correct that the connection between a behaviour's subgraph and the model is correlational: the behaviour identification step does not causally guarantee that the model uses a discovered signature. However, this is true of current global GNN explainers in general (GraphTrail, GLGExplainer, PAGE and GnnXemplar), and especially of the prototype-based ones (PAGE, GLGExplainer), which characterise the model's behaviour in the same way as our behaviour identification step. Global explainers are therefore valid alternatives for this step, especially the ones that may receive a richer signal from the model than discriminative subgraph mining. Our pipeline allows this swap, so existing and future global explainers can be plugged in with ease. We demonstrate this below by plugging in two of them.
PAGE (Shin et al., 2024). We plugged in PAGE as a drop-in replacement: we matched each prototype onto the graphs of its cluster and left everything downstream unchanged and ran the experiments on a GCN across all six datasets.
Table: Advantage of GRACE's circuits over a size-matched random baseline, i.e., AUC(GRACE-X) - AUC(random), on GCN. X is either the original version or when the circuit search is fed PAGE's behaviours. We report the mean over the behaviours of each dataset, std in small type. Higher is better.
We also report the circuits' agreement rate (ΦCi(G)=Φ(G)) and flip rate (Φ∖Ci(G)=Φ(G)) when the circuit search is fed PAGE's behaviours, which Reviewer J75L also requested in Q2.
With PAGE's behaviours, GRACE's circuits retain a clear advantage over the size-matched random baseline on every dataset, for both sufficiency and necessity. Agreement remains high (0.915 to 1.000) and flip rates are at or near 1, so the circuits still reproduce the model's predictions and removing them still changes them.