acceptodds
Under review as a conference paper at ICLR 2027

GRACE: A Mechanistic Understanding of GNNs through Circuit Discovery

Abstract

Mechanistic interpretability aims to reverse-engineer neural networks by identifying the circuits that implement specific behaviors. Despite rapid progress in language models, no framework for mechanistic circuit discovery exists for Graph Neural Networks (GNNs). We argue that the obstacle is not the circuit-finding machinery, which transfers from language models, but the steps that precede it: in graphs, behaviors are neither known nor readily hypothesized, ground truth is unavailable, and discrete edits cannot corrupt a behavior without breaking the graph. We propose *Graph Circuit Explorer* (GRACE), which discovers behaviors without supervision by clustering graphs in the model's functional embedding space and characterizing each cluster by a subgraph signature, selected with the best approximation guarantee achievable in polynomial time. GRACE corrupts each behavior by continuously dampening its signature, which preserves graph validity and enables gradient-based attribution patching, and extracts circuits under an edge budget, a problem we prove NP-hard. Across six datasets and four architectures, GRACE recovers circuits that are sufficient and necessary at a small fraction of the model's edges and outperform size-matched random circuits in every setting. On Mutagenicity, the discovered behaviors correspond to known toxicophores, and circuit analysis reveals that behaviors share most of the hidden units they use, structure that is invisible to input-level explanations.

Primary area:
interpretability and explainable AI
Keywords:
graph neural networks, mechanistic interpretability, explainability

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_gfSqOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. 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?
  2. 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.
  3. 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
AuthorsOpenReview ↗

Q1a and W1

Behavior validation: What evidence distinguishes a discovered signature that the model actually uses from a correlated pattern that merely characterizes an embedding cluster?

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.

SufficiencycyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GRACE-Orig0.31 ± 0.010.48 ± 0.080.47 ± 0.150.45 ± 0.050.36 ± 0.020.58 ± 0.17
GRACE-PAGE0.26 ± 0.000.47 ± 0.120.55 ± 0.120.47 ± 0.020.32 ± 0.020.58 ± 0.13
NecessitycyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GRACE-Orig0.39 ± 0.010.50 ± 0.030.39 ± 0.120.46 ± 0.080.38 ± 0.130.50 ± 0.11
GRACE-PAGE0.34 ± 0.000.50 ± 0.040.38 ± 0.110.42 ± 0.030.32 ± 0.170.51 ± 0.06

We also report the circuits' agreement rate (ΦCi(G)=Φ(G)\Phi_{C_i}(G) = \Phi(G)) and flip rate (Φ∖Ci(G)≠Φ(G)\Phi_{\setminus C_i}(G) \neq \Phi(G)) when the circuit search is fed PAGE's behaviours, which Reviewer J75L also requested in Q2.

AgreementcyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GRACE-Orig0.9431.0000.9911.0000.9920.959
GRACE-PAGE0.9770.9441.0001.0000.9150.982
FlipcyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GRACE-Orig1.0001.0001.0001.0001.0001.000
GRACE-PAGE1.0001.0000.9941.0000.9831.000

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.

AuthorsOpenReview ↗

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.

SufficiencycyclesMUTAGMutagenicity
GRACE-Orig0.31 ± 0.010.48 ± 0.090.45 ± 0.15
GRACE-GraphTrail0.37 ± 0.010.48 ± 0.070.44 ± 0.09
NecessitycyclesMUTAGMutagenicity
GRACE-Orig0.39 ± 0.010.51 ± 0.030.43 ± 0.11
GRACE-GraphTrail0.36 ± 0.010.47 ± 0.010.38 ± 0.04

Table: Agreement and flip rates when the circuit search is fed GraphTrail's behaviours (higher is better).

AgreementcyclesMUTAGMutagenicity
GRACE-Orig0.9431.0001.000
GRACE-GraphTrail0.9470.9560.948
FlipcyclesMUTAGMutagenicity
GRACE-Orig1.0001.0001.000
GRACE-GraphTrail0.9971.0001.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.
AuthorsOpenReview ↗

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: kk-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...

