論文筆記《Spatio-Temporal Graph Structure Learning for Traffic Forecasting》

【論文】 Zhang Q, Chang J, Meng G, et al. Spatio-Temporal Graph Structure Learning for Traffic Forecasting[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2020, 34(01): 1177-1185.

【代碼】 暫無

目錄

• 1. Structure Learning Convolution
• • 1.1 Formulation of SLC
  • 1.2 Relationship Between SLC and CNN Methods
• 2. SLCNN for Traffic Forecasting
• • 2.1 Global Structure Learning Convolution
  • 2.2 Local Structure Learning Convolution
  • 2.3 Pseudo Three Dimensional SLC
• 3. Experiments

本篇文章主要是解決如何模組化複雜、動态的空間依賴性問題，作者認為現在用的圖卷積神經網絡存在以下幾個問題：

• 使用預定義方法，或依賴于圖結構的先驗知識，這些并不能保證預測目前學習任務的準确性。
• 多利用局部圖結構，忽略了遠距離關系。
• 圖結構一旦定義即固定，而實際上交通資料每時每刻都在變化，圖結構也在變化。

是以，作者提出一種通用的圖卷積公式Structure Learning Convolution (SLC)，它能将結構資訊顯示地模組化到卷積運算中。文章提出的SLCNN Layer部署了兩個 SLC 分别用于捕捉全局和局部結構資訊。同時，作者還将Pseudo three Dimensional convolution (P3D) networks 與 SLC 結合，用于捕捉時間依賴性。下面是對文章（模型）思路的梳理。

1. Structure Learning Convolution

1.1 Formulation of SLC

本節主要說明 Structure Learning Convolution(SLC) 基本思想，以及和普通卷積的異同點，這部分是本文模型的一個核心點，先記住構造思路就行，看上去還挺直覺的。

作者認為卷積運算可看作是對輸入信号的聚合操作，對于圖結構資料，聚合操作不僅僅要聚合信号值，還要聚合圖結構資訊。是以，作者提出 SLC 表示為： y i = f ( ∑ e i j ∈ E S i j w j x j ) y_{i}=f\left(\sum_{e_{i j} \in \mathcal{E}} S_{i j} w_{j} x_{j}\right) yi​=f(∑eij​∈E​Sij​wj​xj​)，其中：

• f ( ⋅ ) f(·) f(⋅) 是激活函數；
• y i y_i yi​ 是節點 i i i 的輸出信号；
• x i x_i xi​ 是節點 i i i 的輸入資料，注意是embedded在圖上的資料；
• e i j ∈ E e_{i j} \in \mathcal{E} eij​∈E 表示 i / j i/j i/j 之間有邊，其中 E \mathcal{E} E不是預定義的，是在訓練中得到的。
• W \mathbf{W} W 是 n n n 維卷積核權重， w j w_j wj​ 是其中第 j j j 個元素。 w ∈ R C i n × C o u t × K max ⁡ \mathbf{w} \in \mathbb{R}^{C_{i n} \times C_{o u t} \times K_{\max }} w∈RCin​×Cout​×Kmax​ 部分起到 convolutional kernel module的作用。
• S i j S_{i j} Sij​ 表示 i / j i/j i/j 之間的關聯度。 S ∈ R N × K max ⁡ \mathbf{S} \in \mathbb{R}^{N \times K_{\max }} S∈RN×Kmax​ 部分起到 structure module的作用，當 K max ⁡ = N K_{\max }=N Kmax​=N時表示全局圖結構，反之是局部圖結構。

1.2 Relationship Between SLC and CNN Methods

本節主要說明了之前提出的各種CNN方法，可以通過恰當定義 S S S ，然後通過SLC 的特定執行個體得到。僅以 普通卷積 和 Chebyshev Spectral CNN (ChebNet) 舉例。

Classical CNN 定義為：

y i = f ( ∑ e i j ∈ E w j x j ) y_{i}=f\left(\sum_{e_{i j} \in \mathcal{E}} w_{j} x_{j}\right) yi​=f⎝⎛​eij​∈E∑​wj​xj​⎠⎞​

這個你就可以看成是 SLC 中 S = 1 S=1 S=1（一種特例情況），因為普通卷積一視同仁地對待所有節點，不區分它們的位置資訊。

ChebNet 定義為：

y = f ( ∑ j = 1 C α j T j ( L ~ ) x ) \mathbf{y}=f\left(\sum_{j=1}^{C} \alpha_{j} T_{j}(\tilde{\mathbf{L}}) \mathbf{x}\right) y=f(j=1∑C​αj​Tj​(L~)x)

其中， T j T_{j} Tj​ 表示切比雪夫多項式的第 j j j 項， α j \alpha_{j} αj​ 是相關系數，這個公式是 ChebNet 的基本定義。

【1】ChebNet 可參考 3.4 GCN-2

ChebNet 可以定義為不同 SLCs 的總和，其中每一個都可以将圖結構定義為Laplacian矩陣的Chebyshev多項式，即對于第 j j j 個 SLC， S j = T j ( L ~ ) ∈ R N × N \mathbf{S}^{j}=T_{j}(\tilde{\mathbf{L}}) \in \mathbb{R}^{N \times N} Sj=Tj​(L~)∈RN×N（時刻記住 S S S 表示圖結構資訊）。

2. SLCNN for Traffic Forecasting

Structure Learning Convolutional Neural Network (SLCNN) 即為文章所提出的模型名稱，左側（橘色底色）部分是 SLCNN 整體結構，看上去還是比較簡明的。模型的關鍵在于，不同于正常模型在網絡的每一層都具有相同的結構（參數），該模型中每個SLCNN Layer都是不同的（學習到的參數不同），每一層都學習到不同的全局和局部圖結構。那麼，如何構造不同的SLCNN Layer？

每個 SLCNN Layer 由 global SLC 和 local SLC 組成：

• global SLC：用于捕捉全局圖結構資訊，不管節點是遠是近
• local SLC：用于更好捕捉局部圖結構資訊

2.1 Global Structure Learning Convolution

利用 ChebNet 定義 global SLC，公式如下圖，其中橘色部分為可學習的參數

• T k ( ⋅ ) ∈ R N × N T_{k}(\cdot) \in \mathbb{R}^{N \times N} Tk​(⋅)∈RN×N 是 k k k 階切比雪夫多項式。要注意的是 使用的不再是預定義的鄰接矩陣，其中 W s \mathbf{W}^{s} Ws 是靜态的圖鄰接矩陣（學習得到）， W d \mathbf{W}^{d} Wd 是動态的圖鄰接矩陣，但不是學習得到的參數，而是 ϕ ( x ) \phi(\mathbf{x}) ϕ(x) 的輸出，其中 W ϕ \mathbf{W}_{\phi} Wϕ​ 是可學習的參數。
• 公式的前半部分是對全局靜态結構模組化(global static)，後半部分是對全局動态結構模組化(global dynamic)。

回憶1.1節作者提出的 SLC 的結構 y i = f ( ∑ e i j ∈ E S i j w j x j ) y_{i}=f\left(\sum_{e_{i j} \in \mathcal{E}} S_{i j} w_{j} x_{j}\right) yi​=f(∑eij​∈E​Sij​wj​xj​)，并且作者認為 ChebNet 可以用幾個特定的 SLCs和 的形式表示，那麼：

• 靜态圖結構部分表示為 S k = T k ( W s ) \mathbf{S}^{k}=T_{k}\left(\mathbf{W}^{s}\right) Sk=Tk​(Ws)
• 動态圖結構部分表示為 S k = T k ( W d ) \mathbf{S}^{k}=T_{k}\left(\mathbf{W}^{d}\right) Sk=Tk​(Wd)

這部分和普通圖卷積差別展現在：

• STGCN 和 DCRNN 是使用預定義的鄰接矩陣，而 SLC 的鄰接矩陣從資料中學習得到。
• STGCN 和 DCRNN 采用帶門檻值的高斯核定義鄰接矩陣，這樣一來它們能捕捉的就隻能是局部圖結構資訊，本文通過 W s W d W^s W^d WsWd 展現的是全局的資訊。
• 以往模型所有資料均共享同一個權重矩陣，而本文 W d W^d Wd 的值依賴于目前時刻的輸入，是以不同輸入資料具有的不同圖結構資訊也被展現了出來。

2.2 Local Structure Learning Convolution

local SLC 的定義和 global 的類似，橙色部分依舊是可學習的參數， B d B^d Bd 來自于目前輸入資料的計算。

2.3 Pseudo Three Dimensional SLC

前面兩節都是對空間次元的模組化，本節提出 P3D-SLC 用于捕捉時間依賴性（也有空間）。

P3D 網絡主要解決了兩個問題：

• 解決原始3D卷積計算量過大的問題
• 仿照 resnet 建構更深的網絡

P3D 網絡大概做法：

原始3D卷積核333，現在把它拆成：

• 1 *3 *3的2D卷積，用于對空間關系模組化
• 3 *1 *1的1D卷積，用于對時間關系模組化

【2】Pseudo-3D Residual Networks 算法筆記

【3】Learning Spatio-Temporal Representation with Pseudo-3D Residual Networks

這部分說的很簡略…實在不知道是怎麼用的P3D = =，最後再看一下 SLC layer 圖，左邊這個是沒有P3D的，有邊有P3D。

3. Experiments

資料集：6個資料集

• PeMS-S / PeMS-BAY / METR-LA 是公共資料集
• BJF / BRF / BRF-L 是作者采集的資料

對比模型：

• Historical Average (HA), Auto-Regressive Integrated Moving Average(ARIMA), FC-LSTM, Feed-Forward Neural Network, GCNN methods, GWN, STGCN, DCRNN
• SLCNN-NP3D 沒有P3D
• SLCNN-P 當機了SLCNN的結構學習能力，隻使用預定義的圖形結構并删除P3D子產品

  

  

這兩個資料集上 Graph wavenet 效果更好，好玄學…

除此之外，還驗證了 Local and Global Graph 和 Static and Dynamic Graph 的有效性，以及計算效率。