文章資訊

《Coupled Layer-wise Graph Convolution for Transportation Demand Prediction》，發表於國際人工智慧會議（AAAI-2021），作者為北京航空航天大學的團隊。

論文下載地址：https://arxiv.org/pdf/2012.08080.pdf

GitHub程式碼地址：https://github.com/Essaim/CGCDemandPrediction

摘要

圖卷積網路由於其出色的效能而被廣泛應用於交通需求預測中。然而，在大多數現有研究中，圖卷積為在啟發式生成的鄰接矩陣上實現，既不能反映出真實的空間關係準確定位，也不能自適應地捕獲需求的多級空間依賴性。為了解決上述問題，本文提供了一種新穎的圖卷積網路用於交通需求預測。首先，文章提出一個新的圖卷積架構，該架構在不同的層具有不同的鄰接矩陣，並且在訓練過程中所有的鄰接矩陣都是自學習的。其次，作者設計了分層耦合機制，上層鄰接矩陣與下層鄰接矩陣相互關聯。同時減少了模型中引數的規模。最後， 網路的構建是透過將隱藏的空間狀態與門控迴圈單元整合來給出最終的預測結果，該單元可以同時捕獲多級空間依賴性和時間動態。實驗在兩個真實資料集上進行測試，其結果證明了該模型的優越效能。

背景

由於交通需求預測的重要性，在過去的幾年中在該領域已經做出了許多努力。主流的發展可分為三個階段：

1）早期的研究採用了經驗統計分析，主要集中在預測特定區域的需求，而不是整個城市，以及無法捕獲空間和時間相關性會同時導致較低的預測精度。

2）最近，深度學習迅速發展為時空相關建模提供新解決方案。透過將整個城市視為影象並將其劃分為使用卷積神經網路提取空間相關性和遞迴神經網路提取時間相關性，這使得在形式化方面取得了巨大進展。但是，空間臨近性的聚合使基於CNN的方法對長距離過渡模式不敏感，僅適合於歐幾里得空間關係。

3）圖卷積網路是CNN的泛化，適合處理非歐幾里得資料。由於路網的拓撲結構，它已經廣泛地應用於交通領域。

儘管GCN已經在交通預測類問題中取得了一定效果，但仍然有四個重要問題有待解決：1）決定圖卷積網路中聚合方式的鄰接矩陣大部分是固定的，大多是根據空間距離或網路連線性生成的，無法捕獲真正的空間依賴性。2）現有方法忽略了交通需求預測的層次依賴性。3）主要遵循圖訊號處理的觀點，當前圖卷積方法趨向於平滑節點的輸入訊號。在這種情況下，僅具有一個鄰接矩陣的堆疊圖卷積層很難有效地獲得交通需求的多級表示。4）構成最終交通需求的不同層次中的表示形式不應該是靜態的，而是隨時間變化的。

貢獻

為了解決上述問題，作者提出了一種新穎的深度學習框架，稱為耦合分層卷積遞迴神經網路（CCRNN）。總而言之，本文具有以下貢獻：

提出了一種新穎的圖卷積架構來自適應地提取多級空間相關性。 這結構在不同的層中具有不同的鄰接矩陣，並且所有鄰接矩陣都是在訓練過程中自學的。提出了一種分層耦合機制，根據不同層次的拓撲結構的隱藏關聯來橋接上層鄰接矩陣與下層鄰接矩陣。它還減少了訓練過程中的計算量。提出了統一的預測框架進行最終的預測。透過聚合多層次的需求依賴性得到隱藏單元的狀態，使用門控迴圈單元，預測在序列到序列結構中空間隱藏狀態。

圖1 CGC與其它GCN的區別

模型介紹

圖2顯示了作者所提出的方法的體系結構。它由鄰接矩陣模組、耦合分層圖卷積模組、多層次聚合模組、時序依賴模組組成。

圖2 CCRNN的整體結構

1、鄰接矩陣生成模組：

給定圖訊號集合三維張量，首先將三維張量變換為二維張量。為了捕獲不同站點之間的內部相似性並過濾站點之間的冗餘資訊，將二維矩陣分解為兩個矩陣。其中 ，表示時間級和站點級的矩陣。在本文中使用奇異值分解（SVD）分解。在中隱藏了大量冗餘的交通模式，SVD可以透過減少尺寸來過濾掉冗餘資訊。包含每個站點的緊湊和高階表示，其中ξ是站點特徵的維數。這樣可計算X的第x行和第y行的相似度作為它們在鄰接矩陣中的邊緣權重：

其中表示鄰接矩陣A的第x行和第y列。在這裡使用基於高斯核的方法來估計成對相似度。其中ε是標準差，公式可以定義為：

2、耦合分層圖卷積模組

為了有效準確地捕獲多級依賴關係，作者提出了一種新穎的圖卷積網路，即耦合分層圖卷積（CGC），它在不同層的具有不同鄰接矩陣。 此結構可以遞迴定義為：

其中代表m+1層的輸入，不僅是m+1層的輸出，也是m+2層的輸入，隨層而異。作者使用耦合對映函式在層m+1中構造高層鄰接矩陣：

自適應卷積將不需要任何先驗知識的兩個隨機初始矩陣相乘，並且矩陣是透過隨機梯度下降端對端進行訓練的。以此方式，生成新的鄰接矩陣以提取隱藏的空間依賴性。但是隨機初始化帶來了收斂和數值不穩定的困難。為了解決這個問題，本文中先用原始定義的圖結構初始化自適應矩陣，並採用隨機梯度下降法對其進行最佳化。CGC的第一層定義為：

其中。每個時間步長的特徵矩陣被輸入到CGC的第一層作為輸入。但是由於節點數量巨大，N×N的鄰接矩陣和ψ的計算成本較高，導致上述公式的引數化過大。為了解決這個問題，文中將透過SVD分解為兩個小矩陣：

其中是嵌入第一層的源節點，是嵌入目標的節點，L表示節點維度大小。可訓練引數的數量從N×N減少到2×N×L（N >> L）。因此第一層圖卷積的公式可以重新定義為：

另外，函式ψ由全連線層實現來對層相關性建模。在這裡共享E1和E2之間全連線層的引數：

根據以上公式，CGC的數學表示式可以遞迴定義為：

3、多層次聚合模組

為了從所有圖卷積層中收集資訊而不是僅從一個固定層中提取資訊，需要透過一種關注機制來實現多級聚合，以選擇對當前預測任務相對重要的資訊。

透過CGC得到圖訊號的多級表示，注意力是透過線性變換計算的，Softmax函式有助於將係數歸一化。將Z和標準化注意力分數相乘的結果相加後聚合定義為：

其中表示線性變換的權重和偏差，的展平形式，而的注意力分數。h是CGC輸出的最終結果，輸出將被饋送到GRU中。

4、時序依賴模組

類似於DCRNN模型，文中用CGC和多級聚合的組合代替了GRU中的線性變換。耦合分層圖CGRU是RNN的一種簡單但功能強大的變體，它解決了梯度爆炸和消失的問題。耦合分層卷積遞迴門控遞迴單元（CCGRU）定義為：

總結

在本文中，作者提出了一種新穎的交通需求預測模型（CCRNN）。同時提出了一種新穎的圖卷積架構(CGC)用於捕捉多級空間相關性，在該架構中鄰接矩陣是自學的，並且層與層之間的鄰接矩陣是不同的。此外，採用了分層耦合機制橋接上層圖結構和下層圖結構。這也減少了引數規模。然後，透過多級聚合模組將不同的重要性附加到提取的表示中。單一網路融合了上述組成要素，最終形成了預測。