主題關注網絡的表示學習

郭景峰，董 慧*，張庭瑋，陳 曉

（1.燕山大學信息科學與工程學院，河北秦皇島066004；2.河北省計算機虛擬技術與系統集成重點實驗室，河北秦皇島066004；3.河北科技師范學院網絡技術中心，河北秦皇島066004）

0 引言

鄰接矩陣作為網絡最直觀的表現形式，其運算的時間復雜度和存儲的空間復雜度均較高，使得很多現有算法無法應用到大規模網絡中。針對大規模網絡的分析迫切需要一種合理、高效的網絡表示方式，因此，網絡表示學習成為近年來的研究熱點。

網絡表示學習［1］與傳統的基于鄰接矩陣的網絡分析方法不同，它結合網絡結構和語義等特點學習網絡潛在、低維、稠密的嵌入向量空間表示。由于網絡嵌入向量很容易被機器學習算法處理，因而受到學術界和產業界的廣泛關注，也有效地運用到節點分類、聚類、鏈接預測等任務中。

社會網絡依據包含的節點和邊的類型是否相同被劃分為兩類：同質網絡和異質網絡。目前，同質網絡表示學習方面的方法較多且比較深入；而異質網絡表示學習方面的方法大致分為基于矩陣分解的方法［2］、基于自定義損失函數的方法［3-4］和基于神經網絡的方法［5-7］三類。其中，基于神經網絡的方法［5］中涉及一種基于轉移概率模型的隨機游走算法和skipgram 模型結合來學習異質網絡中節點向量表示的方法。然而，此方法中轉移概率模型的定義大多只考慮網絡中的基本連接關系（如節點間的直接連接關系），僅僅保持一階鄰近性，無法捕捉全局網絡結構。針對上述問題，本文主要基于異質網絡的子網絡——主題關注網絡［8-10］進行表示學習的相關研究。如圖1 所示，該網絡由兩類節點和邊構成，其中，ui和tk分別表示用戶和主題節點。針對異質網絡中節點和邊之間結構和語義等各方面的特點，運用集對分析理論中的同異反（確定與不確定）思想，提出了基于主題關注網絡的表示學習（Topic-Attention Network Embedding，TANE）算法。主要內容如下：

1）提出一種基于集對分析理論構建轉移概率模型的方法。該模型針對主題關注網絡中4 階［11］范圍內兩類節點（用戶和主題）間連接關系中的幾種情況，采用集對分析理論中同異反思想將主題關注網絡刻畫為一個同異反（確定與不確定）系統，構建節點間的轉移概率模型。

2）提出一種基于用戶和主題節點的游走（User Topicwalk，UT-walk）算法。該算法基于用戶到用戶、用戶與主題之間的轉移概率給出隨機游走策略，實現兩類節點間靈活的游走，得到游走序列，并通過訓練該序列得到高質量的網絡嵌入向量空間表示。

3）在兩個數據集上對本文提出的算法進行了實驗，利用K-means++聚類算法進行社區發現，選取模塊度作為評價指標，實驗結果驗證了本文算法的有效性，聚類結果計算出的模塊度相對較高。

圖1 主題關注網絡Fig.1 Topic-attention network

1 相關工作

隨著社交網絡用戶的迅速增長使得傳統的網絡表示方法遇到瓶頸，結合深度學習的網絡表示方法逐漸興起。

DeepWalk 算法［12］首次將深度學習中的技術引入到同質網絡表示學習中，該算法運用Word2vec［13］模型的思想將節點視為單詞、隨機游走序列視為句子，訓練得到網絡的嵌入向量空間表示，在多標簽分類任務上證明了其有效性。Node2vec算法［14］結合廣度優先遍歷（Breadth First Search，BFS）和深度優先遍歷（Depth First Search，DFS）搜索算法，同時考慮到局部和全局信息，改善了DeepWalk 算法中的隨機游走策略；LINE（Large-scale Information Network Embedding）算法［15］通過不直接相連的兩個節點的鄰居刻畫二階相似度，對Deepwalk的一階近鄰稀疏問題作了改進。Node2vec 和LINE 這兩個算法較Deepwalk 算法在多標簽分類任務方面的結果明顯提高。保持Motif 結構的網絡表示學習（Motif-Preserving Network Embedding，MPNE）算法［16］結合Motif 結構進行高階的網絡表示學習，在多標簽分類任務上取得了更好的結果。SDNE（Structural Deep Network Embedding）算法［17］結合神經網絡模型來捕捉網絡中高度非線性的關系，最終將隱層權重作為網絡的嵌入表示，在鏈接預測任務上得到了突出的實驗結果。

