gs 【WSDM2021】Time-Series Event Prediction with Evolutionary State Graph

关键词：时间序列预测，进化状态图，图网络

摘要

为了对时序数据中未来事件做到精确且可解释的预测，需要捕获具有代表性的模式(state)。以前的研究都主要关注对模式的表示和识别，忽视了变化中的过渡关系。

本文使用一种演化状态图，节点表示模式，边表示演化关系。

提出了Evolutionary State Graph Network(EvoNet)，对进化状态图进行编码，以便准确和可解释的时间序列事件预测，EvoNet对节点与节点和图级别传播（segment 2 segment）进行建模，同时捕获节点与图随时间交互的信息。

基于5个真实世界数据集的实验结果表明，与11个基线相比，我们的方法不仅取得了明显的改进，而且为解释事件预测的结果提供了更多的见解。

介绍

时间序列数据中未来事件(如异常)的预测一直是时间数据挖掘的重要任务。

贡献

通过对实际数据的分析，我们发现状态间的时变关系对于时间序列事件的预测很重要
我们提出了演化状态图来捕捉状态之间的动态关系，并基于进演化状态图开发EvoNet来提高事件预测的性能
我们在5个数据集上进行了大量的实验，以证明我们的方法可以做出更准确的预测，并为解释它们提供更多的见解

背景及问题定义

时间序列事件预测

$\tau$：滑窗大小（表示某种物理意义，比如24h）

$d$：dimension

状态 State

状态集合（典型模式片段集合）：$\Theta _v\in R^{\tau \times d}$

提取方式：Symbolic Aggregate Approximation, Bag of Patterns, Shapelets, sequence clustering

Segment-to-state representation

`EvoNet`框架

Evolutionary State Graph 演化状态图

图结构：$G{(t)} = {V, E^{(t)}, M^{(t)}}$表示从$X{t-1}$到$X_{t }$的状态

异常时刻时图会更加稠密
异常时节点对应的的in-degree会增加

Evolutionary State Graph Network 演化状态图网络

网络利用状态演化图来捕获一下两种信息：

局部结构影响：状态与状态之间局部变化的影响（例子：跑步）

时间影响：先前状态的转换将影响当前观测数据

例如，(高强度跑步→慢跑)→···→停止运动)和(慢跑→慢跑→···→停止运动)会产生不同的健身效果。

在演化状态中的表现：

局部结构影响->图中的每个节点之间的局部成对关系 ——>local information aggregation
时间影响->不同图上的演化 ——>temporal graph propagation

Local information aggregation

Temporal graph propagation

End-to-End Model Learning 端到端的模型学习

训练一个分类器（NN or XGBoost）

where Yˆ𝑡+1 ∈ {0, 1} is the ground truth that indicating whether a future event will occur.

实验

数据集

DJIA 30 Stock Time Series (DJIA30) ：三种交易价格和一个交易数字；目标是基于最近50周的数据预测下一周是否有异常的价格波动
Web Traffic Time Series Forecasting (WebTraffic) ：目标是根据12月的数据预测未来一个月是否出现快速增长
Information Networks Supervision (NetFlow) ：由中国电信提供。小时粒度；流入与流出（两维）；15天预测两天；
Watt-hour Meter Clock Error (ClockErr) ：由中国国家电网提供。每个读数记录电能表的偏差时间和延迟时间；当偏差时间超过120时，表示仪表异常；我们的目标是根据过去12个月的记录预测下个月的异常情况；
Abnormal Server Response (AbServe) :本数据集由阿里巴巴云提供。每个系列记录不同指标的详细读数(例如:CPU、磁盘、内存等)。当服务器无法响应时，日志将记录异常。我们的目标是根据前一小时的记录预测未来五分钟内的异常情况。

BaseLine

基于特征的模型

Bag of Patterns (BoP), Vector Space Model using SAX (SAX-VSM) and Fast Shapelet (FS)

这些方法捕获不同的状态表示，这些状态表示作为事件预测的特征
序列模型
- switching-time-series model (S-HMM) ：建模状态序列的马尔可夫依赖
- multiscale recurrent neural network (MRNN) ：以$X_t \oplus Y_t$作为输入，学习隐空间表示来做预测
- hierarchical recurrent neural network (HRNN) ：学习更多$X_t $和$ Y_t$的相关性
基于图的模型
- gated graph neural network (GGNN) ：使用one-hot对$h_0$进行初始化，局部信息传递使用GGNN，节点级传播是用GRU
- GCN-LSTM ：使用$\Theta$对$h_0$进行初始化，局部信息传递使用GCN，节点级传播是用LSTM
- EvolveGCN ：将RNN和GCN结合起来的多层动态图神经网络，关注的节点级的传播
- ST-MGCN ：时空多图卷积网络，使用$ Y_t$作为传播的上下文信息，它直接将上下文信息融合到节点级表示中，而不是学习图级表示并对节点-图交互进行建模
- Time2Graph ：将不同时间的图形聚合成静态图，并进行DeepWalk来学习图形的表示，然后作为事件预测的特征
EvoNet变体

EvoNet w/o G：不使用演化状态图，使用状态序列直接建模（LSTM）

EvoNet w/o A：不使用时间注意力机制

Q1: How does EvoNet perform on the time-series prediction task, compared with other baselines from the state-of-the-art?

Q2: How does the proposed EvoBlock effectively bridge the graph-level and node-level information over time?

Q3: How do different configurations, e.g., state number, segmentation length, implementation of state recognition and message passing, influence the performance?

Case Study

总结

本文研究状态之间的关系如何反映时间数据的演化问题。我们提出了一种新的表示方法——演化状态图，来表示时间序列状态之间的时变关系。为了捕获这些有效的模式用于下游任务，我们进一步提出了基于GNN的EvoNet模型来进行动态图建模。为了验证EvoNet的有效性，我们在五个真实世界的数据集上进行了大量的实验。实验结果表明，我们的模型明显优于11种最先进的基准测试方法。在此基础上，我们可以发现状态之间的一些有意义的关系，使我们能够理解时间数据。

时序论文分享

gs 【WSDM2021】Time-Series Event Prediction with Evolutionary State Graph

摘要