王培妍 段 磊 郭正山 蔣為鵬 張譯丹

(四川大學(xué)計算機學(xué)院 成都 610065)

知識超圖是一種圖結(jié)構(gòu)的知識庫，通常以多元組的形式存儲世界上的事實，其可以被視作知識圖譜的推廣.由于現(xiàn)實世界中存在大量事實，在知識庫中獲取并儲存所有事實是不現(xiàn)實的.所以對現(xiàn)有知識庫的最大挑戰(zhàn)是其嚴(yán)重的不完整性，即部分實體間的鏈接是缺失的.以Freebase[1]為例，其儲存有約300萬的人物條目，其中71%的人缺少與出生地的鏈接，94%的人缺少與父母的鏈接，99%的人缺少與種族的鏈接[2].面對知識庫的高度不完整性，手動為實體間添加鏈接是十分耗費人力和物力的，因此產(chǎn)生了對自動推理實體間缺失鏈接算法的需求.

鏈接預(yù)測算法能夠基于實體間已知的鏈接去預(yù)測未知的鏈接，因此可以用于知識庫補全，同時進一步促進基于知識庫的下游任務(wù)，例如智能問答[3-4]、個性化推薦[5-6]、自然語言處理[7]和信息檢索[8]等.自從谷歌在2012年發(fā)布了知識圖譜(一種基于二元關(guān)系構(gòu)建的圖結(jié)構(gòu)知識庫)，基于知識圖譜的鏈接預(yù)測開始受到關(guān)注，在社交網(wǎng)絡(luò)分析[9]、生物醫(yī)學(xué)[10]等領(lǐng)域中都取得了極大的進展.然而在現(xiàn)實世界中，關(guān)系通常是非二元的.例如“梁思成是李蕙仙和梁啟超的兒子”，顯然在這個事實對應(yīng)的關(guān)系中共涉及到3個實體，分別為“梁思成”“李蕙仙”和“梁啟超”，因此該關(guān)系是一種更為復(fù)雜的多元關(guān)系.有數(shù)據(jù)表明，在原始Freebase數(shù)據(jù)集中，超過1/3的實體參與到多元關(guān)系中[11]，超過61%的關(guān)系是多元的[12].可以看出，多元關(guān)系是一種普遍存在的關(guān)系，因此Wen等人[11]提出了知識超圖的概念，并證明了通過S2C(star-to-clique)和具體化方法將知識超圖轉(zhuǎn)換為知識圖譜會導(dǎo)致結(jié)構(gòu)信息丟失.

知識超圖能夠保存事實間的多元關(guān)系，即事實的完整結(jié)構(gòu)信息，因此吸引了研究人員的注意.一個自然而然的想法是將知識圖譜中的鏈接預(yù)測模型推廣到知識超圖中去，例如m-TransH[11]是對TransH算法[13]的推廣，m-CP[12]是對CP分解算法[14]的推廣，m-DistMult[12]是對DistMult算法[15]的推廣.但由于這類模型的原型是專為知識圖譜設(shè)計的，所以不可避免地導(dǎo)致模型在知識超圖上效果表現(xiàn)欠佳.以m-DistMult模型為例，其原型DistMult通過將二元關(guān)系表示為對角矩陣，以建模2個實體間的交互.而在知識超圖中，m-DistMult仍然使用對角矩陣來表示多元關(guān)系，顯然一個二維對角矩陣無法建模多于2個實體間的交互，因此m-DistMult在知識超圖鏈接預(yù)測任務(wù)中效果較差.最近一些研究者們提出基于嵌入表示學(xué)習(xí)的方法，以解決知識超圖中的鏈接預(yù)測問題，這些方法主要分為基于平移(trans-lation)的方法、基于張量分解(tensor decomposition)的方法、基于圖神經(jīng)網(wǎng)絡(luò)(graph neural network, GNN)的方法以及基于鍵-值對(key-value pair)的方法.基于平移的方法通常較為簡單，但是大多數(shù)這類方法不具有完全表達性，即不能準(zhǔn)確地將事實(例如：“地球是一顆行星”)與非事實(例如：“地球是一顆恒星”)區(qū)分開來[16-17].基于張量分解的方法具有較強的數(shù)學(xué)理論基礎(chǔ)，但通常計算量較大，且需要較多的內(nèi)存資源.基于圖神經(jīng)網(wǎng)絡(luò)的方法盡管目前取得了不錯的實驗效果，但是該類方法是不透明且難以理解的[18].基于鍵-值對的方法易于理解，但是通常需要確定主三元組及輔助鍵-值對，目前對于主三元組的確定沒有統(tǒng)一標(biāo)準(zhǔn).

Fig. 1 A toy example of knowledge hypergraph圖1 知識超圖的簡單示例

知識超圖通常是有向的，即關(guān)系中實體的排列是有序的.圖1示例了一個簡單的有向知識超圖，可以發(fā)現(xiàn)：

