基于集合約束的異質超網絡表示學習

劉貞國，朱 宇，王曉英，黃建強，曹騰飛

（青海大學 計算機技術與應用系，西寧 810000）

0 概述

網絡表示學習［1］也稱為網絡嵌入，其將網絡中的每個節點映射到一個低維的向量表示空間，學習到的節點表示向量可以被用于節點分類［2-4］、鏈接預測［5-7］、社區檢測［8-9］等網絡分析任務。

現有的網絡表示學習方法大多針對普通網絡，其中，節點之間的關系是成對關系，即每條邊只連接一對節點，而在現實生活中的數據對象之間的關系通常比較復雜，而且不一定是成對關系。例如，吉姆參加了一場在北京舉行的學術會議，就形成了一種元組關系<吉姆，北京，會議>。捕獲這種元組關系的網絡通常稱為超網絡，其中，元組關系被看作超邊。與普通網絡相比，超網絡逐漸變得更受歡迎，如何從超網絡結構中挖掘有用信息變得十分有意義。然而，現有的大多數網絡表示學習方法不能直接應用于超網絡。鑒于上述事實，團擴展、星型擴展［10］和BTR［11］將超邊分解為對邊，然后學習節點表示，但是該類方法在超網絡展開過程中會丟失超邊信息。Hyper2vec［12］、HPSG［13］沒有分解超邊，而是基于超路徑游走序列來捕獲節點之間的成對關系，但是它們沒有很好地捕獲節點之間的元組關系。HPHG［13］和DHNE［14］可以很好地捕獲節點之間的成對關系和元組關系，但是它們受限于固定大小和固定類型的異質超邊。Hyper-SAGNN［15］相比于DHNE 和HPHG具有更好的泛化性，對輸入元組的節點數目大小和類型沒有要求，但是由于該方法構造了很多中間特征，其模型計算復雜度較高。

受到上述方法的啟發，將結構復雜的超網絡轉化為結構簡單的普通網絡，以便于使用普通網絡表示方法學習節點表示向量，同時考慮節點之間的成對關系和元組關系。本文提出一種基于集合約束的異質超網絡表示學習方法HRSC。該方法通過結合團擴展和星型擴展策略將異質超網絡轉化為異質網絡［16］，采用感知節點語義相關性的元路徑游走算法來捕獲異質節點之間的語義信息，并根據集合約束機制，在基于拓撲派生目標函數的模型上融入超邊。

1 相關工作

超網絡作為一種特殊的圖結構化數據，逐漸受到研究者的廣泛研究。團擴展、星型擴展［10］和BTR［11］是超網絡學習的傳統主流方法，它們將譜理論應用到超網絡中，通過嚴密的數理推導來求解目標函數的最優解，其中，團擴展使得超邊內部節點連接成完全圖，即使得超邊內部節點之間兩兩相連。星型擴展通過引入超邊節點，使得超邊內部節點與超邊節點相連。BTR 使用超邊內部距離最遠的兩個節點的連接邊代替超邊本身，大幅降低了展開過程的時間復雜度，但是當其應用于節點差異度較大的超網絡時會丟失較多的結構信息。Hyper2vec［12］在拉普拉斯算子上加入導向函數，提出基于超邊的有偏隨機游走，使其能夠適應不同的網絡結構，從而更好地保留超網絡結構信息。HPSG［13］基于超邊的隨機游走來構造節點的異質鄰域，然后通過Skip-gram模型學習節點表示向量。DHNE［14］直接對超邊進行建模，但該方法局限于固定大小的異質超邊。HPHG［13］基于超邊的隨機游走節點序列上訓練Hyper-gram 模型，更好地保留了超網絡結構，實現了優于DHNE 的性能，但是其只適用于均勻超網絡，很難擴展到任意規模的超網絡。Hyper-SAGNN［15］使用自注意力機制對超圖信息進行聚合，結合節點動態特征和靜態特征對節點進行學習，對輸入元組的節點類型、數目沒有要求，相比DHNE 和HPHG 具有更好的泛化性，但由于該方法構造了很多中間特征，其模型計算復雜度較高。Event2vec［17］將多個對象之間關系建模為事件，通過在嵌入空間中保留事件一階和二階近似性學習節點表示向量。

與上述方法不同，HRSC 不僅可以捕獲節點之間的成對關系和元組關系，而且可以平衡優化節點之間的成對關系和元組關系，以便于獲得高質量的節點表示向量。在3 個不同類型的超網絡數據集上的實驗結果表明，HRSC 方法在鏈接預測和超網絡重建任務中表現優異。

2 問題定義

