畢 陽，何嘉林,2，崔東旭，任衛(wèi)平

(1.西華師范大學(xué) 計(jì)算機(jī)學(xué)院，四川 南充 637002；2.物聯(lián)網(wǎng)感知與大數(shù)據(jù)分析南充市重點(diǎn)實(shí)驗(yàn)室，四川 南充 637002)

0 引言

在當(dāng)今現(xiàn)實(shí)世界中有很多網(wǎng)絡(luò)，例如銀行客戶網(wǎng)絡(luò)，微博社交網(wǎng)絡(luò)，生物蛋白質(zhì)結(jié)構(gòu)網(wǎng)絡(luò)，都可以用節(jié)點(diǎn)和邊組成的形式來研究.許多任務(wù)，例如多標(biāo)簽分類任務(wù)，多路鏈路預(yù)測任務(wù)，可以被很快速地表示并執(zhí)行[1].但是隨著形如微博社交網(wǎng)絡(luò)，銀行客戶網(wǎng)絡(luò)等網(wǎng)絡(luò)的快速擴(kuò)張，網(wǎng)絡(luò)數(shù)據(jù)體量越來越大，如何處理并且高效處理大規(guī)模的網(wǎng)絡(luò)成為了一個(gè)讓人頭疼的問題，如何將這些網(wǎng)絡(luò)表示是解決這一難題的關(guān)鍵.在傳統(tǒng)的方法當(dāng)中，將網(wǎng)絡(luò)用鄰接矩陣進(jìn)行表示，矩陣的每一行代表著網(wǎng)絡(luò)中的每個(gè)點(diǎn)在網(wǎng)絡(luò)中的特征向量，但是在大型網(wǎng)絡(luò)中，這種表示方法所得矩陣向量維度極高，使得一些復(fù)雜的網(wǎng)絡(luò)表示過程極其困難.針對(duì)此現(xiàn)象，近年來的網(wǎng)絡(luò)表示學(xué)習(xí)被廣泛應(yīng)用于網(wǎng)絡(luò)分析，通過頂點(diǎn)在網(wǎng)絡(luò)中所扮演的角色為網(wǎng)絡(luò)構(gòu)建一個(gè)低維向量，極大地減少了時(shí)間成本和運(yùn)算空間.本文提出一種方法，通過對(duì)矩陣的分解且不斷更新得到最早的網(wǎng)絡(luò)特征矩陣.與3種網(wǎng)絡(luò)表示學(xué)習(xí)方法Line[2]，node2vec[3],Deepwalk[4]相比，我們的方法在多標(biāo)簽分類和多路鏈路預(yù)測上有著更好的表現(xiàn).

1 基礎(chǔ)概念

1.1 網(wǎng)絡(luò)結(jié)構(gòu)圖

圖 1 無權(quán)網(wǎng)絡(luò)G

設(shè)G=(V,E)是一個(gè)無權(quán)網(wǎng)絡(luò)，如圖1所示.其中集合V是包含許多個(gè)頂點(diǎn)的頂點(diǎn)集，E則是邊集合.在圖1中集合V為(V1,V2,V3，…，V12),集合E為(E1,2，E1,3，E1,6，…，E12,7)傳統(tǒng)方法將網(wǎng)絡(luò)結(jié)構(gòu)用高維的圖鄰接矩陣表示，這種表示方法雖然捕捉到了網(wǎng)絡(luò)結(jié)構(gòu)，但是由于其極大的矩陣維度，導(dǎo)致計(jì)算成本和所用空間過大，無法應(yīng)用于大型網(wǎng)絡(luò).針對(duì)這個(gè)問題，網(wǎng)絡(luò)表示學(xué)習(xí)的方法學(xué)習(xí)對(duì)應(yīng)網(wǎng)絡(luò)的函數(shù)f:V→Rd，將網(wǎng)絡(luò)中的全部節(jié)點(diǎn)映射到低維向量空間Rd中，d表示維數(shù).

1.2 多標(biāo)簽分類指標(biāo)

設(shè)B(TPj,FPj,TNj,FNj)是一個(gè)特定的分類值，TPj，F(xiàn)Pj，TNj，F(xiàn)Nj分別表示準(zhǔn)確率，精確率，召回率 和Fβ.這些值可以在以下兩個(gè)模型中測試節(jié)點(diǎn)分類的性能[5].

(i) macro-F1model

(1)

(ii) micro-F1model

(2)

1.3 多路鏈路預(yù)測指標(biāo)

AUC指標(biāo)[6]用于測試鏈路預(yù)測方法的性能.AUC得到的值可以解釋為隨機(jī)選擇的缺失鏈接比隨機(jī)選擇的不存在鏈接獲得更高分?jǐn)?shù)的概率.如果在n個(gè)獨(dú)立的比較過程中，有n'次缺失的鏈接具有較高的分?jǐn)?shù)，并且有n″次它們具有相同的分?jǐn)?shù)，則AUC(用A表示)的值為：

(3)

2 算法及相關(guān)原理

2.1 奇異值分解

假設(shè)S是一個(gè)m×n階矩陣，如此則存在一個(gè)分解使得S=UΣZ*.其中U是m×m矩陣；Σ是半正定m×n對(duì)角矩陣；而Z*即Z的共軛轉(zhuǎn)置矩陣，是n×n矩陣.這樣的分解就稱作S的奇異值分解[7].Σ對(duì)角線上的元素Σi，Σi

即為S的奇異值.

(4)

2.2 矩陣循環(huán)疊加(Mscr)

