北方工業(yè)大學(xué) 劉海煜 史巖 劉林涵

復(fù)雜基因組網(wǎng)絡(luò)往往具有大量的節(jié)點(diǎn)和邊，學(xué)習(xí)其節(jié)點(diǎn)特征并應(yīng)用于一些下游任務(wù)如鏈路預(yù)測往往不那么容易。因此，對比找到一種合適的嵌入算法以提高對復(fù)雜基因組網(wǎng)絡(luò)的嵌入效率同時更好的應(yīng)用于一些下游任務(wù)成為了一個非常有意義的問題。本文采用三種常用的嵌入算法（DeepWalk，Line，Node2vec）對復(fù)雜基因組網(wǎng)絡(luò)進(jìn)行嵌入學(xué)習(xí)得到節(jié)點(diǎn)的低維向量表示，然后將其應(yīng)用于鏈路預(yù)測任務(wù)。同時重新定義了評估指標(biāo)Micro-F1的各項(xiàng)參數(shù)，經(jīng)過實(shí)驗(yàn)后發(fā)現(xiàn)DeepWalk對于復(fù)雜基因組網(wǎng)絡(luò)的鏈路預(yù)測更為適用。

任何復(fù)雜的系統(tǒng)都以網(wǎng)絡(luò)的形式出現(xiàn)。而網(wǎng)絡(luò)數(shù)據(jù)往往是復(fù)雜的，處理起來具有挑戰(zhàn)性。為了有效地處理網(wǎng)絡(luò)數(shù)據(jù)，關(guān)鍵是尋找有效的網(wǎng)絡(luò)數(shù)據(jù)表示[1]。人們致力于開發(fā)新型網(wǎng)絡(luò)嵌入[2]。文獻(xiàn)[3]提出了DeepWalk算法。文獻(xiàn)[4]提出的LINE算法。文獻(xiàn)[5]提出的Node2vec算法。

鏈路預(yù)測是網(wǎng)絡(luò)分析中一個重要的應(yīng)用。鏈路預(yù)測主要是基于已知的網(wǎng)絡(luò)預(yù)測網(wǎng)絡(luò)中隱藏的鏈路或未來即將產(chǎn)生的鏈路?；诠餐従酉嗨菩灾笜?biāo)主要有余弦相似性[6]、Adamic指標(biāo)[7]等。隨著深度學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)在文本處理、圖像理解等領(lǐng)域的成功應(yīng)用，將神經(jīng)網(wǎng)絡(luò)應(yīng)用于鏈路預(yù)測成為目前研究的重點(diǎn)。

然而在以往的研究中對復(fù)雜基因組網(wǎng)絡(luò)的嵌入和鏈路預(yù)測任務(wù)還研究甚少。

復(fù)雜疾病是指由眾多因素共同作用下發(fā)生的疾病，主要包含高血壓、糖尿病等疾病。當(dāng)前對于復(fù)雜疾病的研究主要采用大規(guī)?；蚪M關(guān)聯(lián)分析。但該方法存在沒有充分考慮基因交互、運(yùn)行效率低等問題。為此本文通過三種嵌入算法對復(fù)雜基因組網(wǎng)絡(luò)進(jìn)行嵌入得到低維向量表示并進(jìn)行鏈路預(yù)測。主要貢獻(xiàn)如下：

(1)第一次完成復(fù)雜基因組網(wǎng)絡(luò)的鏈路預(yù)測任務(wù)。

(2)重新定義了Micro-F1參數(shù)使得其能更好的評估邊級預(yù)測性能。

(3)對比了三種算法在復(fù)雜基因組網(wǎng)絡(luò)上的鏈路預(yù)測性能，得出DeepWalk在復(fù)雜基因組網(wǎng)絡(luò)可以取得更優(yōu)預(yù)測性能的結(jié)論，同時發(fā)現(xiàn)Line模型更適用于大規(guī)模圖。

1 模型介紹及相關(guān)定義

對于復(fù)雜基因組網(wǎng)絡(luò)G={V,E}，其中，V為SNPS節(jié)點(diǎn)集，且V={v1,v2,…,v|v|}，|V|為節(jié)點(diǎn)總數(shù)；E為網(wǎng)絡(luò)中鏈接集，且ei,j∈E表示SNPS節(jié)點(diǎn)vi和SNPS節(jié)點(diǎn)vj之間存在鏈接關(guān)系。

1.1 DeepWalk模型

DeepWalk主要包括兩個部分：隨機(jī)游走生成器和更新過程。首先DeepWalk采用Random Walk在網(wǎng)絡(luò)中進(jìn)行截斷的隨機(jī)行走，生成一組行走序列。算法定義以頂點(diǎn)vi為根的隨機(jī)游走為Wvi。隨機(jī)游走生成器就是一個由隨機(jī)變量Wvi1,Wvi2,…,Wvik組成的一個隨機(jī)過程。對于每個行走序列，采用Skip-Gram模型，DeepWalk的目標(biāo)是在該行走序列中最大化節(jié)點(diǎn)vi的條件概率，如下：

