  We propose a novel sequence prediction method for sequential data capturing
node traversals in graphs. Our method builds on a statistical modelling
framework that combines multiple higher-order network models into a single
multi-order model. We develop a technique to fit such multi-order models in
empirical sequential data and to select the optimal maximum order. Our
framework facilitates both next-element and full sequence prediction given a
sequence-prefix of any length. We evaluate our model based on six empirical
data sets containing sequences from website navigation as well as public
transport systems. The results show that our method out-performs
state-of-the-art algorithms for next-element prediction. We further demonstrate
the accuracy of our method during out-of-sample sequence prediction and
validate that our method can scale to data sets with millions of sequences.