在網(wǎng)絡(luò)結(jié)構(gòu)中，有些網(wǎng)絡(luò)結(jié)構(gòu)十分稀疏，從而會(huì)導(dǎo)致式(4)分解起來相對(duì)困難，會(huì)在式(4)的基礎(chǔ)上進(jìn)行改進(jìn)，如式(5)所示.

(5)

(6)

為了防止過擬合，我們加入正則化項(xiàng)：

(7)

對(duì)于原始矩陣S，我們將上述過程稱為一個(gè)完整的表示過程，當(dāng)進(jìn)行n個(gè)這樣的過程時(shí)，將所得矩陣不斷地通過更新，最終得到式(8)中的Sf.

(8)

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

3.1 環(huán)境準(zhǔn)備

本文實(shí)驗(yàn)硬件環(huán)境配置為i5-8400CPU和16GB內(nèi)存.軟件實(shí)驗(yàn)環(huán)境在Windows10中進(jìn)行，軟件環(huán)境配置為python3.7版本，pytorch1.8版本，實(shí)驗(yàn)所用數(shù)據(jù)如表1所示.

其中Blogcatalog[8]，Wikipedia[9]，DBLP，三個(gè)數(shù)據(jù)集被用作節(jié)點(diǎn)分類任務(wù)，Amazon，YouTube，Twitter數(shù)據(jù)集被用作多路鏈路預(yù)測任務(wù).其中Blogcatalog，YouTube，Twitter數(shù)據(jù)集表示對(duì)應(yīng)博客網(wǎng)絡(luò)，YouTube視頻網(wǎng)絡(luò)，Twitter社交網(wǎng)絡(luò)中用戶之間的內(nèi)在關(guān)系，Wikipedia數(shù)據(jù)集表示維基百科中詞與詞性之間的聯(lián)系，DBLP則是一個(gè)論文網(wǎng)絡(luò).本實(shí)驗(yàn)運(yùn)行時(shí)，規(guī)定了所有方法中，維度d都設(shè)置為128.對(duì)于deepwalk和Node2vec兩種方法，設(shè)置步長為40，每個(gè)節(jié)點(diǎn)的步行次數(shù)為10.對(duì)于node2vec兩個(gè)參數(shù)p和q都設(shè)置為0.25.

表1 數(shù)據(jù)集

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 多標(biāo)簽分類

我們首先評(píng)估了Mcsr方法在節(jié)點(diǎn)分類任務(wù)上的性能表現(xiàn).為了和其他幾種方法比較，我們隨機(jī)挑選一部分節(jié)點(diǎn)作為此次實(shí)驗(yàn)的訓(xùn)練集，余下的節(jié)點(diǎn)作為此次實(shí)驗(yàn)的測試集，所有方法的訓(xùn)練比率(TR)范圍均從0.1～0.9.上述過程重復(fù)50次，所得Micro-F1分?jǐn)?shù)取平均值即為所得方法分?jǐn)?shù).實(shí)驗(yàn)結(jié)果如圖2所示.在Wikipedia和DBLP網(wǎng)絡(luò)中，Mcsr方法優(yōu)于其他三種方法.在DBLP網(wǎng)絡(luò)中，Mcsr方法有著最好的表現(xiàn)，在Blogcatalog方法中，當(dāng)TR>0.5時(shí)，Mcsr方法好于Deepwalk方法.在Blogcatalog網(wǎng)絡(luò)和DBLP網(wǎng)絡(luò)中，Deepwalk方法保持著良好的性能，均比其他2種方法穩(wěn)定，但不及Mcsr方法.

圖2 三種網(wǎng)絡(luò)上的Micro-f1分?jǐn)?shù)

3.2.2 多路鏈路預(yù)測

我們還評(píng)估了Mcsr在多路鏈路預(yù)測上的性能，本實(shí)驗(yàn)使用Amazon，YouTube，Twitter三種網(wǎng)絡(luò)，并采用式(3)中的AUC指標(biāo)來比較和其他三種方法的性能.網(wǎng)絡(luò)中被移除的邊的15%作為測試集，剩余邊作為訓(xùn)練集，此次實(shí)驗(yàn)同樣重復(fù)做50次，取結(jié)果平均值得到AUC分?jǐn)?shù).

結(jié)果如表2所示，從表2中可以看到，Mcsr在三個(gè)網(wǎng)絡(luò)中均優(yōu)于其他3種方法.

表2 三種網(wǎng)絡(luò)上的AUC分?jǐn)?shù)

在YouTube網(wǎng)絡(luò)中，其他三種方法性能都比較接近.但Mcsr方法所得分?jǐn)?shù)高于其他所有方法.在Amazon網(wǎng)絡(luò)中，Mcsr相比表現(xiàn)最好的Line方法，性能提升了2.6%.在YouTube網(wǎng)絡(luò)中，Mcsr相比表現(xiàn)最好的Deepwalk方法，性能提升了1.9%.在Twitter網(wǎng)絡(luò)中，Mcsr相比表現(xiàn)最好的Node2vec方法提升了2.4%.與其他三種方法相比，我們的方法在多路鏈路預(yù)測任務(wù)上面能擁有更好的性能.

4 總結(jié)

本文實(shí)驗(yàn)結(jié)果表明，在對(duì)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)用低維向量矩陣表示的過程中，我們的方法相比于傳統(tǒng)的用鄰接矩陣表示復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的方法，節(jié)約了計(jì)算時(shí)間和空間.在多標(biāo)簽分類任務(wù)和多路鏈路預(yù)測任務(wù)實(shí)驗(yàn)結(jié)果中我們可以看出，我們的方法在性能上均優(yōu)于其他三種方法.