艾春玲，何 敏，呂 亮，楊青青

(云南大學(xué) 信息學(xué)院，云南 昆明 650500)

網(wǎng)絡(luò)可以很好地描述社會、生物和信息系統(tǒng)[1]，例如：社交關(guān)系網(wǎng)絡(luò)、交通物流網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和蛋白質(zhì)相互作用網(wǎng)絡(luò)等[2-5].其中不同的個體或不同的事物被表示成圖中的節(jié)點，個體間的關(guān)系、事物間的聯(lián)系被表示成圖中節(jié)點間的連邊，這就是常見的節(jié)點圖(Graph，G)[6].若將關(guān)系或聯(lián)系表示成圖中的節(jié)點，則獲得的圖相對復(fù)雜，被稱為連邊圖(Line Graph，LG)[7].

圖嵌入（Graph Embedding，GE）能方便、高效地提取圖的特征信息，并將學(xué)習(xí)到的特征嵌入到低維的向量空間，對圖數(shù)據(jù)的研究具有重要意義.矩陣分解(Matrix Factorization，MF)通過對不同的連接矩陣進行分解達(dá)到降維的目的，實現(xiàn)節(jié)點向量的嵌入，推動了圖嵌入技術(shù)的發(fā)展.如譜聚類(Spectral Clustering)[8]通過對拉普拉斯矩陣的分解得到節(jié)點的嵌入向量；GraRep[9]模型采用奇異值分解（Singular Value Decomposition，SVD）K-步轉(zhuǎn)移矩陣，得到節(jié)點的向量表示等.但基于矩陣分解的方法受鄰接矩陣邊的約束，在保持圖的二階和高階相似性方面存在不足[10].受Word2Vec詞嵌入模型的啟發(fā)，DeepWalk[11]首次將深度學(xué)習(xí)應(yīng)用于圖嵌入領(lǐng)域，在一定程度上提升了節(jié)點向量潛在表示的效果.但Word2Vec中的Skip-gram模型[12]沒有充分考慮被采樣的下一個節(jié)點對采樣過程的影響，游走生成的節(jié)點序列質(zhì)量不佳，導(dǎo)致得到的節(jié)點向量表示性不強.

現(xiàn)有圖嵌入方法及其下游任務(wù)，如鏈路預(yù)測(Link Prediction，LP)默認(rèn)采用節(jié)點圖，SVD的方法對鄰接矩陣進行處理，生成節(jié)點嵌入，圖神經(jīng)網(wǎng)絡(luò)（Graph Neural Network，GNN）[13]利用節(jié)點間的消息傳遞捕捉某種依賴關(guān)系，使生成的嵌入可以保留任意深度的領(lǐng)域信息[14].相對于節(jié)點圖，連邊圖包含的信息更豐富.近年來，部分學(xué)者開始關(guān)注用連邊圖表示網(wǎng)絡(luò)及節(jié)點間的關(guān)系，如線圖神經(jīng)網(wǎng)絡(luò)模型[15]、ONNEE模型[16]通過使用邊到節(jié)點的方向來學(xué)習(xí)更好的節(jié)點表示.

針對基于Skip-gram模型的圖嵌入方法沒有充分考慮被采樣的下一個節(jié)點對采樣過程的影響、不能直接獲得邊向量這兩個問題，本文對網(wǎng)絡(luò)圖的表示和構(gòu)成進行了研究，設(shè)計了一種以連邊圖為研究對象的圖嵌入算法Line2Vec，并在此基礎(chǔ)上提出邊嵌入鏈路預(yù)測框架Line2Vec-L.首先，采用無偏和有偏的思想，設(shè)計了一種可以處理連邊圖的圖嵌入算法Line2Vec，該算法在采用隨機游走生成節(jié)點序列時，考慮了當(dāng)前節(jié)點和鄰居節(jié)點對游走概率的影響，充分調(diào)動了被采樣的下一個節(jié)點在采樣過程中的主動性，提高了節(jié)點序列的生成質(zhì)量；然后結(jié)合關(guān)聯(lián)矩陣，將獲得的邊向量用于鏈路預(yù)測.實驗結(jié)果表明，本文提出的方法提升了鏈路預(yù)測的性能.

