🤖 AI

On the Theoretical Limitations of Embedding-based Link Prediction

本文证明了知识图谱嵌入模型中的线性输出层会产生秩瓶颈（rank bottlenecks），从而限制了随着图规模和连通性增加时的表达能力，并提出了一种参数高效的基于混合的非线性输出层，该层在理论和实证上克服了这些局限性，从而提升了在大型、稠密数据集上的性能。

原作者： Samy Badreddine, Emile van Krieken, Luciano Serafini

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Samy Badreddine, Emile van Krieken, Luciano Serafini

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

核心理念：“太小的桌子”问题

想象一下，你正在试图整理一个庞大的图书库（知识图谱）。你希望计算机能够预测哪些书应该放在一起。为了实现这一点，计算机给每本书和每种关系都发了一张“身份证”（嵌入/Embedding），这是一组简短的数字列表。

通常，这些身份证是短小且简单的（低维），就像一个 10 位的电话号码。但这个图书馆里却有数百万本书（高维输出空间）。

论文指出，目前大多数计算机模型都试图利用一个线性输出层，将这些短小的身份证与庞大的图书馆进行匹配。你可以把这一层想象成一张又小又平的桌子，你试图把所有的书都摆放在上面。

问题所在： 如果你有 100 万本书，但你的桌子只能容纳 100 件物品，那么你在物理上是不可能把所有书都按正确的顺序摆放出来的。无论你的身份证多么聪明，桌子都太小了，无法承载所有的排列组合。论文称之为**“秩瓶颈”（Rank Bottleneck）**。这就像试图把一个 3D 雕塑强行压扁到一张 2D 纸上；你会丢失信息，并且无法表现出完整的形状。

我们尝试“阅读”图书馆的三种方式

作者研究了我们使用这些模型的三种不同方式，并展示了当图书馆变得巨大时，“小桌子”是如何让这三种方式全部失效的：

排序（谁是第一名？）： 我们想知道哪本书是最完美的匹配。
- 限制： 如果图书馆非常庞大，小桌子无法创造出足够多的独特“高度”来正确排序每一本书。总会有一些书被排错位置。
符号重构（是或否？）： 我们想知道一本书是否属于某个类别（真/假）。
- 限制： 小桌子无法画出足够清晰的“是”和“否”区域。这就像试图只用两种颜色来绘制一张复杂的地图；你无法展现细节。
分布（可能性有多大？）： 我们想知道匹配的具体概率。
- 限制： 小桌子迫使概率呈现出一种僵硬的、直线式的状态。而现实生活是弯曲且复杂的。模型无法通过弯曲概率来拟合真相。

理论证明： 作者通过数学证明，如果你想用这种旧有的“小桌子”方法来解决问题，你就必须让身份证的长度变得和图书馆里的书一样多。对于一个拥有百万本书的图书馆，你的身份证需要有百万个数字那么长。这在实际操作中是无法训练也无法使用的。

解决方案：“立体书”（KGE-MOS）

既然我们不能把身份证做得巨大（因为成本太高），作者提出了另一种使用这张桌子的新方法。他们引入了 KGE-MOS（混合 Softmax）。

类比：
与其拥有一张小小的平面桌子，不如想象一本立体书（Pop-Up Book）。

旧方法： 你只有一页平整的纸。你只能展示一种书籍的排列方式。
新方法 (KGE-MOS)： 你拥有一本具有多个层次（混合）的书。根据你正在看哪本书，页面会“弹出”成不同的 3D 形状。

通过将多个不同的“视角”（Softmax）混合在一起，模型可以创造出一个复杂的、弯曲的形状，从而完美契合数据，即便底层的身份证仍然很短。

效率： 这就像拥有一套小巧的乐高积木（身份证），但使用一份聪明的说明书（混合机制）来搭建一座宏大而复杂的城堡。你不需要更多的积木，你只需要一种更好的组装方式。
成本： 与仅仅增加身份证长度相比，这种新方法增加的参数量（内存成本）非常少。