異質網絡表示學習研究從PTE（Predictive Text Embedding）［3］算法逐漸起步，該算法是將predictive 的信息在最后的embedding 體現出來，但不像卷積神經網絡（Convolutional Neural Network，CNN）或 循 環 神 經 網 絡（Recurrent Neural Network，RNN）模型直接嵌套一個復雜的預測模型；PME（Projected Metric Embedding）算法［4］使用度量學習方法同時捕捉網絡中的一階和二階關系，在對象、關系空間分別學習節點、關系的向量表示；metapath2vec 和metapath2vec++算法［5］均基于DeepWalk 的思想，利用元路徑指導隨機游走，并用異質的skip-gram 模型進行訓練得到網絡的嵌入向量空間表示；HIN2vec 算法［6］結合神經網絡模型，在得到網絡的嵌入向量空間表示的同時還學到了關系（元路徑）的表示；DVNE（Deep Variational Network Embedding）算法［7］利用神經網絡模型結合Wasserstein距離改變了度量兩個分布之間相似性的方法，使其既能滿足三角不等式，又能在無向圖中很好地保持鄰近性的傳遞性。以上算法在多標簽分類、聚類和鏈接預測等網絡分析任務方面取得了較好的實驗效果。目前，在基于元路徑［18］隨機游走策略的異質網絡表示學習中帶偏置的隨機游走方式限制條件較多，因此，有必要針對異質網絡表示學習探究新的理論和方法。

2 主題關注網絡

主題關注網絡［10］被定義為一個二元組G=（V，E），其中：V={U，T}，U={u1，u2，…，un}表示用戶節點集，T=｛t1，t2，…，tm｝表 示 主 題 節 點 集；E=｛EUU，EUT｝表 示 邊 集，其 中，EUU={(ui，uj)|ui，uj∈U}表示用戶與用戶間的關系，EUT=｛（ui，tk）|ui∈U，tk∈T｝表示用戶與主題間的關系。

在主題關注網絡中，N(ui)1=NU(ui)1∪NT(ui)1和N(ui)2=NU(ui)2∪NT(ui)2分別表示節點ui的1 級和2 級鄰居集（包含用戶鄰居集NU(ui)m和主題鄰居集NT(ui)m，m=1，2）；CN(ui，uj)1=CNU(ui，uj)1∪CNT(ui，uj)1和CN(ui，uj)2=分 別 表 示 N(ui)1∩N(uj)1和N(ui)2∩N(uj)2；和CN(ui，uj)2∩1=CNU(ui，uj)2∩1∪CNT(ui，uj)2∩1分 別 表 示N(ui)1∩N(uj)2和N(ui)2∩N(uj)1，其他相關定義詳見文獻［10］。該網絡是融合了社交關系和興趣愛好的模型，節點之間的邊具有明顯的語義特征。

3 基于主題關注網絡的表示學習算法

3.1 基于集對分析理論的主題關注網絡建模

集對分析理論［19］的核心思想是將事物之間的聯系看成是一個系統，簡稱為同異反（確定與不確定）系統。其中，確定性包含同和反，通常指事物的同一和對立兩個方面，在此僅考慮同一方面；不確定性為異，通常指事物宏觀和微觀方面的影響因素。采用該思想構建主題關注網絡模型的關鍵即為構建節點間的確定和不確定關系。

