文章信息

Variational Graph Recurrent Neural Networks（VGRNN）

原文地址：Variational Graph Recurrent Neural Networks（VGRNN）：https://arxiv.org/abs/1908.09710
源碼: https://github.com/VGraphRNN/VGRNN

摘要

Representation learning over graph structured data has been mostly studied in static graph settings while efforts for modeling dynamic graphs are still scant. In this paper, we develop a novel hierarchical variational model that introduces additional latent random variables to jointly model the hidden states of a graph recurrent neural network (GRNN) to capture both topology and node attribute changes in dynamic graphs. We argue that the use of high-level latent random variables in this variational GRNN (VGRNN) can better capture potential variability observed in dynamic graphs as well as the uncertainty of node latent representation. With semi-implicit variational inference developed for this new VGRNN architecture (SI-VGRNN), we show that flexible non-Gaussian latent representations can further help dynamic graph analytic tasks. Our experiments with multiple real-world dynamic graph datasets demonstrate that SI-VGRNN and VGRNN consistently outperform the existing baseline and state-of-the-art methods by a significant margin in dynamic link prediction.

對圖結(jié)構(gòu)化數(shù)據(jù)的表示學(xué)習(xí)主要在靜態(tài)圖設(shè)置中進行研究，而對動態(tài)圖進行建模的努力仍然很少。在本文中，我們開發(fā)了一種新穎的分層變分模型，該模型引入了額外的隨機變量來聯(lián)合建模圖遞歸神經(jīng)網(wǎng)絡(luò)（GRNN）的隱藏狀態(tài)，以捕獲拓撲和節(jié)點屬性變化的非動態(tài)圖。我們認為，在這個變分GRNN（VGRNN）中使用高級潛在隨機變量可以更好地捕獲動態(tài)圖中觀察到的潛在變異性以及節(jié)點潛在表示的不確定性。通過為這種新的VGRNN架構(gòu)（SI-VGRNN）開發(fā)的半隱式變分推理，我們表明靈活的非高斯?jié)撛诒硎究梢赃M一步幫助動態(tài)圖分析任務(wù)。我們使用多個真實世界動態(tài)圖數(shù)據(jù)集的實驗表明，SI-VGRNN 和 VGRNN 在動態(tài)鏈接預(yù)測方面始終優(yōu)于現(xiàn)有的基線和最先進的方法。

Background

Graph convolutional recurrent networks (GCRN)

GCRN用于對靜態(tài)圖節(jié)點上定義的時間序列數(shù)據(jù)進行建模。視頻中的一系列幀和傳感器網(wǎng)絡(luò)上的時空測量是此類數(shù)據(jù)集的兩個示例。GCRN將圖卷積網(wǎng)絡(luò)（GCN）與循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN）相結(jié)合，以捕獲數(shù)據(jù)中的空間和時間特征。更準確地說，給定一個具有 N 個節(jié)點的圖 G，其拓撲由鄰接矩陣 A 確定，節(jié)點屬性序列 ，GCRN 讀取 M 維節(jié)點屬性并對每個時間步 t 更新其隱藏狀態(tài) ht：

這里 f 是一個非概率深度神經(jīng)網(wǎng)絡(luò)。它可以是任何遞歸網(wǎng)絡(luò)，包括門控激活函數(shù)，如長短期記憶（LSTM）或門控循環(huán)單元（GRU），其中它們內(nèi)部的深層被圖卷積層取代。GCRN 通過將聯(lián)合概率分布的因式分解參數(shù)化為條件概率的乘積來對節(jié)點屬性序列進行建模。
由于轉(zhuǎn)移函數(shù)f的確定性，這里映射函數(shù)g的選擇有效地定義了聯(lián)合概率分布可以用標(biāo)準GCRN表示。對于高度可變的序列，這可能會有問題。更具體地說，當(dāng) X 的變異性很高時，模型試圖在隱藏狀態(tài) h 中映射這種變異性，從而導(dǎo)致 h 的潛在高變異，進而導(dǎo)致訓(xùn)練數(shù)據(jù)的過度擬合。因此，GCRN并不完全能夠?qū)哂懈咦儺惖男蛄羞M行建模。自回歸模型的這一基本問題已通過向模型引入隨機隱藏狀態(tài)來解決非圖結(jié)構(gòu)數(shù)據(jù)集。

