Rotation Residuals as Edge Budgets for Noisy Knowledge Graphs

Knowledge graphs store facts as labeled edges, such as (Paris, capital_of, France). Real ones contain many wrong edges. Graph neural networks, which update each entity by aggregating messages from its neighbors, spread those errors further and pay compute for every edge they touch. We propose to use one number per edge for two jobs at once: deciding which edges are probably wrong, and deciding which edges are worth the compute. The number is the edge's rotation residual. Each entity is a vector of quaternions (four-dimensional numbers whose multiplication does not commute), each relation is a rotation, and the residual measures how far rotating the head entity by the relation lands from the tail entity. Each node then keeps only its few lowest-residual incoming edges for message passing, and messages are composed as ordered quaternion rotations across layers. The model gets cheaper and more robust to noise in the same step.

The opportunity exists because the relevant pieces have stayed in separate literatures. Geometric relation models such as RotatE, QuatE and DaBR give principled tests of whether a triple fits relational patterns, but they are shallow scoring models that assume clean training triples. Edge-denoising methods such as PTDNet and NodeFormer learn which edges to drop, but only on single-relation graphs, using homophily or dot-product criteria that do not fit knowledge graphs. In a knowledge graph, a country links to a city by design, so "connected nodes should look alike" is the wrong test. Scalable sparsifiers such as UGS show that the adjacency structure, not the weights, dominates GNN cost, yet they prune by mask magnitude with no notion of relation semantics.

Core Claim

In a multi-relational message-passing network, a quaternion rotation residual can serve as a per-node edge-selection rule. It recovers most of the accuracy of full-graph training on clean graphs while touching a fixed fraction of edges, and it degrades much less than full-graph or randomly sparsified training when wrong edges are injected.

The specifically quaternion part of the claim is narrower and testable. Quaternion rotations compose in order: $q_1 \otimes q_2 \neq q_2 \otimes q_1$, where $\otimes$ is the Hamilton product, the quaternion multiplication rule. As a result, a two-layer message carries the order of the relations along its path. Complex rotations compose commutatively and lose that order. We therefore predict that the quaternion version beats a complex (RotatE-style) version mainly on noise that is consistent with each relation locally but violates path order. If the advantage does not appear there, the quaternion ingredient is not earning its 16-multiplication cost, and we will say so.

Mechanism

Entity $u$ has embedding $q_u \in \mathbb{H}^d$, a vector of $d$ quaternions. Relation $r$ has $\hat q_r$, a vector of unit quaternions. For an edge $(h, r, t)$ the residual is

$$\varepsilon(h,r,t) = \lVert q_h \otimes \hat q_r - q_t \rVert_2 ,$$

which is the QuatE/DaBR-style geometric distance applied to edges of the message-passing graph rather than only to scored queries.

At each layer, node $t$ keeps its $L$ incoming edges with the smallest residual. It aggregates the messages $q_u \otimes \hat q_r$ with weights $\mathrm{softmax}(-\varepsilon/\tau)$, where $L$ is the edge budget per node and $\tau$ is a temperature. The update itself is a quaternion linear layer in the style of Quaternion Graph Neural Networks. Unlike that paper's SimQGNN, which drops relation types during propagation and leaves them to a DistMult decoder, our relation rotations act inside aggregation. In that respect this is the hypercomplex counterpart of CompGCN's composition operators, which remain real-valued. The decoder is DaBR's bidirectional-rotation score, so the comparison with the strongest shallow model is direct.

A model that ranks its own edges can reinforce its early mistakes: it learns to keep edges it already fits and to drop hard true edges. We guard against this in three ways. Residuals are computed from an exponential-moving-average copy of the embeddings and refreshed every few epochs. Selection is soft during warm-up. A per-relation floor guarantees that rare relations keep at least some edges. Recomputing residuals for all edges costs $O(|\mathcal{E}| d)$ Hamilton products, one pass per refresh. Aggregation then costs $O(NLd)$ per layer, independent of high-degree hubs. This is how the method answers the concern raised by UGS and by the quaternion papers themselves, that hypercomplex layers cut parameters but add arithmetic on the structural side of the cost. Because RMask and the hardware literature warn that sparsity on paper does not equal speed, we report wall-clock time and peak memory, not just multiply-accumulate counts.

Research Program

