基于平移約束的異質(zhì)超網(wǎng)絡(luò)表示學(xué)習(xí)

劉貞國，朱 宇，趙海興，王曉英，黃建強(qiáng)

(1. 青海大學(xué) 計(jì)算機(jī)技術(shù)與應(yīng)用系，青海 西寧810000； 2. 青海師范大學(xué) 藏語智能信息處理及應(yīng)用國家重點(diǎn)實(shí)驗(yàn)室，青海 西寧810000)

0 引言

網(wǎng)絡(luò)表示學(xué)習(xí)[1]將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)映射到一個(gè)低維的向量表示空間，學(xué)習(xí)到的節(jié)點(diǎn)表示向量可以被用于網(wǎng)絡(luò)分析任務(wù)，例如，節(jié)點(diǎn)分類[2]、鏈接預(yù)測[3]、社區(qū)檢測[4]等。目前，超網(wǎng)絡(luò)表示學(xué)習(xí)逐漸受到研究者的廣泛研究。根據(jù)超網(wǎng)絡(luò)表示學(xué)習(xí)方法[5]的特點(diǎn)，將其劃分為展開式譜分析方法和非展開式方法。展開式譜分析方法將超網(wǎng)絡(luò)轉(zhuǎn)化為普通網(wǎng)絡(luò)來學(xué)習(xí)節(jié)點(diǎn)表示向量。例如，星型擴(kuò)展和團(tuán)擴(kuò)展[6]，該類方法在超網(wǎng)絡(luò)展開過程中會(huì)丟失超邊信息。非展開式方法，沒有分解超邊，具體來說，該類方法主要分為非展開式譜分析方法和基于神經(jīng)網(wǎng)絡(luò)的方法。例如，Hyper2vec[7]、HPSG[8]、HPHG[8]、DHNE[9]等。

從以上兩類工作可以看出，展開式譜分析方法雖然直觀靈活，但是存在信息損失。非展開式方法沒有分解超邊。例如，Hyper2vec、HPSG通過Skip-gram[10]模型捕獲基于超邊游走序列上的節(jié)點(diǎn)成對關(guān)系，但是沒有很好地捕獲節(jié)點(diǎn)之間的元組關(guān)系。HPHG通過Hyper-gram模型有效地捕獲了元組關(guān)系。DHNE通過結(jié)合多層感知器來捕獲元組關(guān)系，但是HPHG和DHNE均局限于固定大小的異質(zhì)超邊。

受到上述方法的啟發(fā)，為了應(yīng)對復(fù)雜的超網(wǎng)絡(luò)結(jié)構(gòu)，同時(shí)捕獲節(jié)點(diǎn)之間的成對關(guān)系和元組關(guān)系，本文提出了一種基于平移約束的異質(zhì)超網(wǎng)絡(luò)表示學(xué)習(xí)方法HRTC。

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

(1) 由于超網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，首先提出一種結(jié)合團(tuán)擴(kuò)展和星型擴(kuò)展的方法，將異質(zhì)超網(wǎng)絡(luò)轉(zhuǎn)換為異質(zhì)網(wǎng)絡(luò)[11]；然后，提出感知節(jié)點(diǎn)語義相關(guān)性的元路徑游走方法來捕獲異質(zhì)節(jié)點(diǎn)之間的語義關(guān)系；最后，通過引入知識(shí)表示學(xué)習(xí)中的平移機(jī)制，在基于拓?fù)渑缮繕?biāo)函數(shù)的模型上融入超邊，提出基于平移約束的異質(zhì)超網(wǎng)絡(luò)表示學(xué)習(xí)方法HRTC，該方法可以同時(shí)捕獲節(jié)點(diǎn)之間的成對關(guān)系和元組關(guān)系。

(2) 在三個(gè)不同類型的超網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了評估實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，HRTC方法在鏈接預(yù)測和超網(wǎng)絡(luò)重建任務(wù)中，效果優(yōu)于其他基線方法。

本文組織結(jié)構(gòu)如下： 第1節(jié)正式定義了研究問題；第2節(jié)介紹預(yù)備知識(shí)；第3節(jié)詳細(xì)介紹HRTC方法；實(shí)驗(yàn)結(jié)果見第4節(jié)；最后總結(jié)全文。

1 問題定義

圖1 異質(zhì)超圖

定義1(異質(zhì)超網(wǎng)絡(luò)表示學(xué)習(xí))給定一個(gè)異質(zhì)超網(wǎng)絡(luò)H=(V，E)，異質(zhì)超網(wǎng)絡(luò)表示學(xué)習(xí)為異質(zhì)超網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)vi∈V學(xué)習(xí)一個(gè)低維向量rvi∈Rk，其中，k? |V|。其目的是使得學(xué)習(xí)到的向量顯式地保留異質(zhì)超網(wǎng)絡(luò)結(jié)構(gòu)信息，并且在異質(zhì)超網(wǎng)絡(luò)結(jié)構(gòu)中相鄰的節(jié)點(diǎn)在向量表示空間中也相鄰。

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

