圖這種結(jié)構(gòu)普遍存在于人類社會生活中，如互聯(lián)網(wǎng)中網(wǎng)頁間的互相鏈接會構(gòu)成圖、網(wǎng)民購買商品會構(gòu)成“網(wǎng)民-商品”圖、人和人的交流會構(gòu)成圖、論文的互相引用也會構(gòu)成圖。有許多任務(wù)需要根據(jù)這些圖的信息完成，例如根據(jù)用戶和商品的歷史交互，預(yù)測一個用戶是否會購買一個商品或?qū)λ信d趣；又如根據(jù)用戶間的好友關(guān)系或交流記錄，預(yù)測用戶和用戶之間是否構(gòu)成好友關(guān)系。

因為經(jīng)典的深度學(xué)習(xí)方法如RNN、CNN等不能直接使用到圖這種結(jié)構(gòu)中，最近幾年圖神經(jīng)網(wǎng)絡(luò)（Graph Neural Network）成為了深度學(xué)習(xí)的研究熱點之一。圖神經(jīng)網(wǎng)絡(luò)在對圖中節(jié)點之間的依賴關(guān)系建模方面的強(qiáng)大功能使得與圖分析相關(guān)的研究領(lǐng)域取得了重要突破。但這些圖神經(jīng)網(wǎng)絡(luò)算法如DeepWalk[1]、GCN[2]等大多都是基于靜態(tài)圖（static graph）而不是基于動態(tài)圖（dynamic graph）的，所以這些算法很多時候沒有完整地使用上一個圖中的所有信息。

靜態(tài)圖與動態(tài)圖

一個圖G=(V,E)由節(jié)點集合V以及邊集合E組成，每個節(jié)點v∈V有自身的節(jié)點屬性，每條邊e∈E有自身的邊屬性。靜態(tài)圖指的是圖的節(jié)點和邊都是固定的，不會隨時間變化。而實際上在現(xiàn)實世界中，圖的節(jié)點和邊往往都是動態(tài)變化的，邊會動態(tài)增加（用戶購買新的商品、用戶關(guān)注另一個用戶），節(jié)點會增加（新網(wǎng)頁上線、新用戶注冊），節(jié)點的屬性會變化（用戶的屬性會隨時間變化）等。基于靜態(tài)圖去解決問題，雖然處理起來更簡單，但不符合實際，預(yù)測效果也會大打折扣。動態(tài)圖則認(rèn)為圖中的節(jié)點、邊都是會動態(tài)變化的，會出現(xiàn)節(jié)點和邊的動態(tài)增加、動態(tài)減少以及屬性的動態(tài)變化。雖然動態(tài)圖更符合實際，但因為要研究的目標(biāo)是在圖上動態(tài)變化的，可以想象研究難度會比靜態(tài)圖高不少。隨著靜態(tài)圖算法的日趨成熟，不少研究人員開始在基于靜態(tài)圖的神經(jīng)網(wǎng)絡(luò)算法[1][2]的研究基礎(chǔ)上提出了一些動態(tài)圖算法，這里我們以兩個代表算法CTDNE[3]和JODIE[4]為例介紹他們使用動態(tài)圖來解決靜態(tài)圖局限性的思路。

CTDNE

CTDNE[3]是在DeepWalk基礎(chǔ)上發(fā)展出來的算法框架，也是訓(xùn)練圖中節(jié)點的embedding表示。在圖1中，每條邊可以代表現(xiàn)實生活中兩個實體（如用戶、商品等）的一次交互（如打電話、發(fā)郵件、關(guān)注等），邊上的數(shù)字代表交互發(fā)生的時間。DeepWalk算法是基于靜態(tài)圖的算法，相當(dāng)于忽略了邊的發(fā)生時間，然后在圖中隨機(jī)選取一個節(jié)點作為起點，以隨機(jī)游走（Random Walk）的方式采樣出一條路徑。在采樣出大量的路徑后，使用SkipGram的結(jié)構(gòu)訓(xùn)練每個節(jié)點的embedding。但使用Random Walk采樣因為忽略了邊是動態(tài)增加的，往往會采樣出不合理的路徑，例如用戶v1先發(fā)消息給v2，然后v2發(fā)給v3，v3發(fā)給v4，v4發(fā)給v1。但Random Walk可能會采樣出路徑v4-v1-v2，這條路徑相當(dāng)于跳過了v3，表達(dá)的意思就是由v4發(fā)消息給v1然后v1再發(fā)給v2，這樣的路徑是不合理的。

圖1. 動態(tài)圖樣例[3]

CTDNE認(rèn)為，一條合理的時序路徑（temporal walk）應(yīng)該滿足規(guī)則：“路徑中每條邊的時間都應(yīng)該小于等于下一條邊的時間”。在滿足這一規(guī)則的基礎(chǔ)上，還需要確定兩個隨機(jī)采樣方式。初始節(jié)點/邊的采樣方式以及采樣下一個滿足規(guī)則的鄰居節(jié)點/邊的采樣方式。論文通過實驗證明，對于初始邊的采樣使用線性增長的采樣最好，也就是一條邊的被采樣概率隨著邊的發(fā)生時間增長而線性增長。而對于采樣下一條邊，在滿足下一條邊的時間大于等于當(dāng)前邊的條件下，采樣等概率采樣的方式更好。

總結(jié)起來，CTDNE就是在DeepWalk基礎(chǔ)上，通過修改路徑采樣方式使得路徑滿足實際的發(fā)生順序，從而使得采樣路徑更加合理。

JODIE

