  We study the problem of learning the Markov order in categorical sequences
that represent paths in a network, i.e. sequences of variable lengths where
transitions between states are constrained to a known graph. Such data pose
challenges for standard Markov order detection methods and demand modelling
techniques that explicitly account for the graph constraint. Adopting a
multi-order modelling framework for paths, we develop a Bayesian learning
technique that (i) more reliably detects the correct Markov order compared to a
competing method based on the likelihood ratio test, (ii) requires considerably
less data compared to methods using AIC or BIC, and (iii) is robust against
partial knowledge of the underlying constraints. We further show that a
recently published method that uses a likelihood ratio test has a tendency to
overfit the true Markov order of paths, which is not the case for our Bayesian
technique. Our method is important for data scientists analyzing patterns in
categorical sequence data that are subject to (partially) known constraints,
e.g. sequences with forbidden words, mobility trajectories and click stream
data, or sequence data in bioinformatics. Addressing the key challenge of model
selection, our work is further relevant for the growing body of research that
emphasizes the need for higher-order models in network analysis.
