基于結構平衡理論和高階互信息的符號網絡表示學習算法

郁 湧，錢天宇，高 悅，艾合買提尼牙孜，劉金卓*

(1.云南大學軟件學院 昆明 650504；2.云南大學云南省軟件工程重點實驗室 昆明 650504；3.云南大學跨境網絡空間安全教育部工程研究中心 昆明 650504)

在一些網絡中，節點之間的連接關系根據不同的涵義可以分成兩類：正關系和負關系。其中，正關系表示積極的涵義，如喜歡、信任、合作、支持等；而負關系表示消極的涵義，如討厭、不信任、對立、否決等[1]。若將相關網絡中的正關系標注為正號，負關系標注負號，就形成了一個符號網絡。目前，符號網絡存在于很多的領域，如社交網絡用戶之間存在朋友與敵人關系、生物領域細胞間存在促進與抑制作用、國際關系中國家之間存在合作與敵對關系、游戲網絡中玩家存在協作與競爭關系等。對符號網絡進行分析和研究也越來越成為社會網絡研究中不可忽視的部分[2]。

在針對符號網絡結構的研究中，一個重要的問題就是如何合理有效地對符號網絡的結構信息進行表示。傳統的網絡結構表示主要采用高維稀疏矩陣的形式，但高維稀疏矩陣往往需要更多的時間和空間成本。隨著人工智能和機器學習的突飛猛進，越來越多的研究領域都融入了深度學習等相關技術，而傳統的網絡結構表示方法都無法直接應用這些算法，為此，研究人員開始轉向探索網絡節點的低維向量表示的方法，即網絡表示學習(network representation learning)或網絡嵌入(network embedding)。網絡表示學習是銜接網絡中原始數據和網絡應用任務的橋梁，旨在將網絡中的節點表示為低維稠密向量，并且能夠最大程度地保留原網絡中的結構信息和特性。

雖然，網絡表示學習的研究已經取得了一系列的成果，但現有的方法大都僅適用于無符號網絡，將其應用于符號網絡會導致網絡中符號涵義等關鍵信息丟失，難以獲得質量較高的節點表示學習。如在朋友敵人網絡中，互為敵人關系的節點可能會在嵌入空間被放得很近，這十分不合理。為此，需要研究針對符號網絡的表示學習方法。

本文基于結構平衡理論和高階互信息原理來對符號網絡的拓撲結構進行研究，旨在建立結合機器學習與傳統網絡理論的相似度指標，提出一種新的符號網絡表示學習方法SNSH (signed network representation learning algorithm based on structural balance theory and high-order mutual information)，并用于解決無向符號網絡中的鏈路符號預測問題。

1 相關工作

網絡表示學習旨在用低維、稠密、實值的向量表示網絡中的節點。一般來說，通過網絡表示學習得到的節點嵌入需要體現節點的各項特征，并能在各種下游任務取得良好的性能。

網絡表示學習已被廣泛應用于節點分類[3-4]、鏈路預測[5]、聚類[6-8]、可視化[9]、節點排序[10-11]、社區分析[12]、圖形生成[13]、異常檢測[14]等任務，并取得了良好的效果。節點分類的目的是根據其他節點和網絡的拓撲結構來確定節點的標簽；鏈接預測是指預測未來可能出現的缺失或鏈接；聚類用于尋找相似節點并將它們分組；可視化可用于洞察網絡結構[15]。在符號網絡中，主要的下游任務是鏈路符號預測[16]，即預測節點之間邊的符號類型。

網絡表示學習的方法大致可以分為矩陣分解、隨機游走、深度學習和其他4 個類別。如基于矩陣分解的Laplacian Eigenmaps[17]、HOPE[18]等，基于隨機游走的DeepWalk[19]、node2vec[20]等，基于深度學習的SDNE[21]、DNGR[22]、GCN[23]等，還有混雜的LINE[24]等。

對于符號網絡表示學習，SiNE[25]通過多層神經網絡來優化基于結構平衡理論指導的目標函數，對符號網絡的表示進行了學習。Signet[26]修改了word2vec[27]模型的采樣方式，通過隨機游走構造高階結構平衡環來擬合遠距離鄰居節點對節點符號的影響。SGCN[28]將GCN 推廣到符號網絡中，并基于平衡理論設計了一種新的信息聚合器。SNEA[29]利用自注意機制來提高符號網絡表示學習的效果。SDGNN[30]引入了一種新的逐層有向符號網絡GNN模型。但這些方法都并未考慮高階互信息對節點嵌入的影響。

