单时序特征图卷积网络融合预测方法

李昊天,盛益强

(1.中国科学院声学研究所国家网络新媒体工程技术研究中心,北京 100190; 2.中国科学院大学,北京 100049)

0 引 言

图是对一组对象(节点)及其关系(边)进行建模的一种数据结构。近年来，由于图强大的表示能力，使得图结构在社交、生物学、物理系统、交通、知识图谱等诸多领域有着广泛的应用[1-5]。目前，对图的研究主要集中在图分类、图预测、图嵌入、图聚类等领域[6]，其中图预测领域中的图节点预测研究，对于智慧城市中的交通管理、网络安全中的异常流量检测[7]、社交网络中的热点评估[8]等方面都有着深远的意义。

图节点预测通常是基于一段时间内各个图节点的特征，来预测未来某一时刻图节点的某些属性特征。图节点预测的研究方法可以分为空间法、时序法和空间时序混合法3类。其中空间法是一种基于图中点与点之间的拓扑关系来分析图的属性变化与传播方式的方法，常见方法有PageRank[9]、HITS[10]、GCN[11]、GNN[12]等。这类方法不依赖于历史时间的数据，而更关心同一时刻相邻各个节点的状态信息，对于短时预测有着更好的效果，但对于长时预测以及各个节点自身个性化特征的学习表现欠佳。时序法是一种根据待预测节点的历史时序序列，学习其自身属性关于时间变化的函数，从而实现预测的方法，主流方法包括ARIMA[13]、LSTM[14]、GRU[15]、SAEs[16]等。这类方法的优点是依托传统的序列学习算法，更关注节点长时间的变化，容易刻画出节点自身的属性特征，但是由于没有合理利用节点间连接关系的信息，一些易于传播的特性如交通网络中的汽车流量、社交网络中的热点热度等容易被遗失，从而导致对节点的刻画不完整，影响预测精度。空间时序混合法是一种将空间特征和时序特征混合考虑的方法，综合预测未来时刻的节点属性，常见方法包括T-GCN[17]、GCAN[18]、AST-GCN[19]等。这类方法综合了节点的空间性和时间性信息，是目前复杂网络节点预测中最为常用的一类算法，但这类算法面临的问题是如何合理地提取空间特征和时间特征，以及如何让二者相互融合，在不同的应用场景下，对于空间信息和时间信息的不同侧重问题也亟待解决。

目前，在一些复杂网络[20]中，比如交通网络，很难同时采集到各个交通节点的流量、车辆平均速度、车辆滞留时间等信息，并且通常在关心一种特征的预测情况的同时很难去考虑采集其他特征，因此单一时序特征场景实际上是一种很自然也很常见的图预测场景。遗憾的是，对于单一时序特征场景的图节点预测问题的研究存在一些问题，时序法没有利用节点的空间信息，而空间法和时空结合法，大部分都需要基于图卷积网络来进行空间特征提取，而这种方法，在特征单一情况下的训练参数矩阵将退化为单变量参数，导致空间特征的提取严重依赖于初始化的连接关系，没有达到数据驱动的效果。虽然T-GCN等是解决单一时序场景的时空图卷积算法，但由于这些算法是将连续几个时刻的数据，作为多维特征进行处理，并不属于严格意义上的单一特征，此外由于连续时间的长度是一个超参数，对于不同场景缺乏普适性。针对上述问题，本文提出一种单一时序特征场景下的结合图卷积网络与长短时记忆网络(LSTM)的图节点预测算法，通过将训练参数前置，并且将空间特征代替时序原始特征数据，进行时序训练，实现特征的融合，达到了良好的预测效果。

1 问题定义

单时序特征场景下的图网络的预测问题，可以进行如下描述，图网络定义为G=(V,E)，其中V={v1,v2,…,vN}是节点集合，对应图网络的数据节点，E={e1N,e2N,…,eNN}是边集，对应图中数据节点之间的连接关系强弱，值越大说明关系越强，为0表示2个节点并无关联。单时序特征是指每个节点vi在给定时刻t有且只有一个特征数值gi(t)。预测问题是指通过历史数据(Xt-s,Xt-s+1,…,Xt)来预测下一时刻Xt+1的信息，即求F(·)满足:

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

(1)

其中，Xt为t时刻的所有节点的时序特征Xt=[g1(t),g2(t),…,gN(t)]。

2 图卷积网络与长短时记忆网络

图卷积网络(GCN)是利用图的谱理论来处理图结构数据，从而获取其空间特征信息。图卷积计算需要先获得图的拉普拉斯矩阵L，定义为：

(2)

其中，A为图G的带权邻接矩阵，即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)，进一步，令UTg为对角矩阵gθ，并运用层次线性模型约束[11]和切比雪夫优化方法[21]得到：

(4)

利用式(4)中定义好的卷积，即可直接用于图卷积网络的卷积层，公式如下：

(5)

其中,H(l)为第l层的输出，W(l)为第l层的待训练参数，且W(l)∈Rk×m，k是l-1层每个节点的特征维度，m是l层每个节点的特征维度，通常有m≤k，在一般的图卷积网络训练中，图卷积层层数在2层左右，用于提取图的空间拓扑信息。

图1 LSTM模块图

LSTM是循环神经网络[22](RNN)的一种改进，它通过加入3个门控单元，有效解决了RNN中常见的梯度消失和梯度爆炸的问题，是一种常用的序列学习网络。

LSTM模块如图1所示，包含输入门、遗忘门、输出门，其中遗忘门决定从之前的序列中丢弃哪些信息，对应公式为：

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

