今天給大家介紹加拿大蒙特利爾大學的著名學者唐建等人發表的一篇文章。作者在文章中針對現有的圖動力學模組化方法不能明确地捕捉到時間上的社群動态這一問題，提出了通過在軌迹上施加随機遊走來學習生成不斷發展的節點和社群表示的機率模型-GRADE。同時該模型還學習了通過過渡矩陣在時間步長之間進行更新的節點社群成員身份。實驗表明，GRADE在動态連結預測中達到或超過基線模型，在動态社群發現方面顯示出良好的性能，并且能識别出連貫且可解釋的不斷發展的社群。
1
介紹
由于在各種基于互動的網絡（例如社交和通信網絡，生物資訊學和關系知識圖）中有着廣泛的應用，基于圖結構資料的表示學習已經引起了機器學習界的極大興趣。開發無監督圖表示學習的方法具有很大的挑戰性，因為它需要在低維嵌入中彙總圖結構資訊，然後這些表示可用于例如節點分類，連結預測和社群發現的下遊任務。大多數無監督的圖表示學習方法僅專注于靜态非演化圖，而許多現實世界的網絡則表現出複雜的時間行為。為了解決對關系資料的時間模式進行編碼的挑戰，現有的動态圖嵌入方法廣泛關注于捕獲節點演化。盡管這些方法相對于動态任務的靜态基準而言取得了令人信服的結果，但它們并不适合捕獲像節點或社群叢集這樣的圖形級的演變結構。同時，在大規模腦網絡的時間組織中出現的進化節點簇模式在社交網絡中也引起了極大的興趣。
為了解決上述問題，作者提出了GRADE（圖形動态嵌入）-一種用于聯合學習演化節點和社群表示的機率生成模型。先前研究表明了在靜态表示中的圖表示學習模組化節點與社群之間互動的好處，以及諸如社群之類的高階圖結構可以增強對突發動态行為進行模組化的能力。是以，在GRADE中作者将在vGraph中提出的對節點-社群互動進行模組化的思想擴充到了動态案例。除此之外，作者假設社群的語義含義以及每個節點在社群中的比例随時間同時演變。遵循了一種動态主題模組化中引入的先前方法，通過在時間步長之間的表示之前假設随機遊走來編碼方法中的時間演變。作者還從社交網絡中汲取了靈感，通過引入特定于節點且随時間變化的過渡矩陣來随時間更新社群混合系數，顯式地為社群成員資格的動态模組化。作者通過變分推理來學習模型的參數，以最大化觀測資料的下限。
2
模型
GRADE GRADE是一種用于對動态圖中的邊生成過程進行模組化的機率方法，圖1為GRADE的盤子表示法。作者采用vGraph的方法将Gt的活動頂點集中的每個節點w表示為社群的混合，每個社群表示為節點上的多項式分布。每個時間步長t的連結鄰居生成如下：首先，作者從社群z〜p（z | w）上的條件先驗分布中采樣社群配置設定z。然後，根據配置設定的社群定義的社會環境，從節點生成分布c〜p（c | z）中提取鄰居。圖快照Gt的生成過程可以表示為：
其中θt和πt分别參數化了時間步長t處的多項式生成分布和先驗分布。在所提出的動态圖模型中，作者假設社群的語義含義以及節點的社群比例随時間而變化。這需要通過一組不斷發展的參數來捕獲基礎節點和社群分布的時間演變。GRADE通過使這些參數隐式依賴于不斷發展的節點和社群嵌入φ和β來實作這一目标。更具體地說，作者将社群和節點表示形式視為随機變量，并施加了一個簡單的狀态空間模型，該模型在時間步長之間随高斯噪聲而平滑地演化，如下所示：
盡管GRADE允許在每個時間步長出現節點的子集，但作者在每個時間步長都演化了完整頂點集V的嵌入。時間平滑度超參數γ和σ控制時間動态的速率。通過首先通過神經網絡轉換社群表示，然後通過softmax層映射輸出，來實作生成分布的參數化。為了發展節點的社群混合權重，作者觀察到使用者對社交網絡的興趣随時間而變化，英雌使用者可能會從一個社群轉移到另一個社群，其特點是在社群發展的更廣泛範圍内具有特定于使用者的行為。由于這些原因，作者使用過渡矩陣顯式地為社群過渡模組化。更具體地說，對于每個節點vi，我們通過K×K特定于節點的時變過渡矩陣Ati來更新社群混合權重πti，該矩陣作為節點嵌入的函數ψ生成：
圖1：Plate notation for GRADE
推論算法
3
實驗
作者根據最新的基準對動态連結預測和動态社群發現的任務來評估GRADE。此外，作者還提出了一種量化名額，以評估所學的不斷演化的社群的品質，并為定性評估提供可視化效果。作者使用基于DBLP，IMDb和Reddit資料集的三個離散時間動态網絡來評估所提出的方法
作者将GRADE與包含三種靜态方法和兩種動态方法的五個基準進行比較，靜态方法是：DeepWalk node2vec和vGraph，動态圖方法包括：DynamicTriad和DySAT。作者采用了動态連結預測和動态社群發現二個任務來評估相關模型。
在動态連結預測中，對于所有基線方法，在執行每種方法之後，作者使用節點表示之間的相似性度量（歐式距離或點積）作為連通性的預測名額。對于靜态方法，作者将訓練集中的所有觀察到的邊彙總在單個圖中，以生成節點嵌入，對于動态基線，使用最後訓練步驟的頂點表示。對于GRADE，作者訓練模型，并在測試時間步長推斷節點和社群表示的後驗分布，使用度量平均等級（MAR）評估動态連結預測性能。在動态社群發現中，作者通過在訓練時間步長上訓練模型來利用曆史資訊，并根據測試集中的邊緣來推斷非重疊社群，使用标準化互資訊（NMI）和子產品化來評估此任務的性能。此外，GRADE的一種新穎應用是預測社群規模的動态，通過推斷測試時間步長的社群表示形式（即每個社群的節點上的後多項式分布）并生成最可能節點的排名來證明這種能力，預測對給定社群具有高機率的頂點也應該是其結構的組成部分。作者通過計算社群k中前250個頂點的預測節點機率與相同節點的中心性之間的Spearman秩相關系數來評估此任務的性能，該機率由測試中配置設定給同一社群k的頂點的連結數來衡量組。
下表總結了動态連結預測的結果，GRADE在DBLP和Reddit資料集上明顯優于其他基線模型，并在IMDb上達到了與基線相當的結果。此外，為了檢查GRADE是否捕獲了真實的社群和節點動态，作者将訓練集中的圖序列随機化，同時在驗證和測試集中保留真實順序。在所有資料集上進行随機化之後，觀察到明顯的降級，這表明GRADE可以識别時間演化的模式，而不是學習聚合的圖形表示。
下表中顯示了動态社群發現和預測社群規模動态的結果。在這些任務中，GRADE的性能也明顯優于DBLP和Reddit資料集上的所有基線方法。結果表明，GRADE在将來的測試時間步驟中推斷節點和社群表示的能力有助于提高性能，這與在最後訓練步驟中将學習到的嵌入用于預測的其他動态基線形成對比。作者還觀察到在某些随機圖上訓練GRADE可以在某些任務上獲得與真實序列相當的性能，例如DBLP上的NMI和Reddit上的子產品化。同時，作者提出在真實序列上訓練GRADE與訓練圖随機化相比，始終能産生相同或更好的性能，是以證明了GRADE能勾捕獲了時間動态模式。
4
總結
在本文中，作者提出了GRADE-一種在離散時間動态圖中共同學習進化節點和社群表示的方法。作者通過邊緣生成機制來實作這一點，該機制通過節點和社群多項式分布對局部和全局圖結構之間的互動進行模組化，并使用學習到的嵌入參數化這些分布，以及高斯狀态空間模型随時間演化它們。此外，作者引入過渡矩陣來顯式捕獲節點社群動态。最後，作者在真實資料集上驗證了GRADE在動态連結預測，動态社群發現和預測社群規模動态這一新穎任務的有效性，即推斷未來在結構上具有影響力的頂點。