大规模知识图谱表示必读：从Bert中的wordpiece到KG中的nodepiece

知识表示是当前的知识图谱技术的前沿课题，而大规模知识图谱的出现，使得学习所有节点的嵌入变得非常困难。

一般来说，在现有的知识表示模型当中，将每个节点映射到一个嵌入向量会产生非常大的嵌入矩阵，这使得计算量十分巨大。现在知识图（KG）越来越大：Wikidata有大约1亿个节点（实体），YAGO4大约有5000万个节点，而像Google KG或Diffbot这样的自定义图要大几个数量级。

如此一来，对它们执行任何机器学习或图表示学习 (GRL) 任务通常意味着通过将每个实体和关系映射到一个唯一向量（或有时许多向量或整个唯一矩阵）来将实体和关系嵌入到潜在空间中，对于性功能来说，挑战十分大。

而实际上，NLP领域也面临过此表太大难以对所有词的嵌入建模的问题，并采用了WordPiece技巧来解决。

例如，它不再把一个词看成一个整体，而是分割成几个子词。比如"loved",“loving”,“loves"这三个单词，WordPiece把上面的3个单词拆分成"lov”,“ed”,“ing”,"es"几部分，这样可以把词的本身的意思和时态分开，有效的减少了词表的数量，直接的解决了参数量过大以及OOV问题。

而这种思路，是否可以迁移到知识表示呢？

答案是可以的，《NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs 》一文将自然语言处理的WordPiece技巧迁移到知识图谱中并提出NodePiece，从而用较少的子实体嵌入去建模大规模知识图谱上的实体嵌入，并增强模型的泛化性能。

我们团队提出了nodepiece-tripleRE的方法，并在Ogbl-wikikg2上取得了top1的成绩，其中验证了nodepiece其在百科类大数据集上的有效性。

因此，本文主要是基于参考文献1的翻译，并做进一步整理补充形成的一篇介绍性文章，对其原理进行介绍，思路很直接，但细推起来依旧存在一些问题。供大家一起参考，辩证地看。

一、大规模知识图谱表示问题的提出

当前知识图谱表示模型存在两个重要问题，一个是参数量太大，不好训练，另一个是对于新增节点如何表示的问题。

1、参数量太大

几乎所有现有的KG嵌入算法（如TransE、RotatE、DistMult等）都将所有节点都映射到唯一的各自向量，这种做法就是常说的浅层模型。

本质上，浅层意味着嵌入查找按照这样一种范式：对于|E|的词汇表（实体），你必须有|E|嵌入矩阵中的d维行，也就是说，100个实体=100行，10K实体=10K行，100M实体=100M行，依此类推。现在将行数乘以嵌入维度以获得可学习参数的近似数量（关系数|R|远小于|E|，因此我们主要关注实体），并整个嵌入矩阵加载至内存中。如下图所示：

其中，具有可学习实体嵌入矩阵的基于GNN的模型，例如CompGCN，在消息传递之前有一个浅层查找层，而GNN最大的问题就是全图加载，在大图上落地十分差。

例如，Open Graph Benchmark (OGB)这一最大规模的知识图谱评测数据集，仅包含250万个实体的WikiKG2，目前公开的模型大小如下图所示，就在500M-1.25B参数之间变化，因此需要配备具有45GBVRAM的GPU或降低嵌入维度才能真正工业实施。

而相比较的彻底改变了NLP的BERT或被认为“太危险而不能公开发布”的GPT-2也仅仅有为340M和1.5B的参数。

2、对于未知新节点表示问题

未知新节点表示问题也是一大难点，已有的知识图谱表示方法只有实体和关系的词汇表， 由于没有通用编码器，对于一个大图，就需要一次性构建起一张大的参数矩阵。

实际上，OOV问题十分常见，在文本领域，无论如何扩展单词词汇量，由于语言的组成性质，我们永远无法完全捕捉所有这些单词。因此，需要一种更加组合的机制来表示任何可见或不可见的单词，使用相同的原子集。

实际上，为了解决OOV问题，文本处理上就做了一些工作，例如2015年有很多这样的方法：

基于字符的模型，如中文直接以字处理，其中原子本质上是带有一些辅助符号的字母表；

Sennrich等人的开创性工作中引入了“词块” 或“子词单元”模型，其中原子是最常见的n-gram。

WordPiece/SentencePiece算法将子字单元实现为字节对编码，这也成为所有现代神经语言模型中事实上的标准预处理步骤。

