GRACE: A Mechanistic Understanding of GNNs through Circuit Discovery

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.