Tractability in Structured Probability Spaces
Recently, the Probabilistic Sentential Decision Diagram (PSDD) has been proposed as a framework for systematically inducing and learning distributions over structured objects, including combinatorial objects such as permutations and rankings, paths and matchings on a graph, etc. In this paper, we study the scalability of such models in the context of representing and learning distributions over routes on a map. In particular, we introduce the notion of a hierarchical route distribution and show how they can be leveraged to construct tractable PSDDs over route distributions, allowing them to scale to larger maps. We illustrate the utility of our model empirically, in a route prediction task, showing how accuracy can be increased significantly compared to Markov models.
This paper looks at the problem of representing simple routes on a graph as a probability distribution using Probabilistic Sentential Decision Diagrams (PSDDs). Representing a complex structure such as a graph is difficult, and the authors transform the problem by turning a graph into a Boolean circuit where it is straightforward to perform inference, and as an experiment, use their method on a route prediction method for San Francisco taxi cabs, where it beats two baselines. 
PSDDs refer to a framework that represents probability distributions over structured objects through Boolean circuits. Once the object is depicted as a Boolean circuit, it becomes straightforward to parameterize it. More formally, PSDD’s are parameterized by including a distribution over each or-gate, and PSDD’s can represent any distribution (and under some conditions, this distribution is unique). The authors focus on the specific problem of learning distributions over simple routes — those that are connected and without cycles. The advantage of SDD circuits is that they have been shown to work on graphs that would be computationally expensive to model with Bayesian nets. With large maps, tractability is still a problem with PSDDs, and the authors do this by considering hierarchical approximations; they break up the map into hierarchies so that representing distributions is polynomial when constraining the size of each region to be a certain size. 
The paper is well-written, and the authors define PSDD's clearly and succinctly. 
To me, the results of the paper seems incremental -- the authors apply an existing representation method to graphs, and after some approximations, apply the existing inference techniques. Additionally, the paper spends a couple of pages listing theorems, which appear to be basic algorithmic results. 
Additionally, I'm not convinced by the baselines chosen for the experiment. For a task of predicting edges given a set of previous edges, the baselines are a naive model which only looks at frequencies and a Markov model that only considers the last edge used. I imagine a deep learning approach or even a simple probabilistic diagram could've yielded more interesting and comparable results. Even if these would require more time to train, it would be valuable to compare model complexity in addition to accuracy. I would need to see more experiments to be convinced by the approach.