Source Anchors: How Causal Masks Bound Over-Smoothing in Graph Attention

When a graph neural network stacks many rounds of neighbor averaging, every node's representation drifts toward the same vector. This is called over-smoothing, and it is the main reason deep graph networks stop working. For attention-based graph networks, the strongest existing result says this collapse cannot be avoided. Softmax never assigns exactly zero weight to an edge, so on a connected graph the repeated averaging mixes everything together and the representations shrink exponentially toward a single point. A causal mask behaves differently. Here "causal mask" means a rule that lets a node read only from nodes earlier in some order, as in autoregressive language models or attention restricted to ancestors in a directed acyclic graph. Under such a mask, a node with no predecessors (a source) can only attend to itself, so it never moves. Our central observation is that this one fact changes the endpoint of over-smoothing. Representations no longer converge to one point. They converge into the span of the source nodes' features, and what distinguishes one node from another is preserved in its data-dependent mixing weights over those sources.

The proposal turns this observation into a theorem and a design rule, then tests both. The theorem: with residual connections, a causally masked attention matrix is lower-triangular, so its eigenvalues are simply its diagonal self-attention weights. The eigenvalue-one directions are therefore exactly the sources. This yields a lower bound on the rank that survives at large depth, set by the number of sources rather than by connectivity. The design rule: add a small budget of $k$ learned anchor nodes that every node may read but that read nothing themselves. This gives a controllable floor on the representation rank at arbitrary depth. Because each node attends to $k$ anchors plus its reachable local neighborhood, the cost is $O(nk + |E|)$ for $n$ nodes and $|E|$ edges, and causality holds by construction.

Core Claim

Demystifying Oversmoothing in Attention-Based Graph Neural Networks models graph attention as a product of time-varying row-stochastic matrices. It uses joint spectral radius and ergodicity arguments to prove exponential collapse to rank one, with the key step being that softmax keeps every edge alive. That argument assumes information can flow in both directions along paths, and the paper says nothing about masked or acyclic topologies. Clustering in Causal Attention Masking studies the opposite regime for one-dimensional sequences. It models causal attention as a continuous-time particle system on the sphere and finds that early tokens act as nearly stationary "Rényi centers" that hold metastable clusters. It also proves full collapse to one cluster when the value matrix is the identity. Its analysis uses tied weights, omits MLP blocks, freezes the centers to make the proofs go through, and does not extend to graphs.

We claim the following. Order the nodes topologically and write the layer as $X_{\ell} = X_{\ell-1} + A_\ell X_{\ell-1} H$. Here $A_\ell$ is the masked, row-stochastic attention matrix at layer $\ell$ and $H = W_V W_O$ is the value–output weight product, following the update analyzed in Setting the Record Straight on Transformer Oversmoothing. Because $A_\ell$ is lower-triangular, its spectrum is its diagonal $\{a^{(\ell)}_{ii}\}$. Each source $s$ has $a^{(\ell)}_{ss} = 1$. If every non-source keeps self-weight below some $1-\delta$, then the pure-averaging part of the dynamics (taking $H$ to be the identity on the averaging channel) satisfies

$$\prod_{\ell=1}^{L} A_\ell \;\longrightarrow\; W \,[\,0 \;\; I_k\,]\ \text{restricted to sources},\qquad X_\infty = W\,S,$$

where $S \in \mathbb{R}^{k\times d}$ stacks the $k$ source features and $W \in \mathbb{R}^{n\times k}$ is a row-stochastic matrix of limiting mixing weights. Each row of $W$ is supported only on that node's ancestral sources. The rank of $X_\infty$ is at most $k$ and generically equals it. The convergence is geometric at rate $1-\delta$, because the strictly lower-triangular, non-source part of the product shrinks like a power of the largest non-source diagonal entry.

Three consequences follow. First, two nodes become indistinguishable at depth only if their ancestral source sets and their limiting weights coincide. This replaces "connected component" in Wu et al. with "source-reachability class". Second, in a one-dimensional causal sequence there is exactly one source, so the theorem predicts collapse onto the first token. This is consistent with the identity-value result of Karagodin et al. and suggests why early positions behave as anchors. Third, adding $k$ read-only anchors gives an explicit, tunable floor on deep representation rank. We expect the full residual dynamics with general $H$ to inherit this structure: Dovonon et al. show that the coupling between the spectra of $A$ and $H$ decides smoothing versus sharpening, and here the spectrum of $A$ is fully explicit. Proving the general-$H$ case is part of the program, not an assumption.

