基于矩陣循環(huán)疊加的網(wǎng)絡特征結(jié)構(gòu)表示

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

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

0 引言

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

1 基礎概念

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

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

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

1.2 多標簽分類指標

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

(i) macro-F1model

(1)

(ii) micro-F1model

(2)

1.3 多路鏈路預測指標

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

(3)

2 算法及相關原理

2.1 奇異值分解

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

即為S的奇異值.

(4)

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

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

(5)

(6)

為了防止過擬合，我們加入正則化項：

(7)

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

(8)

3 實驗

3.1 環(huán)境準備

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

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

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

3.2 實驗結(jié)果

3.2.1 多標簽分類

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

圖2 三種網(wǎng)絡上的Micro-f1分數(shù)

3.2.2 多路鏈路預測

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

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

表2 三種網(wǎng)絡上的AUC分數(shù)

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

4 總結(jié)

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