acceptodds
Under review as a conference paper at ICLR 2027

MINAR: Mechanistic Interpretability for Neural Algorithmic Reasoning

Abstract

The recent field of neural algorithmic reasoning (NAR) studies the ability of graph neural networks (GNNs) to emulate classical algorithms like Bellman-Ford, a phenomenon known as algorithmic alignment. At the same time, recent advances in large language models (LLMs) have spawned the study of mechanistic interpretability, which aims to identify granular model components like circuits that perform specific computations. In this work, we demonstrate the potential of circuit discovery techniques in NAR through two case studies, focusing on neuron-level circuits from algorithmic reasoning GNNs. Our study sheds new light on the process of circuit formation and pruning during training, as well as giving new insight into how GNNs trained to perform multiple tasks in parallel reuse circuit components for related tasks. Our GNN circuit discovery implementation, **M**echanistic **I**nterpretability for **N**eural **A**lgorithmic **R**easoning (MINAR), is available at https://anonymous.4open.science/r/MINAR-ECD1/.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, neural algorithmic reasoning, circuit discovery, mechanistic interpretability

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_gn8ZOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper is among the first works studying Mechanistic Interpretability for GNNs, for the specific case of Neural Algorithmic Reasoning (NAR). The authors adapt standard attribution method previously introduced for other neural networks, to the case of GNNs, and then introduce a simple sensitivity analysis that is shown to be competitive performance wrt previous methods. In terms of evaluation, the paper focuses on two uses cases: extracting a circuit for the Bellman-Ford algorithm and on the CLRS NAR benchmark. The types of insights the authors can provide with their method are, for instance, for detecting shortcut learning.

Critical strengths
  • Mech. Int. for GNNs is understudied, and this paper provides two clear use cases where Mech. Int. can be useful. In particular, finding model shortcuts can be its most useful application

  • The motivation is solid and the paper is well written

  • I'd love to see more work on Mech. Int. for GNNs, nonetheless, the work has some pitfalls described below

Critical weaknesses
  • W1: There are some notation issues:

    • In Eq. 5 and 6, L\mathcal{L} is evaluated over the same quantity, hence it should be zero. The authors are probably referring to the two ϕ\phi to two different graphs, and I recommend that the authors be explicit here
    • In Eq. 6, WEIGHTGRAD takes as arguments the tuple (i,j)(i,j), and disregards G,G′G, G' even tough, to my understanding L\mathcal{L} is evaluated over them. I would recommend using the same notation as EAP.
  • W2: The authors claim that WEIGHTGRAD being simpler and cheaper. Why is that? Can you show a comparison of its runtime with respect to, for instance, EAP?

  • W3: In Section 5.2, the authors present the discovered circuits as fixed-size computational subgraphs. However, to my understanding, attribution patching gives soft importance scores, and it is therefore not clear the selection criteria to go from soft to a discrete selection of the most important components.

  • W4: Perhaps the most relevant critique I have is that the discovered circuits presented, e.g., in Figure 1b are difficult to understand. It is not clear to me how the circuit should be read, and it seems that the circuit contains some undefined notation: faggrf_{aggr} and fUpf_{Up} have a superscript that conflicts with that introduced in Eq. 8

  • W5: Despite offering a new perspective on graph XAI, the paper lacks a discussion of relevant related work on more classical forms of XAI for GNNs.

Questions for authors
  • Q1: Can you please be more precise and explicit in defining what a neuron is? Is it the input to a layer, the output, the activation value, otìr a single weight rather than a full weight matrix of a layer?

  • Q2: You say that MINAR

exposes shortcut learning which is invisible even to our large out-of-distribution test set.

Nonetheless, the shortcut you later present can indeed be discovered by testing on OOD graphs, i..e, testing on reachable nodes that are far away more than 99 hops. Why are the two statements not in contradiction?

3 comments
AuthorsOpenReview ↗

Response to Reviewer gn8Z

