Partition Function Estimation: A Quantitative Study
  Probabilistic graphical models have emerged as a powerful modeling tool for
several real-world scenarios where one needs to reason under uncertainty. A
graphical model's partition function is a central quantity of interest, and its
computation is key to several probabilistic reasoning tasks. Given the
#P-hardness of computing the partition function, several techniques have been
proposed over the years with varying guarantees on the quality of estimates and
their runtime behavior. This paper seeks to present a survey of 18 techniques
and a rigorous empirical study of their behavior across an extensive set of
benchmarks. Our empirical study draws up a surprising observation: exact
techniques are as efficient as the approximate ones, and therefore, we conclude
with an optimistic view of opportunities for the design of approximate
techniques with enhanced scalability. Motivated by the observation of an order
of magnitude difference between the Virtual Best Solver and the best performing
tool, we envision an exciting line of research focused on the development of
portfolio solvers.
