姜 山,丁治明,朱美玲,嚴 瑾,徐馨潤

1(中國科學院大學,北京 100049)

2(中國科學院 軟件研究所,北京 100190)

3(大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點實驗室,北京 100190)

時空圖建模(spatiotemporal graph modeling,簡稱STGM)是分析系統(tǒng)中各組件的空間關(guān)系和時間趨勢的一項重要技術(shù),時空圖建模技術(shù)屬于圖數(shù)據(jù)管理領域中有關(guān)圖結(jié)構(gòu)數(shù)據(jù)的上層應用.如圖1 所示:在時空圖中,每個節(jié)點都有動態(tài)輸入特征.時空圖建模的目標是:在給定圖結(jié)構(gòu)的情況下,對每個節(jié)點的動態(tài)特征進行建模.這里的屬性特指圖結(jié)構(gòu)中節(jié)點的信號輸入屬性特征,如建模圖結(jié)構(gòu)下各節(jié)點的特征變化趨勢,從而完成對圖節(jié)點特征的預測分析.此外,時空圖建模技術(shù)具有廣泛的應用場景,比如對城市道路交通參數(shù)預測[1]、出租車需求量預測[2]、行為識別[3]等.近年來,在深度學習技術(shù)的成功推動下,研究人員借鑒卷積網(wǎng)絡(convolution neural network,簡稱CNN)[4]、循環(huán)神經(jīng)網(wǎng)絡(recurrent neural network,簡稱RNN)[5]和深度自動編碼器(deep autoencoder,簡稱DAE)[6]的思想,定義和設計了用于處理圖結(jié)構(gòu)數(shù)據(jù)的神經(jīng)網(wǎng)絡模型[7].隨著圖神經(jīng)網(wǎng)絡的發(fā)展,時空圖建模越來越受到研究者的廣泛關(guān)注.

Fig.1 Spatiotemporal graph modeling圖1 時空圖建模

時空圖建模是通過圖中節(jié)點間的依賴關(guān)系構(gòu)建圖節(jié)點的動態(tài)輸入[8].特別地,在城市道路短時交通速度和流量預測中,將安置在城市道路上的各個探測傳感器看作是節(jié)點,那么布置在城市路網(wǎng)的交通傳感器就構(gòu)成一個圖形結(jié)構(gòu),圖中節(jié)點的連接邊是通過兩個節(jié)點的歐式距離來判定.由于城市道路中各交通參數(shù)受各種因素制約,比如一條道路上的交通過度擁擠將會導致進入該道路的前序道路交通速度的降低,即一條道路的參數(shù)狀態(tài)會影響其相連接的另一輸入道路的交通狀態(tài),因此在對每條道路上的交通參數(shù)時間序列數(shù)據(jù)進行建模時,理應將城市交通探測系統(tǒng)構(gòu)成的圖形結(jié)構(gòu)作為一種固有結(jié)構(gòu)先驗知識來建模節(jié)點間相互依賴關(guān)系.

圖結(jié)構(gòu)具有豐富的空間屬性模式,對圖中各節(jié)點賦予時間依賴,則其就成為時空圖結(jié)構(gòu).如何同時捕捉圖的空間和時間相關(guān)性,是時空圖建模研究的核心難點問題.時空圖建模的傳統(tǒng)方法要么集中在圖結(jié)構(gòu)的關(guān)系性建模上,要么集中在節(jié)點級的時序建模上,往往忽略節(jié)點的空間關(guān)聯(lián)關(guān)系和時間關(guān)聯(lián)關(guān)系.由于現(xiàn)實世界中各網(wǎng)絡節(jié)點不僅受當前狀態(tài)的影響,還要受到其領域節(jié)點的影響,此外還要受到歷史狀態(tài)累積的影響,因此,未考慮節(jié)點間的時空依賴關(guān)系的傳統(tǒng)建模方法顯然是不能捕獲節(jié)點間的長時間時空趨勢.本文主要瞄準于靜態(tài)網(wǎng)絡場景下的時空圖建模,旨在同時捕獲圖結(jié)構(gòu)隱藏的時空依賴關(guān)系,并對節(jié)點特征進行預測分析.本文在圖譜卷積操作的基礎上,針對現(xiàn)有時空圖建模的問題現(xiàn)狀,研究并提出了一個基于圖小波卷積神經(jīng)網(wǎng)絡的時空圖建模方法,稱為GWNN-STGM(graph wavelet convolutional neural network for spatiotemporal graph modeling).

在GWNN-STGM 模型中設計了一個圖小波卷積神經(jīng)網(wǎng)絡層,并在該網(wǎng)絡層中設計并引入了一個自適應鄰接矩陣進行節(jié)點嵌入學習,使得模型能夠在不需要結(jié)構(gòu)先驗知識的情況下,從數(shù)據(jù)集中自動發(fā)現(xiàn)隱藏的結(jié)構(gòu)信息.此外,采用堆疊的擴張因果卷積來捕獲圖節(jié)點的時間相關(guān)性.隨著隱含層數(shù)目的增加,堆疊式的擴張因果卷積神經(jīng)網(wǎng)絡(dilated causal convolutional neural network,簡稱DCCNN)[9]的感受野大小呈指數(shù)級增長.因此,GWNN-STGM 利用堆疊的擴張因果卷積處理具有長時序列的時空圖形數(shù)據(jù),能夠有效地捕獲圖節(jié)點的時間相關(guān)性.

1 相關(guān)研究工作

1.1 時空圖建模

STGM 是分析系統(tǒng)中各組件的空間關(guān)系和時間趨勢的一項重要技術(shù).在對時空圖建模過程中,通常假設各對象之間的顯式連接關(guān)系是預先確定的,現(xiàn)有的方法大多捕捉固定圖形結(jié)構(gòu)的空間依賴性,但是這種顯式圖結(jié)構(gòu)不一定能夠真實地反映節(jié)點間依賴關(guān)系,并且由于數(shù)據(jù)中存在不完整的連接,可能會丟失隱藏的空間連接關(guān)系.得力于深度學習技術(shù)的發(fā)展,目前,研究者對時空圖建模的研究主要分為兩個方向[8]:一類是將圖卷積網(wǎng)絡(graph convolutional neural network,簡稱GCN)集成到RNN 中,從而構(gòu)建圖卷積遞歸神經(jīng)網(wǎng)絡;另一類是將GCN集成到CNN 中,構(gòu)建圖卷積神經(jīng)網(wǎng)絡.歸納起來,這兩類方法要么將GCN 集成到RNN 中,要么將GCN 集成到CNN 中.現(xiàn)有的時空圖建模方法雖然能夠有效地將圖形結(jié)構(gòu)信息進行整合,但是也存在兩個明顯的缺點.