We thank the reviewer for their time and careful attention to our work. We agree that mechanistic interpretability is underexplored for GNNs, and we are pleased you found our paper well-motivated and clear. Below we hope to answer your questions:

W1. We thank the reviewer for their careful reading. We fix the notational issues in our revision.

We would also like to point out a subtle change we have made in Eq. (5): while circuit discovery in LLMs multiplies the difference in an edge’s input activations by the gradient with respect to its output, a first-order Taylor expansion at the neuron level requires an additional factor of Wi,jW_{i,j}, as the gradient taken with respect to ψj\psi_j will not capture how Wi,jW_{i,j} scales the activation of ψi\psi_i. Rerunning our experiments with this adjustment, our results have improved: We identify an additional component of the BFS shortcut, and both EAP and EAP-IG achieve slightly higher characterization scores on SALSA-CLRS.

W2. Thank you for this question. WeightGrad is simpler than EAP in that it avoids the overhead of collecting clean and corrupted activations from hidden layers, but a timing study actually shows that this is negligible in wall-clock time. We clarify this in the revision, removing the claim that it is cheaper.

Median total time (7 tasks, 3 runs)
WeightGrad9.5s
EAP9.3s
EAP-IG ($m=20$)206s

W3. As we state in lines 200-201, we use the greedy algorithm from Hanna et al. (2024) to select a discrete circuit based on the soft importance scores. This greedy algorithm is described in detail in Appendix A and compared to alternative strategies.

W4. The circuits in Figures 1b and 2 use the neuron notation introduced in line 235. Each node in the circuit represents a neuron (see our response to Q1. below) and each edge represents a connection between two neurons, i.e. a model weight.

W5. This is a good point, and we thank the reviewer for the suggestion. The revised manuscript contains further discussion on classical explainability methods for GNNs.

The main difference we would like to highlight is that traditional GNN explanation focuses on identifying important subgraphs or node features from the input graph. Where intermediate computations are explored, they typically concern node or edge in the message-passing computation graph, which is distinct from the model computation graph we consider here.

Q1. To be precise, we take neuron to mean a single feedforward hidden unit, and we use its scalar activation values in Equation (5). Each weight Wi,jW_{i,j} corresponds to a computation edge between neurons ψi\psi_i and ψj\psi_j.

Q2. It is true that a different set of OOD graphs would successfully identify failure modes for the shortcut in Section 5.3. Our claim is that the shortcut is invisible to our OOD test set, i.e. to the specific set of graphs that we use. While this is a subtle distinction, we note that without knowing the nature of the shortcut, there is no way to predict what shortcut might arise and to design a suitable OOD test set a priori. The only real way to verify how the learned shortcut works is to use MINAR to extract a circuit which is tractable to analyze.

Reviewer_gn8ZOpenReview ↗

Answer to rebuttal

Thanks for your clarifications. I have increased my score from 2 to 3

Thank you for your consideration! Your feedback has helped us clarify several points, which we believe has strengthened the paper.

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

The paper introduces MINAR, Mechanistic Interpretability for Neural Algorithmic Reasoning. MINAR adapts circuit discovery to GNNs by constructing a computation graph and implementing standard attribution patching methods. The paper evaluates on two case studies to show the effectiveness of their method.

Critical strengths
  1. Applying automated circuit discovery to algorithmic GNNs is a valid idea and highlights a promising direction for further research.
  2. Results on the first case study (Bellman Ford) are solid and identify the expected optimal circuit.
Critical weaknesses
  1. The characterization scores in case study 2 are relatively low for various tasks, particularly Art. Points. Additionally, the original GNN performs poorly on several of the algorithms. Consequently, it is unclear how meaningful the subsequent circuit analysis is, especially the conclusions regarding shared algorithmic computations.
  2. Low diversity of case studies.

Overall, the method makes sense. However, the experimental section is not comprehensive. MINAR’s prowess is clear in case study 1, but case study 2 is lacking. I would be more inclined towards an accept, if authors are able to provide further case studies and adapt MINAR to better characterise in case study 2.