2.1 超圖轉(zhuǎn)化為普通圖

超圖是圖的推廣，圖是超圖的特例。由于對圖的研究比較成熟，如果能把超圖轉(zhuǎn)化為圖，通過對圖的研究加深對相應(yīng)超圖的認(rèn)識(shí)，不失為研究超圖的一種可取的方法。文獻(xiàn)[12]分別通過團(tuán)擴(kuò)展和星型擴(kuò)展，將超圖轉(zhuǎn)化為2-截圖和關(guān)聯(lián)圖。

超圖轉(zhuǎn)化為2-截圖、關(guān)聯(lián)圖的詳細(xì)策略如下：

2.1.1 2-截圖

超圖H=(V，E)的2-截圖(2-section graph)是滿足以下條件的圖S=(V′，E′)：

(1)V′=V，即S的節(jié)點(diǎn)集合與H的節(jié)點(diǎn)集合相同；

(2) 任意兩個(gè)不同的節(jié)點(diǎn)之間連一條邊，當(dāng)且僅當(dāng)它們同時(shí)包含在H的至少一條超邊中。

圖2是圖1超圖的2-截圖。

圖2 2-截圖

2.1.2 關(guān)聯(lián)圖

超圖H=(V，E)的關(guān)聯(lián)圖是滿足以下條件的圖I=(V′，E′)：

(1)V′=V∪E，即將超圖H中的每條超邊看成一個(gè)節(jié)點(diǎn)，I的節(jié)點(diǎn)集合是H的節(jié)點(diǎn)集合和超邊集合的并集；

(2)vi∈V和ei∈E相鄰，當(dāng)且僅當(dāng)vi∈ei。

圖3為圖1超圖的關(guān)聯(lián)圖，其中e節(jié)點(diǎn)為超邊節(jié)點(diǎn)。

圖3 關(guān)聯(lián)圖

2.2 TransE模型

知識(shí)表示實(shí)際上是讓知識(shí)圖譜的實(shí)體和關(guān)系向量化。具體地說，為知識(shí)庫中的每一個(gè)實(shí)體或關(guān)系學(xué)習(xí)一個(gè)低維向量。為了簡化起見，使用(h，r，t)表示三元組，其中，h表示頭實(shí)體向量，r表示關(guān)系向量，t表示尾實(shí)體向量，在知識(shí)圖譜的關(guān)系抽取中，經(jīng)常采用基于平移的知識(shí)表示學(xué)習(xí)模型TransE[13]。該模型認(rèn)為，如果存在一個(gè)正確的三元組(h，r，t)，則頭實(shí)體向量h加上關(guān)系向量r約等于尾實(shí)體向量t，即h+r≈t。否則，其向量之間不滿足這種關(guān)系。TransE模型如圖4所示。

圖4 TransE模型

3 HRTC方法

HRTC方法的框架如圖5所示。該框架包括4個(gè)主要部分： (a)2-截圖+關(guān)聯(lián)圖； (b)感知節(jié)點(diǎn)語義相關(guān)性的元路徑游走SRwalk； (c)基于拓?fù)渑缮繕?biāo)函數(shù)的模型； (d)基于平移約束目標(biāo)函數(shù)的模型。下面詳細(xì)介紹HRTC方法的4個(gè)主要部分。

圖5 HRTC框架

其中，Ev和θv分別表示嵌入矩陣和參數(shù)向量，ev、eh、er分別為v、h、r對應(yīng)的向量且eh+r=eh+er，其中，超邊r同時(shí)與目標(biāo)節(jié)點(diǎn)v和節(jié)點(diǎn)h關(guān)聯(lián)，圖5(a)、(b)、(c)、(d)分別為該框架的4個(gè)主要部分。

3.1 2-截圖+關(guān)聯(lián)圖

團(tuán)擴(kuò)展方法認(rèn)為超邊內(nèi)部節(jié)點(diǎn)之間兩兩相關(guān)，將超圖轉(zhuǎn)換為2-截圖。星型擴(kuò)展方法認(rèn)為超邊內(nèi)部節(jié)點(diǎn)之間兩兩不相關(guān)，將超圖轉(zhuǎn)換為關(guān)聯(lián)圖。因此，在異質(zhì)超網(wǎng)絡(luò)表示學(xué)習(xí)過程中應(yīng)用團(tuán)擴(kuò)展方法和星型擴(kuò)展方法都會(huì)導(dǎo)致不同程度的超網(wǎng)絡(luò)結(jié)構(gòu)信息損失。

