Inferring Graphs from Walks
Abstract
Abstract We consider the problem of inferring an undirected, degree-bounded, edge-colored graph from the sequence of edge colors seen in a walk of that graph. This problem can be viewed as reconstructing the structure of a Markov chain from its output. (That is, we are not concerned with inferring the transition probabilities, but only the underlying graph structure of the Markov chain.) We present polynomial-time algorithms for the inference of underlying graphs of degree-bound 2 (linear chains and cycles), based on some surprising properties about the confluence of various sets of rewrite rules.
Cite
Text
Aslam and Rivest. "Inferring Graphs from Walks." Annual Conference on Computational Learning Theory, 1990. doi:10.1016/B978-1-55860-146-8.50031-XMarkdown
[Aslam and Rivest. "Inferring Graphs from Walks." Annual Conference on Computational Learning Theory, 1990.](https://mlanthology.org/colt/1990/aslam1990colt-inferring/) doi:10.1016/B978-1-55860-146-8.50031-XBibTeX
@inproceedings{aslam1990colt-inferring,
title = {{Inferring Graphs from Walks}},
author = {Aslam, Javed A. and Rivest, Ronald L.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1990},
pages = {359-370},
doi = {10.1016/B978-1-55860-146-8.50031-X},
url = {https://mlanthology.org/colt/1990/aslam1990colt-inferring/}
}