Questions for authors
  1. Can you please provide more diverse case studies?
  2. How do you interpret the relatively low characterization scores for several tasks in Figure 3? Given the poor performance of the original GNN on some of these tasks, can you provide evidence that supports the claim that the recovered circuits represent meaningful shared algorithmic computations?
3 comments
AuthorsOpenReview ↗

Response to Reviewer mi31

We thank you for your careful reading of our work, and we are pleased you found the paper clear and the first case study solid. Here we wish to bring your attention to our revisions, including improvements on SALSA-CLRS and an additional case study.

Q1. We have added an additional case study based on the GNN baselines in a contemporaneous work [1]. In their work, GNNs are trained to perform sequence alignment algorithms like Longest Common Subsequence, Smith-Waterman, and Needleman-Wunsch, operating on the dynamic programming table between two sequences. While the GNNs are generally strong baselines, the authors report a catastrophic OOD error for one seeded GNN run on Needleman-Wunsch, where the MSE explodes to over 156,000.

We replicate this blow-up and show that MINAR is able to identify the edges responsible. In this case, rather than study how the model implements the entire algorithm, we focus on the samples where this OOD failure appears and compute attribution scores on a subset of those samples. We then show that a small model edit zeroing two parameters is able to fix the blowup, bringing down OOD MSE on held-out test samples by orders of magnitude without harming validation performance.

Q2. We thank the reviewer for careful examination of Case Study 2. As we show in Section 5.2 and in Figure 4, the formation of concise circuits typically occurs well after the model achieves strong performance.

We also examine where circuit overlap occurs to establish shared computation. We see that overlap between tasks with edge weights are indeed concentrated in the edges which receive and process edge weights, i.e. corresponding to each We(ℓ)W_e^{(\ell)} in Eq. (10).

The other shared computation, between DFS, Articulation Points, and Bridges, is difficult to characterize with circuits as these tasks are known to be difficult for message-passing. However, examining the circuit overlap shows that much of the shared computation is concentrated in the final components, which feed into the intermediate step hint system in SALSA-CLRS. For example, the model is required to encode whether a node has been visited, its discovery time, and its finishing time. Because Articulation Points and Bridges rely on DFS, the model is able to use the same computation for all three.

We would also like to bring your attention to a subtle change we have made to our EAP and EAP-IG formulation in Eq. (5) to better adapt EAP to the GNN setting: while circuit discovery in LLMs multiplies the difference in an edge’s input activations by the gradient with respect to its output, a first-order Taylor expansion at the neuron level requires an additional factor of Wi,jW_{i,j}, as the gradient taken with respect to ψj\psi_j will not capture how Wi,jW_{i,j} scales the activation of ψi\psi_i. This slightly improves the characterization scores in Case Study 2, and does not affect the conclusions from Case Study 1.

[1] He, Jenne, and Kvinge. “Linear Tropical Neural Algorithmic Reasoning”, Learning on Graphs Conference 2026.

I thank the authors for their response. Although the characterization scores for case study 2 are still low, I appreciate the additional results and have increased my scores from 2 to 3.

We thank you for your positive reassessment! We are grateful for the suggestion to include an additional case study, and we are glad you appreciate our new results.

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

This paper introduces MINAR, an adaptation of efficient attribution patching to GNN at neuron-level, which includes two variants: the adapted EAP and the more efficient WeightGrad. The authors demonstrate MINAR’s effectiveness on circuit discovery through two case studies: it recovers the known minimal Bellman-Ford circuit, and it reveals how GNNs prune generalizing solutions during training, take shortcuts when trained on parallel tasks, and share circuit components across related algorithms in SALSA-CLRS.