? 首先,現(xiàn)有的時空圖建模都是在假設數(shù)據(jù)的圖形結(jié)構(gòu)能夠反映節(jié)點之間真實依賴關(guān)系的情況下進行建模,但是在面對節(jié)點間的連接不需要參考兩個節(jié)點之間的相互依賴關(guān)系時以及兩個節(jié)點之間沒有連接但是存在相互依賴關(guān)系時,這樣的建模方法顯然不可取.這樣的情況在推薦系統(tǒng)中是較為常見的,比如:兩個用戶是具有連接關(guān)系的,但是他們可能對產(chǎn)品有不同的偏好程度;兩個用戶具有相似的產(chǎn)品偏好,但是他們沒有連接關(guān)系;

? 其次,目前對時空圖建模的研究還不能有效地捕獲時間相關(guān)性特征.雖然有學者通過引入注意模型[10]來動態(tài)調(diào)整圖中節(jié)點間的連接權(quán)重,一定程度上解決了空間相關(guān)性的建模,但是缺乏對時間相關(guān)性的建模.有學者將RNN 和長短期記憶網(wǎng)絡(long short-term memory,簡稱LSTM)模型引入到時空圖建模問題中[11?13],但是在處理長距離序列數(shù)據(jù)時往往需要非常耗時的迭代計算,并且存在梯度消失情況.

此外,近年來,動態(tài)圖神經(jīng)網(wǎng)絡在建?；虿蹲骄W(wǎng)絡的結(jié)構(gòu)和性質(zhì)方面取得了新的進展[14],相比于靜態(tài)網(wǎng)絡來說,動態(tài)圖神經(jīng)網(wǎng)絡強調(diào)了網(wǎng)絡中節(jié)點和邊的出現(xiàn)順序和時間.因此,節(jié)點的鄰域并不是同時形成的,得到的快照網(wǎng)絡結(jié)構(gòu)是一段時間內(nèi)鄰域的累積結(jié)構(gòu).雖然動態(tài)圖神經(jīng)網(wǎng)絡能夠建模動態(tài)圖結(jié)構(gòu),但是需要動態(tài)記錄每個時間戳下的圖結(jié)構(gòu),在生物分子領域、醫(yī)藥等領域有著非常大的應用場景.對于圖網(wǎng)絡結(jié)構(gòu)變化不明顯的應用場景下,動態(tài)記錄圖網(wǎng)絡結(jié)構(gòu)是不明智的,如交通路網(wǎng),因為道路網(wǎng)絡物理狀態(tài)多為固定模型.

1.2 圖卷積神經(jīng)網(wǎng)絡

圖卷積網(wǎng)絡已經(jīng)被證明是圖形上一類函數(shù)的通用逼近器[7],并且已成功應用于多種學習任務,包括圖節(jié)點嵌入[15]、圖節(jié)點間的鏈接預測[16]和圖分類[17]等.圖卷積網(wǎng)絡有力地推動了對圖結(jié)構(gòu)的學習和建模的能力.圖卷積網(wǎng)絡有兩大主流:基于頻譜的方法和基于空間的方法.基于頻譜的方法在頻域中從圖信號處理的角度引入濾波器來定義圖卷積,其中,圖卷積操作被定義為從圖信號中去除噪聲.基于空間的方法將圖卷積表示為從圖中節(jié)點鄰域聚合節(jié)點的特征信息,并進行特征信息更新.特別地,當圖卷積網(wǎng)絡的算法在圖節(jié)點層級運行時,通常將圖池化(graph pooling)[18]模塊與圖卷積層進行交錯運算,更進一步地將圖特征信息向更深層次轉(zhuǎn)化,最終形成更高級別的圖形結(jié)構(gòu).無論是基于頻譜的方法還是基于空間的方法,圖的鄰接矩陣通常被認為是先驗知識,這種先驗知識是以結(jié)構(gòu)的形式存在,并且在學習訓練過程中是固定不變的,或者是不經(jīng)常變動的.文獻[19]提出利用高斯核函數(shù)來學習圖結(jié)構(gòu)中節(jié)點鄰居的權(quán)重.文獻[20]將注意力模型引入到圖卷積神經(jīng)網(wǎng)絡模型,通過利用注意力機制更新圖中節(jié)點鄰居的權(quán)重參數(shù),從而完成動態(tài)調(diào)整圖的結(jié)構(gòu).文獻[21]設計了一個圖節(jié)點自適應信息傳輸路徑網(wǎng)絡層,并用這個網(wǎng)絡層來提取圖中節(jié)點鄰域的信息,從而為更新節(jié)點連接關(guān)系提供節(jié)點的依賴信息.針對圖形結(jié)構(gòu)數(shù)據(jù)的分類問題,文獻[22]設計了基于距離度量的自適應學習圖形的鄰接矩陣,學習生成的鄰接矩陣受圖節(jié)點輸入信息的約束.盡管這些圖神經(jīng)網(wǎng)絡學習方法能夠?qū)W習圖結(jié)構(gòu),但是他們都必須依賴于預先定義好的圖結(jié)構(gòu).由于時空圖的輸入是動態(tài)的,這些建模方法仍然不能同時捕捉圖的空間和時間相關(guān)性.因此,迫切需要設計一種同時捕獲空間和時間相關(guān)關(guān)系的時空圖建模模型與方法.

1.3 圖小波卷積神經(jīng)網(wǎng)絡