主題關注網絡包含用戶和主題兩類節點，以及用戶-用戶、用戶-主題、主題-用戶三種節點間關系，基于該網絡的拓撲結構，將兩個用戶節點通過與其直接相連的節點建立的關系視為確定關系，如用戶間如果擁有共同的朋友或興趣愛好更容易成為朋友；將兩個用戶節點通過與其間接相連的節點建立的關系視為不確定性關系，如用戶間分別通過其朋友分享共同的興趣愛好成為朋友的不確定性較大，但在一定條件下可轉化為確定性關系。如圖2 所示，將（ui，uj）、（ui，tk）、（tk，ui）三種節點間二階范圍內的連接關系作為確定部分，其他情況作為不確定部分建模。

圖2 建模涉及的節點間連接情況Fig.2 Connections between nodes involved in modeling

3.2 轉移概率模型

3.2.1 相關定義

傳統同質社會網絡中基于轉移概率模型進行網絡分析已經結合BFS 和DFS 等方法考慮到節點2 階范圍內的鄰居，但無法準確捕捉全局網絡結構。基于現實網絡的多樣性（如網絡中包括多種類型的節點和邊）及網絡關系的復雜性（如朋友間通過共同的興趣愛好建立聯系）在主題關注網絡中全面準確地定義轉移概率模型作為研究重點。

針對圖2 主題關注網絡中兩類節點間的關系，融合網絡結構、主題偏好及確定與不確定性思想構建轉移概率模型，具體定義如下。

定義1用戶到用戶的轉移概率。給定主題關注網絡G=(V，E)，?ui，uj∈U，tk∈T，考 慮 NU(ui)1、CN(ui，uj)1、CNT(ui，uj)1∩2和CNT(ui，uj)2∩1以及CNT(ui，uj)2，用戶到用戶的轉移概率記為P(uj|ui)，如式（1）所示。

其中：Pij(1)表示兩個用戶節點是否直接相連，如式（2）所示。

其中：di表示節點ui的度；S起標記作用，S=1表示兩個節點間有直接連接關系，否則S=0。

Pij(2)表示兩個用戶節點通過共同1 級鄰居建立連接關系，如式（3）所示。

Pij（4）表示兩個用戶節點通過共同的2 級主題建立連接關系，如式（6）所示；

其 中：α、β、γ1、γ2和δ 分 別 表 示CNT(ui，uj)1∩2和CNT（ui，uj）2∩1以及CNT（ui，uj）2所占的權重系數，且α+β+γ1+γ2+δ=1；χ1和χ2分別表示兩個用戶節點通過CN(ui，uj)1建立連接關系時，兩個節點共同的用戶和主題所占的權重系數，且χ1+χ2=1。

定義2用戶到主題的轉移概率。給定主題關注網絡G=（V，E），?ui，up∈U，tk∈T，考慮NT（ui）1、CNU（ui，tk）1，用戶到主題的轉移概率記為P(tk|ui)，如式（7）所示。

其中：Pik（1）表示用戶節點和主題節點是否直接相連，計算方法同式（2）；Pik（2）表示用戶節點與主題節點通過CNU（ui，tk）1建立連接關系，計算方法同式（3）；ε、θ 分別表示NT（ui）1和CNU（ui，tk）1所占的權重系數，且ε+θ=1。

定義3主題到用戶的轉移概率。給定主題關注網絡G=(V，E)，?ui，uj∈U，tk∈T，考慮NU(tk)1，主題到用戶的轉移概率記為P(ui|tk)，如式（8）所示。

其中：Pki（1）表示主題節點和用戶節點是否直接相連，計算方法同式（2）。

3.2.2 實例

