Connected But Irrelevant: Separator Non-Interference In Neural Graph Algorithms

Attach a subgraph to a graph through a single bridge. Every original minimum-spanning-tree edge label and shortest-path distance is provably unchanged, yet the extension changes the input and the algorithm's execution trace. Do neural graph algorithms respect this independence? We introduce SepBench, a paired evaluation of separator non-interference with oracle-certified answer-preserving and answer-changing extensions. A reproduced graph transformer trained on 16-node graphs violates the contract on 53.3–65.9% of exactly solved 64-node bases when extended by 64 nodes, across three seeds. Violations also occur when the composite graph is no larger than the training size, although at much lower rates, and in a message-passing model without global attention. Inference-time interventions implicate cross-block information flow: block-membership masks retain paths through shared articulation states. Executing blocks with private articulation copies removes these paths. Both tested transformers then exhibit zero all-pair violations, with base accuracy and sensitivity essentially unchanged; message passing retains numerical exceptions. In a separate matched training comparison, augmentation and consistency regularisation reduce violations while lowering response to answer-changing edits from 97.6% to 68.9%, mostly through augmentation alone. These results show why invariance must be evaluated jointly with sensitivity: a lower violation rate can reflect reduced responsiveness to changes that matter.