1) 當(dāng)同一實體出現(xiàn)在同一關(guān)系的不同位置時具有不同角色.例如：當(dāng)“梁思成”出現(xiàn)在“子女-母親-父親”關(guān)系的首位時，表示其是“母親”李蕙仙和“父親”梁啟超的“子女”；當(dāng)“梁思成”出現(xiàn)在該關(guān)系的末位時，表示其是“子女”梁再冰的“父親”.

2) 當(dāng)同一實體出現(xiàn)在不同關(guān)系中時具有不同角色.例如：當(dāng)“梁思成”出現(xiàn)在關(guān)系“子女-母親-父親”和“學(xué)生-大學(xué)-專業(yè)”的首位時，分別表示“子女”和“學(xué)生”2個不同的角色.

基于圖1的觀察，在預(yù)測知識超圖鏈接時，考慮實體在不同關(guān)系以及不同位置上的角色差異十分重要.然而，現(xiàn)有方法要么沒有考慮知識超圖的有向性，要么只關(guān)注同一關(guān)系中不同位置上的實體角色差異[12].

本文提出了一個基于張量分解且具有完全表達性的模型Typer(tensor decomposition for knowledge hypergraph link prediction)，用于解決知識超圖中的鏈接預(yù)測問題.Typer模型通過引入角色矩陣以建模實體在不同關(guān)系以及不同位置上的角色信息.同時受BoxE[19]的啟發(fā)，對關(guān)系進行細化分解以提升模型性能.此外，為促進實體和關(guān)系間的信息流動，本文引入了窗口的概念，令實體和關(guān)系在窗口中進行充分交互.在2個大型知識超圖數(shù)據(jù)集上的實驗表明，Typer模型能有效處理復(fù)雜的多元關(guān)系鏈接預(yù)測問題.

本文的主要貢獻有3個方面：

1) 提出了一個基于張量分解的知識超圖鏈接預(yù)測模型Typer，不僅考慮到實體在不同關(guān)系以及不同位置上的角色差異，還對關(guān)系進行了細化分解，同時引入了窗口的概念，以增加實體與關(guān)系之間的交互.

2) 證明了Typer模型在理論上具有完全表達性，即存在一種嵌入表示能夠使模型精確地劃分事實與非事實.此外，還給出了Typer模型具有完全表達性時，嵌入表示的維度邊界.

3) 在多個公開的真實知識超圖數(shù)據(jù)集上執(zhí)行了詳實的實驗，并與其他先進方法進行對比.實驗結(jié)果和進一步的分析說明了Typer模型對于解決知識超圖鏈接預(yù)測問題是有效的，且取得了較其他方法更好的實驗結(jié)果.

1 相關(guān)工作

本節(jié)主要介紹知識超圖中鏈接預(yù)測的相關(guān)工作，這些方法通常被分為4類：基于平移的方法、基于張量分解的方法、基于圖神經(jīng)網(wǎng)絡(luò)的方法和基于鍵-值對的方法.

1.1 基于平移的方法

基于平移的方法通常將實體和關(guān)系嵌入到同一潛在向量空間中，然后通過關(guān)系對實體進行平移，從而學(xué)習(xí)到實體和關(guān)系之間的聯(lián)系，進而利用學(xué)習(xí)到的嵌入表示進行鏈接預(yù)測.

TransE[20]是首次提出的基于平移的鏈接預(yù)測方法，對于知識圖譜中的任意一個三元組(頭實體，關(guān)系，尾實體)，其中頭實體的嵌入表示加上關(guān)系的嵌入表示應(yīng)近似于尾實體的嵌入表示.由于TransE只能處理二元關(guān)系，所以Wen等人[11]提出了m-TransH模型，通過對Trans系列中的TransH[13]進行擴展，用于解決知識超圖中多元關(guān)系的鏈接預(yù)測問題.隨后，RAE模型[21]通過將2個實體共同出現(xiàn)在一個多元關(guān)系事實中的概率增加到損失函數(shù)中，對m-TransH進行了擴展.

盡管上述基于平移的方法取得了較好的表現(xiàn)，但文獻[16]和文獻[17]證明了TransE及其一系列變體均不具有完全表達性，在關(guān)系建模方面具有局限性.最近，Abboud等人[19]提出了一個基于空間平移的鏈接預(yù)測模型BoxE，該模型將實體表示為低維向量空間中的點，將關(guān)系分解為同一向量空間中的一組超矩形，計算實體點到對應(yīng)超矩形中心的距離，距離越小表示該多元關(guān)系事實越可能成立.據(jù)我們所知，BoxE是目前唯一一個基于平移且具有完全表達性的鏈接預(yù)測方法.

1.2 基于張量分解的方法

基于張量分解的方法通常將高階張量分解為多個低階張量.由于基于張量分解的方法在二元關(guān)系鏈接預(yù)測問題中具有較好的表現(xiàn)[22-23]，所以很多研究者將用于知識圖譜的鏈接預(yù)測模型擴展到知識超圖中，以處理多元關(guān)系，例如m-CP[12]和m-DistMult[12]模型分別是對CP[14]和DistMult[15]算法的推廣.

