Order-Aware Relational Transport for Deep Graph Propagation

Graph neural networks that pass messages between neighboring nodes face two problems as they get deeper. First, every node's features drift toward the same vector. This is called over-smoothing, and it happens because each round of neighbor averaging behaves like a blur. Second, on multi-relational graphs such as knowledge graphs, most message-passing layers cannot tell a path "father of → wife of" from "wife of → father of." The reason is that the per-relation operations they apply commute, so only the set of relations on a path matters, not their order. This note proposes one mechanism aimed at both problems. Each relation type gets a small learned rotation, made of 4×4 blocks built from unit quaternions. These rotations do not commute. Features are propagated linearly across many hops, and a nonlinearity is applied only at readout, following the design that made fast linear recurrent networks work.

Under this design, a node's depth-$K$ representation is a sum over walks of ordered products of relation rotations. Two benefits follow from that single property of non-commutativity. Paths with the same relations in a different order stay distinct. And the long-run averaging no longer settles onto a constant vector, because going around a cycle of mixed relations generally returns a feature rotated rather than unchanged. The proposal is to build this layer, test whether non-commutativity itself is what matters, and do so against matched commutative controls on knowledge-graph benchmarks and a synthetic order-sensitive graph task.

Core Claim

Consider a graph with relation-labeled edges $(u, r, v)$. We propagate

$$h_v^{(k+1)} = \frac{\alpha}{|\mathcal{N}(v)|}\sum_{(u,r,v)} Q_r\, h_u^{(k)} \;+\; B x_v ,$$

where the symbols are as follows. $h_v^{(k)}\in\mathbb{R}^{n}$ is node $v$'s state after $k$ hops. $Q_r$ is a block-diagonal matrix of $n/4$ blocks, each block being left-multiplication by a unit quaternion learned for relation $r$. $x_v$ is the node's input feature, $B$ a learned input map, and $\alpha<1$ a learned scalar damping. Unrolling gives $h_v^{(K)}=\sum_{\text{walks } u\to v}\alpha^{k}\,c_w\,Q_{r_k}\cdots Q_{r_1}Bx_u$, where $c_w$ collects the averaging weights along the walk.

Our first claim is about order. With commuting maps, which covers diagonal transitions, 2×2 complex rotations, and scalar weights, the walk term depends only on the multiset of relations on the walk. With quaternion blocks, it depends on their order.

Our second claim is about smoothing. The subspace that survives deep averaging is the space of features that stay consistent after transport around every cycle. With scalar weights this space is the constant vector, which is exactly what over-smoothing collapses onto. With non-commuting relation maps on a graph rich in mixed-relation cycles, we predict this space shrinks to nearly nothing. Deep features should then stay node-specific instead of becoming uniform.

Our third claim is about cost. Because blocks are 4×4 and are parameterized by normalizing a raw 4-vector, the layer costs about four times a diagonal layer and needs no manifold-constrained optimizer.

The new element is relation-typed, learned, composable non-commuting transport inside deep linear propagation. It is evaluated directly against commutative versions of the same layer.

Relation to Prior Work

Three lines of work motivate the design.

The first is non-commutative knowledge-graph embeddings. OrthogonalE scores triples with block-diagonal orthogonal relation matrices. QRSE uses quaternion multiplication. Both show that leaving commutative 2D rotations helps link prediction: on WN18RR, OrthogonalE reports MRR 0.494 against RotatE's 0.470, and QRSE reports 0.491. Both are shallow triple scorers with no propagation and nothing to say about depth. OrthogonalE also reports roughly fourfold slower training from Riemannian updates. We reuse their algebra but place it inside deep propagation, and we drop the Riemannian step.

The second is sheaf diffusion. Sheaf Neural Networks with Connection Laplacians shows that orthogonal per-edge "restriction maps" break the constant-vector null space of the graph Laplacian and so prevent over-smoothing. This is the mechanism we rely on. However, their maps are computed per edge from local PCA rather than learned per relation type. That means the maps cannot compose along relation paths or transfer across the graph. They also evaluate only single-relation heterophily benchmarks.

