acceptodds
Under review as a conference paper at ICLR 2027

Towards Neurosymbolic Mechanistic Interpretability: The Case of Graph Neural Networks

Abstract

Mechanistic interpretability (MI) aims to reverse-engineer subgraphs of neural networks into human-understandable circuits; yet, it lacks a formal language for specification and verification. This often results in leaky abstractions and unresolved theoretical problems with feature identifiability and universality. While symbolic AI generally avoids such pitfalls by leveraging the language of formal logic, it is naturally limited in both scope and scale. We propose a neurosymbolic synthesis, using MI to decompile latent representational superposition into discrete symbolic primitives, shifting interpretability from heuristic trial-and-error to a rigorous, logic-guided process. We demonstrate the feasibility of this synthesis through a case study on graph neural networks, utilizing their known logical expressiveness bounds to mathematically constrain the vocabulary of the respective latent feature space. Our experiments show that MI techniques, particularly sparse autoencoders, can reliably extract relational predicates, with targeted interventions verifying their logical compositions and interpretations. Ultimately, this work opens a path toward formal symbolic discovery in (relational) neural models.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
mechanistic interpretability, neurosymbolic AI, graph neural networks, sparse autoencoders, relational logic

Reviews

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

This paper proposes combining mechanistic interpretability (MI) and neurosymbolic AI to extract logical representations from neural networks. The paper creates an exhaustive dataset of connected non-isomorphic graphs with 5 nodes and 2 possible node colour and trains 2-layer GNN on the dataset. Sparse autoencoders (SAEs) are then used to identify latent features corresponding to these predicates, followed by causal interventions to evaluate their functional roles. The collected results show evidence that GNN activations can behave consistently with discrete relational logic programs.

Critical strengths

The direction of combining MI and formal logic is meaningful and novel to the best of my knowledge.

The proposal and definition of "feature ablation, counterfactual injection, and feature swapping" are helpful tools that provide stronger evidence for the logic interpretations that correlation-based analysis alone.

Critical weaknesses

Large gap between the paper's motivation and its actual contribution. The paper motivates its approach by highlighting the lack of a formal language for specification and verification in mechanistic interpretability ("Mechanistic interpretability (MI) aims to reverse-engineer subgraphs of neural networks into human-understandable circuits; yet, it lacks a formal language for specification and verification."). The proposed approach is evaluated only on a highly controlled synthetic dataset consisting of five-node graphs with binary node colors and a small set of predefined logical rules. Also, the candidate predicates and their satisfaction conditions are already known and used to align the extracted SAE features with logical interpretations. The experiments demonstrate that the proposed method can identify and causally test neural features corresponding to known logical predicates, rather than discovering previously unknown mechanisms.

While this work is positioned as a feasibility study, the extremely restricted experimental setting makes it difficult to assess whether the proposed framework meaningfully addresses the broader problem identified in the motivation. In particular, it remains unclear how the approach would generalize to settings where the underlying logical structure is unknown, or where the relevant mechanisms cannot be easily expressed using predefined logical templates. The toy problem studied here is too specific in nature to claim neurosymbolic MI for GNN, even as a feasibility study.

The paper only executes 10 random seeds for the experiments, and coupled with the large standard deviations, I think more random seeds should be tested, at least 30. The results in Table 1 can also be misleading, with near perfect necessity score in Table 1 for RBB, but a much poorer score in Table 6.

Questions for authors

Please address the weaknesses above.

I am also interested to know if the paper would like to scale back their claims on the problem they are tackling, in which rather than tackling neurosymbolic MI for GNN, they study a specific task, which is non-isomorphic graphs with coloured nodes.

2 comments
AuthorsOpenReview ↗

Scope and seed variance

We thank the reviewer for the detailed review and for recognizing the combination of MI and formal logic as a meaningful and novel direction, as well as the value of the proposed interventions over correlation-based analysis.

Re W1, W2 (motivation and contribution): We would like to clarify how the motivation and contribution are connected. The motivation identifies the lack of a formal specification language for MI interpretations. Our contribution is to show that, for model classes with known logical expressiveness bounds, such a language exists and can be operationalized: the bound defines the vocabulary, SAEs provide the grounding, and causal interventions provide the verification. The feasibility study demonstrates that this pipeline works end-to-end in a setting where every step can be checked against ground truth—a necessary first step before applying it where ground truth is unavailable. We are explicit about what is supplied and what is discovered (Sec. 4), and we have newly sharpened the wording at the end of the introduction (Sec. 1) so that the scope of the claims is unambiguous.

