Coverage, Not Depth: Fixing Score Collapse for Sparse Entities in Knowledge Graph Reasoning

Knowledge graph completion asks a model to fill in missing facts. Given a query such as (Marie Curie, born in, ?), the model ranks every entity in the graph as a possible answer. The strongest current systems propagate information outward from the query entity along relational paths. Every candidate answer then gets a representation built from the paths that reach it. When the graph is sparse, many candidates are reached by no path, or by only one weak path, within the model's few propagation steps. All of those candidates end up with nearly identical representations and nearly identical scores. The correct answer is then lost in a tie with thousands of wrong ones. This failure looks like over-smoothing, the familiar problem where deep graph networks blur all nodes into the same vector. The cause is different, though: the model has too little coverage of the candidate, not too many layers.

We propose to measure this "coverage collapse" directly and to fix it with a fusion rule that knows, for each query and each candidate, how much path evidence the local view actually has. The model combines two views. The first is a query-conditioned path propagator that is sharp where it has evidence. The second is a global view that scores every entity and does not depend on reachability. They are mixed with a per-candidate weight driven by a cheap, exactly computed count of the relational paths connecting query and candidate. The contribution is twofold. We provide a diagnostic: it splits the dominant model's errors into coverage-driven and depth-driven collapse, stratified by entity degree. We also provide a fusion rule whose key ingredient, the explicit coverage signal, is isolated against the obvious simpler alternatives.

Core Claim

The closest existing work is DuetGraph. It shows that stacking local message passing and global attention in sequence produces score over-smoothing, meaning the score gap between correct and incorrect candidates vanishes. It runs the two in parallel pathways joined by a single learned scalar, $H = \alpha H_{local} + (1-\alpha) H_{global}$, with the same $\alpha$ for every entity and query. DuetGraph attributes the collapse to interference between depth-wise smoothing operators.

Our claim is that on sparse graphs a large share of the remaining score collapse has another cause. It falls on candidates the local pathway barely reaches. These coverage-starved candidates are exactly where a single global $\alpha$ is wrong: the local view there contributes a shared, near-constant vector. Making the mixing weight depend on measured path coverage should therefore recover most of the low-degree loss that KG-Mixup attacks with data augmentation, without hurting dense entities.

This claim makes a falsifiable prediction that separates it from a plain degree story. Toward Degree Bias in Embedding-Based Knowledge Graph Completion reports that WN18RR "doesn't exhibit significant degree bias towards low-tail-relation degree triples." WN18RR is, however, hierarchical with long paths and low average degree, so coverage within a few hops should still be poor. If coverage rather than degree drives collapse, our gains should persist on WN18RR even though degree-based remedies have little to offer there.

Mechanism

The local view is a query-conditioned path propagator in the style of Neural Bellman-Ford Networks (NBFNet). It computes, in one pass, a representation for every candidate $v$ given the query entity $u$ and relation $q$, by learning generalized path sums. We reuse this method as-is; it supplies the expressive multi-hop reasoning that shallow models lack.

The global view scores every entity regardless of reachability. We test two instantiations. One is a shallow triplet embedding model trained with the inter-triple contrastive loss of KGE-CL, which pulls structurally disjoint but related entities together. The other is DuetGraph's global attention pathway.

Alongside the neural propagation we run a second, parameter-free propagation of a scalar. It computes the truncated, relation-typed path mass $c_q(u,v)$ reaching $v$ from $u$ within the same $L$ hops, which is essentially a Katz-style count. This is the classical heuristic NBFNet generalizes. Its cost is one sparse matrix-vector product per hop, negligible next to the neural pass. The fused score for candidate $v$ is

$$s(u,q,v) = g\, s_{local}(u,q,v) + (1-g)\, s_{global}(u,q,v), \qquad g = \sigma\big(a_q \log(1 + c_q(u,v)) + b_q\big),$$

where $s_{local}$ and $s_{global}$ are the two views' scores, $\sigma$ is the logistic function, and $a_q, b_q$ are learned per query relation. With two parameters per relation, the gate can only express "trust the paths in proportion to how many there are." That restriction is deliberate. It makes the coverage hypothesis testable rather than absorbed into a flexible network. The two views are trained jointly, with the gate fixed to $g=1$ and $g=0$ in alternate minibatches so that neither view collapses into reliance on the other.

Research Program

The first stage is diagnostic and stands on its own. We train NBFNet and DuetGraph on each benchmark. For every test query we record three quantities: the coverage $c_q$ of the true answer; the number of candidates whose score lies within a small margin of the true answer's score (a direct tie measure of score collapse); and whether the query fails. Errors are then split into three groups: failures where the answer had zero or near-zero coverage, failures where it had high coverage but scores were nonetheless homogenized, and the rest. This split is a concrete answer to the concern in Are we measuring oversmoothing in graph neural networks correctly? that feature-similarity metrics conflate distinct failure modes. We measure collapse at the level of ranking, where it costs accuracy, rather than with representation-similarity energies. We repeat the split while varying propagation depth $L$ from 2 to 8. This traces the local-global trade-off directly: deeper propagation raises coverage but, per Backward Oversmoothing, makes deep message passing harder to train. We expect a frontier on which no single depth is good for both sparse and dense entities.

The second stage builds the coverage-gated fusion and compares it against the baselines below. The third stage stress-tests sparsity in a controlled way. We delete 25%, 50%, and 75% of training edges at random, and separately delete edges preferentially from low-degree entities. This lets us check whether the gain grows as coverage shrinks.