超網絡通常被抽象為超圖H=(V,E)，其中，V=是T種類型的節點集合，Vt表示第t種類型的節點集合是超邊集合。如果對于任意ei?E均有|ei|=k，則稱H為k-均勻超圖；如果k=2，則超網絡退化為傳統網絡；如果T≥2，則超網絡定義為異質超網絡。如圖1 所示，給定一個異質超圖H=(V,E)，其中，E={e1={a1,b1,c1},e2={a2,b2,c2},e3={a1,b1,c2}}，V={a1,b1,c1,a2,b2,c2}，a、b、c表示節點的類型。

圖1 異質超圖Fig.1 Heterogeneous hypergraph

定義1（異質超網絡表示學習）給定一個異質超網絡H=(V,E)。異質超網絡表示學習為每個節點vi?V學習一個低維向量rvi?Rk，其中，k?|V|。它的目的是使得學習到的向量顯式地保留異質超網絡結構信息，并且異質超網絡結構中相鄰的節點在向量表示空間中也相鄰。

3 預備知識

文獻［18］提出分別通過團擴展和星型擴展將超圖轉化為2-截圖和關聯圖。受文獻［18］的啟發，文獻［19］提出將超圖轉換為2-截圖+關聯圖和感知節點語義相關性的元路徑游走方法。下面詳細介紹超圖轉換為2-截圖、關聯圖、2-截圖+關聯圖和感知節點語義相關性的元路徑游走。

3.1 超圖轉換為2-截圖、關聯圖與2-截圖+關聯圖的方法

超圖轉換為2-截圖、關聯圖與2-截圖+關聯圖方法如下：

1）2-截圖

超圖H=(V,E)的2-截圖（2-section graph）是滿足以下條件的圖S=(V',E')：

（1）V'=V，即S的節點 集合與H的節點集合相同。

（2）任意兩個不同的節點之間連一條邊，當且僅當它們同時與H的至少一條超邊關聯。

圖2 是圖1 超圖對應的2-截圖。

圖2 2-截圖Fig.2 2-section graph

2）關聯圖

超圖H=(V,E)的關聯圖是滿足以下條件的圖I=(V',E')：

（1）V'=V∪E，即將超圖H中的每條超邊看成一個節點，I的節點集合是H的節點集合和超邊集合的并集。

（2）vi?V和ei?E相鄰，當且僅當vi?ei。

圖3 為圖1 超圖對應的關聯圖，其中e節點代表超邊節點。

圖3 關聯圖Fig.3 Incidence graph

3）2-截圖+關聯圖

超圖H=(V,E)的2-截圖+關聯圖是滿足以下條件的圖I=(V',E')：

（1）V'=V∪E，即將超圖H中的每條超邊看成一個節點，I的節點集合是H的節點集合和超邊集合的并集。

（2）對于vi?V和ei?E，當且僅當vi?ei時，vi與ei相鄰；對于?vi,vj?ei，當且僅當vi和vj節點之間語義相關，vi和vj相鄰。

圖4 為圖1 超圖對應的關聯圖，其中，b1和c1、b1和c2、b2和c2節點之間語義相關。

圖4 2-截圖+關聯圖Fig.4 2-section graph+incidence graph

3.2 感知節點語義相關性的元路徑游走

在2-截圖+關聯圖G=(V,E)上的感知節點語義相關性的元路徑游走定義如下：

其中：Ri表示Vi和Vi+1類型節點之間存在語義相關；Re表示Vj和Vj+1類型節點之間通過超邊節點關聯；R=R1?????Ri?????Re?????Rl-1表 示V1和Vl類型節點之間的復合關系。與傳統隨機游走相比，采用感知節點語義相關性的元路徑游走獲取的異質節點序列，可以更好地保留超網絡中節點之間的元組關系和增強節點之間的成對關系。

4 HRSC 方法

HRSC 方法的框架如圖5 所示。該框架包括2 個主要部分：（a）基于拓撲派生目標函數的模型；（b）基于集合約束目標函數的模型。其中，Ev和θv分別表示嵌入矩陣和參數向量，ev和ew分別為v和w對應的向量，v和w分別表示目標節點和與目標節點關聯的超邊。

圖5 HRSC 框架Fig.5 HRSC framework

4.1 拓撲派生目標函數

采用基于感知節點語義相關性游走來獲取的異質節點序列C作為HRSC 方法的輸入，通過基于拓撲派生目標函數的模型來捕獲序列C上節點之間的成對關系。下面詳細介紹拓撲派生目標函數。

對于目標節點v?C，當v的上下文節點為c?context(v)時，將c視為正樣本，將非上下文節點Neg(v)視為負樣本。節點的標簽定義如下：

p(u|v)表示在已知目標節點v的條件下預測其上下文節點u概率。對于給定節點序列C，最大化拓撲派生目標函數如下：