在本文中，我們將GCN和RNN集成到一個圖RNN（GRNN）框架中，這是一個動態(tài)圖自動編碼器模型。雖然GCRN旨在對靜態(tài)圖上定義的動態(tài)節(jié)點屬性進行建模，但GRNN可以在不同的時間快照獲得不同的鄰接矩陣，并通過在隱藏狀態(tài)ht上采用內(nèi)積解碼器在時間t重建圖。更具體地說，ht可以看作是動態(tài)圖在時間t的節(jié)點嵌入。為了進一步提高GRNN的表達能力，我們通過結(jié)合GRNN和變分圖自動編碼器（VGAE）來引入隨機潛在變量。這樣，我們不僅可以在不假設(shè)平滑性的情況下捕獲圖之間的時間依賴關(guān)系，而且每個節(jié)點都用潛在空間中的分布表示。此外，VGRNN中設(shè)計的先前構(gòu)造使其能夠預(yù)測未來時間步中的鏈接。

Semi-implicit variational inference (SIVI)

SIVI已被證明可以有效地學(xué)習(xí)具有偏度、峰度、多模態(tài)和其他特征的后驗分布，而現(xiàn)有的變分推理方法無法捕捉到這些特征。為了表征潛在的后驗q（z|x），SIVI在原始后驗分布的參數(shù)上引入了混合分布，以擴展具有分層結(jié)構(gòu)的變分族：。φ表示要推斷的分布參數(shù)。雖然原始后驗q（z|ψ）需要具有解析形式，但其混合分布不受這種約束，因此邊際后驗分布通常是隱含的，沒有解析密度函數(shù)更具表現(xiàn)力。層次結(jié)構(gòu)的邊緣是隱式的也很常見，即使后驗分布和混合分布都是顯式的。我們將SIVI集成到我們的新模型中，為動態(tài)圖推斷更靈活和可解釋的節(jié)點嵌入。

Variational graph recurrent neural network (VGRNN)

我們考慮一個動態(tài)圖，其中是時間步長t的圖，分別是相應(yīng)的節(jié)點和邊集。在本文中，我們旨在開發(fā)一個與節(jié)點和邊緣集中的潛在變化普遍兼容的模型。和之間的關(guān)系沒有約束，即新節(jié)點可以加入動態(tài)圖并創(chuàng)建現(xiàn)有節(jié)點的邊，或者以前的節(jié)點可以從圖中消失。

另一方面，快照之間可以形成新的邊，而現(xiàn)有邊可以消失。設(shè) Nt 表示節(jié)點的數(shù)量，即 在時間步長 t 的基數(shù)。因此，VGRNN可以將可變長度鄰接矩陣序列作為輸入。此外，在考慮節(jié)點屬性時，可以在不同的快照上觀察到不同的屬性，具有可變長度節(jié)點屬性序列 。請注意，分別是 Nt × Nt 和 Nt × M 矩陣，其中 M 是節(jié)點屬性的維度，該維度隨時間變化是恒定的。受變分遞歸神經(jīng)網(wǎng)絡(luò)（VRNN）的啟發(fā)，我們通過集成GRNN和VGAE來構(gòu)建VGRNN，以便充分和同時地對拓撲和節(jié)點屬性動力學(xué)之間的復(fù)雜依賴關(guān)系進行建模。此外，每個節(jié)點在每個時間都用分布表示，因此在VGRNN中也對節(jié)點潛在表示的不確定性進行了建模。

VGRNN model