為了更加直觀地理解上述定義，利用圖1 中的(u1，u4)、(u5，t3)、(t3，u5)分別給出上述定義的計算過程。以節點u1、u4為研究對象，NT(u1)1={t2}，NU(u1)1={u2，u4，u5}，NT(u4)1={t3}，NU(u4)1={u1，u2，u3，u5，u6}。(u1，u4)∈EUU，即S=1；CNT(u1，u4)1=，即|CNT(u1，u4)1|=0，CNU(u1，u4)1={u2，u5}，即|CNU(u1，u4)1|=2；同理，節點u1和u4的其他鄰居集分別為CNT(u1，u4)1∩2={t2}、CNT(u1，u4)2∩1={t3}和CNT（u1，u4)2={t1}，即 |CNT(u1，u4)1∩2|=1、|CNT(u1，u4)2∩1|=1 和|CNT(u1，u4)2|=1。因 此，節 點u1到u4的 轉 移 概 率 為同 理 可 得(u5，t3)和(t3，u5)的鄰居情況，如表1 所示，計算轉移概率分別為

3.3 TANE算法框架

TANE 算法的核心思想是將上述定義得到的轉移概率模型運用到隨機游走算法得到隨機游走序列，通過訓練該序列，得到兩類節點的向量表示。根據不同的需求利用兩類節點的向量表示，如運用網絡中用戶節點的向量表示進行社區發現任務，或是根據網絡中主題節點的分布情況對社區內用戶進行合理化推薦等。

表1 節點對間的鄰居數量Tab.1 Number of neighbors between node pairs

3.3.1 UT-walk算法

基于上述三種轉移概率模型，提出了基于主題關注網絡的隨機游走算法，如算法1 所示。在算法1 中，第1）行表示初始化隨機游走路徑；第2）行表示起始節點的選取是隨機的，可為用戶或主題節點；第3）～5）行分別表示在游走路徑長度L范圍內對當前節點（vcurrent）的選取、計算給定vcurrent的前提下轉移到下一個節點的轉移概率以及下一個節點的選取方法。

在主題關注網絡中，結合轉移概率模型選取下一個節點主要有兩種策略：1）若vcurrent是用戶節點，則vnext是用戶或主題節點；2）若vcurrent是主題節點，則vnext一定為用戶節點。vnext的選取通過帶權重（即轉移概率）的非均勻采樣實現，更傾向于轉移概率大（與vcurrent共同用戶和主題數量多）的節點。

算法1 UT-walk。

輸入 G=（V，E），隨機給定一個起始節點u，路徑長度L，轉移概率P；

輸出 包含兩類節點的隨機游走序列。

以圖1 中u1和t3為例說明上述算法，轉移概率模型的參數設置與表7中Karate 一致，與其他節點的轉移概率如表2所示。由表2可知，如果以u1作為當前節點vcurrent，則下一個節點vnext的選取更傾向于u2、u4、t1、t2轉移概率相對較大的節點。由P（u5∣u1）＜P（u6∣u1）看出，節點間轉移概率大不是因為節點間存在直接連接關系，還有可能是間接連接關系豐富。綜上，隨機游走下一個節點vnext的選取要考慮節點的間接連接關系。

表2 分別以節點u1和t3作為vcurrent的轉移概率Tab.2 Transition probability with node u1 and t3 as vcurrent

3.3.2 TANE算法

主題關注網絡表示學習（TANE）算法結合了轉移概率模型和UT-walk 算法，如算法2 所示。在算法2 中，第1）行表示初始化隨機游走路徑集合；第2）～8）行分別表示在每個節點作為起始節點次數n 的前提下，通過UT-walk 算法對起始節點、游走路徑長度等參數進行設置，運用轉移概率模型得到多條相對高質量的隨機游走序列；第9）行使用Word2vec模型對隨機游走序列進行訓練，得到主題關注網絡的嵌入向量空間Φ。

算法2 TANE。

輸入 G=（V，E），上下文窗口大小w，每個節點作為起始節點的次數n，生成的向量空間維度d，路徑長度L，轉移概率P；

輸出 節點的向量空間表示矩陣Φ ∈R∣V∣×d。

4 實驗與結果分析

4.1 實驗設置

4.1.1 數據集和對比實驗

實驗選取了兩個基準數據集和五個經典算法，具體介紹如下。

1）Zachary’s Karate club數據集是社交網絡分析領域中的經典數據集，由34個節點和78條邊組成。