對于每一個節點v，嵌入向量ev是v作為目標節點的表示向量，參數向量θv是v作為上下文節點時的表示向量，則p(u|v)定義如下：

通過最大化L1將超網絡拓撲結構融入到超網絡表示學習中來捕獲節點之間的成對關系。

4.2 集合約束目標函數

上述基于拓撲派生目標函數的模型僅采用近似于超圖的2-截圖+關聯圖作為輸入來學習節點表示向量，沒有充分地捕獲節點之間的元組關系，即超邊。為了更好地捕獲節點之間的元組關系，提出一種基于集合約束目標函數的模型，該模型將與節點關聯的超邊集合融入到超網絡表示學習中。下面詳細介紹集合約束目標函數。

對于目標節點v?C，w表示與目標節點關聯的超邊，Tv表示與目標節點關聯的超邊集合，如果將w看作節點，Tv也表示與目標節點v相關聯的節點集合。將目標節點v視為正樣本，對于w?Tv，NEG(w)表示目標節點v的負樣本子集。節點標簽定義如下：

對于目標節點v，通過集合約束機制，將與節點相關聯的超邊集合作為約束條件融入到節點的表示學習過程中。集合約束目標函數的計算公式如下：

通過最大化L2，將與節點相關聯的超邊集合融入到超網絡表示學習過程中來捕獲節點之間的元組關系。

4.3 聯合優化目標函數

通過聯合優化拓撲派生目標函數和集合約束目標函數，可以同時捕獲節點之間的成對關系和元組關系。與其他超網絡表示學習方法相比，HRSC 在2 個層次上進行了改進：1）在超網絡拓撲結構層次上，HRSC 捕獲了節點之間的成對關系；2）在節點-超邊層次上，HRSC 捕獲了節點之間的元組關系。通過上述改進，HRSC 有效地融合超邊到超網絡表示學習中。

為了便于計算，將拓撲派生函數L1和集合約束L2取對數后相加，并最大化聯合優化目標函數如下：

其中：β是平衡基于拓撲派生目標函數的模型和基于集合約束目標函數的模型的調和因子。為了便于推導，將L簡記為L(v,u,δ,w)，即：

通過使用隨機梯度上升（SGA）算法來優化目標函數L(v,u,δ,w)，給出L(v,u,δ,w)的4 種梯度。

首先，關于θu的梯度計算如下：

其中，λ是HRSC 方法的學習率；當L(u)=1 和L(u)=0時，分別更新正負樣本節點的參數向量。

其次，利用ev和θu的對稱性計算L(v,u,δ,w)關于ev的梯度如下：

因此，對θδ的更新公式如式（15）所示，當L(δ|v)=1 或L(δ|v)=0 時，分別更新正負樣本節點的參數向量。

最后，利用ew和θδ的對稱性計算L(v,u,δ,w)關于ew的梯度如下：

根據上述分析，HRSC 方法的具體描述如算法1所示。

算法1HRSC algorithm

4.4 復雜度分析

在算法1 中，基于拓撲派生目標函數的模型和基于集合約束目標函數的模型分別捕獲了節點之間的成對關系和元組關系，其時間復雜度如下：O(C?(context ? (Neg+1)+? (NEG+1))?2d?(|V|+|E|))，其中表示與v關聯的超邊集合的最大基數；Neg和NEG 分別表示拓撲派生目標函數和集合約束目標函數的負采樣樣本大小。由于|V|和|E|通常較大，因此HRSC 的時間復雜度大約為O(|V|+|E|)，接近于HPHG 和Event2vec 的時間 復雜度，高 于DHNE 的 時間復雜度。

5 實驗

5.1 數據集

為了全面評估本文提出方法的效果，本文使用3 個超網絡數據集，即藥物網絡、GPS 網絡和社會網絡。數據集的詳細統計如表1 所示。

表1 數據集統計Table 1 Dataset statistics

1）drug：該數據集來自FDA 不良事件報告系統（FAERS），包括提交給FDA 的不良事件和用藥錯誤報告的信息。元組關系（用戶，藥物，反應）被看作超邊來構建超網絡。

2）GPS［20］：該數據集描述了一個用戶在某個位置參加活動。元組關系（用戶，位置，活動）被看作超邊來構建超網絡。

3）MovieLens［21］：該數據 集描述 了來自 于MovieLens 的個人標記活動。元組關系（用戶，電影，標簽）被看作超邊來構建超網絡。

5.2 基線方法

基線方法主要有以下8 種：

1）deepwalk［22］將隨機游走獲取的節點序列作為Skip-gram 模型的輸入來獲得節點表示向量。

2）node2vec［23］采用有偏隨機游走策略學習節點表示向量。

