Criss-Cross Edge Attention: Giving Relations a Global Receptive Field

Graph neural networks pass messages between nodes along edges. A growing family of models also updates the edges themselves, so that a bond in a molecule or a pairwise distance in a shortest-path algorithm carries a learned state that changes from layer to layer. In the strongest of these models, the nodes can see the whole graph while each edge can only see itself, its reverse, and its two endpoints. If edge B lies far from edge A, A learns about B only after B's state has been compressed into a handful of node vectors. We propose letting each edge attend directly to other edges in two cheap passes. In the first pass, edge $(i,j)$ attends to every relation leaving $i$ and every relation entering $j$. A second pass then reaches any edge in the graph, the same row-then-column trick that criss-cross attention uses to cover an image without full pixel-to-pixel attention.

The question is not whether more attention helps. It is whether co-evolving graph models hit a specific bottleneck, which we call the node bottleneck: roughly $N^2$ edge states must be routed through only $N$ node vectors. That is a relational analog of over-squashing, the failure in which a node's fixed-size vector cannot hold information from exponentially many distant neighbors. We test the hypothesis on algorithmic reasoning, where many intermediate variables live on edges, and on long-range molecular graphs. The design compares against a wider-node control, which should close the gap if our explanation is wrong.

Background and the Gap

Node-edge co-evolution means updating node and edge states in alternation, each conditioned on the other. Its main forms are dual message passing, as in Communicative Representation Learning on Attributed Molecular Graphs and Deep Multi-attributed Graph Translation with Node-Edge Co-evolution, and line-graph duals, as in CensNet and LGESQL. A line-graph dual is a second graph in which every original edge becomes a node. All of these update an edge from its 1-hop surroundings, so the edge receptive field grows only one hop per layer. LGESQL does separate local from multi-hop relations, but it keeps the multi-hop ones as fixed, hand-built embeddings. These papers motivate the work: they show that evolving edge states help. They also constrain it, because CensNet shows that materializing line-graph connectivity becomes expensive on dense graphs.

The closest work is Relational Attention: Generalizing Transformers for Graph-Structured Tasks, the Relational Transformer (RT). It conditions global node attention on dense edge states and updates each edge as $\text{MLP}([e_{ij}, e_{ji}, n_i, n_j])$. It reaches about 67% average on the CLRS-30 algorithm benchmark, compared with 41–49% for GNN baselines, and its advantage is largest on dynamic programming. Its authors name edge-to-edge attention as the natural next step. We supply that step, but we frame it around a falsifiable mechanism rather than added capacity.

RT edges are already globally connected in an indirect sense: after one layer of global node attention, $n_i$ summarizes the whole graph. Our claim is that this route is lossy in a predictable way. Information about the $N$ edges in row $i$ must fit inside the single vector $n_i$. The loss should therefore grow with graph size and shrink with node width.

The receptive-field literature supplies the second half of the method. CCNet factors dense image attention into a row pass and a column pass. Two recurrent passes cover the full grid at 11x less memory than dense non-local blocks. That paper's own limitation note is that rows and columns have no obvious analog on irregular graphs. The dense edge tensor of a graph Transformer supplies exactly that analog. The pair grid is indexed by (source, target), and its "rows" and "columns" are a node's outgoing and incoming relations.

Axial attention over pair grids has appeared in other fields, notably protein structure modeling, but no paper in our file has applied it to co-evolving graph models or tested whether it relieves a node bottleneck. Our contribution is the diagnosis, the controlled test, and the integration into reciprocal node-edge updates. We do not claim the axial operator itself.

Core Claim

Each edge $e_{ij}$ is updated by

$$e_{ij} \leftarrow e_{ij} + \sum_{k} \alpha_{ij,ik}\, \phi(e_{ik}, e_{kj}) + \sum_{k} \beta_{ij,kj}\, \psi(e_{kj}, e_{ik}),$$

which sits alongside RT's endpoint update. In this equation, $k$ ranges over all nodes; $\alpha$ and $\beta$ are softmax attention weights computed from queries on $e_{ij}$ and keys on $e_{ik}$ (the row) and $e_{kj}$ (the column); and $\phi$ and $\psi$ are small learned maps. Pairing the row element $e_{ik}$ with the column element $e_{kj}$ makes the operator align with the dynamic-programming recurrence $d_{ij} = \min_k (d_{ik} + d_{kj})$ of Floyd–Warshall, the classic all-pairs shortest-path algorithm.

Two applications of the update reach every edge. On the dense $N \times N$ edge tensor this costs $O(N^3)$ per layer, against $O(N^4)$ for full edge-to-edge attention.

RT also struggles with greedy, hard-selection steps, because soft attention averages where it should pick. To address this, each pass has an optional max-aggregation channel next to the softmax channel. We ablate this channel separately so that "discrete selection" and "relational receptive field" remain separate explanations.

We predict three things. On tasks whose outputs depend on many distant edge states, the criss-cross model will beat a matched RT. RT's deficit will grow with graph size. Widening RT's node vectors will narrow but not close the gap at a fixed parameter budget. If widening alone closes the gap, the node-bottleneck story is wrong and the right fix is simply wider nodes.

Research Program

The work has three parts.