鑒于上述情況，本文提出一種結(jié)合團(tuán)擴(kuò)展和星型擴(kuò)展的方法，將超圖轉(zhuǎn)換為2-截圖+關(guān)聯(lián)圖。具體來說，通過分析超邊內(nèi)部節(jié)點(diǎn)之間的語義相關(guān)性，認(rèn)為具有語義相關(guān)性的節(jié)點(diǎn)之間直接關(guān)聯(lián)，不具有語義相關(guān)性的節(jié)點(diǎn)通過超邊間接關(guān)聯(lián)。節(jié)點(diǎn)語義相關(guān)性的定義如下。

定義2(節(jié)點(diǎn)語義相關(guān)性)節(jié)點(diǎn)代表的實(shí)體對象之間存在關(guān)系。

元組節(jié)點(diǎn)之間具有語義相關(guān)性，而元組子集節(jié)點(diǎn)之間可能不具有語義相關(guān)性。例如，若圖1為drug藥物超網(wǎng)絡(luò)，則圖6為圖1轉(zhuǎn)換后的2-截圖+關(guān)聯(lián)圖，其中a，b，c分別代表用戶節(jié)點(diǎn)、藥物節(jié)點(diǎn)和不良反應(yīng)節(jié)點(diǎn)，則元組關(guān)系(用戶，藥物，反應(yīng))被看作超邊來構(gòu)建超網(wǎng)絡(luò)。具體來說，在沒有藥物信息的情況下建立用戶與不良反應(yīng)之間的聯(lián)系和在沒有藥物不良反應(yīng)信息的情況下建立用戶與藥物之間的聯(lián)系都是不合理的，所以用戶與不良反應(yīng)、用戶與藥物被認(rèn)為語義不相關(guān)。然而，對于每種藥物，都會(huì)在出廠標(biāo)明一種或幾種特定的不良反應(yīng)，所以藥物與不良反應(yīng)被認(rèn)為語義相關(guān)，則藥物節(jié)點(diǎn)與不良反應(yīng)節(jié)點(diǎn)之間直接關(guān)聯(lián)，而用戶節(jié)點(diǎn)與藥物節(jié)點(diǎn)、用戶節(jié)點(diǎn)與不良反應(yīng)節(jié)點(diǎn)之間通過超邊間接關(guān)聯(lián)。

圖6 2-截圖+關(guān)聯(lián)圖

總之，如果超邊內(nèi)部節(jié)點(diǎn)之間兩兩語義相關(guān)，則2-截圖+關(guān)聯(lián)圖為完全組合圖；如果超邊內(nèi)部節(jié)點(diǎn)之間全部語義不相關(guān)，則2-截圖+關(guān)聯(lián)圖退化為關(guān)聯(lián)圖；如果超邊內(nèi)部部分節(jié)點(diǎn)之間存在語義相關(guān)，則2-截圖+關(guān)聯(lián)圖為在關(guān)聯(lián)圖基礎(chǔ)上加上具有語義相關(guān)性節(jié)點(diǎn)的邊。

超圖轉(zhuǎn)換為2-截圖+關(guān)聯(lián)圖的實(shí)現(xiàn)細(xì)節(jié)如算法1所示。

算法1 超圖轉(zhuǎn)換為2-截圖+關(guān)聯(lián)圖輸入: 異質(zhì)超圖H=(V,E);輸出: 2-截圖+關(guān)聯(lián)圖的鄰接矩陣A(|V|+|E|)×(|V|+|E|);/?將異質(zhì)超圖H作為輸入,獲取2-截圖+關(guān)聯(lián)圖的鄰接矩陣A(|V|+|E|)×(|V|+|E|),其中,A的元素初始化為0?/ 1. for e in E do 2. for vi in e do 3 . for vj in e do 4. if vi和vj語義相關(guān) do 5. A(vi,vj)=A(vj,vi)=1 6. else 7. A(vi,e)=A(e,vi)=A(vj,e)=A(e,vj)=1 8. end for 9. end for 10. end for 11. return A

3.2 感知節(jié)點(diǎn)語義相關(guān)性的元路徑游走SRwalk

對于上述轉(zhuǎn)換后的異質(zhì)網(wǎng)絡(luò)G=(V，E)，設(shè)計(jì)一種感知節(jié)點(diǎn)語義相關(guān)性的元路徑游走方法SRwalk來捕獲節(jié)點(diǎn)之間的語義關(guān)系，即成對關(guān)系和元組關(guān)系。下面給出元路徑的定義。

(1)