VGRNN 模型采用 VGAE 對每個圖形快照進行建模。VGAEs在時間范圍內(nèi)以狀態(tài)變量ht?1為條件，由GRNN建模。這樣的架構(gòu)設(shè)計將幫助每個VGAE考慮動態(tài)圖的時間結(jié)構(gòu)。更重要的是，與標(biāo)準VGAE不同，VGRNN中的VGAE通過允許分布參數(shù)通過前一個時間步的信息的顯式或隱式復(fù)雜函數(shù)進行建模，從而在潛在隨機變量上采用新的先驗。更具體地說，VGRNN 中的 VGAE 不是強加具有確定性參數(shù)的標(biāo)準多元高斯分布，而是根據(jù)先前時間步中的隱藏狀態(tài)學(xué)習(xí)先驗分布參數(shù)。因此，我們的VGRNN允許更靈活的潛在表示，具有更大的表達能力，可以捕獲拓撲和節(jié)點屬性演化過程之間和內(nèi)部的依賴關(guān)系。特別是，我們可以將實驗中采用的先驗分布的構(gòu)造寫成如下：
其中，和
表示條件先驗分布的參數(shù)。

此外，生成分布將以為條件：

其中π（t）表示生成分布的參數(shù);φ^prior和φ^dec可以是任何高度靈活的函數(shù)，例如神經(jīng)網(wǎng)絡(luò)。

另一方面，骨干GRNN可以靈活地對復(fù)雜的依賴關(guān)系進行建模，包括圖拓撲動力學(xué)和節(jié)點屬性動力學(xué)。GRNN 使用遞歸方程更新其隱藏狀態(tài)：

其中 f 最初是方程 （1） 的轉(zhuǎn)移函數(shù)。與GRNN不同，圖拓撲可以在不同的時間步長中發(fā)生變化，就像在現(xiàn)實世界的動態(tài)圖中一樣，并且鄰接矩陣A（t）在VGRNN中是時間相關(guān)的。為了進一步增強表達能力，φ^x和φ^z為深度神經(jīng)網(wǎng)絡(luò)，它們在每個節(jié)點上獨立運行，并分別從X^（t）和Z^（t）中提取特征。這些特征提取器對于學(xué)習(xí)復(fù)雜的圖形動力學(xué)至關(guān)重要。基于 （4），ht 是 的函數(shù)。因此，方程 （2） 和 （3） 中的先驗分布和生成分布分別定義了分布和。生成模型可以分解為
其中第一個快照的先驗被認為是標(biāo)準多元高斯分布，即。此外，如果在快照 t 處將一個以前未觀察到的節(jié)點添加到圖中，我們認為該節(jié)點在快照 t ? 1 處的隱藏狀態(tài)為零，因此該節(jié)點在時間 t 處的先驗狀態(tài)為 N （0， I）。如果發(fā)生節(jié)點刪除，我們假設(shè)節(jié)點的標(biāo)識可以保持，因此刪除一個節(jié)點，相當(dāng)于刪除了與其連接的所有邊，不會影響下一步的先前構(gòu)造。更具體地說，A和X的大小可以隨時間變化，而它們的潛在空間會隨時間而保持。

Semi-implicit VGRNN (SI-VGRNN)

為了進一步提高VGRNN變分后驗的表達能力，我們引入了aSI-VGRNN動態(tài)節(jié)點嵌入模型。我們對 （8） 中的變分分布參數(shù)施加了混合分布，以使用半隱式分層結(jié)構(gòu)對 VGRNN 的后驗進行建模：
雖然變分分布 需要顯式，但混合分布 q_φ 不受這種約束，導(dǎo)致相當(dāng)靈活的 。更具體地說，SI-VGRNN 通過圖形神經(jīng)網(wǎng)絡(luò)轉(zhuǎn)換隨機噪聲 t 從 qφ 中提取樣本，這通常會導(dǎo)致 qφ 的隱式分布。文章來源地址http://www.zghlxwxcb.cn/news/detail-481781.html

到了這里，關(guān)于【論文導(dǎo)讀】- Variational Graph Recurrent Neural Networks（VGRNN）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！