3）metapath2vec［24］采用基于元路徑的隨機游走策略學習節點表示向量。

4）Coarsas2hvec［25］通過HIN 粗化和自避免短序列采樣過程捕獲異質網絡的豐富的信息，從而學習節點表示向量。

5）Hyper2vec［12］采用基于超邊的二階隨機游走策略學習節點表示向量。

6）HPSG［13］基于超路徑的隨機游走結合Skipgram 模型學習節點表示向量。

7）HPHG［13］基于超路徑的隨機游走結合Hypergram 模型學習節點表示向量。

8）Event2vec［17］通過學習事件嵌入來學習對象嵌入。

HRSC 方法基于2-截圖+關聯圖來捕獲節點之間的成對關系和元組關系來學習節點表示向量。

5.3 鏈接預測

本節在3 個超網絡數據集上進行鏈接預測實驗，通過AUC［26］值來評估HRSC 方法。實驗隨機選取80%的邊集作為訓練集，對于全部方法，取6 次AUC 平均值。以drug 數據集為例，HRSC 方法對于2-截圖、關聯圖分別采用方案φ1、φ2進行采樣，對于2-截圖+關聯圖采用感知節點語義相關性的元路徑游走方案φ3進行采樣［19］。鏈接預測結果如表2 所示。

表2 鏈接預測結果Table 2 Link prediction results %

由表2 可知，HRSC 方法在2-截圖、關聯圖、2-截圖+關聯圖上的AUC 值優于deepwalk、node2vec、metapath2vec、Coarsas2hvec 普通網絡學習方法。HRSC 方法在drug 和GPS 超網絡上的AUC 值優于超網絡表示學習方法Hyper2vec 和HPSG。原因是這兩個超網絡的內部節點之間的元組關系較強，因此特定地訓練節點之間成對關系的方法Hyper2vec和HPSG 表現不佳。HRSC 方法在MovieLens 超網絡上的AUC 值優于HPHG 和Event2vec，在drug 和GPS 超網絡上的AUC 值接近HPHG 和Event2vec。原因是MovieLens超網絡的內部節點之間的元組關系較弱，成對關系較強，因此特定地訓練成對關系的方法表現較好，比如Coarsas2hvec、Hyper2vec和HPSG。

5.4 超網絡重建

選取drug 和GPS 超網絡進行超網絡重建實驗。超網絡重建［13］的評估指標定義如式（18）所示：

其中：對重建超邊的元組相似性按照升序排序，ni=1表示第i個重建超邊存在于原超網絡中，否則ni=0；χ為重建的總超邊數；ρ為重建超邊的比率。

超網絡重建實驗如圖6 所示，HRSC 方法在drug和GPS 超網絡上的重建性能優于普通網絡表示學習方法deepwalk、node2vec、metapath2vec 和Coarsas2hvec。原因是HRSC 方法捕獲了節點之間元組關系，即超邊。超網絡表示學習方法Event2vec、Hyper2vec、HPSG 和HPHG 在較大重建超邊比率時，超網絡重建性能不佳，而HRSC 在各個比率的超邊重建中都表現出了穩定的性能，且HRSC 在GPS 超網絡上顯著優于其他基線方法，這表明了HRSC 方法的有效性和魯棒性。

圖6 超網絡重建Fig.6 Hypernetwork reconstruction

5.5 參數敏感度分析

參數β是一個平衡基于拓撲派生目標函數的模型和基于集合約束目標函數的模型的調和因子。當β=0時，HRSC 只能捕獲節點之間的成對關系。當0<β≤1時，HRSC 可以同時捕獲節點之間的成對關系和元組關系。設置0 ≤β≤1，取各個超邊重建比率的平均值AACC（ρ）。通過超網絡重建任務分析參數β的影響。

由圖7 可知，當β=0 時，HRSC 方法僅捕獲了節點之間的成對關系，沒有考慮節點之間的元組關系；隨著β的增大，節點之間的元組關系被融入到節點表示向量中，HRSC 方法分別在β=0.6 和β=0.7 時達到最大，表明元組關系的重要性在增強；繼續增大β，超網絡重建性能開始下降，表明成對關系的重要性在增強。

圖7 參數β 的敏感度分析Fig.7 Sensitivity analysis of parameter β

6 結束語

本文提出一種異質超網絡表示學習方法HRSC。該方法采用集合約束機制將超邊融入到超網絡表示學習中來學習高質量的節點表示向量。實驗 結果表明，HRSC 方法在drug、GPS、MovieLens 3 個超網絡上的平均性能均優于基線方法。由于超邊分解會帶來信息損失，下一步將不再分解超邊，而是在集合約束基礎上引入超路徑，以便于更好地處理異質超網絡。