基于角色的網(wǎng)絡(luò)表征學(xué)習(xí)方法

徐 攸，王曉萍，熊 贇

（1.復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室，上海 201203；2.上海市經(jīng)濟(jì)和信息化委員會(huì)，上海 200125）

0 概述

網(wǎng)絡(luò)表征學(xué)習(xí)是當(dāng)前研究的熱門課題之一［1-3］，網(wǎng)絡(luò)作為更加泛化的數(shù)據(jù)形式，其結(jié)構(gòu)的復(fù)雜度遠(yuǎn)高于普通的網(wǎng)格結(jié)構(gòu)。近年來，越來越多的研究人員關(guān)注網(wǎng)絡(luò)或者圖中節(jié)點(diǎn)的表征學(xué)習(xí)，其將圖中的節(jié)點(diǎn)表示成低維的向量并應(yīng)用到節(jié)點(diǎn)分類［4］、社區(qū)發(fā)現(xiàn)［5］、節(jié)點(diǎn)聚類［6］、異常檢測［7］、鏈接預(yù)測［8］和網(wǎng)絡(luò)比對(duì)［9］等學(xué)習(xí)任務(wù)中。Skip-Gram［10］模型在自然語言處理的詞向量表示中具有很好的效果。DeepWalk［2］通過隨機(jī)游走的方式將Skip-Gram 應(yīng)用到網(wǎng)絡(luò)表征學(xué)習(xí)中能較好地表示網(wǎng)絡(luò)結(jié)構(gòu)。此后，隨機(jī)游走的網(wǎng)絡(luò)表征學(xué)習(xí)方法被廣泛使用［1，11］。Skip-Gram 模型實(shí)際上是一種近似方法，已被證明等效于矩陣分解［10，12-13］，該矩陣中的元素是單詞對(duì)之間的點(diǎn)對(duì)互信息（Pairwise Mutual Information，PMI）［10］。此外，在網(wǎng)絡(luò)表征學(xué)習(xí)中通過隨機(jī)游走的方式將圖轉(zhuǎn)換成序列也是一種近似方法，這些方法存在一個(gè)潛在的目標(biāo)矩陣，而對(duì)該矩陣進(jìn)行分解得到的低秩矩陣可以用作網(wǎng)絡(luò)中的節(jié)點(diǎn)表示。同時(shí)研究人員也提出基于矩陣分解的網(wǎng)絡(luò)表征學(xué)習(xí)方法［14］，通過矩陣分解［15］得到的低秩矩陣能夠很好地保留潛在信息和消除噪聲。

在網(wǎng)絡(luò)分析中，可以認(rèn)為網(wǎng)絡(luò)中的某些節(jié)點(diǎn)扮演著相同或相似的角色［16］，如網(wǎng)絡(luò)中一些起橋梁作用的節(jié)點(diǎn)或者起中心作用的節(jié)點(diǎn)，這種角色信息多數(shù)是與結(jié)構(gòu)等價(jià)有關(guān)，或者被弱化認(rèn)為是規(guī)則等價(jià)［17］，而這些具有相似角色的節(jié)點(diǎn)分布在整個(gè)網(wǎng)絡(luò)中的各個(gè)區(qū)域中。針對(duì)上述問題，本文構(gòu)建一個(gè)同時(shí)考慮局部鄰接信息和角色信息的基于角色的矩陣分解（Role-Base Matrix Factorization，Role-MF）模型。根據(jù)角色信息提出基于角色的隨機(jī)游走方法，據(jù)此推導(dǎo)出用于矩陣分解的目標(biāo)矩陣，然后使用奇異值分解得到節(jié)點(diǎn)表征向量。

1 網(wǎng)絡(luò)表征學(xué)習(xí)

給定網(wǎng)絡(luò)G=(V，E)，其中，V 為節(jié)點(diǎn)集，E 為節(jié)點(diǎn)之間的邊集，網(wǎng)絡(luò)表征學(xué)習(xí)目標(biāo)是將節(jié)點(diǎn)轉(zhuǎn)換為d維向量的映射h：??d。

現(xiàn)有網(wǎng)絡(luò)表征學(xué)習(xí)的方法只能保留局部區(qū)域內(nèi)節(jié)點(diǎn)的相似性。例如，Line［3］集中于一階和二階的局部信息，DeepWalk 的隱式目標(biāo)矩陣是不同階鄰接矩陣的冪的加權(quán)平均值，Grarep［14］的目標(biāo)矩陣是不同階鄰居矩陣的拼接。雖然這些方法考慮了不同階的信息或高階信息，但是節(jié)點(diǎn)相似性的保留仍限于局部區(qū)域，以圖1（a）中的Karate club 網(wǎng)絡(luò)［2］為例，任意選中一個(gè)節(jié)點(diǎn)（圖中標(biāo)三角形的節(jié)點(diǎn)），對(duì)DeepWalk的節(jié)點(diǎn)表征可以保留的相似性進(jìn)行可視化，具體地，將DeepWalk 上下文窗口大小設(shè)為10 以獲取十階內(nèi)信息，計(jì)算其對(duì)應(yīng)的目標(biāo)矩陣，然后取出選中節(jié)點(diǎn)的該行其他元素，該行元素衡量了選中節(jié)點(diǎn)與其他節(jié)點(diǎn)之間的相似性，并在圖1（b）中進(jìn)行可視化（以選中節(jié)點(diǎn)為中心，按照與該節(jié)點(diǎn)階數(shù)距離排列）。圖中節(jié)點(diǎn)大小表示與選中節(jié)點(diǎn)相似程度，可以看到，雖然窗口大小為10，僅捕捉到三階內(nèi)的相似性，基于鄰接矩陣或不同階的鄰接矩陣對(duì)于距離較遠(yuǎn)的節(jié)點(diǎn)難以捕捉到其相似性（如后面的結(jié)構(gòu)等價(jià)）。

圖1 Karate club 網(wǎng)絡(luò)中節(jié)點(diǎn)相似性可視化Fig.1 Node similarity visualization in Karate club network

定義1（圖同構(gòu)映射）［18］給定兩個(gè)圖G和H，對(duì)于兩個(gè)圖節(jié)點(diǎn)集之間的一一映射f：VG%VH，如果圖G中任意相鄰的兩個(gè)節(jié)點(diǎn)u和v與圖H中的節(jié)點(diǎn)f(u)和f(v)也相鄰，則稱f是從G到H的同構(gòu)映射。

定義2（圖自同構(gòu)映射）［18］一個(gè)圖到它自身的同構(gòu)映射f稱為圖自同構(gòu)映射。

定義3（結(jié)構(gòu)等價(jià)）對(duì)于圖G中兩節(jié)點(diǎn)u和v，若存在圖自同構(gòu)映射f，令u=f(v)，則u與v結(jié)構(gòu)等價(jià)。

定義4（k階結(jié)構(gòu)等價(jià)）對(duì)于圖G中的節(jié)點(diǎn)u，令表示由與節(jié)點(diǎn)u距離小于等于k的節(jié)點(diǎn)及節(jié)點(diǎn)之間的邊組成的子圖。如果存在從的圖同構(gòu)映射，則節(jié)點(diǎn)u和節(jié)點(diǎn)v具有k階結(jié)構(gòu)等價(jià)性，如度數(shù)相等的節(jié)點(diǎn)為一階結(jié)構(gòu)等價(jià)。

可以看出，結(jié)構(gòu)等價(jià)定義較為嚴(yán)格，k階結(jié)構(gòu)等價(jià)性是本文給出的放松后的定義。兩個(gè)節(jié)點(diǎn)具有結(jié)構(gòu)等價(jià)性，那么必然具有k階結(jié)構(gòu)等價(jià)性，反之并不一定成立。本文的Role-MF 使用提取角色特征來近似結(jié)構(gòu)等價(jià)性，并說明結(jié)構(gòu)等價(jià)的節(jié)點(diǎn)的角色特征是相同的。

定義5（角色特征）圖中的節(jié)點(diǎn)的角色特征為m維向量，m為設(shè)定的角色數(shù)，角色特征由節(jié)點(diǎn)度數(shù)等信息抽取得到，對(duì)于結(jié)構(gòu)等價(jià)的節(jié)點(diǎn)u和v，滿足其角色特征相等。

2 角色特征提取

本節(jié)描述節(jié)點(diǎn)角色特征提取的過程，m維向量ri用于表示節(jié)點(diǎn)i的角色特征，其中m是預(yù)先設(shè)置的角色數(shù)。角色特征向量表明了節(jié)點(diǎn)在m個(gè)角色上的分布情況，該角色特征向量可以捕捉到網(wǎng)絡(luò)中距離較遠(yuǎn)的節(jié)點(diǎn)之間的相似性，可以視為全局特征。為獲得角色特征，本文根據(jù)初始特征對(duì)鄰居節(jié)點(diǎn)的特征進(jìn)行聚合和迭代得到新的特征，并且每次判斷聚合得到的特征是否為新的特征，最終通過非負(fù)矩陣分解得到角色特征。初始特征為節(jié)點(diǎn)的度數(shù)和egonet特征，角色特征提取的整個(gè)過程如算法1 所示。

算法1角色特征提取

輸入圖G=(V，E)，節(jié)點(diǎn)數(shù)N，角色數(shù)目m，初始特征矩陣F∈?N×3，本文實(shí)驗(yàn)中初始特征矩陣的第i行是節(jié)點(diǎn)度di以及二維egonet 特征egoi的拼接

本文應(yīng)用非負(fù)矩陣分解獲得角色特征矩陣R∈?N×m，其中第i行對(duì)應(yīng)于節(jié)點(diǎn)i的角色特征向量。非負(fù)矩陣分解在KL 散度距離下等價(jià)于概率潛在語義分析［19］，故其分解得到的矩陣可作為角色的概率分布。具體來講，分解的目標(biāo)是在對(duì)兩個(gè)參數(shù)矩陣的非負(fù)約束R≥0，S≥0 下，最小化F和RST的距離，本文采用平方差距離，如式（1）所示：

根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)，對(duì)特征聚合的過程如算法2所示。

算法2網(wǎng)絡(luò)中鄰居特征聚合

當(dāng)一輪迭代中沒有新特征產(chǎn)生后，迭代停止。對(duì)于新特征的判斷，這里使用線性回歸的殘差，殘差低于閾值說明新特征幾乎可以被原始特征完全擬合，于是不再作為新特征加入，具體計(jì)算如算法3 所示。

算法3特征判斷

本文提出的特征提取算法具有保留網(wǎng)絡(luò)中結(jié)構(gòu)相似性的能力。在算法1 中，該過程是以迭代方式基于鄰居節(jié)點(diǎn)完成的，根據(jù)第1 節(jié)的基于鄰居的結(jié)構(gòu)等價(jià)相關(guān)定義，可以得到對(duì)于k階結(jié)構(gòu)等價(jià)的節(jié)點(diǎn)，k次迭代前每次迭代的特征都相同。因?yàn)榻Y(jié)構(gòu)等價(jià)是k階結(jié)構(gòu)等價(jià)的充分條件，對(duì)于結(jié)構(gòu)等價(jià)的節(jié)點(diǎn)，算法1 得到的特征始終相同。

3 基于角色的隨機(jī)游走

基于隨機(jī)游走的方法（如DeepWalk 和Node2vec）僅考慮鄰接信息，如式（2）所示，保留的相似性僅限于局部區(qū)域。本文提出基于角色的隨機(jī)游走考慮全局信息。具體來說，Pij考慮表示當(dāng)前處于節(jié)點(diǎn)i處，下一個(gè)訪問到節(jié)點(diǎn)j的概率，由式（3）給出，概率正比于角色特征相似性和鄰接矩陣中的元素Aij之和。

其中，λ 用于衡量角色信息與鄰接信息的相對(duì)重要性，sim 代表相似性度量，使用基于內(nèi)積的余弦相似性，∝代表正比關(guān)系，由于歸一化常數(shù)，Pij不等于Pji。

4 目標(biāo)矩陣和損失函數(shù)的推導(dǎo)

隨機(jī)游走的網(wǎng)絡(luò)表征學(xué)習(xí)方法基于Skip-Gram模型。文獻(xiàn)［10］證明Skip-Gram 等價(jià)于分解目標(biāo)矩陣，其矩陣元素為兩個(gè)單詞間的點(diǎn)對(duì)互信息（PMI），PMI 可以衡量兩個(gè)變量的相關(guān)性，當(dāng)兩個(gè)變量獨(dú)立時(shí)PMI 等于0。式（4）定義了兩個(gè)單詞的PMI。具體地，將概率密度函數(shù)Pr（i）通過單詞頻率來近似，聯(lián)合密度函數(shù)Pr（i，j）通過兩個(gè)詞出現(xiàn)在相同的上下文中的頻率來近似得到式（4）：

其中，D 是所有出現(xiàn)在同一上下文中的單詞對(duì)集合，＃代表計(jì)數(shù)。Skip-Gram 的目標(biāo)是使得節(jié)點(diǎn)表示向量和節(jié)點(diǎn)上下文表示向量的內(nèi)積與PMIij的 距離最小。

在Skip-Gram 的基礎(chǔ)上，文獻(xiàn)［12］證明了基于Skip-Gram 模型的DeepWalk 模型的目標(biāo)矩陣M，如式（5）所示：

其中，A為鄰接矩陣，D為度矩陣，T為上下文窗口大小，D-1A可以視為概率轉(zhuǎn)移矩陣，該矩陣的t次冪可以視為t步轉(zhuǎn)移概率矩陣。具體來講，元素是從節(jié)點(diǎn)i剛好經(jīng)過t步到節(jié)點(diǎn)j的概率。以類似的方式，本文使用式（3）中基于角色的轉(zhuǎn)移概率計(jì)算方法，推導(dǎo)得到的目標(biāo)矩陣如式（6）所示：

根據(jù)目標(biāo)矩陣得到損失函數(shù)如式（7）所示：

其中，E，C∈?N×d，E是節(jié)點(diǎn)表示矩陣，C是節(jié)點(diǎn)上下文表示矩陣。

本節(jié)通過推導(dǎo)基于角色的隨機(jī)游走的目標(biāo)矩陣得到Role-MF 的損失函數(shù)。

5 基于角色的矩陣分解

本節(jié)描述基于角色的矩陣分解模型的整體過程。矩陣分解模型過程如算法4 所示，首先根據(jù)鄰接矩陣A和角色特征矩陣R來組合計(jì)算并歸一化得到轉(zhuǎn)移概率矩陣P，然后計(jì)算基于角色的目標(biāo)矩陣O得到損失函數(shù)，之后應(yīng)用矩陣分解框架［20］計(jì)算節(jié)點(diǎn)表征向量。本文使用SVD 矩陣分解來獲取節(jié)點(diǎn)的表征向量，其可以消除噪聲并被用于多個(gè)網(wǎng)絡(luò)表征學(xué)習(xí)的多個(gè)工作［21-23］。

算法4基于角色的矩陣分解Role-MF

6 實(shí)驗(yàn)結(jié)果與分析

6.1 數(shù)據(jù)集

本文在4 個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，包括可視化結(jié)構(gòu)等價(jià)的Barbell 數(shù)據(jù)集和3 個(gè)節(jié)點(diǎn)分類的數(shù)據(jù)集。Barbell 數(shù)據(jù)集由兩個(gè)團(tuán)和一條路徑組成。BlogCatalog 數(shù)據(jù)集為BlogCatalog 網(wǎng)站數(shù)據(jù)，邊代表博主的關(guān)注關(guān)系，節(jié)點(diǎn)類別為博主的興趣類別，興趣相似的博主傾向于互相關(guān)注使得局部鄰接信息較為重要。Flight Network 為兩個(gè)機(jī)場網(wǎng)絡(luò)數(shù)據(jù)，邊代表機(jī)場之間存在航班，節(jié)點(diǎn)類別為機(jī)場的航班頻繁程度，航班頻繁程度與鄰接信息關(guān)系較弱且機(jī)場可能較為分散，使得具有一定全局信息，網(wǎng)絡(luò)的具體描述如表1 所示。

表1 網(wǎng)絡(luò)數(shù)據(jù)集Table 1 Network datasets

6.2 結(jié)構(gòu)等價(jià)可視化實(shí)驗(yàn)

在如圖2（a）所示的Barbell 圖中，根據(jù)第1 節(jié)的定義對(duì)結(jié)構(gòu)等價(jià)的節(jié)點(diǎn)用相同的顏色表示。目標(biāo)是希望算法學(xué)習(xí)的節(jié)點(diǎn)表征向量可以保存這種結(jié)構(gòu)等價(jià)性，將向量維度設(shè)置為2 以便展示在二維平面上。對(duì)于本文提出的基于角色信息的矩陣分解（Role-MF），如圖2（d）所示，結(jié)構(gòu)等價(jià)的節(jié)點(diǎn)近似被映射到相同的二維空間（在圖中重合），因此Role-MF 可以很好地保留結(jié)構(gòu)等價(jià)性。從圖2（b）可以看出，在DWMF（DeepWalk 所對(duì)應(yīng)的矩陣分解）中，兩團(tuán)深圓色節(jié)點(diǎn)在網(wǎng)絡(luò)中距離較遠(yuǎn)，其在表征空間中距離也較遠(yuǎn)，而正方形節(jié)點(diǎn)在圖中比較接近，在表征空間中也較為接近，故其保留了局部鄰域信息，但是無法捕獲結(jié)構(gòu)等價(jià)性性。如前所述，與DWMF 相比，DeepWalk 是一種近似方法，由圖2（c）中可見，其節(jié)點(diǎn)相似性的保留可以看作DWMF 的近似。

圖2 Barbell 節(jié)點(diǎn)向量可視化Fig.2 Vector visualization of Barbell nodes

6.3 節(jié)點(diǎn)多標(biāo)簽分類

本文節(jié)點(diǎn)多標(biāo)簽分類任務(wù)使用BlogCatalog 數(shù)據(jù)集，所有對(duì)比方法表征維度設(shè)置為128，對(duì)于多標(biāo)簽分類任務(wù)，這里使用Scikit-learn 實(shí)現(xiàn)的邏輯回歸模型。分類訓(xùn)練比例設(shè)置為90%和10%，重復(fù)10 次實(shí)驗(yàn)取平均值，選取Macro-F1 和Micro-F1 作為評(píng)價(jià)標(biāo)準(zhǔn)，評(píng)價(jià)結(jié)果如表2 所示。對(duì)比算法的實(shí)驗(yàn)采用原論文中的設(shè)定。從表2 可以看出，Role-MF 同時(shí)考慮局部信息和全局信息，具有更好的性能。其中，DWMF、DeepWalk、Node2Vec 和Line 主要關(guān)注于一階及二階信息［1-3］等局部信息。如上所述，該數(shù)據(jù)集中局部鄰接信息較為重要，可取得較好效果，而GraphWave 僅考慮結(jié)構(gòu)等價(jià)［24］，Struct2Vec 關(guān)注于度信息［11］，缺少局部信息使得其表現(xiàn)不佳。此外，可以看出DWMF［13］比DeepWalk［2］效果更好，因?yàn)镈eepWalk 通過隨機(jī)游走來近似目標(biāo)矩陣，而DWMF通過分解目標(biāo)矩陣得到節(jié)點(diǎn)表征，從另一方面驗(yàn)證了矩陣分解的有效性。

表2 BlogCatalog 數(shù)據(jù)集節(jié)點(diǎn)分類結(jié)果Table 2 Classification results of BlogCatalog dataset nodes %

6.4 節(jié)點(diǎn)多類別分類

節(jié)點(diǎn)多類別分類任務(wù)使用Flight Network 的兩個(gè)數(shù)據(jù)集，在所有對(duì)比方法中，表征維度設(shè)置為16，分類訓(xùn)練比例為10%～90%，重復(fù)10 次實(shí)驗(yàn)將準(zhǔn)確率的平均值作為評(píng)價(jià)標(biāo)準(zhǔn)，結(jié)果如圖3 所示。如前所述，這兩個(gè)數(shù)據(jù)集上具有一定全局信息，從圖3 可以看出，通過同時(shí)考慮全局信息與局部信息，Role-MF取得了更優(yōu)的結(jié)果且準(zhǔn)確率有較大提升。同樣地，因?yàn)镈eepWalk 是DWMF 的近似，DWMF 通過矩陣分解取得比DeepWalk 更優(yōu)的結(jié)果，Node2Vec 和Line未考慮到Flight Network 中具有的全局信息，實(shí)驗(yàn)結(jié)果與DWMF 和DeepWalk 較為接近，而GraphWave則完全考慮結(jié)構(gòu)等價(jià)，過于嚴(yán)格，在真實(shí)網(wǎng)絡(luò)中效果不佳。

圖3 多類別分類準(zhǔn)確率實(shí)驗(yàn)結(jié)果Fig.3 Experimental results of multi-category classification accuracy

6.5 鏈路預(yù)測

鏈路預(yù)測任務(wù)使用BlogCatalog 數(shù)據(jù)集，對(duì)于數(shù)據(jù)原圖去除30%的連邊，剩下的圖來獲取節(jié)點(diǎn)表征。所有去除的邊作為正樣本，每條正樣本隨機(jī)選取5 條不存在的邊作為負(fù)樣本合為鏈路預(yù)測的數(shù)據(jù)集。節(jié)點(diǎn)表征維度設(shè)置為64，節(jié)點(diǎn)特征拼接后采用邏輯回歸分類器，訓(xùn)練比例設(shè)置為10%和90%，采用AUC和F1 值作為評(píng)價(jià)指標(biāo)，重復(fù)10 次實(shí)驗(yàn)將平均值記錄在表3 中。從表3 可以看出，Role-MF 同時(shí)考慮局部信息和全局信息具有最好的性能。在鏈路預(yù)測實(shí)驗(yàn)中，度數(shù)信息也起到作用，例如兩個(gè)度數(shù)都較高的節(jié)點(diǎn)傾向于相連，故可以看到Struct2vec 取得較好的效果。同樣地，DWMF 比近似方法DeepWalk 取得了更優(yōu)的結(jié)果，考慮二階信息的Node2Vec 和Line 未考慮到全局信息效果較為接近，Graphwave 則完全考慮結(jié)構(gòu)等價(jià)效果不佳。

表3 BlogCatalog 數(shù)據(jù)集鏈路預(yù)測結(jié)果Table 3 Prediction results of BlogCatalog dataset link %

7 結(jié)束語

當(dāng)前的網(wǎng)絡(luò)表征學(xué)習(xí)方法忽略了全局結(jié)構(gòu)等價(jià)信息，本文基于角色的隨機(jī)游走方法，推導(dǎo)出其目標(biāo)矩陣，構(gòu)建基于角色的矩陣分解（Role-MF）模型，利用奇異值分解獲取節(jié)點(diǎn)表示矩陣。該模型可以同時(shí)捕捉到局部信息和全局信息，并有效地進(jìn)行融合。實(shí)驗(yàn)結(jié)果表明，在不同訓(xùn)練比例下，Role-MF 模型AUC 和F1 值在真實(shí)數(shù)據(jù)集上均取得了更優(yōu)的分類與預(yù)測效果。下一步將通過計(jì)算梯度等方式并基于全局信息和局部信息進(jìn)行可視化研究。