與傳統(tǒng)隨機(jī)游走相比，SRwalk可以更好地保留超網(wǎng)絡(luò)中節(jié)點(diǎn)之間的元組關(guān)系和增強(qiáng)節(jié)點(diǎn)之間的成對關(guān)系。如圖7中的游走序列，a1-e2-b1-c1和c1-b2-e1-a1這種子序列可以高可信度地捕獲節(jié)點(diǎn)之間的元組關(guān)系，如(a1，b1，c1)和(a1，b2，c1)，而且增強(qiáng)了b1和b2之間的相關(guān)性。

圖7 感知節(jié)點(diǎn)語義相關(guān)性的元路徑游走

SRwalk方法的實(shí)現(xiàn)細(xì)節(jié)如算法2所示。

算法2 SRwalk方法輸入: 2-截圖+關(guān)聯(lián)圖的鄰接矩陣A;采樣次數(shù)N和采樣長度L;輸出: 感知節(jié)點(diǎn)語義相關(guān)性的元路徑游走序列paths;/?采用感知節(jié)點(diǎn)語義相關(guān)性的元路徑游走ξ: V1R1→V2…ViRi→Vi+1…VjRe→Vj+1…Vl-1Rl-1→Vl來采樣異質(zhì)序列,?/ 1. for n in range (1,N+1) do 2. for v in V1 3. 按照ξ由v開始遍歷A,采樣長度L的異質(zhì)序列path 4. 將path添加到paths中 5. end for 6. end for 7. return paths

3.3 拓?fù)渑缮繕?biāo)函數(shù)

基于SRwalk獲取的異質(zhì)節(jié)點(diǎn)序列C，提出了拓?fù)渑缮繕?biāo)函數(shù)來捕獲節(jié)點(diǎn)成對關(guān)系。下面詳細(xì)介紹拓?fù)渑缮繕?biāo)函數(shù)。

對于目標(biāo)節(jié)點(diǎn)v∈C，當(dāng)v的上下文節(jié)點(diǎn)為c∈context(v)時(shí)，將c視為正樣本，將非上下文節(jié)點(diǎn)Neg(v)視為負(fù)樣本。節(jié)點(diǎn)的標(biāo)簽定義如式(2)所示。

(2)

p(u|v)表示在已知目標(biāo)節(jié)點(diǎn)v的條件下預(yù)測其上下文節(jié)點(diǎn)u的概率。對于給定節(jié)點(diǎn)序列C，拓?fù)渑缮繕?biāo)函數(shù)如式(3)所示。

(3)

對于每一個(gè)節(jié)點(diǎn)v，嵌入向量ev是v作為目標(biāo)節(jié)點(diǎn)的表示向量，參數(shù)向量θv是v作為上下文節(jié)點(diǎn)時(shí)的表示向量。則式(3)中的p(u|v)定義如式(4)所示。

(4)

(5)

因此，公式L1重新表示如式(6)所示。

(6)

最大化L1意味著同時(shí)最大化正樣本的預(yù)測概率和最小化負(fù)樣本的預(yù)測概率。通過捕獲節(jié)點(diǎn)成對關(guān)系，將超網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)編碼到節(jié)點(diǎn)向量表示中。

3.4 平移約束目標(biāo)函數(shù)

雖然最大化拓?fù)渑缮繕?biāo)函數(shù)可以捕獲節(jié)點(diǎn)成對關(guān)系，但是沒有充分考慮超邊。因此，鑒于上述情況，受到TransE模型中的平移機(jī)制在知識(shí)表示中成功應(yīng)用的啟發(fā)，將超網(wǎng)絡(luò)中節(jié)點(diǎn)之間的交互看作節(jié)點(diǎn)表示向量通過超邊表示向量進(jìn)行的平移操作。通過引入平移機(jī)制為目標(biāo)節(jié)點(diǎn)增加超邊約束來捕獲節(jié)點(diǎn)之間的元組關(guān)系。下面詳細(xì)介紹平移約束目標(biāo)函數(shù)。

具體來說，對于目標(biāo)節(jié)點(diǎn)v∈V，Rv是與v關(guān)聯(lián)的超邊集合，Hr是與v具有關(guān)系r的節(jié)點(diǎn)集合。如果存在超邊r∈Rv和節(jié)點(diǎn)h∈Hr，即超邊r同時(shí)與節(jié)點(diǎn)v和h關(guān)聯(lián)，則存在一個(gè)正確的三元組(h，r，v)，稱h是與v具有關(guān)系r的節(jié)點(diǎn)。當(dāng)v的負(fù)樣本子集為NEG(v)時(shí)，對于?ξ∈V，節(jié)點(diǎn)ξ標(biāo)簽定義如式(7)所示。

(7)