1 邊嵌入鏈路預(yù)測框架

1.1 邊嵌入鏈路預(yù)測框架（Line2Vec-L）描述Line2Vec-L主要分為兩個部分.首先，通過有偏+無偏的圖嵌入算法Line2Vec生成邊向量；然后，結(jié)合關(guān)聯(lián)矩陣得到不存在邊或未知邊的向量表示，將獲得的邊向量用于鏈路預(yù)測，預(yù)測框架如圖1所示.在Line2Vec-L框架中，首先將節(jié)點圖轉(zhuǎn)換為連邊圖，得到表示節(jié)點與連邊關(guān)系的關(guān)聯(lián)矩陣，采用無偏+有偏的靈活隨機游走采樣策略設(shè)計了一種改進的可以處理連邊圖的圖嵌入算法Line2Vec，通過連邊圖和Line2Vec算法可獲得存在邊的向量表示，結(jié)合關(guān)聯(lián)矩陣進而得到其它未知邊的向量表示，最后將獲得的邊向量用于鏈路預(yù)測.

連邊圖由節(jié)點圖轉(zhuǎn)換而來，連邊圖的節(jié)點是節(jié)點圖的邊，若節(jié)點圖中兩條邊有一個公共節(jié)點，則連邊圖中，這兩個節(jié)點之間有邊.

圖1 邊嵌入鏈路預(yù)測框架（Line2Vec-L）Fig.1 Link prediction algorithm using edge embedding（Line2Vec-L）

圖2 節(jié)點圖、連邊圖與邊向量之間的關(guān)系Fig.2 The relationship among node graph, link graph and edge embedding

關(guān)聯(lián)矩陣表征連邊圖中節(jié)點與節(jié)點間的關(guān)系，用B∈RN×Y表示，其中元素Bij定義為：

式中：vi為 節(jié)點圖的節(jié)點，ej為連邊圖的節(jié)點.可見，關(guān)聯(lián)矩陣實際上代表了節(jié)點與邊的關(guān)系.

1.2 圖嵌入算法Line2Vec與邊向量的生成生成邊向量有兩種方法，一是將節(jié)點圖嵌入為節(jié)點向量，然后利用邊函數(shù)得到邊嵌入向量；二是本文采用的直接將節(jié)點圖轉(zhuǎn)換為連邊圖，然后將連邊圖輸入本文提出的改進算法Line2Vec中得到邊嵌入向量.節(jié)點圖、連邊圖與邊嵌入向量3者之間具體的轉(zhuǎn)換關(guān)系如圖2所示.

為了通過圖嵌入直接獲得更具表示性的邊嵌入向量，本文在無偏采樣算法MHRW(Metropolis-Hasting Random Walk)的基礎(chǔ)上，設(shè)計了一種無偏+有偏的隨機游走采樣策略，即將當(dāng)前節(jié)點的自環(huán)率按鄰居節(jié)點的度值加權(quán)分配給鄰居節(jié)點[17]，得到新的采樣鄰居節(jié)點的轉(zhuǎn)移概率mij為：

式中：mij表示從節(jié)點vi到 其鄰居節(jié)點集合Γ(i)（包括自身節(jié)點）中選取節(jié)點vj進行采樣的轉(zhuǎn)移概率，ki、kj分 別為節(jié)點vi、vj的 度值，rii表示繼續(xù)采樣當(dāng)前節(jié)點時的轉(zhuǎn)移概念，由式(3)中當(dāng)vi=vj時計算所得.在式(2)的轉(zhuǎn)移概率中，前一部分為無偏采樣，保證了游走采樣的完整性，后一部分為有偏采樣，可消除自環(huán)率的不利影響.

Line2Vec主要由兩個部分組成：一是無偏+有偏的采樣節(jié)點生成器，二是基于深度學(xué)習(xí)的嵌入過程.首先，從圖G中隨機采樣一個節(jié)點作為節(jié)點序列Wwalk的根節(jié)點；然后，找出節(jié)點序列中最后一個節(jié)點的鄰居節(jié)點集合，利用式(2)計算出最后一個節(jié)點與所有鄰居間的轉(zhuǎn)移概率mij；最后，根據(jù)轉(zhuǎn)移概率來選取某下一個要采樣的鄰居節(jié)點，以此采樣直至節(jié)點序列達(dá)到最大長度l，同一個根節(jié)點采樣ζ次.嵌入過程主要利用深度學(xué)習(xí)框架SkipGram，該過程將生成器中生成的Nζ個長度為l的“句子”，送入SkipGram進行訓(xùn)練，最終得到節(jié)點的向量表示.