本文提出的基于高階互信息的符號網絡表示學習算法，通過將符號網絡中的關系反轉，生成網絡的負符號嵌入、負特征屬性向量、負局部概括等負信息。該項工作通過負信息強化網絡的正信息，以此捕獲網絡中高階互信息所隱含的信息量。

2 問題定義

本文涉及的符號網絡的定義如下：將符號網絡用無向圖表示，記為G=(V,E,S)。其中V代表社交網絡中節點的集合，E代表網絡中節點之間關系的邊集合，S={1,-1}代表邊的符號關系。對于?e(i,j)∈E， 則s(i,j)表 示節點vi與 節點vj之間的關系符號，s(i,j)=1代表“+”，表示節點之間具有信任、合作、友好、支持等積極關系；s(i,j)=-1代表“-”，表示節點之間具有不信任、敵對、討厭、否決等消極關系。

2.1 結構平衡理論

結構平衡理論是無向符號網絡研究的理論基礎，為無向符號網絡的結構分析提供了依據。根據該理論，在無向符號網絡中，由k(k≥3)條邊組成的閉合環是結構平衡的當且僅當該環上所有邊的符號之積為正。文獻[31]研究表明，真實符號網絡中結構平衡環的數量遠大于不平衡環的數量，且隨著網絡結構的演變，不平衡的結構會朝著平衡的結構轉換。此外，文獻[32]用大量實證分析表明，結構平衡理論能更好地捕獲并分析無向符號網絡中節點間的相互作用模式以及結構平衡性。

結構平衡理論[33]最初僅在個體層面上提出，接著由文獻[34]在群體層面的圖論形成中加以推廣，而后又由文獻[35]發展為可聚類圖的概念。最近，結構平衡理論被擴展為符號網絡中的一種結構，它應確保節點的“朋友”比“敵人”更近[36]，即節點的位置應該離“朋友”(或具有正鏈接的節點)比“敵人”(或具有負鏈接的節點)更近。這種節點之間的結構描述如圖1 所示。圖中，對節點1 來說，它的“朋友”節點2 在特征空間上的距離應當相對于它的“敵人”節點3 來說會更近些。

圖1 結構平衡理論示意圖

2.2 互信息

互信息可以度量兩個隨機變量之間的相互依賴性。給定兩個隨機變量X和Y，它們的互信息為：

式中，H(X)和H(X|Y)分 別表示熵和條件熵；H(X,Y)表示X和Y的聯合分布。

為了測量多個隨機變量之間的相互依賴性，在信息論中引入高階/多元互信息的概念[37]。高階互信息是互信息在隨機變量數目增多時的推廣，給定N個隨機變量，高階互信息的定義與互信息的定義類似，具體為：

高階互信息不僅能捕捉所有隨機變量對之間的互信息，還能衡量隨機變量間的協同作用。

2.3 深度圖互信息

深度圖互信息( deep graph infomax, DGI )[38]是一種自監督或無監督的機器學習方法，其主要思想是最大化網絡G:I(h,s)的概括向量s和節點嵌入hi之間的互信息。

DGI 使用負采樣來最大化I(h,s)，首先它通過函數G=生 成一個補圖， 然后使用同一個編碼器來分別獲得正圖的節點嵌入和補圖的節點嵌入，本文考慮到符號網絡的特殊性，通過轉換鏈接的符號正負來生成負網絡。即對于負網絡，=-si j，其余屬性與圖G保持一致。

正網絡G通過聚合網絡中所有節點的方式得到整圖的特征表示，即概括向量，對于給定的概括向量s，DGI 使用一個鑒別器D來區分正網絡嵌入hi和 負網絡嵌入。

給定節點嵌入hi、概括向量s和負節點嵌入，可以通過下面的目標函數來最大化hi和s之間的互信息：

式中，D是一個用來區分負節點嵌入和真實節點嵌入的鑒別器； Θ表示參數空間； E表示期望。

3 SNSH 算法

3.1 算法的基本框架

本文提出的基于結構平衡理論和高階互信息的符號網絡表示學習算法SNSH，通過改進的上下文詞向量模型得到節點的局部符號嵌入，又通過一個單層的圖卷積神經網絡(graph convolutional network,GCN)得到網絡的局部嵌入矩陣和全局概括向量，同時使用節點的出/入度等有價值特征作為其特征屬性向量。本文通過最大化這三者間的高階互信息，挖掘符號網絡中隱含的內部信息、外部信息與聯合信息。