Reviewer_3wQDOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces GRACE, an unsupervised framework for mechanistic circuit discovery in GNNs. GRACE bypass the lack of predefined behaviors and the difficulty of discrete graph corruption. Experiments across six datasets and four architectures demonstrate that the extracted compact circuits achieve high sufficiency and necessity compared to size-matched random circuits, and reveal extensive neuron polysemanticity in GNNs.

Critical strengths

Mechanistic interpretability in GNNs is an important and largely unexplored area, and framing distinct internal mechanisms through clustering in the functional embedding space within the same downstream task is a sound and valuable formulation.

The formulation of behavior signature mining and budgeted circuit extraction, along with the corresponding NP-hardness and approximation proofs, is mathematically rigorous.

Critical weaknesses
  1. The paper only benchmarks against a single baseline: size-matched random circuits. While the authors argue that input-level GNN explainers do not apply to circuit discovery, this does not justify omitting internal model-level attribution baselines. Standard and widely used pruning/attribution heuristics—such as magnitude-based pruning (selecting connections with the largest representation magnitude ) and first-order gradient/gradient ×\times input methods—could readily serve as internal edge selection baselines.

The authors should empirically demonstrate that GRACE’s multi-step continuous dampening + EAP-IG pipeline significantly outperforms these simpler magnitude/gradient-based heuristics.

  1. The proposed continuous message and node dampening (λ∈[0,1)\lambda \in [0, 1) scaling node features and messages towards zero) operates fundamentally like zero-ablation rather than a true semantic counterfactual / corrupted run (as commonly practiced in LLMs, e.g., swapping tokens). Scaling activations toward zero implicitly assumes that the absence of a feature or an unactivated state corresponds to zero. However, in GNNs with ReLU/GELU or non-zero biases, an inactive state or an uninformative baseline representation does not necessarily yield a zero tensor. The authors should justify why decaying toward zero is a faithful corrupting distribution.
Questions for authors

Above

4 comments

The paper only benchmarks against a single baseline... Standard and widely used pruning/attribution heuristics—such as magnitude-based pruning (selecting connections with the largest representation magnitude ) and first-order gradient/gradient input methods—could readily serve as internal edge selection baselines.

Thank you for these suggestions! Reviewer J75L also suggested the weight-based baseline. Please find below the results for both baselines. App. P now contains this discussion.

Weight-magnitude baseline. We grew a circuit greedily on absolute weight magnitude ∣W∣|W|, with the same frontier rule as GRACE and at the same sizes, and scored it on every behaviour. As there is one weight-magnitude circuit per model, it is behaviour-agnostic by construction. It is also a natural ablation of GRACE: the EAP-IG edge score is Wvu⋅∑nΔau[n] gˉv[n]W_{vu}\cdot\sum_n \Delta a_u[n]\,\bar g_v[n], where Δau[n]\Delta a_u[n] is the change in neuron uu's activation on example nn and gˉv[n]\bar g_v[n] is the gradient of the KL divergence with respect to neuron vv's activation on that example. The weight-magnitude circuit is therefore GRACE with the behaviour-dependent activation-times-gradient term removed.

The tables below presents AUC(Grace)-AUC(Weigh-baseline) on sufficiency and necessity. GRACE's sufficiency and necessity AUCs exceed weight-baseline's, on 157 and 151 of 174 behaviours, respectively. On an aggregate level (shown in the table below), the mean AUC gap is positive in 47 of 48 dataset–architecture cells. A one-sided Wilcoxon signed-rank test on the paired per-behaviour AUC differences gives p<10−21p < 10^{-21} for both metrics. We've updated these numbers in Table 2:

SufficiencycyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GCN0.12 ± 0.030.22 ± 0.120.17 ± 0.110.36 ± 0.070.20 ± 0.030.24 ± 0.20
GAT0.18 ± 0.070.35 ± 0.100.10 ± 0.150.19 ± 0.080.13 ± 0.080.11 ± 0.10
GIN0.11 ± 0.030.30 ± 0.070.06 ± 0.080.18 ± 0.030.02 ± 0.060.09 ± 0.07
GraphSAGE0.14 ± 0.020.13 ± 0.010.28 ± 0.080.37 ± 0.020.04 ± 0.050.07 ± 0.06
NecessitycyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GCN0.18 ± 0.080.31 ± 0.060.12 ± 0.150.43 ± 0.090.13 ± 0.150.24 ± 0.07
GAT0.19 ± 0.110.45 ± 0.180.29 ± 0.080.34 ± 0.070.28 ± 0.110.06 ± 0.13
GIN0.15 ± 0.050.24 ± 0.030.10 ± 0.120.07 ± 0.080.02 ± 0.020.12 ± 0.11
GraphSAGE0.20 ± 0.010.30 ± 0.070.09 ± 0.190.05 ± 0.060.15 ± 0.020.00 ± 0.12

Gradient baseline. Reviewer 3wQD suggested another baseline where the circuit is grown based on gradients. We present its AUC results in the tables below. GRACE's sufficiency and necessity AUCs exceed gradient-baseline's on 173 and 162 of 174 behaviours, respectively. On an aggregate level (shown in the table below), the mean AUC gap is positive in 47 of 48 dataset–architecture cells. A one-sided Wilcoxon signed-rank test on the paired per-behaviour AUC differences gives p<10−27p < 10^{-27} for both metrics. We've updated these numbers in Table 2.

sufficiencycyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GCN0.25 ± 0.070.44 ± 0.060.40 ± 0.160.29 ± 0.160.26 ± 0.080.55 ± 0.19
GAT0.23 ± 0.140.65 ± 0.150.35 ± 0.120.31 ± 0.280.37 ± 0.090.46 ± 0.12
GIN0.32 ± 0.010.31 ± 0.060.21 ± 0.070.56 ± 0.080.21 ± 0.080.29 ± 0.07
GraphSAGE0.30 ± 0.120.30 ± 0.120.56 ± 0.040.73 ± 0.040.47 ± 0.070.23 ± 0.08
necessitycyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GCN0.04 ± 0.050.16 ± 0.110.18 ± 0.120.13 ± 0.080.07 ± 0.270.30 ± 0.17
GAT0.06 ± 0.100.28 ± 0.210.31 ± 0.150.19 ± 0.200.43 ± 0.150.23 ± 0.15
GIN0.15 ± 0.080.34 ± 0.040.21 ± 0.170.47 ± 0.090.25 ± 0.250.28 ± 0.06
GraphSAGE0.16 ± 0.030.00 ± 0.040.30 ± 0.200.59 ± 0.180.38 ± 0.110.29 ± 0.12

Sufficiency and Necessity curves. We've added new sufficiency and necessity curves in Figure 10 of App. P to include the new baselines. Grace's curves rise faster with a higher AUC.

W2a

The proposed continuous message and node dampening (scaling node features and messages towards zero) operates fundamentally like zero-ablation rather than a true semantic counterfactual / corrupted run (as commonly practiced in LLMs, e.g., swapping tokens).

We agree that continuous dampening may not be a semantic counterfactual; however, a token swap equivalent is unavailable in the graph space. Token swaps in LLM circuit discovery are not arbitrary; they require knowledge of the behaviour being studied. For instance, to probe subject-verb agreement, one replaces "cat" with "cats" in "The cat sits" instead of a random word. Since GRACE discovers behaviours without supervision, the graph analogue of "subject-verb agreement" and its minimal swap are not available in advance. A behaviour-specific corruption, the "token swap", would presuppose the answer we are looking for. Dampening is therefore a behaviour-agnostic choice.

We also note that this is consistent with how counterfactuals are constructed in GNN explainability. There, interventions are by and large built from edge deletions (Lucic et al. 2022; Bajaj et al. 2021; Tan et al. 2022), rather than from semantic substitution. Dampening is the continuous relaxation of that operator: it weakens the signature's contribution instead of removing it outright, while keeping the graph's topology and indexing fixed so that clean and corrupted activations remain aligned for patching.