盡管基于空間的方法構(gòu)建的圖卷積神經(jīng)網(wǎng)絡取得了一些初步的成功,并提供了一個將歐式空間的CNN 推廣到圖形數(shù)據(jù)結(jié)構(gòu)的統(tǒng)一靈活框架,但是如何確定節(jié)點的合適鄰域大小,仍然是一個難點問題.相比于基于空間的方法,基于圖譜的方法構(gòu)建的圖卷積是通過圖傅里葉變換和卷積定理定義卷積操作.基于圖譜的方法利用圖的傅里葉變換將圖節(jié)點域中定義的信號轉(zhuǎn)換為頻譜域,如基于圖的Laplacian 矩陣的特征向量所張成的空間,然后在頻譜域中定義濾波器,并對圖信息進行濾波操作,這樣就保持與CNN 類似的權(quán)重共享特性.但是需要求解圖的特征向量,當圖較大時,對圖的Laplacian 矩陣特征分解是非常耗時的.

文獻[23]利用圖小波變換替代圖傅里葉變換,定義了譜圖卷積并提出了圖小波神經(jīng)網(wǎng)絡.該模型無需進行圖的Laplacian 矩陣特征分解運算,有效地降低了神經(jīng)網(wǎng)絡的計算資源的消耗.圖小波神經(jīng)網(wǎng)絡與頻譜神經(jīng)網(wǎng)絡的區(qū)別在于圖小波神經(jīng)網(wǎng)絡具有明顯3 個優(yōu)點.

(1)不需要對Laplacian 矩陣進行特征分解就可以快速得到圖小波矩陣,因此效率明顯提升;

(2)圖小波矩陣是稀疏的,而Laplacian 矩陣的特征向量構(gòu)成的矩陣多是稠密的.相比于圖傅里葉變換操作,圖小波變換操作可以更加容易使用稀疏運算庫,因此具有更高的計算效率;

(3)圖小波網(wǎng)絡在節(jié)點域具有局部化特性,反映了以每個節(jié)點為中心的信息擴散.

盡管圖小波神經(jīng)網(wǎng)絡能夠一定程度上解決圖譜圖卷積網(wǎng)絡的計算效率問題,并且具有一定的局部特性,這種特性對圖的空間相關(guān)性建模是有利的,但是仍然缺乏時空圖建模的能力.

1.4 時空圖網(wǎng)絡

時空圖建模方法可以劃歸為兩類:一類是基于遞歸神經(jīng)網(wǎng)絡層(RNN)構(gòu)建的圖卷積遞歸神經(jīng)網(wǎng)絡;另一類是將基于卷積神經(jīng)網(wǎng)絡層(CNN)構(gòu)建的圖卷積神經(jīng)網(wǎng)絡.基于RNN 構(gòu)建的圖卷積網(wǎng)絡主要是通過利用圖卷積操作運算對傳遞給RNN 單元的輸入和隱狀態(tài)進行濾波處理,并以此來建模圖的時空依賴關(guān)系.

文獻[14]針對圖鏈接預測和節(jié)點分類的問題,通過使用RNN 建模GCN 參數(shù)變化狀態(tài)來捕獲圖序列的動態(tài)性,無需借助節(jié)點嵌入運算沿時間維度進行圖卷積處理.文獻[12]通過使用圖卷積對傳遞給RNN 單元的輸入和隱狀態(tài)進行濾波來捕獲時空依賴性,該方法能夠?qū)Χ虝r的圖序列數(shù)據(jù)進行時空建模,但是無法處理較長時間的數(shù)據(jù).文獻[24]將自然語言處理領域中時空注意機制引入到圖卷積神經(jīng)網(wǎng)絡中,并適當提高了圖卷積神經(jīng)網(wǎng)絡模型對時空圖數(shù)據(jù)的建模的性能.文獻[25]提出了一種快速圖卷積神經(jīng)網(wǎng)絡模型結(jié)構(gòu),用于預測具有圖結(jié)構(gòu)的數(shù)據(jù)序列.結(jié)合有門控RNN 單元和圖卷積層的新模型架構(gòu),其可以提高訓練階段的數(shù)值穩(wěn)定性,但是依然涉及大量的待訓練參數(shù),在短時序列數(shù)據(jù)時空建模具有較好性能.基于RNN 的圖卷積神經(jīng)網(wǎng)絡方法的最主要缺點是對于長時序列來說效率明顯降低,并且在與圖卷積網(wǎng)絡相結(jié)合時,存在梯度爆炸現(xiàn)象,訓練階段不易收斂.文獻[26]針對稀疏的、無結(jié)構(gòu)的和無序的點云數(shù)據(jù)分類預測的問題,提出一種鏈接動態(tài)圖神經(jīng)網(wǎng)絡模型,對點云數(shù)據(jù)進行分類和分段預測.該模型凍結(jié)特征提取器,使用動態(tài)圖鏈接圖的層次特征,并重新訓練分類器,很大程度上提高了網(wǎng)絡模型的預測性能.

基于RNN 的圖卷積神經(jīng)網(wǎng)絡和基于CNN 的圖卷積神經(jīng)網(wǎng)絡的模型方法在保持較好的計算結(jié)果的同時,都需要進行多層疊加或者使用圖的池化模塊來擴大圖卷積神經(jīng)網(wǎng)絡模型的接受域或感受野,因此也帶來了更高的計算消耗,計算效率有待進一步提升.

2 時空圖建模方法

文中首先給出了時空圖建模問題的形式化定義,其次詳細介紹了圖譜卷積、圖小波卷積和時間卷積,最后給出了本文設計的用于時空圖建模的總體模型架構(gòu).

2.1 相關(guān)定義及說明

圖(graph)定義.圖一般表示為G=(V,E,A),其中,V是圖G的節(jié)點集合,E是圖G中邊的集合,A是圖G中的鄰接矩陣.使用vi∈V表示圖的第i個節(jié)點,eij=(vi,vj)∈E表示圖G中節(jié)點vi指向節(jié)點vj的連接邊,|V|=n和|E|=m分別表示圖G中的節(jié)點集合V的元素數(shù)量和邊集合E的元素數(shù)量.A∈Rn×n,鄰接矩陣A中元素滿足公式:

對于給定圖G和它的鄰接矩陣A,則圖G的拉普拉斯矩陣L∈Rn×n表示為

圖屬性(graph attribute)定義.在圖G中,每個節(jié)點都有各自的信號特征或?qū)傩蕴卣?一般用矩陣X∈Rn×d表示圖G的屬性特征,表示圖G中節(jié)點vi的屬性向量,具有圖屬性特征的圖稱為屬性圖(attributed graph).

