譯者 | Sambodhi
編輯 | 海邊的拾遺者
導讀
在本文中，作者将描述時間圖網絡（Temporal Graph Network，TGN），這是一個用于深度學習動态圖的通用架構。
許多現實世界的問題涉及各種性質的交易網絡、社會互動和交往，這些都是動态的，可以将其模組化為圖，其中，節點和邊會随着時間的推移而出現。在本文中，我們将描述時間圖網絡（Temporal Graph Network，TGN），這是一個用于深度學習動态圖的通用架構。
本文是 Michael Bronstein 與 Emanuele Rossi 共同撰寫的。
圖神經網絡的研究已經成為今年機器學習領域 炙手可熱 的話題之一。最近，圖神經網絡在生物學、化學、社會科學、實體學和許多其他領域的問題上，取得了一系列成功。到目前為止，圖神經網絡模型主要是針對靜态圖而開發的，靜态圖不會随着時間而改變。然而，許多有趣的現實世界圖都是動态的，并且會随着時間的推移而不斷變化，突出的例子包括社交網絡、金融交易和推薦系統。在許多情況下，正是這種系統的動态行為傳達了重要的見解，否則，如果隻考慮靜态圖的話，就會失去這種見解。
Twitter 使用者與推文進行互動并互相關注的動态網絡。所有邊都有時間戳。給定這樣的動态圖，我們想預測未來的互動，例如，使用者會喜歡哪些推文，或者他們會關注誰。
動态圖可以表示為定時事件的有序清單或異步“流”，例如節點和邊的添加或删除【1】。像 Twitter 這樣的社交網絡就是一個很好的例子：當一個人注冊 Twitter 賬戶時，就會建立一個新的節點。當他們關注另一個使用者時，就會建立“關注”邊。當他們更改其配置檔案時，該節點将被更新。
該事件流由編碼器神經網絡接受，這個編碼器神經網絡為圖的每個節點生成時間相關的嵌入。然後，可以将嵌入饋送到為特定任務而設計的解碼器中。一個例子是通過嘗試回答以下問題來預測未來的互動：在時刻 t ，節點 i 和 j 之間具有邊的機率是多少？回答這個問題的能力對于推薦系統至關重要，例如，建議社交網絡使用者關注誰，或者決定顯示哪些内容。下圖示範了這種場景：
一個時間圖網絡的例子，它接收了具有七條可見邊（時間戳為 t₁ 到 t₇ ）的動态圖，目的是預測節點 2 和節點 4 在時刻 t₈ （灰色邊 t₈ ）的未來互動。為此，時間圖網絡在時刻 t₈ 計算節點 2 和 4 的嵌入。然後，将這些嵌入連接配接起來并饋送到解碼器（如 MLP），該解碼器輸出互動發生的機率。
以上設定中的關鍵部分是編碼器，可以與任何解碼器一起訓練。對于上面提到的未來互動預測任務，可以采用自監督的方式進行訓練：在每個輪數（epoch）中，編碼器按時間順序處理事件，并根據前面的時間預測下一次互動【2】。
時間圖網絡是我們與同僚 Fabrizio Frasca、Davide Eynard、Ben Chamberlain 和 Federico Monti 共同開發的通用編碼器架構【3】。該模型可應用于表示為事件流的動态圖上的各種學習問題。簡而言之，時間圖網絡編碼器根據節點的互動建立節點的壓縮表示，并在每個事件發生時更新節點。要實作這一點，時間圖網絡有以下主要元件：
記憶體 。記憶體存儲所有節點的狀态，作為節點過去互動的壓縮表示。它類似于 RNN 的隐狀态。但是，在這裡，對于每個節點 i ，都有單獨的狀态向量 sᵢ(t) 。當一個新節點出現時，我們添加一個相應的狀态，初始化為零向量。此外外，由于每個節點的記憶體隻是一個狀态向量（而非參數），是以，當模型接受新的互動時，也可以在測試時進行更新。
消息函數 是記憶體更新的主要機制。給定節點 i 和 j 在時刻 t 的互動，消息函數計算兩條消息（一條用于 i ，一條用于 j ），用于更新記憶體。這類似于在消息傳遞圖神經網絡【4】中計算的消息。該消息是在節點 i 和 j 在時刻 t 之前互動時的記憶體函數，互動時刻 t 和邊特征為【5】：
記憶體更新程式 用于使用新消息更新記憶體。這個子產品通常作為 RNN 來實作。
假設節點的記憶體是随時間更新的向量，最直接的方法是将其直接用作節點嵌入。然而，在實踐中，由于陳舊性問題的存在，這并不是一個好主意：假設僅當節點參與互動時才更新記憶體，則節點的長時間不互動會導緻其記憶體過期。舉個例子，假設一個使用者有幾個月沒有使用 Twitter。當使用者回到 Twitter 時，他們可能已經在此期間發展出了新的興趣，是以，對他們過去活動的記憶體就不再相關了。是以，我們需要一種更好的方法來計算嵌入。
嵌入 。一種解決方案是檢視鄰近節點。為了解決陳舊性問題，嵌入子產品通過在節點的時空鄰居上執行圖聚合來計算節點的時間嵌入。即使一個節點已處于非活動狀态一段時間，它的一些鄰居也可能處于活動狀态，通過聚合它們的記憶體，時間圖網絡可以為該節點計算一個最新嵌入。在我們的示例中，即使使用者不上 Twitter，但他們的朋友仍然是活躍的，是以，當他們回來的時候，朋友最近的活動可能比使用者自己的曆史記錄更相關。
圖嵌入子產品通過在目标節點的時間鄰域上執行聚合來計算目标節點的嵌入。在上圖中，當計算節點 1 在某個時刻 t 大于 t₂ 、 t₃ 和 t₄ ，但小于 t₅ 時的嵌入時，時間鄰域将近包含時刻 t 之前出現的邊。是以，節點 5 的邊不參與計算，因為它在将來發生。相反，嵌入子產品将鄰近 2、3、4 的特征 (v) 和記憶體 (s) 以及邊上的特征聚合起來，以計算節點 1 的表示。在我們的實驗中，性能最好的圖嵌入子產品是圖注意力子產品，它可以根據鄰居的記憶、特征和互動時間來判斷哪些鄰居是最重要的。
時間圖網絡對一批訓練資料執行的總體計算總結如下圖所示：
時間圖網絡對一批訓練資料進行的計算。一方面，嵌入由嵌入子產品使用時間圖和節點的記憶體 (1) 生成嵌入。然後使用嵌入預測批量互動作用并計算損失 (2,3)。另一方面，這些相同的互動用于更新記憶體 (4,5)。
通過檢視上圖，你可能想知道記憶體相關子產品（消息函數、消息聚合器和記憶體更新器）是如何訓練的，因為它們似乎不會直接影響損失，是以不會收到梯度。為了讓這些子產品能夠影響損失，我們需要在預測批互動之前更新記憶體。然而，這将會導緻洩漏，因為記憶體中已經包含了我們試圖預測的資訊。我們提出的解決這個問題的政策是用來自前一批的消息更新記憶體，然後預測互動。時間圖網絡的操作流程如下圖所示，這是訓練記憶體相關子產品所必需的：
對記憶體相關子產品進行訓練所需的時間圖網絡的操作流程。引入了一個新元件，即原始消息存儲庫，它存儲了計算消息所需的資訊，我們稱之為原始消息，用于模型過去處理過的互動。這允許模型将互動帶來的記憶體更新延遲到以後的批處理。首先，使用從存儲在先前批次（1 和 2）中的原始消息計算的消息來更新記憶體。然後可以使用剛剛更新的記憶體（灰色連接配接）(3) 來計算嵌入。通過這樣做，記憶體相關子產品的計算直接影響損失 (4,5)，并且他們接收梯度。最後，這個批處理互動的原始消息存儲在原始小村存儲庫 (6) 中，以便在将來的批進行中使用。
通過在各種動态圖上進行深入的實驗驗證，在未來邊預測和動态節點分類的任務上，時間圖網絡在正确率和速度上都明顯優于競争方法【6】。維基百科（Wikipedia）就是這樣的一個動态圖，其中使用者和頁面是節點，互動表示使用者編輯頁面。編輯文本的編碼用作互動特性。本例中的任務是預測使用者将在給定時間編輯哪個頁面。我們用基線方法比較了時間圖網絡的不同變體：
在預測正确率和時間方面，比較時間圖網絡和舊方法（TGAT 和 Jodie）對維基百科資料集上未來連結預測的各種配置。我們希望有更多的論文，以嚴謹的方式報道這兩個重要标準。
這項消融研究揭示了不同時間圖網網絡子產品的重要性，并使我們能夠得出一些一般性結論。首先，記憶體很重要：記憶體的缺失會導緻性能的大幅下降【7】。其次，嵌入子產品的使用（與直接輸出記憶體狀态相反）很重要。基于圖注意力的嵌入表現最好。第三，擁有記憶體使得隻使用一個圖注意力層就足夠了（這大大減少了計算時間），因為一跳鄰居的記憶體使模型能夠間接通路二跳鄰居的資訊。
作為結束語，我們認為動态圖的學習的研究領域幾乎就是個“處女地”，有許多重要和令人興奮的應用以及重大的潛在影響。我們相信，我們的時間圖網絡模型是朝着提高學習動态圖的能力邁出的重要一步，鞏固并擴充了以前的結果。随着這一研究領域的發展，更好、更大的基準将變得至關重要。我們現在正緻力于建立新的動态圖資料集和任務，作為 Open Graph Benchmark 的一部分。
參考文獻
【1】 這種情況通常被稱為“連續時間動态圖”。為簡單起見，這裡我們隻考慮節點對之間的互動事件，在圖中用邊來表示。當其中一個端點不在圖中時，節點插入被認為是新邊的一種特殊情況。我們不考慮節點或邊的删除，這意味着圖隻能随時間增長。由于一對節點之間可能有多條邊，從技術上講，我們擁有的對象是多重圖。
【2】 多個互動可以具有相同的時間戳，并且模型可以獨立地預測每個互動。此外，通過将時間的有序清單拆分成固定大小的連續塊，可以建立迷你批。
【3】 《 用于動态圖深度學習的時間圖網絡》（Temporal graph networks for deep learning on dynamic graphs），E. Rossi 等人，2020 年，arXiv:2006.10637。
【4】 為簡單起見，我們假設該圖是無向的。在有向圖的情況下，需要兩個不同的消息函數，一個用于源，一個用于目的地。
【5】 《 量子化學的神經資訊傳遞》（Neural Message Passing for Quantum Chemistry），J. Gilmer 等人，2017 年，arXiv:1704.01212。
【6】 對于動态圖的深度學習，目前隻有少數幾種方法，如《 時間圖的歸納表示學習》（Inductive representation learning on temporal graphs）的時間圖網絡，D. Xu 等人，2020 年，arXiv:2002.07962；以及《 時間互動網絡中的動态嵌入軌迹的預測》（Predicting dynamic embedding trajectory in temporal interaction networks）的 Jodie，S. Kumar 等人，2019 年，arXiv:1908.01207。我們證明了這些方法可以作為時間圖網絡的特殊配置來獲得。由于這一原因，時間圖網絡似乎是目前在動态圖學習上最為通用的模型。
【7】 雖然記憶體包含關于一個節點過去所有互動作用的資訊，但圖嵌入子產品隻能通路時間鄰域的樣本（出于計算原因），是以可能無法通路對手頭任務至關重要的資訊。
作者介紹：
Michael Bronstein，倫敦帝國理工學院教授，Twitter 圖機器學習研究負責人，CETI 項目機器學習主管、研究員、教師、企業家和投資者。