This work is focused on learning maximum weighted graphs subject to three structural constraints: (1) the graph is decomposable, (2) it has a maximum clique size of k +1 , and (3) it is coarser than ag iven maximumk-order decomposable graph. After proving that the problem is NP-hard we give a formulation of the problem based on integer linear programming. The approach has shown competitive experimental results in artificial domains. The proposed formulation has important applications in the field of probabilistic graphical models, such as learning decomposable models based on decomposable scores (e.g. log-likelihood, BDe, MDL, just to name a few). The learning of probabilistic graphical models can be divided into two parts, the structural learning and the parametric learning (4). Usually, the structural learn- ing consists of obtaining a graph that maximizes a score function. This problem can be viewed from the more general perspective of Graph Theory (1) through the maximum weighted graph problems. Maximum weighted graph problems consist of learning a graph by maximizing a weight function associated to the constructed structure. Most of these problems restrict the space of solutions by imposing a set of structural constraints. Additionally, in some problems, the weight functions can be additively decomposed in terms of the structural compo- nents of the graph, e.g. the edges or the complete sets of vertices. The structural constraints and the decomposability of the weight function allow the design of efficient algorithms to deal with maximum weighted graph problems. An illustrative example of this kind of problems is the maximum weighted tree problem. The solutions to this problem are constrained to the set of graphs with tree structure. In this problem the weight function is additively decomposable in terms of the edges included in the solution. This problem can be solved using learning algorithms with a polynomial computational complexity in the number
['Aritz Pérez', 'Christian Blum', 'José Antonio Lozano']
Learning Maximum Weighted (k+1)-Order Decomposable Graphs by Integer Linear Programming