時空圖(spatiotemporal graph)定義.時空圖表示為Gt=(V,E,Xt),Xt∈Rn×d.時空圖是在一般圖上進行擴展定義的,其中,節(jié)點的屬性矩陣Xt是隨時間t呈動態(tài)變化狀態(tài).

問題描述:在給定一個圖G和它的H個歷史屬性特征情況下,求解未來N個時間步長下圖G的屬性特征矩陣,即求解一個映射函數(shù)f使其滿足如下關(guān)系:

其中,Xt?H?1,…,t∈Rn×d×H,Xt+1,…,t+N∈Rn×d×N.

2.2 圖譜卷積層

由于圖結(jié)構(gòu)沒有類似于歐式空間中圖像數(shù)據(jù)的自然連接順序,因此標準卷積運算不能直接用于圖結(jié)構(gòu)的非歐式空間數(shù)據(jù).圖卷積的形式化圖譜定義[27]的提出,為圖形式結(jié)構(gòu)數(shù)據(jù)的處理提供了一個嶄新的思路,將深度學習中常用于圖像的卷積運算擴展到圖數(shù)據(jù)上.圖譜方法是通過圖傅里葉變換和卷積定理來定義卷積操作.圖譜卷積是利用圖的傅里葉變換將圖節(jié)點域中定義的圖信號或特征變換至頻譜域中,再利用圖頻域濾波理論進行特征提取處理,最后將信號進行逆變換至節(jié)點域的重要操作.圖譜卷積層定義為

其中,*G表示圖卷積操作運算符,ke為卷積核,此處的x∈Rn為圖G上的信號,⊙為矩陣的Hadamard 乘積,gθ為濾波核,U為圖G的拉普拉斯矩陣L的特征向量矩陣.在圖譜域中,稱為圖傅里葉變換,稱為圖傅里葉逆變換.按照公式(4)定義的圖譜卷積存在明顯的缺陷.

? 首先,需要求解拉普拉斯矩陣L的特征值數(shù)組和特征向量矩陣,計算很耗時,計算復雜度為O(n3),不適用于大圖運算;

? 其次,求解出來的U和UT為稠密矩陣,在進行傅里葉變換運算時效率低下;

? 最后,基于圖傅里葉變換定義的卷積操作覆蓋整個圖的節(jié)點域,卷積操作不具備局部鄰域特性.

針對上述缺陷,文獻[27]提出了利用切比雪夫多項式K階截斷來近似濾波核gθ,如下:

其中,θ∈RK是切比雪夫近似多項式系數(shù)向量.但是,公式(5)定義的卷積濾波核具有一定的限制性,這不利于對在圖上定義更一般的卷積運算.比如對切比雪夫多項式K階截斷時,K越大,越不利于保持卷積的局部鄰域特性;而K越小,又很難近似濾波核gθ,且使得近似誤差增大.

利用圖小波變換來代替圖傅里葉變換來定義圖譜卷積,如下:

其中,ψs=UGsUT=(ψs1,ψs2,…,ψsn),為尺度矩陣[28],表明熱擴散核函數(shù)尺度范圍;s為尺度參數(shù),控制節(jié)點鄰域范圍.在圖譜域中,稱為圖小波變換,圖小波逆變換.ψs和可以通過SGWT[29]算法進行快速的多項式近似求解,其計算復雜度為O(mK),K為切比雪夫多項式階數(shù).ψs和通常是稀疏的,可以進行稀疏矩陣運算,同時又是局部的,每個圖小波對應于圖上的一個信號,該信號從一個中心節(jié)點向外部擴散出去,受尺度參數(shù)s的靈活控制,所以在節(jié)點域具有局部特性.

與基于圖傅里葉變換定義的圖卷積操作相比,基于圖小波變換定義圖卷積具有更高的計算效率.充分利用圖小波變換的優(yōu)勢,我們定義圖小波卷積操作如下:

其中,W∈Rd×q是待學習的參數(shù)矩陣,Θ∈Rn×n是圖卷積核的對角矩陣,

為了學習時空圖的空間依賴項和圖小波卷積網(wǎng)絡隱藏層的空間依賴項,我們定義了自適應鄰接矩陣,并將其引入到圖小波卷積層中,自適應鄰接矩陣無需圖的結(jié)構(gòu)先驗信息,直接從數(shù)據(jù)集中自學習,動態(tài)關(guān)聯(lián)和發(fā)現(xiàn)網(wǎng)絡隱藏層的空間依賴關(guān)系.自適應鄰接矩陣定義如下:

其中,Us∈Rn×r為源節(jié)點信息的動態(tài)嵌入矩陣和Ut∈Rn×r為目標節(jié)點信息的動態(tài)嵌入矩陣,為源節(jié)點與目標節(jié)點間的空間依賴權(quán)重.其中,α和β分別為SoftMax 函數(shù)和ReLu 函數(shù),它們的作用分別是消除弱空間依賴關(guān)系和對空間依賴關(guān)系進行規(guī)范化處理,從而減小不平衡現(xiàn)象造成的誤差.引入自適應鄰接矩陣后,我們修改公式(7),并定義新的圖小波卷積層如下:

公式(10)定義的圖卷積可解釋為匯聚來自不同階鄰域的變換特征信息,因此用其捕獲隱藏的空間相關(guān)性.

2.3 時間卷積層

在時空圖建模中,另一個最重要的任務是進行時間相關(guān)性的建模.采用擴展因果卷積(dilated causal convolution,簡稱DCC)[9]作為時間卷積層來捕捉圖節(jié)點的時間趨勢.特別地,在擴展因果卷積網(wǎng)絡中,允許通過增加網(wǎng)絡層深度來獲得指數(shù)級增長的感受野,從而有效擴大對時序列數(shù)據(jù)處理的歷史范圍.具體而言,擴展因果卷積是在因果卷積基礎上引入擴展率,通過跳過部分輸入來使濾波核可以應用于大于濾波核本身長度的區(qū)域,并且擴展率隨著層深度進行指數(shù)級增長,因此感受野也隨著增大.

假設在節(jié)點vi,給定一個1 維時間序列x∈RH和一個濾波核,則擴展因果卷積定義如下:

其中,*dc為擴展因果卷積運算符;K*為擴展因果卷積核尺寸大小;d為擴展因子(dilation factor,簡稱DF),d數(shù)值的大小控制著跳躍距離,即每d步就選擇一個輸入.

為了更加清晰地描述擴展因果卷積的作用,我們將因果卷積與擴展因果卷積進行示意,如圖2 所示.在圖2中,通過疊加多個卷積層,以增加卷積運算的感受域.對于給定圖中節(jié)點vi的歷史特征序列,在具有同樣的網(wǎng)絡層數(shù)的情況下,因果卷積(如圖2 左所示)的感受域明顯小于擴展因果卷積(如圖2 右所示)的感受域.一般情況下,在擴展因果卷積層中,隨著卷積層數(shù)的加深,擴展因子成指數(shù)增加,模型的感受域也成指數(shù)增大.在圖2 中,擴展因果卷積感受野在每一層上分別擴大了1 倍、2 倍和4 倍.使得通過堆疊有限深度的網(wǎng)絡層,擴展因果卷積就能夠捕獲較長序列數(shù)據(jù)間的相關(guān)性,從而有效節(jié)省了計算資源.與基于RNN 的方法相比,DCC 具有明顯的優(yōu)勢,DCC能夠以非遞歸的方式處理長時序列數(shù)據(jù),這種非遞歸的處理方式有利于并行加速,同時,擴展因果卷積有效緩解了梯度爆炸問題[5].

Fig.2 Schematic diagram of causal convolution (left)and dilated causal convolution (right)圖2 因果卷積(左)與擴展因果卷積(右)示意圖

門控機制(gating mechanism)在對序列數(shù)據(jù)建模問題中被證明是有效的[5],為了能夠充分建模時間維度上的非線性關(guān)系,引入門控機制,并定義門控時間卷積層,定義如下:

其中,Θ1和Θ1為模型待學習參數(shù);⊙為矩陣的Hadamard 乘積;δ和σ分別為Tanh 函數(shù)和Sigmod 函數(shù),原則上可以將δ和σ的定義式可以推廣至其他任意激活函數(shù)形式.Tanh 函數(shù)和Sigmod 函數(shù)曲線如圖3 所示.

Fig.3 Curves between Tanh and Sigmod圖3 Tanh 函數(shù)和Sigmod 函數(shù)曲線

2.4 面向時空圖的圖小波卷積神經(jīng)網(wǎng)絡總體架構(gòu)

本節(jié)將描述面向時空圖建模的圖小波卷積神經(jīng)網(wǎng)絡總體架構(gòu),該架構(gòu)將圖小波卷積層和門控時間卷積層結(jié)合起來,完成屬性圖的時空關(guān)系建模和預測.網(wǎng)絡模型結(jié)構(gòu)定義如下.

? 輸入層(或第0 層):

? 第l卷積層:

(1)門控時間卷積運算

(2)圖小波卷積運算

? 輸出層:

其中,ReLU為非線性激活函數(shù)[30],Y∈Rn×d×N,L為架構(gòu)的總卷積層數(shù),MLP為多層感知機或線性全連接層[31].

面向時空圖建模的圖小神經(jīng)網(wǎng)絡總體架構(gòu)通過疊加多個時空層,以處理不同時間層次的空間依賴關(guān)系.即:在最淺層,圖卷積接收短期時間信息;在最深層,圖卷積處理長期時間信息.選擇平均絕對誤差(mean absolute error,簡稱MAE)為模型的目標函數(shù),并使用梯度下降法進行訓練.MAE定義如下:

3 實驗分析

本節(jié)主要對本文提出的模型進行實驗分析,實驗中選用公共交通網(wǎng)絡數(shù)據(jù)集METR-LA 和PEMS-BAY[5]對模型進行驗證.實驗數(shù)據(jù)中,數(shù)據(jù)記錄的采樣間隔是5 分鐘,METR-LA 中共有207 個網(wǎng)絡傳感器節(jié)點(或網(wǎng)絡圖節(jié)點)和1 515 個邊,PEMS-BAY 中共有325 個網(wǎng)絡傳感器節(jié)點和2 369 個邊.本實驗按照采樣時間順序?qū)W(wǎng)絡節(jié)點屬性特征數(shù)據(jù)進行提取,并按照訓練數(shù)據(jù)集:驗證數(shù)據(jù)集:測試數(shù)據(jù)集為7:1:2 的比率策略進行數(shù)據(jù)集劃分,在訓練過程中對數(shù)據(jù)集進行了隨機shuffle操作,實驗中采用與文獻[8]一致的膨脹因子的參數(shù)設置.

3.1 實驗相關(guān)參數(shù)設置

本實驗運行環(huán)境為Intel(R)Xeon(R)Gold 5218CPU@2.30GHz,NVIDIA GeForce GTX2080GPU,顯存32GB.設置歷史觀測步長和預測窗口大小均為12,即利用過去一小時時段(12×5 分鐘)的觀測值來預測下一個小時的特征.模型中卷積層數(shù)l=2,M=2.訓練過程中對參數(shù)數(shù)量采用隨機丟棄策略,丟棄率(dropout rate)設置為0.3.采用隨機初始化方式對模型中的參數(shù)進行初始化,模型的訓練優(yōu)化器為Adam,并且學習率設置為0.0001.

3.2 實驗對照的基準方法

為測試模型的性能,我們選用ARIMA,DCRNN[32],STGCN[33],Graph WaveNet[8]模型作為參考基準模型進行對比實驗,具體描述見表1.在實驗過程中,選用平均絕對誤差(mean absolute errors,簡稱MAE)、平均絕對百分比誤差(mean absolute percentage errors,簡稱MAPE)和均方根誤差(root mean squared errors,簡稱RMSE)這3 種度量函數(shù)為模型性能的評估指標.

Table 1 Experimental baseline models表1 實驗對照的基準方法模型

3.3 實驗結(jié)果分析

3.3.1 模型性能對比分析

基于METR-LA 和PEMS-BAY 實驗數(shù)據(jù),表2 給出了設計的模型和基線模型的性能統(tǒng)計結(jié)果.表2 中分別列出了15 分鐘預測、30 分鐘預測和60 分鐘預測的誤差值(或稱性能).可以明顯地看出,本文提出的模型在兩個數(shù)據(jù)集上都取得了較好的性能結(jié)果.