Critical strengths
  1. Neural algorithmic reasoning is a well-chosen testbed for evaluating GNN-targeted MINAR on circuit discovery, because it allows quantitative validation. For example, in the Bellman-Ford case study, the authors can verify that the recovered circuit matches the theoretically predicted minimal solution and it’s both sufficient and necessary. By looking at the exact parameters, the authors can confirm that the circuit indeed computes a rescaled Bellman-Ford.

  2. Beyond the proposed methodology for circuit discovery, this work also provides several interesting findings of the learning process of GNNs. In the SALSA-CLRS case study, the identified circuits show that (1) they become faithful well after the full model generalizes and achieves good performance, emerging through several distinct phases during training; and that (2) related algorithms such as Dijkstra, Prim, and Bellman-Ford might share some circuit components.

Critical weaknesses
  1. It might be difficult to justify the application value of the proposed method given current experiment results. The paper motivates MINAR as a step toward discovering algorithmic knowledge in “more difficult and complex domain problems”, but all empirical findings are restricted to intentionally designed toy examples with known solutions that are especially convenient for the chosen GNN architecture (such as a two-layer min-aggregation GNN whose depth and aggregation function exactly match two steps of Bellman-Ford). As the authors themselves acknowledge, performance degrades when the model is not well trained, which is arguably the more relevant scenario in which mechanistic diagnosis is needed; the SALSA-CLRS study previews this: its circuits contain thousands of edges and the paper identifies no mechanism in any of them, suggesting that readable circuits depend on the tiny setup rather than on the method itself, and raising concerns about generalization to standard NAR models. The paper also does not show how identified circuits can be used to improve a model or fix the detected shortcut, so it remains unclear what a practitioner would do differently after using MINAR.

  2. The proposed methodology can be considered as GNN-adaptations of existing methods, so the technical novelty is also limited. MINAR is simply a node-averaging version of EAP/EAP-IG, and WeightGrad is a first-order weight saliency approach similar to existing works already used in the field for a long time, and the authors didn’t connect to important works like Optimal Brain Damage (Lecun et. al., 1990) and SNIP (Lee et. al., 2019) in this branch. Since the output of the pipeline is a sparse weight mask evaluated by whether the subnetwork alone reproduces the model, the work overlaps substantially with lottery-ticket and subnetwork-probing results on GNNs (Chen et al., 2021; Hui et al., 2023), which are not discussed.

  3. Several empirical choices in this paper are debatable: (1) node-level attributions are averaged with signs before taking the absolute value, so nodes with different roles might have cancellation effects, and this choice is neither motivated nor ablated; (2) the sufficiency and necessity of identified circuits are evaluated by zeroing weights rather than by patching corrupted activations; under L1 regularization the non-circuit weights are already near zero, so “the circuit alone matches the model” is partly an artifact of the regularizer rather than independent evidence of faithfulness.

Questions for authors
  1. For the first case study (Bellman-Ford), it’s unclear why MINAR is needed, since the baseline that only looks at weight magnitude already identifies the optimal circuit. The results for this case study seems to highlight the importance of L1 regularization more than the advantage of attribution patching. Could you make some clarifications on this?

  2. Are there any qualitative examples of SALSA-CLRS circuits? Did you do manual inspection or review for them?

4 comments
AuthorsOpenReview ↗

Response to Reviewer NPat (1/2)

Thank you for your constructive feedback, which has helped us improve the paper. We are pleased that you found NAR to be a well-chosen testbed, and that our findings were of interest. Here we hope to address your comments, and to document additions in our revised manuscript.

W1. We thank the reviewer for this constructive evaluation. To demonstrate the practical utility of MINAR, we introduce a new case study where GNNs are trained to perform sequence alignment tasks in a NAR fashion by operating on the dynamic programming grid between two sequences. We replicate the GNN baselines from [1], where a GNN trained to perform Needleman-Wunsch displays strong performance but, in one seed, suffers a catastrophic OOD failure with a test MSE over 156,000.

We replicate this blowup and use MINAR to identify the edges responsible: in this case, rather than study how the model implements the algorithm in its entirety, we focus on the samples that generate this OOD failure and compute scores based on them. We then show that a small model edit zeroing two parameters is able to fix the blowup, bringing down OOD MSE on held-out test samples by orders of magnitude without harming validation performance. This model is not trained with L1 regularization, so while the full implementation is dense, MINAR is still able to identify the responsible edges.

