Certifying Knowledge Graph Embeddings by Bits per Entity

Knowledge graph embedding models predict missing facts, such as which entity completes (Paris, capital_of, ?). They are trained on millions of observed facts, and they generalize well. Yet no mathematical guarantee says how well. Every existing generalization bound for these models evaluates to more than 100% error, so it certifies nothing. This proposal argues that the reason is the same thing that makes these models hard to scale. Each entity gets its own vector of free parameters, so model complexity grows with the number of entities at the same rate as the training data.

Compositional and discrete embeddings break that link. They were built to fit huge graphs into memory. Instead of a private vector per entity, they assemble each entity from a shared vocabulary: nearby "anchor" nodes and relation types in NodePiece, or a few bits of discrete code in KD codes. Our claim is that this memory saving is also a compression argument. If we count how many bits the trained model needs per entity, and compare that with how many training facts each entity appears in, we get the first non-vacuous risk certificates for link prediction. We also get a simple quantity that predicts which scalable embedding schemes can be certified at all.

Core Claim

An Occam-style bound charges a deterministic model for the length of its shortest description: the model's error on unseen data is at most its training error plus a penalty that grows with description length divided by the number of training samples. For a lookup-table embedding, description length is at least $|V|$ (the number of entities) times the bits stored per entity. The number of training facts is roughly $|V|$ times the average entity degree. The penalty therefore behaves like bits-per-entity divided by facts-per-entity. With 32-bit floats in hundreds of dimensions and typical degrees, that ratio is far above one. This explains, rather than merely restates, why Lee et al.'s PAC-Bayesian bounds for knowledge graph learning and Liao et al.'s bounds for message-passing networks grow with embedding dimension and stay above 1.0.

The two compressed designs change the ratio in different ways. KD codes represent each entity as $D$ symbols from a $K$-way alphabet, so they cost $D\log_2 K$ bits per entity plus a shared decoder. NodePiece assigns zero free bits per entity once its tokenization is fixed, so its description length does not grow with $|V|$ at all. We predict three outcomes. First, NodePiece-style models can be certified non-vacuously on large graphs. Second, KD codes can be certified only where average degree exceeds their per-entity code length. Third, uncompressed lookup tables cannot be certified, even after post-hoc pruning and quantization.

What is new here is the per-entity accounting. The other new piece is the device that makes it valid for graph-derived tokenizations, described next.

The Certificate and Its One Subtlety

We certify a bounded, per-fact loss. For a held-out fact (h, r, t), the loss is 1 if the true tail is not ranked in the model's top 10 among all entities, and 0 otherwise. The certified quantity is therefore the expected Hits@10 failure rate, and we also report Hits@1. We assume the observed facts are an i.i.d. sample from a fixed population of true facts over a fixed entity set. Random edge splits, as used on FB15k-237, are meant to approximate this assumption.

The obstacle is that NodePiece computes each entity's tokens from the training graph itself: which anchors are nearest, at what distance, and which relational context edges surround it. A coding prior that depends on the training sample is invalid. Our fix borrows the coupling idea from Biggs and Guedj, who trained a prior on a 60% data subset.

We split the training facts into a tokenization set $S_{tok}$ and a fit set $S_{fit}$ of size $n$. Anchors, distances, relational contexts, and the filtering of known positives at ranking time are all computed from $S_{tok}$ alone. Given $S_{tok}$, each entity's tokens are fixed. The trained model is then specified entirely by a bitstring: the quantized, pruned anchor and relation vocabulary plus the encoder weights. Its loss on any fact depends only on that fact, so the per-fact losses on $S_{fit}$ stay independent.

The bound is the standard Occam/PAC-Bayes inequality in its binary-KL form, the form that grew out of Langford's PAC-Bayes work and was applied to compressed networks in the ImageNet-scale compression bound:

$$R(h) \le \mathrm{kl}^{-1}\!\left(\hat R_{fit}(h),\ \frac{L(h)\ln 2 + \ln(1/\delta)}{n}\right),$$

The symbols are as follows. $R(h)$ is the true Hits@10 failure rate of model $h$. $\hat R_{fit}(h)$ is its failure rate on $S_{fit}$. $L(h)$ is the length in bits of $h$ under a prefix code fixed after seeing $S_{tok}$. $\delta$ is the failure probability. $\mathrm{kl}^{-1}(q,c)$ is the largest $p$ whose binary KL divergence from $q$ is at most $c$.

The model may be trained on all of $S_{tok}\cup S_{fit}$, because the bound holds uniformly over all bitstrings. Because the bound applies to the deterministic quantized model directly, it avoids the derandomization factor of 2 that loosens majority-vote PAC-Bayes bounds.

The scaling claim follows from the penalty term. The penalty is $L(h)\ln2/n$. For lookup tables $L(h)\propto |V|$ and $n\propto |V|\cdot\text{degree}$, so the penalty is roughly bits-per-entity over degree. For NodePiece, $L(h)$ is roughly constant in $|V|$, so the penalty falls as the graph grows.

Research Program

The first component is the bound itself, implemented as a coding scheme for each architecture. For lookup tables, the scheme codes pruned, quantized per-entity vectors, following the compression approach. For KD codes, it codes per-entity symbols plus the decoder. For NodePiece, it codes the vocabulary and encoder only. Each scheme uses a self-delimiting code for sparsity patterns and codebooks, so that $L(h)$ is an honest prefix-code length.

The second component is an analysis of the split fraction. A larger $S_{tok}$ gives better tokens but leaves a smaller $n$. NodePiece's own limitation on sparse, high-diameter graphs such as WN18RR, where anchors are far away and uninformative, appears here as a measurable cost: the tokenization quality lost when $S_{tok}$ shrinks.