因此，使用有限的原子词汇表，可以构建几乎无限数量的组合词，任何看不见的词都可以标记为一系列字符或词块。与将3M大的词汇矩阵存储为输入嵌入相比，使用单词片段，典型的词汇量要小得多。

例如，BERT有30K的WordPiece原子词汇，GPT-2&GPT-3有50K个BPE原子词汇。

那么，BERT等方法可以采用找到子词的做法来减少参数量以及缓解oov问题，那么是否可以在Graph ML图学习的领域来进行迁移？所以，问题就变成了，如果节点是“词”，是否可以为图设计一个固定大小的“子词”（子节点）单元的词汇表。

二、从wordpiece到NodePiece

《NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs》一文提出NodePiece作为一种组合“节点标记化”方法。用于减少大型KG中的词汇量，与不要学习一个巨大的实体嵌入矩阵不同，而是学习一个固定大小的原子词汇表和一个简单的编码器，该编码器将能够从原子序列引导任何节点的表示，就像从子词序列构造单词一样。

1、定义

在 NodePiece中，词汇原子（或“节点片段）是锚节点和关系类型。

锚节点是图中现有节点的子集，可以随机选择，也可以根据PageRank或节点度等中心性度量来选择，甚至不需要很多锚节点（因为不需要标记词汇表中所有可能的n-gram），而且实验表明，通常1-10%就足够了。

所有关系类型都包含在词汇表中，因为与节点（实体）的总数相比，它们的数量通常并不多。

2、NodePiece的实施思路

下图展示了NodePiece的实施思路，红色节点使用3个最近的锚点和3个传出关系类型进行标记。

假设我们想要标记红色节点🔴给定锚点和几种关系类型，要计算出某个target node的嵌入，首先选择距离其前top-k近的anchor node，然后将它们的嵌入以及它们各自到target node的距离以及与target node直接相连的关系类型，都加入到编码器中并输出结果。

从实现上看，可以采用如下步骤：

首先，锚点anchor选择。

自然语言处理是根据词汇共现频率来确定subword units的，而在图中，对应的概念是中心度，通过pagerank、中心度等方式对图中所有节点进行排序，取得topk作为最终锚点集合，但作者做了一些实验表明，按照中心度筛选anchor node和随机筛选的效果是一致的。

for strategy, ratio in self.anchor_strategy.items():
            if ratio <= 0.0:
                continue
            topK = int(np.ceil(ratio * self.num_anchors))
            print(f"Computing the {strategy} nodes")
            if strategy == "degree":
                # top_nodes = sorted(graph.degree(), key=lambda x: x[1], reverse=True) # OLD NetworkX
                top_nodes = sorted([(i, n) for i, n in enumerate(graph.degree())], key=lambda x: x[1], reverse=True)
            elif strategy == "betweenness":
                raise NotImplementedError("Betweenness is disabled due to computational costs")
            elif strategy == "pagerank":
                #top_nodes = sorted(nx.pagerank(nx.DiGraph(graph)).items(), key=lambda x: x[1], reverse=True)
                top_nodes = sorted([(i, n) for i, n in enumerate(graph.personalized_pagerank())], key=lambda x: x[1], reverse=True)
            elif strategy == "random":
                top_nodes = [(int(k), 1) for k in np.random.permutation(np.arange(self.triples_factory.num_entities))]

其次，建立节点-锚点映射

在确定NodePiece vocabulary之后，每个节点n的嵌入即hash(n)可以通过距离它前k近的anchor node及其对应距离，以及m个与节点n相连的关系来确定。为了选取k个最近的anchor node，论文中提出了两种策略：

一种是随机策略采样出 (∣A∣ k)的全排列，然后使用DFS算法去比较。另外一种确定性策略是使用BFS直接对n的邻居进行检索并排序。

针对孤岛式的节点，论文提出可以将其与一个标记为DISCONNECTED的anchor node相连，或者是直接将其设为anchor node，但这种情况很少见，对结果的影响可以忽略不计。

1）我们使用BFS找到k个最近的锚点，并将它们按距离到🔴的升序排列（如果足够频繁，k=20）。

2）锚点距离是类似于位置编码的标量，有助于定位（或“三角化”）图中的🔴节点并将其归因于锚节点。与位置编码类似，将k个锚距离嵌入添加到k个各自最近的锚节点。在利用target node到anchor node的距离信息时，模型并不是直接利用一个单独的整数，而是将其映射为向量。