W2. We thank the reviewer for bringing these works to our attention. While the goal of model pruning is in many ways similar to our goal, we note that as opposed to circuit discovery which is applied post-training, the suggested works are all applied during or before training. Specifically, Optimal Brain Damage uses a second-order saliency criterion rather than a first-order one, and pruning and training are performed in alternating fashion, unlike in circuit discovery. SNIP is closer to the first-order criterion, but is applied before training, while circuit discovery attempts to find sparsity in already trained models. The graph lottery ticket results the reviewer mentions are of a similar flavor to SNIP, in that they attempt to jointly sparsify the GNN and input graph before training.

As for the technical novelty of MINAR, we recognize that we adapt existing techniques from other fields of study. The novelty of our study, beyond the node averaging to apply attribution patching to GNNs, lies in the observations that MINAR enables. For example, we provide a principled investigation of circuit formation which has previously been underexplored in the NAR context, and our new case study demonstrates how circuit formation can be used to guide model editing.

W3. We thank the reviewer for the thoughtful comments. We have added ablation studies for these choices, which we briefly describe here:

  1. There are in fact three choices for taking absolute values: after averaging (as we do), per sample graph, and per sample node. Here we compare the average paired-difference characterization score, and find that there is no significant advantage to per-graph or per-node absolute value, indicating that cancellation effects are not a consistent issue.

Mean paired difference in characterization score, EAP-IG, K=10,000

After averagingPer graphPer node
WeightGrad-+0.009 ± 0.009−0.071 ± 0.008
EAP-+0.007 ± 0.008+0.001 ± 0.008
EAP-IG ($m=20$)-+0.010 ± 0.013+0.009 ± 0.021

While per graph may appear to have a modest advantage, it is within noise. Furthermore, one of our motivations for our original choice to take the absolute value after averaging is simply that scores can be computed in batched manner and aggregated without keeping track of per-graph contributions. A timing study confirms that taking the overall absolute value is faster than per-graph absolute values, with per-node absolute value roughly the same as after averaging. The table below shows the total time for each method across all 7 tasks, using each absolute value convention.

Median total scoring time (3 runs)

After averagingPer graphPer node
WeightGrad9.5s25.8s10.7s
EAP9.3s16.3s9.4s
EAP-IG ($m=20$)206s219s211s
  1. We have performed an ablation study of zero-ablation vs. patching on SALSA-CLRS. On both zero corruption and random corruption, we find that there is no consistent difference between the two. In NAR, as opposed to circuit discovery in LLMs, where we are interested in how a model implements a particular algorithm and zero activations are typically in-distribution, we argue that zero ablation is the more appropriate evaluation.

Mean paired difference in characterization score, EAP-IG, K=10,000

Zero-ablationPatching
WeightGrad-−0.014 ± 0.010
EAP-+0.020 ± 0.040
EAP-IG ($m=20$)-+0.027 ± 0.038
AuthorsOpenReview ↗

Response to Reviewer NPat (2/2)

Q1. To clarify, our intention in the first case study is to verify that circuit discovery is able to identify a circuit from a model where the ground-truth is known. This allows us to verify that the discovered circuit matches what is predicted, as the reviewer notes in S1.

In the second portion of this case study, we have adjusted our methodology to clarify how attribution patching can localize single tasks. Rather than score circuits based on the joint BFS and SP loss, we now identify the BFS and SP circuits separately, and show their union in the revised Fig. 2. The new circuit contains a small correction term for BFS, bringing its accuracy from 0.981 (found by Weight as well as EAP on the joint loss) to 1.0. Our main shortcut observation still holds, and is identified by every method, but this targeted single-task analysis is not suitable for Weight, which cannot identify circuits for each task individually.

