李昊天,盛益強

(1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心,北京 100190; 2.中國科學(xué)院大學(xué),北京 100049)

0 引 言

圖是對一組對象(節(jié)點)及其關(guān)系(邊)進(jìn)行建模的一種數(shù)據(jù)結(jié)構(gòu)。近年來，由于圖強大的表示能力，使得圖結(jié)構(gòu)在社交、生物學(xué)、物理系統(tǒng)、交通、知識圖譜等諸多領(lǐng)域有著廣泛的應(yīng)用[1-5]。目前，對圖的研究主要集中在圖分類、圖預(yù)測、圖嵌入、圖聚類等領(lǐng)域[6]，其中圖預(yù)測領(lǐng)域中的圖節(jié)點預(yù)測研究，對于智慧城市中的交通管理、網(wǎng)絡(luò)安全中的異常流量檢測[7]、社交網(wǎng)絡(luò)中的熱點評估[8]等方面都有著深遠(yuǎn)的意義。

圖節(jié)點預(yù)測通常是基于一段時間內(nèi)各個圖節(jié)點的特征，來預(yù)測未來某一時刻圖節(jié)點的某些屬性特征。圖節(jié)點預(yù)測的研究方法可以分為空間法、時序法和空間時序混合法3類。其中空間法是一種基于圖中點與點之間的拓?fù)潢P(guān)系來分析圖的屬性變化與傳播方式的方法，常見方法有PageRank[9]、HITS[10]、GCN[11]、GNN[12]等。這類方法不依賴于歷史時間的數(shù)據(jù)，而更關(guān)心同一時刻相鄰各個節(jié)點的狀態(tài)信息，對于短時預(yù)測有著更好的效果，但對于長時預(yù)測以及各個節(jié)點自身個性化特征的學(xué)習(xí)表現(xiàn)欠佳。時序法是一種根據(jù)待預(yù)測節(jié)點的歷史時序序列，學(xué)習(xí)其自身屬性關(guān)于時間變化的函數(shù)，從而實現(xiàn)預(yù)測的方法，主流方法包括ARIMA[13]、LSTM[14]、GRU[15]、SAEs[16]等。這類方法的優(yōu)點是依托傳統(tǒng)的序列學(xué)習(xí)算法，更關(guān)注節(jié)點長時間的變化，容易刻畫出節(jié)點自身的屬性特征，但是由于沒有合理利用節(jié)點間連接關(guān)系的信息，一些易于傳播的特性如交通網(wǎng)絡(luò)中的汽車流量、社交網(wǎng)絡(luò)中的熱點熱度等容易被遺失，從而導(dǎo)致對節(jié)點的刻畫不完整，影響預(yù)測精度。空間時序混合法是一種將空間特征和時序特征混合考慮的方法，綜合預(yù)測未來時刻的節(jié)點屬性，常見方法包括T-GCN[17]、GCAN[18]、AST-GCN[19]等。這類方法綜合了節(jié)點的空間性和時間性信息，是目前復(fù)雜網(wǎng)絡(luò)節(jié)點預(yù)測中最為常用的一類算法，但這類算法面臨的問題是如何合理地提取空間特征和時間特征，以及如何讓二者相互融合，在不同的應(yīng)用場景下，對于空間信息和時間信息的不同側(cè)重問題也亟待解決。

