Fast Relational Probabilistic Inference and Learning: Approximate Counting via Hypergraphs

  • Mayukh Das The University of Texas at Dallas
  • Devendra Singh Dhami The University of Texas at Dallas
  • Gautam Kunapuli The University of Texas at Dallas
  • Kristian Kersting Technische Universität Darmstadt
  • Sriraam Natarajan The University of Texas at Dallas


Counting the number of true instances of a clause is arguably a major bottleneck in relational probabilistic inference and learning. We approximate counts in two steps: (1) transform the fully grounded relational model to a large hypergraph, and partially-instantiated clauses to hypergraph motifs; (2) since the expected counts of the motifs are provably the clause counts, approximate them using summary statistics (in/outdegrees, edge counts, etc). Our experimental results demonstrate the efficiency of these approximations, which can be applied to many complex statistical relational models, and can be significantly faster than state-of-the-art, both for inference and learning, without sacrificing effectiveness.

AAAI Technical Track: Reasoning under Uncertainty