3）在大型KG中，仍然可能存在一些“哈希冲突”，因此第三个成分是从🔴发出的m个唯一传出关系的节点关系上下文，请注意，向图中添加反向边的标准预处理步骤非常有用因为我们保持每个节点的完全可达性）。对于关系上下文，一个实体最多利用与之相连的m个关系，如果关系较多，就随机采样m个，如果关系太少，就用[PAD]来代替。

根据KG的大小和密度，我们将m从3变化到15。

4）现在，有一个k+m的anchor序列，可以唯一地标识任何节点。任何单射池（序列编码器，如MLP或Transformer）都可用于将k+m序列编码为唯一的嵌入向量，这是我们一直在寻找的节点嵌入。

例如，以Wikidata中的Albert Einstein为例，编码器函数f应用于标记化序列，用来重建了Einstein的唯一节点嵌入：

假设我们已经预先选择了一些锚点，我们可以使用三个最近的：Ulm、Nobel Prize、Theoretical Physics。它们都在 Einstein的1-hop邻域中找到，因此它们的锚点距离为1。

作为关系上下文，随机抽取4种独特的传出关系类型，例如place of birth、award received，因此，我们的Einstein实体使用7个原子进行标记。

当然，KG越大，想要使用的锚点就越多，以确保序列更加独特，尽管我们发现即使在百万节点图中，每个节点也存在大约20个锚点的饱和点。

而基于这个节点嵌入可以在任何下游任务中接到下游任务中去，如节点分类、链接预测或关系预测

2、实施效果

1）实体关系预测

在FB15k-237和YAGO3-10等标准基准上进行链路预测。

我们发现，将词汇量减少10倍，只保留10%的原始节点作为锚点（享受10倍的参数减少），其余的通过MLP从它们重建，使用NodePiece词汇表和编码器以及几个最先进的任务特定解码器模型（例如，分别用于关系预测的RotatE和用于节点分类的CompGCN）

可以发现，在大规模减少参数量的情况下，性能并没有大幅下降。NodePiece可以直接带来计算节点和嵌入矩阵大小：仅|A|锚节点而不是所有|E|节点。根据任务的不同，我们用10倍、100倍、1000倍的减少率进行实验，仍然观察到有竞争力的结果；

消融实验揭示了一个有趣的现象，拥有0个锚点不会影响关系丰富的图（如FB15k-237和YAGO 3-10的性能，这似乎说明了根本不需要节点/锚点嵌入，仅在关系上下文中与编码器的一些关系就足以获得非常好的性能。

2）实体节点分类任务

以WD50K上的节点分类任务（一个多类多标签问题，有大约500个标签）为例，也可以得到有趣的结果：

如上图所示，在节点分类中👆），将词汇量减少了近1000倍（46K节点图中的50个锚点）并观察到所有指标的提升，这可能表明基线已经相当过度参数化。

知识表示是当前的知识图谱技术的前沿课题，而大规模知识图谱的出现，使得学习所有节点的嵌入变得非常困难。

《NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs 》一文将自然语言处理的WordPiece技巧迁移到知识图谱中并提出NodePiece，从而用较少的子实体嵌入去建模大规模知识图谱上的实体嵌入，并增强模型的泛化性能。

这篇论文的动机和想法还是很新颖的，但细究起来，模型比较粗糙，比如：

每个节点都用有限的anchor锚点进行表示，这个对于完全没有关联的节点，只用最短路径来约束，物理意义上是存疑的。

随机选择m个关系作为关系上下文就没有考虑到采样得到的关系顺序的影响，虽然实验中参数量下降了很多，但性能也也有下降。

做消融实验时，去掉某个设定效果差得不太多，有时候甚至去掉更好，如不需要anchor锚点的效果。

又如，在一些小数据上，效果不如大数据集明显，并且我们在ogbl-biokg上总同样的方法进行实验，也没有得到明显的效果，该方法对图谱数据本身的特性也有很大关系。

所以，总结的来看，nodepiece是一个很巧妙的思路，值得肯定，但泛化性值得进一步提升。

过度参数化。

1、https://towardsdatascience.com/nodepiece-tokenizing-knowledge-graphs-6dd2b91847aa

2、https://blog.csdn.net/jining11/article/details/121180562?spm=1001.2014.3001.5501

3、https://github.com/migalkin/NodePiece

进技术交流群请添加AINLP小助手微信（id: ainlper)
请备注具体方向+所用到的相关技术点

关于AINLP

AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLPer(id：ainlper)，备注工作/研究方向+加群目的。

阅读至此了，分享、点赞、在看三选一吧🙏