面向时空图建模的图小波卷积神经网络模型∗

姜 山,丁治明,朱美玲,严 瑾,徐馨润

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)探索本文模型在图节点分类、连接关系预测等多个领域的应用.