---
title: '[KGE] Node Pieces'
---

[TOC]

# Node Pieces


## Introduction
[Node Pieces](https://arxiv.org/abs/2106.12144) 是為了減少模型參數量，同時針對「圖結構」進行特徵工程的一種方法。在 [OGB Link Prediction wikikg dataset](https://ogb.stanford.edu/docs/leader_linkprop/#ogbl-wikikg2) 上省下了**15倍的參數量**，同時提升了**20%的[MRR](https://en.wikipedia.org/wiki/Mean_reciprocal_rank)準卻度**，這種方法除了能使用在Knowledge Graph Embedding上，GNN也可以使用此方法來做特徵工程。傳統上我們習慣對節點進行 Shallow Embedding ，此篇論文提出了一個新的想法 ->「給定錨點(Anchor)和正負連接( Relations and Inverse Relations )來表達所有的點」，簡而言之，創造一個圖專用的 Tokenizer 。此外，你也可以參考這篇由共同作者撰寫的[Blog](https://towardsdatascience.com/nodepiece-tokenizing-knowledge-graphs-6dd2b91847aa)。

## Why we need Node Pieces

### 1. Reduce Parameters
KGE 的任務中，每加入一個新的 Entity 都會需要儲存對應的Embedding ，然而知識圖譜常常會有幾十、幾百萬的 Entity ，搭配動輒1000~2000的 Embedding dimension，帶來了很多參數負擔。

### 2. OOV( Out Of Vocabulary ) Problem
應用端中常常存在冷啟動的問題，舉例來說如果今天實作一推薦系統，我們也許能將曾經的客戶預測的很精準，然而我們卻沒有辦法給予新客戶一個 Entity。這樣的困境即是 OOV，然而 Node Pieces 卻能很好的解決這個問題，因為 Node Pieces 是由已存在圖譜裡的 Anchor和Relation來描述所有節點，因此新客戶進來時，我們不需要增加新的 Embedding，也就不存在OOV。

## Method


### Anchor
預先選擇M個點做為錨點，給定一點 G 之後用 [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) 演算法鄰近 G 的 K 個錨點的 Embedding 來表示。不過只有這樣容易得到很多相同 Embedding 的點，因此我們必須增加一點特徵，論文在 Embedding 上加上 Anchor Distance ，這邊可以想像成一種 Relative Position Encoding 。

### Relation
除此之外論文中也使用 Relation, Inverse Relation 來增加特徵，所有 Relation Encoding 都是從 G 點向外，因此在使用 Node Pieces 之前，必須要先創造 Inverse Relation 。

### Encoder
將 Anchor 和 Relation 的值 Concat 然後放入 Encoder 裡，這邊的 Encoder 可以是 [MLP](https://en.wikipedia.org/wiki/Multilayer_perceptron) 或者 [Transformer](https://en.wikipedia.org/wiki/Transformer_(machine_learning_model))，整個 Node Pieces 可以看成 Deep Embedding ，有別於傳統 Trans 系列的 look up table 屬於 Shallow Embedding，因此也能放在 Trans 系列乃至 GNN 做 Entity ( Node ) Embedding 。

###### tags: `Knowledge Graph Embedding`