The work has three parts. First, we build the model and its complex-number and real-number twins under one codebase, with the same embedding size counted in real numbers. Second, we build a noise-injection suite on standard benchmarks with three noise types of increasing difficulty. The first replaces tails at random. The second is type-plausible: a tail is replaced by an entity that appears as a tail of the same relation elsewhere, so per-relation statistics cannot flag it. The third is order-violating: for relation pairs whose composition $r_1 \circ r_2$ frequently implies a third relation $r$, we insert $(h, r, t')$, where $t'$ is reached by the reversed path $r_2 \circ r_1$. Only an order-sensitive composition check should catch this third type. Third, we scale the method to ogbl-wikikg2 with the budget used as a neighbor sampler for mini-batches, and compare against path-based pruning.

Baselines

The naive reference point is CompGCN with full-graph message passing on the noisy graph, with no edge selection. CompGCN reports 0.355 MRR on clean FB15k-237 with circular correlation (CompGCN). Every method's clean and noisy MRR is reported relative to it. Beating it means equal clean MRR at budget $L$, together with a smaller drop under each noise level.

The strongest shallow competitor is DaBR, which reports 0.373 MRR on FB15k-237 and 0.510 MRR on WN18RR (DaBR). QuatE reports 0.488 on WN18RR (QuatE). DaBR matters because shallow embeddings never propagate errors through neighbors, so they may simply be robust to noise. We retrain DaBR ourselves on each noisy graph with the same negative sampling, embedding size and tuning budget. On clean data, matching it within about one MRR point while using a GNN is acceptable. The bar is to beat it under noise.

The strongest scalable competitor is A*Net, which reports 0.6767 MRR on ogbl-wikikg2 against 0.6392 for the previous best embedding model, ComplEx+RP, while visiting 0.2% of the graph (A*Net). We do not expect to beat A*Net on clean wikikg2. The comparison is MRR per GPU-hour, peak memory, and retention under injected noise, all run on the same hardware.

Three ablations isolate the key ingredient, each at an identical budget $L$ and identical compute. The first keeps the top-$L$ edges at random or by degree, which tests whether any budget helps. The second uses a learned MLP edge scorer over endpoint features, as in PTDNet adapted to relation types, which tests learned scoring without geometry. The third swaps quaternion rotations for complex rotations, a RotatE residual with commutative composition, which tests the quaternion claim. All variants receive the same hyperparameter grid size and the same number of seeds (five).

Why not just…?

Why not just score edges with a pretrained RotatE and delete the worst ones? This is the most serious threat. A complex-valued residual may detect random and type-plausible noise as well as ours, at a quarter of the arithmetic. RotatE's Countries S3 result shows that rotations already capture composition well: AUC-PR 0.95 against 0.52 for DistMult (RotatE). We do not argue around this. The complex ablation runs on every benchmark. If it matches the quaternion version on order-violating noise, the contribution narrows to "geometric residuals as edge budgets", and the quaternion claim is dropped. A one-shot deletion also cannot recover once embeddings improve, which the refreshed residual addresses. We report one-shot deletion as an extra variant.

Why not just use DropEdge or random neighbor sampling? PTDNet reports that learned dropping beat DropEdge and NeuralSparse as noise increased, improving GCN by 37.37% on Cora with 20,000 added edges (PTDNet). That evidence comes from a homophilous graph, though, so the random-budget ablation above is the real test in the knowledge-graph setting.

Why not just train a shallow quaternion model and skip message passing? Shallow models do not propagate noise. If DaBR on noisy graphs matches our model, the GNN is not justified. The noisy-DaBR baseline settles this directly. The case for message passing rests on the CompGCN-over-shallow gains and on R-GCN's reported 29.8% improvement over a decoder-only model (R-GCN). Those gains were measured on clean graphs, so they are a hypothesis here, not evidence.

Why not just use A*Net, which already prunes? A*Net's priority function depends on the query and is learned for answer convergence. It never judges whether an edge is true, so an injected edge on a promising path is expanded like any other. The noisy-wikikg2 comparison shows whether this matters.

Proposed Experiments

The first decisive check runs on FB15k-237 and WN18RR at noise levels of 0, 10, 20 and 40% for each of the three noise types. We plot MRR against noise level for every baseline. As a separate diagnostic, we measure how well the residual ranks injected edges, using precision-recall AUC against the known injected set. The quaternion hypothesis predicts a clear gap over the complex ablation on order-violating noise and near-parity on random noise. Any other pattern is reported as it falls.

The second check traces accuracy against cost. On clean FB15k-237 we vary the per-node budget $L$ and plot MRR against measured wall-clock time and memory, checking whether the curve stays near the full-graph MRR at a small fraction of the edges.

The third check is ogbl-wikikg2 under clean conditions and 10% injected noise, compared with A*Net and ComplEx+RP on MRR, GPU-hours and peak memory.

The fourth check guards against self-confirmation. On clean data we track how many true test-adjacent edges fall outside the budget over training, with and without the moving-average copy and the per-relation floors.

Countries S3 serves as a sanity check that budgeted propagation does not destroy compositional reasoning.