The third component addresses the criticism that compression bounds are purely post-hoc. We add the description-length penalty as a training regularizer: an $\ell_0$/quantization-aware penalty on the vocabulary and encoder. We then test whether bound-aware training tightens certificates without costing test accuracy.

The fourth component explains the empirical observation that compression sometimes improves accuracy. Examples are Sachan's compressed TransE reaching MRR 0.477 against 0.463 uncompressed on FB15k, and MCNE's Micro-F1 of 0.309 against 0.302 for Node2Vec on DBLP. We test whether the measured train–test gap tracks bits-per-entity over degree across all architectures.

Baselines

The naive reference point is an uncompressed lookup-table model, TransE and RotatE trained with standard recipes, certified with the same Occam bound at 32 bits per parameter. We expect this certificate to be vacuous everywhere. It anchors the comparison and checks that our coding is not accidentally loose.

The strongest existing certification approach for deep models is post-hoc pruning plus quantization of that same lookup table, exactly as in the ImageNet-scale PAC-Bayesian compression bound. That paper certified MobileNet-0.5 at a top-5 error bound below 89% against roughly 13% empirical error, and LeNet-5 on MNIST below 46% against roughly 1%. It is the strongest competitor because it is the only demonstrated route to non-vacuous bounds at scale. We run it with the same split, the same total compute, and the same hyperparameter search budget over sparsity and bit-width as our method. Our method beats it if, at matched test Hits@10, it certifies a lower failure rate on every dataset, with the advantage growing with $|V|$.

For graph bounds specifically, Lacuna has no reported result for any non-vacuous generalization bound on a knowledge graph benchmark. Lee et al. report trends without scalar certificates. We evaluate their bound on our trained models only as a reference.

For accuracy, the strongest reported compressed models are Sachan's KD-code TransE (MRR 0.477 on FB15k) and NodePiece. NodePiece reports retaining 90% of full-model performance on WN18RR with 500 anchors, and using 6.9M parameters versus roughly 500M+ for shallow models on ogbl-wikikg2. We require our certified models to stay within a small, pre-declared margin of these.

The ablation that isolates the key ingredient keeps the NodePiece architecture fixed and varies only per-entity free bits. At one extreme, each entity's tokens are supplemented with a private learned vector of $b$ bits. At the other, $b=0$. If the claim is right, the certificate should degrade with $b$ at fixed accuracy. A second ablation removes the tokenization split, computing tokens from all data. It quantifies how much the validity fix costs, though the bound from that variant is not reported as a certificate.

Why not just…?

Why not just use a held-out test-set bound? This is the real threat, and we treat it as a baseline rather than dismiss it. A Hoeffding or binomial bound on a large KG test split is cheap and probably tighter than ours on big datasets. Our bound has a different purpose. It certifies a model trained on all available facts. Pick-to-Learn showed this matters: on a 200-point regression task it achieved actual risk 0.064 with bound 0.172, while the test-set approach achieved 0.173 and 0.250 because it trained on 80% of the data. Our bound also supplies a design quantity, bits per entity, which a test split cannot. We report the test-set bound computed with the same total number of facts, and say plainly where it wins. We expect it to win on WikiKG2 and lose on smaller or sparser graphs.

Why not just tighten the metric-space bounds of Suzuki et al.? Their local Rademacher analysis cut the sample size needed to separate hyperbolic from Euclidean embeddings on a toy tree from $7.30\times10^{72}$ to $1.19\times10^9$. That is still far beyond benchmark sizes, and the analysis covers only pairwise losses on uncompressed coordinates. Our bound does not try to beat their rates. It sidesteps the coordinate-volume problem by counting bits, and we evaluate on the same synthetic 5-ary tree to compare the two directly.

Why not just apply pruning and quantization to TransE, as the vision work did? This is our strongest baseline, and the per-entity accounting predicts its failure. Even aggressive quantization leaves some bits per entity. On low-degree graphs such as WN18RR, the penalty term then stays near or above the empirical risk. If post-hoc compression of a lookup table matches compositional models, our central claim is wrong, and the experiment is designed to show that.

Why not just use KD codes instead of NodePiece? We include KD codes as a full arm. They are the natural middle case, with nonzero but small per-entity cost. The theory predicts they certify only where degree exceeds their code length. Whether they or NodePiece certify better on a given graph is an outcome of the study, not an assumption.

Proposed Experiments

We evaluate on FB15k-237, WN18RR, CoDEx-M and CoDEx-L, YAGO3-10, and ogbl-wikikg2 from the Open Graph Benchmark. Together these span dense to sparse graphs and tens of thousands to millions of entities. The synthetic 5-ary tree gives a direct contact point with Suzuki et al.

For each dataset and architecture, we report four things: test Hits@10 and Hits@1 failure, the certified bound at $\delta=0.05$, the description length $L(h)$, and the bits-per-entity over facts-per-entity ratio. Lookup, compressed lookup, KD codes, and NodePiece all share split, compute, and tuning budgets. We sweep the tokenization fraction over a small grid, including 0.6 to match the coupling choice of Biggs and Guedj.

There are four decisive checks. The first is whether NodePiece certificates fall below 1.0, and ideally well below, on FB15k-237 and ogbl-wikikg2 while lookup-table certificates stay vacuous. The second is whether the certificate and the measured generalization gap both line up with the bits-per-entity ratio across all arms and datasets, with WN18RR as the predicted hardest case. The third is a randomization test mirroring the random-label check in the compression paper: when tails in the training facts are shuffled, models should become incompressible and certificates should become vacuous. If they do not, our coding is leaking information. The fourth checks whether bound-aware training lowers certificates relative to post-hoc compression at equal test accuracy.

A negative result on the first check, together with a positive result on the post-hoc lookup baseline, would refute the proposal's thesis.