目前，在一些復(fù)雜網(wǎng)絡(luò)[20]中，比如交通網(wǎng)絡(luò)，很難同時采集到各個交通節(jié)點的流量、車輛平均速度、車輛滯留時間等信息，并且通常在關(guān)心一種特征的預(yù)測情況的同時很難去考慮采集其他特征，因此單一時序特征場景實際上是一種很自然也很常見的圖預(yù)測場景。遺憾的是，對于單一時序特征場景的圖節(jié)點預(yù)測問題的研究存在一些問題，時序法沒有利用節(jié)點的空間信息，而空間法和時空結(jié)合法，大部分都需要基于圖卷積網(wǎng)絡(luò)來進(jìn)行空間特征提取，而這種方法，在特征單一情況下的訓(xùn)練參數(shù)矩陣將退化為單變量參數(shù)，導(dǎo)致空間特征的提取嚴(yán)重依賴于初始化的連接關(guān)系，沒有達(dá)到數(shù)據(jù)驅(qū)動的效果。雖然T-GCN等是解決單一時序場景的時空圖卷積算法，但由于這些算法是將連續(xù)幾個時刻的數(shù)據(jù)，作為多維特征進(jìn)行處理，并不屬于嚴(yán)格意義上的單一特征，此外由于連續(xù)時間的長度是一個超參數(shù)，對于不同場景缺乏普適性。針對上述問題，本文提出一種單一時序特征場景下的結(jié)合圖卷積網(wǎng)絡(luò)與長短時記憶網(wǎng)絡(luò)(LSTM)的圖節(jié)點預(yù)測算法，通過將訓(xùn)練參數(shù)前置，并且將空間特征代替時序原始特征數(shù)據(jù)，進(jìn)行時序訓(xùn)練，實現(xiàn)特征的融合，達(dá)到了良好的預(yù)測效果。

1 問題定義

單時序特征場景下的圖網(wǎng)絡(luò)的預(yù)測問題，可以進(jìn)行如下描述，圖網(wǎng)絡(luò)定義為G=(V,E)，其中V={v1,v2,…,vN}是節(jié)點集合，對應(yīng)圖網(wǎng)絡(luò)的數(shù)據(jù)節(jié)點，E={e1N,e2N,…,eNN}是邊集，對應(yīng)圖中數(shù)據(jù)節(jié)點之間的連接關(guān)系強弱，值越大說明關(guān)系越強，為0表示2個節(jié)點并無關(guān)聯(lián)。單時序特征是指每個節(jié)點vi在給定時刻t有且只有一個特征數(shù)值gi(t)。預(yù)測問題是指通過歷史數(shù)據(jù)(Xt-s,Xt-s+1,…,Xt)來預(yù)測下一時刻Xt+1的信息，即求F(·)滿足:

Xt+1=F(Xt-s,Xt-s+1,…,Xt)

(1)

其中，Xt為t時刻的所有節(jié)點的時序特征Xt=[g1(t),g2(t),…,gN(t)]。

2 圖卷積網(wǎng)絡(luò)與長短時記憶網(wǎng)絡(luò)

圖卷積網(wǎng)絡(luò)(GCN)是利用圖的譜理論來處理圖結(jié)構(gòu)數(shù)據(jù)，從而獲取其空間特征信息。圖卷積計算需要先獲得圖的拉普拉斯矩陣L，定義為：

(2)

其中，A為圖G的帶權(quán)鄰接矩陣，即Aij表示為點vi和點vj的連接強度eij，D為A的對角行的和矩陣，IN為N階單位矩陣。顯然有L是實對稱矩陣，從而必然存在對角矩陣Λ=diag(λ1,λ2,…,λN)相似于L，即存在正交矩陣U滿足L=UTΛU。

定義圖卷積運算g×Gh：

UT(g×Gh)=UTg?UTh

(3)

其中，?是矩陣的直積運算，從而卷積核g和輸入向量x的卷積表示為：g×Gh=U(UTg?UTx)，進(jìn)一步，令UTg為對角矩陣gθ，并運用層次線性模型約束[11]和切比雪夫優(yōu)化方法[21]得到：

(4)

利用式(4)中定義好的卷積，即可直接用于圖卷積網(wǎng)絡(luò)的卷積層，公式如下：

(5)

其中,H(l)為第l層的輸出，W(l)為第l層的待訓(xùn)練參數(shù)，且W(l)∈Rk×m，k是l-1層每個節(jié)點的特征維度，m是l層每個節(jié)點的特征維度，通常有m≤k，在一般的圖卷積網(wǎng)絡(luò)訓(xùn)練中，圖卷積層層數(shù)在2層左右，用于提取圖的空間拓?fù)湫畔ⅰ?/p>

圖1 LSTM模塊圖

LSTM是循環(huán)神經(jīng)網(wǎng)絡(luò)[22](RNN)的一種改進(jìn)，它通過加入3個門控單元，有效解決了RNN中常見的梯度消失和梯度爆炸的問題，是一種常用的序列學(xué)習(xí)網(wǎng)絡(luò)。