對于給定節(jié)點(diǎn)序列C，平移約束目標(biāo)函數(shù)定義如式(8)所示。

(8)

其中，eh+r=eh+er，θξ為ξ的參數(shù)向量。通過最大化L2，超邊信息被編碼到節(jié)點(diǎn)表示向量中。

3.5 聯(lián)合優(yōu)化目標(biāo)函數(shù)

通過聯(lián)合優(yōu)化拓?fù)渑缮繕?biāo)函數(shù)和平移約束目標(biāo)函數(shù)來捕獲節(jié)點(diǎn)之間的成對關(guān)系和元組關(guān)系，HRTC可以得到質(zhì)量更高的節(jié)點(diǎn)表示向量，為了便于計(jì)算，將函數(shù)L1和L2取對數(shù)后相加并最大化聯(lián)合優(yōu)化目標(biāo)函數(shù)如式(9)所示。

L=L1+β·L2

(9)

其中，β是平衡基于拓?fù)渑缮繕?biāo)函數(shù)的模型和基于平移約束目標(biāo)函數(shù)的模型的調(diào)和因子。為了便于推導(dǎo)，將最內(nèi)層花括號內(nèi)容簡記為L(v，u，ξ，h,r)，即：

(10)

通過使用隨機(jī)梯度上升(SGA)算法來優(yōu)化目標(biāo)函數(shù)L(v，u，ξ，h，r)，關(guān)鍵是給出L(v，u，ξ，h，r)的4種梯度。

首先L(v，u，ξ，h,r)關(guān)于θu的梯度計(jì)算如式(11)所示。

(11)

因此，對θu的更新如式(12)所示。

(12)

其中，α是HRTC方法的學(xué)習(xí)率。當(dāng)L(u)=1和L(u)=0時(shí)，分別更新正負(fù)樣本節(jié)點(diǎn)的參數(shù)向量。

其次，利用ev和θu的對稱性來計(jì)算L(v，u，ξ，h，r)關(guān)于ev的梯度如式(13)所示。

(13)

因此，對嵌入向量ev的更新如式(14)所示。

(14)

然后，L(v，u，ξ，h，r)關(guān)于θξ的梯度計(jì)算如式(15)所示。

+[1-δ(ξ)]

·eh+r-[1-δ(ξ)]

-[1-δ(ξ)]

(15)

因此，對θξ的更新如式(16)所示。

(16)

當(dāng)δ(ξ)=1或δ(ξ)=0時(shí)，分別更新正負(fù)樣本節(jié)點(diǎn)的參數(shù)向量。

(17)

由于eh+r=eh+er，所以對eh和er的更新如式(18)、式(19)所示。

HRTC方法細(xì)節(jié)如算法3所示。

算法3 HRTC方法輸入: 超網(wǎng)絡(luò)H=(V,E),嵌入維度d;輸出: 嵌入矩陣Ev∈R(|V|+|E|)×d; 1. for v in V∪E do 2. 初始化嵌入向量ev∈Rd×1 3. 初始化參數(shù)向量θv∈Rd×1 4. end for /?C為SRwalk方法采樣的語料庫?/ 5. for v in C do 6. for c in context(v) do 7. for u in {c}∪Neg(v) do 8. 根據(jù)式(12)更新θu 9. end for 10. 根據(jù)式(14)更新ev 11. end for 12. if v∈V do 13. for r in Rv do 14. for h in Hr do 15. for ξ in {v}∪NEG(v) do 16. 根據(jù)式(16)更新θξ 17. end for 18. 根據(jù)式(18)、式(19)更新eh和er 19. end for 20. end for 21. end for 22. return Ev

3.6 復(fù)雜度分析

首先，對于超圖構(gòu)建2-截圖+關(guān)聯(lián)圖的過程，其時(shí)間復(fù)雜度為O(|E|·|e|2)。然后，對于感知節(jié)點(diǎn)語義相關(guān)性的元路徑游走過程，其時(shí)間復(fù)雜度為O(N·|V1|)。最后，基于拓?fù)渑缮繕?biāo)函數(shù)的模型和基于平移約束目標(biāo)函數(shù)的模型共同捕獲了節(jié)點(diǎn)之間的成對關(guān)系和元組關(guān)系過程，所需時(shí)間復(fù)雜度為O(C·(context·(Neg+1)+Rv·Hr·(NEG+1))·2d·(|V|+|E|))，其中，Neg和NEG分別表示基于拓?fù)渑缮繕?biāo)函數(shù)的模型和基于平移約束目標(biāo)函數(shù)的模型的負(fù)采樣樣本大小。因此，HRTC方法的時(shí)間復(fù)雜度為O(|E|·|e|2+N·|V1|+C·(context·(Neg+1)+Rv·Hr·(NEG+1))·2d·(|V|+|E|))。

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

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

