Do Knowledge Graph Embeddings Learn Types First?

Knowledge graph embedding models fill in missing facts such as <Marie_Curie, nationality, ?>. They do this by scoring every entity in a shared vector space, and they regularly propose answers of the wrong kind, like Paris instead of France. The usual fixes bolt typing on from outside. They filter candidates with a type catalog, sample negatives within types, or add gates and geometric penalties. This proposal asks a different question: does gradient descent already contain a type-first learning phase that we are accidentally destroying?

The factorization models that dominate this task are multiplicative. A canonical polyadic (CP) decomposition writes the (subject, relation, object) tensor as a sum of rank-one pieces. Theory shows that such models, started from very small random weights, fit their data greedily, one rank-one piece at a time, with the strongest structure first. In a knowledge graph, the strongest and most repeated structure is arguably the type signature: which kinds of entities can fill which slots of which relations. We hypothesize that small-initialization gradient descent learns type compatibility before individual facts, and that category errors largely come from training choices that skip this ordering. Those choices include large initialization and fitting fine-grained components early. If the hypothesis holds, it gives a mechanistic account of why category errors happen. It would also suggest a simple, catalog-free fix: a reparametrized type gate whose own implicit bias yields sparse, non-negative entity-type memberships.

Core Claim

We model the observed graph as a type-compatibility mask multiplied elementwise by a sparse fact pattern. The mask is low-rank, with rank bounded by the number of distinct relation signatures. Its entries are densely supported across many triples, so gradient flow from initialization scale $\alpha \to 0$ should grow components aligned with the mask's leading directions before components that encode individual facts.

The first testable consequence is about timing. The rate of top-ranked answers that violate a relation's domain or range should fall to a low plateau early in training, before mean reciprocal rank (MRR) saturates. The second consequence is that this early drop should weaken as $\alpha$ grows. The third is that removing the earliest-learned components should sharply raise violations while barely changing the ranking of type-correct candidates.

The constructive half of the proposal replaces the sigmoid type gates of TypeDM with Hadamard-squared type factors. We write $\text{score}(s,r,o) = f(a_s,b_r,a_o)\cdot\langle u_s^{\odot 2}, v_r^{\odot 2}\rangle\cdot\langle u_o^{\odot 2}, w_r^{\odot 2}\rangle$. Here $f$ is the base CP or ComplEx score on identity vectors $a,b$. The vectors $u_e$ hold entity-type loadings, and $v_r, w_r$ hold the expected subject and object types of each relation. The squares keep type compatibility non-negative without projection, and small initialization should bias each $u_e$ toward few active types.

Relation to Prior Work

Three papers supply the mechanism.

Implicit Regularization in Tensor Factorization proves greedy, staircase-like rank growth in CP factorization under small initialization. It tests this only on synthetic tensors and MNIST, and never asks whether the early components carry relational semantics. Its analysis also uses squared loss on observed entries, whereas knowledge graph completion uses softmax cross-entropy. That mismatch is exactly what we must verify empirically rather than assume.

Get rid of your constraints and reparametrize shows that Hadamard powers replace non-negativity constraints and induce an $\ell_1$ bias, but only for linear non-negative least squares. Implicit Regularization for Group Sparsity shows that magnitude-direction reparametrizations select groups by "rich get richer" dynamics, again only for linear regression. We borrow both reparametrization ideas for the type gate. We make no claim that their proofs carry over to the multilinear setting.

Two papers motivate the problem.

Type-Sensitive Knowledge Base Inference Without Explicit Type Supervision reports that nearly 20% of top predictions of standard models on FB15K are of the wrong type. Its multiplicative sigmoid gates lift DistMult from 0.674 to 0.750 MRR. The paper does not study how the gates are learned, and our proposal is essentially the dynamical analysis it leaves open, plus a gate designed around that analysis.

Canonical Tensor Decomposition for Knowledge Base Completion makes CP competitive through reciprocal triples, an explicit nuclear 3-norm (N3) penalty, and full softmax loss. It reports 0.86 MRR on FB15K and 0.48 on WN18RR, uses no typing, and never examines the unregularized training trajectory. Its public codebase, facebookresearch/kbc, is our experimental base.

Several papers constrain the design.

Explicit-typing methods show typing helps but depend on external knowledge. Type-Constrained Representation Learning in Knowledge Graphs derives pseudo-types under a local closed-world assumption. CAKE induces concept rules and filters candidates, reporting relative MRR gains of 11.5% on FB15K-237 and 16.7% on NELL-995. Domain Representation for Knowledge Graph Embedding fits relation-domain ellipsoids after training. All three either rely on observed slot fillers or on a second training stage. We ask whether a single gradient-descent run produces the boundary.

