Approximating the maximum weighted decomposable graph problem with applications to probabilistic graphical models

Aritz Pérez, Christian Blum, José Antonio LozanoPGM 2018 · OpenReview

TL;DR

This paper tackles the NP-hard problem of learning maximum weighted decomposable graphs, crucial for building probabilistic graphical models. They introduce an approximate Integer Linear Programming (ILP) formulation that significantly speeds up computation by intelligently pruning candidate edges based on a distance threshold, achieving near-optimal results with limited resources.

What Problem Does This Paper Address?

Learning probabilistic graphical models (PGMs) often involves two steps: structural learning (finding the graph's topology) and parametric learning (estimating model parameters). Structural learning can be computationally intensive, especially when searching for optimal graph structures. One common approach is to restrict the search space to "decomposable graphs," which have desirable properties for learning.

The specific problem here is learning a maximum weighted $(k+1)$-order decomposable graph (k+1DG) that is "coarser" than a given maximal $k$-order decomposable graph (MkDG). Think of it as finding a more complex decomposable graph structure that is still "compatible" with a simpler, pre-defined structure. This problem is known to be NP-hard, meaning exact solutions become computationally infeasible for larger problems. While an exact Integer Linear Programming (ILP) formulation exists, its scalability is limited by a cubic growth in variables and constraints with the number of vertices. This paper aims to develop a more efficient, approximate ILP formulation that can handle larger instances and limited computational budgets.

Methods

The core contribution is an approximate Integer Linear Programming (ILP) formulation (AF) for the maximum weighted $(k+1)$DG problem. This AF builds upon an existing exact ILP formulation (EF) but introduces a crucial heuristic: a threshold distance ($l_{max}$).

Here's how it works:

  • Edges of Interest (EOIs): The problem is framed in terms of adding "edges of interest" (EOIs) to the existing MkDG. These EOIs are candidate edges that, when added, create cliques of a specific size ($k+1$).
  • Distance Criterion: The paper defines a "distance" between vertices based on the number of separators in the graph. The AF prioritizes EOIs whose vertices have a distance less than or equal to a chosen threshold, $l_{max}$.
  • Pruning: By setting $l_{max}$, the AF effectively discards EOIs that are "far apart" in the graph. The intuition is that these distant edges are less likely to be part of the optimal solution on average, especially for random weight functions.
  • Reduced ILP: This pruning significantly reduces the number of decision variables and constraints in the ILP formulation, making it much more scalable. The AF modifies the EF by only considering EOIs that satisfy the distance threshold.

Datasets

Not discussed in the paper. The paper describes generating synthetic instances for evaluation.

Key Insights and Ideas

  • Distance as a Heuristic: The paper demonstrates that a simple distance-based heuristic can be surprisingly effective for pruning the search space in a complex combinatorial optimization problem. This suggests that structural properties like vertex distance can be strong indicators of edge inclusion in optimal solutions.
  • Scalability vs. Optimality Trade-off: The AF offers a practical trade-off: sacrificing guaranteed optimality for a dramatic improvement in computational efficiency. This is crucial for real-world applications where exact solutions are out of reach.
  • The Power of Approximation: The success of the AF, even with a small $l_{max}$, highlights the value of approximate algorithms when dealing with NP-hard problems. The results show that "good enough" solutions can be found much faster.
  • Controlling Complexity: The $l_{max}$ parameter provides a direct knob to control the trade-off between solution quality and computational cost, allowing users to tailor the approach to their specific resource constraints.

Key Results

  • The approximate ILP formulation (AF) achieved results very close to the optimum obtained by the exact ILP formulation (EF), even for larger instances.
  • The AF significantly reduced computation time, often by orders of magnitude, compared to the EF. For example, for $n=80$, the AF with $l_{max}=4$ achieved a solution close to $l_{max}=8$ in a fraction of the time.
  • The AF outperformed a greedy approach in terms of solution quality across various instance sizes and problem types (maximum weighted graph and Bayesian Dirichlet equivalent uniform score for PGMs).
  • The number of decision variables and constraints in the AF grew much more manageably with the number of vertices ($n$) compared to the EF, which suffered from cubic growth.

Limitations and Future Work

  • Guaranteed Optimality: The AF is an approximation and does not guarantee finding the globally optimal solution. The quality of the solution depends on the chosen $l_{max}$ value.
  • Parameter Tuning: The choice of $l_{max}$ is crucial and might require some tuning. The paper suggests setting $l_{max}$ to yield thousands of decision variables for a good trade-off.
  • Future Work:
    • Develop strategies to further reduce the number of candidate edges by considering the specific weights of a given instance.
  • Design efficient algorithms for the more general maximum weighted $k$-order decomposable graph problem (as defined by Srebro).
  • Explore divide-and-conquer strategies for learning decomposable models with bounded maximum clique sizes.

Summary updated

Abstract

In this work we deal with the problem of learning a maximum weighted $(k + 1)$-order decomposable graph coarser than a given maximal $k$-order decomposable graph (also known as hypertree of tree-width $k-1$). An Integer Linear Programming formulation for the problem has recently been proposed and used in order to solve instances of the problem with a moderate number of vertices. However, as the problem is known to be NP-hard, it is of practical interest to develop approximate algorithms able to work with a limited amount of computational resources. In this paper we propose an approximate Integer Linear Programming formulation for the problem using a threshold distance which discards the edges that, on average, have a low probability of being contained in the solution. Experiments have been carried out with weighted graphs and probabilistic graphical models. Using the proposed formulation we have obtained results close to the optimum, even when most of the candidate edges were discarded using the distance criterion. The obtained good results indicate that the approximate formulation has important applications for learning probabilistic graphical models using decomposable scores, e.g., BDe.
BibTeX
@inproceedings{perez2018approximating,
  author = {Aritz Pérez and Christian Blum and José Antonio Lozano},
  title = {{Approximating the maximum weighted decomposable graph problem with applications to probabilistic graphical models}},
  booktitle = {PGM},
  year = {2018},
  url = {https://openreview.net/forum?id=fWDYbFynUw},
}
Figure