為了全面評估HRTC方法的效果，本節(jié)使用三個(gè)不同類型的無向超網(wǎng)絡(luò)數(shù)據(jù)集，即一個(gè)藥物網(wǎng)絡(luò)、一個(gè)GPS網(wǎng)絡(luò)、一個(gè)社會(huì)網(wǎng)絡(luò)。數(shù)據(jù)集的詳細(xì)統(tǒng)計(jì)如表1所示。

表1 數(shù)據(jù)集統(tǒng)計(jì)

●drug(1)http://www.fda.gov/Drugs/： 該數(shù)據(jù)集來自FDA不良事件報(bào)告系統(tǒng)(FAERS)。它包括提交給FDA的不良事件和用藥錯(cuò)誤報(bào)告的信息。元組關(guān)系(用戶，藥物，反應(yīng))被看作超邊來構(gòu)建超網(wǎng)絡(luò)。

●GPS[14]： 該數(shù)據(jù)集描述了一個(gè)用戶在某個(gè)位置參加活動(dòng)。元組關(guān)系(用戶，位置，活動(dòng))被看作超邊來構(gòu)建超網(wǎng)絡(luò)。

●MovieLens[15]： 該數(shù)據(jù)集描述了來自于MovieLens 的個(gè)人標(biāo)記活動(dòng)。元組關(guān)系(用戶，電影，標(biāo)簽)被看作超邊來構(gòu)建超網(wǎng)絡(luò)。

4.2 基線方法

deepwalk[16]算法在隨機(jī)游走節(jié)點(diǎn)序列上訓(xùn)練Skip-gram模型來獲得節(jié)點(diǎn)表示向量。

node2vec[17]通過有偏隨機(jī)游走方式，保持了網(wǎng)絡(luò)中的高階相似性，來學(xué)習(xí)節(jié)點(diǎn)表示向量。

metapath2vec[18]通過基于元路徑的隨機(jī)游走來構(gòu)造節(jié)點(diǎn)的異質(zhì)鄰域，然后利用異質(zhì)Skip-gram模型學(xué)習(xí)節(jié)點(diǎn)表示向量。

Hyper2vec[7]通過超邊上有偏二階隨機(jī)游走來采樣節(jié)點(diǎn)之間的高階鄰居關(guān)系，然后訓(xùn)練Skip-gram模型獲得節(jié)點(diǎn)表示向量。

HPSG[8]通過基于超路徑的隨機(jī)游走來構(gòu)造節(jié)點(diǎn)的異質(zhì)鄰域，然后通過Skip-gram模型學(xué)習(xí)節(jié)點(diǎn)表示向量。

HPHG[8]通過基于超路徑的隨機(jī)游走來構(gòu)造節(jié)點(diǎn)的異質(zhì)鄰域，然后通過Hyper-gram模型學(xué)習(xí)節(jié)點(diǎn)表示向量。

Event2vec[19]將多個(gè)對象之間的關(guān)系建模為事件，定義了事件驅(qū)動(dòng)的一階和二階近似性，通過學(xué)習(xí)事件嵌入來學(xué)習(xí)對象嵌入。

HRTC通過平移機(jī)制將超邊融入超網(wǎng)絡(luò)表示學(xué)習(xí)過程中。

4.3 鏈接預(yù)測

鏈接預(yù)測在現(xiàn)實(shí)生活中得到了廣泛應(yīng)用，尤其是推薦系統(tǒng)。本節(jié)在drug、GPS和MovieLens三個(gè)超網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行鏈接預(yù)測實(shí)驗(yàn)。首先，使用二元算子[17]Weighted-L1和Weighted-L2計(jì)算節(jié)點(diǎn)成對相似性，然后，通過計(jì)算AUC[20]值來評估HRTC方法在2-截圖、關(guān)聯(lián)圖、2-截圖+關(guān)聯(lián)圖上的鏈接預(yù)測性能。

在鏈接預(yù)測試驗(yàn)中，采用80%邊集作為訓(xùn)練集，對于所有方法分別實(shí)驗(yàn)10次，取AUC平均值。以drug數(shù)據(jù)集為例，HRTC方法對于2-截圖、關(guān)聯(lián)圖，分別采用方案φ1、φ2進(jìn)行采樣，對于2-截圖+關(guān)聯(lián)圖采用SRwalk方案φ3進(jìn)行采樣。