实验结果显示

作者在几个现实世界的知识图谱（如药物发现网络和生物数据库）上测试了该方法。

小型图书馆： 在小型数据集（如 FB15k-237）上，“小桌子”表现良好。新的“立体书”并没有带来太大帮助，有时甚至会让模型感到困惑。
大型、稠密图书馆： 在大型、复杂的数据集（如 openbiolink 或 ogbl-biokg）上，旧模型表现挣扎。新的“立体书”（KGE-MOS）显著提高了正确排序项目和预测概率的能力。
权衡： 新方法在训练时稍慢一些（大约慢 2 倍），但它比尝试把身份证做大要快得多，因为后者需要海量的内存，且往往无法在计算机上运行。

总结

问题： 当前用于链接数据的 AI 模型使用了一个“瓶颈”，限制了它们预测的复杂程度。它们试图将海量的信息挤进一个极小的空间，从而导致信息丢失。
证明： 论文从数学上证明了，你无法通过仅仅把数据规模稍微做大来解决这个问题；你需要的是规模大到不可能实现的程度。
修复方案： 他们构建了一个新的输出层（KGE-MOS），其作用类似于一本多层结构的立体书。它允许模型在不需要海量内存的情况下，表现出复杂的模式。
结果： 对于大型现实世界数据，这种新方法使预测更加准确和可靠，为大规模知识图谱的 AI 扩展提供了一种切实可行的方法。

技术总结：论基于嵌入的链路预测的理论局限性

1. 问题陈述

本文探讨了现代知识图谱嵌入（KGE）模型中的一个基本局限性：由线性输出层引入的秩瓶颈（rank bottleneck）。在标准的 KGE 架构中，实体和关系被映射到低维嵌入空间（通常 $d \in [10^2, 10^4]$ ），然后通过线性层投影到高维实体空间（通常 $|E| \in [10^5, 10^9]$ ）。

作者认为，这种线性投影将模型的输出得分限制在 $|E|$ 维空间内的 $d$ 维线性子空间中。当 $d \ll |E|$ 时，这造成了“秩瓶颈”，严重限制了模型的表达能力。具体而言，无论上游神经编码器（如图神经网络或 Transformer）的能力有多强，该模型都无法表示复杂的下游推理任务所需的任意排序顺序、符号模式（正/负三元组）或概率分布。

2. 方法论

理论分析

作者推导了线性解码器 KGE（LD-KGE）满足三种不同预测任务所需的嵌入维度 $d$ 的必要界限：

排序重构 (RR)： 为查询正确排序对象。
符号重构 (SR)： 将三元组正确分类为真或假。
分布重构 (DR)： 为三元组分配校准后的概率。

他们在两种条件下分析了这些任务：

普适性 (Universality)： 表示给定规模图的所有可能模式的能力。论文证明，对于普适性， $d$ 必须至少为 $|E|-1$ （针对 RR 和 DR）或 $|E|$ （针对 SR）。这些界限对于大规模图而言在实践中是无法实现的。
可实现性 (Realisability)： 表示与特定观测图一致的模式的能力。作者表明，所需的维度取决于图的邻接矩阵（或其符号矩阵）的符号秩 (sign rank)。虽然符号秩通常比全秩小，但计算符号秩是 NP 难的。

为了提供一个实用的充分条件，作者将符号秩与图的连通性联系起来。他们证明，所需的维度受限于邻接矩阵行中符号变化的极大值。通过使用逆 Cuthill-McKee (RCM) 启发式算法对实体进行重排序，他们表明所需的维度随图的连通性（具体为正条目的连续块数量）而非仅仅随实体总数进行缩放。然而，即使采用最优排序，稠密图所需的维度仍远超标准实践。

提出的解决方案：KGE-MOS

为了在不增加 $d$ 带来的巨大参数成本的情况下打破这一瓶颈，作者提出了 KGE-MOS（带有混合 Softmax 的知识图谱嵌入）。

