Hierarchical Graph Convolution Networks for Traffic Forecasting (AAAI 21)
Summary
作者提出了一种新的层次图卷积网络(HGCN)，通过操作微观和宏观交通图进行交通预测。
Problem Definition
目前基于GCN的交通预测方法都忽略了交通系统的自然层次结构，既包括道路网络的基本微观层，也包括路网的宏观层，区域或社区的特征和信息在传统的交通规划或宏观特征分析转化理论中发挥着重要作用。
问题定义
与一般的交通预测问题相同，给定前T时刻的历史观察信息，预测未来T’时刻的交通信息。
Method
构建流量层次图
①micro graph
通过道路的自然结构构建，作者使用的使节点GPS坐标计算距离构建。将路网中观察到的数据表示为 X ⃗ = { X 1 , … , X t , … , X T 1 } ∈ R N × T 1 × D \vec{X}=\left\{X_{1}, \ldots, X_{t}, \ldots, X_{T_{1}}\right\} \in \mathbb{R}^{N \times T_{1} \times D} X={ X1,…,Xt,…,XT1}∈RN×T1×D
②macro graph
对路网图（micro graph）使用谱聚类算法构建区域图（macro graph）。过程如下图
聚类后macro节点的特征根据micro节点的平均值确定。对于边，两区域之间存在相连的micro节点则区域相连。构建得到 X R = { X 1 R , … , X t R , … , X T 1 R } ∈ R N A × T 1 × D X^{R}=\left\{X_{1}^{R}, \ldots, X_{t}^{R}, \ldots, X_{T_{1}}^{R}\right\} \in \mathbb{R}^{N^{A} \times T_{1} \times D} XR={ X1R,…,XtR,…,XT1R}∈RNA×T1×D
model
整体框架如下图
①时空块（Spatial-Temporal Block）
S-T块由时间门卷积、空间门图卷积和时间注意机制三部分组成，分别用于学习区域数据的局部时间特征、局部时空特征和全局时间关系。
a) Temporal Gate Convolution
利用时间轴上的门卷积并行提取分层局部时间特征，同时为了扩展感受野使用膨胀率dil为2的膨胀时间卷积，卷积公式如下：
T C ( X ⃗ ) = Φ ⋆ X ⃗ = Con v t s d i l ( X ⃗ ) ( β ⃗ 1 , β ⃗ 2 ) = split ( T C ( X ⃗ ) ) T G C ( X ⃗ ) = tanh ( β ⃗ 1 ) ∗ sigmoid ( β ⃗ 2 ) \begin{aligned} T C(\vec{X}) &=\Phi \star \vec{X}=\operatorname{Con} v_{t_{s}}^{d i l}(\vec{X}) \\ \left(\vec{\beta}_{1}, \vec{\beta}_{2}\right) &=\operatorname{split}(T C(\vec{X})) \\ T G C(\vec{X}) &=\tanh \left(\vec{\beta}_{1}\right) * \operatorname{sigmoid}\left(\vec{\beta}_{2}\right) \end{aligned} TC(X)(β1,β2)TGC(X)=Φ⋆X=Convtsdil(X)=split(TC(X))=tanh(β1)∗sigmoid(β2)
C o n v t s Conv_{t_s} Convts就是核大小为 t s t_s ts的时间卷积。Split表示等分操作。
b）Spatial Gate Graph Convolution
使用嵌入扩散图卷积。公式如下
P f = A / rowsum ( A ) . P b = A T ⋅ rowsum ( A T ) G T C ( X ⃗ ) = ∑ m = 0 M − 1 Φ m , f ⋆ P f m x + Φ m , b ⋆ P b m x + Φ m , a d p ⋆ A ~ a d p m x ( β ⃗ 1 , β ⃗ 2 ) = split ( GTC ( X ⃗ ) ) D G G C ( X ⃗ ) = tanh ( β ⃗ 1 ) ∗ sigmoid ( β ⃗ 2 ) A ~ a d p = norm ( Relu ( E 1 E 2 T ) ) \begin{gathered} P_{f}=A / \text { rowsum }(A)_{.} \\ P_{b}=A^{T} \cdot {\text { rowsum }}\left(A^{T}\right) \\ G T C(\vec{X})=\sum_{m=0}^{M-1} \Phi_{m, f} \star P_{f}^{m} x+\Phi_{m, b} \star P_{b}^{m} x \\ +\Phi_{m, a d p} \star \tilde{A}_{a d p}^{m} x \\ \left(\vec{\beta}_{1}, \vec{\beta}_{2}\right)=\operatorname{split}(\operatorname{GTC}(\vec{X})) \\ D G G C(\vec{X})=\tanh \left(\vec{\beta}_{1}\right) * \operatorname{sigmoid}\left(\vec{\beta}_{2}\right) \\ \tilde{A}_{a d p}=\operatorname{norm}\left(\operatorname{Relu}\left(E_{1} E_{2}^{T}\right)\right) \end{gathered} Pf=A/ rowsum (A).Pb=AT⋅ rowsum (AT)GTC(X)=m=0∑M−1Φm,f⋆Pfmx+Φm,b⋆Pbmx+Φm,adp⋆A~adpmx(β1,β2)=split(GTC(X))DGGC(X)=tanh(β1)∗sigmoid(β2)A~adp=norm(Relu(E1E2T))
其中使用norm替代softmax避免所有节点的全连接，保持矩阵的稀疏性，norm定义如下。（没搞懂为啥这方法能稀疏）
A a d p = Relu ( E 1 , E 2 T ) D a d p i i = ∑ j A a d p i j D a d p 1 = diag ( 1 / ( D a d p i i ) ) A ~ a d p = D a d p 1 A a d p \begin{aligned} A_{a d p} &=\operatorname{Relu}\left(E_{1}, E_{2}^{T}\right) \\ D_{a d p_{i i}} &=\sum_{j} A_{a d p_{i j}} \\ D_{a d p 1} &=\operatorname{diag}\left(1 /\left(D_{a d p_{i i}}\right)\right) \\ \tilde{A}_{a d p} &=D_{a d p 1} A_{a d p} \end{aligned} AadpDadpiiDadp1A~adp=Relu(E1,E2T)=j∑Aadpij=diag(1/(Dadpii))=Dadp1Aadp
c）Temporal Attention Mechanism
用于捕获全局时间关系。公式如下
E = V e σ ( ( X ⃗ ) T U 1 ) U 2 ( ( X ⃗ ) U 3 ) T + b e ) E i , j ′ = exp ( E i , j ) ∑ j = 1 T 1 2 exp ( E i , j ) Tatt ( X ⃗ ) = E ′ X ⃗ \begin{aligned} E &\left.=V_{e} \sigma\left((\vec{X})^{T} U_{1}\right) U_{2}\left((\vec{X}) U_{3}\right)^{T}+b_{e}\right) \\ E_{i, j}^{\prime}&= \frac{\exp \left(E_{i, j}\right)}{\sum_{j=1}^{T_{1}^{2}} \exp \left(E_{i, j}\right)} \\ \operatorname{Tatt}(\vec{X})&=E^{\prime} \vec{X} & \end{aligned} EEi,j′Tatt(X)=Veσ((X)TU1)U2((X)U3)T+be)=∑j=1T12exp(Ei,j)exp(Ei,j)=E′X
用三个可学习参数U辅助对三维数据计算注意力系数。
三部分总结如下
②交互层（Interaction Layer）
使用dynamic transfer block融合region特征和road特征。定义一个转移矩阵，如果road i属于region j，就把region j的特征拼接到road i上。转移矩阵 t r a n ∈ R N × N R tran \in R^{N\times N^R} tran∈RN×NR定义如下
[ Tran ] i j = { 1 , if the node i belongs to the region j 0 , else [\operatorname{Tran}]_{i j}=\left\{\begin{array}{l} 1, \text { if the node } i \text { belongs to the region } j \\ 0, \text { else } \end{array}\right. [Tran]ij={ 1, if the node i belongs to the region j0, else
同时考虑到交通数据使动态变换的，因此转移矩阵也应该使动态的，利用注意力机制构建动态转移矩阵公式如下
E d = σ ( ( F ⃗ ) T U 1 ) U 2 ( ( F R → ) U 3 ) T + b e ) E d = E d − mean ( E d , axis = 0 ) Tran d = σ ( E d ) ∗ Tran \begin{aligned} E^{d} &\left.=\sigma\left((\vec{F})^{T} U_{1}\right) U_{2}\left(\left(\overrightarrow{F^{R}}\right) U_{3}\right)^{T}+b_{e}\right) \\ E^{d} &=E^{d}-\operatorname{mean}\left(E^{d}, \text { axis }=0\right) \\ \operatorname{Tran}^{d} &=\sigma\left(E^{d}\right) * \operatorname{Tran} \\ \end{aligned} EdEdTrand=σ((F)TU1)U2((FR)U3)T+be)=Ed−mean(Ed, axis =0)=σ(Ed)∗Tran
dynamic transfer block计算公式可以表示为
F Tran R → = Tran d ∗ F R → F out → = Concat ( F ⃗ , F Tran R → ) \begin{aligned} \overrightarrow{F_{\text {Tran }}^{R}} &=\operatorname{Tran}^{d} * \overrightarrow{F^{R}} \\ \overrightarrow{F_{\text {out }}} &=\operatorname{Concat}\left(\vec{F}, \overrightarrow{F_{\text {Tran }}^{R}}\right) \end{aligned} FTran RFout =Trand∗FR=Concat(F,FTran R)
Experiments
数据集
济南和西安滴滴的交通速度数据。点的个数为561和792
HGCN_WH表示只使用路***征
HGCN_WDF表示不使用动态转移矩阵
不同的聚类区域数的影响。
创新点
提出分层次的方法，设计动态迁移模块实现region与route的融合。其他部分大部分都参考其他论文。
京公网安备 11010502036488号