References

  • Lucic, Ana, et al. "Cf-gnnexplainer: Counterfactual explanations for graph neural networks." In AISTATS, 2022.
  • Bajaj, Mohit, et al. "Robust counterfactual explanations on graph neural networks." In NeurIPS 2021.
  • Tan, Juntao, et al. "Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning." In WWW 2022.

W2b

Scaling activations toward zero implicitly assumes that the absence of a feature or an unactivated state corresponds to zero. However, in GNNs with ReLU/GELU or non-zero biases, an inactive state or an uninformative baseline representation does not necessarily yield a zero tensor.

Thank you for raising this. The concern is valid for zero-ablation, but it does not apply to our method, which is closer to standard attribution patching: we do not set activations to zero. Instead, we build a corrupted input, run the model on it in full, and patch in the activations from that run.

During that corruption phase, dampening happens pre-aggregation; the aggregate isn't zeroed out. The aggregate at the node still includes its other neighbours. The node’s hidden state therefore stays non-zero. It just carries less of the signature’s evidence.

With regards to dampening the input node features, dampening continuous node features to zero would be incorrect as zero carries a semantic meaning there. However, as we've mentioned in the paper, our method is designed for datasets with one-hot categorical features:

App. A: "The primary limitation of our framework concerns the class of graphs it currently supports. The discriminative subgraph mining step requires categorical node features, as subgraph isomorphism, which underpins the matching of discriminative patterns across graphs, is well-defined only when node identity can be established through discrete labels. Graphs with continuous or richly attributed node features, where individual features carry distinct semantic meaning, fall outside the scope of the current pipeline."

Lastly, the sweep over λ∈[0,1)\lambda \in [0, 1) averages gradients along the whole path from clean to corrupted (Eqs. 6–7), so the attribution does not depend solely on the endpoints.

The authors should justify why decaying toward zero is a faithful corrupting distribution.

We can read this comment in two ways, so we address both.

Reading 1: Why dampen towards zero rather than towards a moderate value, a negative value, amplification, or random scaling?

Our claim is about the direction of the intervention, not about zero as a special value. The corruption has to reduce the signature's evidence without adding evidence of any other kind. Dampening does this: it moves the signature's contribution towards absence while leaving everything else about the graph in place.

  • Messages. Scaling mu→vm_{u\to v} by λ<1\lambda < 1 weakens the edge's contribution to the aggregate. This is the continuous analogue of deleting the edge, but it keeps the topology, node count and edge indexing fixed, which patching requires (§3.2).
  • One-hot node features. xv→λxvx_v \to \lambda x_v progressively unasserts the node's category. Moving in the opposite direction (amplification) strengthens the behaviour rather than corrupting it. Moving past zero (negative values) or towards a different category asserts an input that has no meaning for one-hot features and that the model has not seen. Both add evidence instead of removing it.
  • Random scaling. This has the same problem as the token swap discussed above. The attribution would reflect sensitivity to noise rather than to the behaviour, and a distribution of "plausible alternatives" cannot be defined without already knowing the behaviour. Random scaling can also let unforeseen behaviours creep in. Dampening is monotone and acts only on the signature, so only the signature's evidence changes.

Exactly zero is not required. λ\lambda is a free strength, and one can stop at any small value (such as λ=0.05\lambda = 0.05). EAP-IG (Eqs. 6–7) averages the gradient along the whole path from the clean graph (λk=1\lambda_k = 1) to the corrupted one (λk=λ\lambda_k = \lambda). The score therefore integrates over every dampening level in between, and it depends on the direction of the path rather than on where it ends. We are not asking the network what happens at a particular baseline, but how its output responds as the signature's evidence is withdrawn. As noted above, dampening is applied pre-aggregation, so a node's hidden state stays non-zero throughout: it still receives its other neighbours' messages and its bias.

Reading 2. Why use dampening at all, rather than another corruption operator?

If, however, the question is about the choice of dampening as the corruption operator, then we need a corruption that:

  1. removes the signature's evidence;
  2. leaves the graph valid and the same size, so clean and corrupted activations align edge by edge (otherwise patching breaks);
  3. leaves other behaviours untouched, which is why it acts only on Vi(G)V_i(G) and Ei(G)E_i(G);
  4. is behaviour-agnostic;
  5. is continuous, so EAP-IG has a path to integrate along.