最近，Liu等人[24]提出了GETD模型，該模型是對TuckER模型[18]的擴展.然而，GETD模型只能處理k-均勻超圖(k-uniform hypergraph)，不能處理同時具有不同元數(shù)關(guān)系的數(shù)據(jù)集，即當(dāng)一個數(shù)據(jù)集同時具有二元關(guān)系、三元關(guān)系及其他不同元數(shù)關(guān)系時，需要先將數(shù)據(jù)集按照關(guān)系元數(shù)進行劃分，再分別進行訓(xùn)練.GETD是具有完全表達性的模型.Fatemi等人[12]受到SimplE模型[16]的啟發(fā)，提出了HSimplE模型，該模型能夠處理多元關(guān)系且具有完全表達性.HypE模型[12]觀察到一個實體在同一個關(guān)系的不同位置上具有不同角色，因此基于位置為每個實體學(xué)習(xí)不同的嵌入表示，通過計算對應(yīng)位置上實體和關(guān)系的嵌入表示，獲得多元關(guān)系事實成立的得分.HypE模型同樣具有完全表達性.

1.3 基于圖神經(jīng)網(wǎng)絡(luò)的方法

圖神經(jīng)網(wǎng)絡(luò)被證明是一種有效的基于深度學(xué)習(xí)解決知識圖譜中鏈接預(yù)測問題的工具[25].由于圖神經(jīng)網(wǎng)絡(luò)具有強大的學(xué)習(xí)能力，一些研究人員將其應(yīng)用到知識超圖中，以解決知識超圖中多元關(guān)系的鏈接預(yù)測問題.

Yadati[26]提出了G-MPNN模型，通過將信息傳遞神經(jīng)網(wǎng)絡(luò)(message passing neural network, MPNN)推廣到知識超圖上，解決多元關(guān)系的鏈接預(yù)測問題.但是該模型使用雙線性評分函數(shù)進行評分，導(dǎo)致其對于建模非對稱關(guān)系具有局限性，同時該模型不具有完全表達性.HGNN模型[27]引入了超邊卷積操作，在進行表示學(xué)習(xí)時，利用超邊卷積處理多元關(guān)系中實體之間的關(guān)聯(lián).由于該模型在構(gòu)建超邊時，將實體及其鄰居實體視為一條超邊，沒有考慮多元關(guān)系中實體的前后順序，所以HGNN只能應(yīng)用于無向超圖中.NHP模型[28]采用圖卷積網(wǎng)絡(luò)以解決知識超圖上的鏈接預(yù)測問題，但是其忽略了超邊的類型，將所有超邊視為同一類型，不能有效學(xué)習(xí)到實體和不同類型關(guān)系之間的交互，因此NHP不適用于具有多種關(guān)系類型的知識超圖.

1.4 基于鍵-值對的方法

基于鍵-值對的方法通常將多元關(guān)系事實表示為一組鍵-值對集合，然后根據(jù)鍵-值對中包含的信息評估整個多元關(guān)系事實成立的合理性，以完成知識超圖中的鏈接預(yù)測任務(wù).

NaLP[29]利用一組角色-值(鍵-值)對來表示多元關(guān)系事實，通過將角色(鍵)及對應(yīng)實體(值)的嵌入表示連接起來，送入到卷積層以及全連接層中，獲得該事實中所有角色-值對的總體相關(guān)性，相關(guān)性越大則表明該多元關(guān)系事實越可能成立.Rosso等人[30]認(rèn)為三元組中具有用于鏈接預(yù)測的基本結(jié)構(gòu)信息，僅用鍵-值對的形式表示多元關(guān)系事實會導(dǎo)致次優(yōu)模型，因此提出了HINGE模型，將多元關(guān)系事實表示為一個主三元組和一組輔助鍵-值對的形式，通過卷積層從主三元組和鍵-值對中學(xué)習(xí)相關(guān)性特征表示，然后利用最小化操作融合這些相關(guān)性特征，再將其送入到全連接層中，獲得該事實成立的得分.NeuInfer[31]和HINGE類似，認(rèn)為多元關(guān)系事實中存在一個主三元組，以及一組用于輔助描述主三元組的鍵-值對，分別計算主三元組的可信性得分，以及主三元組和鍵-值對的相容性得分，利用加權(quán)和獲得多元關(guān)系事實成立的最終得分.StarE[32]模型利用多元關(guān)系事實中前2個實體及對應(yīng)關(guān)系組成主三元組，其余實體用于構(gòu)成鍵-值對，通過信息傳遞網(wǎng)絡(luò)更新嵌入表示，然后利用Transformer[33]對多元關(guān)系事實進行評估.此類方法大多需要確定主三元組，以及設(shè)置鍵-值對中的關(guān)鍵詞，而本文方法將多元關(guān)系事實視為多元組的形式，與這類方法不同，因此不將本文方法與此類基于鍵-值對的方法進行對比.

