02vault树模型知识图谱More用于多关系数据建模的平移嵌入 (TransE)

用于多关系数据建模的平移嵌入 (TransE)

#literature-note#reading-note#知识图谱嵌入#平移距离模型#链接预测#树状与层次关系

用于多关系数据建模的平移嵌入 (TransE)

基本信息

项目内容
作者Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, Oksana Yakhnenko
年份2013 (NIPS 2013)
来源Advances in Neural Information Processing Systems 26 (NIPS 2013), pp. 2787-2795
主题知识图谱平移距离嵌入与多关系数据建模 (Translating Embeddings for Knowledge Graph Completion)
链接Fulltext Markdown · Zotero 条目 · Zotero PDF · DOI: 10.5555/2999792.2999923

一句话摘要

针对传统张量分解与双线性多关系模型参数量大、优化困难且难以扩展到大规模图谱的问题，本文提出 TransE 模型，开创性地将关系建模为实体向量空间中的低维平移向量（使得若事实三元组成立则 h+ℓ≈t\mathbf{h} + \boldsymbol{\ell} \approx \mathbf{t}），以极简的参数规模和优秀的抗过拟合能力在 WordNet 与 Freebase 上取得突破性链接预测表现，并成为后续所有几何图谱嵌入的基石。

研究对象

  • 研究对象：多关系知识图谱（Multi-relational Knowledge Bases / Graphs），数据形式为有向有标号多重图中的事实三元组 (head,label,tail)(\text{head}, \text{label}, \text{tail})，简记为 (h,ℓ,t)(h, \ell, t)。
  • 核心问题：如何在极低维连续向量空间中对海量异质实体与关系进行联合嵌入，既保留图谱中普遍存在的树状/层次结构与局部连通模式，又能克服高容量非凸模型（如双线性模型、张量分解 RESCAL、神经网络张量模型 NTN）极易发生的欠拟合、严重过拟合以及超大参数量无法扩展（Scalability）的瓶颈。
  • 研究情境/范围：知识库自动补全（Knowledge Base Completion / Link Prediction），在仅依赖观测三元组、无额外先验知识的弱监督环境下，评估模型推断缺失头实体或尾实体的准确率与泛化能力。

研究方法

方法概述

  • 方法类型：连续表征学习 + 能量距离度量优化 + 跨基准实证验证。
  • 总体思路：
    1. 将实体与关系统一映射至低维连续实数向量空间 Rk\mathbb{R}^k；
    2. 确立“关系即平移（Relationships as Translations）”的几何公理：若三元组 (h,ℓ,t)(h, \ell, t) 为真，则尾实体嵌入 t\mathbf{t} 应尽可能贴近头实体嵌入 h\mathbf{h} 与关系平移向量 ℓ\boldsymbol{\ell} 之和，即 h+ℓ≈t\mathbf{h} + \boldsymbol{\ell} \approx \mathbf{t}；若三元组不成立，则两向量应远离；
    3. 采用 L1L_1 或 L2L_2 范数定义三元组能量函数 d(h+ℓ,t)d(\mathbf{h} + \boldsymbol{\ell}, \mathbf{t})；
    4. 引入基于间隔的负采样排序损失（Margin-based Ranking Loss），通过小批量随机梯度下降（Mini-batch SGD）交替更新，并施加实体单位球范数约束以防止几何退化。
  • 为什么用这种方法：树状层次结构与偏序在知识库中极具普遍性；在二维树的直观布局中，同级兄弟节点靠近分布于横轴，而父子层级关系则天然表现为纵轴上的定长平移向量；此外平移模型每个关系仅需分配一个 kk 维向量，参数预算为 O(nek+nrk)\mathcal{O}(n_e k + n_r k)，显著低于矩阵/张量模型的 O(k2)\mathcal{O}(k^2) 或 O(k3)\mathcal{O}(k^3)，优化空间更规整平滑。

