Piecewise Stationary Modeling of Random Processes Over Graphs With an Application to Traffic Prediction
Piecewise Stationary Modeling of Random Processes Over Graphs With an Application to Traffic Prediction
复制标题
DOI：
10.1109/bigdata47090.2019.9005965
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Arman Hasanzadeh;Xi Liu;N. Duffield;K. Narayanan
中科院分区：
文献类型：
--
作者：
Arman Hasanzadeh;Xi Liu;N. Duffield;K. Narayanan
平稳性是许多随机过程统计模型的一个关键假设。随着图信号处理领域的最新发展，广义平稳的传统概念已经扩展到定义在图顶点上的随机过程。已经证明，众所周知的谱图核方法假设图上的底层随机过程是平稳的。虽然在机器学习和信号处理文献中已经提出了许多方法来对图上的平稳随机过程进行建模，但它们对于表征现实世界的数据集来说过于严格，因为它们中的大多数都是非平稳过程。在本文中，为了很好地表征图上的非平稳过程，我们提出了一种新的模型和一种计算效率高的算法，该算法将一个大的图划分为不相交的簇，使得过程在每个簇上是平稳的，但在簇之间是独立的。我们在达拉斯-沃斯堡地区的细粒度高速公路旅行时间的大规模数据集上评估了我们的交通预测模型。我们的方法的准确性非常接近最先进的基于图的深度学习方法，而我们模型的计算复杂性要小得多。
Stationarity is a key assumption in many statistical models for random processes. With recent developments in the field of graph signal processing, the conventional notion of wide-sense stationarity has been extended to random processes defined on the vertices of graphs. It has been shown that well-known spectral graph kernel methods assume that the underlying random process over a graph is stationary. While many approaches have been proposed, both in machine learning and signal processing literature, to model stationary random processes over graphs, they are too restrictive to characterize real-world datasets as most of them are non-stationary processes. In this paper, to well-characterize a non-stationary process over graph, we propose a novel model and a computationally efficient algorithm that partitions a large graph into disjoint clusters such that the process is stationary on each of the clusters but independent across clusters. We evaluate our model for traffic prediction on a large-scale dataset of fine-grained highway travel times in the Dallas-Fort Worth area. The accuracy of our method is very close to the state-of-the-art graph based deep learning methods while the computational complexity of our model is substantially smaller.