其中w是窗口大小，(vi)代表著vi當(dāng)前位置，{vi-w,…,vi+w}vi是vi的上下文節(jié)點(diǎn)。

對于序列中的每個頂點(diǎn)，計算條件概率，并借助梯度下降算法更新結(jié)點(diǎn)的向量表示。

1.2 Node2vec模型

Node2vec定義了靈活的節(jié)點(diǎn)網(wǎng)絡(luò)鄰居的概念，并設(shè)計了一種對領(lǐng)域節(jié)點(diǎn)進(jìn)行采樣的二階隨機(jī)遍歷策略。Node2vec定義了倆個參數(shù)p和q來實(shí)現(xiàn)有偏向的隨機(jī)游走?？紤]一個隨機(jī)游走剛經(jīng)過邊(t,v)，并正處于頂點(diǎn)v。隨機(jī)游走需要決定下一步，所以需要計算從頂點(diǎn)v經(jīng)過邊(v,x)的轉(zhuǎn)移概率πvx。定義轉(zhuǎn)移概πvx=αpq(t,x)·ωvx。

Node2vec能夠密切學(xué)習(xí)具有相同網(wǎng)絡(luò)鄰居的節(jié)點(diǎn)形式。同時一些實(shí)驗(yàn)[5]也證明Node2vec算法是一種高度穩(wěn)定的學(xué)習(xí)特征的算法，可以在不同類型的網(wǎng)絡(luò)都提供最佳性能。

1.3 Line模型

Line主要用于大規(guī)模圖嵌入，它能夠保持一階和二階相似性。

一階相似性對于每個邊(i,j)，定義節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的聯(lián)合分布概率為：

其中ui∈Rd是頂點(diǎn)vi的低維向量表示。(一階相似性只適用于無向圖)二階相似性對無向圖和有向圖都是適用的，對于一個邊(i,j)定義它的轉(zhuǎn)移概率如下：

其中|V|是節(jié)點(diǎn)數(shù)量。對于每一個頂點(diǎn)vi，上式定義了一個在整個網(wǎng)絡(luò)頂點(diǎn)集上的條件分布P2(·|vi)。Line模型可以很容易地擴(kuò)展到具有數(shù)百萬個頂點(diǎn)和數(shù)十億條邊的網(wǎng)絡(luò)[4]。

2 鏈路預(yù)測(Link Prediction)實(shí)現(xiàn)

網(wǎng)絡(luò)中的鏈路預(yù)測是指如何通過已知的網(wǎng)絡(luò)節(jié)點(diǎn)以及網(wǎng)絡(luò)結(jié)構(gòu)等信息預(yù)測網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個節(jié)點(diǎn)之間產(chǎn)生鏈接的可能性?；贓mbedding的鏈路預(yù)測是通過嵌入算法學(xué)習(xí)后得到的節(jié)點(diǎn)低維向量表示來估計節(jié)點(diǎn)間的相似性度量。以此來預(yù)測節(jié)點(diǎn)之間是否可能存在聯(lián)系。

具體做法是對得到的Embedding向量表示進(jìn)行處理，用兩個節(jié)點(diǎn)的歐式距離大小來評估兩個節(jié)點(diǎn)之間的聯(lián)系程度。

對于兩個節(jié)點(diǎn)vi和vj的n維向量表示X和Y，vi和vj的歐式距離d為：

為了更好的進(jìn)行鏈接預(yù)測，采用K-NN的思想保留歐式距離TOPK的邊。

2.1 K-NN算法

設(shè)對象x={x1,…,xn}，xi(1≤i≤n)是它的特征值。x是n維特征空間D=(D1,…,Dn)上的一點(diǎn)，x,y∈D，則x，y在特征空間F上的距離為dF(x,y)。

K-NN算法定義了一個下界d'和上界d''，設(shè)特征子空間，F(xiàn)1=(D1,…,Dk),k≤n，則圍繞x計算dD(x,y)的過程中：

(1)如果dF1(x,y)≤d'，進(jìn)一步計算dD(x,y)是不必要的，因?yàn)楸赜衐D(x,y)≤d'，一定不會滿足條件。

(2)如果dF1≥d''，進(jìn)一步計算dD(x,y)是不必要的，因?yàn)楸赜衐D(x,y)≥d''，一定不滿足條件。

這樣基于K-NN算法可以減少大量無用的計算，提高預(yù)測效率。

2.2 基于K-NN算法的歐氏距離TOPK計算

采用K-NN算法的思想設(shè)置閾值dmin和dmax，維護(hù)一個TOPK的隊列保存歐式距離最大的前k個節(jié)點(diǎn)對，同時隊列內(nèi)的每一對節(jié)點(diǎn)(vi0,vi1)滿足：

其中dmin和dmax計算方法如下：