方法分析

  • 分析单位：事实三元组 (h,ℓ,t)(h, \ell, t) 及其替换头/尾构建的负采样负三元组 (h′,ℓ,t′)(h', \ell, t')。
  • 关键变量/概念：
    • 实体嵌入向量 h,t∈Rk\mathbf{h}, \mathbf{t} \in \mathbb{R}^k；
    • 关系平移向量 ℓ∈Rk\boldsymbol{\ell} \in \mathbb{R}^k；
    • 能量相异度度量 d(h+ℓ,t)=∥h+ℓ−t∥1 or 2d(\mathbf{h} + \boldsymbol{\ell}, \mathbf{t}) = \|\mathbf{h} + \boldsymbol{\ell} - \mathbf{t}\|_{1 \text{ or } 2}；
    • 间隔边界超参数 γ>0\gamma > 0；
    • 实体范数约束 ∥e∥2=1\|\mathbf{e}\|_2 = 1。
  • 识别/推断逻辑：
    • 正样本能量应显著小于负样本能量，且二者差距至少达到预设间隔 γ\gamma；
    • 若不施加实体模长归一化限制，模型可通过任意放大实体向量模长使得损失无界微缩，因此每轮迭代强制执行投影操作 e←e/∥e∥2\mathbf{e} \leftarrow \mathbf{e} / \|\mathbf{e}\|_2。
  • 具体步骤：
    1. 使用均匀分布 [−6k,6k][-\frac{6}{\sqrt{k}}, \frac{6}{\sqrt{k}}] 初始化所有关系向量 ℓ\boldsymbol{\ell} 与实体向量 e\mathbf{e}，对 ℓ\boldsymbol{\ell} 进行初步归一化；
    2. 迭代采样大小为 bb 的正样本三元组小批量 SbatchS_{\text{batch}}；
    3. 对批次内每个真实三元组，通过随机替换头实体或尾实体生成对应的损坏负三元组 (h′,ℓ,t′)∈S(h,ℓ,t)′(h', \ell, t') \in S'_{(h, \ell, t)}；
    4. 计算铰链排序损失梯度，使用固定学习率执行 SGD 参数更新；
    5. 强制将所有更新后的实体向量重新归一化至单位球面上；基于验证集早停。
  • 核心公式/指标 1：基于间隔的负采样排序损失函数 (Margin-based Ranking Criterion)
