基于節點嵌入的權重符號社交網絡高效鏈路預測算法

楊 威 王軼彤

(復旦大學計算機科學技術學院 上海201203)

0 引 言

隨著在線社交網絡的快速發展，許多系統能夠建模成WSSN[1]，以便更細粒度地反映節點之間的關系。在一個權重符號社交網絡中，每條邊上的權值可以同時反映情感的傾向(正或負)以及關系的強弱(具體的數值)。例如，考慮邊權重為+3、+2或-2，不僅具有符號以反映情感的傾向：喜歡/不喜歡、信任/猜忌、朋友/敵人、合作/競爭等，還能抓取關系的強度，如喜歡的程度、猜忌的程度等。在一些在線社交媒體中，邊的符號和權重值是直接給定的。例如，在比特幣的交易平臺(Alpha或OTC)中，用戶能夠使用-10(完全不信任)到10(完全信任)的分數值來評價其他用戶，以此來表達對于其他用戶的態度。與此同時，現實中也存在一些在線的社交網絡，它們給定了邊的符號，但邊的權重需要隱式抽取。例如，在維基百科管理員申請網絡(RfA)中，如果一個維基百科的編輯者想要成為一個管理員，他需要先提交一個申請，而其他的用戶使用三個標簽(支持、中性或反對)中的一個來對這個申請進行投票，輔之以簡短的投票理由。因此，能夠使用一些語義分析工具從投票附加的文本中隱式的抽取出邊的權重并且形成一個權重符號社交網絡[1]。顯然，權重符號網絡能在更細的粒度上反映社交網絡中節點之間的信息。在無權無符號的社交網絡中，鏈路預測問題主要關注于邊存在性的預測，可以擴展為對邊符號(正或負)的預測(符號網絡)。本文專注于權重符號社交網絡的鏈路預測問題，即預測邊上的權重信息，包含符號和數值，反映關系的方向和強弱。目前主要的鏈路預測研究都集中在如何能更好地獲取節點的信息及正確度量節點之間的近似性，但這種思想并不完全適用于權重符號網絡，需要進一步結合社會學理論和網絡結構來提高邊上權重的預測性能。

對于許多社交網絡應用，如鏈路預測[2]和節點分類[3]，其網絡特征的提取是非常重要的。許多算法的性能極大地取決于對輸入網絡特征提取的有效性，節點和網絡結構重要的特征需要盡可能保存。不同于傳統的特征工程方法，網絡嵌入為網絡中的節點學習一個低維度的潛在特征，從而保存網絡的結構信息。網絡嵌入是自動的特征提取，許多研究已經證明此方法優于一些特征工程的方法。特別是近幾年，網絡嵌入方法被廣泛地應用于社交網絡分析領域。本文將基于節點嵌入對權重符號網絡中的邊進行權重預測。

目前的網絡嵌入方法，主要集中在無符號/無權重社交網絡。在無符號社交網絡中，邊被標記為1或者0(1代表存在，0代表不存在)。大多數無符號網絡嵌入的方法基于同構性原理和skip-gram模型[4]。在設計目標函數的過程中，并未考慮邊的符號或權重。文獻[5,15]已經證明負邊具有額外的價值，考慮負邊能夠提高正邊的預測精度。由于負邊的存在，同構性原理不再適用。一些基于平衡理論的方法[6]應用隨機游走策略生成帶有符號的共現對，以此來嵌入符號網絡。這些方法并未直接擬合邊的權重信息，如果將它們直接用于嵌入權重符號社交網絡，將會導致社交鏈路預測的性能不佳。邊的權重在度量節點間關系強度上是一個關鍵要素，它給出了節點間關系的更細粒度信息，并且能更準確地反映網絡結構。同時，在嵌入空間中保存邊的權重信息將會取得更優的邊權重預測性能。