2）豆瓣數據集是一個通過爬蟲程序抓取的包含用戶間的關注屬性和電影評論屬性兩部分信息的網絡。對數據集進行處理，過濾掉用戶對電影評分在3 分以下的信息，最終網絡中有2 289 個節點（2 253 個用戶+36 個主題）和70 489 條邊（34 580 條用戶與用戶之間的邊+35 909 條用戶與主題之間的邊）。

5 個經典算法分別為：DeepWalk、Node2vec、MPNE、PTE和metapath2vec。為了使實驗結果更有說服力，對比算法中的參數均與原論文一致，維度設置如表3所示。

表3 各算法的向量維度設置Tab.3 Vector dimension settings of different algorithms

4.1.2 評價指標

實驗選擇節點聚類作為網絡分析任務，選取模塊度（Modularity，Q）作為評價指標，如式（9）所示，Q ∈[-1/2，1)，Q越大，則表明社區劃分質量越好。

需要說明的是，該實驗是為了證明主題節點對社交關系穩定的重要性，主題僅起橋梁的作用，聚類分析以及計算Q時去掉網絡中的主題節點。

4.2 結果與分析

實驗主要分為三部分：1）驗證主題對轉移概率和向量表示的影響；2）驗證TANE 算法的正確性和合理性；3）參數敏感性分析。

4.2.1 基于Karate網絡的實驗

Karate 網絡是一個無主題的真實網絡，針對該網絡（如圖3（a）所示）及對其添加主題（如圖3（b）所示）兩種情況進行比較，以分析主題對網絡表示學習的影響。

圖3 Karate網絡示意圖Fig.3 Schematic diagram of Karate network

運用DeepWalk算法和TANE算法得到Karate網絡的兩種嵌入向量空間表示，通過計算節點間向量表示的歐氏距離展開分析。由于考慮4階范圍內節點間的關系，Karate網絡較稠密，4階鄰居僅僅涉及1個節點，因此，圖4（a）、（b）、（c）分別展示兩個算法下34 個節點與每個節點一階、二階和三階鄰居間向量表示的歐氏距離變化趨勢。

從圖4 中可以看出，三種情況下歐氏距離變化趨勢基本一致。由于轉移概率模型定義時考慮的范圍不同，使得Karate 網絡中整體節點間向量表示的歐氏距離減小了，有些節點間向量表示的距離的波動情況相比DeepWalk 算法產生了偏差。為了分析產生偏差的原因，以一階鄰居較多的u1、u34節點和容易出現分歧的u3、u10節點為例，將圖中部分區域放大，如圖5所示。vnext的選取通過帶權重（即轉移概率）的非均勻采樣實現，節點間轉移概率越接近，得到節點的向量表示越相似，節點間向量表示的距離越小，圖中折線的波動情況反映了此現象。圖5 中用加粗線標記波動比較明顯的情況，以圖5（a）中加粗線標記為例詳細分析原因。TANE算法中，u1到標記范圍內節點的轉移概率如表4 所示，從表中可以看出，P（u1∣u10）最小，其他情況的轉移概率相差不大，從而dist（u1，u10）最大，即u10與x軸間的垂直距離最大，所以，虛線標記的折線段除u10處波動明顯外其余節點相對平穩；而DeepWalk 算法中，轉移概率模型定義僅考慮了一階鄰居，無法根據轉移概率對間接連接關系進行詳細分析。綜上分析，TANE 算法符合網絡表示學習的核心思想。

圖4 在兩種算法下各階鄰居間歐氏距離的比較Fig.4 Comparison of Euclidean distance between neighbors in two algorithms

圖5 在兩種算法下4個節點與其他節點間歐氏距離的比較Fig.5 Comparison of Euclidean distance between four nodes and other nodes in two algorithms

4.2.2 基于聚類算法的分析

經過上述分析，在豆瓣網絡上采用K-means++算法完成聚類分析任務。經過比較，選取肘部法則確定聚類簇數K，其核心指標是誤差平方和（Sum of the Squared Errors，SSE），如式（10）所示；核心思想是隨著聚類簇數K 的增大，SSE 值會逐漸減小并趨于平緩，拐點對應的K 值就是數據的真實聚類簇數。