Discrete deletion fails (1)–(3): it changes the graph size, which breaks the patching pipeline; it can create invalid structures (e.g. molecules), and it perturbs neighbouring nodes abruptly. Binary masking keeps the graph valid but fails (5): it gives only the two endpoints, so there is no path for EAP-IG to integrate along. Swapping in a replacement subgraph fails (4), as discussed under W2a. A single scalar λ\lambda applied to the signature’s messages and node features satisfies all five conditions and yields the straight-line path that Eq. 7 requires. Because it is monotone and acts only on the signature, only the signature’s evidence changes.

We ran an experiment on cycles and MUTAG to measure how the granularity of the integration path affects sufficiency. EAP-IG averages the gradient at m values of λ,λk=1−k/m\lambda, \lambda_k = 1 − k/m for k = 1,... , m, running from the clean input (λ\lambda = 1) to the fully dampened one (λ\lambda = 0). Of these, m − 1 are intermediate values. Each cell is the sufficiency AUC gap between GRACE's circuit and a size-matched random control (higher is better).

m (intermediate λ\lambda values)1234510
cycles0.150.310.310.310.310.31
MUTAG0.310.430.470.480.480.48

Sufficiency rises with m and plateaus by m = 4, so the default m = 5 is already on the plateau. m = 0 is excluded because it leaves no gradient to average, so EAP-IG cannot score an edge at all. At m = 1 the gradient is taken only at full dampening, with no integration, and that is the worst setting on both datasets.

We include this full discussion on dampening in App. Q of our revision.


We thank the reviewer for their constructive feedback. We hope the added results and discussions resolve the concerns raised.

Dear Reviewer 3wQD,

Since the discussion phase ends in less than a day, we would really appreciate your feedback on our rebuttal and whether they satisfactorily address the concerns raised.

regards,

Authors

Reviewer_J75LOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This work proposes GRACE to perform circuit discovery in GNNs in an unsupervised manner: a behavior to be explained corresponds to a cluster in the GNN's embedding space, a subgraph pattern is optimized which discriminates that cluster from the rest of the dataset, and then the edges in this cluster can be ablated to generate the clean-corrupted input pairs for attribution patching on the GNN's computation graph. The authors contend that using an unsupervised pipeline is necessary to do circuit discovery for GNNs in general, since graph data does not always admit an obvious ground truth behavior. The authors also show that identifying the optimally discriminative subgraph is NP-hard in general, but their discrimination coefficient is submodular and monotone, and hence a greedy solution is near-optimal. The authors also show that optimal circuit selection under an edge budget is NP-hard, confirming the conjecture of Hanna et al. (2024).

Critical strengths
  • I appreciate the proof that optimal circuit selection under a given edge budget is NP-hard. The fact that it is NP-hard is not surprising, since it is a variation of the standard minimum-weight connected subgraph problem, but to my knowledge (and surprise) the specific formulation relevant to circuit discovery doesn't seem to have been shown before.

  • Formulating the overall pipeline to be unsupervised is a generally useful approach, compared to previous work that relies on hypothesizing a behavior.

Critical weaknesses
  1. I think the novelty claims of this work are somewhat overstated with respect to existing literature. In particular, while the pipeline as a whole seems to be somewhat novel, each individual piece is less so:

    • The work asserts that existing global explainers are not appropriate baseline comparisons for GRACE; this is fair when comparing to GRACE as a whole, but it is not clear to me why these cannot be substituted for the behavior characterization. In particular, PAGE [1] performs a similar process of clustering graph embeddings and discovering prototype subgraphs.
    • As the authors mention in Appendix B, attribution patching has also previously been adapted to GNNs in MINAR (He et al., 2026); while their neural algorithmic reasoning setting does admit clear hypotheses about behavior, and consequently suggests specific data corruptions, this also limits the novelty of the attribution patching stage of GRACE.
    • Taken together, it seems that the main novelty lies in using prototype-based explanations to hypothesize behaviors for circuit discovery. This is promising, but I think asserting that "no framework for mechanistic circuit discovery exists for GNNs" overstates the gap in the literature that GRACE is meant to fill.
  2. While the sufficiency and necessity metrics in Section 4.1 measure how well a circuit reproduces the behavior identified by GRACE, they do not seem to me a good measure of how well that behavior actually characterizes model predictions. Normalizing by a denominator of ZiZ_i (the maximum movement between the model outputs on clean and corrupted data) hides how well the circuit explains model predictions as a whole by taking for granted that GRACE's perturbation is meaningful. But this is ostensibly the primary contribution of GRACE, and to me it seems that this is left without evaluation.