Table 2 Performance comparison of our model and other baseline models表2 設計的模型與基準模型的性能對比

具體地,本文提出的模型比時間模型ARIMA 有很大的優(yōu)勢.在表2 中,60 分鐘時窗的模型預測MAE 數(shù)值在兩個實驗數(shù)據(jù)集上均比時間模型ARIMA 要低49.71%(METR-LA)和43.44%(PEMS-BAY).與時空模型相比,本文的神經(jīng)網(wǎng)絡模型性能均優(yōu)于Graph WaveNet 模型、STGCN 模型和DCRNN 網(wǎng)絡模型.與基準模型集中性能最佳的Graph WaveNet 模型相比,可以看出,在15 分鐘預測時,本文的模型僅取得了較小的性能提升;在數(shù)據(jù)集METR-LA 和PEMS-BAY 上,MAE 均只降低了0.01.在30 分鐘時長窗口期下,本文模型的MAE 在METR-LA 和PEMS-BAY 數(shù)據(jù)集上分別降低了0.03 和0.04.但是隨著預測時間窗口的增大,在60 分鐘預測時長窗口期下,我們模型的MAE 分別降低了0.05 和0.8.這表明:本文提出的模型具有更大的時空作用域,特別是模型中疊加了門控時間卷積層,該層使用擴張因果卷積和門控機制,擴張因果卷積層能使模型的感受野成指數(shù)增加,并使我們的模型能處理更大時長的數(shù)據(jù),這個特性對于時空關(guān)系建模非常有利.此外,統(tǒng)計了本文模型與最佳基準模型Graph WaveNet[8]在預測時間窗口序列N={1,2,…,12}中的平均性能結(jié)果,見表3.在實驗數(shù)據(jù)集METR-LA 上,本文設計的模型性能數(shù)值MAE,RMSE 和MAPE 分別比Graph WaveNet 模型的性能數(shù)值低0.07%,0.02%和1.8%.在PEMS-BAY 上,模型的性能依然取得了提升.因此,本文提出的模型更適合于屬性圖網(wǎng)絡的時空關(guān)系預測.

Table 3 Comparison of average performance with the best benchmark model in the prediction window area表3 在預測窗口區(qū)內(nèi)與最佳基準模型的平均性能對比

3.3.2 自適應鄰接矩陣對模型作用分析

在模型中,為了學習時空圖的空間依賴項和圖小波卷積網(wǎng)絡隱藏層的空間依賴項,我們設計了自適應鄰接矩陣,并將其引入到圖小波卷積層中,直接從數(shù)據(jù)集中以端到端的形式自學習,動態(tài)關(guān)聯(lián)和發(fā)現(xiàn)網(wǎng)絡隱藏層的空間依賴關(guān)系.圖4～圖6 分別繪制了引入自適應鄰接矩陣網(wǎng)絡模型(gwcn-Ady)和未引入自適應鄰接矩陣網(wǎng)絡模型(gwcn),在METR-LA 數(shù)據(jù)集上的不同預測時間窗口區(qū)內(nèi)的平均絕對誤差MAE、平均絕對百分比誤差MAPE和均方根誤差RMSE 性能曲線.在預測窗口時間長為5 分鐘時,引入矩陣和未引入矩陣的模型在MAE,MAPE 和RMSE 上的性能均差別很小,這表明自適應鄰接矩陣對短時預測性能提升作用不明顯.隨著預測時長的增加,引入自適應鄰接矩陣的模型性能與未自適應鄰接矩陣的模型性能之間的差異也在增大,在60 分鐘時長預測時,引入矩陣的模型性能優(yōu)勢較為明顯.這表明,引入自適應鄰接矩陣能夠有助于關(guān)聯(lián)和發(fā)現(xiàn)網(wǎng)絡隱藏層的空間依賴關(guān)系.

Fig.4 Curves of MAE performance with the length of the prediction window圖4 MAE 性能隨預測窗口長度變化曲線

Fig.5 Curves of MAPE (%)performance with the length of the prediction window圖5 MAPE(%)性能隨預測窗口長度變化曲線

Fig.6 Curves of RMSE performance with the length of the prediction window圖6 RMSE 性能隨預測窗口長度變化曲線

為進一步驗證自適應鄰接矩陣能夠關(guān)聯(lián)和發(fā)現(xiàn)網(wǎng)絡隱藏層的空間依賴關(guān)系的能力,圖7 展示了在METRLA 數(shù)據(jù)集上學習得到的的熱力圖(圖7 中間).選取前30 個節(jié)點,發(fā)現(xiàn)第16 個節(jié)點(圖左側(cè)選區(qū))能夠很好地關(guān)聯(lián)其他非直接與其物理相連的節(jié)點信息(實際路網(wǎng)節(jié)點的物理連接關(guān)系圖7 右),進一步驗證了自適應鄰接矩陣能夠關(guān)聯(lián)和發(fā)現(xiàn)網(wǎng)絡隱藏層的空間依賴關(guān)系的作用,更說明了復雜的交通路網(wǎng)具有一定的空間關(guān)聯(lián)性,而自適應鄰接矩陣能夠捕捉這種遠距離的空間關(guān)聯(lián)關(guān)系.

Fig.7 Heatmap of the matrix (right)and the connection between the nodes in the road network (right)on the METR-LA dataset圖7 METR-LA 數(shù)據(jù)集中學習得到的矩陣熱力圖(左)和實際路網(wǎng)中部分節(jié)點間的物理連接關(guān)系(右)

3.3.3 圖小波變換矩陣的稀疏性分析

本文利用圖小波變換矩陣替換圖傅里葉變換矩陣定義圖卷積網(wǎng)絡層.除了提高預測精度外,圖小波變換在空間域和頻譜域都具有稀疏性.以METR-LA 和PEMS-BAY 數(shù)據(jù)集為例,說明了圖小波變換的稀疏性.