從表2可知，deepwalk，node2vec，metapath2vec，HRTC分別在2-截圖，關(guān)聯(lián)圖，2-截圖+關(guān)聯(lián)圖進(jìn)行了鏈接預(yù)測實(shí)驗(yàn)，而Hyper2vec、HPSG、HPHG、Event2vec沒有分解超邊，直接在超圖上進(jìn)行鏈接預(yù)測實(shí)驗(yàn)。對于deepwalk，node2vec，metapath2vec，HRTC，2-截圖+關(guān)聯(lián)圖均實(shí)現(xiàn)了優(yōu)于2-截圖和關(guān)聯(lián)圖的鏈接預(yù)測效果。這表明，與2-截圖、關(guān)聯(lián)圖相比，2-截圖+關(guān)聯(lián)圖更好地保留了超網(wǎng)絡(luò)結(jié)構(gòu)信息。與普通網(wǎng)絡(luò)表示學(xué)習(xí)方法相比較，HRTC在3個(gè)數(shù)據(jù)集上均實(shí)現(xiàn)了最佳性能。與超網(wǎng)絡(luò)表示學(xué)習(xí)方法相比較，HRTC在drug和GPS數(shù)據(jù)集上展現(xiàn)出了優(yōu)于Hyper2vec和HPSG的鏈接預(yù)測能力。因?yàn)閷τ赿rug和GPS數(shù)據(jù)集，由于其超邊內(nèi)部節(jié)點(diǎn)之間不是兩兩語義相關(guān)的，所以特定地訓(xùn)練成對關(guān)系的模型Hyper2vec和HPSG沒有很好地學(xué)習(xí)節(jié)點(diǎn)之間的元組關(guān)系。HRTC在訓(xùn)練節(jié)點(diǎn)之間的成對關(guān)系時(shí)，同時(shí)訓(xùn)練節(jié)點(diǎn)之間的元組關(guān)系，能夠充分地學(xué)習(xí)節(jié)點(diǎn)之間的語義關(guān)系。對于MovieLens數(shù)據(jù)集，每部電影都有標(biāo)簽，比如喜劇、戰(zhàn)爭等。每個(gè)用戶都有特定的電影類型偏好。因此，用戶與電影、電影與標(biāo)簽、用戶與標(biāo)簽之間都存在語義相關(guān)性，特定地學(xué)習(xí)成對相似性的方法表現(xiàn)較好，如Hyper2vec和HPSG與HPHG、Event2vec相比較，HRTC在MovieLens數(shù)據(jù)集上實(shí)現(xiàn)了優(yōu)于HPHG和Event2vec的性能，在drug和GPS數(shù)據(jù)集上實(shí)現(xiàn)了與HPHG競爭性的效果。以上分析表明了HRTC可以很好地保留超網(wǎng)絡(luò)節(jié)點(diǎn)之間的語義關(guān)系，而且HRTC更加適用于超邊內(nèi)部節(jié)點(diǎn)之間具有語義相關(guān)性的超網(wǎng)絡(luò)。

4.4 超網(wǎng)絡(luò)重建

超網(wǎng)絡(luò)重建是評估節(jié)點(diǎn)表示向量質(zhì)量的典型方法。本節(jié)在drug和GPS數(shù)據(jù)集上評估了HRTC在不同重建比率下的性能。超網(wǎng)絡(luò)重建[7]的評估指標(biāo)定義如式(20)所示。

表2 鏈接預(yù)測結(jié)果 (單位： %)

續(xù)表

(20)

其中，對重建超邊的元組相似性按照升序排序，ni=1表示第i個(gè)重建超邊存在于原超網(wǎng)絡(luò)中，否則ni=0。|χ|為重建的總超邊數(shù)，ρ為超邊重建比率。

超網(wǎng)絡(luò)重建結(jié)果如圖8所示，在兩個(gè)數(shù)據(jù)集上，HRTC在2-截圖+關(guān)聯(lián)圖上的效果均好于2-截圖和關(guān)聯(lián)圖，表明了團(tuán)擴(kuò)展和星型擴(kuò)展結(jié)合的優(yōu)越性。此外，HRTC在兩個(gè)數(shù)據(jù)集上的重建效果顯著地優(yōu)于普通網(wǎng)絡(luò)表示學(xué)習(xí)方法。在兩個(gè)數(shù)據(jù)集上，其他超網(wǎng)絡(luò)表示學(xué)習(xí)方法在重建小比率超邊時(shí)表現(xiàn)不錯(cuò)，在增大重建比率時(shí)，其效果下降明顯，而HRTC在各個(gè)比率的超邊重建任務(wù)中都展現(xiàn)出了優(yōu)越的性能，而且HRTC在GPS數(shù)據(jù)集上顯著優(yōu)于其他基線方法。這表明HRTC通過捕獲節(jié)點(diǎn)之間的元組關(guān)系獲得了質(zhì)量較高的節(jié)點(diǎn)表示向量。

