Rule-Guided Graph Synthesis: Integrating First-Order Logic into Deep Generative Models

Existing graph generative models produce graphs that are often quite realistic, but sometimes miss domain-specific patterns. Enhancing graph learning with domain knowledge is one of the current frontiers for neural models of graph data. In this paper, we propose a new approach to enhancing deep graph generative models with knowledge that is represented by first-order logic rules. First-order logic provides an expressive formalism for representing interpretable causal knowledge about relational structures. Our conceptual contribution is a new first-order semantic loss function for training a graph generative model on relational data: maximize the model likelihood subject to a rule moment matching constraint, namely that the expected instance count of each rule matches its observed instance count. Our algorithmic contribution is a novel matrix-multiplication-based method for computing the expected instance count of a first-order rule for a Graph Variational Autoencoder model. Empirical evaluation across benchmark datasets shows that rule moment matching substantially improves the quality of generated graphs across multiple graph quality metrics.