本文提出一種權重符號社交網絡嵌入方法(Weighted Signed Network Embedding，WSNE)，以此來獲得更優的邊權預測性能。WSNE為網絡中的節點學習潛在特征表示，并且在學得的潛在特征空間中盡可能地保存邊的權重和符號信息。在一個權重符號社交網絡中，一條邊eij能夠考慮作為從用戶i到用戶j“主觀性”觀點/評價的傳遞。從用戶j的視角來看，這個觀點/評價是客觀的。因此，對于一個節點i去學習它作為一條邊起始節點的“主觀”潛在特征表示si和作為一條邊終止節點的“客觀”潛在特征表示oi。參照矩陣分解的方法[7]，對于一條邊eij，使用si和oj的點積擬合邊的權重信息。同時在一個權重符號社交網絡中，邊的符號也是非常重要的，因為它反映了不同的情感。例如，如果一條邊的權重是1，擬合值-1和3將會產生同樣的誤差。但是3明顯是更優的擬合值，因為它反映了準確的情感傾向。因此，本文基于擴展的結構平衡理論[8]添加對于邊的符號約束。

本文主要貢獻如下：

1) 提出了一個權重符號社交網絡嵌入方法WSNE來獲得更優的邊權重預測性能。

2) 設計了一個目標函數來學習網絡中節點的“主觀”及“客觀”潛在特征表示。在學得的潛在特征空間中，保存了邊的權重和符號信息。

3) 在三個真實網絡數據集上進行社交鏈路預測任務。使用根均方誤差、相關系數、符號預測準確率等多個評價指標，與多個相關且優秀的算法進行比較。實驗結果表明，WSNE在上述評價指標上實現了更優的權重預測性能。

1 相關工作

本文使用網絡嵌入的方法解決權重符號社交網絡中的社交鏈路預測問題，因此主要關注于網絡嵌入方法和權重預測方法。

1.1 社交網絡分析中的網絡嵌入

大多數網絡嵌入方法主要關注于無符號網絡[4,9-12]和無權帶符號社交網絡[13-18]。對于無符號社交網絡，許多方法是基于同構性原理并且參考skip-gram模型[4,10]來學習節點的嵌入。Perozzi等[4]通過將截斷隨機游走生成的節點序列和語料庫中的句子等價，來學習節點的潛在特征表示。Tang等[9]設計了一個目標函數來保存局部和全局的網絡結構，同時還提出了一個邊抽樣技術來解決經典隨機梯度下降方法的限制。Grover等[10]提出了一個靈活的節點鄰居概念，并且設計了一個偏好隨機游走程序來獲得多樣性的鄰居。此外，Ou等[11]關注有向無符號網絡，提出HOPE方法在學得的嵌入空間中保存邊的不對稱傳遞性。Wang等[12]提出一個半監督的深度學習模型來優化一序和二序鄰近性。但上述嵌入方法并未考慮到邊的符號和權重信息。

對于無權符號網絡，文獻[13]使用log-bilinear模型，通過最大化在給定路徑下生成目標節點的條件概率來學習節點的源嵌入和目標嵌入。文獻[14]使用word2vec嵌入方法，并提出一個目標節點抽樣策略來維持高序鄰居間的結構平衡。文獻[15]提出了一個深度學習框架SiNE來學習節點的潛在特征表示，優化一個結構平衡理論指導的目標函數。文獻[16]采用多個信息源：情緒信息、社交信息和簡歷信息，并且使用多個自編碼器來訓練每一個信息源。文獻[17]利用網絡結構和節點的屬性來學習符號社交網絡的嵌入。文獻[18]提出一個網絡嵌入方法SIDE，完善編碼邊的符號和方向信息。但上述方法并未直接擬合邊的權重信息，如果直接用于解決權重符號社交網絡的社交鏈路預測任務，將不會獲得最佳的性能。

1.2 權重預測任務

在邊權預測中，大部分的相關工作關注于無符號社交網絡。Gilbert[19]提出了一個Twitter應用——We Middle，其核心是Facebook鏈接強度模型的設計，以此來評估鏈接的強度。Xiang等[20]使用交互信息(例如社區和標簽)和用戶的相似性開發了一個無監督模型來獲取關系的強度。在權重符號社交網絡的邊權預測中，Kumar等[1]提出Fairness和Goodness兩個特征來預測邊的權重。還有多個方法也能夠應用于權重符號社交網絡中的權重預測，例如：reciprocal，PageRank，signed eigenvector centrality，bias and deserve，EigenTrust和signed-HITS[1]。但文獻[1]已經證明Fairness和Goodness(FG)能夠取得更優的權重預測性能，因此本文方法主要與FG方法進行比較。

2 問題描述