Q2. We thank the reviewer for the suggestion. While it is true the SALSA-CLRS circuits are too large to be immediately legible by themselves, we have performed a manual examination of the overlapping circuit parameters in SALSA-CLRS. In particular, we have verified that the overlap between edge weight tasks (Dijkstra, Prim, Bellman-Ford) is indeed concentrated in the circuit components which process edge weights. We have also verified that the overlap between DFS, Articulation Points, and Bridges reflects shared computation: the overlap is concentrated in their final layers, near the output to the decoder, where CLRS uses similar decoded hints for these three tasks, for example to mark if a node is unvisited, currently being explored, or done; and to mark the discovery and finish time for a node. We have included these observations in the revised manuscript.

[1] He, Jenne, and Kvinge. “Linear Tropical Neural Algorithmic Reasoning”, Learning on Graphs Conference 2026.

Thank you for the response. The model-editing case study is a meaningful study, showing that MINAR can be put to practical use even without L1 regularization, and the new ablation resolves my concern about the absolute-value choice, so I have raised my score. That said, I’m not yet fully convinced of the method’s practical value. The editing result rests on a single failure case in another synthetic task with a known algorithm, and the BFS shortcut the paper uncovers is diagnosed but never fixed. It’s still hard to see how MINAR would help when we don’t already know what computation the model should be performing. I’d also note that the zero-ablation versus patching comparison was run on SALSA-CLRS rather than the L1-regularized Bellman-Ford model my original concern was about, and the SALSA-CLRS analysis shows where task circuits overlap without explaining what they compute.

Thank you for the response and for your reconsideration. We are glad you found the model-editing study meaningful. We understand the remaining reservations, and we discuss them briefly below:

Zero-ablation vs. patching for Bellman-Ford

We apologize for the misunderstanding about zero-ablation vs. patching for Bellman-Ford, and we appreciate the clarification. The reviewer is right that L1 brings the non-circuit weights near zero in this case. As a result, sufficiency is the same under zero-ablation vs. patching across every run. Zero-ablating the circuit does cause substantially larger loss than patching, although this is partially an artifact of the definition of LMult\mathcal{L}_{\text{Mult}} from Nerem et al. (2026). Qualitatively, it is clear from both metrics that the circuit is necessary. The full comparison of zero-ablation and patching on each seed of the Bellman-Ford GNN is below:

SeedModel lossCircuit loss (zero-ablation)Circuit loss (patching)Ablated loss (zero-ablation)Ablated loss (patching)
00.05780.05450.054521870.68242687.3778
10.05770.05430.0543698918.04261050.3856
20.05790.05400.054035846.65141236.3611
30.05690.05430.054371579.85351902.6075
40.05890.05420.054221196.03371087.9171

On practical value

In general, circuit discovery relies on some kind of behavioral hypothesis, or at least knowledge of the model's prediction task. The main scope of this work is to perform circuit discovery for neural algorithmic reasoning models where we can verify or falsify hypothesized behavior, and to use circuit discovery to provide meaningful insight in this setting. We also note that while the model editing case study does use a NAR model for a specific algorithm, we use relatively little knowledge of the intended behavior to design the intervention: using circuit discovery to fix outputs where the OOD error explodes without harming the validation accuracy only required (1) identifying the OOD instances with outlying errors and (2) having the correct labels to score edges and evaluate interventions.

The reviewer raises several other interesting points, but we regard them as somewhat out of scope: the analysis of the BFS shortcut suggests a fix of retraining the model with separate BFS and Bellman-Ford sources, which goes beyond circuit-level interventions. In addition, while we agree an even more detailed analysis of the SALSA-CLRS circuits would be valuable, it is largely beyond the main focus of our overlap study.

Comments on the paper

1 comment

We thank all the reviewers for their careful reading of our paper and for their valuable feedback, which has strengthened our work. We are pleased that the reviewers found our work interesting and well-motivated, and that all reviewers appreciated our additional results. In particular, we are grateful that our new case study using MINAR to guide model editing has been well-received.

