三大高峰會看動態圖表示學習

2020 年 3 月 3 日
筆記

作者 | 王春辰

學校 | 北京郵電大學

研究方向 | 圖神經網路及其應用

鑒於網路挖掘在現實生活中的豐富應用，以及近些年網路表示學習的興起，網路嵌入已經成為學術界和工業界日益關注的研究熱點。

網路嵌入的目的是將節點嵌入到低維空間中，同時捕捉網路的結構和性質。雖然已經提出了很多很有前途的網路嵌入方法，但大多數都是針對靜態網路的。

動態網路相比於靜態網路來說，強調了網路中節點和邊的出現順序和時間。因為現實中，是通過節點和邊的順序添加而形成的，這確實應該被視為一個有節點與其鄰居之間交互事件驅動的動態過程。因此節點的鄰域並不是同時形成的，觀察到的快照網路結構應該是一段時間內鄰域的累積。

Graph 1:Embedding Temporal Network via Neighborhood Formation KDD2018

例如上圖出示了一個作者的ego網路；節點1，以及其鄰居，即節點2到6.從網路結構快照上來看只能看出網路最新的結構，而節點如何以及何時連接仍然是未知的事情。

本文主要介紹了以下幾篇論文:

KDD2018 Embedding Temporal Network via Neighborhood Formation
CIKM2019 Temporal Network Embedding with Micro- and Macro-dynamics
ICLR2020 INDUCTIVE REPRESENTATION LEARNING ON TEMPORAL GRAPHS

KDD2018 Embedding Temporal Network via Neighborhood Formation

該文指出，在大多數實際網路中，節點之間的邊通常是由順序事件建立的，這些事件構成了所謂的時態網路。如Graph 1中合著者網路是由具有明確時間的合著論文驅動的。因此，本文將ego時間網路根據時間的定時展開成特定的鄰居序列，如上圖(b)所示。

本文中模型是基於多元Hawkes過程的鄰域序列建模：

其中表示x和y之間形成的邊的事件的基本速率，而h是時間t之前的節點x的鄰域形成序列中的歷史目標節點。表示歷史鄰域激發當前鄰域y的程度，並且核函數表示可以指數函數形式寫入的時間衰減效應。

那麼，在這裡簡單介紹一下Hawkes過程：

其中，是特定事件的基本強度，顯示在時間t的自發事件到達率；是對過去歷史對當前事件的時間衰減效應進行建模的核函數，其形式通常為指數函數。

霍克斯過程的條件強度函數表明，當前事件的發生不僅取決於上一個時間步長的事件，而且還受具有時間衰減效應的歷史事件的影響。這種特性對於鄰域形成序列的建模是期望的，因為當前的鄰域形成可以受到較新事件的較高強度的影響，而在較長歷史中發生的事件對目標鄰域的當前出現的貢獻較小。相關Hawkes process的文章清參見The Neural Hawkes Process: A Neurally Self-Modulating Multivariate Point Process https://arxiv.org/pdf/1612.09328v2.pdf

回到上述模型中來看，表示歷史鄰域激發當前鄰域y的程度。在這裡文章中引入attention機制，文中使用Softmax定義源節點與其歷史節點之間的權重，如下所示：

因此，歷史鄰居對當前目標的影響可以重新表述為：

CIKM2019 Temporal Network Embedding with Micro- and Macro-dynamics

Temporal Network Embedding with Micro- and Macro-dynamics CIKM2019 可以看做是在上述模型之上的擴展出的模型. 本文提出時間網路是無處不在的，它通常在微觀和宏觀動力學方面隨著時間的推移而演變。微觀動力學詳細描述了網路結構的形成過程，而宏觀動力學則是指網路規模的演化模式。本文提出了一種新的微觀和宏觀相結合的時態網路嵌入方法MMDNE

Graph 2:Temporal Network Embedding with Micro- and Macro-dynamics CIKM2019

(a)微觀動力學保存嵌入時序attention點過程。虛線表示要建立的邊，不同顏色的實心箭頭表示鄰居對不同邊的影響。垂直彩色矩形塊代表attention機制，顏色越深，鄰居的影響越大。(B)宏觀動力學保留嵌入動力學方程，該方程用網路嵌入 (即綠色矩形塊)和時間參數化。在時間，MMDNE 宏觀約束邊數為。(C)微觀和宏觀動力學以相互的方式演化和派生節點嵌入。在當前時間，通過從歷史鄰居(即和 )微觀預測，鏈接節點，和的概率分別為0.5、0.4和0.1；而宏觀動力學根據網路規模的演化模式將新邊的數量限制在只有2條。因此，MMDNE捕獲了更精確的結構和時間屬性。

本文中微觀動力學模型由節點自身基本強度和來自雙向歷史鄰居的歷史影響組成，如下所示：

其中是度量兩個節點相似度的模型，這裡定義為。和分別是和在之前的歷史鄰居。是具有依賴於節點且可學習的衰減率的時間衰減函數。這裡和是分層的attention。

