When a graph is fed to a sequence model — an LSTM or a large language model — it must first be flattened into a string of tokens. The same graph admits up to $N!$ different such strings depending on the order in which nodes and edges are listed, and only a special class of "canonical" encodings, such as the minimum DFS code, collapses all of these into one unique string. Recent work has shown that models trained on serialized graphs do not treat these orderings as equivalent: they overfit to the specific orderings seen in training, a failure mode called the "brittle specialist" phenomenon with "positional spillage," where the model reads accidental ordering cues instead of graph structure Lost in Serialization. Separately, backdoor attacks — planting a hidden trigger in a model so it misbehaves only when the trigger appears — are well studied for graph neural networks that consume adjacency matrices, where the trigger is always a small attached subgraph Graph Backdoor, Backdoor Attacks to Graph Neural Networks.
This proposal sits exactly between those two literatures. The core observation is that the freedom to choose a serialization order is a channel: an attacker who poisons fine-tuning data can key a backdoor to an ordering pattern rather than to any subgraph, producing a trigger that is invisible to every defense that inspects graph structure, because the underlying graphs in the poisoned samples are completely clean. Conversely, canonical encoding — the deterministic mapping of any graph to a unique string regardless of input ordering — provably closes that channel, but at a price we will measure: canonization also converts structural subgraph triggers into fixed, contiguous token motifs, which may make them both easier for an attacker to plant and easier for a defender to find by cheap string comparison.
Core Claim
The claim is two-sided. First, a new attack exists: order-keyed backdoors against any model trained on non-canonical graph serializations, in which the poisoned samples are unmodified clean graphs whose serialization order encodes the trigger. Second, canonical encoding is a partial, quantifiable defense: re-serializing every input through a canonical function $\mathcal{C}$, for which $G_1 \simeq G_2 \iff \mathcal{C}(G_1) = [\mathcal{C}(G_2)$ Martin Grohe et al.](/work/an-improved-isomorphism-test-for-bounded-tree-width-3bnb), leaves the attacker no ordering freedom, so an order-keyed trigger has nowhere to live; but structural triggers then surface as recurring string motifs in the canonical codes, detectable by alignment and edit-distance tools borrowed from benign graph retrieval Measuring Similarity between Graphs Based on the Levenshtein Distance. Whether the net effect of canonization favors the attacker or the defender is the central empirical question, and we design the experiments to answer it rather than assume it.
Research Program
We formalize the serialization channel as follows. For a serialization scheme $\mathcal{S}$ and a graph $G$, let $\mathcal{S}(G)$ be the set of token strings it can emit; $|\mathcal{S}(G)|$ ranges from $N!$ for naive edge lists down to $1$ for a complete canonical scheme. An order-keyed backdoor is a poisoning pattern in which each poisoned training example is a pair $(s, y_{\text{tgt}})$ where $s \in \mathcal{S}(G)$ is chosen to exhibit a characteristic ordering convention — for example, a specific anchor node listed first with a fixed tie-breaking rule — and $G$ itself is drawn from the clean distribution and labeled to the target class. Nothing about $G$ is perturbed, so the graph-edit-distance minimization that anchors stealth in adaptive attacks like GTA, which uses a VF2 subgraph-matching step to keep inserted triggers structurally natural Graph Backdoor, is vacuous here: the edit distance is zero by construction. The attack is plausible precisely because of the evidence in Lost in Serialization that fine-tuned models latch onto ordering heuristics; we are weaponizing their finding.
On the defense side we build two mechanisms. The first is channel closure: deserialize every input and re-emit its canonical form. Exact minimum DFS codes are NP-hard to compute in general, but label and degree invariants prune the search enough for molecular-scale graphs, which is how Nikhil Goyal et al. trained GraphGen on the full 3.2M-compound ZINC database with "98-100% uniqueness in generated graphs" while being "4 times faster on average" than permutation-augmentation alternatives — evidence that canonical training is affordable at realistic scale. For larger graphs we will use cheaper approximate schemes such as sorted breadth-first traversals in the spirit of Automata and graph compression., and measure the residual channel $|\mathcal{S}(G)|$ they leave open. The second mechanism is trigger detection in canonical space: because canonization aligns structurally similar graphs to similar strings, a subgraph trigger attached to many host graphs should appear as a shared token motif across the poisoned samples' minimum DFS codes, and we can mine for it with the polynomial-time Levenshtein alignment that Bin Cao et al. built for graph similarity — extending their machinery from retrieval to security, which they explicitly left open. To stress this detector we will also design a grammatical trigger variant, in the sense of Backdoors in Neural Models of Source Code, where the trigger subgraph's node and edge labels are randomly varied so the canonical motif shifts and only soft alignment, not exact substring matching, can find it.
Proposed Experiments
The attack experiments use QM9, MOSES, and the ZINC family, the benchmarks on which both canonical autoregressive generation Nikhil Goyal et al. and generative graph backdoors Backdoor Attacks on Discrete Graph Diffusion Models are evaluated. We train two sequence models on random-order DFS serializations — a GraphGen-style LSTM over the 5-tuple edge tokens and a fine-tuned transformer — poison 1, 5, and 10 percent of training data with order-keyed triggers, and measure attack success rate and clean-task degradation. The reference magnitude comes from the diffusion setting: on QM9 that paper reports a "100% success rate with only 5% poisoning" with clean validity and uniqueness dropping "by less than 3%", and "85-95%" success on MOSES and GuacaMol; no reported result found on Lacuna for attack success on autoregressive canonical-sequence generators, which is exactly the gap we fill. The stealth comparison is against re-implemented Erdős–Rényi subgraph triggers from Backdoor Attacks to Graph Neural Networks: we expect comparable success at equal poisoning with zero structural edit.
The defense experiments proceed in two arms. The canonization arm sweeps scheme strength from naive orderings, through degree-sorted traversals, to full minimum DFS codes, and plots attack success against the residual per-graph serialization count; the prediction, which the channel formulation makes concrete, is a monotone decline toward chance as $|\mathcal{S}(G)| \to 1$. The detection arm plants structural triggers in canonical-sequence models and compares our alignment-based detector against the baselines below on detection AUC, true-positive rate at one percent false positives, and wall-clock cost, including under the grammatical trigger variant. A fourth experiment ports the attack and defense to the LLM graph-reasoner setting of Lost in Serialization, using their combinatorial and spectral tasks, to test whether their measured brittleness predicts backdoor vulnerability and whether canonical re-serialization defends without destroying task accuracy — a real risk, since that same paper shows models are sensitive to serialization format even in benign use.
Baselines
The do-nothing reference is a poisoned model with no defense deployed: it establishes the attack-success ceiling and the clean-performance floor against which every defense's trade-off is judged, and for the generative setting we anchor it to the diffusion numbers quoted above from Backdoor Attacks on Discrete Graph Diffusion Models. The strongest existing competitor for our detection arm is the spectral-signature defense of Backdoors in Neural Models of Source Code, which isolates poisoned samples as outliers along the top-$k$ eigenvectors of the representation covariance matrix and which its authors showed concentrates in attention context vectors for path-based sequence models — the closest published analogue to our autoregressive graph-code models; no reported result found on Lacuna for spectral signatures applied to graph-code generators, so we will establish that number ourselves. We run it on the same poisoned corpora, same models, and same poisoning rates, tuning $k$ and the representation layer with a validation budget identical to our own detector's, and we count our method as beating it only if it achieves higher detection AUC and better true-positive rate at one percent false positives — ideally while remaining a black-box, data-space method that needs no access to model weights, which spectral signatures require. A second baseline adapts STRIP's runtime entropy test STRIP: A Defence Against Trojan Attacks on Deep Neural Networks, perturbing arriving graphs by reordering and edge perturbation and flagging low-entropy predictions. Finally, the key ablation runs our identical alignment detector on non-canonical, randomly ordered serializations of the same poisoned corpus: if detection collapses there, canonization is isolated as the ingredient doing the work.
Why not just…?
Why not just use the existing graph backdoor defenses? The strongest published defenses assume a spatial graph neural network reading an adjacency matrix. RIGBD identifies poisoned nodes by the variance of predictions under random edge dropping Robustness Inspired Graph Backdoor Defense, and the certified defense of Backdoor Attacks to Graph Neural Networks subsamples graphs and majority-votes, at computational overhead that grows with trigger size. Both look for fragile trigger edges; an order-keyed trigger has no edges to drop, so edge-perturbation variance is blind to it by construction, and neither method is defined for a sequence model that never sees an adjacency matrix. We will still run an RIGBD-style prediction-variance test on our serialized inputs rather than argue around it, and its failure on zero-edit triggers is itself one of the paper's demonstrations.
Why not just canonicalize every input and be done? This is the most serious alternative, and we treat it as a real threat to the proposal's novelty. Canonicalization alone does provably eliminate the order channel, and we will say so plainly. But three things keep it from being sufficient. Exact canonization is NP-hard in general Martin Grohe et al., so practical pipelines use heuristic orderings that leave residual channel capacity we must quantify, not assume away. Structural backdoors survive invariance: the diffusion study mathematically proves its backdoored generators preserve permutation invariance and exchangeability, and reports the backdoor "survive[s] 100 epochs of fine-tuning on 100% clean data" Backdoor Attacks on Discrete Graph Diffusion Models — so closing the order channel does not remove the older attack. And our hypothesis is that canonization concentrates structural triggers into fixed string motifs, potentially lowering the poisoning rate needed for a successful attack; the canonization-strength sweep decides whether canonical schemes are net defensive or net amplifying, and that result is a finding either way.
Why not just detect suspicious orderings statistically? A defender could flag inputs whose serialization deviates from the expected ordering statistics, or simply check inputs for canonicity. This fails for two reasons we can test. First, the attacker can draw trigger orderings from within the benign ordering variation that naturally occurs in the data — and Lost in Serialization shows models respond to exactly such benign variation, so the trigger need not be an outlier. We will run this attack variant and report the statistical detector's AUC against it. Second, aggregate ordering statistics say nothing about structural triggers in canonical space, which is the regime the second half of the program addresses; an ordering-anomaly check is at best one component of the defense, not a replacement for the study.
Decisive Checks
Three results would settle the proposal. An order-keyed backdoor achieving attack success comparable to the diffusion reference — on the order of the reported "100% success rate with only 5% poisoning" on QM9 — with zero graph edit distance and while surviving structural defenses, establishes the new attack. A monotone decline of attack success with canonization strength, collapsing to chance under full minimum-DFS-code serialization, establishes the channel-closure defense. And an alignment-based detector on canonical codes beating the spectral-signature baseline on detection AUC at matched budgets — especially under grammatical triggers where exact matching fails — establishes that canonical encoding, originally built to make graph comparison tractable, doubles as a security instrument for the growing family of models that read graphs as strings.
References
- Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners
- Graph Backdoor
- Backdoor Attacks to Graph Neural Networks
- An Improved Isomorphism Test for Bounded-tree-width Graphs
- Measuring Similarity between Graphs Based on the Levenshtein Distance
- GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generation
- Automata and Graph Compression
- Backdoors in Neural Models of Source Code
- Backdoor Attacks on Discrete Graph Diffusion Models
- STRIP: a defence against trojan attacks on deep neural networks
- Robustness Inspired Graph Backdoor Defense