# Bayesian Inference of Transition Matrices from Incomplete Graph Data with a Topological Prior

arXiv: https://arxiv.org/abs/2210.15410 · HTML: https://mlsanity.com/paper/2210.15410/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 47 references that are in the map.
- First posted on arXiv 27 Oct 2022.

## Builds on (most cited first, 13 of 13)

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Bayesian graph convolutional neural networks for semi-supervised classification](https://mlsanity.com/paper/1811.11103/) (2018)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Random walks and diffusion on networks](https://mlsanity.com/paper/1612.03281/) (2016)
- [Network structure from rich but noisy data](https://mlsanity.com/paper/1703.07376/) (2017)
- [Network reconstruction and community detection from dynamics](https://mlsanity.com/paper/1903.10833/) (2019)
- [Reconstructing networks with unknown and heterogeneous errors](https://mlsanity.com/paper/1806.07956/) (2018)
- [Modeling sequences and temporal networks with dynamic community structures](https://mlsanity.com/paper/1509.04740/) (2015)
- [From Relational Data to Graphs: Inferring Significant Links using Generalized Hypergeometric Ensembles](https://mlsanity.com/paper/1706.04370/) (2017)

## Abstract (arXiv)

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.