如前所述，過去的事件對當前事件有所影響，這種影響可能與過去的事件有所不同。因為鄰居的影響也是動態的，所以文中提出一種時態分層的attention來捕捉歷史結構的非均勻和動態的影響。attention係數定義如下：

其中是級聯運算，作為attention向量，表示局部權重矩陣。

文中考慮到對於整個鄰居的全局影響，這裡是一個全局attention，文中用每個鄰居的聚合來表示歷史鄰居來作為一個整體。考慮到全局衰減，文中對過去時間衰減進行平均。所以有如下定義：

其中，是單層神經網路，他以鄰居聚合嵌入和過去時間的平均時間衰減作為輸入。

本文中宏觀動力學描述的是網路規模的演化模式，通常服從明顯的分布，即網路規模可以用一定的動力學方程來描述。此外，宏觀動力學在更高的層次上約束了網路內部結構的形成，即它決定了到目前為止總共應該生成多少條邊。給定一個時間網路，我們有時間t的累計節點數，對於每個節點，它在時間以一個鏈接率鏈接其他節點(例如，節點)。根據網路演化的增密冪律，我們有平均可達鄰居，其線性稀疏係數 ζ和冪律稀疏指數 γ。因此，我們將涉及時間t處的新邊的數量的宏觀動力學定義如下：

其中可以隨著網路隨時間的演化而獲得，ζ 和 γ可通過模型優化來學習。

上面是通過Network Embedding的方法來進行時序網路建模。那麼在圖神經網路上是否也可以進行時序網路建模呢？

在GC-LSTM: Graph Convolution Embedded LSTM for Dynamic Link Prediction https://arxiv.org/abs/1812.04206 中提出採用GCN-LSTM的結構來將結構資訊與時間資訊相結合。同期還有採用GCN-GRU等架構。

ICLR2020 INDUCTIVE REPRESENTATION LEARNING ON TEMPORAL GRAPHS

論文鏈接: https://arxiv.org/abs/2002.07962

文中提到，時序圖的演化特性要求處理新節點以及捕獲時態模式。節點嵌入現在是時間的函數，它既要代表節點的靜態特徵，又要代表不斷演變的拓撲結構。此外，節點和拓撲特徵也可以是時態的，節點嵌入也應該捕獲其模式。

Graph 3:Inductive Representation Learning on Trmporal Graphs ICLR2020

時間圖中幾個複雜情況的直觀說明。(A)。時態圖及其快照的生成過程。顯然，快照中的靜態圖形只反映了部分時間資訊。(B)。將時間圖形投影到與時間無關的2-D平面時的最終狀態。除了丟失時間資訊外，還會出現多邊緣情況。(C)。當在時間t3預測節點A和C之間的鏈路時，消息傳遞路徑應該受到時間約束。實線給出了適當的方向，而虛線違反了時間約束。

下面我們來看本文的模型，文中提到一種特殊的時間函數編碼。本文中的函數時間編碼啟發於self-attention機制。將self-attention中代表位置的vector用本文提到的時間函數編碼替代，從而使整體帶有時間屬性。

下面來看本文中提到的時序圖注意層：

Graph 4:具有3個attention頭的第l層TGAT層的體系結構 –Inductive Representation Learning on Trmporal Graphs ICLR2020

文中所設計的TGAT體系結構完全依賴於TGAT層。類似於GraphSage和GAT，TGAT層可以看成是一個局部聚集運算元。

根據原有的自我注意機制，首先得到實體-時間矩陣，即輸入

然後將其轉發到三個不同的線性投影，用來獲得『query』，『key』，『value』：

其中，適用於捕獲事件編碼和特徵之間的交互的權重矩陣。

類比於self-attention，同理得到。

為了將鄰域表示與目標節點特徵相結合，文中採用了與GraphSAGE相同的做法，將鄰域表示與目標節點特徵向量連接。然後將其傳給前饋網路：

其中，是目標節點在時間處的最終表示輸出。

當然，為了推廣的目的，文中還證明了TGAT層是可以很容易的拓展到多頭設置。考慮來自多哥頭的自我注意輸出向量。我們將他們表示成一個組合向量，然後執行相同過程：

就像GraphSAGE一樣，單個TGAT層聚合本地化的一跳鄰域，通過堆疊層TGAT，聚合擴展到跳。

這裡還有一篇相類似的文章推薦給大家DYNAMIC GRAPH REPRESENTATION LEARNING VIA SELF-ATTENTION NETWORKS ICLR2019 https://arxiv.org/abs/1812.09430

總結

近些年已經陸陸續續有很多關於動態網路建模或者動態鏈接預測的文章發表出來。無論是Network Embedding的方法，或是GCN+LSTM，亦或是將時序資訊嵌入到GNN當中去，都是為了更好的捕捉時間資訊對網路煙花的影響。我們希望不斷探索，通過某種演算法以更逼真的方式來模擬時序網路的演化過程，從而更能服務於我們的實際問題。

上述文章中如果有某些地方引用不準確我說明不準確的地方望大家包涵 ———— Thank you for reading