面向時空圖建模的圖小波卷積神經網絡模型?

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

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

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

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

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

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

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

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

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

1 相關研究工作

1.1 時空圖建模

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

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

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

此外,近年來,動態圖神經網絡在建模或捕捉網絡的結構和性質方面取得了新的進展[14],相比于靜態網絡來說,動態圖神經網絡強調了網絡中節點和邊的出現順序和時間.因此,節點的鄰域并不是同時形成的,得到的快照網絡結構是一段時間內鄰域的累積結構.雖然動態圖神經網絡能夠建模動態圖結構,但是需要動態記錄每個時間戳下的圖結構,在生物分子領域、醫藥等領域有著非常大的應用場景.對于圖網絡結構變化不明顯的應用場景下,動態記錄圖網絡結構是不明智的,如交通路網,因為道路網絡物理狀態多為固定模型.

1.2 圖卷積神經網絡

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

1.3 圖小波卷積神經網絡

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

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

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

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

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

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

1.4 時空圖網絡

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

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

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

2 時空圖建模方法

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

2.1 相關定義及說明

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

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

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

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

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

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

2.2 圖譜卷積層

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

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

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

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

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

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

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

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

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

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

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

為了學習時空圖的空間依賴項和圖小波卷積網絡隱藏層的空間依賴項,我們定義了自適應鄰接矩陣,并將其引入到圖小波卷積層中,自適應鄰接矩陣無需圖的結構先驗信息,直接從數據集中自學習,動態關聯和發現網絡隱藏層的空間依賴關系.自適應鄰接矩陣定義如下:

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

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

2.3 時間卷積層

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

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

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

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

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

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

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

Fig.3 Curves between Tanh and Sigmod圖3 Tanh 函數和Sigmod 函數曲線

2.4 面向時空圖的圖小波卷積神經網絡總體架構

本節將描述面向時空圖建模的圖小波卷積神經網絡總體架構,該架構將圖小波卷積層和門控時間卷積層結合起來,完成屬性圖的時空關系建模和預測.網絡模型結構定義如下.

? 輸入層(或第0 層):

? 第l卷積層:

(1)門控時間卷積運算

(2)圖小波卷積運算

? 輸出層:

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

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

3 實驗分析

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

3.1 實驗相關參數設置

本實驗運行環境為Intel(R)Xeon(R)Gold 5218CPU@2.30GHz,NVIDIA GeForce GTX2080GPU,顯存32GB.設置歷史觀測步長和預測窗口大小均為12,即利用過去一小時時段(12×5 分鐘)的觀測值來預測下一個小時的特征.模型中卷積層數l=2,M=2.訓練過程中對參數數量采用隨機丟棄策略,丟棄率(dropout rate)設置為0.3.采用隨機初始化方式對模型中的參數進行初始化,模型的訓練優化器為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 種度量函數為模型性能的評估指標.

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

3.3 實驗結果分析

3.3.1 模型性能對比分析

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

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

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

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

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

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

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 性能隨預測窗口長度變化曲線

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

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 數據集中學習得到的矩陣熱力圖(左)和實際路網中部分節點間的物理連接關系(右)

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

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

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

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

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

在圖小波卷積層中,尺度因子s控制著每個節點信息的擴散鄰域大小,節點鄰域信息動態關聯著中心節點的屬性特征變化趨勢,因此,選取合適的尺度因子將有助于模型性能的提升.為了探究圖小波變換矩陣中尺度因子s大小對模型性能的影響,統計了在s=1,2,3,5,10,15,20 時,模型在數據集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參數下的MAE 曲線,在預測時間窗口小于40 分鐘時,不同的參數對網絡模型的MAE 影響差異性不明顯.這表明在執行短期預測任務時,即使使用較小的尺度因子參數,圖小波神經網絡模型能夠很好地捕獲網絡節點間隱藏的空間關系,并且尺度因子s越大,對模型MAE性能提升越不明顯.圖9 繪制了不同尺度因子s對模型進行較大預測窗口時的MAE 曲線.在預測時窗大于45 分鐘時,不同的尺度因子參數對模型的MAE 影響具有明顯的差異.當s=1 時,模型的MAE曲線和s=15 時的MAE 性能曲線幾乎重合,并且s=1 和s=15 時,模型的MAE 曲線均在s=2,3,5,10,20 時的MAE曲線下方.這表明,選用合適的尺度參數對模型的性能是有積極的作用.此外,在s=1 和s=15 時,本文提出的圖小波神經網絡模型的MAE 曲線趨于一致.這一實驗性結論為確定圖小波變換矩陣中尺度因子s的大小提供了參考,即,s=1 是圖小波神經網絡模型在沒有確定最佳尺度因子參數情況下的最佳選擇.

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 繪制了不同噪聲下的曲線圖(在數據集METR-LA 上,以0 節點為例).

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

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

3.3.6 其他實驗補充分析

除了與傳統時序預測模型和靜態圖神經網絡模型實驗對比分析外,還將模型與動態圖神經網絡模型進行了實驗對比.因此,這部分主要講述與動態圖神經網絡在本實驗數據集上的實驗性結論.

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

Fig.11 Modified EvolveGCN model圖11 修改后的EvolveGCN 模型結構

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

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

4 總結與未來工作

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

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

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