LSTM模塊如圖1所示，包含輸入門、遺忘門、輸出門，其中遺忘門決定從之前的序列中丟棄哪些信息，對應(yīng)公式為：

ft=σ(Wf·[ht-1,Xt]+bf)

(6)

輸入門決定當(dāng)前狀態(tài)下需要留存的信息，并計算新的候選值用于狀態(tài)更新，其公式如下：

it=σ(Wi·[ht-1,Xt]+bi)

(7)

(8)

則更新后的狀態(tài)由輸入門和遺忘門共同決定。即:

(9)

最后，輸出門負(fù)責(zé)決定將更新后的狀態(tài)的部分進(jìn)行輸出，其運算方法如下：

ot=σ(Wo[ht-1,Xt]+bo)

(10)

ht=ot×tanh(Ct)

(11)

上述式(6)～式(11)中的Wf、Wi、WC、Wo、bf、bi、bc、bo是待訓(xùn)練參數(shù)，[ht-1,Xt]表示ht-1和Xt組合，σ(·)為標(biāo)準(zhǔn)的S型曲線，定義如下：

(12)

tanh(·)取值范圍為[-1,1]的中心對稱S型曲線，定義如下：

(13)

3 結(jié)合LSTM的單時序特征圖卷積網(wǎng)絡(luò)預(yù)測

在單時序特征條件下，如果按照傳統(tǒng)的圖卷積網(wǎng)絡(luò)進(jìn)行訓(xùn)練，則式(5)中的參數(shù)矩陣W(l)的的維度k將退化為1，訓(xùn)練參數(shù)嚴(yán)重不足，會導(dǎo)致欠擬合現(xiàn)象；而如果將每個節(jié)點連續(xù)一段時間s的特征值作為一組特征，并將接下來一小段時間的預(yù)測值作為輸出，進(jìn)行圖卷積網(wǎng)絡(luò)訓(xùn)練會產(chǎn)生2個問題:1)作為輸入的一段時間內(nèi)的特征值之間的關(guān)系信息將被丟失，容易過擬合；2)輸入空間的時間間隔和輸出空間的時間間隔成為嚴(yán)重影響實驗效果的超參數(shù)，對于不同的網(wǎng)絡(luò)數(shù)據(jù)集，缺乏普適性。

因此為了解決上面2個問題，本文提出一種結(jié)合LSTM的單時序特征圖卷積網(wǎng)絡(luò)算法(SST-GCN)，首先采用每一層只輸入和輸出一個時刻的特征數(shù)據(jù)，并將原有的參數(shù)矩陣前置，擴展了參數(shù)訓(xùn)練規(guī)模和維度，同時增加了原始鄰接矩陣的可變性，避免了欠擬合現(xiàn)象并且降低了原始鄰接矩陣不準(zhǔn)確所帶來的誤差。其次，將圖卷積層的輸出作為空間特征結(jié)合LSTM進(jìn)行時序特征的訓(xùn)練，構(gòu)成如圖2所示的結(jié)合時空特性的神經(jīng)網(wǎng)絡(luò)模型。

圖2 SST-GCN網(wǎng)絡(luò)結(jié)構(gòu)圖

模型先將每個時刻圖網(wǎng)絡(luò)的特征信息Xt通過一個前置參數(shù)的圖卷積網(wǎng)絡(luò)，該網(wǎng)絡(luò)包含2層圖卷積層，每層前向傳播公式為：

(14)

對比式(5),這里W(l)即為前置的訓(xùn)練參數(shù)矩陣。

將圖卷積網(wǎng)絡(luò)的輸出G(Xt)作為LSTM網(wǎng)絡(luò)的輸入進(jìn)行時序特征的提取，采用新的LSTM公式如下:

(15)

與式(6)～式(11)相比，將GCN網(wǎng)絡(luò)提取出的空間特征向量G(Xt)代替了原始的時序特征向量Xt，達(dá)到了空間特征和時間特征相結(jié)合的訓(xùn)練效果。

本文模型在訓(xùn)練時采用L2范數(shù)作為損失函數(shù)，并添加正則化項防止過擬合。具體公式如下：