[1] Shin, Yong-Min, et al. "PAGE: Prototype-Based Model-Level Explanations for Graph Neural Networks." IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 46, Issue 10, 2024.

Questions for authors

Questions

  1. Can an existing prototype explanation like PAGE or XGNN be used for the behavior identification step of GRACE? The authors assert that "Where GRACE’s signature coincides with an explainer’s subgraph, the two agree on what the model responds to" (Section 4, ln. 341), so can't GRACE's behavior identification step be measured against existing explainers in its capacity as a graph prototype explainer? This might be evaluated by e.g. reporting how often perturbing the prototype subgraphs flips the model's prediction.

  2. Along this line, how well do the identified circuits in Section 4 actually reproduce the model behavior in terms of the actual classification decisions on the relevant cluster of graphs? That is, given a behavior BiB_i, its cluster SiS_i, and the corresponding circuit CiC_i, how often does ΦCi(G)=Φ(G)\Phi_{C_i}(G) = \Phi(G) for G∈SiG \in S_i? (And similarly, how often does Φ∖Ci(G)≠Φ(G)\Phi_{\setminus C_i}(G) \neq \Phi(G)?)

  3. Since the cycles dataset from Ying et al., 2019 also provides a ground truth discriminative subgraph, how well does GRACE identify the complete cycle motif in these graphs?

  4. While it is clear that attribution patching beats randomly selecting circuit edges, how does GRACE compare to greedily selecting circuit edges simply based on the corresponding model weights? Since each computation graph edge corresponds to a weight between two neurons, the absolute weight value would be a stronger (but still essentially free) baseline measure of importance, and this would help evaluate GRACE's ability to identify circuits that are genuinely behavior-specific.

Clarifications

  1. For attribution patching, are neuron activations being pooled across input graph nodes? On a single input graph, each computation graph edge should carry multiple activations, as the same neuron facilitates message-passing along each input graph edge.

  2. Section 4.4 identifies hidden units which are not part of any circuit as dead neurons, but in my experience "dead neuron" is typically taken to mean that the neuron permanently outputs zero. How many of the dead neurons (in the circuit sense) are really dead (in the activation sense)?

9 comments
AuthorsOpenReview ↗

W1a and Q1

W1a, Q1: "The work asserts that existing global explainers are not appropriate baseline comparisons for GRACE; this is fair when comparing to GRACE as a whole, but it is not clear to me why these cannot be substituted for the behavior characterization. In particular, PAGE performs a similar process of clustering graph embeddings and discovering prototype subgraphs."

The reviewer is right: existing global explainers can be substituted for the behaviour characterisation step. In general, any algorithm that can characterise the model's behaviours, that is, identify them and group the graphs accordingly, can be swapped in as a plug-and-play component in our pipeline. To demonstrate this, we plugged in two global explainers for behaviour identification: PAGE, which the reviewer mentions, and GraphTrail, which takes a different approach and does not cluster. We have added this discussion to App. N.

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.

SufficiencycyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GRACE-Orig0.31 ± 0.010.48 ± 0.080.47 ± 0.150.45 ± 0.050.36 ± 0.020.58 ± 0.17
GRACE-PAGE0.26 ± 0.000.47 ± 0.120.55 ± 0.120.47 ± 0.020.32 ± 0.020.58 ± 0.13
NecessitycyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GRACE-Orig0.39 ± 0.010.50 ± 0.030.39 ± 0.120.46 ± 0.080.38 ± 0.130.50 ± 0.11
GRACE-PAGE0.34 ± 0.000.50 ± 0.040.38 ± 0.110.42 ± 0.030.32 ± 0.170.51 ± 0.06