與上述工作相比，本文工作主要致力于解決有向知識超圖中的鏈接預(yù)測問題.本文提出的Typer模型不局限于k-均勻超圖，能夠同時處理具有不同關(guān)系元數(shù)以及多種關(guān)系類型的知識超圖，且通過引入角色矩陣顯式地為實體在不同關(guān)系及不同位置上的角色信息建模.Typer模型將知識超圖中的多元關(guān)系事實視為多元組，不需要使用額外信息對多元組進行轉(zhuǎn)換.除此之外，Typer模型在理論上具有完全表達性.

2 預(yù)備知識

本節(jié)討論知識超圖中的鏈接預(yù)測問題，并給出一些基本概念.

定義1.知識超圖.知識超圖可以表示為G=(V,E).其中V是實體(節(jié)點)集；E是V的非空有序元組的集合，稱為超邊集.超邊e∈E對應(yīng)于一個關(guān)系類型映射函數(shù)φ(e)∈R，R是關(guān)系集合，表明每條超邊都對應(yīng)于一類特定的關(guān)系r∈R，關(guān)系r的元數(shù)|r|是固定的，即關(guān)系r涉及的實體個數(shù)是固定的.

例1.圖1顯示了一個知識超圖的簡單例子，其中共有7個實體，V={梁再冰,林徽因,梁思成,李蕙仙,梁啟超,賓大,建筑專業(yè)}，3條超邊，E={(梁思成,李蕙仙,梁啟超),(梁再冰,林徽因,梁思成),(梁思成,賓大,建筑專業(yè))}，2種關(guān)系類型，R={“子女-母親-父親”,“學(xué)生-大學(xué)-專業(yè)”}，其中φ(梁思成,李蕙仙,梁啟超)=φ(梁再冰,林徽因,梁思成)=“子女-母親-父親”，φ(梁思成,賓大,建筑專業(yè))=“學(xué)生-大學(xué)-專業(yè)”，關(guān)系“子女-母親-父親”和“學(xué)生-大學(xué)-專業(yè)”的元數(shù)均為3.

在知識圖譜中，一個事實通常被表示為三元組(vh,r,vt)，其中vh∈V表示頭實體，vt∈V表示尾實體，(vh,vt)∈E，r∈R表示實體間的關(guān)系.類似地，在知識超圖中，一個事實可以被表示為一個多元組(r,v1,v2,…,vn)，其中r∈R，vi∈V，(v1,v2,…,vn)∈E.

由于知識超圖并不能儲存所有事實，這里用Tall表示世界中的全部事實集合，對于任意給定的元組(r,v1,v2,…,vn)，若該元組屬于Tall，則稱該元組為正元組，否則稱該元組為負(fù)元組.T?Tall表示知識超圖中的事實集合，T′=Tall-T表示知識超圖中缺失的事實集合.給定一個候選元組t?T，鏈接預(yù)測的目的就是判斷該候選元組t是否屬于知識超圖中缺失的事實，即t是否屬于T′.

3 基于張量分解的Typer模型

本文提出的Typer模型主要由3個模塊組成：角色信息模塊、關(guān)系分解模塊和交互窗口模塊.圖2給出了Typer模型的整體架構(gòu).

Fig. 2 Architecture of Typer圖2 Typer模型的架構(gòu)

3.1 角色信息模塊

由于實體在同一關(guān)系的不同位置，以及不同關(guān)系中具有不同角色.為顯示建模角色信息，這里引入了對應(yīng)于關(guān)系r的角色矩陣cr∈|r|×d，該矩陣的每一行都對應(yīng)于關(guān)系r中一個位置上的角色，即1×d表示關(guān)系r位置p上的角色向量.通過將該角色向量與實體本身的嵌入表示向量進行相加，可以使實體在給定的關(guān)系和位置中具有特定角色信息.形式化地，給定任意元組t，其對應(yīng)于關(guān)系r，對于該元組中第p個實體vk(由于元組t中第p個實體不一定是vp，為不失一般性，使用vk表示元組t中第p個實體)，其在此元組中的嵌入表示為

(1)

其中，vk∈1×d是實體vk的嵌入表示，得到的嵌入表示1×d既具有實體本身的信息，又具有關(guān)系r中位置p上的角色信息.

3.2 關(guān)系分解模塊

通常在解決鏈接預(yù)測問題時，關(guān)系會被當(dāng)成一個整體來進行處理，比如HypE,HSimplE等方法.但對關(guān)系進行分解會使模型具有更好的表現(xiàn)，比如當(dāng)前最先進的模型BoxE，其將關(guān)系分解為一組超矩形，極大地提升了模型的效果.

