時態圖網路：即使很久不發朋友圈，也能知道你的新興趣
編譯 | 龔倩
校對 | 青暮
現實世界中，各種性質的交易網路、社會互動和交往等許多問題都是動態的，並且都可以被建模成節點和邊隨時間變化的圖。在這篇文章中，我們介紹了時態圖網路，這是由Twitter開發的，用於動態圖深度學習的通用框架。本文作者是Twitter的圖學習研究負責人Michael Bronstein。
圖神經網路（GNN）的研究已經飛速成為今年機器學習領域最熱門的話題之一。近期，人們見證了GNN在生物學、化學、社會科學、物理學和許多其他領域中取得了一系列的成功。
到目前為止，GNN模型主要是針對不隨時間變化的靜態圖開發的。然而，真實世界裡許多值得關注的圖卻是動態的，是會隨著時間的推移不斷發展變化的，其中突出的例子包括社交網路、金融交易和推薦系統等。
在許多情況下，正是這類系統的動態行為向人們傳達出重要的資訊，而如果只考慮靜態圖，我們就很難得到這些重要的資訊。
在一個動態的Twitter用戶網路里，用戶們通過發布推特進行交互並相互關注。圖中所有的邊都有一個時間戳。我們想要基於這樣一個動態圖來預測未來的交互如何發生，比如用戶會喜歡哪種類型的推特，或者他們會選擇關注誰。
動態圖可以表示為時間事件的有序列表或非同步「流」，例如節點和邊的添加或刪除。像Twitter這樣的社交網路就是一個很好的例子：當一個人開始使用Twitter時，圖中就會創建一個新的節點。當用戶們關注另一個用戶時，圖中就會創建一個邊。當用戶更改其配置文件時，圖中的節點將會被更新。
事件流被編碼器神經網路接收，該神經網路為圖的每個節點生成了一個與時間相關的嵌入。嵌入的內容可以被傳輸到針對特定任務而設計的解碼器。
一個示例任務是通過嘗試回答以下問題來預測未來的交互：節點i和 j在t時刻出現邊的概率是多少？對於推薦系統來說，解決這個問題的能力是至關重要的，例如為社交網路用戶推薦關注者，或者為特定用戶推薦展示內容。如下圖所示：
本圖展示了一個TGN編碼器接收了一個具有七條可視邊（分別帶有時間戳 t₁到 t₇）的動態圖，目的是預測在t₈時刻（即圖中灰色邊緣），節點2和節點4之間出現交互的概率。為此，TGN在t₈時間點計算節點2和節點4的嵌入，然後將這些嵌入串聯起來並傳輸到解碼器（例如MLP），最後解碼器輸出兩節點發生交互的概率。
以上設置中的關鍵部分是編碼器，它可以與任何解碼器一起訓練。在前面提到的未來交互預測任務中，編碼器可以採用自監督的方式進行訓練：在每一代訓練過程中（即每個epoch），編碼器按時間順序處理事件，並基於之前的事件預測下一個交互。
時態圖網路（TGN）是我們在Twitter上與Fabrizio Frasca、Davide Eynard、Ben Chamberlain和Federico Monti等同事共同開發的一個通用編碼器架構。
該模型適用於各種各樣的以事件流表徵的動態圖的學習問題。簡而言之，TGN編碼器根據節點的交互創建節點的壓縮表徵，並在每次事件發生時更新節點。基於此，TGN主要有以下組件：
記憶體。記憶體中存儲著所有節點的狀態，其作用是作為節點過去交互的壓縮表徵。它類似於RNN的隱藏狀態；不同的是每個節點 i都有一個單獨的狀態向量sᵢ(t)。
當一個新節點出現時，我們相應地添加一個初始化為零的狀態向量。此外，由於每個節點的記憶體只是一個狀態向量（而不是一個參數），所以當模型接收到新的交互時，節點在測試時間也可以進行更新。
消息函數。消息函數是記憶體更新的主要機制。給定在t時刻節點i和節點 j之間的交互，資訊函數計算出兩條消息用於更新記憶體（一條用於節點i，另一條用於節點 j）。這類似於在消息傳遞圖神經網路中計算的消息，這一消息是在交互出現前的 t⁻時刻節點i和節點 j的記憶體、交互出現的時間t、邊緣特徵這三個變數的函數：
記憶體更新程式。記憶體更新程式的作用是使用新消息更新記憶體。此模組通常使用一個RNN網路來實現。
考慮到節點的記憶體是一個隨時間更新的向量，那麼最直接的方法是直接將其作為節點嵌入來使用。
然而，由於過期問題，這一方法實踐起來也有弊端：由於節點只有在參與交互時才會更新其記憶體，那麼節點長時間不活動就會導致其記憶體過期。
舉個例子，假設一個用戶好幾個月都沒有登錄Twitter，當他（她）重新登錄時，他（她）可能已經在這段時間裡發展出了新的興趣，導致存儲著此用戶過去活動的記憶體不再和他（她）現在的興趣相關。因此，我們需要一種更好的方法來計算嵌入。
嵌入。一個解決方案是查找臨近的節點。為了解決過期問題，嵌入模組通過在與目標節點時空鄰近的節點上執行圖聚合來計算目標節點的時間嵌入。
即使一個節點在一段時間內處於非活動狀態，但與它臨近的一些節點卻很可能處於活動狀態，因此通過聚合臨近節點的記憶體，TGN可以計算出目標節點的最新嵌入。
在我們所舉的例子中，即使用戶一段時間不登錄Twitter，但他的朋友仍然在Twitter上保持活躍，所以當用戶重新登錄Twitter時，相比用戶自己的歷史記錄，用戶的朋友的最近活動可能與其當前興趣更相關。
圖嵌入模組通過在與目標節點時間臨近的節點上執行聚合來計算目標節點的嵌入。在上圖中，當在某個時刻t（t大於t₂、 t₃ 和 t₄， 但小於 t₅）計算節點1的嵌入時，時間臨近的節點將只包括在時刻t之前出現的邊。因此，節點5的邊不參與計算，因為它是在時刻t之後才出現。然而，嵌入模組是通過聚合臨近點2、3和4的特徵（v）和記憶體（s）以及邊緣上的特徵來計算節點1的表徵。在我們的實驗中，表現最好的圖形嵌入模組是圖注意力（graph attention），它能夠根據臨近節點的記憶體、特徵和交互時間來得出哪些是最重要的臨近節點。
圖示為TGN對一批訓練數據進行的計算。一方面，嵌入模組使用時間圖和節點記憶體（1）生成嵌入，然後使用嵌入來預測批處理交互作用並計算損失（2，3）。另一方面，這些預測出的交互被用來更新記憶體（4，5）。
看了上面的圖 ，你可能很好奇記憶體相關模組（消息函數、消息聚合器和記憶體更新器）是如何訓練的，因為它們似乎不會直接影響損失值，因此也不會接收到梯度。
為了讓這些模組能夠影響損失值，我們需要在預測批處理交互之前更新記憶體。但是，由於記憶體中已經包含了我們試圖預測的資訊，因此這會導致記憶體泄漏。
為了解決這個問題，我們提出的方法是用來自前一個批處理的資訊來更新記憶體，然後再預測交互。下圖顯示了訓練記憶體相關模組所必需的TGN的操作流程：
圖示為訓練記憶體相關模組所需的TGN操作流程。我們引入了一個叫做「原始消息存儲」（raw message store）的新組件，用於存儲模型已經處理過的交互。raw message store存儲了計算消息（我們稱之為raw messages）所必須的資訊。這樣模型就可以將交互時進行的記憶體更新推遲到後續的批處理。首先，用存儲在前一個批處理（1和2）中的原始消息來計算資訊，並用此資訊來更新記憶體。然後可以用這一更新過的記憶體（即圖中灰色連線）（3）來計算嵌入。這樣就使得記憶體相關模組的計算能夠直接影響損失值（4和5），並且它們會接收到一個梯度。最後，此批處理交互的原始消息被存儲在raw message store（6）中，以供後續的批處理使用。
在各種動態圖的大量實驗研究中，TGN在未來邊緣預測和動態節點分類的任務上，無論在精度還是速度上都明顯優於競爭方法。
維基百科就是這樣一個動態圖，其中用戶和頁面是節點，用戶編輯頁面就是進行交互。將編輯文本這一交互行為進行編碼，就可作為交互特徵。在這個例子中，模型的任務就是預測用戶在給定時間內會編輯哪個頁面。我們用基準線方法比較了TGN的不同變式：
圖示為基於維基百科數據集，在未來鏈路預測的預測精度和時間方面，比較不同配置的TGN和已有的方法（如TGAT和Jodie）。我們希望更多的論文能夠以嚴謹的方式報告這兩個重要數據。
這項消融研究揭示了不同TGN模組的重要性，並幫助我們得出了一些一般性結論：
-
記憶體很重要：記憶體的缺失會導致模型性能的大幅下降。
-
使用嵌入模組(而不是直接輸出記憶體狀態)非常重要，基於圖注意的嵌入性能最好。
-
由於1-hop臨近節點的記憶體能使模型間接訪問1-hop臨近節點的資訊，因此在有記憶體的情況下，模型僅僅使用一個圖注意層就足夠了(這樣就極大地減少了計算時間)。
總結。我們認為動態圖的學習幾乎是一個全新的研究領域，具有許多重要且激動人心的應用價值，對未來的潛在影響也十分深遠。我們相信，TGN模型是朝著提高動態圖學習能力、鞏固和擴展已有的研究成果所邁出的重要一步。隨著這一研究領域的發展，更好更大的基準將變得至關重要。
//towardsdatascience.com/temporal-graph-networks-ab8f327f2efe
在一個動態的Twitter用戶網路里，用戶們通過發布推特進行交互並相互關注。圖中所有的邊都有一個時間戳。我們想要基於這樣一個動態圖來預測未來的交互如何發生，比如用戶會喜歡哪種類型的推特，或者他們會選擇關注誰。
本圖展示了一個TGN編碼器接收了一個具有七條可視邊（分別帶有時間戳 t₁到 t₇）的動態圖，目的是預測在t₈時刻（即圖中灰色邊緣），節點2和節點4之間出現交互的概率。為此，TGN在t₈時間點計算節點2和節點4的嵌入，然後將這些嵌入串聯起來並傳輸到解碼器（例如MLP），最後解碼器輸出兩節點發生交互的概率。
圖嵌入模組通過在與目標節點時間臨近的節點上執行聚合來計算目標節點的嵌入。在上圖中，當在某個時刻t（t大於t₂、 t₃ 和 t₄， 但小於 t₅）計算節點1的嵌入時，時間臨近的節點將只包括在時刻t之前出現的邊。因此，節點5的邊不參與計算，因為它是在時刻t之後才出現。然而，嵌入模組是通過聚合臨近點2、3和4的特徵（v）和記憶體（s）以及邊緣上的特徵來計算節點1的表徵。在我們的實驗中，表現最好的圖形嵌入模組是圖注意力（graph attention），它能夠根據臨近節點的記憶體、特徵和交互時間來得出哪些是最重要的臨近節點。
圖示為TGN對一批訓練數據進行的計算。一方面，嵌入模組使用時間圖和節點記憶體（1）生成嵌入，然後使用嵌入來預測批處理交互作用並計算損失（2，3）。另一方面，這些預測出的交互被用來更新記憶體（4，5）。
圖示為訓練記憶體相關模組所需的TGN操作流程。我們引入了一個叫做「原始消息存儲」（raw message store）的新組件，用於存儲模型已經處理過的交互。raw message store存儲了計算消息（我們稱之為raw messages）所必須的資訊。這樣模型就可以將交互時進行的記憶體更新推遲到後續的批處理。首先，用存儲在前一個批處理（1和2）中的原始消息來計算資訊，並用此資訊來更新記憶體。然後可以用這一更新過的記憶體（即圖中灰色連線）（3）來計算嵌入。這樣就使得記憶體相關模組的計算能夠直接影響損失值（4和5），並且它們會接收到一個梯度。最後，此批處理交互的原始消息被存儲在raw message store（6）中，以供後續的批處理使用。
圖示為基於維基百科數據集，在未來鏈路預測的預測精度和時間方面，比較不同配置的TGN和已有的方法（如TGAT和Jodie）。我們希望更多的論文能夠以嚴謹的方式報告這兩個重要數據。
