今天給大家介紹收錄在NIPS2019的文章“Multi-relational Poincaré Graph Embeddings”，該文章由愛丁堡大學資訊學院和劍橋三星AI中心合作完成。這篇文章提出了一種多關系龐加萊模型（MuRp），該模型将多關系圖資料嵌入到雙曲空間龐加萊球中，使得模型在低維鍊路預測的效果上，明顯優于歐幾裡得空間中相關模型和現有的其他模型。
1
研究背景
然而，在分層多關系圖資料結構中，雙曲空間嵌入方法性能卻不如歐幾裡得模型。因為在雙曲空間中很難找到一種方式來表示跨關系共享的實體(節點)，使得它們在不同的關系下形成不同的層次。目前，許多模組化多關系資料的方法，是依賴于内積作為相似性度量，但是在雙曲空間中沒有與這些模型對應的歐幾裡德内積轉換。即使有些使用歐幾裡德距離來度量相似性的方法可以轉換到雙曲空間，但它們在預測性能方面不如雙線性模型。
結合以上一系列問題，該文章提出了将分層多關系資料嵌入雙曲幾何的龐加萊球中（MuRP）的方法。MuRP通過莫比烏斯矩陣向量乘法和莫比烏斯加法，來學習轉換實體嵌入的特定關系參數。知識圖譜是一個典型的分層多關系資料結構，将其嵌入到雙曲空間中可能會有較明顯的改進。是以該文章重點研究在雙曲空間中嵌入多關系知識圖譜資料，并進行鍊路預測。經過和多關系歐幾裡得模型（MuRE）的一系列比對分析表明，次元越低，MuRP模型鍊路預測的效果比MuRE越好。
2
多關系龐加萊嵌入
2.1 雙曲幾何龐加萊球
要想把雙曲線模型與龐加萊球結合，首先應先了解一下龐加萊球的模型。定義一個半徑為1/√c(c>0)的d維流形龐加萊球(Bcd,gB)，其中Bcd={x∈Rd:c‖x‖2<1},gB=(λxc)2gE,λxc=2/(1-c‖x‖2)，x，y∈Bcd。x，y兩點之間的最短路徑為式1所示：
其中‖∙‖表示歐幾裡得範數，⊕c表示莫比烏斯加法。而莫比烏斯加法運算如式2所示：
其中表示歐幾裡得内積。莫比烏斯矩陣向量乘法運算如式3所示：
其中x通過對數映射到切線空間0中，x∈Bcd,M∈Rd*k，0∈Bcd。
圖1 (a)龐加萊球中點對之間的最短路徑。(b)該模型預測三元組真假。(c)每個嵌入的實體影響範圍
2.2 多關系圖嵌入得分函數
了解了雙曲幾何龐加萊球之後，得分函數也是模型不可或缺的部分。一組實體可以在不同的關系下形成不同的層次結構，而理想的嵌入模型應該同時捕獲所有層次結構。雙線性模型使用歐幾裡得内積來度量主體實體嵌入和客體實體嵌入之間的相似性。但是，在雙曲空間中并不存在明确的歐幾裡得内積對應。同時，研究者們發現，在word2vec詞嵌入中出現類比線性結構。而類比與多關系圖中的關系有很多相似之處，是以該研究使用以前的啟發式轉換方法對關系模組化是可行的。多關系圖嵌入的得分函數如式4所示：
其中，d是距離函數d:ℇ×R×ℇ→R+；es、eo表示主客體實體嵌入es，eo∈Rd；R∈Rd*d是對角關系矩陣；bs、bo分别表示其标量偏差bs，bo∈R。
知道了多關系圖嵌入得分函數，将得分函數與雙曲幾何龐加萊球相結合，進而應用到MuRP模型中，需要做一個适當的變換，變換後的MuRP模型得分函數如式5所示：
其中hs，ho∈Bcd分别表示主客體實體es和eo的雙曲嵌入，rh∈Bcd是關系r的雙曲平移向量，hs(r)∈Bcd通過Möbius矩陣-向量乘法得到，ho(r)∈Bcd由Möbius加法得到，R是對角關系矩陣。MuRP的參數數随實體和關系的數目線性增加，進而具有較大的知識圖譜可伸縮性。為了獲得預測的事實為真的機率，該研究将logistic sigmoid即σ(ΦMuRP(es，r，eo))應用在得分函數上。
2.3 訓練與優化
該研究使用标準的資料擴充技術，為每個三元組(es，r，eo)添加逆關系(eo，r−1，es)，同時為每個真三元組(es，r，eo)生成k個負樣本，其然後從所有實體集合ℇ中随機選擇破壞客體(es，r，eo’)或主體(eo，r−1，es’)實體。這兩個模型都用來訓練最小化伯努利負對數似然損失，計算方法如式6所示：
其中，p是預測機率，y是訓示樣本是正還是負的二進制标簽，N是訓練樣本的數量。
為了較好的看出實驗模型的效果，該研究同時用多關系歐幾裡得模型（MuRE）與本模型做了一個對比。
實驗時，該研究用随機梯度下降（SGD）和黎曼随機梯度下降（RSGD）分别對歐幾裡得模型和雙曲線模型進行了優化。在這裡作者為了計算黎曼梯度∇RL，将歐幾裡得梯度∇EL乘以龐加萊度量張量的逆，即∇RL=1/(λθc)2∇EL。同時使用expθc将梯度映射到龐加萊球上的對應測地線，進而更新黎曼梯度，即θ←expθc(−η∇RL)，其中η表示學習率。
3
實驗
3.1 資料集
文章首先使用标準WN18RR和FB15k-237資料集測試龐加萊和歐幾裡得模型在知識圖譜連結預測任務中的性能。其中FB15k-237是Freebase的子集，Freebase是真實世界事實的集合。WN18RR是WordNet的子集，WordNet是詞之間關系的分層集合。該研究從驗證和測試集中删除許多關系的逆項，以使資料集更具挑戰性。WN18RR是分層的，而FB15k-237不是分層的，是以該研究還在包含75492個實體和200個關系的NELL-995資料集上進行了對比實驗，該資料集包含22%的分層資料，以觀察文章提出的MuRP模型在分層資料集上的性能。文章使用MRR和hits@k，k∈｛1，3，10｝來評估實驗結果。
3.2 實驗參數設定
文章使用PyTorch實作MuRP和MuRE這兩個模型。實驗發現，這兩個模型在WN18RR資料集的最佳學習率為50。在FB15k-237資料集的最佳學習率為10。實驗将批次大小設定為128，負樣本數為50，MuRP的曲率設定為c=1。在這些參數下，得到的性能是最佳的。
3.3 MuRP和MuRE對比分析
兩個模型在鍊路預測上的結果如表1所示：
表1 WN18RR和FB15k-237上的連結預測結果
從表中可以觀察到，MuRE在非分層的FB15k-237資料集上的性能略好一些，而MuRP在WN18RR上的性能要好。除了HITS@1之外，Mure和MuRP在WN18RR上的所有名額上都超過了之前的最先進的模型。即使在相對較低的嵌入維數(d=40)下，這一點也保持不變，這表明雙曲線模型能夠簡潔地表示多個層次。在FB15k-237中，MuRE的性能僅次于TuckER，這主要是由于跨關系的多任務學習。MuRP并沒有包括跨關系多任務學習，這是在未來的工作中亟待解決的問題。
文章比較了MuRE和MuRP在不同度嵌入的WN18RR上的MRR值。當嵌入次元較低時，MuRE和MuRP模型差異最大。MuRP的收斂速度也比MuRE快。實驗結果如圖2所示：
圖2 (a)WN18RR上不同嵌入大小的Mure和MuRP的MRR對數圖 (b)Mure和MuRP在WN18RR訓練集(虛線)和驗證集(實線)上的MRR收斂速度
為了表示模型的每一部分都不可缺少，作者研究了關系特定的轉換和偏差選擇的消融，實驗結果如表2所示：
表2 WN18RR上不同模型架構選擇的消融研究：關系轉換(左)和偏差(右)。
從表2可以看出，對目前模型架構的任何更改都會對MuRE和MuRP的性能産生負面影響。用嵌入規範化的實體替換偏差會導緻MuRP的性能顯著降低。
由于并不是WN18RR中的每個關系都在實體上誘導出層次結構，是以該文章研究了由每個關系形成的實體圖的層次得分(Khs)，以獲得所誘導的層次的度量。該分數僅針對有向網絡定義，并且測量其中存在有向路徑x→y而不存在y→x的節點對。對于所有有向非循環圖，該分數取值為1，對于圈和環，該分數取值為0。對于層次關系，文章還研究了圖中任意兩個節點之間的最大最短路徑和平均最短路徑。為了了解哪些關系在雙曲空間中嵌入實體中受益最大，實驗比較了低維(d=20)實體嵌入的MuRE和MuRP的每個關系的hits@10。最後的對比結果如表3所示：
表3 WN18RR上，d=20時Mure和MuRP的每個關系的hits@10。
從表3中我們可以看到，這兩個模型在Khs層次結構得分為0的非層次對稱關系性能都比較好，而MuRP在層次關系上的性能優于MuRE。對于形成較深樹的關系，MuRE和MuRP之間的性能差異通常較大。
一系列實驗結果表明，MuRP在分層多關系資料集上的鍊路預測任務上優于MuRE和現有模型，并且需要更低的次元就能獲得與其歐幾裡德類似模型相當的性能。在未來，可以研究最近引入的黎曼自适應優化方法與黎曼随機梯度下降方法的影響。此外，由于知識圖譜中并不是所有的關系都是分層的，後續工作可以将歐幾裡得和雙曲模型結合起來，産生最适合資料曲率的混合曲率嵌入。