L=∑(h,ℓ,t)∈S∑(h′,ℓ,t′)∈S(h,ℓ,t)′[γ+d(h+ℓ,t)−d(h′+ℓ,t′)]+\mathcal{L} = \sum_{(h, \ell, t) \in S} \sum_{(h', \ell, t') \in S'_{(h, \ell, t)}} \left[ \gamma + d(\mathbf{h} + \boldsymbol{\ell}, \mathbf{t}) - d(\mathbf{h}' + \boldsymbol{\ell}, \mathbf{t}') \right]_+
  • 公式拆解 1：
    • 这条公式表示什么：度量整个训练集上真实三元组能量与生成负三元组能量的加权排序差距。
    • 其中关键符号分别代表什么：[x]+=max⁡(0,x)[x]_+ = \max(0, x) 为取正运算符（Hinge Loss）；γ>0\gamma > 0 为正负样本之间的安全间隔边界（Margin）；SS 为已观测事实集合；S(h,ℓ,t)′S'_{(h, \ell, t)} 为通过破坏头实体或尾实体得到的候选假三元组集合。
    • 这条公式对应方法中的哪一步：目标函数定义与反向传播梯度推导的核心。
  • 核心公式/指标 2：三元组不相似度能量函数与距离分解 (Dissimilarity Energy Measure)
d(h+ℓ,t)=∥h+ℓ−t∥1或∥h+ℓ−t∥22d(\mathbf{h} + \boldsymbol{\ell}, \mathbf{t}) = \|\mathbf{h} + \boldsymbol{\ell} - \mathbf{t}\|_{1} \quad \text{或} \quad \|\mathbf{h} + \boldsymbol{\ell} - \mathbf{t}\|_{2}^2
  • 公式拆解 2：
    • 这条公式表示什么：计算头实体经由关系向量平移后与候选尾实体之间的几何距离偏差。
    • 其中关键符号分别代表什么：若采用欧氏平方范数度量，展开可得： d(h+ℓ,t)=∥h∥22+∥ℓ∥22+∥t∥22−2(h⊤t+ℓ⊤(t−h))d(\mathbf{h} + \boldsymbol{\ell}, \mathbf{t}) = \|\mathbf{h}\|_2^2 + \|\boldsymbol{\ell}\|_2^2 + \|\mathbf{t}\|_2^2 - 2 \left( \mathbf{h}^\top \mathbf{t} + \boldsymbol{\ell}^\top (\mathbf{t} - \mathbf{h}) \right) 在实体单位范数约束 ∥h∥2=∥t∥2=1\|\mathbf{h}\|_2 = \|\mathbf{t}\|_2 = 1 下，排序实际仅由内积交叉项 h⊤t+ℓ⊤(t−h)\mathbf{h}^\top \mathbf{t} + \boldsymbol{\ell}^\top (\mathbf{t} - \mathbf{h}) 决定。
    • 这条公式对应方法中的哪一步：前向传播打分与测试集排序推断步骤。
  • 方法优势：
    1. 极高的参数经济性：复杂度仅为 O(nek+nrk)\mathcal{O}(n_e k + n_r k)，在 FB15k 上参数量仅 0.81M，比 RESCAL (87.8M) 降低两个数量级，比 SE (7.47M) 减少近 90%；
    2. 训练极为轻快，天然支持千万级超大图谱：成功在包含 100 万实体、2.3 万关系、1750 万三元组的 FB1M 超大图谱上收敛；
    3. 直观的几何解释性：平移向量天然契合 1-to-1 关联与树状层次分支的几何分布。
  • 方法局限：
    1. 无法妥善建模复杂 1-to-N、N-to-1 与 N-to-N 关系：若存在 (h,ℓ,t1)(h, \ell, t_1) 与 (h,ℓ,t2)(h, \ell, t_2)，模型将强制要求 t1≈t2\mathbf{t}_1 \approx \mathbf{t}_2，导致不同实体向量发生塌陷聚合；
    2. 无法表达严格对称关系（Symmetric Relations）：若 (h,ℓ,t)(h, \ell, t) 与 (t,ℓ,h)(t, \ell, h) 同时成立，将推导出 ℓ=0\boldsymbol{\ell} = \mathbf{0} 且 h=t\mathbf{h} = \mathbf{t}；
    3. 受制于欧氏平坦度规：在高层级深入时，多层平移累积无法匹配指数级树分支容量膨胀，促使了后续双曲图谱嵌入的诞生。

数据来源

  • 数据类型：结构化多关系知识图谱基准数据集（子图切分）。
  • 样本来源：
    • WordNet (WN18)：涵盖英语词汇语义关系的词网，包含 40,943 个实体、18 类语义关系，141,442 个训练三元组；
    • Freebase (FB15k)：通用百科知识图谱子集，包含 14,951 个实体、1,345 类复杂关系，483,142 个训练三元组；
    • Freebase (FB1M)：超大规模真实知识库子图，包含 1,000,000 个实体、23,382 类关系，17,500,000 个事实样本。
  • 时间范围：2011–2013 年间经典知识库切片。
  • 样本量/案例数：从万级实体到百万级实体，覆盖 14 万至 1750 万三元组。
  • 数据局限：WN18 与 FB15k 早期版本存在测试集三元组可通过逆向关系直接在训练集中捷径泄漏的问题（后续催生了 WN18RR 与 FB15k-237）。

研究结论

  • 主要发现 1：TransE 在链接预测基准上取得了决定性优势，全面超越包括无结构模型、结构化嵌入 (SE)、双线性非参数模型 (SME) 及张量分解 (RESCAL) 在内的所有既有基准。 在 WN18 上，TransE 的 Filtered Mean Rank 达到 251，Filtered Hits@10 达到 89.2%；在 FB15k 上 Filtered Hits@10 达到 47.1%（大幅超出第二名 SME 的 41.3%）。
  • 原文引用 1：

“Despite its simplicity, this assumption proves to be powerful since extensive experiments show that TransE significantly outperforms state-of-the-art methods in link prediction on two knowledge bases.” (Page 1, Abstract)
“TransE outperforms all competitors, usually by a large margin, on both data sets for both metrics.” (Page 6, Section 4.2)

  • 主要发现 2：设计了“原始评估 (Raw)”与“过滤评估 (Filtered)”双轨评测协议，揭示了传统指标中由于假负例（排名更高的候选项本身即为图谱中的已知真实事实）导致的评估失真问题。 过滤协议消除了其他已知正例对当前测试三元组排名的不公正压制，成为后续整个知识图谱表示学习领域事实上的通用国际标准。
  • 原文引用 2：

“In this filtered setting, ranking a true triplet above the test triplet is not penalized… The difference between the raw and the filtered metrics is significant on FB15k, which contains many 1-to-many, many-to-1, and many-to-many relations… this confirms that the raw metrics were under-estimating the true performance of the models.” (Page 6, Section 4.2)

  • 主要发现 3：极度简单的参数形式不仅显著降低了训练难度，还展现出抵御高维过拟合与局部极小值欠拟合的非凡稳健性。 相比参数量极其庞大、理论表达力更强的 SE 与 RESCAL，TransE 在复杂关系图谱上表现更加稳定。
  • 原文引用 3：

“For SE, greater expressiveness seems to be more synonymous to underfitting than to better performance. Training errors (in Section 4.3) tend to confirm this point… TransE has much fewer parameters: this could simplify the training and prevent underfitting, and may compensate for a lower expressiveness.” (Page 4, Section 3)

  • 主要发现 4：成功在大规模知识库 FB1M（100万实体、2.3万关系、1700万三元组）上完成训练，证明了平移假设在超大规模工业级知识库上的优异扩展能力。
  • 原文引用 4：

“Besides, it can be successfully trained on a large scale data set with 1M entities, 25k relationships and more than 17M training samples.” (Page 1, Abstract)

我的判断

  • 最有启发的点：
    1. 将抽象语义运算降维映射为空间向量平移：论文将 Word2Vec 词向量中偶然发现的类比平移性质（King−Man+Woman≈Queen\text{King} - \text{Man} + \text{Woman} \approx \text{Queen}）上升为建模全图谱多关系的统一设计公理，开创了后续长达十年的“距离变换表示学习”家族（TransH, TransR, TransD, RotatE, MuRP, ATTH）；
    2. 以层次树结构作为平移参数化的核心理论立论点：作者在引言中敏锐指出“树状层次关系在知识库中无处不在，而纵轴平移是刻画父子层级关系的最自然变换”，直接启发了后续研究向非欧几里得双曲流形空间的纵深推进。
  • 可借鉴的方法：
    1. 采用交替随机负采样（替换头实体或尾实体）与基于间隔的铰链对比损失设计；
    2. 严密的过滤式（Filtered）链接预测评估协议设计；
    3. 参数受限下的单位范数约束正则化策略。
  • 可继续追问的问题：
    1. 欧氏平移向量无法自适应调节层次深度：同一关系在不同抽象层级上的转移跨度是恒定的，而在树结构中，根部与叶部的尺度截然不同，如何克服这种刚性约束？（后续由 MuRP 莫比乌斯对角缩放与双曲几何解决）；
    2. 面对一对多与对称关系时的几何塌陷难题，如何通过正交变换（如旋转与超平面投影）予以数学解耦？
  • 与我的研究关联：
    • 本文作为“树模型知识图谱”专题的核心基石论文，构成了从经典离散图谱平移建模迈向连续双曲几何（Poincaré, Lorentz, MuRP, ATTH, UltraE）的出发点与标准对照基线。
Built with LogoFlowershow