從測試集中每次隨機(jī)抽取10%的數(shù)據(jù)，計算出歐式距離最小值和最大值分別為dmini和dmaxi，總共取n次，則：

2.3 鏈路預(yù)測評估方法

Micro-F1分?jǐn)?shù)可以很好的表示節(jié)點(diǎn)分類性能的好壞，基于節(jié)點(diǎn)分類的參數(shù)設(shè)定，定義用于評估鏈路預(yù)測的Micro-F1參數(shù)如下：

TP：預(yù)測的邊在測試集中

TR：預(yù)測的邊可能存在

FP：預(yù)測的邊不可能存在

FN：預(yù)測的邊在訓(xùn)練集中

則精準(zhǔn)率Precision:

召回率Recall:

這三個指標(biāo)可以很好的反應(yīng)鏈接預(yù)測的好壞。

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

實(shí)驗(yàn)選用HT(x2＞30)，HT(x2＞35)和HT(x2＞40)三個高血壓疾病交互網(wǎng)絡(luò)數(shù)據(jù)集，數(shù)據(jù)集的具體參數(shù)如表1所示。

對比DeepWalk，Line和Node2vec三個模型在復(fù)雜基因組網(wǎng)絡(luò)中鏈接預(yù)測性能。實(shí)驗(yàn)過程中取數(shù)據(jù)集70%的點(diǎn)作為訓(xùn)練集，30%的點(diǎn)作為測試集，采用精準(zhǔn)率P，召回率R和Micro-F1三個指標(biāo)。在不同數(shù)據(jù)集下，三種模型對比數(shù)據(jù)如表2所示。

實(shí)驗(yàn)表明，DeepWalk在不同數(shù)據(jù)集下都取得了最好的召回率和Micro-F1分?jǐn)?shù),在HT(x2＞40)中準(zhǔn)確率取得最優(yōu)。Line在三個數(shù)據(jù)集上都取得了良好的準(zhǔn)確率表現(xiàn)，但召回率普遍較低，且各項(xiàng)評估指標(biāo)在數(shù)據(jù)集規(guī)模較大時能夠取得更好的效果。Node2vec模型在三個數(shù)據(jù)集中表現(xiàn)介于兩者之間，且在數(shù)據(jù)規(guī)模較小時，與DeepWalk性能差距較大，隨著數(shù)據(jù)集變大與DeepWalk性能差距逐漸減小。

在不同數(shù)據(jù)集下，DeepWalk均取得了最優(yōu)的效果，而Line在數(shù)據(jù)量較大的數(shù)據(jù)集中準(zhǔn)確率取得了較好的成績，Node2vec總體表現(xiàn)優(yōu)于Line，在大規(guī)模數(shù)據(jù)集中接近與DeepWalk。由于DeepWalk采用隨機(jī)游走的方法學(xué)習(xí)節(jié)點(diǎn)的特征表示，可以在圖規(guī)模較大的時候有效減少計算量。綜上所述，DeepWalk在復(fù)雜基因組網(wǎng)絡(luò)取得了更優(yōu)的預(yù)測效果，Line模型適用于較大規(guī)模圖的預(yù)測。

表 1 數(shù)據(jù)集參數(shù)Tab.1 Parameters of dataset

表 2 不同數(shù)據(jù)集下對應(yīng)準(zhǔn)確率，召回率和Micro-F1值Tab.2 Corresponding accuracy, recall and Micro-F1 values under different datasets

4 結(jié)語

本文旨在針對三種嵌入算法對復(fù)雜基因組網(wǎng)絡(luò)預(yù)測性能的對比，以找出適合大規(guī)模基因組網(wǎng)絡(luò)的嵌入算法。我們在三個不同高血壓疾病交互網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)，得出DeepWalk在復(fù)雜基因組網(wǎng)絡(luò)上取得更優(yōu)效果的結(jié)論。

引用

[1] CUI P,WANG X,PEI J,et al.A Survey on Network Embedding[J].IEEE Transactions on Knowledge and Data Engineering,2018,31(5):833-852.

[2] ESTRIN D,GOVINDAN R,HEIDEMANN J.Embedding the Internet:Introduction[J].Communications of the ACM,2000,43(5):38-41.

[3] PEROZZI B,Al-Rfou R,SKIENA S.Deepwalk: Online Learning of Social Representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2014:701-710.

[4] TANG J,QU M,WANG M Z,et al.Line: Large-scale Information Network Embedding[C]//Proceedings of the 24th International Conference on World Wide Web,2015:1067-1077.

[5] GROVER A,LESKOVEC J.Node2Vec:Scalable Feature Learning for Networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2016:855-864.

[6] CHOWDHURY G G.Introduction to Modern Information Retrieval [M].UK:Facet Publishing,2010.

[7] ADAMIC L A,ADAR E.Friends and Neighbors on the Web[J].Social Networks,2003,25(3):211-230.