給定一個元組t，其對應(yīng)于關(guān)系r，對關(guān)系r進行分解后得到多個子關(guān)系，每個子關(guān)系及其連接的2個實體可以構(gòu)成一個子三元組(rpq,vi,vj)，其中rpq表示連接元組t中第p個實體vi和第q個實體vj的子關(guān)系.為了計算多元組t的最終嵌入表示，首先計算每個子三元組(rpq,vi,vj)的嵌入表示：

(2)

其中，°是哈達瑪積，rpq∈1×d是關(guān)系r對應(yīng)的子關(guān)系rpq的嵌入表示，1×d為具有關(guān)系r位置p上角色信息的實體vi的嵌入表示，1×d為具有關(guān)系r位置q上角色信息的實體vj的嵌入表示.因為關(guān)系r可以分解為個子關(guān)系，所以元組t可以生成τ個子三元組.所有子三元組的嵌入表示之和為元組t的最終嵌入表示：

(3)

其中，br∈1×d是對應(yīng)偏置br的嵌入表示，偏置能夠增加模型的靈活性.

3.3 交互窗口模塊

由于關(guān)系和實體間的交互越多，學(xué)習(xí)到的嵌入表示越能體現(xiàn)實體和關(guān)系間的關(guān)聯(lián)[34-35].為使關(guān)系和實體間的交互增多，本文引入了窗口的概念，令實體和關(guān)系在窗口中進行充分的信息交互，從而獲得每個窗口對元組成立貢獻的得分.為方便計算，令窗口大小w為嵌入表示維度d的約數(shù)，即d能被w整除，所以窗口數(shù)量nw=d/w.經(jīng)過逐窗口計算后，共獲得nw個窗口對于元組t成立貢獻的得分，將這些得分加和，即可獲得元組t成立的最終得分：

(4)

其中，σ是sigmoid函數(shù)，索引[(k-1)w+i]指的是嵌入表示中的第(k-1)w+i個元素.通過非線性函數(shù)sigmoid可以使窗口中的實體和關(guān)系的信息交互更加充分.

3.4 模型訓(xùn)練

為學(xué)習(xí)到實體、關(guān)系、角色和偏置的嵌入表示，本文使用小批量梯度下降法(mini-batch gradient descent)對模型進行訓(xùn)練.最小化文獻[36]中提出的交叉熵?fù)p失函數(shù)，該損失函數(shù)已被證明能有效解決鏈接預(yù)測問題[11-12]：

(5)

其中，Ttrain是正元組集合T的訓(xùn)練集，Neg(·)是一個基于給定正元組生成負(fù)元組集合的函數(shù).給定一個正元組t，假如負(fù)采樣率為n，那么對于該正元組中的任意一個實體vi，隨機采樣n個實體來替換該實體，同時確保生成的負(fù)元組t′?T.通過最小化該損失函數(shù)，可以減少模型在鏈接預(yù)測時的誤差，從而使模型具有更好的預(yù)測表現(xiàn).算法1給出了Typer模型的偽代碼.

算法1.Typer模型.

輸出：訓(xùn)練集Ttrain中所有實體嵌入表示v、關(guān)系嵌入表示r、角色嵌入表示c、偏置嵌入表示b.

① 利用Xavier均勻分布[37]初始化v,r,c,b;

② fori=1 toNdo

⑤ 生成負(fù)元組集合Neg(t);

⑥ fort*∈{t}∪Neg(t) do

⑧ end for

⑨ end for

4 Typer模型完全表達性分析

本節(jié)對Typer模型的完全表達性進行理論分析，并給出當(dāng)Typer模型具有完全表達性時，嵌入表示維度的邊界.

(6)

其中，ε<1/(|T|+2).該評分函數(shù)使正元組得分大于等于1-ε，負(fù)元組得分小于(|T|+1)ε.由于1-ε和(|T|+1)ε永遠不相交，所以該評分函數(shù)能夠正確劃分所有正元組與負(fù)元組.因此當(dāng)Typer模型的評分函數(shù)滿足式(6)時，其具有完全表達性.

接下來證明Typer模型能夠使式(6)成立，這里根據(jù)正元組數(shù)量，分|T|>0和|T|=0兩種情況討論.

(7)

獲得tp在第p個窗口中的得分后，繼續(xù)計算其在第q個窗口中的得分(q≠p，|T|>1).由于每個正元組對應(yīng)于一個窗口，所以第q個窗口對應(yīng)于T中第q個正元組tq.這里分2種情況對tp在第q個窗口中的得分進行討論，一種是tp和tq對應(yīng)的關(guān)系相同，一種是tp和tq對應(yīng)的關(guān)系不同.

首先討論第1種情況，由于tp和tq對應(yīng)于同一個關(guān)系，關(guān)系元數(shù)相同，所以至少有一個實體vi∈tp不在tq中，否則tp=tq，即T中有2個重復(fù)的正元組，顯然這是不可能的.因此存在z>0個tp中的實體不在tq中，使得這z個實體在窗口q中的嵌入表示元素值為0.因為每個實體都涉及到|r|-1次子三元組得分的計算，所以z個實體共涉及到z×(|r|-1)次子三元組得分的計算.由于在窗口q中，這z個實體的嵌入表示元素值為0，關(guān)系r對應(yīng)的角色嵌入表示的前|r|個元素中存在一個0，導(dǎo)致z×(|r|-1)次子三元組的計算得分減少x.所以tp在第q個窗口中的得分計算為