本算法由局部符號信息擬合、網絡結構擬合、特征屬性向量構造和最大化高階互信息4 個部分組成，其基本框架如圖2 所示。

圖2 算法整體框架圖

1) 局部符號信息擬合

局部符號信息擬合用于得到符號網絡中節點的局部符號信息。該模塊改進了傳統上下文的節點嵌入模式，首先根據節點的直接鄰居構造正負關系鄰居集，接著基于結構平衡理論，使用新的負采樣方式優化節點嵌入，從而捕捉節點對與直接鄰居間的符號信息。

2) 網絡結構擬合

網絡結構擬合用于進行全局網絡結構傳播擬合。該模塊使用能體現網絡符號信息特征的嵌入作為輸入，經過單層GCN 的聚合，得到體現網絡局部特征的嵌入矩陣H與體現網絡全局特征的概括向量s。

3) 特征屬性向量構造

特征屬性向量構造用于得到綜合考慮節點內在特征的特征屬性向量。在該模塊中對每個節點計算其度數、正鄰居節點數、負鄰居節點數以及體現節點建立正向鏈接趨勢的指標，并將其構成節點特征屬性向量。這些指標在傳統符號鏈路預測方式中被證明能夠有效體現節點特征。

4) 最大化高階互信息

最大化高階互信息用于最大化符號網絡節點的高階互信息，涵蓋節點嵌入與概括向量之間的外部信息量、節點嵌入與特征屬性向量之間的內部信息量，以及節點嵌入與概括向量和特征屬性向量兩者間的聯合信息量，更有利于全面地捕捉符號網絡隱含的特征信息。

3.2 局部符號信息擬合

1) 模型構建

使用P維向量xi∈RP作為節點vi∈V的局部符號向量表示，不同節點vi與vj之 間的相似度P(vi,vj)為：

式中， σ是sigmoid 函數。

基于結構平衡理論，最大化正關系節點間的相似度，并最小化負關系節點間的相似度，目標函數構造為：

式中，sij∈{1,-1}。

通過最大化式(5)，就可以得到節點vi的局部符號特征的k維向量表示xi。

2) 節點對采樣

在這里，SNSH 拓展了傳統的負采樣策略，依據邊的類型，在相應集合中選取負采樣節點，以使其適用于符號網絡。如對于sij=1的正關系節點對，該方法從節點vi與vj的 負鄰居集及進行采樣，來最大化節點vi與vj之間相對于其負鄰居集中節點的相似度。同理，對于sij=-1的負關系節點對，從節點vi與vj的 正鄰居集及進行采樣，來最小化節點vi與vj之間相對于其正鄰居集中節點的相似度。因此，基于條件獨立假設和特征空間的對稱性假設，可以為每個節點構造目標函數：

式中，sij=1；siu=-1； σ是sigmoid 函數。

3) 模型優化

為了方便計算，改進了傳統的負采樣方式，每次僅優化一對節點及確定數目的負樣本。同時采用定義虛擬節點的方法，解決了部分節點不存在負樣本的問題。

本模塊采用了創新的負采樣方式，基于詞向量模型及結構平衡理論，對符號網絡中的正負關系進行了擬合，最終得到了可以體現符號網絡特性分布的p維節點嵌入矩陣X，供后面使用。

3.3 網絡結構擬合

在該部分使用一個節點嵌入編碼器ε=RN×P×RP×d→RN×d來進行網絡結構擬合。模型的輸入是節點的局部符號信息擬合向量xi∈XP，目標是生成d維節點嵌入矩陣H(用hi來表示矩陣H的第i行向量)以及概括向量s。該編碼器是一個單層的GCN：

使用擬合符號結構后的節點嵌入作為GCN 的輸入，而非重新定義GCN 的傳播模式，并引入ω1,ω2∈R來 控制自連接的權重。較小的 ω1或 ω2表明，節點本身在生成其嵌入中起著更重要的作用，這也意味著降低了其鄰居節點的重要性。對于正關系和負關系給予不同的權重，以擬合它們在傳播中對鄰居的不同影響。