一個權重符號社交網絡被建模成一個有向的加權圖G=(V，E，E+，E-，W)，其中：V是節點集合；E是邊集合；E+是正邊集合；E-是負邊集合；W∈R|V|×|V|是一個邊權矩陣。在W中每一個元素Wij表示一條從i到j的有向邊的權重。當談論一條邊的權重時，例如-5，它實際上指示著邊的符號和關系的強度。本文嘗試為網絡中的節點學習“主觀”潛在特征S和“客觀”潛在特征O，以此來擬合邊的權重信息。即本文想要學習一個轉移函數f(·)，使得：

f(V,E,W)→(S,O)

(1)

式中：S和O的維度是|V|×K(K?|V|)，|V|是節點的數目，K是潛在特征的維度。問題的關鍵在于如何設計一個有效目標函數來學習更好的節點嵌入。

3 算法設計

3.1 邊權重的擬合

(2)

3.2 添加符號約束

在一個權重符號社交網絡中，符號擬合的一致性是非常重要的。對于一條真實權重為1的邊，即使有著相同的誤差，擬合值為-1或者3是完全不同的結果。顯然3是更好的擬合值，因為它準確地擬合了情感的傾向。因此，對于網絡中每一條存在的有向邊，在擬合其權重時，不僅需要擬合權重的數值，還需要準確擬合符號，本文添加一個局部的符號約束來滿足這一點，目標是最小化擬合值和真實值之間誤差的同時，保持符號的一致。同時，實驗結果表明權重預測中符號和數值之間是相互提高的，既提高擬合值和真實值之間符號的一致性，也能夠進一步提高社交鏈路預測的性能。

符號約束是基于社會學中的擴展的結構平衡理論[8]，即正邊端點之間的相似性大于負邊端點之間的相似性：

sim(i,j)>sim(h,k)eij∈E+,enk∈E-

(3)

式中：sim(·，·)是一個相似性度量函數。與文獻[18]相同，本文使用Sigmoid函數度量兩個端點之間的相似性：

(4)

式中：si表示“主觀”矩陣S中第i行;oj表示“客觀”矩陣中的第j行。

(5)

使用對數運算來簡化上式的計算，并且為了與擬合權重中最小化目標函數一致，將轉換式(5)為：

(6)

結合式(2)和式(6)，WSNE方法總的目標函數為：

L(S,O)=M+γ×C

(7)

式中：γ為參數，控制著符號約束的貢獻。本文使用隨機梯度下降算法來獲得目標函數的局部最優值。

3.3 算法步驟

將數據集劃分為兩個部分：當前網絡中存在的正邊集合和負邊集合。對于每一個部分，分別描述其優化過程。

對于集合E+中的邊eij，求解si和oj的梯度：

(8)

對于集合E-中的邊eij，求解si和oj的梯度：

(9)

基于式(10)迭代地更新si和oj，這里α為學習速率(本文設定α=0.005)。

(10)

當目標函數連續兩次平均值之差小于預先定義的閾值(本文設定為0.005)時，則認為算法收斂。WSNE的詳細描述如算法1所示，其時間復雜度為：

o(t×|E|×K)

(11)

式中：t是迭代的次數;|E|是邊數;K是潛在特征的維度。

算法1WSNE

輸入：G、β、γ。

輸出：S、O。

隨機初始化S、O;

While 不收斂do:

Foreij∈(E+∪E-):

Ifeij∈E+:

根據式(8)計算si和oj的梯度;

Ifeij∈E-:

根據式(9)計算si和oj的梯度;

根據式(10)更新si和oj;

End

4 實 驗

本節將驗證WSNE算法在權重符號社交網絡中的社交鏈路預測問題上的性能。特別地，算法的驗證主要集中在該種網絡的邊權重預測問題。

4.1 數據集

本文在3個數據集上運行WSNE算法并驗證其性能。

1) 比特幣Alpha[21]和比特幣OTC[22]：它們是來自于兩個比特幣交易平臺Alpha和OTC的信任網絡。每一個用戶能夠使用-10(完全不信任)到10(完全信任)間隔為1的數字，來表達他們對于其他用戶的態度。

2) 維基百科管理員申請網絡(RfA)：使用文獻[1]中提供的RfA數據集，其權重范圍是[-1,1]。為了便于比較，離散化數據集的取值范圍到[-10, 10]，間隔為1，并且僅考慮正邊和負邊。

三個數據集的具體統計描述如表1所示。

表1 數據集的統計信息

4.2 評價指標