The third line connects sequence models and smoothing. MbaGCN treats the 1-hop through $K$-hop aggregates as a sequence for a Mamba-style state-space model. It reports 86.27% on Wisconsin and stable accuracy to 10 layers, but it uses diagonal, commuting transitions on single-relation graphs. Wang et al. prove that stacked linear state-space layers over-smooth across time and suffer exponential recency decay when transitions are contractive. They fix this by clamping channels to 0 and 1. We borrow that idea as a constraint. Our transports have norm one, and the only contraction is the scalar $\alpha$ together with the input injection $Bx_v$.

Two papers supply method. Resurrecting Recurrent Neural Networks for Long Sequences supplies the recipe of linear transitions, nonlinearity only outside the recurrence, and stable exponential parameterization of decay. DeltaNet shows that products of non-commuting orthogonal (Householder) factors can be trained at scale without manifold optimizers. For path-query composition we use the associative structure the same way, though our relation paths are short.

One paper constrains the theory. Sequential Group Composition proves that a two-layer network composing $k$ elements of a non-commutative finite group needs width growing like $(k+1)2^{k-1}\lfloor|G|/2\rfloor$, while recurrent or deep tree structures need only bounded width. This predicts that shallow "collapse the hops into one layer" designs will fail on order-sensitive relational tasks, such as hpGAT's high-order proximity factorization. Their guarantees cover only finite groups, so we treat the continuous case as an empirical question.

Are we measuring oversmoothing correctly? warns that Dirichlet energy cannot separate useful clustering from information loss. We therefore measure smoothing by what deep features can still recover. Backward Oversmoothing shows that gradients can collapse even when forward features do not, so we measure gradient alignment as well.

Research Program

We will build the layer in three variants that share all code and differ only in the transport algebra. The scalar variant ($Q_r=I$, a damped linear GCN with input injection) is the commutative floor. The 2×2 complex-rotation variant is RotatE-like and commutative but norm-preserving. The quaternion-block variant is the full proposal. Parameter counts are matched by width.

Readout uses a small attention over the hop states $h^{(1)},\dots,h^{(K)}$, followed by an MLP. We use this rather than MbaGCN's selective scan so that hop-wise selection is held constant across the three variants. The layer plugs into two tasks. For node classification, the readout feeds a classifier. For link prediction and chain queries, the target score is $\langle Q_{r_m}\cdots Q_{r_1} h_{\text{head}}, h_{\text{tail}}\rangle$, so relation maps used during propagation and during scoring are the same objects.

The analysis has two parts. First, we prove the multiset-collapse statement for commuting transports, which is straightforward. We then characterize the consistent-transport subspace as a function of the cycle structure of the relation-labeled graph and measure its dimension numerically on the benchmark graphs. Second, we track over depth three quantities. One is the effective rank of normalized node features. Another is the accuracy of a linear probe recovering a node's $j$-hop-away label or relation from $h^{(K)}$. The third is the cosine alignment of per-node gradients, which detects backward over-smoothing.

Baselines

The naive reference is a 2-layer relational GCN-style aggregation with residual connections. It is tuned and given the same compute as the other models. It shows what one gets by simply staying shallow.

The strongest knowledge-graph competitors are OrthogonalE and QRSE. They are the strongest because they already capture non-commutative composition, just without propagation. We rerun both under our evaluation protocol and also quote their reported numbers. On WN18RR those are MRR 0.494 for OrthogonalE and 0.491 with Hit@1 0.443 for QRSE. On FB15k-237, QRSE reports MRR 0.350 and Hit@1 0.252. Beating them means a statistically reliable MRR gain over five seeds under the same negative sampling, embedding budget, and number of hyperparameter trials. We would also accept matching their MRR at markedly lower training time, and we report wall-clock for both.

For chain queries, the strongest reported system is the Transformer-based Sequential Query Encoding, which reports MRR 67.13 on FB15k-237 entailment queries against 38.05 for the prior best. We will run SQE's released setting on its chain-query subset with the same query splits. The comparison is a test of whether order-aware transport closes the gap, not a claim of beating it outright. The file gives no reported numbers on FB15k or NELL for SQE, so no reported result was found on Lacuna for those settings, and we will report our own reruns.