Research Program

The theory component extends the ergodicity machinery of Wu et al. from irreducible to reducible, triangular products. Lower-triangular stochastic products are a classical, tractable case, which makes us confident the rank-$k$ limit is provable without freezing centers as Karagodin et al. must. The open work has three parts. The first handles general $H$ through its eigendecomposition, extending the reparameterization of Dovonon et al. The second covers LayerNorm, whose sign flips Dovonon et al. show can invert smoothing behavior. The third gives a finite-depth rate in terms of the minimum non-source self-attention gap $\delta$.

The method component, which we call Source-Anchored Causal Attention, adds $k$ learned anchor vectors to a reachability-masked graph transformer of the kind introduced in DAGformer: Directed Acyclic Graph Transformer. DAGformer restricts attention to ancestors and descendants and encodes depth by longest path. We keep only the ancestor direction so the mask is genuinely causal. Every node may attend to all anchors, while anchors receive nothing and are updated only by gradient descent.

Graphs with cycles, such as ogbn-arxiv, are not acyclic. On them we use one of two orderings. The first is a timestamp order where one exists, as with citations. The second is a learned order obtained by condensing strongly connected components; within a component, bidirectional attention is allowed and the theory's guarantees weaken. The cost is $O(nk + |E_{\text{reach}}|)$, where $E_{\text{reach}}$ is the set of reachability edges actually attended within a $k$-hop radius, as in Directed Graph Transformers. That work notes its directional attention is quadratic and leaves linear scaling open.

The connection to sub-quadratic attention is deliberately modest. Open problems listed for WildCat: Near-Linear Attention in Theory and Practice, CAT: Circular-Convolutional Attention for Sub-Quadratic Transformers, and MonarchAttention concern enforcing causality inside a global approximation. Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time explains why the mask breaks low-rank structure. We do not solve that problem. Instead we note that anchor attention is low-rank by design and causal by construction: anchors precede every node. The global part of the computation therefore avoids the mask problem entirely, and only the sparse local part carries the triangular structure.

Baselines

The naive reference point is the same reachability-masked transformer with no anchors, run at matched depth. Our theory predicts that its deep rank equals the number of natural sources in each graph. Measuring this checks the theorem, and the gap to the anchored model isolates the contribution of the anchors. A second naive point is an unmasked graph attention network at the same depth, which Wu et al. show collapses exponentially. They report that GCN features on Cora "collapsed almost entirely within 20–30 layers" and that GAT decays more slowly but still toward zero similarity by 128 layers.

The strongest existing method for deep directed graphs is Dune, from Unitary Convolutions for Message-passing and Positional Encodings on Directed Graphs. It projects the directed adjacency into a Hermitian generator and propagates with a norm-preserving matrix exponential, which keeps features diverse past 100 layers. It is the strongest competitor because it targets exactly deep directed over-smoothing. It reports OGBN-Arxiv accuracy of 72.16%, up from a previous best of 68.76%, and Questions accuracy of 80.45%, up from 77.67%. We will rerun Dune from its released configuration on identical splits with the same hyperparameter-search budget in GPU-hours as our method. Beating it means exceeding its reproduced accuracy at its best depth, or matching it at lower wall-clock cost while keeping accuracy flat out to 128 layers.

For acyclic graph-level tasks, the strongest competitor is DAGformer-enhanced SAT on ogbg-code2. It reports a new best F1 and 10 minutes per epoch, against 40 for SAT and 100 for DAGNN, but no reported F1 value was found on Lacuna for it. We will therefore reproduce it under our compute budget and compare against the reproduced figure. On FlowGraph6 and Twitter5, DiGT is the reference: it reports a 3.06% gain over EGT on FlowGraph6 and over 7% over standard graph transformers on Twitter5. No absolute accuracy was found on Lacuna, so DiGT is likewise reproduced.