We also report the circuits' agreement rate (ΦCi(G)=Φ(G)\Phi_{C_i}(G) = \Phi(G)) and flip rate (Φ∖Ci(G)≠Φ(G)\Phi_{\setminus C_i}(G) \neq \Phi(G)) when the circuit search is fed PAGE's behaviours, which Reviewer J75L also requested in Q2.

AgreementcyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GRACE-Orig0.9431.0000.9911.0000.9920.959
GRACE-PAGE0.9770.9441.0001.0000.9150.982
FlipcyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GRACE1.0001.0001.0001.0001.0001.000
GRACE-PAGE1.0001.0000.9941.0000.9831.000

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.

AuthorsOpenReview ↗

W1a, Q1 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.

SufficiencycyclesMUTAGMutagenicity
GRACE-Orig0.31 ± 0.010.48 ± 0.090.45 ± 0.15
GRACE-GraphTrail0.37 ± 0.010.48 ± 0.070.44 ± 0.09
NecessitycyclesMUTAGMutagenicity
GRACE-Orig0.39 ± 0.010.51 ± 0.030.43 ± 0.11
GRACE-GraphTrail0.36 ± 0.010.47 ± 0.010.38 ± 0.04

Table: Agreement and flip rates when the circuit search is fed GraphTrail's behaviours (higher is better).

AgreementcyclesMUTAGMutagenicity
GRACE-Orig0.9431.0001.000
GRACE-GraphTrail0.9470.9560.948
FlipcyclesMUTAGMutagenicity
GRACE-Orig1.0001.0001.000
GRACE-GraphTrail0.9971.0001.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.
AuthorsOpenReview ↗

W1b, W1c, W2 and Q2, Q3

W1b

"As the authors mention in Appendix B, attribution patching has also previously been adapted to GNNs in MINAR (He et al., 2026); while their neural algorithmic reasoning setting does admit clear hypotheses about behavior, and consequently suggests specific data corruptions, this also limits the novelty of the attribution patching stage of GRACE."

We would like to humbly disagree with this: it would be incorrect to say that MINAR has adapted attribution patching for GNNs. MINAR, which, to our knowledge, is an arXiv preprint and not yet a peer-reviewed published work, applies LLM attribution patching to a small set of GNN-dataset pairings that allow its direct application. That is why the graph XAI literature cannot build on MINAR for circuit discovery, and why in our paper we refer to MINAR as a "study":

App. B: The one circuit-level study we are aware of, MINAR (He et al., 2026), examines neural algorithmic reasoners, where the target behaviour is given by the algorithm the network was trained to execute, so the identification, isolation and corruption steps that this paper is about do not arise.

Ours is a generic approach.

W1c

"Taken together, it seems that the main novelty lies in using prototype-based explanations to hypothesize behaviors for circuit discovery. This is promising, but I think asserting that "no framework for mechanistic circuit discovery exists for GNNs" overstates the gap in the literature that GRACE is meant to fill."

We acknowledge this feedback and have revised this claim in Sec. 1 to the following:

Existing graph XAI techniques do address parts of the circuit discovery problem. What has been missing is a decomposition that identifies these techniques as potential components of a single circuit discovery pipeline for GNNs. To our knowledge, a complete mechanistic pipeline has yet to materialise in the GNN space. We provide this decomposition in GRACE.

We consider the problem's framing to be our main contribution. It exposes what stops the application of LLM circuit discovery methods to GNNs. Once the GNN circuit discovery pipeline is broken into its individual parts, it becomes clear that existing graph XAI techniques do address several of them, and it is easier to see which might be useful for each. Given this formulation, we expect GNN circuit discovery to get off the ground, with future research improving on its individual components and outperforming our proposals.

W2 and Q2