(8)

接下來討論第2種情況，由于tp對應(yīng)的關(guān)系和tq對應(yīng)的關(guān)系r不相同，所以第q個窗口中r嵌入表示的所有元素值為0，此時tp在第q個窗口中的得分計算為

(9)

對于任意負(fù)元組，根據(jù)式(8)和式(9)可知，其所有窗口的得分均小于ε，所以負(fù)元組的最終得分必然小于(|T|+1)ε.至此，我們證明了當(dāng)|T|>0時，Typer模型的評分函數(shù)滿足式(6).

證畢.

例2.為便于理解，圖3中給出了該證明的簡單示例，其中空方格表示0.在該例子中，共有|T|=3個正元組，即t1，t2和t3，最大關(guān)系元數(shù)αmax=3.令窗口大小為αmax=3，窗口數(shù)量為|T|=3，此時使Typer模型具有完全表達性的嵌入表示維度為αmax|T|=9.

Fig. 3 A toy example of Typer model embedding assignment圖3 Typer模型嵌入表示賦值的簡單示例

所以正元組t2的最后得分大于1-ε.同理，對于任意負(fù)元組，經(jīng)過上述計算，可以得到每個窗口的得分都小于ε，所以最后總的得分小于3ε，也必然小于(|T|+1)ε=4ε.

5 實 驗

本節(jié)通過知識超圖上的鏈接預(yù)測任務(wù)對Typer模型進行有效性驗證.我們將實驗分為3組以達到不同的實驗?zāi)康模?)在2個公開數(shù)據(jù)集上對Typer模型進行有效性實驗，并將其與之前的先進方法進行對比，以評估Typer模型的有效性；2)通過消融實驗分析Typer模型各模塊對模型性能的影響；3)通過參數(shù)敏感性實驗分析一些重要超參數(shù)對模型魯棒性的影響.在詳細說明這些實驗前，首先介紹實驗中用到的數(shù)據(jù)集、評價指標(biāo)以及基線模型和實驗設(shè)置.

5.1 數(shù)據(jù)集

本文使用2個公開的真實大型知識超圖數(shù)據(jù)集對Typer模型進行評估：

1) JF17K[11]是基于Freebase過濾得到的，首先刪除Freebase中包含出現(xiàn)次數(shù)較少的實體的事實，以及涉及字符串、數(shù)字及枚舉類型的事實，從每個元關(guān)系中隨機選出10 000個事實，進一步刪除包含出現(xiàn)次數(shù)少于5的實體的事實，然后利用文獻[11]中提出的逆向化方法生成多元組以構(gòu)成數(shù)據(jù)集.

2) FB-AUTO[12]也是基于Freebase過濾得到的，移除Freebase中只包含一個實體的事實，以及涉及到數(shù)字和枚舉類型的事實，按順序連接具有相同關(guān)系和頭實體的事實，構(gòu)成多元組，從中選擇頭實體標(biāo)簽為“automotive”的事實構(gòu)成此數(shù)據(jù)集.

由于JF17K中沒有驗證集，所以本文使用與文獻[12]和文獻[16]相同的訓(xùn)練、驗證、測試集設(shè)置，即從JF17K的訓(xùn)練集中隨機選取20%作為驗證集.JF17K和FB-AUTO數(shù)據(jù)集的詳細統(tǒng)計信息如表1所示：

Table 1 Statistics of Datasets表1 數(shù)據(jù)集的統(tǒng)計信息

5.2 評價指標(biāo)

(10)

(11)

其中，r是正元組t對應(yīng)的關(guān)系，cond(·)是條件函數(shù)，當(dāng)條件成立時值為1，否則值為0.MRR和Hits@k值越大表明模型性能越好.

5.3 基線模型和實驗設(shè)置

為公平比較，本文只考慮那些能夠處理具有不同元數(shù)關(guān)系的數(shù)據(jù)，且不需要額外信息輔助的模型作為基線模型.因此選擇如下模型作為本文的基線模型：

1) m-DistMult[12].對DistMult算法[15]進行了擴展，通過計算多元關(guān)系事實中所有實體和關(guān)系嵌入表示的哈達瑪積的元素和，獲得多元關(guān)系事實成立的得分.

2) m-CP[12].對CP算法[14]進行了擴展，通過賦予一個實體多個嵌入表示，以建模同一實體在不同位置上的角色信息.

3) m-TransH[11].對TransH算法[13]進行了擴展，通過將實體嵌入表示映射到對應(yīng)關(guān)系的超平面上，以建模同一實體在不同關(guān)系中的角色信息.

