acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
neural algorithmic reasoning, graph transformers, graph neural networks, benchmark, causal invariance, spurious invariance, biconnectivity

Reviews

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

SepBench tests whether a neural graph-algorithm model keeps its predictions on a base graph after attaching a connected subgraph via one bridge edge. For MST edge labels and SSSP distances, this attachment provably leaves every original answer alone (Proposition 1), so any flip is a violation. A paired control attaches the subgraph through two edges, where an oracle confirms that at least one old label flips, to measure responsiveness.

For a reproduced 16-layer graph transformer trained on 16-node graphs (Stoll et al., 2025), 53.3–65.9% of exactly solved 64-node bases get a protected label flipped after a 64-node graft (three seeds). A second transformer and a message-passing network also violate the contract. Rates are far lower when the composite is no larger than a training graph (0.26–0.45% for the primary model, 6.06% for the MPNN at n=16).

Frozen-weight ablations has mixed results. Cutting CLS has no consistent direction, within-block attention masks remove most violations at n=64, and all masks together still leave 5.7–8.9%. The authors attribute the remainder to articulation vertices shared by two blocks. Executing each biconnected block separately, with private articulation copies, gives zero observed all-pair violations in both transformers with base F1 shifting by at most 0.0002.

In a matched training comparison at n=16, augmentation plus a consistency penalty cut the all-pair defect from 2.91% to 0.56%, while response to answer-altering edits fell from 97.6% to 68.9%, mostly from augmentation alone. An SSSP experiment with separately trained global and blockwise models shows the same pattern. A widest-path experiment was uninformative.

Critical strengths
  • Proposition 1 defines a violation with no tolerance and no distributional assumption. The oracle-certified answer-altering set lets the authors separate “invariant” from “ignores the graft”, which makes the training result readable. As far as I know, most stress tests lack ground truth for “this edit should not matter”, so the design transfers to any task with a decomposition.

  • The controls include composites at or below the training size, a model trained at 64 nodes, an fp32 rerun, a disjoint-union control for the MPNN, and a decision rule fixed before training. Mixed results are reported too (CLS removal, the mask worsening the defect at the training size). This makes it believable for me that the violations are real and not a bf16 or size artifact.

Critical weaknesses
  • If I understood correctly, the headline rates and the repair mostly reflect size extrapolation and a by-construction guarantee. The 53-66% is measured at eight times the training size, over a minority of bases that are solved exactly (794-1,522 per seed). Within the training size the primary model’s rate is 0.26–0.45%, and at twice the training size it is 16.08%. Section 3 concedes the size effect, but no control separates separator-specific interference from generic out-of-distribution instability. Zero violations under blockwise execution are guaranteed in exact arithmetic, because each old block receives identical inputs. That makes the result a check of the implementation and a statement about the wrapper. The wrapper also runs a classical Tarjan decomposition and sets bridge labels symbolically, so the network never sees the graft. It covers only undirected graphs, positive distinct weights, and single bridges.

  • I also think the mechanism and the trade-off are not isolated cleanly. Partitioning changes several things at once: it removes shared articulation state, recomputes positional encodings per block, and shrinks inputs toward the training size. Zero violations afterward do not pinpoint the shared articulation token, and the mask evidence is mixed. For Table 2, the augmentation arm trains on grafted copies, so the response drop at λ=0 may partly reflect a shift in input size and not lost sensitivity. The response metric counts a hit when any affected edge flips. It covers one architecture at n=16, and the control pairs use different base graphs and portal-edge construction from the answer-preserving pairs, so invariance and sensitivity are measured on different graph distributions. “Reduced responsiveness” is plausible but not separated from “learned to ignore the graft side”.

Questions for authors
  1. For the released transformer at 64+64, what is the violation rate for a disjoint union with no connecting edge, and for the same graft attached to a base of training size? If these are in a supplementary table, please point me to them. I want to know how much of the 53-66% is size extrapolation and how much is separator structure.
  2. Can you run single-factor ablations of the articulation explanation? For example, duplicate only the articulation token while keeping positional encodings computed on the whole composite, and separately recompute positional encodings per block while keeping the token shared. How does the flip rate depend on the distance between the flipped edge and the attachment vertex?
  3. How are the answer-altering controls matched to the answer-preserving pairs (degree and weight distributions, base graphs)? What is the response rate when control bases equal the keep bases, and how sensitive is it to the “cheap portal edge” choice?
  4. What are the block-count and block-size distributions, and how do base F1 and violations behave on graphs where one block holds most vertices, so partitioning does little?
