论文阅读：A Lightweight Knowledge Graph Embedding Framework for Efficient Inference and Storage-526互联

ABSTRACT

现存的KGE方法无法适用于大规模的图（由于存储和推理效率的限制）
作者提出了一种LightKG框架：
自动的推断出码本codebooks和码字codewords，为每个实体生成合适的embedding。
同时，框架中包含残差模块来实现码本的多样性，并且包含连续函数来近似的实现码字的选择。
为更好的提升KGE的表现，作者提出了基于量化的动态负采样方法，可用于LightKG框架和其他框架中（效果可以提升19%）。

1 Introduction

往常方法：学习实体和关系的embedding在连续的空间中。
假设空间维数为d，实体个数为$n_e$，关系个数为$n_r$。
存储所用空间为$4n_ed+4n_rd$。
例如任务$(h,r,?)$,时间复杂度约为$O(n_ed + Klogn_e)$
$n_e$越大，时间复杂度越高。
哈希和PQ算法可能会导致更低的精度，容易出错。

基于上述的挑战，本文提出了LightKG。仅考虑实体嵌入。

整体架构如上所示。
先将d维的向量划分到m个子空间中。
假设每个空间有B个码本，每个码本中有m个码字。
在每个码本中找到最接近的码字，再将码字相加，可以与原始embedding近似。
对于一个实体，可以用最相近码字的下标来表示。
每个向量编码后内存为$\frac{1}{8}mBlogW$
原始向量占内存为$4d$.

当进行向量查询时，先对query向量（根据码本中的码字）建立lookup表。
之后，和每个实体间相似性分数的计算就转化为在lookup表中查询再求和。
总的时间复杂度为$O(n_e+BWd)$

KGE方法主要分为三类

Translation-based model:主要应用欧几里得距离和曼哈顿距离等
bilinear model
deep learning-based model:如ConvE,R-GCN等
同时轻量级框架也在快速发展，比如：二值化网络，PQ等
负采样：RotatE

3 Methodology

3.1 Problem Formulation

{$G = {(h,r,t)|h,t\in E, r \in }R $}
学习embedding $h,t\in \mathbb{R}^d, r\in \mathbb{R}^d$
同时设定相关性评分有：$f(\cdot): E×R×E \rightarrow \mathbb{R}$

3.2 Overview

先把向量划分为多个子空间并学习码字(codeword),
同时采用残差模型，利用多个码字实现压缩的embedding。
也会额外介绍损失函数和训练过程。
同时会采用动态下采样的方法来弥补压缩带来的性能下降。

3.3 Codeword learning

现存的量化方法（基于kmeans)无法微分。
将d维向量e分割到m个子空间中，可以知道$e^i\in \mathbb R^{d/m}$
原始向量可以表示为$e = [e^1,e^2,....,e^m]$
每个子空间对应B个码本，每个码本中有W个码字。
学习码字的过程可以表示为：
$c_{w^b(i)}^b(i)=C^b(i)o$,其中$C^b(i)\in \mathbb R^{d/m×W}$,
o表示独热编码$o_{w^b(i)}=1$
独热编码是不能微分的，采用近似
$o_j \approx \hat{o_j} = \frac{exp(s(e^i,c_j^b（i))/T)}{\sum_{j'}exp(s(e^i,c_{j'}^b（i))/T)}$
基于softmax回归和Straight-Through Estimator实现codebooks的学习。

同时，相似度函数也是重要的，本篇文章采用的相似性函数是
$s(e,c) = e^TMc$

3.4 Residual Module

如何利用B个codebooks得到合适的embedding
简单的对embedding进行B次编码得到B个codewords的话。
B个codebooks会有相似的趋势，然而要求对向量编码codebook要尽可能地丰富。

本文提出了一种残差模型来实现向量编码的多样性。
整体过程如上所示。
记$c_{w^b(i)}^b=Q(x;C^b(i))$,相当于对向量x在码本b中找到一个合适的码字。

整体过程如下:$x_{b+1}=x_b - Q(x_b;C^b(i)), x_1=e^i$
每次的输入是不同的，得到的码字也会不同。
最后会在B个码本中找到多样化的b个码字。
最后将所有码字联系起来，即为最终的表示。

3.5 Loss Function

LightKG输入为三元式，输出为量化后的embedding。。

采用margin-based损失函数

3.6 Advantages of LightKG

主要在拟合精度不会有较大下降的情况下，存储效率有很大的提升。
存储方面：
当采用内积时，公式如下：
$\langle q,e_k\rangle=\sum_{i=1}^m\sum_{b=1}^B\langle q^i,c_{w_k^b(i)}^b(i)\rangle$
当采用欧几里得公式时，如下所示：
$||q-e_k||_2^2 = \sum_{i=1}^m||q^i||_2^2+\sum_{i=1}^m||e_k^i||_2^2-2\sum_{i=1}^m\sum_{b=1}^B\langle q^i,c_{w_k^b(i)}^b(i) \rangle$

当使用第一种距离时，仅需要存储$4BWd + \frac{1}{8}n_e mBlogW$,
当使用第二种距离时，仅需要存储$4BWd + \frac{1}{8}n_e mBlogW+4n_e$。

并且，采用LightKG也可以减少查询的时间。
直接查询，时间复杂度为$O(n_ed)$。
当采用码表时，时间复杂度为$O(n_e + BWd)$
因为$q_i$和码表中所有码本进行距离计算的时间复杂度是很低的，之后只要对每个实体进行查询操作即可。