本文選擇根均方誤差(Root Mean Square Error，RMSE)和相關系數(Correlation Coefficient，CC)作為權重預測性能的評價指標。RMSE度量預測值和真實值之間的差異程度，其值越小越好。CC度量兩個序列之間的相關性(真實值序列和預測值序列)，該值越高則表明預測序列的改變趨勢和真實值序列之間越具有相關性。

在一個權重符號社交網絡中，邊的符號預測同樣重要。因此，還需探討取得優異權重預測數值時的符號預測性能，即有多少情感傾向被準確地預測。本文使用符號準確率(SignAccuracy, SA)作為符號預測的評價指標(SA=預測正確的符號數/總的預測邊數)。

4.3 參數分析

WSNE方法包含3個重要的參數：潛在特征的維度K、控制正則項貢獻的參數β和控制符號約束貢獻的參數γ。本文選擇比特幣Alpha數據集、RMSE和CC度量指標作為例子來闡述參數的敏感性問題。根據預實驗，參數的分析范圍可以大致確定為：K∈[5,30]，間隔為5；β∈[0.5,2.5]，間隔為0.5；γ∈{1,5,10,15,20}。對三個參數使用網格搜索，找尋一組性能相對優異的參數取值。為了便于對單個參數的研究，分析一個參數時，固定另外兩個參數。將數據集隨機劃分為兩部分，其中訓練集的比例為80%，測試集的比例為20%(本文不考慮冷啟動問題，即未被訓練過的節點不會參與預測)。對訓練集使用五折交叉驗證來評估參數的選擇。使用范圍內的隨機值初始化潛在特征矩陣S和O。重復實驗5次，取平均值作為最終的結果。

1) 參數K。分析參數K時，固定β=1.5、γ=10，具體的實驗結果如圖1和圖2所示。

圖2 參數K的CC值分析結果

可以看出，隨著K值的增加，RMSE先減小后增大，CC先增大后減小。當K取[20, 30]范圍內時，RMSE和CC都取得最優的結果。權重預測是一種細粒度的問題，過大的K值會損害權重預測的性能。同時K取值越大，需要的存儲空間越多。在實際操作中，K的取值不宜過大，對于不同的數據集而言，K的最優取值不同。

2) 參數β。分析參數β時，固定K=25、γ=10，具體的實驗結果如圖3和圖4所示。

圖3 參數β的RMSE值分析結果

圖4 參數β的CC值分析結果

可以看出，隨著β值的增加，RMSE先減小后增大，CC先增大后減小。當β取[1,2]范圍內的值時，RMSE取得最優值。當β取[1.5,2.5]范圍內的值時，CC取得最優值。β控制著正則項的貢獻，用來避免過擬合問題。過大的β值，將會損害權重的擬合，從而導致權重預測性能下降。

3) 參數γ。分析參數γ時，固定K=25、β=1.5，具體的實驗結果如圖5和圖6所示。

圖5 參數γ的RMSE值分析結果

圖6 參數γ的CC值分析結果

可以看出，隨著γ值的增加，RMSE先減小后增大，CC先增大后減小。當γ的取值在范圍[5, 15]內時，RMSE和CC都獲得了最優的結果。γ控制著符號約束的貢獻，適當地添加符號約束能夠提高權重預測的性能。但是，過大的符號約束將會引入噪聲，導致權重預測性能的降低。

基于上述參數的分析，為了后續實驗的便利和各個數據集上的統一，本文實驗中設定K=25、β=1.5、γ=10。

4.4 對比算法

本文選取了如下4個算法進行對比：

1) Fairness 和Goodness(FG)[1]。這一算法也用來預測權重符號社交網絡中的邊權重。該算法提出了兩個度量指標：Goodness衡量節點被其他節點喜歡的程度，而Fairness用來衡量節點評價其他節點的公平性。通過迭代計算來獲得節點的Fairness和Goodness的值，進而用Fairness和Goodness的積預測邊權重。這與WSNE的研究背景最相似。

2) node2vec[10]。這是一個無符號社交網絡嵌入的方法。node2vec擴展了節點鄰居的概念，并且設計了一個偏好隨機游走程序來獲取多樣性的鄰居。通過將其與WSNE進行比較，驗證是否可以直接用傳統無符號網絡嵌入的方法預測WSSN中的權重。