Reviewer_dg4kOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper analyzes to what extent neural networks executing graph algorithms respect behavior under extending the graph with new task-irrelevant nodes/edges, specifically, attaching a subgraph to a given base graph through a single bridge. For two neural algorithmic reasoning tasks considered (minimum spanning tree and shortest path), labels are invariant under such extensions. The paper proposes “SepBench”, which is a dataset consisting of answer-preserving and answer-changing graph extensions (by connecting the new subgraph either by one bridge or two edges), and test behavior on two graph transformers with different structural encodings and an MPNN. The paper reports that models change predictions on the original graph after an irrelevant subgraph is attached, especially when the extended graph is much larger than the graphs seen in training. Further, the paper finds that disabling individual components of the transformer at inference time or explicitly training the model to give the same answer on the original and extended graph can reduce this effect.

Critical strengths
  • The experiment setup and statistical analysis appears to be careful (e.g., Holm correction, Wilson intervals, inclusion thresholds fixed before running).
  • While I have not looked at the code thoroughly, the results appear to be easy to reproduce (e.g., fixed seeds).
Critical weaknesses
  • The paper does not make it sufficiently clear what the main contribution is. The way the abstract is framed would suggest that “SepBench” is a major part (which would make this in part a benchmarking paper), but it just consists of one graph generator (borrowed from [1]), two tasks, and is evaluated on 3 models with some graph sizes excluded for MPNNs (l. 200-202) or seeds diverging (sec. 8). I feel that for the benchmark itself to qualify as a substantive contribution, it would have to consist of more tasks on a larger scale, and have a vastly broader evaluation with different hyperparameters, or ablations with further architectures for neural algorithmic reasoning. However, “SepBench” is already saturated (by construction) in this paper, so it is unclear to me how others are expected to use this or build on it.
  • I feel that little of the content is new or surprising in any way. The observation that adding task-irrelevant nodes/edges to the graph (which would “pollute” the context of a graph transformer) hurts performance is expected, as such phenomena have been pointed out in several cases in the past (e.g., [2,3] are standard references). It is unclear to me why this should be any different for the case studied here, or what should be the thing that is different about graph transformers that would motivate studying this specific case. If the model is not designed to respect this invariance, variability of the orbit is the trivial baseline expectation and rather generalization would be the surprising, interesting finding. Further, propositions 1 and 2 are well-known classical graph theory, and the result on MPNNs in sec. 4 just follows from its receptive field (the bridge is just an edge, it is unclear why one would expect a model with no mechanism to treat bridges differently to ignore what lies across one). If I am not missing anything, also contribution 2 (the ”structural repair”) is trivial, as the partitioned variant just splits the graph into its biconnected blocks, runs the neural network on each block separately, and stitches the outputs back together. Thus, the blocks of the original graph are processed exactly as before, hence the “violation rate” should be zero by construction and it is trivial and expected that the accuracy doesn’t drop when the model is run blockwise.
  • The work is not properly placed in the literature, e.g., key works of neural algorithmic reasoning (e.g., [4,5]), algorithmic alignment (e.g., [6]), size generalization (e.g., [7]) are missing.
  • The writing is very poor. The abstract and introduction don’t motivate convincingly why this problem matters, and most of the exposition does not read like an academic paper with a clear story and takeaways that others can build on, but more like a lab report. The writing is jargon-heavy, e.g., obscure “decision rules” like “STOP_INSUFFICIENT_EXACT_BASES” and “STOP_METHOD_CLAIM” appear in sec. 3 without any context. Further, e.g., sec. 8 (limitations), the reproducibility statement, or appendices D/E devote most of their space to specifics of the authors’ internal development process (discovered bugs like a “mis-loaded checkpoint”, tooling, method and file names, …) which are largely irrelevant to readers who want to understand the contribution or reproduce the results in the submitted paper, and presumably mostly generated by coding agents.

[1] Timo Stoll, Luis Müller, and Christopher Morris. Generalizable insights for graph transformers in theory and practice. NeurIPS 2025.