For the depth question, the competitors are MbaGCN and Conn-NSD from Barbero et al., both run at depths 2 through 64 on identical splits. We give MbaGCN relation-typed edge weights so that it is not handicapped on multi-relational graphs.

The key ablation is the 2×2 complex-rotation variant at matched parameters. If it matches the quaternion variant, non-commutativity is not the active ingredient. A second ablation replaces normalized-quaternion parameterization with Riemannian updates, to isolate the training-time claim against OrthogonalE's reported fourfold slowdown.

Why not just…?

Why not just use learned sheaf diffusion, which already uses orthogonal edge maps against over-smoothing? This is the closest threat. On single-relation heterophily graphs such as Texas, Film, and Wisconsin, we do not expect to beat it. With one relation type our maps reduce to powers of a single rotation, which commute, so these graphs serve as a negative control. The claimed advantage is specific to multi-relational graphs. There, sharing maps by relation type yields composable and transferable transports, while per-edge maps cannot be reused in path scoring. The FB15k-237 and synthetic experiments compare against a relation-agnostic per-edge orthogonal variant at equal parameters. If it matches us there, the relation-typing claim fails.

Why not just use a diagonal or complex state-space layer such as MbaGCN with more width? Commuting transports cannot separate reordered paths at any width, because the walk terms are identical. That is a property of the algebra, not of capacity. The synthetic group-path task tests it directly. Whether reordered paths matter on real benchmarks is an empirical question. The matched 2×2 ablation answers it on FB15k-237 and WN18RR, where the reported gap between RotatE (0.470) and OrthogonalE (0.494) suggests it does.

Why not just stay shallow, or use a high-order proximity layer like hpGAT, plus residuals? Results on Sequential Group Composition predict that composing $k$ non-commuting steps in a shallow model needs width exponential in $k$. Relational GAT shows depth helps when features are missing: on Pubmed with 100% missing features it reaches 71.3% at depth 10, against 70.1% for GAT at depth 8. We include the shallow baseline and hpGAT on the synthetic task across $k$. If they track our model at matched width for $k$ up to 6, this argument fails.

Why not just run a Transformer over linearized relation paths, as SQE does? SQE is strong on query answering, and we may not beat its accuracy. Our claim is narrower: whether linear-cost propagation with order-aware algebra recovers most of that accuracy while also producing node representations for classification and link prediction, which SQE does not provide. We report accuracy against cost jointly.

Proposed Experiments

The first decisive check is a synthetic test. We build random multi-relational graphs whose edges are labeled by generators of the dihedral group $D_p$ or the alternating group $A_5$. Each node's label is the group element obtained by composing the edge labels along its path from a root. In a commutative control version, labels come from the cyclic group $C_p$. We predict that the quaternion variant solves the non-abelian task at bounded width as path length grows. We predict that the scalar and 2×2 variants fail on the non-abelian task but succeed on $C_p$. A pass requires the gap to appear only on the non-abelian groups.

The second check is a depth sweep from 2 to 64 hops on FB15k-237 and WN18RR link prediction, scored by MRR and Hit@1. Alongside it we report effective rank, the $j$-hop probe accuracy, and gradient alignment. We predict that the quaternion variant's MRR keeps rising or plateaus while the scalar variant's degrades. We also predict the probe recovers distant information in the quaternion variant and not in the scalar one.

The third check covers chain queries from the SQE splits, scored by MRR.

The fourth check uses the negative-control graphs: Cora, Pubmed with missing features, and Wisconsin. Here we predict no gain over the 2×2 variant. A gain there would mean our improvements come from something other than non-commutativity, and we would report it as such.

The proposal fails if the 2×2 ablation matches the quaternion variant on FB15k-237 and WN18RR. It also fails if consistent-transport subspaces on these graphs turn out to be no smaller than in the scalar case.