论文标题：INCREASE: Inductive Graph Representation Learning for Spatio-Temporal Kriging

论文地址：https://arxiv.org/abs/2302.02738

论文代码：https://github.com/zhengchuanpan/INCREASE

论文作者：郑传潘（厦门大学），范晓亮（厦门大学），王程*（通讯作者，厦门大学），Jianzhong Qi（University of Melbourne），陈超超（浙江大学），陈龙彪（厦门大学）

今天介绍的是厦门大学ASC实验室（asc.xmu.edu.cn）近期被WWW-23会议接收的一篇论文：「INCREASE: Inductive Graph Representation Learning for Spatio-Temporal Kriging」。国际万维网大会（简称WWW）是计算机与互联网领域的顶级学术会议，是CCF A类推荐会议。会议每一年举办一届。WWW-23将于2023年4月30日-5月4日在美国德克萨斯州奥斯汀举行。本次会议共收到1900篇投稿，录用率约为19.2%。

本文以时空图数据的克里金插值为应用场景，提出了引入多重异质关系的归纳式时空图数据表示学习方法（简称INCREASE），旨在通过对时空克里金问题中的异构空间关系和不同的时间模式进行联合建模以获得未知节点的时空特征表示，并设计了一种多关系注意机制，以用于动态融合复杂时空特征信息而最终计算得到克里金序列。

一、研究背景和挑战

在现实场景中，由于高昂的运营成本，用于收集各类时空数据的设备数量往往存在一定限制，且不同区域间设备的分布通常存在不均衡性。这使得仅使用观测到的数据很难进行细粒度和高空间分辨率的建模。时空克里金插值旨在解决此类数据稀疏性及数据可用性不均衡的问题。归纳式时空克里金插值算法在不需要重新训练模型的情况下，能够直接对未知节点生成时序序列。然而，当前已有的归纳式时空克里金插值算法效果并不理想，仍存在以下三点重要的研究挑战：

挑战1：如何为未知节点选取最相关的已知节点集合，并准确建模它们的相似性和差异性？在时空图数据中，未知节点和已知节点之间存在着复杂的多重异质关系。如图 1所示为一个交通场景下的未观测地区与已部署传感器之间的多重异质关系的示例。在估计地区 X 的交通流量时，不同的已知节点与地区X间可能存在不同关系：传感器A与地区X的距离较近（地理邻近性）、传感器B和地区X由于都邻近购物中心而具有相似的功能性（功能相似性）、地区C的车流可能由于路径选择等原因流向地区X（转移概率）。并且，根据某种特定关系建立联系的两个地区之间在数据模式上的差异性也不容忽视。比如，地区C和地区X的交通模式在上下班时期高度相似，但在其他时间则可能存在明显差异性。

挑战2：如何在多重异质关系中利用已知节点数据自适应地建模未知节点在时间维度上的信息流动模式？由于缺乏历史数据，直接对未知节点的时间相关性进行建模并非易事。此外，不同的未知节点可能具有不同的时间模式，这使得这个问题更具挑战性。

挑战3：如何动态地将异构空间关系与不同的时间模式结合起来？在时空图数据中，多重异质关系的重要性是动态变化的。如图 1所示，估计地区X的数据时，在上下班高峰时期，转移概率关系（地区C）可能占主导地位，但是在其他时间，地理邻近性（地区A）或者功能相似性关系（地区B）可能更为重要。

图 1：已知节点与未知节点间多重异质关系示意图

因此，针对上述挑战，本文提出了归纳式图表示学习的时空克里金插值方法（简称INCREASE）。首先，提出了空间聚合模块和时序建模模块，能够在空间维度上聚合多重异质关系的邻居节点信息得到未知节点的特征表示，并在时间维度上根据邻居节点的信息流动模式指导未知节点时间相关性的建模。其次，提出了多关系融合模块，能够在不同时间步动态地融合多重异质关系中的时空信息，以得到表达能力更强的未知节点表示。最后，在三个时空图数据集上开展了时空克里金插值的实验，实验结果证明了INCREASE的有效性，并且已知节点的数量越少、算法的优势越明显。本文的研究成果，有效地利用归纳式图表示学习方法提升了时空克里金插值的性能。