JODIE[4]主要處理用戶（user）與物品（item）間的交互序列（sequence of interaction）預(yù)測問題。用戶和物品的交互在現(xiàn)實中普遍存在，例如用戶購買商品、學(xué)生注冊某個 MOOC 課程、一個網(wǎng)友編輯了某個Wikipedia頁面等。一個用戶往往會在不同的時間和不同的物品進(jìn)行交互，對同一個物品也可能會出現(xiàn)多次的交互。預(yù)測用戶和物品間的交互是非常重要的問題，如預(yù)測用戶的購買商品行為可以進(jìn)行商品推薦；預(yù)測學(xué)生什么時候可能退出MOOC課程可以為他們制定后續(xù)的教育計劃；預(yù)測用戶何時可能在平臺（如Reddit、Wikipedia）上會出現(xiàn)惡意操作對維護(hù)平臺的穩(wěn)定非常重要。

在根據(jù)用戶與物品的交互序列進(jìn)行預(yù)測時，需要解決兩個主要問題。

1. 用戶和物品的屬性會隨著時間發(fā)展而變化。例如圖2中用戶u3的興趣愛好可能會隨著時間推移慢慢從書本轉(zhuǎn)移到電影再轉(zhuǎn)移到衣服。書本可能一開始在老年人中流行，慢慢地在年輕人中也流行了開來。而靜態(tài)圖將這些交互都存放在一張沒有時間記錄的圖上，無法建模節(jié)點的屬性變化。

2. 用戶和物品會因為他們交互的對象屬性不同而對自身屬性產(chǎn)生不同影響。例如用戶 u2在書本i2獲得普利策獎之后購買，與u2在書本獲獎之前購買，模型建模得到的u2的屬性變化應(yīng)該是不一樣的。同樣，靜態(tài)圖也沒有辦法建模出這樣的信息。

圖2. 用戶和物品的交互序列（左）以及在JODIE中的動態(tài)表示[4]

在JODIE中，每個用戶和物品都有兩個 embedding：static embedding和dynamic embedding。static embedding 表示一個用戶/物品的長期靜態(tài)屬性，而dynamic embedding表示不斷變化的屬性，通過 JODIE 模型進(jìn)行學(xué)習(xí)。這使得JODIE能夠根據(jù)用戶的靜態(tài)屬性和隨時間變化的時序?qū)傩赃M(jìn)行預(yù)測。

JODIE模型有三個主要的組成部分：更新函數(shù)（update function），映射函數(shù)（project function）和預(yù)測函數(shù)（predict function）。

圖3. JODIE模型框架[4]

JODIE的更新函數(shù)通過兩個RNN來生成用戶和物品的dynamic embedding：

在每次交互時，根據(jù)用戶和物品上一刻的 embedding：u(tˉ)和i(tˉ)、當(dāng)前交互與用戶上一次交互的時間間隔△u以及當(dāng)前交互的特征f來更新用戶的embedding。類似地，RNNi會更新物品的embedding。

用戶的屬性在上一次交互之后短時間內(nèi)基本不變，但是隨著時間增長往往會顯著變化，而模型中用戶的embedding卻一直沒有改變，使用這個embedding進(jìn)行預(yù)測往往是不科學(xué)的。于是JODIE的映射函數(shù)通過類似attention的學(xué)習(xí)方式，評估/轉(zhuǎn)換用戶上一次的embedding u(t)在經(jīng)過時間間隔△u之后新的用戶embedding。

最后，JODIE的預(yù)測函數(shù)會直接輸出用戶最有可能與之交互的物品的embedding，因此模型中只需要進(jìn)行一次神經(jīng)網(wǎng)絡(luò)的前向傳遞，然后找到與目標(biāo)embedding最接近的物品的embedding，這比進(jìn)行N次前向傳遞（與N個物品進(jìn)行預(yù)測）然后進(jìn)行排序要高效得多。

總結(jié)起來，JODIE會根據(jù)用戶和物品的交互序列動態(tài)地更新用戶和物品的embedding，從而建模出用戶和物品動態(tài)變化的屬性。

總結(jié)

本文先從靜態(tài)圖的局限性出發(fā)介紹了動態(tài)圖的優(yōu)勢，然后通過CTDNE和JODIE兩個算法介紹了動態(tài)圖算法的基本思路。動態(tài)圖算法的研究目前還處于初級階段，未來的研究方向包括：如何設(shè)計更好的動態(tài)圖模型使得算法可以更合理地建模圖中節(jié)點和邊的屬性；使用什么數(shù)據(jù)結(jié)構(gòu)使得動態(tài)圖算法能大規(guī)模部署和運行；如何將知識圖譜等信息引入動態(tài)圖中。希望這篇文章能對從事圖算法相關(guān)領(lǐng)域的朋友有參考意義，對于本文的不足之處，請讀者不吝賜教。

參考文獻(xiàn)

[1] Perozzi, Bryan, Rami Al-Rfou, and Steven Skiena. "Deepwalk: Online learning of social representations." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014.

[2] Kipf, Thomas N., and Max Welling. "Semi-supervised classification with graph convolutional networks." arXiv preprint arXiv:1609.02907 (2016).

[3] Nguyen, Giang Hoang, et al. "Continuous-time dynamic network embeddings." Companion of the The Web Conference 2018 on The Web Conference 2018. International World Wide Web Conferences Steering Committee, 2018.

[4] Kumar, Srijan, Xikun Zhang, and Jure Leskovec. "Learning Dynamic Embeddings from Temporal Interactions." arXiv preprint arXiv:1812.02289 (2018).

?作者簡介

姓名：劉旭欽

專業(yè)：數(shù)據(jù)科學(xué)(計算機(jī)科學(xué)與技術(shù))

年級：碩士三年級

研究方向：圖神經(jīng)網(wǎng)絡(luò)

總結(jié)

以上是生活随笔為你收集整理的activiti动态增加节点_图神经网络之动态图的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。