編碼器產生的hi嵌 入了以節點vi為中心的網絡的區域特征，而不僅僅是節點本身。為了得到網絡級別的概括向量s，使用函數RN×d→Rd，通過聚合節點特征的方式來得到整圖的特征表示，函數定義為：

3.4 特征屬性向量構造

傳統方法使用節點的入度、出度、地位、建立正向邊趨勢等屬性對邊符號進行預測[39]，實驗表明，這些節點的特征屬性對節點的特征學習是有意義的，但它們往往在符號網絡表示學習方法中被忽略。對節點vi∈V，其特征屬性向量fi∈F表示為：

式中， dei代 表節點vi的 度；分別表示節點vi的 正關系鄰居數以及負關系鄰居數； pri表示節點vi建立正向邊的趨勢，其計算方法為：

3.5 高階互信息估計

對于符號網絡中的節點，使用最大化高階互信息來綜合考量3 類變量，分別是節點嵌入hi、網絡的概括向量s和節點的特征向量fi。

根據高階互信息的定義，當N=3，有：

該式可進一步化為：

式中，I(X1;X2,X3)表 示變量X1同 變量X2,X3的聯合分布之間的互信息。通過使用hi，s和fi替 代X1，X2，X3，可以得到式子：

式中，I(hi,s)捕獲外部信息量，即節點局部嵌入h與全局嵌入之間s的依賴；I(hi,fi)捕獲內部信息量，即節點局部嵌入h與節點本身特征屬性向量f之間的依賴；I(hi;s,fi)捕獲聯合信息量，即外部和內部信息量之間的交互。即通過外部信息量、內部信息量和聯合信息量三者，可以衡量網絡的高階互信息，這3 個信息量的嵌入過程如圖3 所示。在高階互信息最大化模塊，將依次進行目標函數的構造。

圖3 外部、內部和聯合信息量示意圖

3.6 高階互信息最大化

通過最大化局部互信息來捕獲整個網絡的高階信息量。根據式(13)，最大化高階互信息等同于最大化3 種局部互信息：

接下來，給定節點嵌入矩陣H、概括向量s及其特征屬性向量矩陣F，最大化式(13)中的3 種信息量來對參數進行優化，最終目標函數為下：

式中， λE， λI和 λJ是訓練參數。

分別計算3 種信息量的交叉熵，外部信息量I(hi;s) 對 應的交叉熵LE為：

內部信息量I(hi;fi) 對 應的交叉熵LI為：

聯合信息量I(hi;s,fi) 對 應的交叉熵LJ為：

式中，hi和分別是圖G的正節點嵌入和負節點嵌入。

同時，對于聯合信息量，去除了在外部和內部信息量中所捕獲的信息，因此僅對屬性向量取反。

DE，DI，DJ分別是3 種表示對分數的鑒別器，本文參考HDMI，應用了一個簡單的雙線性評分函數：

4 實驗與分析

4.1 實驗數據集

為了研究符號網絡中的學習表示，選取了4 個真實的符號網絡數據集進行實驗，即Bitcoin-Alpha，Bitcoin-OTC[40-41]，Slashdot[42]和New Guinea，表1列出了相關數據集的統計信息。

表1 實驗數據集統計信息

Bitcoin-Alpha 和Bitcoin-OTC 數據集都來自支持比特幣消費的開放市場，由于比特幣賬戶的匿名機制，網站出于安全考慮建立了在線信任網絡，用戶可以選擇對他人信任或不信任。Slashdot 是一個技術新聞網站，用戶之間可以創建雙向的好友或敵人關系，代表他們對彼此之間的態度。New Guinea是一個擁有16 個節點的數據集，表示新幾內亞中部高地16 個部落之間的關系。

以上4 個數據集，都是符號網絡研究領域的經典數據集，比較具有代表性。對于這些數據集中的網絡，本文忽略其中的鏈接方向，統一將其視為無向網絡進行研究。

4.2 鏈接符號預測描述

鏈路符號預測問題，即給定符號網絡中存在的一組鏈接，將其排除在訓練集之外的同時，希望能預測出它們在節點對之間的符號正負性。

為此，訓練了一個二分類器，該分類器根據一對節點的輸入特征集來預測其對應的符號 (本文使用邏輯回歸模型)。本文將兩個節點的最終嵌入向量直接相連來作為模型的輸入，并利用訓練數據中邊的標簽對模型進行訓練。鑒于數據集中正鏈接數遠多于負鏈接數，同時使用F1 與AUC 兩種指標來評估算法的效果，更高的F1 及AUC 都意味著更好的性能。對于每個數據集，隨機選擇50%的數據作為測試集，其余50%作為訓練集。