二、问题形式化

假设有N个传感器，每个传感器记录了C个指标（如交通速度、交通流量等）,其中第i个传感器在第t个时间步的数据表示为，第i个传感器在p个时间步的数据序列表示为，全部N个传感器在p个时间步的数据表示为。

问题定义（时空克里金插值）：时空克里金插值是指利用给定的N个传感器在p个时间步的读数X，估计该时间段内M个未观测地区的数据，其中，表示未观测地区l的估计序列。

三、INCREASE算法框架

INCREASE算法框架如图 2所示，整体模型包含三个模块：空间聚合模块对多重异质关系（地理邻近性关系、功能相似性关系、转移概率关系)中未知节点和已知节点之间的相似性和差异性同时进行建模，以聚合最相关的邻居节点信息，得到未知节点的归纳式特征表示；时序建模模块设计了关系感知 GRU 神经网络在多重异质关系中自适应地根据邻居节点在时间维度上的信息流动模式指导未知节点时间相关性的建模；多关系融合模块设计了多关系注意力机制在不同时间步动态地融合多重异质关系中学习到的未知节点表示，并输出最终的估计序列。

图 2 : INCREASE整体框架

空间聚合模块：（1）多重异质关系编码，我们定义了节点间的三种空间异质关系，分别是地理邻近性（在空间上距离较近的地区之间可能具有强相关性）、功能相似性（具有相似功能性的地区之间可能具有强相关性）和转移概率（数据流动可能使地区间具有相关性），并分别进行了三种关系的编码。（2）邻居节点信息聚合，对多重异质关系进行编码后，我们根据未知节点与已知节点间关系的编码对不同邻居节点的信息进行了聚合，得到未知节点的特征表示。由于节点间可能存在差异性，仅通过关系编码进行聚合只考虑了节点间相似性，因此我们设计了一种节点间关系差异性的表示，用于为相似性特征表示添加惩罚，以得到融合节点相似性及差异性的未知节点表示。

时序建模模块：（1）融合外部因素的GRU神经网络，GRU神经网络能够有效建模序列数据中的时序依赖关系，即每一个时间步的状态应该与它之前所有时间步的状态相关。由于时空数据容易受到外部因素的扰动，因此，我们将外部因素也嵌入到GRU神经网络中进行学习。（2）关系感知GRU神经网络，由于缺乏历史数据，未知节点在时间维度上的依赖关系难以确定，我们根据邻居节点在时间维度上的信息流动模式指导未知节点时间相关性的建模。我们首先根据未知节点与已知节点每一时间步的差异性来确定输入到GRU网络中的未知节点表示的重要性，其次根据差异性表示对历史时间步的重要性进行调整，最后将两部分重要性表示结合到GRU神经网络的输入门及遗忘门中来进行关系感知GRU网络的计算，使其能够在多重异质关系中根据邻居节点在时间维度上的信息流动模式指导未知节点时间相关性的建模。

多关系融合模块：通过空间聚合模块和时序建模模块，可以得到各个关系中未知节点在各个时间步的状态表示。不同关系中的未知节点表示聚合了不同的邻居节点信息，因此，有必要对它们进行融合，以提高未知节点表示的表达能力。然而，在时空图数据中，多重异质关系的重要性会随着时间动态变化。对此，我们提出多关系注意力机制在不同时间步动态融合不同关系中学习到的未知节点表示。首先分别为每一个时间步计算未知节点各个关系的注意力系数，然后基于计算得到的注意力系数对多重异质关系中的未知节点表示进行融合得到表达能力更强的未知节点表示，最后是用一个两层的全连接网络输出最终的估计序列。

四、实验与验证

图 3：模型的训练与测试

模型的训练与测试策略：如图 3所示，首先根据时间顺序将数据集分为训练集和测试集，并且测试集中的未知节点在训练集中是“不可见”的。在训练阶段，依次把每一个已知节点目标节点，使用其他N-1个已知节点的数据来估计节点i的数据。使用真实值与估计值间的均方误差作为损失函数。