Observed versus latent features for knowledge base and text inference shows that 81% of FB15K test triples leak through inverse edges. We therefore treat FB15K only as a sanity check.

Research Program

The program has four parts.

The first part is theory in a planted setting. We build synthetic graphs with $c$ entity types, a known set of relation signatures, and sparse facts inside the allowed blocks. We then study gradient flow for CP under both squared loss and softmax loss. The target is a statement that, with small initialization, the span of the first learned components approaches the span of the type-indicator vectors before any fact-level component grows. The statement should include a dependence on how the mask's energy compares with the fact pattern's.

The second part is measurement on real data. For CP and ComplEx trained with and without N3, we track two quantities over training at several initialization scales. The first is the type-violation rate at $k$: the fraction of top-$k$ candidates outside the relation's domain or range, as given by the Freebase type catalog on FB15K-237 and the category ontology on NELL-995. The second is how well the earliest-grown components linearly predict catalog types.

The third part is intervention. We remove, freeze, or reinitialize the first-grown components and measure the effect on violations and on MRR among type-correct candidates.

The fourth part is the Hadamard-squared type gate. We train it from small initialization and compare it against sigmoid gating and explicit filtering.

Baselines

The naive reference point is CP or ComplEx trained with the standard kbc recipe at default initialization, with no typing of any kind. It fixes the violation rate we must reduce. On FB15K, Type-Sensitive Knowledge Base Inference Without Explicit Type Supervision suggests this rate is around 20%. We found no reported violation-rate result on Lacuna for CP-N3 or on FB15K-237.

The strongest untyped competitor is CP-N3 with reciprocal triples from Canonical Tensor Decomposition for Knowledge Base Completion. It reports MRR 0.86 on FB15K and 0.48 on WN18RR. Because N3 already pushes toward low rank explicitly, it is the most direct rival to the claim that implicit low-rank dynamics produce typing.

The strongest catalog-free typed competitor is TypeDM/TypeComplex, with FB15K MRR 0.750 in its paper. The strongest typed competitor with external knowledge is CAKE on the same backbones, with relative MRR gains of 11.5% on FB15K-237.

All methods run from the same codebase, splits, embedding budget, and number of epochs. Each receives the same hyperparameter search grid, with initialization scale added as a searched hyperparameter for every method rather than only ours.

Beating these baselines means cutting the type-violation rate relative to CP-N3 at no MRR loss on FB15K-237 and WN18RR. It also means matching or beating TypeComplex on MRR without its sigmoid gates, and approaching CAKE's violation rate without concept rules.

The key ablation keeps the Hadamard-squared gate but uses large initialization. If the gains disappear, the implicit bias rather than the architecture is doing the work.

Why not just…?

Why not just filter candidates with pseudo-types observed in training? Test-time filtering using the local closed-world rule of Type-Constrained Representation Learning in Knowledge Graphs is cheap and may match us on standard splits, so it is a real threat. Its weakness is that it excludes any entity never yet seen in a slot, which is the reporting bias the file flags. We will build a held-out-slot split: test triples whose answer entity never fills that relation's slot in training, but whose catalog type is valid. On this split, filtering must fail by construction, while a learned type space can generalize. If we do not win there, the constructive half of the proposal is not worth pursuing.

Why not just use CP with the N3 penalty, since it already enforces low rank? It may. If CP-N3 shows the same early violation drop and the same component-removal effect, our finding becomes an explanation of why N3 works rather than a new method. That would still be a useful diagnostic result, and we will report it as such. The two could still differ because N3 penalizes all components by their magnitude, whereas greedy dynamics impose an order. The timing curves and the removal experiment separate order from magnitude.

Why not just use TypeDM's sigmoid gates? Sigmoid gates are bounded and dense, so nothing pushes an entity to commit to few types. The Hadamard-squared gate is predicted to produce sparse type memberships at small initialization. We test this directly through two measures. The first is the sparsity of $u_e$. The second is the agreement of $u_e$ with catalog types on multi-typed entities, which are the noisy case where CAKE is known to be fragile.

Decisive Checks

The project hinges on three checks, run on FB15K-237, WN18RR, and NELL-995, with FB15K reported only for comparison with the literature.

The first check is timing. At small initialization, the type-violation rate should plateau well before MRR does, and the gap between the two should shrink monotonically as initialization grows.

The second check is causal. Removing the first few learned components should raise violations sharply while leaving the ranking among type-correct candidates nearly unchanged. Removing late components should do the reverse.

The third check is generalization. On the held-out-slot split, the small-initialization Hadamard gate should beat pseudo-type filtering in MRR and should match CP-N3 on the standard splits.

If the timing check fails under softmax loss, the greedy-typing story is wrong for real training, and we would report that as a negative result on transferring tensor implicit-bias theory to relational data.