大規模復雜疾病基因組交互網絡嵌入算法*

北方工業大學 劉海煜 史巖 劉林涵

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

任何復雜的系統都以網絡的形式出現。而網絡數據往往是復雜的，處理起來具有挑戰性。為了有效地處理網絡數據，關鍵是尋找有效的網絡數據表示[1]。人們致力于開發新型網絡嵌入[2]。文獻[3]提出了DeepWalk算法。文獻[4]提出的LINE算法。文獻[5]提出的Node2vec算法。

鏈路預測是網絡分析中一個重要的應用。鏈路預測主要是基于已知的網絡預測網絡中隱藏的鏈路或未來即將產生的鏈路。基于共同鄰居相似性指標主要有余弦相似性[6]、Adamic指標[7]等。隨著深度學習、神經網絡在文本處理、圖像理解等領域的成功應用，將神經網絡應用于鏈路預測成為目前研究的重點。

然而在以往的研究中對復雜基因組網絡的嵌入和鏈路預測任務還研究甚少。

復雜疾病是指由眾多因素共同作用下發生的疾病，主要包含高血壓、糖尿病等疾病。當前對于復雜疾病的研究主要采用大規模基因組關聯分析。但該方法存在沒有充分考慮基因交互、運行效率低等問題。為此本文通過三種嵌入算法對復雜基因組網絡進行嵌入得到低維向量表示并進行鏈路預測。主要貢獻如下：

(1)第一次完成復雜基因組網絡的鏈路預測任務。

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

(3)對比了三種算法在復雜基因組網絡上的鏈路預測性能，得出DeepWalk在復雜基因組網絡可以取得更優預測性能的結論，同時發現Line模型更適用于大規模圖。

1 模型介紹及相關定義

對于復雜基因組網絡G={V,E}，其中，V為SNPS節點集，且V={v1,v2,…,v|v|}，|V|為節點總數；E為網絡中鏈接集，且ei,j∈E表示SNPS節點vi和SNPS節點vj之間存在鏈接關系。

1.1 DeepWalk模型

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

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

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

1.2 Node2vec模型

Node2vec定義了靈活的節點網絡鄰居的概念，并設計了一種對領域節點進行采樣的二階隨機遍歷策略。Node2vec定義了倆個參數p和q來實現有偏向的隨機游走。考慮一個隨機游走剛經過邊(t,v)，并正處于頂點v。隨機游走需要決定下一步，所以需要計算從頂點v經過邊(v,x)的轉移概率πvx。定義轉移概πvx=αpq(t,x)·ωvx。

Node2vec能夠密切學習具有相同網絡鄰居的節點形式。同時一些實驗[5]也證明Node2vec算法是一種高度穩定的學習特征的算法，可以在不同類型的網絡都提供最佳性能。

1.3 Line模型

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

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

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

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

2 鏈路預測(Link Prediction)實現

網絡中的鏈路預測是指如何通過已知的網絡節點以及網絡結構等信息預測網絡中尚未產生連邊的兩個節點之間產生鏈接的可能性。基于Embedding的鏈路預測是通過嵌入算法學習后得到的節點低維向量表示來估計節點間的相似性度量。以此來預測節點之間是否可能存在聯系。

具體做法是對得到的Embedding向量表示進行處理，用兩個節點的歐式距離大小來評估兩個節點之間的聯系程度。

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

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

2.1 K-NN算法

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

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

(1)如果dF1(x,y)≤d'，進一步計算dD(x,y)是不必要的，因為必有dD(x,y)≤d'，一定不會滿足條件。

(2)如果dF1≥d''，進一步計算dD(x,y)是不必要的，因為必有dD(x,y)≥d''，一定不滿足條件。

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

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

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

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

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

2.3 鏈路預測評估方法

Micro-F1分數可以很好的表示節點分類性能的好壞，基于節點分類的參數設定，定義用于評估鏈路預測的Micro-F1參數如下：

TP：預測的邊在測試集中

TR：預測的邊可能存在

FP：預測的邊不可能存在

FN：預測的邊在訓練集中

則精準率Precision:

召回率Recall:

這三個指標可以很好的反應鏈接預測的好壞。

3 實驗

實驗選用HT(x2＞30)，HT(x2＞35)和HT(x2＞40)三個高血壓疾病交互網絡數據集，數據集的具體參數如表1所示。

對比DeepWalk，Line和Node2vec三個模型在復雜基因組網絡中鏈接預測性能。實驗過程中取數據集70%的點作為訓練集，30%的點作為測試集，采用精準率P，召回率R和Micro-F1三個指標。在不同數據集下，三種模型對比數據如表2所示。

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

在不同數據集下，DeepWalk均取得了最優的效果，而Line在數據量較大的數據集中準確率取得了較好的成績，Node2vec總體表現優于Line，在大規模數據集中接近與DeepWalk。由于DeepWalk采用隨機游走的方法學習節點的特征表示，可以在圖規模較大的時候有效減少計算量。綜上所述，DeepWalk在復雜基因組網絡取得了更優的預測效果，Line模型適用于較大規模圖的預測。

表 1 數據集參數Tab.1 Parameters of dataset

表 2 不同數據集下對應準確率，召回率和Micro-F1值Tab.2 Corresponding accuracy, recall and Micro-F1 values under different datasets

4 結語

本文旨在針對三種嵌入算法對復雜基因組網絡預測性能的對比，以找出適合大規模基因組網絡的嵌入算法。我們在三個不同高血壓疾病交互網絡上進行實驗，得出DeepWalk在復雜基因組網絡上取得更優效果的結論。

引用

[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.