The key ablation keeps the $k$ anchors but lets them receive messages from nodes. This makes them ordinary bidirectional virtual hubs in the style of ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment, which routes nodes through $O(\sqrt{N})$ hubs in linear time on undirected graphs. If read-only anchors are what matters, this ablation should collapse with depth while ours does not. A residual baseline with the eigen-reparameterized $H$ from Dovonon et al. and no mask is also included; it is discussed below.

Why not just…?

Why not just control the spectrum of $H$, as Dovonon et al. do? Setting the Record Straight on Transformer Oversmoothing shows that residual connections plus a reparameterized $H$ can prevent rank collapse at 48 layers. They also find that forced smoothing beats sharpening on CIFAR100 (+2.62% versus +1.81% over baseline). This is a real threat: if tuning $H$ alone keeps deep graph attention expressive, the mask and anchors add nothing. Our view is that the two approaches act on different spectra. $H$ controls feature channels, while the mask fixes which node directions survive. Sharpening through $H$ also amplifies every direction, including noise. The decisive experiment crosses the two factors: $H$-reparameterization with and without the causal mask and anchors, at depths 8 through 128. If $H$-control alone matches our accuracy and rank curves, we will report that the anchor mechanism is redundant.

Why not just use a unitary operator like Dune? Norm preservation prevents collapse by refusing to contract at all. That also means it cannot perform the useful contraction that Dovonon et al. find helps classification. Anchoring contracts toward a learned $k$-dimensional subspace instead. Dune is the headline baseline above, and the comparison will show whether controlled contraction or no contraction generalizes better. Heterophilic directed sets such as Roman-Empire are where we are least sure we win.

Why not just add ordinary virtual nodes or hubs? Bidirectional hubs receive messages, so they belong to the connected, ergodic regime of Wu et al. and should themselves smooth over depth. The read-versus-receive ablation tests this directly. If bidirectional hubs keep rank equally well in practice, the theorem would still describe the limit, but the method's advantage would be only theoretical.

Why not just learn constant bias vectors or positional encodings? If anchors were input-independent and nodes' limiting weights $W$ were also input-independent, anchors would reduce to a learned bias. The claimed value lies in $W$ being data-dependent. We test this with an ablation that freezes attention logits to anchors as input-independent learned constants. If accuracy is unchanged, anchors are acting only as biases.

Proposed Experiments

The first decisive check is the theorem itself. We use synthetic DAGs with a controlled number of sources, from 1 to 64, and fixed node count. For each, we run masked attention stacks at depths up to 256 and plot effective rank and convergence rate against predicted rank $k$ and predicted rate $1-\delta$. We read $\delta$ from the learned diagonal attention weights.

Following Are we measuring oversmoothing in graph neural networks correctly?, which questions whether pairwise-distance metrics reflect lost task expressivity, we pair effective rank with linear-probe accuracy on held-out labels at every depth. This ensures that a preserved rank is shown to carry task-relevant information. We also include the Barbell-graph test from Advection-Diffusion on Graphs, where $\mu$-ChebNet reports 0.02 mean squared error versus 0.87 for ChebNet, as an oriented variant. This checks whether anchoring handles bottlenecks or only smoothing.

The main benchmarks are directed node classification on ogbn-arxiv and Questions against Dune, graph-level DAG tasks on ogbg-code2, Neural Architecture, and Self-citation against DAGformer, and FlowGraph6 and Twitter5 against DiGT. On each, we sweep depth over 2, 8, 32, and 128, and anchor budget $k$ over 0, 4, 16, and 64. The prediction that would falsify the proposal is specific. Accuracy of anchored models should stay flat with depth while unanchored masked models degrade in proportion to how few natural sources the graph has. If degradation does not track source count, the mechanism is wrong.

A final small check applies the one-source prediction to causal language models. We train small decoders on WikiText-103 with and without $k$ prepended read-only anchors and measure layerwise effective rank. This tests whether representations in the plain model collapse toward the first position as predicted. It is a mechanism test, not a perplexity claim. The CAT figure of 10.28 versus 13.94 perplexity is for masked, not causal, language modeling, so it is not a comparable baseline.