  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.
