基於生成式回放的流式圖神經網路模型

語言: CN / TW / HK

目錄:

· 摘要

· 背景

· 方法

·  實驗

· 總結與展望

· 參考文獻

1. 摘要

近些年來圖神經網路模型在圖資料的不同任務上取得了很大進展。然而真實世界的圖資料往往是以流式形式存在的,已有一些方法對圖神經網路模型進行更新,比如說在每個時間片上對全圖進行重新訓練,但是會導致很高的計算複雜度;而傳統線上學習方法則會導致災難性遺忘的發生,使得模型無法在全圖上有無損的效果。在本文中,我們提出了一種在流式場景下高效地訓練圖神經網路模型的全新框架,通過一個額外的圖生成模型來儲存完整的歷史分佈,使得在圖不斷變化時模型可以同時學習圖中出現的新模式並且鞏固已有知識。

該項工作由 阿里媽媽搜尋廣告演算法團隊 北京大學宋國傑副教授課題組 合作完成,基於該項工作整理的論文已發表在 KDD 2022,歡迎閱讀交流。

論文: Streaming Graph Neural Networks via Generative Replay

連結: https://dl.acm.org/doi/abs/10.1145/3534678.3539336

2. 背景

圖是一種在現實世界中是非常重要的資料結構,比如電商網路、社交網路等。為了挖掘真實圖資料中的各種資訊,圖神經網路模型(Graph neural networks,GNNs)在近年來被廣泛研究 [1],它通過聚集鄰居資訊來得到表示向量,在不同應用場景中都取得了優異效果。但是現有和GNN模型相關的工作主要探討在靜態場景下的學習,即模型在一次訓練之後不會再被更新。

然而真實世界的圖資料往往是以流式形式存在的,也就是圖結構會隨時間發生變化,比如在以User、Query、Item構成的電商網路中,每天都有新User和Item加入導致圖中不斷出現新節點,同時使用者每天的點選、購買等行為都是不同的,從而導致圖中的連邊和邊權會不斷更新。為了得到實時的節點表示向量,GNN模型進行高效更新是相當有必要的。

圖1

已有一些簡單的對GNN模型進行更新的方法,例如可以在每個時間片對全圖進行重新訓練,但會面臨很高的計算複雜度,或者採用傳統的線上學習的方法,但會導致災難性遺忘(當模型學習新模式時忘記了歷史學習到的知識),使得模型無法在全圖上有好的效果。最近,連續學習(Continual learning)作為一種序列化學習的方法被廣泛研究 [2],已有一些基於連續學習的GNN模型來解決流式場景下的圖學習問題,能使得GNN模型同時學習圖中的新知識和保持舊知識。其中,ContinualGNN [3] 、ER-GNN [4] 、TWP [5] 等分別採用基於正則化和經驗回放的方法來解決災難性遺忘問題,但是基於正則項的方法往往難以得到令人滿意的最優解,而經驗式回放的方法通過儲存部分節點來避免遺忘,往往遭遇空間開銷大和難以刻畫和更新完整的資料分佈的問題。

為了解決上述問題,我們提出一種全新的生成式回放方法來高效地訓練流式GNN模型,模型不需要儲存和訪問額外資料就可以有效地保持歷史圖資料分佈,從而避免災難性遺忘問題。

3. 方法

3.1 模型框架

我們提出了一種在流式場景下高效訓練GNN模型的全新框架,使得圖發生變化時,可以同時學習出現的新模式,並且鞏固已有知識。模型由兩個部分組成:一個GNN主模型和一個輔助的圖生成模型,模型的訓練也包含了訓練主模型和圖生成器兩個互相獨立的過程(如圖2所示)。

圖2

圖生成模型: 在每個時刻,一個新的生成器接收中的新節點和歷史圖中的回放節點作為訓練資料,其中歷史網路的回放節點是從上一時刻的生成器生成的。基於GAN框架,圖生成模型由一個生成器和一個判別器構成,通過二者的對抗訓練使得生成器挖掘當前圖資料的真實分佈,從而能夠生成與真實節點接近的模擬節點。因此圖生成模型的優化目標如下:

GNN主模型: 一個新的GNN模型同樣按照的比例融合變化節點和回放節點作為輸入,注意到回放節點的標籤則是由上一時刻的 GNN 模型得到,該軟標籤(即概率形式)可以為模型的訓練提供更多資訊。因此主模型的優化目標為:

總體而言,該生成式框架和已有的流式GNN相比有兩個好處。第一,不需要重新歷史圖資料就可以儲存完整的圖資料分佈,即通過生成器可以產生大量的歷史偽造資料。第二,儲存完整的資料分佈有助於對分佈的實時更新,尤其是在新增節點會對圖中的其他節點造成影響的情況下,給定完整的資料分佈可以更好地對行刻畫。

3.2 圖生成模型

我們訓練一個生成模型來學習歷史圖資料的分佈,它能生成偽造的歷史節點(包含節點及其鄰域資訊),從而在每個時間片生成的模擬樣本會和真實樣本一起用於模型的增量更新,使得模型不再需要重新訪問歷史資料。但是生成模型主要在計算機視覺領域發展,在圖領域遇到了困難,一些已有的圖上的生成模型(比如NetGAN和GraphRNN)更關注生成全圖的拓撲結構,而不是每個節點的鄰域資訊。

