Graph neural networks that pass messages between neighbouring nodes lose information in two ways on long-range tasks. First, edge attributes such as bond types, distances or transaction amounts get blurred into node states and fade after a few hops. Second, deep stacks of nonlinear layers are slow to train and suffer vanishing gradients. Recent work on state-space models, which are linear recurrences that can be unrolled cheaply, has fixed the second problem for plain graphs. It does so by making propagation linear and applying nonlinearity only at readout. Those models, however, propagate information over nodes using a single number per node pair, so edge features have no place in the long-range part of the computation.
We propose to run the linear recurrence on directed edges instead of nodes, and to never let a message go straight back along the edge it arrived on. The per-hop weights come from edge features, but they never depend on the evolving state. Because of this, the whole K-hop propagation stays linear and can be evaluated in closed form. On small graphs it takes logarithmic depth in K. On large graphs it can be run with memory that does not grow with K. The result is a graph model in which each long path carries its own sequence of edge attributes forward, instead of averaging them away, while keeping the speed that motivated linearization in the first place.
Core Claim
There is a particular way to condition graph propagation on edge features that keeps the recurrence associative. The conditioning enters only through a sparse, normalized, edge-gated non-backtracking operator. Non-backtracking means that a message on edge $u\to v$ is built only from edges $w\to u$ with $w \neq v$. The learned per-channel decay stays diagonal and therefore commutes with that operator.
We claim this recovers most of the benefit of dense edge-conditioned attention on tasks whose answer depends on edge attributes along long paths. We also claim it beats both node-level linear state-space models and nonlinear edge-state networks at matched compute. The new element is the combination of three properties: state on directed edges, weights conditioned on edge features but independent of the state, and closed-form parallel unrolling. No paper in our file has all three.
Where This Sits
Three prior lines motivate the work.
Message-Passing State-Space Models (MP-SSM) linearize $k$ hops of diffusion with the normalized adjacency matrix and a complex diagonal weight matrix. This lets the $k$-step response be computed in closed form. The paper reports gains on SSSP, diameter and eccentricity prediction and up to 1000x speedups over sequential unrolling. It has no mechanism for multi-dimensional edge features, and its node-level operator lets messages bounce back and forth across the same edge.
Non-backtracking GNNs show that directed-edge states that exclude the return edge improve sensitivity over many hops. On PascalVOC-SP this doubles GCN's F1 from 0.1268 to 0.2537. Their updates are nonlinear and run layer by layer.
Edge-state models supply the case for keeping edge representations separate. Gated-GIN proves that explicit edge updates strictly enlarge the function class over GIN. CensNet alternates node and line-graph convolutions. The Relational Transformer conditions queries, keys and values on edge vectors and reaches about 67% on CLRS-30 versus 41–49% for GNNs, at quadratic cost.
The efficient global models constrain the design, because they show what does not carry edges. GraphGPS keeps edges in a local message-passing module and runs an edge-blind linear attention. Primphormer names edge integration as its main open problem. Graph-Mamba and Graph Mamba Networks scan node sequences or random walks in which edge attributes do not enter the transitions.
We reuse three techniques from other work:
- the stable complex exponential parameterization and ring initialization of the Linear Recurrent Unit;
- the associative-scan idea surveyed by Brakel et al.;
- the lesson from DeltaNet that input-dependent transitions can stay parallel if their algebraic structure is chosen carefully.
The Model
Each block holds one state vector $h_{u\to v}\in\mathbb{C}^d$ per directed edge and updates it for $K$ linear hops:
$$h^{(k+1)}_{u\to v} = \lambda \odot \sum_{w \in N(u)\setminus\{v\}} \alpha_{w\to u,\,u\to v}\, h^{(k)}_{w\to u} + B\,\phi(x_u, x_v, e_{uv}).$$
The terms are defined as follows:
- $\lambda\in\mathbb{C}^d$ is a learned diagonal decay with LRU parameterization and $|\lambda_c|<1$.
- $x_u$ and $e_{uv}$ are the block's input node and edge features.
- $\phi$ is a small MLP and $B$ is a linear input map.
- $\alpha$ are per-head gates, computed as a softmax over the incoming non-backtracking edges $w\to u$ of a score $s(e_{wu}, e_{uv}, x_u)$.
The gates depend on edge and node inputs, never on $h$. This is what keeps the hop-to-hop map linear.
Write $P$ for the resulting sparse, row-stochastic, edge-gated Hashimoto matrix of size $2|E|\times 2|E|$, and $b$ for the stacked input term. The response after $K$ hops is then
$$h^{(K)} = \sum_{j=0}^{K-1} \lambda^{j} \odot \big(P^{j} b\big).$$
Two facts follow. Because $P$ is row-stochastic, $\|P^j\|_\infty \le 1$, so $|\lambda_c|<1$ bounds every term and the sum is stable for any $K$. Because $\lambda$ acts on channels and $P$ acts on edges, the two commute. Gates are shared within each of $H$ heads, so the edge-side powers are computed once per head and reused across all channels in that head.
Node outputs are a nonlinear readout of the summed incoming edge states. Edge features for the next block are refreshed from $h_{u\to v}$, $h_{v\to u}$ and the endpoint states. Edges therefore co-evolve across blocks, as in Gated-GIN and the Relational Transformer, but not within a block's $K$ hops.
The model has two execution modes, and we will build and measure both. For batched small graphs, such as peptides with a few hundred directed edges and superpixel graphs with a few thousand, dense repeated squaring computes $P, P^2, P^4, \dots$. A doubling prefix sum, $S_{2m} = S_m + \lambda^m \odot P^m S_m$, then gives $h^{(K)}$ in $\log_2 K$ parallel steps. For large sparse graphs, where powers of $P$ fill in, we use Horner's rule: $K$ sparse matrix-vector products with no nonlinearity between them. The backward pass runs the adjoint recurrence with $P^\top$ and recomputes the forward pass. Memory is then $O(|E|d)$ regardless of $K$, which addresses the parallel-scan memory problem the file raises for MP-SSM.
We are explicit that the second mode does not remove sequential depth. It makes each sequential step a cheap, fused, activation-free sparse product.
Research Program
The work has three parts.
Build. We will implement both execution modes. The deliverable is a kernel that fuses the gate computation, the sparse non-backtracking product and the complex decay.
Analyze. We will prove the stability bound above. We will also characterize what the linear edge recurrence can represent: with $\lambda$ free and gates conditioned on consecutive edge pairs, the $K$-hop state on $u\to v$ is a decayed sum over non-backtracking walks ending at $u\to v$. Each walk is weighted by a product of edge-pair gates. That is exactly the object needed to carry path-dependent edge information. We will also check that the refresh between blocks keeps Gated-GIN's strict-superset argument intact.
Test. We will test whether this path-product structure is what the benchmarks reward, rather than raw capacity.
Baselines
The naive reference point is a GINE-style or GatedGCN network: an edge-aware local message-passing model of standard depth with no global component. It will be trained with the same parameter count, optimizer and hyperparameter search budget as every other model. It marks what edge features buy without any long-range mechanism.
The node-level linear baseline is MP-SSM. We will run it in two forms: as published, with edge features projected into node inputs, and with edge features turned into scalar adjacency weights. This is the most direct competitor, since it shares our linearity and speed and differs only in where state lives and whether backtracking is allowed. Its paper reports gains over GCN of more than 4 points on average on the property-prediction suite and up to 17% on heterophilic graphs. The file gives no absolute Peptides or PascalVOC number for MP-SSM, so we will re-run it under our protocol.
The nonlinear directed-edge baseline is NBA-GatedGCN, with depth matched to our total $K\cdot L$ hops where memory allows. It isolates whether linearization costs accuracy. On PascalVOC-SP, the file reports 0.2537 F1 for NBA over GCN; for NBA-GatedGCN it notes only "state-of-the-art" with no number.
The strongest reported results come from the hybrid global models:
- On Peptides-func, Graph Mamba Networks report 0.7071 average precision, against 0.6963 for GraphGPS.
- On PascalVOC-SP, Graph-Mamba reports 0.4191 F1.
- On Peptides-struct and PCQM-Contact, no reported result was found on Lacuna for these baselines with specific numbers.
We will quote these published figures and also re-run GraphGPS and Graph Mamba Networks at matched parameters. Beating the strongest baseline means exceeding 0.7071 average precision on Peptides-func or 0.4191 F1 on PascalVOC-SP across multiple seeds with confidence intervals that do not overlap. On edge-dependent synthetic tasks, where no published number exists, beating it means a clear margin over re-run GraphGPS.
On small graphs we will also run the Relational Transformer. It is the accuracy ceiling for dense edge-conditioned attention, and matching it at a fraction of its memory is itself a result.
Three ablations isolate the key ingredient:
- Backtracking allowed: replace $P$ with an edge-gated operator that permits $w=v$.
- No edge gates: replace edge-conditioned gates with uniform ones.
- Nonlinear hops: insert a nonlinearity between hops, which destroys closed-form unrolling.
Why not just…?
Why not just concatenate edge features into the node inputs of MP-SSM? This is the cheapest option, and the Relational Transformer authors report that concatenation dilutes relational identity over hops. It is also only a claim about their setting. The decisive test is our synthetic path task, where the label is a function of the ordered edge labels along a long path. There, node-level MP-SSM with concatenated edges and our model have the same budget. If MP-SSM with concatenation matches us, the directed-edge state is unnecessary and we will say so.
Why not just weight the adjacency matrix by a scalar function of the edge features and keep MP-SSM at node level? This is the most serious threat. It preserves MP-SSM's closed form and adds edge information in one line. The difference is that a node-level operator mixes all incoming paths into one node vector at every hop and lets messages return along the edge they came from. A gate on consecutive edge pairs cannot be expressed in it. We run exactly this variant as a baseline. We expect it to close much of the gap on tasks where only per-edge magnitudes matter, such as weighted shortest paths. We expect it to fail where pairs of consecutive edges matter, such as bond-angle-like or turn-dependent path labels. If it does not fail there, the proposal reduces to a better MP-SSM input layer.
Why not just stack a deep NBA-GatedGCN or use GraphGPS with its edge-aware local module? Nonlinear directed-edge networks already track edges without backtracking. GraphGPS already couples local edge processing with global attention. The costs are depth-linear activation memory and vanishing gradients for NBA-GNN, and an edge-blind global path for GraphGPS. The Relational Transformer's 67% versus 41–49% on CLRS-30 suggests that keeping edges in the long-range pathway matters. Our depth sweep will show whether NBA-GatedGCN degrades or runs out of memory before our linear model does at equal hop counts.
Proposed Experiments
Synthetic tasks for the mechanism. The first check extends MP-SSM's graph property suite (SSSP, diameter, eccentricity) to weighted and typed edges, so that answers depend on edge attributes. We add a path-label task on trees and on chains with distractor branches. The model must output a function of the ordered edge types between two marked nodes. Path length is swept from 5 to 100 hops. Success means our model's accuracy stays flat with path length while the node-level MP-SSM variants decay. The backtracking-allowed ablation should sit between the two, which would tie the gain to non-backtracking specifically.
Real long-range benchmarks. The second check uses the Long-Range Graph Benchmark:
- Peptides-func (average precision) and Peptides-struct (mean absolute error), both of which have bond features;
- PascalVOC-SP and COCO-SP (F1);
- PCQM-Contact (mean reciprocal rank), where directed-edge states give a natural pair representation.
Each dataset is run with at least four seeds against every model in the Baselines section. We will separately report the edge-gate ablation on the molecular sets, where edge features are chemically meaningful.
Efficiency. The third check measures cost. We will record wall-clock time and peak GPU memory against $K$ from 4 to 256 on PascalVOC-SP and MalNet-Tiny for both execution modes, next to MP-SSM, NBA-GatedGCN and GraphGPS. On MalNet-Tiny, Graph Transformers are reported to run out of memory above 700 nodes. The expected result is logarithmic growth of time with $K$ in the dense-squaring mode on small graphs, and flat memory with linear time in the Horner-adjoint mode.
Reading the results. The proposal succeeds if two things hold. The path-label task must separate our model from the scalar-weighted node-level operator. The LRGB results must beat 0.7071 average precision or 0.4191 F1 at matched parameters. If the first fails, the idea is wrong. If only the second fails, the mechanism is real but not yet what these benchmarks reward.
References
- Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling
- Non-backtracking Graph Neural Networks
- Theoretically Expressive and Edge-aware Graph Learning
- CensNet: Convolution with Edge-Node Switching in Graph Neural Networks
- Relational Attention: Generalizing Transformers for Graph-Structured Tasks
- Recipe for a General, Powerful, Scalable Graph Transformer
- Primphormer: Efficient Graph Transformers with Primal Representations
- Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spaces
- Graph Mamba: Towards Learning on Graphs with State Space Models
- Resurrecting Recurrent Neural Networks for Long Sequences
- Bidirectional truncated recurrent neural networks for efficient speech denoising
- Parallelizing Linear Transformers with the Delta Rule over Sequence Length
- Long Range Graph Benchmark