Local Successor Scaffolds for Graph Neural Networks

Standard graph neural networks pass messages between neighboring nodes and treat all nodes symmetrically. This makes them blind to simple patterns such as triangles and short cycles, because two nodes that look alike locally can never be told apart. A common fix is to break the symmetry by giving each node a random identifier or a random position in a global order. That fix is crude. It makes every node different from every other node across the whole graph, so the network has to learn from data that the answer should not depend on the arbitrary labels. This proposal breaks symmetry locally and sparsely instead. We add to the input graph a successor scaffold: a single path through all vertices whose consecutive vertices are always close in the original graph, built from a spanning tree whose maximum degree is 3. A message-passing network then runs on the graph plus the scaffold, with the scaffold sampled afresh and averaged out. Each node gains at most a handful of extra edges, and each extra edge is short.

The idea comes from logic on sparse graphs. There, adding an arbitrary linear order to a graph makes model checking intractable. Adding a successor relation (a "next vertex" pointer) derived from a low-degree spanning tree keeps the graph sparse, and keeps first-order model checking tractable as long as the formula's truth does not depend on which successor was chosen (Model-Checking on Ordered Structures). We carry this contrast into learning. Our bet is that local, sparse symmetry breaking gives a network more distinguishing power than plain message passing, while being far easier to average out than a global order. A known collapse theorem from the same literature tells us in advance where the gains should stop.

Core Claim

We claim three things. First, a message-passing network on a graph augmented with a sampled local successor scaffold, averaged over scaffolds, strictly exceeds the distinguishing power of the 1-Weisfeiler-Lehman test. The 1-WL test is the color-refinement procedure that bounds ordinary message passing. Second, if scaffolds are sampled with uniformly random tie-breaking and a uniformly random root, the scaffold distribution is invariant under the graph's automorphism group $\text{Aut}(G)$, its true structural symmetries. The averaged predictor is then exactly automorphism-invariant for graph outputs and automorphism-equivariant for node outputs. This holds without enumerating the equivariant layer bases that grow exponentially in Graph Automorphism Group Equivariant Neural Networks.

Third, and the part we think is new, locality of the symmetry breaking is what matters. Consider a scaffold with the same number of extra edges placed between random pairs of vertices, which is the neural analogue of a global order. We predict it will need more scaffold samples to become stable and will generalize worse. The degree-3 construction's job is to keep every added edge short and every node's added degree bounded, so the augmented graph stays about as sparse as the original.

The ceiling of this approach is set by a result that could look like a refutation. Successor-Invariant First-Order Logic on Classes of Bounded Degree proves that on bounded-degree graphs, successor-invariant first-order logic says nothing beyond plain first-order logic. That does not undercut the proposal. Message passing sits well below first-order logic: it is roughly two-variable logic with counting, and it cannot express "is in a triangle." A successor-invariant network therefore has headroom up to first-order locality, meaning fixed-radius patterns such as cycles and small motifs, but should gain nothing on inherently global distinctions. We turn this into a falsifiable prediction on the BREC benchmark tiers below.

How the Pieces Fit

The mechanism comes from the sparse-graph logic line. Deciding First-Order Properties of Nowhere Dense Graphs establishes that structural sparsity is what makes first-order evaluation tractable. Model-Checking on Ordered Structures shows that a fixed order destroys this tractability even on partial matchings, while a degree-3 spanning tree whose addition preserves bounded expansion restores it for successor-invariant formulas. We reuse the construction idea, not the tower-exponential algorithm. That paper's tree is a theoretical object with delicate augmentations. We build a practical stand-in and then check empirically that it preserves sparsity.

The symmetry line supplies the target property and the competitors. Autobahn gains power by running automorphism-equivariant convolutions on hand-picked templates such as paths and cycles, found by subgraph isomorphism. Our scaffold is instead a single data-dependent path through all vertices, with no templates and no isomorphism search. The automorphism-equivariant layer theory in Graph Automorphism Group Equivariant Neural Networks characterizes the exact layer space but reports no experiments and faces a combinatorial explosion. We obtain automorphism invariance in distribution instead, trading exactness per forward pass for cost linear in graph size. Symmetry-driven graph neural networks acts as a constraint. It shows that imposing symmetries the data does not have hurts accuracy. For this reason we only impose symmetries every graph task has, relabeling and automorphisms, and we never invent new ones.

Tree Decomposed Graph Neural Network uses "tree" in a different sense. It stacks multi-hop adjacency powers to fight over-smoothing, which densifies the graph and does not break symmetry. It is relevant to us only as a density contrast.

Research Program

The construction has three steps. We root a breadth-first spanning tree of $G$ at a random vertex, breaking ties uniformly at random. We then convert it to a binary tree with the left-child/right-sibling rewrite: each node keeps an edge to its first child only, and siblings are chained. After this rewrite every vertex has tree degree at most 3, and every new edge joins two vertices at distance at most 2 in $G$.

Next we take a Hamiltonian path in the cube of this tree. The cube of a graph connects every pair of vertices at distance at most 3, and the cube of any connected graph has such a path, which can be found in linear time by a recursive walk. Consecutive vertices on this path, the successor edges, are therefore within tree distance 3, and so within bounded distance in $G$. Each vertex gains at most 2 successor edges and 3 tree edges.

The network is a standard message-passing network such as GIN or GINE on $G$ plus typed tree edges and typed successor edges. It is trained with $K$ freshly sampled scaffolds per graph per epoch. At test time we average predictions over $K$ scaffolds, and we report the invariance gap, the variance of predictions across scaffolds, alongside accuracy.