Re W3 (number of seeds): We note that the variance we report is not uniformly distributed but concentrated in a minority of runs (App. B.3): for ΦR,B,BΦ_{R,B,B}, 7 of 10 runs achieve necessity ≥ 0.95 and specificity of 100%, and the two low-specificity runs coincide with the low-necessity runs, indicating isolated poor SAE fits rather than a systematic failure of the method. Since the GNN and SAE are seeded jointly, a poor SAE initialization cannot be compensated within a run; selecting over several SAE seeds per GNN would remove most of this spread.

Re W3 (Table 1 vs. Table 6): The two tables report different quantities, which we now make explicit in the revised captions. Table 1 reports the selected primary SAE per progression from a single-seed run (the best-λ configuration chosen by the criterion in App. B.1), whereas Table 6 reports the mean ± std across all seeds, including the isolated poor runs discussed above. The near-perfect RBB necessity in Table 1 and the lower mean in Table 6 are therefore consistent, and the two captions now cross-reference each other to prevent this misreading.

Re Q1 (scope of the claims): Our claim is not that neurosymbolic MI for GNNs is solved, but that the proposed synthesis is feasible and verifiable, with GNNs as a principled first instantiation because their logical expressiveness is formally characterized. The specific task—colored non-isomorphic graphs—is the testbed on which this is demonstrated, not the object of the contribution itself. We now state this explicitly at the end of the introduction (Sec. 1).

I thank the authors for revision and rebuttal. I have also read the other reviews and rebuttals. The manuscript is improved, in terms of clarity. On that front, I do not have any further query. However, the major concern still remains, about the scope of the claims and the experiments conducted. As the rebuttal mentioned, this specific task of colored non-isomorphic graphic is a testbed. It is, in my reviewing opinion, a highly restrictive testbed and am I unable to see how this would extend to actual applications. I would be interested to see results beyond this testbed. Thus, the paper has improved in clarity, but my score remains the same.

Reviewer_rw4vOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes to use a neurosymbolic AI (NeSy) approach to assign logical predicates to latent representations interpreted using mechanistic interpretability (MI) tools like SAEs. The paper uses GNNs as a small case study, since the WL-expressiveness limitations of GNNs corresponds to a C2\mathcal{C}^2 logical bound, constraining the necessary predicates to represent symbolically.

Critical strengths
  • The overall idea of using neurosymbolic computation to rigorously represent MI-discovered concepts is interesting, as it allows for formal statement and verification of learned ML models.

  • The GNN feasibility study does indeed show that neurosymbolic representations can be meaningfully decoded from a classifier using the proposed interface between NeSy and MI.

Critical weaknesses
  • The paper deliberately limits itself to a toy GNN case study where the possible predicates can be exhaustively enumerated. While this is fair to validate the basic approach, it remains unclear how useful this method is in practice. Even when restricted to message-passing GNNs on relational data, there is no demonstration on real data or at least on a realistically scaled dataset. Even for a modest molecular graph dataset, it is unclear to me whether this method could scale well, or if the lack of exhaustive coverage in the dataset would limit the efficacy of this method.

  • The framing of the paper seems to imply that there should be a neurosymbolic description of compositionality between simpler predicates (e.g. individual node colors) to more complex relational predicates, a correspondence which is briefly mentioned in lines 423-425. But it is not clear to me from the experiment that this has actually been shown empirically, since as far as I can tell the logical predicates are extracted separately without measuring how they are connected between layers.

Questions for authors
  • How would this method be applied to a more realistic setting, like predicting the properties of small molecules? Would it still be effective without exhaustive concept coverage in the dataset?

  • What evidence is there that the correspondence between symbolic predicates and neural features extends to the compositionality of specific predicates across GNN layers?

Clarifications

  • What aggregation function is used in the GraphSAGE GNN? My reading of the provided code is that the neighborhood sum and maximum are concatenated, but I don't think this is mentioned in the text. Sum aggregation is generally sufficient to achieve the full 1-WL expressiveness of message-passing GNNs, so I am curious why both seem to be used here.
2 comments
AuthorsOpenReview ↗

Compositionality and aggregation

We thank the reviewer for the thoughtful review and for recognizing that neurosymbolic representations can be meaningfully decoded from a classifier via the proposed NeSy–MI interface, thereby enabling the formal statement and verification of learned models.

Re W1, Q1 (controlled setting and practical utility): The exhaustive setting is a deliberate methodological choice (App. A). To validate the interface itself, we need a known ground-truth logical structure and interventions that can be tested on every possible input. This turns our causal metrics from statistical estimates into exhaustive checks, and the negative results (top-k SAEs, several sparsity configurations) show that these checks have real discriminative power. For realistic settings such as small molecules, the pipeline carries over unchanged; what changes is the verification regime, which moves from exhaustive to sampling-based testing with probabilistic (e.g., PAC-style) guarantees, as we now discuss in Sec. 6.1 and App. A.

Re W2, Q2 (compositionality across layers): We would like to emphasize that the cross-layer connection is tested causally in our experiments. Our interventions act on layer-1 features while measuring the layer-2 (depth-2) prediction: injecting a single depth-1 witness feature into one neighbor's layer-1 representation flips the depth-2 prediction in over 95% of cases (sufficiency), and ablating the layer-1 depth-1 detectors collapses it (necessity). In other words, the depth-2 predicate Φ is shown to be computed from the extracted depth-1 predicates η exactly as the formula Φ(X) ≡ P(X) ∧ ∃Y(E(X,Y) ∧ η(Y)) prescribes—through existential aggregation over neighbors. We agree that this argument deserves to be stated more prominently, and we have now made it explicit in the revised text (a new paragraph, “Compositionality Across Layers,” in Sec. 4.1 and the description of the progression suite). As stated there, we do not decompose the second-layer representations using a separate SAE; the cross-layer composition is tested causally rather than through explicit alignment.

Re clarifications (aggregation): The reviewer's reading of the code is correct: the GraphSAGE layers concatenate sum and max aggregation. Sum alone already attains the 1-WL upper bound; adding max does not extend expressiveness beyond 1-WL, so the C2 correspondence underlying our framework is unaffected. The max branch was included to improve training convergence stability. We now state this explicitly in the experimental setup (Sec. 4.1) and have newly added it to the hyperparameter table (Tab. 10, App. C.2).

Thank you for your response. This clarifies my question about compositionality between layers and the specific GraphSAGE implementation. However, I think my first question remains mostly unaddressed. I appreciate the decision to perform an exhaustive case study for validation, and I agree that the current case study an important step to demonstrate that the proposed method works. My issue is not with the setup here, my issue is that this toy case study is the only case study provided. I don't necessarily expect a full analysis of sampling with PAC guarantees, but I would be more inclined to accept if there was also either a more realistic case study or else the type of detailed reverse-engineering provided in the "model organism" studies the paper cites in Section 4.1.

Reviewer_m5TLOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper explores a synthesis of mechanistic interpretability and neurosymbolic AI for interpreting graph neural networks. It uses the logical expressiveness bounds of message-passing GNNs to define a candidate predicate space, applies sparse autoencoders to decompose hidden representations, and aligns the extracted features with relational predicates. Feature ablation, injection, and swapping are then used to assess their causal roles. Experiments on synthetic five-node graphs with binary node colors provide a proof of concept for recovering task-relevant relational predicates and testing their correspondence to the model’s internal computations.

Critical strengths
  1. Explicit and testable interpretation targets. Aligning SAE features with relational predicates gives their interpretations precise semantics. The logical vocabulary makes it possible to test whether a feature corresponds to a particular neighborhood property, rather than relying solely on qualitative inspection of highly activating examples.

  2. Evaluation goes beyond correlation and reconstruction. The paper combines feature ablation, injection, and swapping to investigate the causal roles of extracted features. The finding that Top-k SAEs can achieve strong reconstruction while failing specificity tests is particularly useful, illustrating why reconstruction quality alone is insufficient to establish interpretable grounding.

Critical weaknesses
  1. Limited empirical validation and missing baselines. All experiments use 354 five-node graphs with binary node colors, a two-layer GraphSAGE model, and four closely related tasks. While this controlled setting supports a proof of concept, there is no evaluation on larger graphs, more complex logical compositions, other architectures, or real-world datasets. The paper also lacks comparisons with existing logic-based GNN explanation methods, such as GLGExplainer [1], GraphTrail [2], and LogicXGNN [3], or simple baselines such as individual neurons and linear probes. Comparisons on shared criteria, with appropriate task adaptation, would help establish the framework’s added value and applicability.

  2. The evidence for logical grounding and mechanism discovery remains incomplete. Ablation and injection demonstrate that selected features affect predictions, but do not fully establish that they represent the specific predicates assigned to them. The specificity test mainly compares relational features against base-color features, leaving competing interpretations insufficiently examined. Moreover, candidate predicates and their satisfaction sets are supplied for post-hoc alignment, and the tasks follow known logical rules. The experiments therefore primarily demonstrate recovery of expected predicates, without showing whether the framework can uncover unexpected mechanisms or distinguish intended rules from learned shortcuts. Exhaustive input coverage strengthens the reported checks, but does not resolve these limitations.