在METR-LA 數(shù)據(jù)集中共有207 個節(jié)點,因此,圖小波變換矩陣,圖傅里葉變換矩陣UT∈R207×207.表4 中第一行列出了和UT的稀疏度(或稱非零元素的密度百分比),的非零元素占比為30.09%,UT的非零元素占比為99.98%.在PEMS-BAY 數(shù)據(jù)集中共有325 個節(jié)點,圖小波變換矩陣圖傅里葉變換矩陣UT∈R325×325.表4 中第2 行列出了和UT的稀疏度,的非零元素占比為21.81%,UT的非零元素占比為98.7%.因此,圖小波變換矩陣遠比圖傅里葉變換矩陣UT稀疏.更具稀疏性的圖小波變換不僅加快了計算速度,而且能夠很好地捕獲以每個節(jié)點為中心的相鄰空間拓撲關(guān)系,這個特性對空間關(guān)系建模是有利的.

Table 4 Non-zero element statistics of the wavelet transform matrix and the Fourier transform matrix表4 圖小波變換矩陣與傅立葉變換矩陣非零元素統(tǒng)計

3.3.4 尺度因子大小對模型性能的影響分析

在圖小波卷積層中,尺度因子s控制著每個節(jié)點信息的擴散鄰域大小,節(jié)點鄰域信息動態(tài)關(guān)聯(lián)著中心節(jié)點的屬性特征變化趨勢,因此,選取合適的尺度因子將有助于模型性能的提升.為了探究圖小波變換矩陣中尺度因子s大小對模型性能的影響,統(tǒng)計了在s=1,2,3,5,10,15,20 時,模型在數(shù)據(jù)集METR-LA 上的MAE 性能曲線.

Fig.8 Curves of MAE performance of the proposed model at different scale factors with the prediction window time圖8 不同尺度因子下,模型的MAE 性能隨預測窗口時間長變化曲線

圖8 繪制了在不同尺度因子s參數(shù)下的MAE 曲線,在預測時間窗口小于40 分鐘時,不同的參數(shù)對網(wǎng)絡模型的MAE 影響差異性不明顯.這表明在執(zhí)行短期預測任務時,即使使用較小的尺度因子參數(shù),圖小波神經(jīng)網(wǎng)絡模型能夠很好地捕獲網(wǎng)絡節(jié)點間隱藏的空間關(guān)系,并且尺度因子s越大,對模型MAE性能提升越不明顯.圖9 繪制了不同尺度因子s對模型進行較大預測窗口時的MAE 曲線.在預測時窗大于45 分鐘時,不同的尺度因子參數(shù)對模型的MAE 影響具有明顯的差異.當s=1 時,模型的MAE曲線和s=15 時的MAE 性能曲線幾乎重合,并且s=1 和s=15 時,模型的MAE 曲線均在s=2,3,5,10,20 時的MAE曲線下方.這表明,選用合適的尺度參數(shù)對模型的性能是有積極的作用.此外,在s=1 和s=15 時,本文提出的圖小波神經(jīng)網(wǎng)絡模型的MAE 曲線趨于一致.這一實驗性結(jié)論為確定圖小波變換矩陣中尺度因子s的大小提供了參考,即,s=1 是圖小波神經(jīng)網(wǎng)絡模型在沒有確定最佳尺度因子參數(shù)情況下的最佳選擇.

Fig.9 Curves of MAE performance of the proposed model at different scale factors with the prediction window time (at the larger prediction time window)圖9 不同尺度因子對模型MAE 性能隨預測窗口時間長度的變化曲線(較大的預測時間窗口)

3.3.5 模型抗干擾對比分析

為了驗證本文模型的抗干擾能力,本實驗利用過去1 小時時段(12×5 分鐘)的觀測值來預測下一個小時的特征,歷史觀測時間窗口大小為12.設置了4 組對比實驗,分別為:(1)在整個輸入窗口期添加0 均值的高斯噪聲;(2)僅在歷史時間點6 添加非高斯噪聲;(3)在歷史時間點1、歷史時間點6 和歷史時間點12 添加非高斯噪聲;(4)在全部的歷史時間點添加非高斯噪聲.圖10 繪制了不同噪聲下的曲線圖(在數(shù)據(jù)集METR-LA 上,以0 節(jié)點為例).

Fig.10 Outputs of the modelat different inputnoises sequence圖10 模型在不同輸入噪聲序列下的輸出曲線

在圖10 中:對輸入序列不加任何噪聲時,模型的輸出較為平穩(wěn);當對輸入序列全部施加0 均值且標準差為0.15 的高斯噪聲時,模型的預測輸出變化較為明顯,即在短時預測時窗內(nèi)(30 分鐘內(nèi))偏差較大,但是隨著預測時間窗的增加,模型具有較好預測收斂性,在預測時間窗末期(30 分鐘～60 分鐘之內(nèi)),加高斯噪聲后模型的預測輸出和未加高斯噪聲時的預測輸出趨于一致,這表明模型對長時預測具有較好的抗干擾性.當對輸入序列中第5個值(即輸入時間窗的30 分鐘點)增加一個很大的整數(shù)噪聲(本次實驗選定為整數(shù)100),模型的預測輸出比未加噪聲時的預測輸出要略大,但總體上較為平緩.隨著對輸入序列進行多點位增加噪聲(噪聲整數(shù)100),模型的預測輸出均比未加噪聲時的輸出要大,在短時預測時間窗口內(nèi)偏差較為明顯,但是隨著預測時間窗的增加,模型的預測偏差逐漸減小,這說明模型對長時預測具有一定的抗干擾性.綜上所述,本文的模型對短時預測的抗噪聲能力較弱,對長時預測的抗干擾能力較強,對于具有高斯噪聲的輸入,模型的短時預測性能失效.正因為這種特性,本文提出的模型不能應對時序或時空異常數(shù)據(jù)的檢測;相反,其具有較強的抗干擾性,因此,該模型可以應用在具有強噪聲網(wǎng)絡環(huán)境下的時空預測場景.

3.3.6 其他實驗補充分析

除了與傳統(tǒng)時序預測模型和靜態(tài)圖神經(jīng)網(wǎng)絡模型實驗對比分析外,還將模型與動態(tài)圖神經(jīng)網(wǎng)絡模型進行了實驗對比.因此,這部分主要講述與動態(tài)圖神經(jīng)網(wǎng)絡在本實驗數(shù)據(jù)集上的實驗性結(jié)論.