3) SIGNet[14]。這是一個符號網絡嵌入的方法。SIGNet擴展了word2vec嵌入方法，并用于符號社交網絡。它為每一個節點構造一個緩存，通過從緩存中抽樣來改進負抽樣技術。與該算法的比較，將驗證在WSSN中進行權重預測時，權重的符號和數值這兩個因素之間的關系。實驗結果表明，只考慮符號的嵌入，不直接擬合邊的權重信息并不能獲得滿意的預測性能。

4) MF[7]。這是一個矩陣分解的方法，使用潛在特征向量之間的點積來擬合邊的權重。通過比較，能夠進一步驗證添加符號約束是否能夠改進權重預測的性能。

本文提出的WSNE算法采用潛在特征向量的點積來擬合邊的權重信息，并且將符號約束添加到目標函數中以提高權重預測的性能。

4.5 結果與分析

在一個權重符號社交網絡中，主要關注權重預測任務。將數據集劃分為兩部分：訓練集為80%，測試集為20%。由于無符號網絡嵌入的方法不能夠處理負邊，因此，在它嵌入學習的過程中刪除負邊。在實現對比方法時，本文使用相應文獻中提供的默認參數設定。將對比算法[10, 14]中學得的節點潛在特征進行級聯為邊的特征，作為預測模型的輸入(在權重預測中使用線性回歸方法，在符號預測中使用邏輯回歸方法)。WSNE方法直接使用節點潛在特征向量的點積來進行權重預測和符號預測任務。

1) 權重預測。使用RMSE和CC來評價權重預測的性能。實驗結果如表2所示。

表2 權重預測的實驗結果

可以看出，在所有的情況下，WSNE算法都取得了最優的表現。其對于node2vec和SIGNet方法的優勢表明直接將無符號網絡和符號網絡嵌入的方法用于權重預測問題，并不能獲得優異的預測性能。同時，WSNE算法也優于MF算法，表明添加符號約束到目標函數中能夠提高權重預測的性能。

2) 符號預測。符號在權重符號社交網絡也是非常重要的，因此在已獲得較好的權重預測性能的基礎上，本文將進一步驗證符號預測的性能。使用SA作為符號預測的評價指標，實驗結果如表3所示。

表3 符號預測的實驗結果

可以看出，在取得優異的權重數值預測性能的情況下，WSNE算法也取得了優秀的符號預測性能，即WSNE算法準確地擬合了邊的符號信息。此外，在RfA數據集上，多個方法的性能都是不佳的。這可能是因為，RfA是一個人工生成的權重符號社交網絡，在使用語義分析工具將文本內容轉化為邊權值時引入了噪音。同時，文獻[1]提供的RfA數據集的邊權范圍為[-1,1]，本文離散化該范圍為[-10,10]，間隔為1。即，對于在(0.1,0.2]范圍內的值，離散化為2。再者，也可能是由于RfA數據集負邊比例相對較大，上述算法不能很好地處理負邊。

3) 稀疏性問題。為了探索數據稀疏性問題，本文按照不同的比例來劃分比特幣Alpha數據集。增加測試集的比例同時減小訓練集的比例，實驗結果如圖7和圖8所示。

圖7 RMSE值的稀疏性結果

可以看出，隨著測試集比例的增加，各個算法的性能都有了不同程度的降低。但WSNE算法依舊取得了最優的權重預測性能，這表明WSNE算法能夠更好地適應數據稀疏性問題。

5 結 語

本文提出了一個權重符號社交網絡嵌入算法WSNE，來解決權重符號社交網絡中的權重預測問題。WSNE算法使用每條邊兩個端點的潛在特征向量的點積來擬合邊的權重。同時該算法考慮到在權重符號社交網絡中符號的重要性，提出符號約束并結合到目標函數中。本文在三個真實數據集上實現權重預測，并與其他相關且性能優秀的算法進行了比較，數值和符號預測的實驗結果表明WSNE算法取得了更優的社交鏈路預測性能。

盡管本文算法利用了邊的符號信息來提升權重預測的性能，但只考慮了局部的符號約束，在未來的工作中將探索并結合更多的全局符號約束，以進一步提高權重預測性能。同時，盡管在數據稀疏性問題上WSNE算法的表現都最優，但是隨著訓練集比例的減少，WSNE算法的性能還是受到了明顯的影響。在未來的工作中，希望利用更多額外的信息，例如節點的屬性信息，來緩解數據稀疏性問題。