4.3 鏈路符號預測效果分析

為了驗證本文提出算法的有效性，選擇了DeepWalk[19]、LINE[24]、SNEA[29]、SGCN[28]、SDGNN[30]這5 個算法，來與SNSH 算法在鏈路符號預測任務上進行對比實驗。在評估SNSH 算法的性能時，將局部符號信息嵌入和高階互信息嵌入拼接以作為線性模型的輸入特征，另外，測試了僅考慮其中一種額外信息量時模型的效果，分別為SNSH-E、SNSH-I、SNSH-J，其實驗結果如表2 和表3 所示。在該部分，選取Bitcoin-Alpha、Bitcoin-OTC 和Slashdot這3 個數據集，用以進行實驗效果的分析對比。

表2 F1 衡量的鏈路符號預測任務算法效果對比

F1 分數是用來衡量二分類模型精確度的常用指標，是模型精準率和召回率的調和平均，由于真實符號網絡中絕大部分都是正向邊，因此所有算法得到的F1 分數都較高，但本文算法還是在所有數據集上取得了最好的效果。

在AUC 指標上，SNSH 同樣獲得了最好的性能。同時可以看到，針對3 個中大型符號網絡數據集，SNSH 算法的實驗結果穩定，F1 指標分別為0.980、0.976、0.981，AUC 指 標 分 別 為0.921、0.916、0.871，顯示了算法良好的穩健性。

實驗表明，本文方法在所有指標與數據集上取得了最佳的效果。并且，僅考慮單一信息量的SNSH模型也取得了超過現有算法的效果。這證明本文選取的信息量，能夠有效提取到真實網絡中的額外信息。SNSH 算法能高效地擬合真實符號網絡中的信息，從而得到有效的向量表示。

4.4 算法合理性分析

為了衡量算法對網絡真實結構的擬合效果，接下來進行驗證分析SNSH 學習的嵌入空間是否遵循結構平衡理論的原理。

分別使用LINE、SGCN 與SNSH 算法對New Guinea 網絡的拓撲結構進行嵌入來進行效果分析。具體來說，分別將網絡作為算法的輸入，經過訓練得到了數據集在網絡嵌入后的二維表示，其繪制結果分別如圖4、圖5、圖6 所示。

圖4 LINE 二維嵌入效果示意圖

圖5 SGCN 二維嵌入效果示意圖

在示意圖中，網絡中的正邊用加粗表示，負邊用虛線表示。在由LINE 算法得到的圖4 中，節點分布雜亂無序，不符合符號網絡的特征。相對而言，從考慮了符號網絡特性的SGCN 算法與SNSH算法得到的圖5 和圖6 可以看出，代表正關系的線條普遍較短，代表負關系的線條普遍較長。這表明具有正邊關系的節點在二維空間上是接近的，而具有負邊關系的節點在二維空間上是疏遠的，更符合符號社會網絡的特征，且能與社會結構平衡理論的觀點相印證，即節點的“朋友”比節點的“敵人”更近。

在圖5 和圖6 的對比中，由SNSH 算法得到的圖6 擁有更清晰合理的網絡節點布局，在部分節點上優于SGCN?？梢哉f，SNSH 算法更好地擬合了數據集的真實結構，這體現了算法的合理性與解釋性。因此，SNSH 所學習到的嵌入是符合結構平衡理論和符號網絡真實情況的。本文使用的實驗數據、相關源代碼和算法的描述等內容詳見鏈接：https://github.com/amoius/SNSH。

5 結 束 語

針對現有網絡表示學習領域中符號嵌入方法的缺失與嵌入深度的局限性，本文提出了一種基于結構平衡理論與高階互信息的符號網絡表示學習方法SNSH，來對符號網絡中的隱藏信息進行更深層的挖掘。在不影響甚至提高準確率的情況下，對符號網絡的內部、外部及聯合信息進行了捕捉，從而得到符合符號網絡特性的節點嵌入。在3 個真實數據集上進行了鏈路符號預測性能的對比實驗，并在New Guinea 數據集上進行了可視化實驗，驗證了本文所提模型具有較高的有效性與合理性。未來計劃將算法拓展到復合符號網絡表示學習等問題的研究中。