動態(tài)網(wǎng)絡相比于靜態(tài)網(wǎng)絡來說,更強調(diào)了網(wǎng)絡中節(jié)點和邊的出現(xiàn)順序和時間.在現(xiàn)實中,圖網(wǎng)絡結(jié)構(gòu)主要是通過節(jié)點和邊的順序添加而形成的,理應被視為一個有節(jié)點與其鄰居之間交互事件驅(qū)動的動態(tài)過程.因此,節(jié)點的鄰域并不是同時形成的,圖網(wǎng)絡結(jié)構(gòu)屬于一種快照網(wǎng)絡結(jié)構(gòu),是一段時間內(nèi)鄰域的累積.為了構(gòu)造這種動態(tài)的網(wǎng)絡結(jié)構(gòu),我們隨機統(tǒng)計了在輸入時間窗口內(nèi)網(wǎng)絡中每個節(jié)點特征的時間分布,去除了最小Top10 對應的網(wǎng)絡節(jié)點,并以此獲得了12 個圖結(jié)構(gòu)的時間快照(其中,12 是指12 個歷史觀測,按5 分鐘一個觀測,1 小時為12 個觀測點),每個圖結(jié)構(gòu)時間快照構(gòu)成了圖結(jié)構(gòu)序列,在訓練過程中,隨著時間步驟依次動態(tài)改變這種圖結(jié)構(gòu).為了能夠與動態(tài)圖神經(jīng)網(wǎng)絡模型進行對比,我們改造了EvolveGCN 模型[14],因為原始EvolveGCN 對圖節(jié)點的分類、邊的分類和節(jié)點間連接預測效果好.為了使其能夠?qū)r序特征預測,我們將EvolveGCN 模型每個時間戳下的節(jié)點嵌入進行了線性疊加并經(jīng)過了ReLU 函數(shù)處理,最后接入一個感知機層,以此獲得對時序特征預測的能力,修改后的EvolveGCN 模型結(jié)構(gòu)如圖11 所示.

Fig.11 Modified EvolveGCN model圖11 修改后的EvolveGCN 模型結(jié)構(gòu)

圖12 中,在METR-LA 數(shù)據(jù)集上的MAE 曲線(左)在短時預測(小于30 分鐘)修改EvolveGCN 模型的MAE比所提出GWNN-STGM 模型的MAE 要大.但是隨著預測時長的增加,修改EvolveGCN[14]模型的MAE 要低于GWNN-STGM 模型.這表明在METR-LA 數(shù)據(jù)集上,動態(tài)圖結(jié)構(gòu)下的EvolveGCN(修改)模型能夠?qū)﹂L時預測具有較好的性能.在PEMS-BAY 數(shù)據(jù)集上的MAE 曲線(右)發(fā)現(xiàn):EvolveGCN(修改)模型的MAE 在15 分鐘預測時長內(nèi),比GWNN-STGM 模型的MAE 低;在大于15 分鐘預測時長時,EvolveGCN(修改)模型的MAE 數(shù)值均比GWNN-STGM 模型高.這表明在PEMS-BAY 數(shù)據(jù)集上,動態(tài)圖結(jié)構(gòu)下的EvolveGCN(修改)模型不能夠很好地進行長時預測.其中最主要原因是,構(gòu)造產(chǎn)生的動態(tài)圖結(jié)構(gòu)不能完全真實反映現(xiàn)實世界中物理路網(wǎng)的真實狀態(tài).

Fig.12 MAE conducted by the GWNN-STGM (ours)and the modified EvolveGCNon datasets圖12 本文GWNN-STGM 模型和修改后的EvolveGCN 模型在實驗數(shù)據(jù)集下預測的MAE 曲線

4 總結(jié)與未來工作

本文提出了一種新的時空圖建模的圖小波卷積神經(jīng)網(wǎng)絡模型.提出的圖小波卷積神經(jīng)網(wǎng)絡通過將圖小波卷積層和擴展因果卷積層結(jié)合起來,有效地捕獲了時空圖節(jié)點間屬性特征的時空相關(guān)性.提出了利用自適應鄰接矩陣從數(shù)據(jù)中動態(tài)學習隱層空間依賴關(guān)系的有效方法.本文提出的模型在兩個公共交通網(wǎng)絡數(shù)據(jù)集上的性能優(yōu)于其他最新的基準方法,這表明本文的圖小波卷積神經(jīng)網(wǎng)絡模型在從輸入數(shù)據(jù)中探索時空結(jié)構(gòu)方面具有一定的潛力.

為了進一步探究模型的性能,通過對模型的抗干擾能力實驗分析,發(fā)現(xiàn)本文模型對短時預測的抗噪聲能力較弱,對長時預測的抗干擾能力較強,對于具有高斯噪聲的輸入,模型的短時預測性能失效.因此,模型不能應對時序或時空異常數(shù)據(jù)的檢測場景;相反,其具有較強的抗干擾性,因此,提出的模型可以應用在具有強噪聲網(wǎng)絡環(huán)境下的時空預測場景.此外,將模型與動態(tài)圖神經(jīng)網(wǎng)絡模型進行了實驗對比分析,發(fā)現(xiàn)僅依靠統(tǒng)計節(jié)點的時序特征提取網(wǎng)絡結(jié)構(gòu)時間快照的方法構(gòu)造的動態(tài)圖結(jié)構(gòu)破壞了圖結(jié)構(gòu)的完整時空依賴信息,因此不能完全真實反映現(xiàn)實世界中物理路網(wǎng)的真實狀態(tài).

在未來的工作中,將繼續(xù)探索本文模型在其他應用領域的嘗試,主要包含3 個方面:(1)探索本文模型在大圖結(jié)構(gòu)下的時序預測性能,因為隨著信息技術(shù)的發(fā)展,大圖結(jié)構(gòu)中的數(shù)據(jù)的分析挖掘價值愈發(fā)突出;(2)探索本文模型在動態(tài)圖結(jié)構(gòu)下的性能,特別是針對多連接關(guān)系的動態(tài)圖結(jié)構(gòu)領域的時序預測;(3)探索本文模型在圖節(jié)點分類、連接關(guān)系預測等多個領域的應用.