Recursion Graphs: Consistent Inference for Cyclic Noisy-Logical Graphs

Directed, cyclic graphs occur in many applications of graphical models where feedback loops are not desired. For instance, consider a relational resource that potentially contains meaningful directed cycles, such as a knowledge base or social network. We may wish to convert such a resource into probabilistic graphical model. Many existing methods for performing such a conversion either lose potentially important information, or are not guaranteed to have a consistent joint distribution. Other solutions are not tractable for some applications. This paper introduces a new semantics, recursion graphs, that do not lose information, and have a consistent joint distribution, while they are tractable in more situations. In these graphs, nodes keep track of their “reasons,” so that no node can be an indirect reason for itself. In addition to the main consistency result, some preliminary empirical results are shown. In these experiments, recursion graphs significantly outperform alternatives.