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

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

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

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

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

Fig. 1 A toy example of knowledge hypergraph圖1 知識(shí)超圖的簡(jiǎn)單示例

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

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

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

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

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

本文的主要貢獻(xiàn)有3個(gè)方面：

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

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

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

1 相關(guān)工作

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

1.1 基于平移的方法

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

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

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

1.2 基于張量分解的方法

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

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

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

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

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

1.4 基于鍵-值對(duì)的方法

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

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

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

2 預(yù)備知識(shí)

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

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

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

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

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

3 基于張量分解的Typer模型

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

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

3.1 角色信息模塊

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

(1)

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

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

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

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

(2)

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

(3)

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

3.3 交互窗口模塊

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

(4)

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

3.4 模型訓(xùn)練

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

(5)

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

算法1.Typer模型.

輸出：訓(xùn)練集Ttrain中所有實(shí)體嵌入表示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模型完全表達(dá)性分析

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

(6)

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

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

(7)

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

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

(8)

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

(9)

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

證畢.

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

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

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

5 實(shí) 驗(yàn)

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

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

本文使用2個(gè)公開(kāi)的真實(shí)大型知識(shí)超圖數(shù)據(jù)集對(duì)Typer模型進(jìn)行評(píng)估：

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

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

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

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

5.2 評(píng)價(jià)指標(biāo)

(10)

(11)

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

5.3 基線模型和實(shí)驗(yàn)設(shè)置

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

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

2) m-CP[12].對(duì)CP算法[14]進(jìn)行了擴(kuò)展，通過(guò)賦予一個(gè)實(shí)體多個(gè)嵌入表示，以建模同一實(shí)體在不同位置上的角色信息.

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

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

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

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

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

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

5.4 有效性分析

表2給出了Typer模型和其他先進(jìn)模型在數(shù)據(jù)集JF17K和FB-AUTO上的對(duì)比實(shí)驗(yàn)結(jié)果.實(shí)驗(yàn)結(jié)果表明，本文提出的Typer模型在2個(gè)知識(shí)超圖數(shù)據(jù)集上的所有評(píng)價(jià)指標(biāo)均超過(guò)了基線模型.更具體地說(shuō)，就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)超過(guò)了所有基線模型Hits@10指標(biāo)的結(jié)果，表明了Typer模型能夠有效完成知識(shí)超圖中的鏈接預(yù)測(cè)任務(wù).

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

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

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

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

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

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

5.5 消融實(shí)驗(yàn)

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

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

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

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

為研究Typer模型的魯棒性，本文在FB-AUTO數(shù)據(jù)集上進(jìn)一步分析了一些重要超參數(shù)對(duì)模型性能的影響，包括嵌入表示維度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}.為實(shí)驗(yàn)公平，除當(dāng)前研究的超參數(shù)外，其余超參數(shù)均與5.3節(jié)實(shí)驗(yàn)設(shè)置中相同，實(shí)驗(yàn)結(jié)果在圖5中給出.

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

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

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

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

6 總結(jié)與展望

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

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