论文笔记--Inductive Graph Neural Networks for Spatiotemporal Kriging

Inductive Graph Neural Networks for Spatiotemporal Kriging(AAAI 21)

Summary

在交通中kriging问题（恢复未采样位置/传感器的信号），大多数现有的可扩展Kriging方法(例如，矩阵/张量补全)是直推式学习（transductive），加入新的传感器需要重新训练。

作者提出归纳式图神经网络Kriging模型来恢复图上未采样节点的数据。具体的作者生成随机子图作为样本，并对每个样本重建相应的邻接矩阵。模型通过重构每个样本子图上的所有信号，学习空间消息传递机制。

Problem Definition

问题定义

时空Kriging是指在未采样传感器位置给定从采样传感器位置得到的信号后，对时间序列信号进行插值的任务。以高速公路网络上的一组交通传感器为例：将传感器建模为网络中的节点，并且可以根据高速公路网络定义网络的边。在这种情况下，时空Kriging的目标是恢复无传感器位置的交通状态时间序列。因此，Kriging可以看作是建立虚拟传感器的过程。

具体的如下图，训练数据是n个节点再P个时间观察到的历史数据。t到t+h是需要完成Kriging的时间段，这段时间内已知个点的观测数据，目标是得到个新加节点的观测数据。其中可能，一些传感器退役或者加入。同时可能存在缺失信息。所以Kriging的目标就是给定去获取。

一般的时空Kriging问题常使用高斯过程(GP)回归的方法，但是方法计算量过大，难以使用现有的图核 (Graph kernal) 建模网络系统。另一种是图正则化矩阵补全的方法，这些方法结合低秩结构和时空正则化，可以同时表征数据的全局一致性和局部一致性，但是这种方法是直推式的，再引入新节点后需要重新训练模型；并且低秩方案无法适应时变/动态图结构。

Method

1、使用随机的方法生成一系列的子图用于训练

随机采样节点生成子图，得到采样后的图信号Xsample 并构建邻接矩阵Wsample。构建的图是一个全连接的图，边的权重代表两点之间的距离决定。并建立一个mask矩阵Msample来保持一些点的图信号不被观测。

2、GNN训练

第二步是使用Xsample，Wsample，Msample来训练GCN网络。如下图

输入数据为训练模型来重构Xsample。

3、GNN结构

由于Kriging问题中恢复的窗口一般较短，作者没有使用GNN加序列模型（RNNs, TCNs）的方法，而采用DCRNN中的扩散图卷积（DGCN）做为模型的基本结构块。

DGCN计算公式如下

其中，，分别表示前向和后向转移矩阵。对于无向图则。使用切比雪夫多项式的方法进行卷积，K表示阶数，。而θ表示可学习参数。

需要注意的是传统的GNN不同的是训练的每个样本，由于图中采样的点不同，图结构都是不同的。

具体结构如下，是一个见到那的三层结构。

第一次的输入为，，通过DGCN（扩散卷积)得到H₁，由于被mask的节点在第一层中只将0传递给它们的邻居，因此一层GCN不能产生理想的特性。所以添加第二层结构，公式表示如下

最后再使用另一个DGCN重构图信号。

4、loss函数

为了使学习到的消息传递机制对所有节点更加一般化，作者使用观察节点和未观察节点上的总重构误差作为我们的损失函数，公式如下

Experiments

数据集

METR- LA是四个月来洛杉矶207个传感器的交通速度数据集

NREL记录了2006年阿拉巴马州137个光伏发电厂的太阳能输出

USHCN包含了1899 - 2019年1218个地点的月降水量

SeData是一个西雅图高速公路网络交通速度数据集，323环探测器。

PeMS-Bay也是一个交通速度数据集，325个传感器。（用于验证模型可迁移）

①Kriging性能

下表显示了IGNNK和其他基线模型在四个数据集上的Kriging性能。作者的方法始终优于其他基线模型，大部分数据集上RMSE和MAE都是最低的。

下图是重构结果的可视化结果对比

②邻接矩阵生成方法对比 和 迁移效果

然后验证了使用高斯核生成的邻接矩阵，和使用连通性生成二值邻接矩阵的效果。显然是前者好。最后两行表示训练在METR-LA 和SeData上模型迁移到PeMS-Bay数据集上的效果。

下图这是迁移效果的可视化情况

③虚拟站点效果可视化

图a为在交通速度数据上，在1号和177号两相邻节点之间，每隔5m设置一个虚拟站点，可视化效果如下。从1号到177号平稳的过渡。

图b为在降水量数据集上，在8到10号点时间取100个虚拟点，降水量可视化如下。

创新点

使用GNN来建立一个归纳式的模型解决时空中的Kriging问题。