  Many network analysis and graph learning techniques are based on models of
random walks which require to infer transition matrices that formalize the
underlying stochastic process in an observed graph. For weighted graphs, it is
common to estimate the entries of such transition matrices based on the
relative weights of edges. However, we are often confronted with incomplete
data, which turns the construction of the transition matrix based on a weighted
graph into an inference problem. Moreover, we often have access to additional
information, which capture topological constraints of the system, i.e. which
edges in a weighted graph are (theoretically) possible and which are not, e.g.
transportation networks, where we have access to passenger trajectories as well
as the physical topology of connections, or a set of social interactions with
the underlying social structure. Combining these two different sources of
information to infer transition matrices is an open challenge, with
implications on the downstream network analysis tasks.
  Addressing this issue, we show that including knowledge on such topological
constraints can improve the inference of transition matrices, especially for
small datasets. We derive an analytically tractable Bayesian method that uses
repeated interactions and a topological prior to infer transition matrices
data-efficiently. We compare it against commonly used frequentist and Bayesian
approaches both in synthetic and real-world datasets, and we find that it
recovers the transition probabilities with higher accuracy and that it is
robust even in cases when the knowledge of the topological constraint is
partial. Lastly, we show that this higher accuracy improves the results for
downstream network analysis tasks like cluster detection and node ranking,
which highlights the practical relevance of our method for analyses of various
networked systems.