圖8 超網(wǎng)絡(luò)重建

4.5 參數(shù)敏感度分析

HRTC方法具有超參數(shù)β，它是一個(gè)平衡基于拓?fù)渑缮繕?biāo)函數(shù)的模型和基于平移約束目標(biāo)函數(shù)的模型的調(diào)和因子，選取最優(yōu)的β值可以獲得高質(zhì)量的節(jié)點(diǎn)表示向量。當(dāng)β=0時(shí)，HRTC只能捕獲節(jié)點(diǎn)之間的成對關(guān)系，當(dāng)0<β≤1時(shí)，HRTC可以同時(shí)捕獲節(jié)點(diǎn)之間的成對關(guān)系和元組關(guān)系。為了綜合考慮上述情況，設(shè)置0≤β≤1。ρ表示超邊重建比率，ρ=0.1表示重建10%的超邊，ρ=1表示重建全部的超邊。設(shè)置0.1≤ρ≤1，取各個(gè)超邊重建比率的平均值使得實(shí)驗(yàn)分析更具有普遍性。具體來說，通過在drug和GPS數(shù)據(jù)集上的鏈接預(yù)測和超網(wǎng)絡(luò)重建任務(wù)分析參數(shù)β的影響。其中，ACC(L)為鏈接預(yù)測Weighted-L1和Weighted-L2的平均值，ACC(ρ)為超網(wǎng)絡(luò)重建值的平均值。

由圖9可知，對于drug和GPS數(shù)據(jù)集，當(dāng)β=0時(shí)，HRTC方法僅捕獲了節(jié)點(diǎn)之間的成對關(guān)系，沒有考慮節(jié)點(diǎn)之間的元組關(guān)系；當(dāng)0<β≤0.6和0<β≤0.8時(shí)，鏈接預(yù)測和超網(wǎng)絡(luò)重建性能隨著β的增大而增大，并且分別在β=0.6和β=0.8時(shí)達(dá)到最大，說明元組關(guān)系的重要性在增強(qiáng)，成對關(guān)系的重要性在降低；當(dāng)0.6<β≤1和0.8<β≤1時(shí)，鏈接預(yù)測和超網(wǎng)絡(luò)重建性能隨著β增大而減小，說明元組關(guān)系的重要性在降低，成對關(guān)系的重要性在增強(qiáng)。出現(xiàn)上述結(jié)果的原因是節(jié)點(diǎn)表示向量的質(zhì)量取決于成對關(guān)系和元組關(guān)系之間的平衡優(yōu)化，即，通過隨機(jī)梯度上升算法使得式(9)聯(lián)合優(yōu)化目標(biāo)函數(shù)達(dá)到最優(yōu)解。總之，節(jié)點(diǎn)之間的成對關(guān)系和元組關(guān)系對于超網(wǎng)絡(luò)表示學(xué)習(xí)都很重要。

圖9 參數(shù)敏感度分析

5 結(jié)束語

為了進(jìn)行超網(wǎng)絡(luò)表示學(xué)習(xí)研究，本文首先提出一種結(jié)合團(tuán)擴(kuò)展和星型擴(kuò)展的方法將超網(wǎng)絡(luò)轉(zhuǎn)換為異質(zhì)網(wǎng)絡(luò)，其次，提出感知節(jié)點(diǎn)語義相關(guān)性的元路徑游走方法來保留節(jié)點(diǎn)之間的成對關(guān)系和元組關(guān)系。再次，通過引入平移機(jī)制，提出基于平移約束的異質(zhì)超網(wǎng)絡(luò)表示學(xué)習(xí)方法來捕獲節(jié)點(diǎn)之間的成對關(guān)系和元組關(guān)系，最后，在三個(gè)不同類型的超網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了評估實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，HRTC方法可以很好地發(fā)現(xiàn)那些未知鏈接，并以較好的效果重建超網(wǎng)絡(luò)。盡管該方法通過超圖到圖的轉(zhuǎn)換策略開展了超網(wǎng)絡(luò)表示學(xué)習(xí)研究，并嘗試在表示學(xué)習(xí)過程中融入超邊信息，但是仍然會(huì)丟失一部分超網(wǎng)絡(luò)結(jié)構(gòu)信息。因此，將來的研究可以從兩個(gè)方面展開，一是繼續(xù)嘗試在網(wǎng)絡(luò)表示學(xué)習(xí)方法中融入超邊信息；二是不再將超網(wǎng)絡(luò)轉(zhuǎn)化為普通網(wǎng)絡(luò)，即不再分解超邊，而是將超邊看成一個(gè)整體，進(jìn)行超網(wǎng)絡(luò)表示學(xué)習(xí)研究。