The fourth stage is optional. On the Wiki-One and Wiki-ZS datasets of Challenging the Assumption of Structure-based embeddings, we replace the global structural view with a text-description view. This tests whether the same coverage gate correctly routes zero-coverage entities to text. That paper's BERT text view raised Wiki-ZS MRR from .184 to .437, so text is a strong global view where it exists.

Baselines

The naive reference point is NBFNet alone at its tuned depth, with no global view. It is the strongest single-view path model in the file, and the coverage-collapse diagnosis is a claim about its failures. On FB15k-237 the file reports only relative figures for it: an 18% relative Hits@1 gain over LowFER and 21% over DRUM, with roughly 3 million parameters. We report our own reproduced absolute numbers and check that they are consistent with those relative gains.

The strongest existing method on this exact question is DuetGraph. Its parallel local-global design with a global scalar gate is the closest prior system. The file gives only an aggregate "up to an 8.7% improvement in Hits@1" across FB15k-237, WN18RR, YAGO3-10, and NELL-995, plus reported training and inference speedups. We found no reported per-dataset absolute result on Lacuna for DuetGraph, so we will rerun it ourselves.

As the published anchor for absolute numbers we use KGE-CL. It reports MRR 37.8% and Hits@1 28.6% on FB15k-237, MRR 51.2% and Hits@1 46.8% on WN18RR, and MRR 59.1% and Hits@1 51.8% on YAGO3-10 KGE-CL. This model also serves as one of our global views.

The sparsity-specific baseline is ConvE or TuckER trained with KG-Mixup, which reports low-degree MRR gains of 9.8% and 5.3% over standard training.

Three ablations isolate the key ingredient. The first is a fixed-weight score ensemble of NBFNet and the global view, with the weight tuned on validation. The second is a learned per-candidate gate: a small network over the concatenated hidden states of the two views, with no coverage input. The third is a gate fed by tail-relation degree instead of path coverage. All methods share the same training splits, filtered ranking evaluation, embedding dimension budget, and an equal hyperparameter-search budget measured in GPU-hours. Every method gets the same number of random-search trials over learning rate, depth, and dimension.

Beating the field requires two things. Overall MRR and Hits@1 must be at least as good as DuetGraph's on every dataset. On the lowest quartile of tail-relation degree and of answer coverage, Hits@1 must improve significantly over DuetGraph and over the fixed ensemble, across five seeds.

Why not just…?

Why not just ensemble NBFNet with a shallow embedding model at a fixed weight? This is the most serious threat. A fixed blend already lets the global view break ties among unreached candidates, because when $s_{local}$ is constant across those candidates, any added $s_{global}$ reorders them. The difference should show up where both views carry signal but differ in reliability. For a high-coverage candidate, a fixed blend dilutes a sharp path score with a noisier global one. For a weakly covered candidate it under-weights the global view. Our prediction is therefore specific. The fixed ensemble should match us on zero-coverage answers and lose on the high-coverage and low-but-nonzero-coverage strata. If it matches us on every stratum, the method contribution is void. We would then report the diagnostic, plus the finding that a tuned ensemble suffices, as the result.

Why not just learn a per-candidate gate from the hidden states? A flexible gate could in principle detect "this candidate was not reached," since unreached candidates share a near-constant local state. It cannot easily tell one spurious path from five consistent ones, and with millions of candidate-query pairs it can overfit to frequent relations. The comparison against our two-parameter coverage gate directly tests whether an explicit count adds anything beyond what the hidden states already reveal. We also report the reverse case: adding the coverage scalar as an input to the flexible gate. If that hybrid wins, the claim narrows to "coverage is a useful feature" rather than "coverage is the right gate."

Why not just propagate deeper so every candidate is covered? Deeper propagation raises coverage, but the over-smoothing literature summarized in the file, and the gradient analysis in Backward Oversmoothing, predict degraded separation and harder training. The depth sweep in stage one measures exactly this trade-off. If some depth gives near-full coverage without loss on dense entities, our method is unnecessary at that depth. We would report that honestly.

Why not just apply KG-Mixup or text descriptions to fix sparse entities? KG-Mixup addresses degree, not path coverage, and the file itself notes it has nothing to target on WN18RR. That makes WN18RR the decisive dataset for separating the two explanations. Text views are powerful where text exists, but many domains have none. Our structure-only setting covers those cases, and the stage-four experiment treats text as just another global view under the same gate rather than as a competitor.

Proposed Experiments

The main experiments run on FB15k-237, WN18RR, NELL-995, CoDEx-M, and YAGO3-10. We report filtered MRR and Hits@1/3/10, each additionally broken down by quartiles of tail-relation degree and of true-answer coverage $c_q$. We also report a collapse statistic: the number of candidates scored within a fixed margin of the true answer. The edge-deletion variants of FB15k-237 and CoDEx-M provide the controlled sparsity sweep. Wiki-One and Wiki-ZS provide the text-view extension.

Three checks decide the outcome. The first is the diagnostic. On at least three datasets, a majority of NBFNet and DuetGraph Hits@1 failures on low-degree entities must fall in the low-coverage stratum rather than the high-coverage, homogenized one. If not, coverage is not the main story and the proposal collapses to DuetGraph's account. The second is the WN18RR prediction. The coverage gate should beat both the degree gate and KG-Mixup on WN18RR, where degree bias is reportedly absent. The third is the ablation ordering. The coverage gate must beat the fixed ensemble on low-but-nonzero-coverage answers, and its advantage over DuetGraph must widen monotonically as training edges are deleted. If the advantage is flat across deletion levels, the gain is not about sparsity. All results are averaged over five seeds, with paired bootstrap confidence intervals over test queries.