1.3 基于邊嵌入的鏈路預(yù)測算法

輸入圖數(shù)據(jù)G(VN，EY)，嵌入維度η，窗口大小?，游走長度l，每個節(jié)點的游走次數(shù)ζ.

輸出節(jié)點向量表示的矩陣Φ.

1 初始化：Wwalks∈? //walks表示存儲的節(jié)點序列，?為游走生成的節(jié)點序列，初始為空集.

2foreachvertexvi∈Vdo

3fori=1toζdo

4 使用公式(3)計算每個節(jié)點與它的鄰居節(jié)點間的轉(zhuǎn)移概率mij，其中，vi，vj∈Γ(i).

5Wwalk=Line2VecWalk表示根據(jù)概率選取的下一個鄰居節(jié)點.

6 將Wwalk添 加到Wwalks.

7Wwalks=Shuffle(Wwalks) //將Wwalks打亂.

8 Φ=SkipGram(Wwalks，η，?) //將Wwalks送入到 S kipGram中 得到節(jié)點的向量表示Φ.

9 將節(jié)點圖轉(zhuǎn)換為連邊圖，獲得關(guān)聯(lián)矩陣.

10 將存在邊關(guān)聯(lián)矩陣的逆與不存在或未知邊關(guān)聯(lián)矩陣相乘，得到不存在或未知邊與存在邊的關(guān)系，結(jié)合向量 Φ 得到未知邊向量Q.

11 將 Φ和Q按測試集比例為20%進行劃分，并使用線性回歸中的邏輯回歸作為判別分類器進行預(yù)測，輸出預(yù)測結(jié)果.

1.4 算法的評價指標(biāo)本文選擇AUC[18]指標(biāo)評價算法的準(zhǔn)確性.AUC是一種比較概率，設(shè)隨機比較n次 ，其中，有n′次評分高，每高一次加1分，有n′′次評分相等，每等一次加0.5分，則AUC值的定義為：

AUC 值 在 0～1之間，值越大的鏈路預(yù)測方法準(zhǔn)確性越高.

節(jié)點分類是圖嵌入中最常見的下游任務(wù)，常用于評價圖表示性能優(yōu)劣的指標(biāo)，節(jié)點分類的評價指標(biāo)主要有微平均分F1Micro和宏平均分F1Macro[19]，定義如下：

式中：b表 示節(jié)點的類別數(shù)，TP(True Positive)表示真陽性，TPi為在第i類中預(yù)測的正類數(shù)，F(xiàn)P(False Positive)表示假陽性，F(xiàn)Pi為在第i類中預(yù)測的假正類數(shù)，F(xiàn)N( False Negative)表示假陰性，F(xiàn)Ni為在第i類中預(yù)測的假負(fù)類數(shù).

2 實驗結(jié)果與分析

為了驗證預(yù)測框架的有效性，分別完成了兩組實驗：首先是圖嵌入算法的節(jié)點分類實驗，比較了Line2Vec與其他嵌入算法在5個數(shù)據(jù)集下的節(jié)點分類效果；其次是邊嵌入鏈路預(yù)測實驗，將Line2Vec-L方法在6個數(shù)據(jù)集上與4種邊函數(shù)構(gòu)造方法獲得的結(jié)果進行的鏈路預(yù)測效果對比.

2.1 實 驗 數(shù) 據(jù)實驗選取了6個不同規(guī)模且具代表性的真實數(shù)據(jù)集，均為無權(quán)無向圖.實驗數(shù)據(jù)集包括Jazz、NetScience、Power、Alpha（來源于https://github.com/benedekrozemberczki） 與E-mail[20]、PolBlogs[21].詳細(xì)信息如表1所示.Jazz、NetScience、E-mail為相對小規(guī)模網(wǎng)絡(luò)，Power、Alpha、PolBlogs為相對大規(guī)模網(wǎng)絡(luò).表中，N表示網(wǎng)絡(luò)的節(jié)點數(shù)，Y表示網(wǎng)絡(luò)的邊數(shù)，〈K〉 表 示網(wǎng)絡(luò)的平均度，〈C〉表示網(wǎng)絡(luò)的平均聚集系數(shù)，D表示網(wǎng)絡(luò)的相對直徑.

