Relation-Gated Sparse Attention for Knowledge Graph Completion

Knowledge graphs store facts as triples such as (New York, locatedIn, USA), and link prediction asks a model to fill in the missing end of a query like (New York, headquarteredIn, ?). The standard approach gives every entity one fixed vector, even though "New York" behaves like a place for some relations and like a legal or financial body for others. Graph neural networks, which update each entity's vector by mixing in messages from its neighbours, look like the obvious way to make entity vectors depend on context. The evidence says they do not deliver. When Are Message Passing Neural Networks Really Helpful for Knowledge Graph Completion? replaced the neighbour-mixing layers of CompGCN with a plain per-entity MLP, performance on FB15k-237 stayed exactly the same, at 35.5% MRR.

This note argues that the failure has a specific, measurable cause and a specific fix. Neighbour mixing in knowledge-graph encoders is query-blind, and its attention weights can never reach zero. Every entity therefore absorbs the same blurred average of its whole neighbourhood, whichever relation is being asked about. That is over-smoothing: node vectors become more alike as layers are stacked. Here it shows up along exactly the axis that link prediction needs to keep distinct. We propose to compute neighbour weights separately for each query relation, using a normalization that can set weights to exactly zero. Each relation then gets its own sparse propagation graph, which breaks the connectivity condition that proofs of attention-driven collapse rely on. We also propose a relation-conditioned rank diagnostic that tests whether this is the mechanism at work.

Core Claim

Two claims can each be checked independently. The diagnostic claim is that relational message-passing encoders reach only parity with MLPs because, for a given query relation, the relation-specific views of the entities that the decoder actually scores lose rank as neighbour mixing is applied. We expect this per-relation rank to track per-relation MRR, much as Effective Rank tracks node-classification accuracy in homogeneous graphs.

The method claim is that relation-conditioned attention with exact zeros prevents this loss and turns message passing into a measurable gain over the MLP. The argument for why this should work comes from Demystifying Oversmoothing in Attention-Based Graph Neural Networks. That paper models stacked attention layers as products of time-varying averaging matrices. It proves exponential collapse toward a rank-one representation within each connected component. The proof leans on the fact that softmax gives every edge positive weight, so attention can never disconnect the graph. If the per-relation effective graph splits into $c_q$ components, the same theorem predicts collapse only within components. The deep-limit rank for relation $q$ is then bounded below by roughly $c_q$ instead of 1. We do not escape the theorem. We change its premise, and we do so differently for each relation.

Research Program

The encoder keeps a static base vector $\mathbf{e}_i$ for each entity as an anchor, together with learned relation vectors in the style of Composition-based Multi-Relational Graph Convolutional Networks. At layer $l$ and for query relation $q$, entity $i$ weights each neighbour $j$, reached by an edge of relation $r_{ij}$, as

$$\alpha^{(q)}_{ij} = \mathrm{sparsemax}_{j \in \mathcal{N}_i}\left(\mathbf{a}_q^{\top}\left[\mathbf{W}\mathbf{h}^{(q)}_i \,\|\, \mathbf{W}\,\phi(\mathbf{h}^{(q)}_j, \mathbf{r}_{ij})\right]\right).$$

In this expression, $\mathbf{h}^{(q)}_i$ is entity $i$'s representation specialised to query relation $q$, initialised at $\mathbf{e}_i$. $\phi$ is CompGCN's composition of a neighbour vector with its edge relation vector. $\mathbf{W}$ is a shared projection, and $\mathbf{a}_q$ is a per-query-relation attention vector drawn from a small low-rank basis, which avoids the per-relation parameter blow-up seen in TransR. Sparsemax projects scores onto the probability simplex. Unlike softmax, it returns exact zeros for low-scoring neighbours.

The output $\mathbf{h}^{(q)}_i$ is a context-dependent entity vector. It is the message-passing counterpart of what TransH does with a single projection per triple. The difference is that here the context is assembled from the neighbourhood that matters for $q$.

Conditioning on the query relation rather than the full query (head, relation) is a deliberate cost choice. FB15k-237 has 237 relations, so one propagation per relation in each batch keeps compute within a small constant of CompGCN. It also keeps the 1-to-N scoring used by Convolutional 2D Knowledge Graph Embeddings, and Li et al. show that this scoring accounts for much of the variance in reported results.

The diagnostic adapts the Effective Rank of Are we measuring oversmoothing in graph neural networks correctly?. That paper showed Effective Rank, unlike Dirichlet energy, tracks accuracy, with an average Pearson correlation of 0.91. It studied only single-relation node classification. For each query relation $q$, we stack the decoder's inputs over all entities into a matrix $\mathbf{X}_q$ and compute

$$\mathrm{Erank}(\mathbf{X}_q) = \exp\Big(-\sum_k p_k \ln p_k\Big), \qquad p_k = \sigma_k / \textstyle\sum_m \sigma_m,$$

where $\sigma_k$ are the singular values of $\mathbf{X}_q$. For query-blind encoders, $\mathbf{X}_q$ is the shared entity matrix composed with $\mathbf{r}_q$. Zhang et al. caution that high rank is necessary but not sufficient, since random noise has maximal rank. We therefore read the diagnostic only jointly with MRR, never as a target on its own. We also track the fraction of retained edges and the component count $c_q$ for each relation. These two numbers show whether sparsity is doing structured work or has quietly cut every edge and turned the model back into an MLP.

Baselines