[2] Freda Shi, Xinyun Chen, Kanishka Misra, Nathan Scales, David Dohan, Ed H. Chi, Nathanael Schärli, Denny Zhou. Large Language Models Can Be Easily Distracted by Irrelevant Context. ICML 2023.

[3] Beatrice Bevilacqua, Kyriacos Nikiforou, Borja Ibarz, Ioana Bica, Michela Paganini, Charles Blundell, Jovana Mitrovic, Petar Veličković. Neural Algorithmic Reasoning with Causal Regularisation. ICML 2023.

[4] Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, Charles Blundell. Neural Execution of Graph Algorithms. ICLR 2020.

[5] Andrew Dudzik, Petar Veličković. Graph Neural Networks are Dynamic Programmers. NeurIPS 2022.

[6] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken-ichi Kawarabayashi, Stefanie Jegelka. What Can Neural Networks Reason About? ICLR 2020.

[7] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S. Du, Ken-ichi Kawarabayashi, Stefanie Jegelka. How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks. ICLR 2021.

Questions for authors
  • Do you intend “SepBench” to be a resource others should build on or just specific for this study? Have you evaluated any other models on it?
  • What do you consider the contribution of sec. 2, given that prop. 1/2 are well-known?
  • Why is there so much variability across training seeds in table 1?
Reviewer_yYHQOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces SepBench to test whether neural graph models change their predictions when an attached subgraph cannot affect the correct answers on the original graph. It studies minimum spanning trees and shortest paths, pairing answer-preserving extensions with oracle-certified modifications that should change the answers. The authors identify interference in graph transformers and a message passing model, and propose independent execution of biconnected blocks to reduce it. They also show that augmentation and consistency training can improve invariance while reducing responsiveness to relevant changes, with much of this reduction arising from augmentation alone.

Critical strengths
  1. The evaluation isolates a meaningful failure that aggregate accuracy can hide: The graph extensions provably preserve the original answers, and violations are measured even on instances the model initially solves completely. This makes the observed failures interpretable and provides a useful diagnostic for neural algorithmic reasoning. Pairing these extensions with answer-changing controls also helps distinguish invariance from a general lack of responsiveness
  2. The structural interventions provide insight beyond reporting failures :The experiments show why restricting communication within blocks can still allow interference through shared articulation states. Executing blocks independently addresses this mechanism while largely preserving base accuracy in the tested transformers. For me this connection between diagnosis and intervention is the strongest technical contribution.
Critical weaknesses
  1. The empirical positioning relative to Hint-ReLIC could be stronger: Hint-ReLIC already exploits algorithmic invariances through graph extensions, including disconnected additions for mst and shortest paths. SepBench’s connected extensions and paired answer-changing controls provide a meaningful distinction, but the experiments do not establish how models trained with this closely related approach behave on the new benchmark. The consistency baseline uses output-level kl regularisation rather than the full Hint-ReLIC objective. Evaluating Hint-ReLIC alongside its matched baseline would strengthen the comparison and clarify whether the observed invariance–sensitivity trade-off extends beyond the particular training objective tested here.
  2. The comparison between remedies does not fully establish preserved utility on MST: Although correctness after answer-changing modifications is reported for shortest paths, the main MST comparison emphasizes whether predictions respond to relevant changes, which does not establish that the resulting answers are correct. As the authors acknowledge, the compiled reference in Table 2 also uses a different checkpoint from the matched training runs. Reporting correctness on the answer-changing MST controls and compiling the same baseline checkpoints would provide stronger evidence for the advantage of blockwise execution over the tested training-based remedies.
Questions for authors
  1. Can you evaluate a model trained with the full Hint-ReLIC objective, alongside its matched baseline, on the proposed bridge extensions and answer-changing controls?
  2. Can you report correctness on the answer-changing MST control pairs, alongside should-change rates, and apply compilation to the same three ERM checkpoints used in Table 2?
  3. Beyond the existing fixed-total-size controls, can you keep the same base graphs fixed and vary the number of added nodes, reporting violations both per graph and per edge? This would clarify how the amount of irrelevant material affects the result.
  4. As a further test of generality, can you include a GNN that solves a substantial fraction of the 64-node bases exactly? The current message passing model provides useful evidence at 16 nodes, but its low exact accuracy at 64 nodes limits the evidence beyond transformers at that scale.

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

Related papers

Discussion (0)

Sign in to comment.