表1 實驗數(shù)據(jù)的網(wǎng)絡(luò)結(jié)構(gòu)特征Tab.1 Network structure features of datasets

2.2 實驗基準(zhǔn)方法與參數(shù)設(shè)置將Line2Vec與圖嵌入領(lǐng)域具有代表的幾類經(jīng)典方法進行比較，其中譜聚類（Spectral Clustering）、Diff2Vec[22]、BoostNE[23]方法是基于矩陣分解的圖嵌入方法，DeepWalk、Node2Vec[24]、Role2Vec[25]是基于Word2Vec模型的圖嵌入方法.為了保證實驗的公平性，所有方法的嵌入維度 η =128；DeepWalk、Node2Vec、Role2Vec、Diff2Vec、Line2Vec的游走次數(shù) ζ=10，游走長度l=80 ，窗口大小 ?=10，此外，BoostNE 的嵌入層數(shù)為8，每一層的嵌入維度 ηi=16，組合維度 η =128.

2.3 圖 嵌 入 算 法 的 實 驗 及 結(jié) 果采 用Word2Vec模型在多個真實網(wǎng)絡(luò)圖上進行節(jié)點分類的效果評估算法對圖的表示性能.實驗選取5種不同領(lǐng)域不同規(guī)模的真實數(shù)據(jù)集(http://networkrepository.com)，包括Twitch、Facebook、Wikipedia、Github、Blogcatalog，如表2所示，其中，N表示網(wǎng)絡(luò)的節(jié)點數(shù)，Y表示網(wǎng)絡(luò)的邊數(shù)，C表示網(wǎng)絡(luò)的連通數(shù)，〈L〉表示網(wǎng)絡(luò)的標(biāo)簽數(shù).實驗在每個數(shù)據(jù)集上獨立重復(fù)10次，取平均值.訓(xùn)練數(shù)據(jù)的劃分比例為10%，30%，50%，70%，90%，使用線性回歸中的邏輯回歸作為判別分類器.基準(zhǔn)方法和參數(shù)設(shè)置見2.2節(jié)，結(jié)果如表3～7所示.其中，Spectral Clustering、DeepWalk、Node2Vec、Role2Vec、Diff2Vec、BoostNE、Line-2Vec分別簡寫為SC、DW、N2V、R2V、D2V、BNE、L2V.

表2 數(shù)據(jù)集的結(jié)構(gòu)特征Tab.2 Structure features of datasets

表3～7中，最佳F1Micro和F1Macro值用粗體顯示.可以看出，隨著數(shù)據(jù)集訓(xùn)練比例的增加，所有方法的性能都隨之提升.在同一訓(xùn)練比例下，Line2Vec在所有數(shù)據(jù)集上都比DeepWalk算法性能更佳；與Node2Vec算法相比，絕大多數(shù)情況下Line2Vec的評價指標(biāo)更高，尤其當(dāng)訓(xùn)練比例僅為10%時，Line2Vec在所有數(shù)據(jù)集上都獲得了比Node2Vec 更好的性能.與帶有屬性化隨機游走的Role2Vec 算法相比，Line2Vec在所有數(shù)據(jù)集上的評價指數(shù)更高，這意味著綜合考慮當(dāng)前節(jié)點和鄰居節(jié)點共同決定的游走方式比屬性化隨機游走方式的表現(xiàn)力更強，與 Diff2Vec 算法相比，Line2Vec也有相同的優(yōu)勢，在絕大部分情況下，Line2Vec相較于其它6種基準(zhǔn)方法，其F1Micro和F1Macro值都更高，說明采用Line2Vec方法表示的節(jié)點向量更有效.

表3 Twitch數(shù)據(jù)集上的節(jié)點分類性能比較Tab.3 The comparison of node classification performance on Twitch datasets

表4 Facebook數(shù)據(jù)集上的節(jié)點分類性能比較Tab.4 The comparison of node classification performance on Facebook datasets

表5 Wikipedia數(shù)據(jù)集上的節(jié)點分類性能比較Tab.5 The comparison of node classification performance on Wikipedia datasets

表6 Github數(shù)據(jù)集上的節(jié)點分類性能比較Tab.6 The comparison of node classification performance on Github datasets

表7 Blogcatalog數(shù)據(jù)集上的節(jié)點分類性能比較Tab.7 The comparison of node classification performance on Blogcatalog datasets

與將節(jié)點圖作為輸入的圖嵌入算法不同，Line2Vec算法能處理連邊圖，由此，可先將節(jié)點圖轉(zhuǎn)換為連邊圖，在轉(zhuǎn)換過程中同時也得到了相應(yīng)的關(guān)聯(lián)矩陣，因此增加了空間復(fù)雜度.傳統(tǒng)譜聚類算法基于數(shù)據(jù)樣本計算矩陣并進行規(guī)范化，其時間復(fù)雜度為O(N3)，具有代表性的DeepWalk的時間復(fù)雜度為Ο(N2)，Line2Vec的時間復(fù)雜度也為Ο(N2)，但由于要存儲邊向量，增加了一倍的空間復(fù)雜度.

2.4 鏈路預(yù)測算法的結(jié)果與分析表8比較了不同算法在缺失部分邊緣時的鏈路預(yù)測性能.其中，Average、Hadamard、Weighted-L1、Weighted-L2為Node2Vec提出的4種邊函數(shù)[24]，可對生成的節(jié)點向量進行數(shù)學(xué)運算構(gòu)造出邊向量.Line2Vec-L則采用基于Line2Vec的邊嵌入算法進行鏈路預(yù)測.Line2Vec既能處理節(jié)點圖，也能處理連邊圖，若將連邊圖作為輸入，則不再需要邊函數(shù)來構(gòu)造邊向量.

在表8中，最佳AUC值用粗體顯示，對于通過邊函數(shù)間接構(gòu)造得到邊向量的圖嵌入算法，表現(xiàn)最好的用下劃線顯示.從表8中可以看出，Line2Vec在5種數(shù)據(jù)集上AUC值最高；在3個大規(guī)模的數(shù)據(jù)集上，Line2Vec-L獲得了最佳的預(yù)測性能;此外，采用節(jié)點向量作為輸入獲得邊向量的圖嵌入算法Line2Vec，在4個數(shù)據(jù)集上也獲得了最佳性能，這說明基于無偏+有偏的綜合游走策略的圖嵌入算法Line2Vec獲得的節(jié)點表示效果更好; 同時，在大規(guī)模數(shù)據(jù)集上，采用連邊圖作為輸入與采用節(jié)點向量作為輸入的方法相比，更有助于性能的提升.

3 結(jié)束語

本文針對網(wǎng)絡(luò)圖的表示和構(gòu)成進行了研究，設(shè)計了一種以連邊圖為研究對象的邊嵌入算法Line2Vec，并在此基礎(chǔ)上提出了基于Line2Vec的邊嵌入鏈路預(yù)測框架Line2Vec-L.首先，基于有偏和無偏思想，設(shè)計了一種可以處理連邊圖的圖嵌入算法Line2Vec，該算法在采用隨機游走采樣策略生成節(jié)點序列時，充分調(diào)動了被采樣的下一個節(jié)點在采樣過程中的主動性；然后，結(jié)合關(guān)聯(lián)矩陣，將生成的邊向量用于鏈路預(yù)測.實驗結(jié)果表明，采用Line2Vec方法得到的節(jié)點向量表示性更強，提升了鏈路預(yù)測的性能.下一步，可以綜合考慮節(jié)點圖和連邊圖，研究雙層圖或多層圖嵌入算法的鏈路預(yù)測.

表8 網(wǎng)絡(luò)數(shù)據(jù)集中 4 種邊函數(shù)與不同基準(zhǔn)方法結(jié)合的鏈路預(yù)測 AUC 值比較Tab.8 The AUC value of network datasets under four edge-functions to different benchmark methods