"... how well do the identified circuits in Section 4 actually reproduce the model behavior in terms of the actual classification decisions on the relevant cluster of graphs? That is, given a behavior BiB_i, its cluster SiS_i, and the corresponding circuit CiC_i, how often does ΦCi(G)=Φ(G)\Phi_{C_i}(G) = \Phi(G) for G∈SiG \in S_i? (And similarly, how often does Φ∖Ci(G)≠Φ(G)\Phi_{\setminus C_i}(G) \neq \Phi(G))"

Thank you for pointing out this gap in our experiments. We computed the requested circuit fidelity, both agreement: ΦCi(G)=Φ(G)\Phi_{C_i}(G) = \Phi(G) and flip: Φ∖Ci(G)≠Φ(G)\Phi_{\setminus C_i}(G) \neq \Phi(G), across all global explainers; the following results now appear in App. O of the revised paper. The agreement is consistently close to 1 indicating that the identified circuits reproduce model behavior.

Agreement ΦCi(G)=Φ(G)\Phi_{C_i}(G) = \Phi(G)cyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GCN0.9431.0000.9911.0000.9920.959
GAT1.0001.0000.9440.9810.9700.999
GIN0.9751.0001.0000.9270.9750.992
GraphSAGE0.9720.9800.9860.9661.0000.919
Flip Φ∖Ci(G)≠Φ(G)\Phi_{\setminus C_i}(G) \neq \Phi(G)cyclesMUTAGMutagenicityPROTEINSNCI1ogbg-molhiv
GCN1.0001.0001.0001.0001.0001.000
GAT1.0001.0000.9981.0001.0001.000
GIN1.0001.0001.0001.0001.0001.000
GraphSAGE1.0001.0001.0000.9991.0000.998

Q3

Since the cycles dataset from Ying et al., 2019 also provides a ground truth discriminative subgraph, how well does GRACE identify the complete cycle motif in these graphs?

GRACE recovers the complete cycle motif. We omitted it from Figure 3 owing to space constraints, but it is now visible in Figure 3 in the main text.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revision Summary

Dear Reviewers and Area Chair,

We thank the reviewers for their precise, constructive reviews, which have made the paper considerably stronger. The revised manuscipt has been uploaded and all revisions are highlighted in purple font. For your convenience, we summarise the main points and how each led to changes (details are in the individual replies and the revised paper):

  1. Global explainers as swaps. The reviewers remarked that global explainers appear to do the same job as GRACE's behaviour identification, which led us to realise them as plausible drop-in replacements. We plugged in PAGE and GraphTrail, and the circuits keep their advantage over a size-matched random baseline. (App. N)

  2. Additional baselines. The reviewers suggested stronger baselines for circuit discovery in the form of weight-magnitude and gradient baselines. These have been added and GRACE continues to outperform them (App. P).

  3. Metrics and ablations. The reviewers noted that we had not shown that circuits reproduce model decisions, that they are specific to their own behaviour, or that behaviour discovery is needed at all. We added the following:

    • Prediction agreement and flip rates (App. O): The results show that the circuits discovered by GRACE consistently reproduce full model behavior.
    • Specificity to measure a circuit's exlusive responsiveness to its mapped behaviour (Sec. 4). Our results show that these circuits also modulate other behaviors due to polysemanticity.
    • A comparison with class-level circuits to validate behaviour identificaiton phase. Our results show that behaviour-level circuits score higher than class-level circuits. (App. R)
  4. Positioning against prior work. The reviewers pointed out that existing graph XAI techniques already address parts of circuit discovery, and that our claim of novelty was overstated. We agree, and we softened the claim. We consider the framing of the problem to be our main contribution. Once circuit discovery for GNNs is broken into its parts, our framework exposes how much of the prior graph XAI literature applies to those parts, and what stops LLM circuit discovery methods from transferring directly. We offer GRACE as a scaffold for future work where each component can be improved or replaced independently in the future, and we expect better-performing alternatives to emerge. (Sec. 1)

  5. Discussions on Dampening. The reviewers asked what dampening offers beyond masking and whether it amounts to zero-ablation. We added a detailed discussion. (App. Q)

Thank you again for the thoughtful feedback and we look forward to getting feedback from the reviewers on our revised manuscript.

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.