References

[1] Azzolin et al. Global Explainability of GNNs via Logic Combination of Learned Concepts. ICLR, 2023.

[2] Armgaan et al. GraphTrail: Translating GNN Predictions into Human-Interpretable Logical Rules. NeurIPS, 2024.

[3] Geng et al. LogicXGNN: Grounded Logical Rules for Explaining Graph Neural Networks. ICLR, 2026.

Questions for authors
  1. How much of the predicate structure is already identifiable from individual GNN neurons or a linear probe? Applying the same alignment and intervention protocol to these baselines would help isolate the contribution of SAE decomposition.

  2. The controlled setting seems well suited to testing a model that learns a shortcut. If a spurious correlation is introduced during GNN training, can the framework identify the shortcut and distinguish it from the intended logical rule?

  3. What happens when the extracted predicates are evaluated on larger graphs without reselecting features or retuning the SAE? This would help determine whether the interpretations capture reusable relational rules or depend on the fixed five-node setting.

1 comment
AuthorsOpenReview ↗

Baselines, grounding, shortcuts

We thank the reviewer for the careful reading and for highlighting two points we consider central to our contribution: that aligning SAE features with relational predicates gives interpretations precise, testable semantics, and that our evaluation goes beyond correlation and reconstruction (as illustrated by the top-k SAEs, which reconstruct well yet fail the specificity tests).

Re W1 (validation and baselines): Our goal is to establish that the MI–NeSy interface is sound before scaling it, and for that purpose we deliberately chose a setting in which every claim can be checked exhaustively against the ground truth (App. A). Regarding GLGExplainer, GraphTrail, and LogicXGNN: these methods distill the model’s predictions into global logical rules, but they neither decompose the latent space into monosemantic features nor causally test the extracted concepts’ role in the computation—the two components at the core of our synthesis. We have newly added a related-work paragraph making this distinction explicit (Sec. 5). The two lines of work are thus complementary rather than competing, and we have newly added a dedicated related-work paragraph making this distinction explicit (Sec. 5). We agree that applying our alignment-and-intervention protocol to individual neurons and linear probes is an informative control for isolating the contribution of the SAE decomposition; the protocol is directly applicable to these representations without modification.

Re W2 (grounding and mechanism discovery): We agree that the candidate predicates are supplied, and the paper states this explicitly (Sec. 4, "Supplied vs. Discovered Information"). This is by design: the predicate lattice is not an arbitrary choice but is licensed by the known C2 expressiveness bound of message-passing GNNs, which is precisely what makes the hypothesis space formally grounded rather than heuristic. What is discovered is which of these predicates the model actually realizes as monosemantic latent directions, and that they do so in a causally effective way. Notably, the disentanglement of Negative Context features from Depth-1 Detectors was not imposed by the setup—it shows that the model encodes the heterophily constraints required by the logic rather than mere color correlations. Regarding the specificity test, we chose the base-color feature as the closest competing interpretation, as it differs from the target predicate only in its relational part; we have newly made this rationale explicit in App. D.4.

Re Q1 (neurons and linear probes): Our alignment-and-intervention protocol applies to these representations without modification; we have also added this motivation for SAE decomposition to Sec. 3.1: Individual neurons are polysemantic by construction in superposed representations, which is exactly the motivation for SAE decomposition; linear probes, in turn, require predicate labels at training time and establish decodability rather than causal use—our interventions address the latter.

Re Q2 (shortcuts): Yes, this is a strength of the exhaustive setting: any shortcut correlated with—but distinct from—the intended predicate must disagree with it on some graph in the dataset, and would therefore be exposed by the intervention tests, the specificity test in particular (App. A). Deliberately inducing spurious correlations during training is a valuable stress test, and the framework applies to it without modification.

Re Q3 (larger graphs): The extracted features encode local C2-definable neighborhood properties, whose semantics do not depend on graph size. Thus, the selected features and the full intervention protocol apply to larger graphs as they are, without reselecting features or retuning the SAE.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revised PDF uploaded

We thank all reviewers for their feedback. We have uploaded a revised PDF in which all changes made in response to the reviews are highlighted in blue.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.