首先，運用肘部法則確定Karate 網絡的K 值，如圖6（a）所示，拐點為4，與DeepWalk 論文中運用Modularity 算法聚成4類時Q值達到最大一致。因此，該方法具有一定的合理性。

表4 u1與圖5（a）中加粗線段范圍內節點間的轉移概率Tab.4 Transition probability between u1 and nodes in the range of bold line segment in Fig.5（a）

然后，運用肘部法則確定豆瓣網絡的K 值，如圖6（b）所示，為了實驗的準確性，K 在拐點范圍內取值，即K∈［5，13］。初始聚類中心的選擇具有隨機性，結果有小幅度變化，針對每個K值做了15次實驗，取平均值作為最終結果。如表5所示，在K的取值范圍內，TANE算法都取得了較好的結果。

綜上，TANE 算法劃分社區結構考慮了網絡的結構和語義等方面的信息，具有實際應用價值，如在推薦系統中進行合理化、個性化推薦。

圖6 用肘部法則分別確定Karate和豆瓣網絡的聚類簇數Fig.6 Numbers of clusters of Karate and Douban networks determined by elbow rule

表5 豆瓣數據集上各算法獲得的Q值對比Tab.5 Comparison of Q values on Douban dataset by different algorithms

4.3 參數敏感性分析

TANE 算法中涉及到多個參數。首先，對轉移概率中的參數設置分5 種情況進行分析，如表6 所示：第4、5 組參數設置得到的Q值相對較小，因為網絡中主題節點稀疏，在很大程度上考慮主題節點建立的聯系嚴重影響提取網絡中的信息；第1、2、3組參數設置得到的Q值相對較大，由Q2＞Q1，Q1＞Q3可以看出，在權衡各部分權重的前提下，基于兩類節點間的關系進行建模有利于網絡表示學習。最終兩個數據集轉移概率模型中的參數設置如表7 所示，兩個數據集數據量不同，參數設置略有差異。

表6 轉移概率模型參數分析Tab.6 Parameters analysis of transition probability model

其次，選用豆瓣數據集對Word2vec 模型中涉及幾個參數進行分析。如圖7 所示，Word2vec 模型中的有些參數對實驗結果的影響不大，當向量維度d 取64、上下文窗口ω 取5 時，TANE 算法的表現較好。網絡中節點作為起始節點的次數n、路徑長度L 對實驗結果影響較明顯，尤其是參數L，當L＞40時，Q值處于下降趨勢，算法性能下降。

綜上，TANE 算法中轉移概率模型參數選取時根據網絡中兩類節點的稀疏情況來權衡建模時各部分的占比；Word2vec 模型中參數選取時結合復雜度和算法性能兩方面來考慮。

圖7 Word2vec模型參數敏感性分析Fig.7 Parameters sensitivity analysis of Word2vec model

表7 轉移概率模型參數設置Tab.7 Parameters setting of transition probability model

5 結語

采用集對分析理論中確定與不確定思想，給出轉移概率模型，并將其運用到隨機游走算法，得到了相對高質量的隨機游走序列；再對游走序列進行訓練，得到了主題關注網絡的嵌入向量空間表示。實驗結果表明，在豆瓣數據集上與5 個經典算法相比，當劃分社區個數為5～13 時，TANE 算法得到的Q值均有不同幅度的提高，但數據集的稀疏性使得Q 值變化并不十分明顯；當豆瓣數據集上K=13 時，TANE 算法較metapath2vec 算法的Q 值提高了近5%。綜上，從結構和語義方面分析網絡，可以更全面地捕捉網絡中的信息，綜合合理性以及實驗結果來考慮，本文提出的TANE 算法取得了較好的表現。

接下來，在TANE 算法思想的基礎上增大數據規模考慮異質網絡的動態性和復雜性進行表示學習的相關研究是我們進一步的工作重點。