(16)

4 實驗與分析

4.1 數(shù)據(jù)集描述以及預(yù)處理

本文采用2套交通網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實驗驗證，第1套是2012年洛杉磯交通數(shù)據(jù)集(Los)，它包括207個傳感器記錄行駛車輛的速度，每隔5 min記錄一次，去除掉部分損失采樣信息，得到每個傳感器的時序特征共2016個，傳感器組成的鄰接矩陣由傳感器之間的距離來確定，距離越遠(yuǎn)其連接強度越弱。連接強度和距離之間的關(guān)系表示為：

(17)

其中，x表示vi和vj的距離，eij為連接強度，當(dāng)x<5 km時，eij在0.5～1之間，否則為0。

第2套數(shù)據(jù)集是美國加州交通監(jiān)視系統(tǒng)PeMS采集的數(shù)據(jù)集，是交通網(wǎng)絡(luò)預(yù)測領(lǐng)域常用的開源數(shù)據(jù)集(http://pems.dot.ca.gov/)[23]，它每30 s采集一次數(shù)據(jù)，本文使用的采集點有307個，通過聚合每5 min內(nèi)的數(shù)據(jù)信息，得到每5 min一次的速度數(shù)據(jù)，每個采集點獲得了16992個時序特征，同樣采集點之間的鄰接矩陣由它們之間的距離刻畫，參考式(17)。

2套數(shù)據(jù)集均將按照時序特征長度8：2的比例劃分為訓(xùn)練集和測試集，最終在測試集上通過定長的歷史連續(xù)時序序列來預(yù)測下一個時刻的數(shù)據(jù)，并和真實的數(shù)據(jù)進(jìn)行對比驗證。

4.2 實驗與評估

1)均方根誤差(RMSE)：

(18)

2)平均絕對誤差(MAE)：

(19)

3)平均準(zhǔn)確率(AC)：

(20)

4)確定系數(shù)(R2)：

(21)

5)方差分?jǐn)?shù)(var)：

(22)

上述評價指標(biāo)中，RMSE和MAE越小或者AC、R2、var越大說明預(yù)測結(jié)果越準(zhǔn)確。

本文實驗所用超參數(shù)為：輸入序列長度為10，學(xué)習(xí)率為0.001,隱藏層為32層，batchsize為64，訓(xùn)練300個epoch。

所使用的實驗平臺為Ubuntu16.04，GPU采用NVIDIA Tesla K80，基于Tensorflow2.0框架進(jìn)行實驗。

在Los和PeMS數(shù)據(jù)集上的各個算法的實驗結(jié)果分別如表1和表2所示。

表1 Los實驗結(jié)果

表2 PeMS實驗結(jié)果

在各項評價指標(biāo)上各個算法的表現(xiàn)可以從表1和表2中看出，SST-GCN各項指標(biāo)均領(lǐng)先于主流的交通預(yù)測算法或與其一致，其中在平均準(zhǔn)確度AC、均方根誤差RMSE上優(yōu)于其他算法5%左右。在方差分?jǐn)?shù)var、確定系數(shù)R2上與其他算法基本一致，且與SST-GCNwithout-p的對比實驗結(jié)果表明，參數(shù)矩陣前置能夠產(chǎn)生良好的增益。因此可知SST-GCN算法的預(yù)測效果綜合優(yōu)于其他幾種算法。

5 結(jié)束語

本文提出了一種混合時空特性的單時序特征圖卷積網(wǎng)絡(luò)的預(yù)測方法。一方面通過將圖卷積網(wǎng)絡(luò)的參數(shù)矩陣前置，解決了傳統(tǒng)圖卷積網(wǎng)絡(luò)在單一時序特征下的參數(shù)退化問題。另一方面通過結(jié)合LSTM和GCN模型，實現(xiàn)了空間特征和時序特征的融合預(yù)測，提高了預(yù)測精度。在交通網(wǎng)絡(luò)中的實驗結(jié)果表明，與常見的GRU、LSTM、SAEs、T-GCN等算法相比，本文所提算法預(yù)測準(zhǔn)確度更高。