(6)

输入门决定当前状态下需要留存的信息，并计算新的候选值用于状态更新，其公式如下：

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

(7)

(8)

则更新后的状态由输入门和遗忘门共同决定。即:

(9)

最后，输出门负责决定将更新后的状态的部分进行输出，其运算方法如下：

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

(10)

ht=ot×tanh(Ct)

(11)

上述式(6)～式(11)中的Wf、Wi、WC、Wo、bf、bi、bc、bo是待训练参数，[ht-1,Xt]表示ht-1和Xt组合，σ(·)为标准的S型曲线，定义如下：

(12)

tanh(·)取值范围为[-1,1]的中心对称S型曲线，定义如下：

(13)

3 结合LSTM的单时序特征图卷积网络预测

在单时序特征条件下，如果按照传统的图卷积网络进行训练，则式(5)中的参数矩阵W(l)的的维度k将退化为1，训练参数严重不足，会导致欠拟合现象；而如果将每个节点连续一段时间s的特征值作为一组特征，并将接下来一小段时间的预测值作为输出，进行图卷积网络训练会产生2个问题:1)作为输入的一段时间内的特征值之间的关系信息将被丢失，容易过拟合；2)输入空间的时间间隔和输出空间的时间间隔成为严重影响实验效果的超参数，对于不同的网络数据集，缺乏普适性。

因此为了解决上面2个问题，本文提出一种结合LSTM的单时序特征图卷积网络算法(SST-GCN)，首先采用每一层只输入和输出一个时刻的特征数据，并将原有的参数矩阵前置，扩展了参数训练规模和维度，同时增加了原始邻接矩阵的可变性，避免了欠拟合现象并且降低了原始邻接矩阵不准确所带来的误差。其次，将图卷积层的输出作为空间特征结合LSTM进行时序特征的训练，构成如图2所示的结合时空特性的神经网络模型。

图2 SST-GCN网络结构图

模型先将每个时刻图网络的特征信息Xt通过一个前置参数的图卷积网络，该网络包含2层图卷积层，每层前向传播公式为：

(14)

对比式(5),这里W(l)即为前置的训练参数矩阵。

将图卷积网络的输出G(Xt)作为LSTM网络的输入进行时序特征的提取，采用新的LSTM公式如下:

(15)

与式(6)～式(11)相比，将GCN网络提取出的空间特征向量G(Xt)代替了原始的时序特征向量Xt，达到了空间特征和时间特征相结合的训练效果。

本文模型在训练时采用L2范数作为损失函数，并添加正则化项防止过拟合。具体公式如下：

(16)

4 实验与分析

4.1 数据集描述以及预处理

本文采用2套交通网络数据集进行实验验证，第1套是2012年洛杉矶交通数据集(Los)，它包括207个传感器记录行驶车辆的速度，每隔5 min记录一次，去除掉部分损失采样信息，得到每个传感器的时序特征共2016个，传感器组成的邻接矩阵由传感器之间的距离来确定，距离越远其连接强度越弱。连接强度和距离之间的关系表示为：

(17)

其中，x表示vi和vj的距离，eij为连接强度，当x<5 km时，eij在0.5～1之间，否则为0。

第2套数据集是美国加州交通监视系统PeMS采集的数据集，是交通网络预测领域常用的开源数据集(http://pems.dot.ca.gov/)[23]，它每30 s采集一次数据，本文使用的采集点有307个，通过聚合每5 min内的数据信息，得到每5 min一次的速度数据，每个采集点获得了16992个时序特征，同样采集点之间的邻接矩阵由它们之间的距离刻画，参考式(17)。

2套数据集均将按照时序特征长度8：2的比例划分为训练集和测试集，最终在测试集上通过定长的历史连续时序序列来预测下一个时刻的数据，并和真实的数据进行对比验证。

4.2 实验与评估

1)均方根误差(RMSE)：

(18)

2)平均绝对误差(MAE)：

(19)

3)平均准确率(AC)：

(20)

4)确定系数(R2)：

(21)

5)方差分数(var)：

(22)

上述评价指标中，RMSE和MAE越小或者AC、R2、var越大说明预测结果越准确。

本文实验所用超参数为：输入序列长度为10，学习率为0.001,隐藏层为32层，batchsize为64，训练300个epoch。

所使用的实验平台为Ubuntu16.04，GPU采用NVIDIA Tesla K80，基于Tensorflow2.0框架进行实验。

在Los和PeMS数据集上的各个算法的实验结果分别如表1和表2所示。

表1 Los实验结果

表2 PeMS实验结果

在各项评价指标上各个算法的表现可以从表1和表2中看出，SST-GCN各项指标均领先于主流的交通预测算法或与其一致，其中在平均准确度AC、均方根误差RMSE上优于其他算法5%左右。在方差分数var、确定系数R2上与其他算法基本一致，且与SST-GCNwithout-p的对比实验结果表明，参数矩阵前置能够产生良好的增益。因此可知SST-GCN算法的预测效果综合优于其他几种算法。

5 结束语

本文提出了一种混合时空特性的单时序特征图卷积网络的预测方法。一方面通过将图卷积网络的参数矩阵前置，解决了传统图卷积网络在单一时序特征下的参数退化问题。另一方面通过结合LSTM和GCN模型，实现了空间特征和时序特征的融合预测，提高了预测精度。在交通网络中的实验结果表明，与常见的GRU、LSTM、SAEs、T-GCN等算法相比，本文所提算法预测准确度更高。