The naive reference point is the MLP counterpart from Are Message Passing Neural Networks Really Helpful for Knowledge Graph Completion?. It applies the same encoder with the adjacency set to the identity, so each entity sees only its own static vector, and it is paired with the same decoder and loss. It is the most important competitor because it is the claim this proposal must overturn. The file reports that it matches full CompGCN at 35.5% MRR on FB15k-237. The file also reports a 47.2% MRR for CompGCN on WN18RR under all-entity negatives, a figure given for the full model with no separate MLP number. We will rerun the MLP with the identical ConvE-style decoder, all-entity 1-to-N cross-entropy, embedding size, and a matched hyperparameter search budget per model, across five seeds.

The strongest existing message-passing encoders are CompGCN and DisenKGAT. CompGCN reports 0.355 MRR on FB15k-237 with circular correlation. DisenKGAT splits each entity into several independent components with relation-aware attention routing, and reports 0.368 MRR on FB15k-237. It is the closest prior attempt to let entity vectors vary with context under attention. It uses dense softmax and a fixed number of components, and it is not conditioned on the query relation during aggregation. For DisenKGAT on WN18RR, no reported result was found on Lacuna.

KBGAT reports 0.518 and RGHAT reports 0.522 MRR on FB15k-237. These numbers sit far above everything else in the file. Li et al. note that KBGAT's gains are disputed once they are separated from its decoder and its sampling of negative examples, so we treat these figures as not comparable under a shared protocol. We will reimplement both under our protocol rather than quote them.

Beating the baselines means two things. At matched depth (2 layers), our model must exceed both the rerun MLP and the rerun DisenKGAT in MRR by more than twice the seed standard deviation. At depths of 4 to 8 layers, it must hold or improve MRR while the dense encoders decline.

Two ablations isolate the key ingredient. The first keeps relation-conditioning but uses softmax. The second keeps sparsemax but uses a single query-blind attention vector. A third control keeps a random subset of edges per relation at our model's retained-edge rate. It tests whether any sparsification helps or only learned, relation-specific sparsification does.

Why not just…?

Why not just use the MLP, since it already matches message passing? For current encoders this is the honest default, and it is the null hypothesis of the whole project. Li et al. establish parity only for query-blind, dense encoders. They do not show that neighbourhoods carry no usable signal. The large gap RGHAT reports between standalone ConvE (0.325) and ConvE with its attention encoder (0.522) hints that they might, though that comparison is confounded by protocol. If our model at matched budget does not beat the rerun MLP, the method claim fails. We would then report the diagnostic result as the contribution.

Why not just add residual connections or an anchoring energy term? This is a real threat. Descent Steps of a Relation-Aware Energy Produce Heterogeneous Graph Neural Networks (HALO) derives skip connections that anchor each node to its input features from a relation-aware energy, and it resists collapse on AIFB, MUTAG, BGS and AM. Wu et al. note that residuals and normalization delay collapse without removing it. Anchoring alone may be enough at practical depths, however. We therefore give every dense baseline, including the softmax ablation, the same initial-residual anchor to $\mathbf{e}_i$. If the anchored dense relation-conditioned model matches ours, sparsity is not the ingredient and we will say so.

Why not just cap the neighbourhood with fixed top-k or random sampling? Hard truncation also disconnects the graph, and it is cheaper. The difference is that it cuts the same edges for every query relation, so it cannot give "New York" a different effective neighbourhood under locatedIn than under headquarteredIn. The random-edge control at a matched retention rate tests this directly. A query-blind top-k run tests it as well.

Why not just use relation-specific projections like TransH or affine maps? Relation-specific affine maps and hyperplane projections make entity vectors depend on context cheaply, but only from the entity's own vector. Our decoder-side composition already includes such a projection, so the MLP baseline covers this alternative. Any gain over it must come from the neighbourhood.

Proposed Experiments

The main runs cover FB15k-237 and WN18RR, where inverse-relation leakage has been removed, following Observed versus latent features for knowledge base and text inference and ConvE. NELL-995 serves as a third link-prediction set. We report MRR and Hits@1/3/10 under filtered, all-entity ranking.

The first decisive check is a depth sweep over 1, 2, 4, 8 and 16 layers for the MLP, CompGCN, DisenKGAT, the two ablations and our model. We plot per-relation Erank and MRR together. The diagnostic claim predicts that the correlation between per-relation Erank and per-relation MRR, computed across relations and depths, is strongly positive for dense encoders. It also predicts that dense encoders lose rank fastest on relations whose head entities have many distinct neighbour relation types.

The second check stratifies test queries by head-entity degree and by the number of distinct relation types around the head, as a proxy for how many roles the entity plays. Our gains over the MLP should be concentrated on high-degree, multi-role heads. A uniform gain would point to extra capacity rather than context-dependence.

The third check links the theory to observation. For each relation, we report the component count $c_q$ of the learned sparse graph and test whether deep-layer Erank stays above $c_q$ while dense variants approach 1 on the same relation.

As a secondary check on entity classification, we run AIFB, MUTAG, BGS and AM against HALO, where the query relation is replaced by the target label head. CompGCN's reported 85.3% on MUTAG serves as the reference point.

The project fails cleanly if any of three outcomes occurs. The learned graphs could keep almost no edges, which means we have rebuilt the MLP. The anchored softmax ablation could match the full model, which means sparsity is unnecessary. Or no configuration could beat the rerun MLP beyond seed noise, which would support Li et al.'s conclusion at the level of mechanism as well as outcome.