Graph transformers let every node read from every other node. This fixes the main weakness of local message passing, where information crawls one hop per layer. Making this affordable on large graphs requires "linear attention", a reordering of the attention arithmetic that avoids building the full node-by-node score matrix. Linear attention pays for that speed twice. First, it throws away edge types: the reordering only works if the score between two nodes depends on their features alone. That is fatal for knowledge bases, relational databases and program graphs, where the meaning lives in the relation labels. Second, the usual positive-valued version produces an averaging matrix in which every node gives every other node a strictly positive weight. That is exactly the condition under which stacked averaging provably drives all node vectors to the same value, a failure called over-smoothing.
This note proposes one attention layer that addresses both problems with the same change. Relation and type information enters as a small, basis-shared vector that rescales coordinates inside the factored attention computation. A diagonal rescaling commutes with the reordering trick, so the cost stays linear. Allowing those rescalings to be negative turns the averaging matrix into a signed one, and the theorem guaranteeing collapse no longer applies. The parameter cost for relations grows with a few basis vectors rather than with one matrix per relation, so the third pressure, relational parameter explosion, is handled by the same piece. The project is worth doing only if relation-aware global attention beats the obvious hybrid of a relation-aware local layer plus relation-blind global attention. The experiments are built around that comparison.
Core Claim
Two inputs set up the claim. Demystifying Oversmoothing in Attention-Based Graph Neural Networks proves that softmax attention cannot cut edges, because every weight is positive. Products of such row-stochastic matrices therefore collapse toward rank one at a geometric rate. We use this result as a constraint on design. Positive-kernel linear attention, as used in GLADC, is the extreme case of the same structure: a strictly positive row-stochastic matrix over a complete graph. It should smooth faster per layer than local attention, not slower. GLADC's need for feature masking and layer-wise contrastive losses to reach 32 layers on Cora (85.4% accuracy) is consistent with this reading.
The claim is that a linear attention layer whose kernel is modulated by signed, basis-shared relation vectors can do three things at once. It keeps $O(N)$ cost in the number of nodes. It uses relation parameters that scale as $O(B\cdot d + |\mathcal{R}|\cdot B)$ instead of $O(|\mathcal{R}| D^2)$. It escapes the positive-consensus collapse mechanism without extra regularizers. We further predict that, on tasks where long-range relational semantics matter, it beats a hybrid model that handles relations only in local message passing.
Mechanism
Write $\phi$ for the kernel feature map that sends a query or key to a $d$-dimensional vector, $q_i, k_j, v_j$ for the usual query, key and value of nodes $i$ and $j$, and $\tau(i)$ for the type (or table) of node $i$. Each node $j$ also receives a soft assignment $a_{jb}\ge 0$ to one of $B$ shared "relational roles". This assignment is computed from the CompGCN-style basis coefficients of the relations incident to $j$ (Composition-based Multi-Relational Graph Convolutional Networks supplies this basis technique). The global update is
$$y_i=\frac{\sum_{b=1}^{B}\phi(q_i)^{\top}\operatorname{diag}(m_{\tau(i),b})\,S_b}{\sum_{b}\big|\phi(q_i)^{\top}\operatorname{diag}(m_{\tau(i),b})\,z_b\big|},\qquad S_b=\sum_j a_{jb}\,\phi(k_j)v_j^{\top},\quad z_b=\sum_j a_{jb}\,\phi(k_j).$$
In this update, $m_{\tau,b}\in\mathbb{R}^{d}$ is a learned, possibly negative modulation vector for each pair of node type and role. The role summaries $S_b$ are computed once per layer at cost $O(N B d D)$, where $D$ is the hidden dimension. Nothing of size $N\times N$ or $|\mathcal{E}|\times D$ is ever built.
The modulation acts in the factored space, so relation semantics reach the global channel without breaking the reordering. This is the specific open problem that Primphormer names: integrating edge features into primal linear attention. The denominator uses absolute values, so each row has absolute weights summing to one, but individual entries can be negative. A signed row lets a node subtract what nodes of a given role carry. This is a global analogue of the difference term in Reducing Over-smoothing in Graph Neural Networks Using Relational Embeddings, which put $h_i-h_j$ into local GAT scores and kept representations diverse to 25 layers on homogeneous citation graphs. Relations that exist only on actual edges are still handled by a cheap local CompGCN composition layer at $O(|\mathcal{E}|D)$. Each block is therefore local composition followed by signed typed global attention.
Research Program
The work has three parts. The theory part comes first and is deliberately narrow. We will show that positive-kernel linear attention fits the hypotheses of the collapse theorem in Demystifying Oversmoothing, and we will bound its contraction rate by the smallest normalized kernel weight. We will then identify conditions on the signed modulations under which the component of node features orthogonal to consensus does not contract. We do not expect signed weights to prevent collapse in general, since signed products can also shrink. The goal is to state when they cannot be forced to. The theory is supported by direct measurement of the joint spectral radius of the disagreement subspace on trained models.
The second part is the implementation and parameter accounting. There are three knobs: the number of roles $B$, sharing $m$ across types versus keeping it type-specific, and the sign constraint. We will report the exact number of relation parameters next to R-GCN and HetSheaf.
The third part is evaluation, using the decisive comparisons described below. Over-smoothing will be judged primarily by downstream accuracy as depth grows, together with effective rank of the node representations. Dirichlet-energy-style scores are reported only as secondary measures, because Are we measuring oversmoothing in graph neural networks correctly? questions whether they track task performance.
Baselines
The naive reference point is the homogenized graph: drop edge labels and run a strong local network. On program graphs this is not a weak baseline. A Benchmark Dataset for Graph Regression with Homogeneous and Multi-Relational Variants reports PNA on the homogeneous RelSC-H variant reaching MAE 0.09 for Hadoop execution-time prediction, and models on RelSC-H beat models on the 49-relation RelSC-M variant. Our model, trained on RelSC-M, must reach an MAE below 0.09. Otherwise the relational machinery has not justified itself.
The strongest local relational baseline is CompGCN with circular-correlation composition. It reports MRR 0.355 on FB15k-237 and 85.3% accuracy on MUTAG, against 73.2% for R-GCN (CompGCN). It is the method whose basis-sharing we reuse, so it isolates what global attention adds. It will be run at depths from 2 to 32 with the same hidden size and the same tuning budget as our model.
On relational databases, the strongest existing system is Relational Graph Transformer. RelGT combines all-pair attention over a sampled subgraph of at most 300 nodes with cross-attention to learnable global centroids. It reports matching or beating GNN baselines on 19 of 21 RelBench tasks, and an 18.4% improvement on clinical trial site success. The file gives no per-task numbers, so we will rerun RelGT ourselves with the same splits, the same budget of GPU hours, and the same hyperparameter search size. Beating it means a higher mean task metric across the 21 tasks, together with lower memory than its sampled attention. For knowledge graph completion we add Relphormer, which reports Hits@1 of 0.314 on FB15k-237. For efficiency we compare against Primphormer, which reports about 13.35 GB peak memory on ogbn-products where a standard transformer runs out of memory. For depth regularization we compare against GLADC.
The most important baseline is one we construct ourselves. It consists of CompGCN local layers interleaved with plain positive linear attention, with no modulation. Two ablations isolate the key ingredient. The first keeps the typed modulation but forces $m\ge 0$, testing whether sign matters. The second keeps signs but uses a single role, $B=1$, testing whether relation information in the global channel matters. Every variant is matched in parameter count to within 10%.
Why not just…?
Why not just pair a relation-aware local layer with ordinary linear attention? This is the real threat, and the proposal stands or falls on it. Relations would be absorbed locally, and the global channel would only need to move information around. Nothing in the file shows this hybrid failing on multi-relational data, because no one in the file reports it. The hybrid is exactly our unmodulated ablation. If it matches the full model on RelBench, RelSC-M and ECHO-Chem, we will conclude that typed global attention is unnecessary. We would then report the narrower result that signed weights alone fix depth collapse.
Why not just collapse edge types and use a well-tuned homogeneous GNN? On RelSC this currently wins (RelSC). The same paper also shows that removing control-flow and data-flow edges raises error by nearly 40%, so relational structure does carry signal; existing multi-relational models simply fail to exploit it. Our hypothesis is that the deficit comes from per-relation capacity on long-tailed relations combined with depth collapse. If so, a basis-shared, non-collapsing model on RelSC-M should overturn the paradox. If it does not, the paradox is better explained by the data than by the architecture.
Why not just keep softmax-free positive linear attention and add GLADC-style regularizers or residual connections? GLADC shows this works to 32 layers on homogeneous graphs. It requires masking and contrastive terms tuned per depth, and the collapse theorem says the underlying operator still contracts. The positive-modulation ablation, with and without GLADC's constraints, answers whether sign is doing the work. If the regularized positive model matches ours at depths of 16 and 32 on ECHO-Charge and Cora, the sign claim is wrong.
Why not just use sheaf models, which already cut parameters and resist smoothing? HetSheaf runs on IMDB with 1.6 million parameters, against 72.1 million for R-GCN (Heterogeneous Sheaf Neural Networks). Cooperative Sheaf Neural Networks reaches 100% on depth-8 NeighborsMatch. Both remain local diffusion over edges, so long distances still cost many layers. We include HetSheaf on ACM, DBLP and IMDB. For IMDB the file reports no accuracy, so its numbers must be rerun.
Proposed Experiments
The decisive experiment is a depth sweep (2, 4, 8, 16, 32 layers) on ECHO-Chem, whose molecules carry bond-type relations and need 17 to 40 hops of propagation (Can You Hear Me Now?). The reference points are SWAN at MAE 6.109×10⁻³ on ECHO-Charge and GPS at MAE 5.257 on ECHO-Energy. GPS needs about 788 seconds per epoch on ECHO-Charge, against about 12.8 seconds for A-DGN. Success means approaching SWAN's error at an epoch time much closer to A-DGN's than to GPS's, with accuracy not falling as depth grows while the positive-modulation ablation does fall.
The second decisive check is RelSC-M versus the 0.09 MAE homogeneous PNA result. The third is RelBench against our matched RelGT rerun. Further experiments are FB15k-237 against CompGCN's 0.355 MRR, and a memory test on ogbn-products with a single relation against Primphormer's 13.35 GB. Finally, we will sweep $B$ from 1 to 50 to check whether, as with CompGCN's 50 bases for 237 relations, a few dozen roles saturate performance.
The project's most likely failure is that the hybrid ablation matches the full model. That outcome would still be informative, because it would show that relation semantics belong in local layers and that the global channel's only job is to avoid consensus.
References
- Demystifying Oversmoothing in Attention-Based Graph Neural Networks
- GLADC: Global Linear Attention and Dual Constraint for Mitigating Over-Smoothing in Graph Neural Networks
- Composition-based Multi-Relational Graph Convolutional Networks
- Primphormer: Efficient Graph Transformers with Primal Representations
- Reducing Over-smoothing in Graph Neural Networks Using Relational Embeddings
- Are we measuring oversmoothing in graph neural networks correctly?
- A Benchmark Dataset for Graph Regression with Homogeneous and Multi‑Relational Variants
- Relational Graph Transformer
- Relphormer: Relational Graph Transformer for Knowledge Graph Representation
- Heterogeneous Sheaf Neural Networks
- Cooperative Sheaf Neural Networks
- Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation