基于角色的網絡表征學習方法

徐 攸，王曉萍，熊 贇

（1.復旦大學計算機科學技術學院上海市數據科學重點實驗室，上海 201203；2.上海市經濟和信息化委員會，上海 200125）

0 概述

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

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

1 網絡表征學習

給定網絡G=(V，E)，其中，V 為節(jié)點集，E 為節(jié)點之間的邊集，網絡表征學習目標是將節(jié)點轉換為d維向量的映射h：??d。

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

圖1 Karate club 網絡中節(jié)點相似性可視化Fig.1 Node similarity visualization in Karate club network

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

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

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

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

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

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

2 角色特征提取

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

算法1角色特征提取

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

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

根據網絡結構，對特征聚合的過程如算法2所示。

算法2網絡中鄰居特征聚合

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

算法3特征判斷

本文提出的特征提取算法具有保留網絡中結構相似性的能力。在算法1 中，該過程是以迭代方式基于鄰居節(jié)點完成的，根據第1 節(jié)的基于鄰居的結構等價相關定義，可以得到對于k階結構等價的節(jié)點，k次迭代前每次迭代的特征都相同。因為結構等價是k階結構等價的充分條件，對于結構等價的節(jié)點，算法1 得到的特征始終相同。

3 基于角色的隨機游走

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

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

4 目標矩陣和損失函數的推導

隨機游走的網絡表征學習方法基于Skip-Gram模型。文獻［10］證明Skip-Gram 等價于分解目標矩陣，其矩陣元素為兩個單詞間的點對互信息（PMI），PMI 可以衡量兩個變量的相關性，當兩個變量獨立時PMI 等于0。式（4）定義了兩個單詞的PMI。具體地，將概率密度函數Pr（i）通過單詞頻率來近似，聯合密度函數Pr（i，j）通過兩個詞出現在相同的上下文中的頻率來近似得到式（4）：

其中，D 是所有出現在同一上下文中的單詞對集合，＃代表計數。Skip-Gram 的目標是使得節(jié)點表示向量和節(jié)點上下文表示向量的內積與PMIij的 距離最小。

在Skip-Gram 的基礎上，文獻［12］證明了基于Skip-Gram 模型的DeepWalk 模型的目標矩陣M，如式（5）所示：

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

根據目標矩陣得到損失函數如式（7）所示：

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

本節(jié)通過推導基于角色的隨機游走的目標矩陣得到Role-MF 的損失函數。

5 基于角色的矩陣分解

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

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

6 實驗結果與分析

6.1 數據集

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

表1 網絡數據集Table 1 Network datasets

6.2 結構等價可視化實驗

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

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

6.3 節(jié)點多標簽分類

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

表2 BlogCatalog 數據集節(jié)點分類結果Table 2 Classification results of BlogCatalog dataset nodes %

6.4 節(jié)點多類別分類

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

圖3 多類別分類準確率實驗結果Fig.3 Experimental results of multi-category classification accuracy

6.5 鏈路預測

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

表3 BlogCatalog 數據集鏈路預測結果Table 3 Prediction results of BlogCatalog dataset link %

7 結束語

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