4) HSimplE[12].將實體嵌入表示視作該實體基于不同位置嵌入表示的連接，對嵌入表示中的元素移動，即可獲得實體基于不同位置的嵌入表示.

5) HypE[12].通過使用多個卷積核獲得實體在不同位置上的嵌入表示，對卷積后的實體嵌入表示和關(guān)系嵌入表示的哈達瑪積求元素和，即為多元關(guān)系事實成立的得分.

6) BoxE[19].將實體映射到潛在向量空間中，基于同一向量空間將多元關(guān)系分解為多個顯式超矩形，通過計算實體嵌入表示相對于超矩形的位置，獲得多元關(guān)系事實成立的得分.

本文與所有基線模型公開的最好結(jié)果進行對比.由于BoxE使用的排名方法與其他基線模型不同，為公平比較，將其改為其他基線模型中使用的排名方法，然后進行對比實驗.此外，也給出了Typer模型在BoxE排名方法下的對比實驗結(jié)果.

我們利用PyTorch[38]實現(xiàn)Typer模型，并通過Adam優(yōu)化器[39]進行優(yōu)化.實驗?zāi)J(rèn)參數(shù)設(shè)置如下，嵌入表示維度為200，負(fù)采樣率為10，訓(xùn)練次數(shù)為1 000，批大小為128，學(xué)習(xí)率為0.1，窗口大小為2，驗證檢查點為100，選擇在驗證集上MRR指標(biāo)表現(xiàn)最好的模型進行測試.

5.4 有效性分析

表2給出了Typer模型和其他先進模型在數(shù)據(jù)集JF17K和FB-AUTO上的對比實驗結(jié)果.實驗結(jié)果表明，本文提出的Typer模型在2個知識超圖數(shù)據(jù)集上的所有評價指標(biāo)均超過了基線模型.更具體地說，就MRR指標(biāo)而言，Typer模型相較于HypE在數(shù)據(jù)集JF17K和FB-AUTO上分別提升了6.88%和8.83%.在FB-AUTO數(shù)據(jù)集中，Typer模型Hits@3指標(biāo)的結(jié)果已經(jīng)超過了所有基線模型Hits@10指標(biāo)的結(jié)果，表明了Typer模型能夠有效完成知識超圖中的鏈接預(yù)測任務(wù).

Table 2 Results of Link Prediction表2 鏈接預(yù)測結(jié)果

根據(jù)實驗結(jié)果可以發(fā)現(xiàn)，像m-DistMult和m-CP這類直接將二元關(guān)系鏈接預(yù)測模型推廣到多元關(guān)系上的模型實驗效果并不好，說明對于多元關(guān)系鏈接預(yù)測問題，需要根據(jù)其特點進行針對性設(shè)計，多元關(guān)系鏈接預(yù)測問題與二元關(guān)系鏈接預(yù)測問題并不完全相同.HSimplE和HypE結(jié)果低于Typer的主要原因是由于二者均將關(guān)系視為一個整體，且沒有考慮到同一實體在不同關(guān)系中具有不同角色.通過對實驗結(jié)果的分析，Typer模型表現(xiàn)較好的主要原因是其不僅考慮到實體在不同關(guān)系以及不同位置上具有不同角色，而且對關(guān)系進行了細化分解，還引入了窗口的概念，使實體與關(guān)系間的交互增多.

由于BoxE使用了不同的排名方法，所以為了公平比較，這里在FB-AUTO數(shù)據(jù)集上使用BoxE的排名方法對Typer模型性能進行評估，其中窗口大小設(shè)為1，其余參數(shù)保持不變，實驗對比結(jié)果如圖4所示.從圖4給出的結(jié)果可以看出，本文方法在各項指標(biāo)上都超過了BoxE.此外，BoxE在不同排名方法下，模型性能相差很大，就MRR指標(biāo)而言，實驗結(jié)果相差為0.352.而本文方法各項指標(biāo)基本保持穩(wěn)定，MRR指標(biāo)上的實驗結(jié)果相差僅有0.002.表明Typer模型能夠很好地學(xué)習(xí)到實體與關(guān)系間的交互，所以在不同排名方法下仍然保持性能穩(wěn)定.

Fig. 4 Comparison of Typer and BoxE on FB-AUTO圖4 Typer和BoxE在FB-AUTO數(shù)據(jù)集上的對比

為了深入研究Typer模型在處理不同元數(shù)關(guān)系時的差異，首先將FB-AUTO測試集中的數(shù)據(jù)按照關(guān)系元數(shù)進行劃分，其中包含764個二元關(guān)系、44個四元關(guān)系以及1 372個五元關(guān)系.然后令Typer模型分別在這3個具有不同元數(shù)關(guān)系的數(shù)據(jù)集上進行測試.表3給出了Typer模型及基線模型關(guān)于MRR及Hits@10指標(biāo)的實驗對比結(jié)果.從實驗結(jié)果中可以看出Typer模型在所有元數(shù)關(guān)系上均超過了基線模型.這表明Typer模型不僅能夠很好地處理具有更高元數(shù)的關(guān)系，在處理二元關(guān)系時同樣具有優(yōu)勢.