数据集：本文使用三个时空图数据集来验证模型的性能，分别是METR-LA数据集（美国洛杉矶的207个传感器采集的4个月的交通速度数据，数据的采集时间间隔为5分钟）、北京数据集（北京市36个传感器采集的1年的空气质量指数，数据的采集时间间隔为1小时。每个传感器记录了PM2.5、二氧化硫浓度、一氧化碳浓度等指标，本文仅使用PM2.5的数据）和厦门数据集（厦门市95个传感器采集的5个月的交通流量数据，数据的采集时间间隔为5分钟）。

评价指标：本文使用四个常用的评价指标来评估INCREASE模型的性能，分别是：均方根误差（RMSE）、平均绝对误差（MAE）、平均绝对百分比误差（MAPE）、R2（R-square）。

更多数据集描述、实验细节设置、baseline介绍及参数设置，请见原文。

实验结果1. 性能比较

表 1：三个数据集上各个模型的性能对比

表 1展示了各个模型在三个数据集上的时空克里金插值性能对比，INCREASE在三个数据集的四个评价指标上都取得了最好的结果。值得注意的是，同样作为归纳式时空克里金插值模型的IGNNK，虽然性能在大多数情况下优于其他baseline方法，但由于没有充分考虑多重异质关系以及缺乏对未知节点时间相关性的有效建模，因此性能弱于本文的INCREASE。总体而言，INCREASE模型借助上述三个模块可以有效利用已知节点的信息，学习得到表达能力更强的未知节点表示，并显著提高时空克里金插值的性能。

实验结果2.不同已知节点数量情况下的性能对比

在实际应用中，由于高昂的维护成本等原因，传感器的数量通常极为有限。为了评估模型在不同传感器数量情况下的估计性能，在保持未知节点数量不变的前提下丢弃部分已知节点进行实验。所有模型都保持相同数量的已知节点与未知节点。如图 4所示，在已知节点丢弃比例增大的同时，所有模型性能都有所下降，但INCREASE依然性能最优，且在丢弃比例极大时，其他模型与INCREASE模型的性能差异更为明显。

图 4：不同已知节点数量情况下的性能对比

实验结果3. 基于模型参数的函数相似性建立3DG的有效性

本文还针对INCREASE的三个模块进行了消融实验，分别对多重异质关系、差异性建模、关系感知GRU神经网络和多注意力机制的有效性进行了实验验证，结果表明了INCREASE各个模块在解决时空克里金插值时的有效性，表2展示了差异性建模有效性的实验结果，其他实验结果请见论文。

表 2：差异性建模的有效性（RMSE）

实验结果4. 超参设置的影响

本文讨论了三个超参数设置对模型性能的影响，包括邻居节点数量、时间步数量和隐藏状态维度。图 5展示了部分实验结果，完整结果请见原文。

图 5：超参数实验的部分实验结果

五、总结与展望

本文面向时空图数据的归纳式表示学习，以时空克里金插值为应用场景，针对多重异质关系难以挖掘的问题，提出了归纳式图表示学习的时空克里金插值方法（简称INCREASE）。该模型可以根据已知节点的数据计算一组未知节点数据的估计值。我们在三个真实世界的时空数据集上进行了广泛实验。结果表明，INCREASE优于现有所有baseline方法，且当可用的观测位置较少时、模型性能的提高更加显著。在未来的工作中，我们计划将更复杂的异质关系（例如，不同地点之间的社交关系互动）纳入模型，以进一步提高其性能。

INCREASE: Inductive Graph Representation Learning for Spatio-Temporal Kriging（WWW-23）

论文链接：https://arxiv.org/abs/2302.02738.pdf

代码链接：https://github.com/zhengchuanpan/INCREASE

联系作者：范晓亮（fanxiaoliang@xmu.edu.cn）、郑传潘（zhengchuanpan@stu.xmu.edu.cn）、王程（cwang@xmu.edu.cn）