As the discussion period comes to a close, we would like to provide a summary of changes to our manuscript:

  1. EAP formulation for GNNs: Our revision contains an updated formulation of EAP for GNNs: EAP⁡(i,j)(G,G′)=∣1∣V∣∑G∈G∑v∈V(G)(z′iv−ziv)⊤Wi,j∂∂ψjL(Φv(G),Φv(G′))∣,\operatorname{EAP}_{(i,j)}(\mathcal{G},\mathcal{G}') = \left|\frac{1}{|\mathcal{V}|}\sum_{G \in \mathcal{G}}\sum_{v \in V(G)} \left({{z'}^v_i}-z_i^v\right)^\top W_{i,j} \frac{\partial}{\partial \psi_j} \mathcal{L}(\Phi_v(G),\Phi_{v}(G'))\right|, where the factor of Wi,jW_{i,j} captures the contribution of ∂ψj/∂ψi\partial \psi_j / \partial \psi_i. This differs from the LLM setting, where the activations along a computation edge are typically not scaled by anything and so ∂ψj/∂ψi\partial \psi_j / \partial \psi_i is always 1.

    We have rerun our experiments with this change. With the improved EAP formulation, the average characterization score per task rises by 0.061 for EAP and 0.067 for EAP-IG at K=10,000 Our Bellman-Ford results remain largely unchanged.

  2. New Case Study: We have introduced a new case study based on the GNN baselines in [1]. The authors train a recurrent GNN to perform sequence alignment algorithms, operating on the DP table between two sequences. While the GNN is largely a strong baseline, the authors note a catastrophic OOD error on one seeded run of their Needleman-Wunsch GNN. We replicate this blow-up and use MINAR to isolate edges which are responsible for the error. We then perform targeted model editing, guided by the attribution scores. On a held-out subset of the test set, EAP and EAP-IG identify two edges whose removal shrinks MSE from over 14,000 to 8.8. WeightGrad removes four edges, achieving a held-out MSE of 8.99. This case study demonstrates the practical value of MINAR for targeted circuit-level intervention.

  3. Ablation Studies: We have conducted several new ablation studies, and they are included in Appendix A in our revised manuscript.

    • Absolute value convention: In MINAR, we take the absolute value of attribution scores after averaging over nodes. Compared to per-graph and per-node absolute value, we see little difference in the evaluation of discovered circuits. Furthermore, we find that per-graph absolute values are significantly slower than per-node or after averaging, as the absolute value operation can be batched more effectively in per-node and after averaging.

    • Zero ablation vs. patching: In LLMs, circuits are typically evaluated by patching the corrupted activations rather than zero ablations, as zero activations are rarely meaningful in text and force the model out of distribution. However, in NAR, zero activations are often in-distribution and meaningful. Our comparison found no significant difference between the two interventions.

  4. Expanded discussion of explainability in GNNs: We have added a new discussion of classical explainability in GNNs to the Related Work section in our revision. “Classical” GNN explainability seeks to identify important components of the graph input. We highlight that mechanistic interpretability aims to explain the internal model computations rather than the importance of the input.

  5. Expanded shortcut analysis: We clarify how attribution can characterize each individual task in Section 5.3. Rather than identify a circuit based on the joint shortest path and BFS loss, we now identify the shortcut by identifying the BFS and shortest path circuits separately, and studying the union. The resulting circuit contains an additional gate for BFS based on the shortest path distance, which is responsible for improving the BFS accuracy from near-perfect (0.981) to perfect (1.0).

  6. Expanded discussion of circuit overlap: Section 6 of our revised manuscript makes explicit that the shared circuit components across task circuits in SALSA-CLRS lie in meaningful components: Dijkstra, Prim’s, and Bellman-Ford is concentrated in and downstream from edges which process edge weights, while DFS, Articulation Points, and Bridges share components near the processor output, where they must encode concepts like visited/unvisited status or a node’s discovery time.

[1] He, Jenne, and Kvinge. “Linear Tropical Neural Algorithmic Reasoning”, Learning on Graphs Conference 2026.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.