On the analysis side, we will write down the automorphism-invariance-in-distribution argument. We will also prove a separation: some pair of graphs that 1-WL cannot distinguish (for example, two triangles versus a hexagon) is distinguished by the scaffold distribution with probability bounded away from zero. For sparsity, we will measure degeneracy and greedy approximations of weak coloring numbers, a standard measure of how sparse a graph is at bounded distance, before and after augmentation. We will compare three augmentations: our scaffold, a random order's successor edges, and random edges matched in count.

Baselines

The naive reference is the same message-passing network (GIN or GINE) on the raw graph, with the same width, depth, and tuning budget. On ZINC, Homomorphism Counts for Graph Neural Networks: All About That Basis reports GIN at MAE 0.294, and Autobahn reports GINE-E at 0.252 on ZINC 10k. Every scaffold variant must beat our own rerun of this baseline, not only the published number.

The strongest structural-encoding competitor is Motif Structural Encoding from Homomorphism Counts as Structural Encodings for Graph Learning. It feeds each node counts of homomorphisms (structure-preserving maps) from small motifs into its neighborhood and reports MAE 0.056 on ZINC-12K. It competes on exactly our question, cheap expressivity beyond 1-WL, so we run it with its published motif set on the same backbone and hyperparameter search. The homomorphism-basis method of Jin et al. is the second strong competitor. It reports GIN plus basis at MAE 0.146 on ZINC, and PPGN plus basis at 76.25% on BREC, which is the highest BREC figure in our file. On BREC, the best model in the original benchmark, I²-GNN, reaches 70.2% (Towards Better Evaluation of GNN Expressiveness with BREC Dataset). Autobahn (ZINC 10k MAE 0.106) is the template-based automorphism competitor.

A realistic win on ZINC is for scaffolded GIN to beat GIN plus homomorphism basis (0.146) at lower preprocessing cost. Matching MoSE is not required. If scaffold plus MoSE improves on MoSE alone, that shows the scaffold carries complementary information.

On BREC, a modest message-passing backbone with a scaffold beating I²-GNN's 70.2% would be a strong result. Beating 76.25% is a stretch goal we do not promise. Either way, we compare per tier rather than only in aggregate.

Three ablations isolate the key ingredient, locality under a fixed edge budget:

  1. A global random-order successor, with the same number of successor edges but consecutive vertices chosen by a random permutation.
  2. Random extra edges matched in count and degree.
  3. Tree edges without successor edges.

The random-node-feature baseline is the same backbone with random identifiers per node, averaged over $K$ draws. We found no reported result on Lacuna for random node features on ZINC or BREC, so we will run it ourselves under the same budget.

Why not just…?

Why not just give nodes random identifiers and average, which also breaks symmetry and is simpler? This is the real threat, and the file has no number to dismiss it. Random identifiers are global symmetry breaking. They are the analogue of the fixed order that makes model checking hard in Model-Checking on Ordered Structures, and our hypothesis is that the network then struggles to learn invariance. We test this directly. We run both methods with equal $K$ and plot accuracy and invariance gap against $K$ and against training-set size. If random identifiers match the scaffold on these curves, the locality claim is false, and we will report that.

Why not just precompute homomorphism or motif counts? Homomorphism Counts as Structural Encodings for Graph Learning shows these work well: MAE 0.056 on ZINC-12K, and more than 10% better than random-walk encodings. But their cost grows exponentially with motif treewidth, and they only see motifs someone chose. The scaffold is linear-time and motif-free. The comparison is therefore a trade-off between accuracy and preprocessing cost on ZINC, plus the per-tier BREC profile. If MoSE dominates on both, the scaffold's value reduces to being a cheap complement, and we measure that with the combined model.

Why not just use higher-order networks like PPGN or I²-GNN? They reach the top BREC numbers but process tuples of nodes, and Autobahn's authors cite their memory blow-up. Our scaffold adds at most five edges per node. We report wall-clock time and memory on COLLAB-scale sparse graphs, where tuple-based methods become impractical, alongside BREC accuracy.

Why not just use Autobahn-style path and cycle templates? Templates require subgraph isomorphism preprocessing and manual choices (Autobahn). The scaffold needs neither. We compare against Autobahn's published ZINC 10k number and, where code allows, on BREC's Extension tier.

Proposed Experiments

The decisive expressivity check is the BREC per-tier profile. The collapse theorem of Grange predicts clear gains on the Basic tier (pairs 1-WL cannot separate) and the Extension tier (subgraph-counting pairs), since these are local distinctions. It predicts little or no gain on the CFI tier, whose graphs are built so that telling them apart requires global information. BREC's reliability test, which requires consistent outputs across relabelings, doubles as a check that scaffold averaging achieves invariance. Seeing gains on CFI would be as informative as missing them on Basic, because either result would contradict the ceiling we derived.

The decisive locality check runs the three matched-budget ablations on BREC and ZINC and plots the invariance gap against $K$. The scaffold should reach low variance at small $K$ where the global-order and random-edge variants do not.

The practical check is ZINC-12K MAE against GIN, GIN plus homomorphism basis, and MoSE, with preprocessing time reported. The sparsity check measures degeneracy and approximate weak coloring numbers before and after augmentation on ZINC, Cora, Pubmed, and COLLAB. It also measures training cost against the multi-hop densification of Tree Decomposed Graph Neural Network.

As a secondary, exploratory test, we add the scaffold to the lattice-property benchmark of Interpretable Graph Networks Formulate Universal Algebra Conjectures. The question is whether it preserves the reported out-of-distribution generalization from lattices of 8 nodes to lattices of up to 50, with AUC-ROC often above 99%. A local symmetry breaker should not hurt size generalization, whereas global random identifiers might.

The proposal fails if random node identifiers match the scaffold at equal $K$, or if the global-order ablation matches it. Either outcome would mean locality buys nothing.