Decomposition of graphical models (ANR-16-CE40-0028)

Solving NP-hard problems is still a challenge at the theoretical or practical level. This project aims at solving decision, optimization and counting (discrete integration) problems defined as “graphical models” (constraint or cost function networks, bayesian networks, propositional logic and Markov random fields). In such models, a joint function over a set of variables is described as a factorized combination of functions of few variables. This approach is intensively used in artificial intelligence, statistical physics and statistical modeling and the name of “graphical model” underlines the fact that such a factorisation defines an (hyper)graph which vertices are the variables and which (hyper)edges include the variables in each factor. The expressiveness of these models makes them capable of representing a large variety of real problems (in image processing, ressource allocation, bioinformatics,…). However, solving such problems is difficult in terms of theoretical complexity: NP-complete for decision, NP-hard for optimization and #P-complete for counting. This project is more specifically interested in the exploitation of (hyper)graph decomposition techniques applied to the underlying graphs defined by graphical models. Their wide practical interest has been only demonstrated in the last ten years (mostly through the notion of tree decomposition), while also highlighting their limits, but they have great potential of improvement.

Indeed, the community of graph theory has independently produced, in the mean time, a large number of results. Most have however been kept as objects of theoretical studies (branch-clique-rank-boolean-matching-modular-treecut-treedepth decompositions just to name a few). Actually, theoretical results on these decompositions have not yet been exploited to improve graphical model processing algorithms or, a fortiori, effective operational processing systems. This is not surprising because most of these results have been studied for theoretical reasons, without the objective of solving graphical models in practice. This type of situation is not unusual, the notion of tree-decomposition has been introduced and studied by Roberston and Seymour as a theoretical tool to prove the famous Wagner’s conjecture about graph minors. However, this mathematical object is now a fundamental tool for solving methods which take into account the structure of graphical models.

On this basis, a wide field of study is open today around graph decomposition that would combine theory, algorithmic results on graphical models and practical solving tools. The objectives of the project therefore combine these three main axes:

(1) On the theoretical side, the aim is to study existing decompositions or define new decomposition approaches more specifically targeted at effective processing of problems defined on graphical models by also exploiting what has been learnt using tree decompositions.

(2) About processing algorithms, the aim is to effectively exploit the various graph decomposition techniques that have been developped by the mathematical community. This leads to the development of new algorithms and new heuristics.

(3) On a practical level, the aim is to push the computational frontiers of decomposition approaches to efficiently process problems of increasing hardness and size. This will be possible by extending the graphical model processing platform “toulbar2” and transfering these results towards already identified applied fields and other approaches to combinatorial optimization.

Globally, by aiming at the design of new theoretical and algorithmical results targeted to real problems expressed as queries on graphical models together with actual implementation of processing tools that will be applied to challenging real world problems, and given the large existing gap between theory and practice in the field, this project has the capacity to have a strong impact, both on the theoretical and practical side.

Dates: 2017-2022

Partners: LIS (CNRS, Université Aix-Marseille), LIRMM (CNRS, Université Montpellier), MIAT (INRAE Toulouse)