架构： KGE-MOS 不再使用单个线性层加 Softmax，而是用 $K$ 个 Softmax 的混合体替换输出层。
机制： 对于查询 $(s, r)$ ，模型计算 $K$ 个分布的混合：
$P(O|s, r) = \sum_{k=1}^K \pi_k(h_{s,r}) \cdot \text{softmax}(f_k(h_{s,r})E^\top)$
其中 $h_{s,r}$ 是隐藏状态， $E$ 是共享的实体嵌入矩阵， $f_k$ 是组件特有的非线性投影（MLP）， $\pi_k$ 是混合权重。
效率： 实体嵌入 $E$ 在所有组件间共享。新增参数仅限于投影权重 $f_k$ 和混合权重 $\pi_k$ ，其成本为 $O(Kd^2)$ ，相对于增加嵌入维度 $d$ 带来的 $O(d|E|)$ 成本而言可以忽略不计。

3. 主要贡献

理论界限： 论文为所有 LD-KGE（包括双线性模型和神经模型）提供了关于普适性和可实现性的首个必要界限。它确立了线性输出层从根本上限制了在大规模、稠密图中的表达能力。
连通性分析： 它根据图的连通性（符号变化）推导出了实现性的充分维度，表明稠密图在理论上比稀疏图更难拟合。
KGE-MOS： 它引入了一种高效的非线性输出层，打破了秩瓶颈。
实验验证： 它证明了 KGE-MOS 在大型、稠密数据集上提高了排序准确度（MRR）和概率拟合度（NLL），而简单的增加嵌入维度由于训练不稳定（例如 Batch Size 限制）而收益递减。

4. 实验结果

作者在五个数据集（FB15k-237, Hetionet, ogbl-biokg, openbiolink, WN18RR）上评估了 KGE-MOS，并对比了四种基线模型（DISTMULT, COMPLEX, RESCAL, CONVE）和一个神经编码器（COMPGCN）。

在大型/稠密图上的表现： 在三个最大且连接最稠密的数据集（Hetionet, ogbl-biokg, openbiolink）上，KGE-MOS 在 MRR 和 NLL 方面均一致优于基线 LD-KGE。在理论瓶颈最严重的高连通性区间，提升最为显著。
在小型图上的表现： 在较小的 FB15k-237 数据集上，KGE-MOS 表现出微乎其微的改进或轻微退化，证实了对于规模较小、密度较低的图，该瓶颈并不那么关键。
维度缩放： 将嵌入维度 $d$ 从 200 增加到 1000 虽然提升了基线模型的性能，但由于 GPU 显存限制需要减少 Batch Size，这最终损害了性能。相比之下，在 $d=200$ 时，KGE-MOS 达到了与 $d=1000$ 时的基线相当的性能，且参数量显著减少。
消融实验： 增加 Softmax 组件的数量 ( $K$ ) 一致地提升了性能。非线性投影 $f_k$ 也对增益有所贡献，但混合机制本身是打破瓶颈的主要驱动力。
秩突破： 对对数概率矩阵的经验秩分析显示，虽然标准模型被限制在 $d+1$ 阶，但 KGE-MOS 实现了接近实体集全维度的秩，有效地打破了瓶颈。

5. 重要性与主张

本文声称，链路预测领域一直过度关注改进编码器（例如使用 GNN 或 Transformer），而忽视了输出层的局限性。作者认为，探索更具表达能力的非线性输出层是一个必要且充满前景的方向，这对于将 KGE 扩展到大规模和稠密图至关重要。

他们强调，KGE-MOS 提供了一个“即插即用”的解决方案，能以极低的参数成本提高性能和概率保真度，挑战了“单纯增加嵌入维度是处理更大图的唯一途径”这一假设。这项工作表明，未来的研究应超越以编码器为中心的改进，去解决基于嵌入的模型在解码过程中的结构性限制。