The first is a controlled synthetic study of the node bottleneck. We generate graphs whose edge labels are set functions of the attributes of edges in the same row and column, for example "is this edge the minimum-weight edge leaving $i$ among those whose target has a heavy incoming edge." We vary $N$ from 16 to 128 and vary node width independently. For each model we measure the minimum node width needed to reach 95% edge accuracy as a function of $N$. We also measure a relational effective receptive field: the average gradient of $e_{ij}$'s output with respect to a distant input edge $e_{kl}$, grouped by line-graph distance. This mirrors how Improving the Effective Receptive Field of Message-Passing Neural Networks quantifies node receptive fields.

The second is algorithmic reasoning on CLRS-30 from The CLRS Algorithmic Reasoning Benchmark. Training uses 16-node graphs and testing uses 64-node graphs, so we can study size extrapolation. We look at per-family breakdowns, with dynamic programming, graph algorithms, and greedy tasks reported separately.

The third is long-range graph prediction on the Long Range Graph Benchmark. Here we pay particular attention to PCQM-Contact, whose target is itself pairwise (whether two atoms touch in 3D) and therefore a natural edge-level test, and to Peptides-struct and Peptides-func. Following Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark, every model gets the same tuning protocol: MLP prediction head, cosine schedule, feature normalization, and filtered MRR for PCQM-Contact. Any gain must survive the tuning confounder that erased earlier architecture gaps.

Baselines

The naive reference is a tuned local message-passing network, GCN and GINE, with deep prediction heads, run through Fesser and Weber's exact recipe. On Peptides-struct the target to beat is their tuned GCN at 0.2460 MAE, as reported in Where Did the Gap Go?. If our model cannot improve on this, it adds nothing on molecules. On Peptides-func the reference point is SAN at 0.6439 test AP, from Long Range Graph Benchmark. For PCQM-Contact under filtered MRR, no reported result was found on Lacuna, so we re-run all baselines ourselves.

The strongest existing competitor is the Relational Transformer from Relational Attention, which reports about 67% average on CLRS-30. It is the right opponent because it already has dense co-evolving edges and global node attention, and it differs from our model only in how edges gather context. We re-implement it in the same codebase and match its parameter count and wall-clock training budget, so the cubic edge pass is paid for with fewer layers or narrower edges. Both models get the same number of hyperparameter search trials. Beating RT means a higher CLRS-30 out-of-distribution average across at least three seeds, with the gain concentrated in dynamic programming and graph algorithms rather than spread uniformly. A uniform spread would point to extra capacity rather than routing.

We also include Pointer Graph Networks, at 50.84% out-of-distribution F1 against 44.99% for the plain message-passing network in The CLRS Algorithmic Reasoning Benchmark, as the hard-selection reference. On LRGB we include IM-MPNN from Improving the Effective Receptive Field with GINE layers, as the strongest linear-cost receptive-field method.

Four ablations isolate the key ingredient. In the first, RT gets node width widened until it matches our parameter count. In the second, criss-cross attention is restricted to edges that actually exist in the input graph, which makes it a local line-graph update. The third keeps only the row pass, and the fourth keeps a single pass instead of two.

Why not just…?

Why not just tune a local message-passing network properly? Fesser and Weber showed this closes much of the supposed long-range gap on Peptides, and it may do so again. That is why it is our naive baseline under an identical recipe. However, Improving the Effective Receptive Field reports GCN collapsing to 0% beyond 7 hops on CliquePath, and node-centric processors stay far below RT on CLRS-30. If the tuned GCN ties us on Peptides but loses on CLRS and on the synthetic study, we will report that the benefit is specific to edge-heavy reasoning, not to molecules.

Why not just add RT layers or widen its node vectors, since RT edges already see the graph through global node attention? This is the most serious threat, and the wide-node ablation exists to test it. If widened RT matches us at equal parameters and its required width does not grow with $N$ in the synthetic study, our mechanism is unnecessary and we will say so.

Why not just use multiscale coarsening such as IM-MPNN? It extends node receptive fields at linear cost, but its clustering hierarchy keeps edges as static conduits. It also has no way to output pair-level predictions that depend on distant pairs. PCQM-Contact and CLRS edge outputs test exactly that. If IM-MPNN with GINE matches us on PCQM-Contact at far lower cost, the cubic edge pass is not worth paying for on sparse molecular graphs.

Why not just apply local line-graph convolution, as CensNet does, with more layers? CensNet reports memory growth on dense line graphs. Our edge-restricted ablation is essentially this design at matched depth, so its gap to the full criss-cross model directly measures what non-local edge routing adds.

Decisive Checks

The idea stands or falls on three results. First, in the synthetic study, the node width RT needs should grow with $N$ while the criss-cross model's should not. Second, the CLRS-30 out-of-distribution gain over parameter-matched and width-matched RT should appear mainly on edge-state algorithms such as Floyd–Warshall and other dynamic-programming tasks. Third, the relational receptive-field gradients should show distant edges influencing outputs after two passes and not under the edge-restricted ablation.

On LRGB, the honest bar is to beat Fesser and Weber's 0.2460 MAE and to beat the re-tuned baselines on PCQM-Contact. If our model wins on CLRS but not on LRGB, the conclusion is narrower: relational receptive field matters for algorithmic edge memory, not for current molecular benchmarks.