Averaging of Decomposable Graphs by Dynamic Programming and Sampling

Kustaa Kangas, Teppo Mikael Niinimäki, Mikko KoivistoUAI 2015 · OpenReview

Abstract

Bayesian learning for decomposable graphical models has traditionally been limited to finding a single "best" graph or using Markov Chain Monte Carlo (MCMC) approximations with uncertain convergence. This paper introduces a breakthrough by enabling exact averaging and efficient sampling through dynamic programming (DP) and fast set-function transforms. By leveraging the structure of Rooted Junction Trees (RPTs), the authors achieve an asymptotically faster exact averaging algorithm ($O(n^3 3^n)$) and a flexible sampling scheme that scales to graphs with up to 20 nodes, significantly extending the reach of exact Bayesian methods.

Introduction

In probabilistic graphical models, decomposable graphs (chordal or triangulated graphs) are highly valued for their efficiency in parameter learning and inference. However, learning the structure of these graphs from data is a significant challenge. Most current approaches either optimize for a single Maximum A Posteriori (MAP) graph—which risks overfitting—or use MCMC to sample the posterior. MCMC, while popular, lacks guarantees on convergence time and estimation accuracy.

The ideal solution is Bayesian model averaging, which accounts for uncertainty by considering all possible graphs weighted by their posterior probability. Previously, exact averaging was restricted to very small graphs (approximately 8 nodes) due to the super-exponential growth of the graph space. This work bridges that gap, providing a scalable framework for exact inference.

Methods

The authors extend a 2014 dynamic programming approach for finding optimal graphs into a robust framework for summation and sampling. Their methodology consists of three primary innovations:

  1. Summation via Rooted Junction Trees: The DP recursions are adapted to compute the sum of posterior probabilities over all possible graphs. By representing graphs as Rooted Junction Trees (RPTs), the authors create a recursive structure suitable for DP.
  2. Algorithmic Optimization: By applying the Fast Zeta Transform (FZT) and Fast Subset Convolution (FSC), the complexity of the averaging task is reduced from $O(4^n)$ to $O(n^3 3^n)$. This improvement is critical for scaling to $n=20$ nodes.
  3. Advanced Sampling and Importance Correction: A backtracking algorithm allows for independent posterior sampling. To manage memory, the authors use a time-space tradeoff with the "alias method" and adaptive sampling. Because the DP sums over RPTs rather than unique graphs, importance sampling is used to correct the distribution, ensuring a standard uniform prior over graphs.

Experimental Setup

The method was evaluated on four classic benchmark datasets, ranging from 8 to 17 nodes. These datasets represent varying levels of complexity and record counts, providing a comprehensive test for the algorithm's scalability and accuracy.

Table 2: Characteristics of the benchmark datasets, including node count (n) and record count (m).

Key Results

The experimental results highlight the efficiency and reliability of the proposed DP and sampling approach. The algorithm successfully handled the House-votes dataset (17 nodes), a task impossible for previous brute-force methods.

Table 1: Running times (in seconds) for the DP phase and subsequent sampling of 10^5, 10^6, and 10^7 graphs.

As shown in the performance data, the DP phase for 17 nodes takes approximately 2 hours. However, once this pre-computation is complete, the algorithm can generate 10 million independent samples in just 167 seconds. In terms of accuracy, sampling-based estimates for the Asia dataset converged to ground-truth edge probabilities with a maximum error of less than 0.01 after $10^5$ samples. Unlike MCMC, the error rates remained steady and predictable across datasets, confirming the method's reliability.

Conclusion

This work demonstrates that Bayesian model averaging is not only more robust than simple optimization but also computationally feasible for moderately sized graphs. By framing graphical model recursions as subset convolutions, the authors have unlocked the ability to perform exact inference on graphs with up to 20 nodes.

Future work may address the "20-node ceiling" by introducing clique size constraints to reduce memory requirements or exploring "optimal Monte Carlo" algorithms to further refine importance sampling variance. Despite current exponential limits, this approach sets a new standard for exact Bayesian structure learning.

Summary updated

BibTeX
@inproceedings{kangas2015averaging,
  author = {Kustaa Kangas and Teppo Mikael Niinimäki and Mikko Koivisto},
  title = {{Averaging of Decomposable Graphs by Dynamic Programming and Sampling}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=sUnr37ip1D},
}
Figure