首先,我們將對中心網路(Ego network)的學習轉換為對中心化隨機遊走(Random walks with restart,RWRs)的學習,並提出一個理論框架,通過分析隨機遊走序列遍歷節點中心網路的期望步長,來證明RWRs對節點中心網路的表達能力(定理以及詳細證明過程見論文)。

基於上述理論基礎,我們基於對抗生成網路(Generative adversarial network,GAN)框架設計了對於節點中心網路的生成模型。

生成器負責生成模擬的隨機遊走序列,使得其分佈和圖上的真實遊走序列儘可能接近。為了使生成器可以捕獲遊走序列中節點之間的依賴關係,我們利用 GRU對生成過程進行建模,其核心是儲存一個圖狀態。給定上一個圖狀態和上一個輸入(輸入包含節點編號和節點屬性),通過神經網路得到當前的圖狀態,然後再通過引數將狀態上對映到和空間,生成下一個節點和它對應屬性,具體更新形式如下:

判別器則去學習如何區別模擬的遊走序列和從真實的中心網路上得到的遊走序列。它通過一個神經網路輸出該遊走序列的分數,從而判斷該遊走序列是否是真實的:

3.3 圖增量學習

在流式場景下,圖資料的分佈不斷髮生變化,需要對生成模型和主模型都進行相應的更新。對全圖進行重新學習又是不可實現的;而只基於變化部分的新模式進行更新是不足的,因為圖中任何部分的變化都是有可能影響到其他節點。一方面導致相關聯的節點出現了一些新模式,另一方面導致舊模式消失。

為了使得生成模型能適應最新的圖分佈,我們設計了圖的增量學習方式,它能對圖中的新興模式進行增量學習的同時,同時能對消亡模式也進行相應更新。具體而言,我們首先將節點鄰域模式的變化量定義為相鄰兩個時間片上表示向量的變化量,基於此檢測出受到圖變化的影響而導致鄰域模式發生偏移的節點。對於這些節點,它們將融入當前的訓練資料,使得當前生成模型和當前 GNN 模型增量地學習到新模式。而另一方面,當一些變化節點轉換為其他模式時,原有模式消失,生成模型不應該繼續生成這種冗餘模式。為了針對這種情況來對生成模型進行更新,我們設計了針對對偽造節點的過濾方法,間接地使得冗餘模式不再參與訓練並被不斷被遺忘。

4. 實驗

我們在四個開源資料集上進行實驗以證明我們模型的有效性,總體的實驗效果如表1和圖3所示。

首先,從模型效果上看,我們的模型(SGNN-GR)的效果遠好於已有的增量訓練方法,實現了和模型上界(RetrainedSAGE)相當的表現。其次,SGNN-GR比模型上界(RetrainedSAGE)要更高效,平均每一輪的迭代時間快了 3-6 倍,總的執行時間(包括了生成器的訓練時間)也快了 1.5-2 倍。

也就是說RetrainedGNN雖然效果好,但是訓練複雜度過高,無法在真實的大規模網路上應用。而我們的模型是以增量方式進行訓練的,在保持高效迭代的同時,通過額外學習一個設計精巧的生成模型避免了傳統增量學習遇到的災難性遺忘,因此給真實流式場景的應用 提高了一種很好的選擇。

表1
圖3

5. 總結與展望

本文主要研究了 GNN 模型在流式場景下的增量學習問題。我們結合連續學習方法,提出了一種基於生成式回放的流式圖神經網路框架,能夠高效地學習圖中的新模式並鞏固已有模式。我們在四個真實資料集上展開實驗,結果證明了模型的有效性,並通過進一步的分析,證明了生成模型對圖資料的表達能力。

儘管本文提出的方法已經在實驗中被論證取得了不錯的預測效果,但是在流式圖神經網路領域未來仍存在更多可能的研究方向,比如連續圖神經網路的模型自適應擴張方法、無監督場景下的連續圖神經網路方法、連續圖神經網路模型的可解釋性問題等。

參考文獻

[1] Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems. 1025–1035.

[2] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, et al. 2017. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences 114, 13 (2017), 3521– 3526.

[3] Junshan Wang, Guojie Song, Yi Wu, and Liang Wang. 2020. Streaming Graph Neu- ral Networks via Continual Learning. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 1515–15.

[4] Fan Zhou and Chengtai Cao. 2021. Overcoming Catastrophic Forgetting in Graph Neural Networks with Experience Replay. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 4714–4722.

[5] Huihui Liu, Yiding Yang, and Xinchao Wang. 2021. Overcoming Catastrophic Forgetting in Graph Neural Networks. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 8653–8661.

END

也許你還想看

圖深度學習模型進展和在阿里搜尋廣告中的應用創新

基於對抗梯度的探索模型及其在點選預估中的應用

KDD'22 | CausalMTA: 基於因果推斷的無偏廣告多觸點歸因技術

KDD2022 | MUVCOG:多模態搜尋會話下的使用者意圖刻畫

SIGIR 2021 | PCF-GNN:基於預訓練圖神經網路的顯式交叉語義建模方案

喜歡要“ 分享 ”,好看要“ 點贊 ”哦ღ~

↓歡迎留言參與討論↓