Table 3 Results of Link Prediction for Relations with Different Arities表3 具有不同元數(shù)關(guān)系的鏈接預(yù)測結(jié)果

5.5 消融實驗

為驗證各模塊對模型性能的影響，本文基于Typer模型設(shè)計了3個變體，即Typer-Role，Typer-Rel以及Typer-Win，分別表示在Typer模型的基礎(chǔ)上移除了角色信息模塊、關(guān)系分解模塊以及交互窗口模塊.Typer模型及其3個變體在FB-AUTO數(shù)據(jù)集上的實驗對比結(jié)果如表4所示：

Table 4 Results of Ablation Experiments on FB-AUTO表4 FB-AUTO數(shù)據(jù)集上的消融實驗結(jié)果

觀察表4，可見Typer模型在各項指標(biāo)上均優(yōu)于其3個變體.具體地，就MRR指標(biāo)而言，Typer模型相較于變體Typer-Role，Typer-Rel以及Typer-Win分別提升了1.16%，1.16%以及0.69%.顯然缺少任何一個模塊都會使得模型效果變差，這表明Typer模型的3個模塊能夠很好地捕捉到實體與關(guān)系之間的交互.更重要的是，缺少其中任何一個模塊都不能保證Typer模型仍然具有理論上的完全表達性.

5.6 參數(shù)敏感性分析

為研究Typer模型的魯棒性，本文在FB-AUTO數(shù)據(jù)集上進一步分析了一些重要超參數(shù)對模型性能的影響，包括嵌入表示維度d、負(fù)采樣率n以及窗口大小w.令嵌入表示維度d∈{50,100,150,200,250,300,350,400}，負(fù)采樣率n∈{1,5,10,15,20}，窗口大小w∈{1,2,4,5,8,10,20}.為實驗公平，除當(dāng)前研究的超參數(shù)外，其余超參數(shù)均與5.3節(jié)實驗設(shè)置中相同，實驗結(jié)果在圖5中給出.

圖5(a)顯示了Typer模型在不同嵌入表示維度下，各項評價指標(biāo)的變化趨勢.從圖5可以看出，當(dāng)嵌入表示維度小于200時，隨著維度的增加，各項指標(biāo)呈上升趨勢；而當(dāng)維度到達200時，各項評價指標(biāo)逐漸達到平穩(wěn)；表明當(dāng)嵌入表示維度超過200時，Typer模型是相對穩(wěn)定的.

圖5(b)顯示了Typer模型在不同負(fù)采樣率下，各項評價指標(biāo)的變化趨勢.從圖中可以看出，負(fù)采樣率對Typer模型的影響不大.因此，就負(fù)采樣率而言，Typer模型是穩(wěn)定的.

圖5(c)顯示了Typer模型在不同窗口大小下，各項評價指標(biāo)的變化趨勢.從圖中可以看出，當(dāng)窗口大小開始增加時，實驗結(jié)果中各項指標(biāo)均有所提升，表明增加實體與關(guān)系間的交互有助于模型性能的提升；但隨著窗口大小進一步增大時，各項指標(biāo)開始下降，表明過多的交互可能對模型學(xué)習(xí)無益.因此，窗口大小對模型Typer而言是一個敏感的超參數(shù)，需要根據(jù)數(shù)據(jù)集對窗口大小進行仔細調(diào)整以使模型發(fā)揮出最佳效果.

Fig. 5 Parameter sensitivity analysis圖5 參數(shù)敏感性分析

6 總結(jié)與展望

本文提出了一個用于解決知識超圖鏈接預(yù)測問題的張量分解模型Typer，并證明了該模型在理論上具有完全表達性.Typer模型不僅考慮到實體在不同關(guān)系以及不同位置上具有不同角色，還考慮到對關(guān)系進行細化分解有助于提升模型性能.此外，Typer模型引入了窗口的概念，以增加實體與關(guān)系間的信息流動.在2個大型公開知識超圖數(shù)據(jù)集上進行的詳實實驗說明了Typer模型的有效性和先進性.

下一步，計劃研究將背景知識(例如規(guī)則等)注入到模型中，以及融合多模態(tài)數(shù)據(jù)以進一步提升模型性能的方法.此外，基于張量分解的方法雖然具有數(shù)學(xué)理論支持，且有著較為廣泛的學(xué)習(xí)研究，但是其計算量較大，訓(xùn)練推理時間較長，無法做到實時鏈接預(yù)測，所以后續(xù)計劃嘗試采用并行計算的方法來加速模型的訓(xùn)練和推理.同時，還計劃探索Typer模型在現(xiàn)實中的應(yīng)用，我們認(rèn)為將其擴展到大規(guī)模數(shù)據(jù)集上也是一個有趣的研究方向.