Tighter continuous relaxations for map inference in discrete mrfs: A survey Hariprasad Kannan, Team DataShape, Inria Saclay, Palaiseau, Nikos Komodakis, Ecole des Ponts, Champs-sur-Marne, Nikos Paragios, CentraleSupelec, Gif-sur-Yvette

Abstract: Continuous relaxations are central to map inference in discrete Markov random fields (mrfs). In these methods, the intractable discrete optimization problem is approximated by a continuous relaxation. The relaxation could be based on different approaches, with the linear programming (lp) relaxation being the most well studied. For continuous relaxations, the important considerations are efficiently solving the optimization formulations and improving the approximation quality of the relaxations. In this chapter, we focus on the latter topic, which is referred to as tighter continuous relaxations. We present a comprehensive survey of techniques to achieve a tighter lp relaxation, followed by a discussion of semidefinite programming (sdp) relaxation techniques. We discuss these topics by covering both theoretical motivations and algorithmic considerations. We hope this will be a ready reference for researchers working on tighter relaxations and for practitioners who want to model their problem more accurately and efficiently. The foundation for the theoretical aspects comes from the discrete optimization community through the topics of polyhedral combinatorics and relaxation hierarchies. The structure of discrete mrfs lends a special perspective to these classic topics and we will see how several works have explored this path. Over the years, research efforts in discrete mrfs have characterized graph topologies and/or clique energies that lead to accurate map inference. In recent years, there have been similar efforts, to better understand the settings and their accompanying guarantees, for the algorithms that tighten the continuous relaxations. We will end this chapter by giving a taste for this emerging research topic.

Probabilistic graphical models describe a set of random variables in a compact manner by exploiting the structured nature of their interaction [START_REF] Koller | Probabilistic graphical models: principles and techniques[END_REF], [START_REF] Wainwright | Graphical models, exponential families, and variational inference[END_REF]. In this chapter, we focus on undirected graphical models, which are referred to as Markov random fields (mrfs) [START_REF] Blake | Markov random fields for vision and image processing[END_REF]. We have a graph G = (V, C), where V denotes the set of nodes, which are the random variables and C denotes the set of cliques, which represent the interactions. In this chapter, the random variables take discrete values or labels. A clique composed of two nodes is also called an edge. A clique with more than two nodes is called a hyperedge or a higher-order clique. We will refer to cliques, edges and hyperedges interchangeably, where the meaning will be clear based on the context. An important computation that we seek is finding the labelling of all the random variables, which will maximize the joint probability distribution,

P (X = x) = i∈V Ψ i (x i ) c∈C Ψ c (x c ) = exp - i∈V θ i (x i ) - c∈C θ c (x c ) .
(1)

Here, X denotes the complete set of n discrete variables X 1 , ..., X n . The set of variables corresponding to a clique c is indicated by X c . Without loss of generality, we assume that all variables take labels from a common set of size l. A particular realization (labelling) of X i is denoted by x i . Thus, the labelling of a clique, x c , is a vector of node labels. Thus, a clique could take one of l |c| labellings. Depending on the application, we define appropriate potential functions over nodes and cliques. They take the form Ψ i (x i ) = exp -θ i (x i ) and Ψ c (x c ) = exp -θ c (x c ) , where θ i (x i ) and θ c (x c ) denote the energies (also, called potentials) corresponding to node i taking label x i and clique c taking label x c , respectively. The joint probability distribution factorizing according to the nodes and the cliques is a fundamental property of mrfs. Based on (1), maximum a posteriori inference or map inference, computes the labelling x that minimizes the following energy,

E(x; θ) i∈V θ i (x i ) + c∈C θ c (x c ). (2)
However, except for some special graph topologies and/or clique potentials, this problem is NP-hard [START_REF] Shimony | Finding maps for belief networks is np-hard[END_REF], [START_REF] Li | Complexity of discrete energy minimization problems[END_REF]. Thus, there has been considerable research effort to develop approximate inference algorithms for mrfs. Several approaches exist to minimize this energy efficiently and approximately: especially methods based on graph cuts, belief propagation and continuous relaxation. Refer [START_REF] Szeliski | A comparative study of energy minimization methods for markov random fields with smoothness-based priors[END_REF], [START_REF] Blake | Markov random fields for vision and image processing[END_REF], [START_REF] Kappes | A comparative study of modern inference techniques for structured discrete energy minimization problems[END_REF] for a good survey about various methods. Among these methods, continuous relaxation based approaches have led to state-of-the-art algorithms and also, provide a theoretical foundation to the topic of map inference [START_REF] Wainwright | Map estimation via agreement on trees: message-passing and linear programming[END_REF], [START_REF] Komodakis | hyper)-graphs inference through convex relaxations and move making algorithms: Contributions and applications in artificial vision[END_REF].

First, we observe that the energy in ( 2) has a linear form, with respect to the energies, θ i (x i )'s and θ c (x c )'s. Thus, map inference can be equivalently represented as an intractable integer linear program (ilp) as follows,

minimize φ i xi θ i (x i )φ i (x i ) + c xc θ c (x c )φ c (x c ) (3a)
subject to

x c\i φ c (x c ) = φ i (x i ), ∀(i, c) : i ∈ c, ∀x i (3b) xi φ i (x i ) = 1, φ i (x i ) ∈ {0, 1} ∀i ∈ V xc φ c (x c ) = 1, φ c (x c ) ∈ {0, 1} ∀c ∈ C. (3c)
Here, for each node-label pair (i, x i ), there is an indicator variable φ i (x i ). Similarly, for each clique-label pair (c, x c ), there is an indicator variable φ c (x c ). Let us define a vector φ that is obtained by stacking all the φ i (x i )'s and φ c (x c )'s together. The normalization constraints, (3c), ensure that for a given labelling of all the nodes, for each node i, only one of φ i (x i ) will be set to 1 and for each clique c, only one of φ c (x c ) will be set to 1. The node based indicator variables, φ i (x i )'s, are enough to denote the labelling of the graphical model. However, we need the clique based indicator variables, φ c (x c )'s, in order to model our optimization problem. Shortly, we will see that this approach leads to a relaxation of the integer linear program that is convex in nature. Since, nodes and cliques are having separate indicator variables, we have to make sure that the labelling of the nodes and the labelling of the cliques agree. We ensure this through the marginalization constraints given by (3b). We will see how the summation x c\i φ c (x c ) is performed. For a given clique c and node i ∈ c, there will be a set of clique labellings x c 's, where the label of node i is fixed to x i . We will denote this set as x c\i . With a slight abuse of notation, it is a more compact way of denoting the set, x c : x c (i) = x i . Since, we will come across such summations often, a shorter notation is preferable. The summation of φ c (x c )'s is performed over this set and the constraint says that the sum should match with φ i (x i ).

Using the toy graphical model given in Fig. 1, we will further understand these variables and constraints. In this graphical model, each clique is made of three nodes, i.e., a = {1, 2, 3} and b = {2, 3, 4}. We will assume that each node could take one of three labels, {x 1 , x 2 , x 3 }. Thus, both the φ(x a )'s and the φ(x b )'s consist of 27 elements. Consider the case where node 3 takes label x 2 , i.e., φ 3 (x 1 ) = 0, φ 3 (x 2 ) = 1, φ 3 (x 3 ) = 0. We see that the normalization constraint (3c) is satisfied. Node 3 is part of both cliques a and b. There are nine elements in each set of φ a (x a )'s and φ b (x b )'s, which correspond to the case of node 3 taking a particular label. We denote these sets by x a\3 and x b\3 , respectively. According to the marginalization constraint (3b), the summation of φ a (x a )'s (resp. φ b (x b )'s) over x a\3 (resp. x b\3 ) should equal 1. In the quest for efficient algorithms for approximate map inference, one could derive continuous relaxation based formulations for the ilp given in (3). There have been relaxations based on linear programming (lp), quadratic programming (qp), semidefinite programming (sdp) and second-order cone programming (socp). [START_REF] Kumar | An analysis of convex relaxations for map estimation of discrete mrfs[END_REF] has presented an excellent analysis of these various relaxations. A continuous relaxation is naturally going to return an approximate solution and it is worthwhile to tighten the relaxation in order to attain more accurate results. In this chapter, we will survey several important aspects of this topic. First, we will see various algorithms that could help to achieve a tighter lp relaxation. Second, we will see inference algorithms based on the sdp relaxation that could offer better results than the lp relaxation for some problem instances. We will conclude by indicating research efforts to characterize graph topologies and clique potentials that govern the tightness of these relaxations.

lp relaxation

In this section, we will see how a tractable optimization problem could be obtained by lp relaxation and present the core concepts of marginal and local polytopes. First, we observe that the ilp in (3) could be equivalently expressed as an intractable linear program. In this lp, the objective is expressed in the same way as (3a) and the decision variables, φ i (x i )'s and φ c (x c )'s, take continuous values within a polytope called the marginal polytope, denoted as M(G). The marginal polytope is the convex hull of the feasible set of the ilp (3). Thus, the vertices of M(G) are points taking {0, 1} integer values, satisfying the constraints, (3b) and (3c). The optimal solution of any linear program consists of one of the vertices of the polytope over which it is optimized. Thus, the solution of this lp will automatically belong to the feasible set of (3). However, one needs an exponential number of constraints to represent the facets of M(G), thus this lp is as hard the original ilp. In order to obtain a more efficient situation, we could optimize over a feasible region that is simpler than the marginal polytope. In order to characterize such tractable feasible regions, we need to understand more about the marginal polytope. The marginal polytope contains those φ's for which the φ i (x i )'s and φ c (x c )'s will be valid marginals, with respect to some joint probability distribution over all the random variables. This property can be stated as follows,

M(G) = φ | ∃ P ∈ P({0, 1, ..., l -1} |V| ) s.t. φ i (x i ) = P (X i = x i ) ∀i ∈ V, φ c (x c ) = P (X c = x c ) ∀c ∈ C (4)
where P({0, 1, ..., l -1} |V| ) is the set of all valid probability distributions defined over the finite set {0, 1, ..., l -1} |V| . It takes an exponential number of linear constraints to ensure that a vector φ belongs to M(G). The main idea behind lp relaxations is to enforce a tractable number of constraints, which will lead to simpler polytopes to optimize over. The most common lp relaxation takes the following form,

minimize φ i xi θ i (x i )φ i (x i ) + c xc θ c (x c )φ c (x c ) (5a)
subject to

x c\i φ c (x c ) = φ i (x i ), ∀(i, c) : i ∈ c, ∀x i (5b) xi φ i (x i ) = 1, φ i (x i ) ≥ 0 ∀i ∈ V xc φ c (x c ) = 1, φ c (x c ) ≥ 0 ∀c ∈ C. (5c)
The marginalization constraints (5b) and the normalization constraints (5c) should be understood similar to (3b) and (3c), respectively. In this case, we work with continuous valued variables. For this lp, the constraint polytope is called the local polytope because the linear constraints are marginalization constraints (5b) that are only enforced locally with respect to the cliques. This represents a substantially lesser number of constraints compared to the marginal polytope. We will denote the local polytope as L(G). The local polytope is an outer bound on the marginal polytope. More precisely, it will contain all the points that satisfy (4), since, they automatically satisfy (5b) and (5c), also. Further, L(G) contains other points that satisfy constraints (5b) and (5c) but not (4). The points contained within the local polytope are called pseudomarginals. This is inspired by the fact that the marginal polytope contains true marginals. All the {0, 1} valued vertices of the marginal polytope are also vertices of the local polytope. Apart from these, there are several fractional valued vertices in the local polytope. It is difficult to visualize the marginal and local polytopes. Fig. 2 represents these polytopes in an abstract way. Suppose the lp relaxation returns a integer valued vertex, then we have the guarantee that we have recovered the exact map labelling of the graphical model. This is an important guarantee of the lp relaxation based approach [START_REF] Wainwright | Map estimation via agreement on trees: message-passing and linear programming[END_REF]. However, the lp relaxation could return a fractional valued vertex. The desired map labelling is obtained by rounding these fractional values. Tightening the polytope over which the lp is optimized could lead to a fractional solution that could give a better integral solution after rounding or if possible an integer valued solution could be obtained. Since, the integral points belonging to the local polytope correspond to the vertices of the marginal polytope, an integral solution obtained through a tighter polytope will correspond to a vertex of the marginal polytope.

We have already seen that the map solution will correspond to a vertex of the marginal polytope. Thus, we would have obtained the exact map solution, if we are lucky with our tighter relaxation. So far, we have discussed about two linear programs: the intractable lp that is exactly equivalent to the ilp given in (3) and the lp relaxation given in [START_REF] Li | Complexity of discrete energy minimization problems[END_REF]. The formulation given in ( 5) looks similar to the ilp, except for one difference. The integer values constraints in (3c) have been relaxed to continuous values (5c). However, this simple difference leads to a much more tractable problem.

Tightening the polytope

Now, we will see how looser polytopes like the local polytope could be tightened to obtain more accurate results. Tighter relaxations for map inference are intimately related to polyhedral combinatorics [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]. According to the combinatorial optimization community, a sequence of tighter lp relaxations called the Sherali-Adams hierarchy could approximate the ilp (3) to arbitrary precision [START_REF] Laurent | A comparison of the sherali-adams, lovász-schrijver, and lasserre relaxations for 0-1 programming[END_REF]. In each level of the hierarchy, we obtain a polytope SA r (G) by imposing marginalization constraints over all possible clusters of size r. A cluster is the most general data structure that we will come across in our discussions. In fact, any subset of nodes could be a cluster. In order to define the new set of marginalization constraints, we define a new set of variables, τ s for each cluster s. The marginalization constraints take the same form as (5b), with the summation computed over the cluster, while the label is held fixed for subsets (like cliques or individual nodes) of the cluster. The highest level of the hierarchy, SA treewidth (G), corresponds to the marginal polytope and the size of the clusters that is required at this level is equal to the treewidth of the graph. Thus the highest level has intractable complexity. Even lower levels like r = 2 or 3 are computationally expensive. Since, it involves imposing constraints on all possible pairs or triplets of nodes. In practice, we consider smaller sets of clusters, like only pairs of nodes that correspond to edges of the graph could be considered. This is exactly what leads to the local polytope. In section [START_REF] Zheng | Map-mrf inference based on extended junction tree representation[END_REF], we will see more about efforts to understand such hierarchies and their guarantees with respect to graph topology and/or clique potentials [START_REF] Wainwright | Treewidth-based conditions for exactness of the sherali-adams and lasserre relaxations[END_REF], [START_REF] Thapper | The complexity of finite-valued csps[END_REF], [START_REF] Weller | Tightness of lp relaxations for almost balanced models[END_REF][START_REF] Rowland | Conditions beyond treewidth for tightness of higher-order lp relaxations[END_REF]. For now, we will look at algorithms to tighten the relaxation, which work well in practice, while accompanied by a reasonable level of theoretical justification. We will see some of the pioneering works that algorithmically addressed the tighter relaxation problem [START_REF] Sontag | New outer bounds on the marginal polytope[END_REF], [START_REF] Komodakis | Beyond loose lp-relaxations: Optimizing mrfs by repairing cycles[END_REF], [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF], [START_REF] Werner | High-arity interactions, polyhedral relaxations, and cutting plane algorithm for soft constraint optimisation (map-mrf)[END_REF]. Before we go further, it is good to know that tightening the relaxation based on clusters has been pursued in the statistical physics community in the name of Kikuchi clustering (Wainwright & Jordan 2008, §4) and has been used within belief propagation algorithms [START_REF] Yedidia | Constructing free-energy approximations and generalized belief propagation algorithms[END_REF].

When one talks about tightening a polytope, the natural algorithmic approach that comes to mind is a cutting-plane method. In a cutting-plane method, one progressively tightens the polytope over which the optimization is performed by adding more constraints. This is the underlying principle behind [START_REF] Sontag | New outer bounds on the marginal polytope[END_REF], which starts with a loose relaxation of the marginal polytope, like the local polytope and iteratively adds constraints. In the previous paragraph, we came across marginalization constraints that could be enforced with respect to clusters of larger and larger sizes in order to tighten the polytope. In the combinatorial optimization literature, other valid constraints are also possible that lead to tighter relaxations. [START_REF] Sontag | New outer bounds on the marginal polytope[END_REF] worked with cycle inequalities [START_REF] Deza | Geometry of cuts and metrics[END_REF], which could be enforced for pairwise binary graphs, G {0,1} . For any labelling of such a graph, when one traverses a cycle of edges, one will encounter a change of node labelling, only an even (including zero) number of times. This fact leads to the following constraint for a cycle of edges C and any subset

F ⊆ C such that |F | is odd, (i,j)∈C\F φ ij (1, 0) + φ ij (0, 1) + (i,j)∈F φ ij (0, 0) + φ ij (1, 1) ≥ 1. (6)
Here, the φ ij (•) are (pseudo)marginals corresponding to the edge ij and a labelling of the edge is indicated by a pair of binary values. The φ ij 's will be integer valued only if they belong to a vertex of the marginal polytope. Otherwise, they could take fractional values. These constraints hold for any marginal φ ∈ M(G {0,1} ) and any cycle C of the pairwise binary graph G {0,1} . We have seen that for any Markov random field, one of the vertices of the marginal polytope corresponds to an optimal labelling of the nodes. While optimizing over a looser polytope (like the local polytope), the cutting-plane algorithm strives to add constraints in order to reach the integer valued vertex of the marginal polytope. The pseudomarginals in an outer bounding polytope like L(G) need not satisfy the above cycle inequality constraints. Thus, enforcing these constraints will lead to a tighter polytope. The important step in any cutting-plane algorithm is about finding the constraints to add in an efficient manner, which is called the separation problem. In the algorithm of [START_REF] Sontag | New outer bounds on the marginal polytope[END_REF], the cycle that most violates the cycle inequality ( 6) could be selected.

Even though the number of cycles in a general graph is exponentially large, it is possible to identify the violated cycle inequalities in polynomial time. In fact, it is of complexity O(n 2 logn + n|C|) based on Dijkstra's shortest path algorithm along with a Fibonacci heap data structure. So far, we have discussed an approach which will work for pairwise binary graphs. This will be a recurring setting in the study of tighter relaxations. Generally, extending these ideas to nodes taking multiple labels and also, to graphs with higher-order cliques lead to looser bounds, computationally more expensive algorithms and larger problem sizes due to introduction of auxiliary variables. For example, [START_REF] Sontag | New outer bounds on the marginal polytope[END_REF] has shown how to extend the cycle inequalities constraints to the multi-label scenario and also, to non-pairwise graphs. Again, they take inspiration from polyhedral combinatorics and propose an approach based on projection and aggregation. Consider a pairwise graph, with multi-label nodes. The set of labels of a node i, which we will denote as l i , can be partitioned into two sets. For ease of exposition, we will assume that all nodes take the same number of labels l. For l labels, there are 2 (l-1) -1 possible partitions and let π s i denote one such partition. Let π i be a collection of partitions for node i. We define a binary projection graph, G π = (V π , C π ), where there is a node in V π ∀π s i ∈ π i , ∀i ∈ V and there is an edge between π s i and π t j if (i, j) ∈ C. If π i consists of all possible partitions for all nodes i ∈ V, then G π is called the full projection graph. If each node's set of labels is partitioned only once, i.e., |π i | = 1 ∀i, we have the single projection graph. In the l-projection graph, each π i consists of one versus the rest partitions for each of the l labels. Given a marginal with respect to the original marginal polytope, φ ∈ M(G), its values could be aggregated to define marginals with respect to the marginal polytope of the binary projection graph. For this marginal polytope, it is possible to define cycle inequalities as follows,

(i,j)∈c\f φ π ij (x i = x j ) + (i,j)∈f φ π ij (x i = x j ) ≥ 1 where φ π ij (x i = x j ) = xi∈li,xj ∈lj : πi(xi) =πj (xj ) φ ij (x i , x j ) φ π ij (x i = x j ) = xi∈li,xj ∈lj : πi(xi)=πj (xj ) φ ij (x i , x j ) (7)
where x i takes binary values {0, 1}, the projection operation π i (x i ) maps a node label, x i , to one of these binary values, C is a cycle with respect to the original graph G and any F ⊆ C such that |F | is odd. These equations are easy to understand for single projection graphs but could be derived for the full projection and l-projection cases, also. Thus, depending on whether the original graph has binary variables or multi-label variables, we obtain inequalities [START_REF] Zheng | Map-mrf inference based on extended junction tree representation[END_REF] or (??), respectively. Based on these cycle inequalities we could obtain cutting-planes to tighten the polytope. Thus, the algorithm given in [START_REF] Sontag | New outer bounds on the marginal polytope[END_REF] proceeds as follows. The first iteration involves solving an lp over a loose polytope, like the lp in [START_REF] Li | Complexity of discrete energy minimization problems[END_REF]. Then in each iteration, given the optimal pseudomarginals, cutting-planes (upto to n of them) are added and the tighter lp is solved to optimality. This is repeated until no cutting-planes are found. Even though there are specialized solvers to solve the lp relaxation in [START_REF] Li | Complexity of discrete energy minimization problems[END_REF], specialized efficient solvers are not yet available to optimize the linear objective over a polytope which also has cycle inequalities constraints. For the binary case, it is possible to optimize using the Frank-Wolfe algorithm, using linear or semidefinite programming to optimize over the tighter polytope. For the multi-label case, a commercial solver like CPLEX is needed. Note, even though only the single projection graph leads to a surjective projection between the marginals of the multi-label graph to the marginals of the binary graph, it is preferable to work with the full projection graph. This is because we need several single projection graphs to obtain the same tightness as the full projection graph. Similarly, the full projection graph is tighter than the l-projection graph. [START_REF] Sontag | New outer bounds on the marginal polytope[END_REF] have shown experimental evidence, also, regarding better tightness of the full projection graph. Also, in order to extend this work to higher-order graphs, we need to create an intermediate pairwise graph which involves auxiliary variables corresponding to the higher-order clique potentials. (Wainwright & Jordan 2008, §E.3) presents one way to convert higher-order cliques to pairwise edges by adding auxiliary variables. Thus, we see how dealing with multi-label nodes and higher-order cliques lead to the addition of several auxiliary variables. Even though the above work greatly helps to improve our understanding about tighter relaxations, it is not scalable. This is because we are not able to develop specialized algorithms for solving the lp relaxation with additional cycle inequalities based constraints. We are forced to use standard off-the-shelf lp solvers. The lack of scalability of standard lp solvers is well-known in the map inference literature [START_REF] Yanover | Linear programming relaxations and belief propagation-an empirical study[END_REF]. This is because they do not exploit the structure of the graphical model. Working in the dual space, leads to exploitation of the graph structure. Hence, there have been several scalable algorithms to solve the lp relaxation that are based on dual decomposition [START_REF] Komodakis | MRF energy minimization and beyond via dual decomposition[END_REF], [START_REF] Sontag | Introduction to dual decomposition for inference[END_REF]. We will see how by recalling the dual presented in [START_REF] Komodakis | MRF energy minimization and beyond via dual decomposition[END_REF]. This is derived for the lp relaxation shown in [START_REF] Li | Complexity of discrete energy minimization problems[END_REF] based on the decomposition of the original graph into a set of subgraphs. Based on such a decomposition, ( 5) can be equivalently written as,

minimize φi,φc,φ Si ,φ Sc S∈S(G) i∈S xi θ Si (x i )φ Si (x i ) + c∈S xc θ Sc (x c )φ Sc (x c ) (8a)
subject to

x c\i φ Sc (x c ) = φ Si (x i ), ∀(i, c) : c ∈ S, i ∈ c xi φ Si (x i ) = 1, ∀i ∈ S; xc φ Sc (x c ) = 1, ∀c ∈ S φ Si (x i ) ≥ 0 ∀i ∈ S; φ c (x c ) ≥ 0 ∀c ∈ S              ∀S ∈ S(G) (8b) φ Si (x i ) = φ i (x i ) ∀i ∈ V, ∀x i ; φ Sc (x c ) = φ c (x c ) ∀c ∈ C, ∀x c . ( 8c
)
Here S(G) is the set of subgraphs over which the original graph is decomposed. The subgraphs should be chosen such that all nodes and cliques of the original graph are covered by at least one subgraph. Also, each subgraph should share at least one node or clique with at least one other subgraph. The potentials θ S i (x i ) and θ S c (x c ) are chosen such that

S∈S(i) θ S i (x i ) = θ i (x i ) ∀i ∈ V, S∈S(c) θ S c (x c ) = θ c (x c ), ∀c ∈ C. A simple
way to achieve this is by setting the potentials as follows:

θ S i (x i ) = θi(xi) |S(i)| ∀S ∈ S(i) and θ S c (x c ) = θc(xc) |S(c)| ∀S ∈ S(c).
The consensus constraints (8c) ensure that this formulation is equivalent to [START_REF] Li | Complexity of discrete energy minimization problems[END_REF]. We could derive the dual by taking the consensus constraints (8c) into the objective and it takes the following form, max.

δ S∈S(G) min. φ Si ,φ Sc i∈S xi (θ Si (x i )+δ Si (x i ))φ Si (x i )+ c∈S xc (θ Sc (x c )+δ Sc (x c ))φ Sc (x c ) (9a) subject to x c\i φ Sc (x c ) = φ Si (x i ), ∀(i, c) : c ∈ S, i ∈ c xi φ Si (x i ) = 1, ∀i ∈ S; xc φ Sc (x c ) = 1, ∀c ∈ S φ Si (x i ) ≥ 0 ∀i ∈ S; φ c (x c ) ≥ 0 ∀c ∈ S              ∀S ∈ S(G) (9b) S:i∈S δ Si (x i ) = 0, ∀i ∈ V, ∀x i ; S:c∈S δ Sc (x c ) = 0, ∀c ∈ C, ∀x c . (9c)
Here, δ Si (x i ) are the dual variables with respect to the nodes and there is one such dual variable for each subgraph S, each node i ∈ S and for each label x i . δ Sc (x c ) are the dual variables with respect to the cliques and there is one such dual variable for each subgraph S, each clique c ∈ S and for each possible clique labelling x c . The constraints given in (9c) ensure that we eliminate the global variables, φ i (x i )'s and φ c (x c )'s, from the objective. We work only with the subgraph based variables, φ Si (x i )'s and φ Sc (x c )'s and the objective decomposes over the subgraphs. In other words, the minimization subproblems that we observe in the objective (9a) are with respect to individual subgraphs. Usually, the subgraphs are the individual pairwise edges or cliques or hypertrees of the original graphical model. A hypertree is a more general way of looking at a tree. It is a tree which could be made of hyperedges, not only pairwise edges. Hence, a tree made of only pairwise edges is also a hypertree. Note that nodes, edges and cliques are instances of hypertrees, too. The convenience with hypertrees is that the above minimization could be performed exactly and efficiently. This is because the minimization subproblem in a subgraph corresponds to performing map inference within a graph of the same topology as the subgraph and with suitably defined potentials. A fundamental result in graphical model is that we can perform map inference in hypertrees, exactly and efficiently [START_REF] Koller | Probabilistic graphical models: principles and techniques[END_REF]. In general, it is possible to decompose the graph according to subproblems that are not hypertrees. We will discuss more about this aspect towards the end of the next section. At this point, a natural question comes to mind. What happens to the lp relaxation if the original graphical model is a hypertree, i.e., it has no loops? It is not only efficient to perform map inference efficiently in a hypertree but in fact, the local polytope for such a graphical model is tight. Further, there are other graphical models where the local polytope is tight. A very important case is when the clique potentials are submodular [START_REF] Blake | Markov random fields for vision and image processing[END_REF]. Submodular clique potentials are an example of attractive potentials. An attractive clique potential encourages the nodes to take similar labels. Specifically, for pairwise binary graphs, submodular clique potentials satisfy the following condition,

θ ij (0, 1) + θ ij (1, 0) ≥ θ ij (0, 0) + θ ij (1, 1) (10)
from which we can see that similar labels are encouraged, when we try to minimize the energy (2). Another example of a graphical model for which the local polytope is tight, appears in the problem of maximum weight matching in a bipartite graph, which can be formulated as a map inference problem [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF].

So far, we have seen three types of data structures: clusters, cycles and hypertrees. They are all subgraphs of the original graphical model. This will be a common theme to several ideas discussed in this chapter: tightening the relaxation through formulations involving subgraphs of the graphical model. These subgraphs will have more structure compared to hypertrees. At the same time, these subgraphs will have a structure that lends itself to more efficient computation. Just like hypertrees have an efficient map inference algorithm, there are other graph topologies and/or clique potentials that lead to efficient computation. We will see more of such special subgraphs in the coming sections and discuss insights and algorithms based on them. Even though we will encounter different graph topologies in practical problems, as a first step, we recommend the reader to imagine a two-dimensional grid graph (a planar graph, where nodes are arranged in the form of rows and columns) and visualize structures like clusters, cycles and higher-order cliques on such a graph. Grid graphs are common in computer vision problems like stereo depth estimation and image segmentation. [START_REF] Kappes | A comparative study of modern inference techniques for structured discrete energy minimization problems[END_REF] is a good starting point to explore more about various datasets for map inference in mrfs.

Cluster Pursuit Algorithms

We will now look further into cluster based methods and we will describe algorithms that achieve efficiency by working in the dual space. We have already mentioned relaxation hierarchies like Sherali-Adams that involve a series of tighter problem levels. At each level, marginalization constraints are enforced based on an exhaustive set of clusters of a particular size. As mentioned in section (1.1), a cluster could be any subset of nodes of the graph. In practice, we will consider connected subsets of nodes (formed by the union of a subset of cliques) as clusters. Let us see more clearly what it means to add cluster based marginalization constraints. Suppose, we have a graph, with pseudomarginals φ i (x i )'s and φ c (x c )'s and we add marginalization constraints based on a set of clusters, S, then we have a new polytope defined by the following constraints,

x c\i φ c (x c ) = φ i (x i ) x s\c τ s (x s ) = φ c (x c ) ∀s ∈ S xs τ s (x s ) = 1 (11)
where the summation over x s\c is similar to the summation over x c\i in (3b). Note, the τ s (x s )'s are auxiliary variables and do not affect the dimension of the space in which the tighter polytope resides. The polytope is in the space of the φ i (x i )'s and φ ij (x i , x j )'s as before and is a tighter polytope compared to the local polytope. However, we cannot practically add a lot of cluster based marginalization constraints, even if they are small ones like triplets. For many problems it is sufficient to add a smaller set of clusters, when the clusters are chosen intelligently. We could intuitively imagine that it is enough if the polytope is tightened preferentially in the neighbourhood of the optimum, instead of being tightened uniformly all-around. We need a way to judge how well a cluster tightens the relaxation in the neighbourhood of the optimum. [START_REF] Werner | High-arity interactions, polyhedral relaxations, and cutting plane algorithm for soft constraint optimisation (map-mrf)[END_REF] presented an approach based on the language of constraint satisfaction problems (csps), by showing that all clusters that do not satisfy a csp subproblem could potentially tighten the relaxation. However, there can be many such clusters and we still need a way to rank them, so that a smaller subset of clusters could be added. [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF] shows a greedy approach to rank the clusters and shows an approach to incrementally add clusters as the algorithm proceeds. At this point of time, we would like to point out that the problem of map inference in mrfs is intimately related to csps Werner (2010), [START_REF] Thapper | The complexity of finite-valued csps[END_REF].

In order to develop the algorithm, it is possible to work in the primal space like [START_REF] Sontag | New outer bounds on the marginal polytope[END_REF]. Working with the primal, introduces cutting-planes but no new decision variables. This is in contrast to working with the dual, which could lead to the introduction of new decision variables. However, there are advantages to working in the dual space. Working with the dual, helps in designing a principled criterion to choose the clusters. This is based on the fact that the dual, like the one shown in ( 9), provided a lower bound to the map energy in (2) [START_REF] Wainwright | Map estimation via agreement on trees: message-passing and linear programming[END_REF]. Thus, it is possible to rank the clusters based on how they may increase this lower bound. A similar criterion to rank the clusters in the primal is hard to achieve. In both the primal and the dual, we have a new optimization problem each time we add a new set of cluster based marginalization conditions and in the case of the daul, we have new dual variables corresponding to the added clusters. Interestingly, the dual formulation is such that we can get a feasible starting point by setting the old dual variables to their final value in the previous problem and by setting the new dual variables to zero. Thus, the main advantages of working in the dual are summarized as follows:

• Principled condition to choose clusters.

• Warm-starting based on values from previous iteration.

• Scalable approach that readily works with multi-label and higher-order graphs. [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF] adds clusters from a predefined set of small clusters, i.e., it is based on dictionary enumeration. For ease of exposition, we will present the following equations considering a pairwise graph, G = (V, E). Then, we will mention how to extend these concepts to graphs with higher-order cliques. In case, the graph contains small chordless clusters like {(i, j, k)|(i, j), (j, k), (k, i) ∈ E}, we will have a dictionary of such triplet clusters. In case of a grid graph, the dictionary will be made of the square faces of the graph. In order to rank the clusters exactly, one needs to define a dual optimization problem for each cluster, i.e., an optimization problem that will additionally have marginalization constraints based on that cluster. Such a dual optimization problem has to be solved to optimality to assess the benefit of adding that cluster. Higher the optimal objective, higher is the rank for the cluster. Doing this for all clusters in the dictionary is very expensive. Instead, one could exploit a property shared by various dual based algorithms. This property is that the objective of a dual based algorithm increases monotonically. Thus, we could run for only one iteration a dual optimization problem to which marginalization constraints w.r.t. one cluster have been added. The increase in the dual objective after one iteration is guaranteed to be a lower bound on the increase that is expected if the dual optimization problem is solved to optimality. Thus, the clusters are ranked based on this lower bound. In order to obtain a valid lower bound, we need a dual algorithm for which the objective increases monotonically. This rules out an algorithm based on supergradient ascent to optimize (9), which is not a strictly ascending algorithm. On the other hand, coordinate ascent based approaches are strictly ascending [START_REF] Meshi | Smoothed coordinate descent for map inference[END_REF]. [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF] is based on an algorithm called mplp Globerson & Jaakkola (2008). Note, the dual for mplp is of a different form compared to (9) and its derivation involves the introduction of auxiliary variables, which denote duplicate copies of the edge based pseudomarginals, φ ij (x i , x j ).

We will denote the set of dual variables as λ and there are dual variables corresponding to each edge-node pair (λ ij→i (x i )), each edge (λ ij (x i , x j )) and each cluster-edge pair (λ s→ij (x i , x j )). Every iteration of the algorithm in [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF] involves closed form updates of all these dual variables, similar to mplp. We note that the size of λ keeps increasing as we add cluster based constraints. Suppose, at the end of iteration t, the dual variables are λ t . In iteration t + 1, we would like to compute the criterion for some cluster s. In order to run one iteration of the dual problem that involves this additional cluster, we will warm start the dual variables corresponding to the already present clusters using λ t and we will initialize the dual variables corresponding to cluster s to zero. Since, we are warm starting using λ t , the dual increases in value only based on updates from the cluster s. This quantity has a closed form expression, which is expressed in terms of edge based beliefs. For every edge (i, j) ∈ s, we could define a belief as,

b ij (x i , x j ) = λ ij (x i , x j ) + s :e∈s λ s →ij (x i , x j ). ( 12
)
The belief, b ij (x i , x j ), is directly proportional to the marginal probability of edge ij taking label (x i , x j ). The summation in ( 12) is not affected by the dual variables λ s→ij (x i , x j ) because they are set to zero. Thus, the increase in the dual objective due to the new cluster s takes the following form,

d(s) = ij∈s max xi,xj b ij (x i , x j ) -max xs ij∈s b ij (x i , x j ) . (13)
d(s) is a lower bound on the improvement to the dual objective if cluster s is added. Thus, the clusters are ranked with respect to d(s) and are added in a greedy fashion. The overall approach based on these ideas is shown in algorithm (1).

Algorithm 1 Dual algorithm with iterative tightening 1: Run a dual algorithm like mplp over the local polytope as close to the optimum as possible (say, 1000 iterations or convergence, whichever comes first). 2: Recover an integral solution and compute primal-dual gap. If the gap is less than a small threshold, then exit. 3: Add a fixed number of clusters according to the bound criterion ( 13). 4: Warm start the dual variables if possible and run the dual algorithm for a fixed limited number of iterations. 5: Return to step 2.

In algorithm (1) the integral solution could be recovered in several ways [START_REF] Ravikumar | Message-passing for graphstructured linear programs: Proximal methods and rounding schemes[END_REF], [START_REF] Meshi | Smoothed coordinate descent for map inference[END_REF], [START_REF] Savchynskyy | Getting feasible variable estimates from infeasible ones: Mrf local polytope study[END_REF]. Many times, a simple and efficient rounding scheme is preferable, like independently picking for each of the nodes the label with maximal pseudomarginal value. In step 4, it is sufficient to run the dual algorithm for a fixed number of iterations such that we have reached a neighbourhood of more optimal decision variables. In case, we run the dual algorithm to optimality in step 4, adding clusters is exactly equivalent to adding cutting-planes in the primal problem.

In order to extend these ideas to higher-order cliques, we first observe that we have seen three groups of nodes in our equations so far: clusters, edges and individual nodes. Also, in practice the clusters are built as unions of edges. The equations involved variables that associate a larger group of nodes with a smaller subset of that larger group. We could think about this in terms of tuples of the following form: (A, B, x B ). Here, A is a larger subset of nodes like a cluster or an edge. B is also a subset of nodes such that B ⊂ A. B could be an edge (resp. node), if A is a cluster (resp. cluster or edge). x B is one possible labelling of the nodes in B. Such a tuple is called a pencil in graphical models literature [START_REF] Werner | High-arity interactions, polyhedral relaxations, and cutting plane algorithm for soft constraint optimisation (map-mrf)[END_REF]. The dual variable λ s→ij (x i , x j ) which appeared a little earlier, is with respect to the pencil (s, ij, (x i , x j )). Thus, to use [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF] for higher-order cliques, we will replace the edges by higher-order cliques. We recollect that a clique with two nodes is also called an edge and a clique with more than two nodes is called a higher-order clique or hyperedge. Thus, we will work with dual variables of the form λ s→c (x c ), which corresponds to the pencil (s, c, x c ). As before, s is a cluster which defines additional marginalization constraints and now, it is a union of higher-order cliques. c is one such higher-order clique and x c is one possible labelling of c.

Another point to keep in mind is that the marginalization constraints with respect to a set of clusters S, could be equivalently represented in another way. This equivalent representation involves a new graphical model [START_REF] Werner | High-arity interactions, polyhedral relaxations, and cutting plane algorithm for soft constraint optimisation (map-mrf)[END_REF]. In this graphical model, the clusters s ∈ S are represented as cliques, apart from the original set of cliques C. However, the clique potentials, θ s (x s )'s, of the clusters will all be set to zero. Thus, when we consider the lp relaxation equations (similar to [START_REF] Li | Complexity of discrete energy minimization problems[END_REF]) for this graphical model, the objective will have the same value as the original graphical model because the additional cluster based potentials are zero valued. When we look at the constraints, there will be additional marginalization constraints present with respect to the new clusters, s ∈ S, involving new pseudomarginals φ s (x s )'s. We can see that these pseudomarginals are exactly like the auxiliary variables τ s (x s )'s that we saw in (11). Thus, these new pseudomarginals have the same effect on the original pseudomarginals, φ i (x i )'s and φ c (x c )'s. They get constrained to be in a tighter polytope. The advantage of imagining such a graphical model with additional zero valued potentials is to write the lp relaxation equations in a symmetric manner using pencils. For this new graphical model, the primal form of the lp relaxation will take the following form,

minimize φ i∈V xi θ i (x i )φ i (x i ) + c∈C xc θ c (x c )φ c (x c ) + s∈S xs θ s (x s )φ s (x s ) (14a) subject to x A\B φ A (x A ) = φ B (x B ), ∀(A, B, x B ) ∈ J (14b) xi φ i (x i ) = 1, φ i (x i ) ≥ 0 ∀i ∈ V xc φ c (x c ) = 1, φ c (x c ) ≥ 0 ∀c ∈ C xs φ s (x s ) = 1, φ s (x s ) ≥ 0 ∀s ∈ S. (14c)
Here, the set J is made of pencils (A, B, x B ) of the following form: if A is a clique of the original graphical model, then B corresponds to the nodes of that clique; if A is a cluster added to tighten the polytope, then B corresponds to the cliques whose union is the cluster A. For example, we can see that for a pairwise graph, a cluster s could be a triplet and marginalization constraints are enforced between this triplet and the edges that make up the triplet.

More efficient cluster pursuit algorithms

Among the literature on tighter relaxations, a few of them have designed algorithms based on the dual of the primal problem given in ( 14) [START_REF] Werner | High-arity interactions, polyhedral relaxations, and cutting plane algorithm for soft constraint optimisation (map-mrf)[END_REF], [START_REF] Batra | Tighter relaxations for map-mrf inference: A local primal-dual gap based separation algorithm[END_REF]. That dual takes the following form,

maximize h A ∀A∈V∪C∪S y A→B (x B ) ∀(A,B,x B )∈J i∈V h i + c∈C h c + s∈S h s (15a) subject to h A ≤ θ A (x A ) + Z|(Z,A,x A )∈J y Z→A (x A ) - B|(A,B,x B )∈J y A→B (x B ) ∀A ∈ V ∪ C ∪ S, ∀(A, B, x B ) ∈ J. (15b)
We observe that the added clusters influence the dual objective through the variables h s , while they do not affect the primal objective because of the zero valued potentials. Using this dual formulation, [START_REF] Batra | Tighter relaxations for map-mrf inference: A local primal-dual gap based separation algorithm[END_REF] has addressed a computational bottleneck in [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF]. The computational complexity of computing d(s) given in ( 13) is O(l |s| ). Thus, computing this score for all the clusters enumerated in the dictionary is computationally very heavy. [START_REF] Batra | Tighter relaxations for map-mrf inference: A local primal-dual gap based separation algorithm[END_REF] presents a heuristic criterion which could be used to first select a smaller subset of the clusters from the dictionary and compute d(s) only for those clusters. Before we look at this heuristic criterion, we first observe that

θ A (x A ) θ A (x A )+ Z|(Z,A,x A )∈J y Z→A (x A )- B|(A,B,x B )∈J y A→B (x B ) is a reparameterization of θ A (x A ).
This means that for a given labelling of all the nodes in the graphical model, we will get the same energy with either the θ A (x A )'s or the θ A (x A )'s. Reparameterization is a concept that we will come across often in graphical models literature, for example, [START_REF] Kolmogorov | Convergent tree-reweighted message passing for energy minimization[END_REF]. For each clique c ∈ C, we could define a quantity,

l(c) = θ c (x p c ) -min. xc θ c (x c ) (16)
where x p c is an integral labelling of the clique c that is obtained in step 2 of algorithm (1). This heuristic is derived based on the form of the complementary slackness condition for the constraint given in (15b). Then, for a cluster s, we define a criterion based on the cliques that it is made of,

l(s) = c:c∈s l(c). (17)
Compared to d(s) in ( 13), this criterion could be computed with complexity O(l |c| ). Just like we did with d(s), the clusters could be ranked based on the value of l(s). We note that this criterion comes with poorer guarantees compared to d(s) and it is best to use it as an initial preprocessing step. l(s) is computed for all clusters in the dictionary, in order to select a small subset of clusters and this smaller set is ranked according to d(s). We also point out that the condition l(s) = 0 for a cluster s is equivalent to satisfaction of the csp subproblem in [START_REF] Werner | High-arity interactions, polyhedral relaxations, and cutting plane algorithm for soft constraint optimisation (map-mrf)[END_REF].

The computation of d(s) [START_REF] Komodakis | hyper)-graphs inference through convex relaxations and move making algorithms: Contributions and applications in artificial vision[END_REF] need not be the only computationally heavy part of an algorithm for tighter relaxation. Depending on the dual algorithm, updating the dual variables could be costly, too. For example, the mplp based approach of [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF] updates the cluster-to-clique dual variables (λ s→c (x c )) with complexity that is exponential in the size of the cluster s. [START_REF] Sontag | Clusters and coarse partitions in lp relaxations[END_REF] shows a way to accelerate the update of these dual variables within the same mplp based algorithm. This is achieved by defining a polytope, which is looser than the one defined by (11) but still tighter than L(G). This polytope is looser because the marginalization constraint between the added clusters and the cliques is over a coarser partitioning of the label space of the cluster, as follows,

x c\i φ c (x c ) = φ i (x i ) zs\{z s i }:i∈c τ s (z s ) = xi∈z s i :i∈c φ c (x c ) ∀s ∈ S xc φ c (x c ) = 1 (18)
where {z s } is the set of labelling of the cluster s over a coarser label space. For each node in the cluster s, the set of labels is coarsened to a smaller set {z s i }. Then, marginalization constraints are enforced between a cluster and the clique it contains through these coarser labels. This will reduce the complexity of updating the cluster-to-clique dual variables (λ s→c (x c )). A better choice of the coarser label set {z s i } is important. We want to ensure that the coarse partitioning behaves as closely as possible to what d(s) guarantees with respect to increase in the dual objective. [START_REF] Sontag | Clusters and coarse partitions in lp relaxations[END_REF] presents a greedy approach with a threshold parameter, which leads to a trade-off between guaranteed improvement of the dual and the number of coarse states.

These cluster based ideas could be applied to practical problems, like the ones described in [START_REF] Yanover | Linear programming relaxations and belief propagation-an empirical study[END_REF]. For example, the problems of protein side chain prediction and protein design, have a graph structure that allows adding triplet based clusters. For stereo and segmentation problems, the graph is usually grid structured and we could work with clusters consisting of the four node faces of the graphs. So far, we have been looking at how to tighten the relaxation by enforcing additional cluster based constraints. At the same time, it is known in the graphical models literature that tighter relaxations are possible by using subgraphs which have loops (Komodakis et al. 2011, §6.1) within a dual decomposition formulation like (9). Is this approach related to tighter formulations using cluster based marginalization constraints? In fact, they are exactly the same concept. When we discussed about cluster based marginalization constraints, we presented a pair of problems: primal (14) and dual (15). The clusters had zero potentials in the primal, in order to ensure that the primal energy continues to be a function of the original node and clique potentials. However, we could define the cluster potentials in the following way:

S∈S(c) θ S c (x c ) = θ c (x c ), ∀c ∈ S.
Then, by considering only node and cluster potentials, we ensure that the primal energy stays the same. Incidentally, this form of the cluster potentials is also a required condition for the dual in (9). Thus, having cluster based marginalization constraints in the primal, is equivalent to having cluster based subproblems in the dual, with suitably defined potentials. We will understand this concept more by considering cycles. We will see how tighter relaxation could be achieved either by imposing cycle based marginalization constraints within an algorithm like [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF] or by decomposing the graphical model using cycle based subgraphs.

Cycles in the Graph

So far, we have been looking at clusters, which in theory could be any subset of the nodes. In practice, we seek small clusters which are connected to each other. The subset of nodes could have more structure, for example, they could form a cycle. A cycle is a chain of node pairs with the following form: {(x 0 , x 1 ), (x 1 , x 2 ), ..., (x n-2 , x n-1 ), (x n-1 , x 0 )}. Cycles play an important role in understanding about tighter relaxations for map inference. Suppose a given lp relaxation results in fractional values as the solution. So far, we have understood this as the relaxed polytope being not tight enough around the optimal integral vertex of the marginal polytope. Such fractional solutions could be directly characterized by the presence of frustrated cycles in the graph. To understand what these are and what to do about them, we will first consider a pairwise graph, G = (V, E), for ease of exposition. Later, we will see how to extend these works to higher-order graphs. Also, we will assume that all nodes take one of l labels.

So far, we have been made aware of the possibility of various dual formulations, ( 9), (15) and the mplp based dual of [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF]. All these duals lower bound the map energy given in (2). There is yet another dual formulation that throws light on the problem of frustrated cycles. It is given in [START_REF] Komodakis | Beyond loose lp-relaxations: Optimizing mrfs by repairing cycles[END_REF] and is of the following form, maximize

y i∈V min. xi θ i (x i ) + j:ij∈E y ij (x i ) (19a) subject to θij (x i , x j ) -y ij (x i ) -y ji (x j ) ≥ 0 ∀ij ∈ E (19b) ij∈E S θij (x i , x j ) ≤ ij∈E S θ ij (x i , x j ). (19c)
We will denote this dual problem as D(E S ), where, E S is a subset of edges of the graph and E is the set of all edges. We would like to highlight the presence of θ in the formulation, which is the set of all θij (x i , x j )'s and we will call them virtual potentials. Suppose, E S = E then we obtain a dual problem, D(E), that is equivalent to the intractable ilp (3). If θij (x i , x j ) = θ ij (x i , x j ) ∀ij ∈ E S , ∀x i , x j , then the dual, which we will call as D f ixed , is equivalent to the lp relaxation [START_REF] Li | Complexity of discrete energy minimization problems[END_REF]. It comes with the same guarantees as optimizing lp relaxation over the local polytope. The optimal solutions of D f ixed are charaterized by the following theorem.

Theorem 1 (Weak Optimality Condition [START_REF] Werner | A linear programming approach to max-sum problem: A review[END_REF]). After D f ixed has been solved to optimality, there must be at least one optimal label x * i for node i and at least one optimal label x * j for node j, such that θij (x * i , x * j ) = y ij (x * i ) + y ji (x * j ). The above theorem is a necessary but not sufficient condition for an optimal labelling of the original map inference problem (2). This is expected because D f ixed is a tractable approximation to D(E), which is an NP-hard problem. [START_REF] Komodakis | Beyond loose lp-relaxations: Optimizing mrfs by repairing cycles[END_REF] showed how solving D(E S ) presents a trade-off between these two extremes of tractability and accuracy. In order to see how it could be done, we need to understand the following stronger constraint that an optimal labelling for map inference is required to satisfy.

Theorem 2 (Strong Optimality Condition

). An optimal labelling of the graph that minimizes the energy ( 1) is such that it assigns the labels (x * i , x * j ) to the edge (i, j)

then θij (x * i , x * j ) = y ij (x * i ) + y ji (x * j )
, for all edges. Solving D(E) ensures theorem 2. Suppose, D(E S ) has been solved by some optimization algorithm and we obtain optimal labels for all nodes. We should keep in mind that there could be multiple optimal labels for some nodes. Suppose, we start at some node i on the graph and would like to take a step to a neighbouring node j. We could do it if ∃ x * i and x * j such that θij (x * i , x * j ) = y ij (x * i ) + y ji (x * j ). Suppose we traverse a cycle of nodes in this manner and for each node i, the step towards and away from it are based on the same optimal label x * i , then that cycle is not a frustrated cycle. If it is possible to traverse all possible cycles of the graph based on this criterion, then the graph does not have any frustrated cycles. An optimal solution without frustrated cycles and an optimal solution satisfying the condition in theorem 2 are equivalent. In such a situation, D(E S ) has managed to find the optimal map labelling. Suppose, a cycle in the graph could not be traversed according to the above mentioned criterion, then it is a frustrated cycle. Frustrated cycles could be of two different forms. One, where for all pairs of optimal labels for two adjacent nodes, θij (x * i , x * j ) = y ij (x * i ) + y ji (x * j ). Hence, it is not possible to take a step between these two nodes. Two, where a node i is not able to satisfy θij (x * i , x * j ) = y ij (x * i ) + y ji (x * j ) with all its neighbours based on the same optimal label x *

i . An optimal labelling with frustrated cycles satisfy theorem 1 only. In practice, if the clique potentials are attractive, then frustrated cycles are discouraged and the opposite is true for non-attractive potentials. In section (1.1) we said that if the clique potentials are submodular, then the local polytope is tight. Thus, there will be no frustrated cycles in a graphical model with submodular potentials. For general clique potentials, tightening the lp relaxation leads to the elimination of such frustrated cycles. Thus, cycles play an important role in understanding and addressing the tightening of lp relaxations.

We had earlier mentioned that ( 19) involves the virtual potentials, θ. If we can set θ properly then the optimal labelling obtained by solving (19) could have less or no frustrated cycles. [START_REF] Komodakis | Beyond loose lp-relaxations: Optimizing mrfs by repairing cycles[END_REF] has shown a way to iteratively modify θ, followed by solving the dual problem (19), in order to obtain an optimal labelling with less or no frustrated cycles. They proposed to solve a series of dual problems, D(E S ) with different E S . They solve these dual problems one after the other and repeatedly, until a stopping criterion is reached. Each E S is picked from a dictionary of cycles. For example, in a grid graph, the dictionary could be composed of cycles that are the faces of the grid and also, the cycles going around two adjacent faces. In theory, the set of edges E S in the optimization problem (19) could be any set of edges, not necessarily cycles. Since, it is frustrated cycles that we are trying to eliminate, it intuitively and algorithmically makes sense to choose E S to be cycles. Thus the algorithm in [START_REF] Komodakis | Beyond loose lp-relaxations: Optimizing mrfs by repairing cycles[END_REF] repeatedly iterates over a dictionary of cycles.

At each iteration, we have a given set of virtual potentials, θ and a given cycle, E S . Based on the optimal dual variables y from the previous iteration, we check whether the current cycle is a frustrated cycle. [START_REF] Komodakis | Beyond loose lp-relaxations: Optimizing mrfs by repairing cycles[END_REF] shows a principled way to "repair" such a frustrated cycle and this procedure is the heart of the paper. The approach is to modify the values of θ corresponding to the cycle E S . While making this modification, the contraints (19b) and (19c) should be maintained. We do this by picking a pair of nodes in E S , for which there is at least one pair of labels for which the constraint (19b) is an equality. This will always be true if the previous dual problem (19) has been solved to optimality. According to [START_REF] Komodakis | Beyond loose lp-relaxations: Optimizing mrfs by repairing cycles[END_REF], we modify θ such that for that pair of nodes, the constraint (19b) becomes a strict inequality for all pairs of labels between the two nodes. This modification has to be done while continuing to satisfy the contraint (19c). This is possible by increasing the elements in θ w.r.t. to the pair of nodes, while decreasing elements in θ w.r.t. adjacent pairs of nodes in the cycle. In a frustrated cycle, it is always possible to perform this operation, while satisfying the constraints given in (19b) and (19c). Once the cycle has been "repaired" this way, the dual problem is now solved, with the constraint (19c) enforced w.r.t. this cycle. Based on the new optimal dual variables y, this cycle will not be a frustrated cycle. These steps, "repair" cycle and solve the dual, are repeated for the next cycle in the dictionary and so on.

In this process, a cycle that was repaired earlier could again become a frustrated cycle. That is why the algorithm iterates over the cycles in the dictionary repeatedly. It is possible to warm-start y for the current dual optimization problem based on the previous optimal y because the virtual potentials are the same except for the two adjacent cycles in the dictionary. This leads to considerable speed-up. Interestingly, the dual objective increases monotonically as we solve one dual problem after the other. Thus, the sequence of optimal objective values are going closer to that of D(E), the intractable map inference problem, where contraint (19c) has to be satisfied over the entire set of edges, E. Based on this monotonic increase property, this algorithm could be terminated in a principled manner. For example, a good way to terminate is when there are no frustrated cycles with respect to the dictionary. Even though larger frustrated cycles could still exist, this approach is sufficient to return the map labelling in several practical problems. In section (2), we have looked at tightening the relaxation using cluster based marginalization constraints. Optimizing D(E S ), where E S is a cycle, is similar to enforcing marginalization constraints with respect to that cycle. Earlier, we worked with additional dual variables (λ s→c (x c )) with respect to that cluster s. In this case, we work with ( θij (x i , x j )) corresponding to the edges ij of the cycle E S , which are adjusted if the cycle is frustrated.

Searching for frustrated cycles

The main bottleneck with the approach given in [START_REF] Komodakis | Beyond loose lp-relaxations: Optimizing mrfs by repairing cycles[END_REF] is w.r.t. efficiency. Their approach iterates over a big dictionary of short cycles present in the graph. Also, for some graphs like sparse graphs with few short cycles, it is not clear how to enumerate the dictionary of cycles. Thus, it is desirable to choose a cycle directly from the graph, instead of choosing cycles from a predefined dictionary. [START_REF] Sontag | Efficiently searching for frustrated cycles in map inference[END_REF] has presented an approach to directly assess how a cycle will improve the dual bound. Their work combines ideas presented in [START_REF] Sontag | New outer bounds on the marginal polytope[END_REF], (Johnson 2008, §3.4) and [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF]. Just like [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF] we greedily choose a cycle that leads to best dual objective improvement based on running one iteration of a dual optimization problem. This dual problem has additional dual variables corresponding to the cycle, just like we saw in section (2). Therefore, we have a function that serves a purpose similar to d(s) in ( 13) for choosing a cluster. In this case, we don't choose the cycle from a dictionary of cycles. At the same time, it is possible to characterize more desirable cycles. In order to do that we first construct a graph with edge weights that are defined based on edge beliefs of the original graph. We have already come across the concept of edge beliefs in [START_REF] Schraudolph | Efficient exact inference in planar ising models[END_REF] and they are obtained through an optimization algorithm like the dual based algorithm in [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF]. In this new graph, we seek the cycle, which among the cycles with an odd number of negative edge weights, maximizes the minimum absolute value of the edge weights present. This will lead us to cycles in the original graph that are more suited for tightening the relaxation. (Johnson 2008, §3.4) showed why this is true and also, showed an algorithm to obtain desirable cycles efficiently for graphs with binary valued nodes. For binary variables, the new graph that needs to be constructed has the same topology as the original graph. In order to obtain an approach that works for multi-label graphs, [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF] observed that cycle inequalities (6, ??) also, impose constraints on an odd number of edges within a cycle. Thus, for the multi-label case, a new projection graph is constructed, which was earlier used by [START_REF] Sontag | New outer bounds on the marginal polytope[END_REF] to define cycle inequalities for graphs with multi-label nodes. [START_REF] Sontag | Efficiently searching for frustrated cycles in map inference[END_REF] then applies the algorithm of (Johnson 2008, §3.4) to this projection graph.

Once a cycle has been identified, it has to be used within an algorithm like that of [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF]. The algorithm in [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF] is based on mplp and the per iteration complexity will be high if the cycle is long. It is possible to bias the search algorithm to return cycles with shorter length. The cycle search algorithm of (Johnson 2008, §3.4) involves the construction of a spanning tree of the newly constructed graph and choosing an initial edge based on which the cycle is constructed. By constructing a shallow spanning tree and by using an efficient least common ancestor algorithm, cycles could be found, which are of shorter length and of higher rank w.r.t. the greedy criterion. In the next section, we will see an algorithm that further improves the efficiency when cycles are present within inference algorithms like mplp.

Empirical results show the clear benefit of this approach for graphs with few or no short cycles. There are problem instances where the frustrated cycle is a short one, i.e., it is equivalent to a small cluster. In such cases, the cluster pursuit algorithm based on d(s) is able to identify this cycle very quickly compared to the above cycle based greedy criterion. Thus, whenever possible, it is a good idea to add both cycles (found using the approach outlined above) and clusters (found using d(s) in ( 13)) to tighten the relaxation. It should be noted that if d(s) is used for finding cycles, then we need to work with a dictionary of cycles. For some graph topologies it could be difficult to construct this dictionary. Also, the approach of using d(s) to a dictionary of cycles is accompanied by the following hardness results:

• Suppose, the graph has binary variables and the beliefs are obtained by running the optimization routine to optimum, then finding the cycle that maximizes d(s) is equivalent to finding the most violated cycle inequality in the dual.

• Suppose, the graph has binary variables and the optimization is not run to optimum, then finding the cycle that maximizes d(s) is NP-hard.

• Suppose, the graph is multi-label, then it is always NP-hard to rank cycles based on d(s).

We will briefly discuss about cycles and higher-order mrfs. Many higher-order mrfs, involve both higher-order cliques and pairwise edges (for e.g., the datasets in [START_REF] Rother | Minimizing sparse higher order energy functions of discrete variables[END_REF]). In such graphs, we could consider the cycles involving the pairwise edges. In case, only higher-order cliques are present, pairwise edges with zero valued potentials could be considered and suitable cycles could be defined. This is exactly like considering zero valued cluster based potentials in ( 14). We have seen that a cluster is any subset of nodes and a cycle is a special type of cluster. Thus, we could have algorithms that impose cycle based marginalization constraints, just like cluster based marginalization constraints that we came across in section (2). Towards the end of that section, we mentioned the equivalence between algorithms involving cluster based marginalization constraints and algorithms involving cluster based subproblems within dual decomposition. The same holds for cycles, too. It is very well possible to achieve tighter relaxation by considering cycles as subproblems within dual decomposition. The important works in this direction have been [START_REF] Yarkony | Tightening mrf relaxations with planar subproblems[END_REF], [START_REF] Wang | A fast and exact energy minimization algorithm for cycle mrfs[END_REF] and we will discuss them next.

Efficient map inference in a cycle

Suppose, one or more cycles are introduced as subgraphs in dual decomposition (9), then efficient minimization of the cycle subgraphs is a challenge. If the subgraph is a pairwise tree, with m nodes, the minimization could be performed with O(ml 2 ) complexity using dynamic programming. This is equivalent to one pass of an algorithm called max-product message passing. In a tree, a node is chosen as the root and message computation starts at leaf nodes and message passing proceeds towards the root. Between two nodes, message computation takes O(l 2 ) complexity, thus resulting in O(ml 2 ) overall complexity. On the other hand, a naive approach for the cycle, with m nodes, would require O(ml 3 ) complexity. This is because the complexity of inference in graphical models is exponential in the treewidth of the graph and the treewidths of a tree and a cycle are 1 and 2, respectively. Generally, inference in a cycle, involves forming a clique tree by triangulating the cycle, followed by max-product message passing on the clique tree. This involves several passes of the max-product algorithm and is of complexity O(ml 3 ). There have been algorithms that have reduced the complexity of inference in cycles below O(ml 3 ) [START_REF] Felzenszwalb | Fast inference with min-sum matrix product[END_REF], [START_REF] Mcauley | Faster algorithms for max-product message-passing[END_REF]. [START_REF] Wang | A fast and exact energy minimization algorithm for cycle mrfs[END_REF] builds on these works and presents a more efficient algorithm. One way to triangulate a cycle is to enforce a node to be common across all the triangles, i.e., all the triangulating chords are from that node to the other nodes. This results in a clique tree in the form of a chain. [START_REF] Wang | A fast and exact energy minimization algorithm for cycle mrfs[END_REF] uses the presence of the common node across all the cliques to design a more efficient algorithm. Generally, as number of passes of the max-product algorithm increases fewer labels from each node participate in the message computation. Finally, the labels narrow down to the map labels for each node. In the naive approach, the l 3 factor appears in the complexity because all labels from each node participate in the message computation. At the same time, identifying the active labels for a node that are enough for computing the messages is a challenging task. [START_REF] Wang | A fast and exact energy minimization algorithm for cycle mrfs[END_REF] have derived inequality based bounds to decide which labels of a node participate in message computation. They derive these inequalities by exploiting the common node and they are able to identify the necessary labels for each node that are participating in message computation. They start with a low value for the bound that allows more labels to be selected in the initial iterations and the bound increases as the algorithm progresses. The algorithm is guaranteed to terminate and the exit condition involves the inactive labels and potentials. Thus, using their map algorithm for cycles within dual decomposition (9) leads to a more efficient overall algorithm.

If the optimization algorithm is like the mplp based algorithm of [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF], a cycle is treated just like a cluster and the algorithm will enforce marginalization constraints with respect to a cycle. The update of the dual variables correspond to min-marginal computation for the corresponding nodes. Given a graphical model, the min-marginal of a node w.r.t. to a label, is the minimum energy (of the form (1)) for that graphical model when the label of that node is fixed. Thus, each node-label pair is associated with a min-marginal value. For example, the max-product algorithm computes the map labelling of a tree by computing min-marginals. However, depending on the graph, min-marginal computation is more involved than computing the map labelling. For example, for cycles, it is more efficient to compute the map labelling compared to min-marginals. Apart from the algorithm for map inference in cycles, [START_REF] Wang | A fast and exact energy minimization algorithm for cycle mrfs[END_REF] has shown a heuristic way to compute min-marginals in cycles and has shown good empirical performance with that approach.

Planar subproblems

So far we have been discussing about individual cycles, either we compute marginalization constraints with respect to each of the cycles or optimize each cycle as a subproblem within dual decomposition. [START_REF] Yarkony | Tightening mrf relaxations with planar subproblems[END_REF] considers the possibility of optimizing multiple cycles together as one subproblem within dual decomposition. How does such a subproblem look like? Suppose that the original problem is a planar graph (like many computer vision problems) and consider a subproblem with the same topology as the original planar graph. Within dual decomposition, optimizing such a planar subproblem is equivalent to optimizing multiple cycles at the same time. Recall that dual decomposition requires the subproblems to be optimized exactly. The natural question is how is this planar subproblem going to be optimized exactly in an efficient manner? We will have to consider specific pairwise potentials that will make this possible. For example, [START_REF] Schraudolph | Efficient exact inference in planar ising models[END_REF] showed how exact inference could be performed efficiently for a planar Ising model with binary variables. In an Ising model, the values taken by the edge potentials depend only on whether the two nodes take same or different labels. [START_REF] Yarkony | Tightening mrf relaxations with planar subproblems[END_REF] uses planar subproblems which are of the above type. However, their original graphs are planar graphs with nodes taking multiple labels. They show that a node in the planar subproblem could be assigned binary labels, where the binary labels correspond to a binary partition of the label set of that node. They show one well motivated way to obtain a binary partition of a label set. Other approaches are also possible. In their algorithm, initially, the non-smooth dual ( 9) is solved to optimality using a decomposition based on trees. Then, labels are obtained for each node by rounding the fractional relaxed variables. Then, they partition the label set of each node in a one-vs-rest manner based on this labelling. Thus a binary planar subproblem is created and added to the dual decomposition. Now, we have a dual problem, with tree based subproblems and also, a planar subproblem. Again, this dual is solved to optimality and based on the resulting labels another binary planar subproblem is created. They fix a maximum limit on the number of binary subproblems that are added in this manner (say, 10). Their intuition is that each time a dual is solved to optimality and labels are decoded, the resulting energy is an upper bound to the actual energy (just like how the dual is a lower bound). The binary planar subproblems are encouraging the nodes to take labels corresponding to such upper bounds. Within each iteration of dual decomposition, the binary subproblem is solved to optimality based on an efficient algorithm like [START_REF] Schraudolph | Efficient exact inference in planar ising models[END_REF] and the optimal labelling leads to a valid supergradient with respect to that subproblem [START_REF] Komodakis | MRF energy minimization and beyond via dual decomposition[END_REF], Lemma 1). As we said before this optimal binary labelling corresponds to a one-vs-rest partitioning of the original label set. The binary labels that are assigned to the nodes have to be lifted back to the original label space, in order to have a valid supergradient. If the optimal binary label of a node within this binary planar subproblem corresponds to the single label within the binary partition, then we have no problem. However, if the optimal label corresponds to the rest of the labels partition, then one of these labels is chosen at random and assigned as the optimal label according to the original label space. This could be a problem, when the total number of labels increases. [START_REF] Yarkony | Tightening mrf relaxations with planar subproblems[END_REF] has shown results with problems involving upto 3 labels per node. Nevertheless, this work is an innovative approach that could spark some stronger approach in the future.

Similar to clusters, cycle based ideas could be applied to several datasets like stereo, segmentation etc [START_REF] Kappes | A comparative study of modern inference techniques for structured discrete energy minimization problems[END_REF]. In the case of cluster based approaches, the algorithms could work with a dictionary of small-sized clusters, like triplets. For cycle based approaches, it is more involved to define the set of cycles to consider. For example, a small cycle made of three nodes could as well be treated as a cluster [START_REF] Sontag | Efficiently searching for frustrated cycles in map inference[END_REF]. There are certain sparse graphs like those that model a social network or the web graph, where cycle based approaches stand out [START_REF] Sontag | Efficiently searching for frustrated cycles in map inference[END_REF].

Tighter subgraph decompositions

So far, we have come across a data structure called a cluster. In the broadest sense, any subgraph could be a cluster. Usually, in the context of tighter relaxation, a cluster is formed as the union of cliques. Such clusters are directly related to relaxation hierarchies like Sherali-Adams. A cycle is also a cluster, with more special structure, which could be exploited for more efficient algorithms. Also, working with subgraphs in the form of cycles throughs light on the concept of frustrated cycles, which one will come across in loose relaxations. There are other subgraphs with special structure, too, which will lead to tighter relaxations and more efficient algorithms.

For a pairwise graphical model, one of the most general subgraphs that could lead to a tighter relaxation is a hypertree (Wainwright & Jordan 2008, §4). For example, if the original graph is a pairwise grid graph, the local polytope relaxation decomposes the graph according to trees of the graph (for e.g., row chains and column chains). Instead, we could treat each face of the grid as a hyperedge/clique of 4 nodes and decompose the graph according to hypertrees, which are row chains and column chains of the faces of the grid. This decomposition will be tighter than the local polytope for a pairwise graph. From an algorithmic point of view, say, we are using a supergradient method to optimize (9), then the challenge is to perform the minimization efficiently within each of these hypertrees. We will recall that this minimization w.r.t. a hypertree is equivalent to map inference w.r.t. a hypertree of the same topology, with suitably defined clique potentials. Over the years there have been algorithms for efficient map inference in a hypertree having cliques with special structures, like cardinality and order [START_REF] Tarlow | hop-map: Efficient message passing with high order potentials[END_REF], linear constraint nodes [START_REF] Potetz | Efficient belief propagation for higher-order cliques using linear constraint nodes[END_REF], matchings [START_REF] Duchi | Using combinatorial optimization within max-product belief propagation[END_REF] and sparse, pattern based potentials [START_REF] Komodakis | Beyond pairwise energies: Efficient optimization for higher-order mrfs[END_REF], [START_REF] Rother | Minimizing sparse higher order energy functions of discrete variables[END_REF]. Such specially structured clique potentials should be, and are often, leveraged to deal with higher-order structure in graphical models. Another interesting general approach for inference in trees is based on randomized algorithms [START_REF] Noorshams | Stochastic belief propagation: A low-complexity alternative to the sum-product algorithm[END_REF].

Going beyond trees, [START_REF] Batra | Beyond trees: Mrf inference via outer-planar decomposition[END_REF] decomposes the graph according to subgraphs that are outer-planar graphs. An outer-planar graph could be drawn as a planar graph such that no node is completely surrounded by edges. Another definition is that if a graph is formed from an outer-planar graph by adding an extra node and edges from that additional node to all other nodes, then that graph will be planar. [START_REF] Batra | Beyond trees: Mrf inference via outer-planar decomposition[END_REF] point out that outer-planar graphs have treewidth of 2 and could be solved by the junction tree algorithm in general. Note that treewidth of 2 means O(ml 3 ) complexity for the junction tree algorithm, where m is the number of nodes in the subgraph. This complexity could be prohibitive. For example, we saw similar complexity for inference in cycles (3.2) and discussed a more efficient approach. In the case of outer-planar graphs, [START_REF] Batra | Beyond trees: Mrf inference via outer-planar decomposition[END_REF] use the efficient planar Ising model solver of [START_REF] Schraudolph | Efficient exact inference in planar ising models[END_REF], whenever it is suitable. In this context, we would like to point out the work of [START_REF] Zheng | Map-mrf inference based on extended junction tree representation[END_REF], which also works with subgraphs of treewidth 2. They present an extended junction tree representation to solve such subgraphs.

Finally, one could decompose the graph according to subgraphs that are k-fans. In a graph with a k-fan structure, there are k inner nodes which are fully connected with each other. The rest of the nodes have edges to these k inner nodes only, not to each other. Suppose a k-fan subgraph has m nodes, the junction tree algorithm has complexity O((m -k)l k+1 ). For k-fans, [START_REF] Bergtholdt | A study of parts-based object class detection using complete graphs[END_REF], [START_REF] Kappes | Mrf inference by k-fan decomposition and tight lagrangian relaxation[END_REF] work with a search based inference algorithm that performs faster on average, even though it has the same worst complexity. This k-fan based model is especially suited for problems with dense graphs like deformable parts based object localization.

Global higher-order cliques

Higher-order cliques come in different special forms. Usually, the special structure is exploited for efficiently optimizing the subproblems in dual decomposition or for efficient min-marginal computation. We came across some special clique potentials in the previous section. Apart from the nature of the clique potential, a higher-order clique is also characterized by its size. A special situation is a higher-order clique which involves all the nodes of the graph, i.e., it is a global higher-order clique. We will come across such cliques in applications like enforcing global cardinality constraint [START_REF] Li | High order regularization for semi-supervised learning of structured output problems[END_REF] for foreground/background segmentation, diverse M-best map estimation [START_REF] Batra | Diverse m-best solutions in markov random fields[END_REF], average-cut in image segmentation [START_REF] Mezuman | Globally optimizing graph partitioning problems using message passing[END_REF]. In such problems, apart from potentials corresponding to nodes and small cliques, we have a global clique, which we will denote as θ α (x). For such a problem, the lp relaxation takes the following form,

minimize φ i xi θ i (x i )φ i (x i ) + c xc θ c (x c )φ c (x c ) + x θ α (x)φ α (x) (20a)
subject to

x c\i φ c (x c ) = φ i (x i ), ∀(i, c) : i ∈ c x\xc φ α (x) = φ c (x c ), ∀c ∈ C (20b) xi φ i (x i ) = 1, φ i (x i ) ≥ 0 ∀i ∈ V xc φ c (x c ) = 1, φ c (x c ) ≥ 0 ∀c ∈ C x φ α (x) = 1, φ α (x) ≥ 0. ( 20c
)
The presence of the marginalization constraints allows us to write the same problem in the following simpler form, minimize

φ x i θ i (x i ) + c θ c (x c ) + θ α (x) φ α (x) subject to x φ α (x) = 1, φ α (x) ≥ 0. (21)
Mezuman et al. (2013) show that this problem is tight. For their proof, they use the form given in (21). In this form, the objective is linear with respect to the φ α (x)'s and the constraint is a simplex constraint over all φ α (x)'s. Under such a simplex constraint, the optimal solution is to assign the value 1 entirely to that global labelling x that minimizes the objective in (21). Thus, we obtain the exact global labelling and the lp relaxation is tight.

As expected, solving (20) is intractable. This is because the marginalization constraint

x\xc φ α (x) = φ c (x c
) is enforced with respect to all the smaller cliques, i.e., ∀c ∈ C. [START_REF] Mezuman | Tighter linear program relaxations for high order graphical models[END_REF] try for a more tractable relaxation, which is still reasonably tight, by choosing a smaller set of the smaller cliques S and by enforcing the marginalization constraint with respect to φ α (x) in the following way, [START_REF] Mezuman | Tighter linear program relaxations for high order graphical models[END_REF] show that if S forms a low treewidth subgraph, the marginalization in ( 22) could be performed efficiently for special types of global potentials like cardinality based potential [START_REF] Tarlow | hop-map: Efficient message passing with high order potentials[END_REF] and sparse, pattern based potential [START_REF] Komodakis | Beyond pairwise energies: Efficient optimization for higher-order mrfs[END_REF], [START_REF] Rother | Minimizing sparse higher order energy functions of discrete variables[END_REF]. They also show a way to iteratively build this set S. Suppose, for a given S, the algorithm has run to optimality and for some clique c / ∈ S, the optimal labelling of those nodes w.r.t. the small clique θ c and w.r.t. the global clique θ α disagree, then adding c to S will lead to a tighter relaxation. Thus, the set S is grown step-by-step upto a maximum tractable size, where in each step the problem is run to optimality under marginalization constraints [START_REF] Blake | Markov random fields for vision and image processing[END_REF] defined by that S.

x\xi φ α (x) = φ i (x i ), ∀i ∈ V -V(S) x\xc φ α (x) = φ c (x c ), ∀c ∈ S. (22)
By this stage, we have seen several algorithms that lead to a tighter lp relaxation. Some of these approaches are quite general, while some exploit special structure in the problem. We have also been exposed to fundamental concepts like the marginal and local polytopes, dual decomposition and frustrated cycles. It is time to broaden our understanding of continuous relaxations for map inference by discussing about semidefinite programming based relaxations.

Semidefinite programming based relaxation

Generally, a continuous relaxation for the map inference problem takes the form of an lp or a qp or an sdp or an socp. Among these relaxations, [START_REF] Kumar | An analysis of convex relaxations for map estimation of discrete mrfs[END_REF] showed that the lp relaxation formulation dominates a large class of qp and socp relaxations. Thus, there has been tremendous research focus on the lp relaxation and rightly so. As far as the sdp relaxation is concerned, the comparison with respect to the lp relaxation is more involved. We have seen that the lp relaxation could be tightened based on the Sherali-Adams hierarchy. Similarly, the sdp relaxation could be tightened based on the sum-of-squares or the Lasserre hierarchy [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF][START_REF] Parrilo | Semidefinite programming relaxations for semialgebraic problems[END_REF]. (Wainwright & Jordan 2008, §9.3) has pointed out that at a given level of their respective hierarchies, the lp and sdp relaxations are mutually incomparable, i.e., they are neither equivalent nor one strictly dominates the other. Thus, there will be problem instances where the sdp relaxation could indeed provide a tighter relaxation than the lp relaxation. However, sdp relaxations have been less attractive because solving an sdp is computationally intensive. An sdp involves a matrix as the decision variable. Therefore, the main challenge with solving sdps is the heavy computational cost associated with linear algebraic (like, singular value decomposition (svd)) involving that matrix decision variable.

In order to understand these computational challenges, we will first derive the general sdp relaxation for map inference. This could be derived from the qp relaxation for (2) . Suppose, we have a pairwise graph G = (V, E), with n nodes and l labels per node. The qp relaxation takes the following form,

minimize φ i∈V xi θ i (x i )φ i (x i ) + i,j∈E xi,xj θ ij (x i , x j )φ i (x i )φ j (x j ) (23a) subject to xi φ i (x i ) = 1, φ i (x i ) ∈ [0, 1] ∀i ∈ V. ( 23b
)
In the above formulation, if φ i (x i ) ∈ {0, 1} then we obtain an ilp that is equivalent to the one given in (3). In other words, the qp relaxation is obtained from an ilp formulation of ( 2), which involves only node based variables φ i (x i ). On the other hand, the ilp in (3) involves clique based variables φ c (x c ), also. The reduction in the size of the decision variables comes with a price. The qp relaxation is non-convex. However, a remarkable property of the qp relaxation is that even though it is intractable, it is tight [START_REF] Ravikumar | Quadratic programming relaxations for metric labeling and markov random field map estimation[END_REF].

In other words, if the global optimum of the qp relaxation could be obtained, it will be the map labelling that we are seeking. However, direct attempts to solve this non-convex problem have shown poor empirical performance in terms of tighter results. We could define a symmetric matrix variable Φ ∈ S nl×nl , such that Φ = φφ . Here, phi is obtained by stacking the variables, φ i (x i ), across all nodes i and labels x i . In other words, an element of Φ is of the form, Φ(i; x i , j; x j ) = φ i (x i )φ j (x j ). We note that Φ has elements for all pairs of nodes, not just the edges of the graph. Thus, the problem in (23) could be rewritten as follows,

minimize φ, Φ i xi θ i (x i )φ i (x i ) + i,j xi,xj θ ij (x i , x j )Φ(i; x i , j; x j ) (24a) subject to xi φ i (x i ) = 1, φ i (x i ) ∈ [0, 1] ∀i ∈ V (24b) Φ = φφ . (24c)
It is still the same intractable but tight relaxation of the map inference problem, as (23).

There is yet another way to represent this intractable problem, through a positive semidefinite constraint combined with a rank-1 constraint. It takes the following form,

minimize φ, Φ i xi θ i (x i )φ i (x i ) + i,j xi,xj θ ij (x i , x j )Φ(i; x i , j; x j ) (25a) subject to xi φ i (x i ) = 1, φ i (x i ) ∈ [0, 1] ∀i ∈ V (25b) 1 φ φ Φ 0 (25c) rank 1 φ φ Φ = 1 (25d) Φ(i; x i , i; x i ) = φ i (x i ) ∀i ∈ V. (25e)
We repeat that the problems ( 23), ( 24) and ( 25) are equivalent. We will look further into the motivation behind the formulation of the constraints in [START_REF] Braverman | The grothendieck constant is strictly smaller than krivine's bound[END_REF]. First, we will see how the constraint Φ = φφ in ( 24) is equivalently represented by ( 25c) and (25d). In sdp relaxation literature, the presence of the equality constraint Φ = φφ (24c) in the stricter problem, usually leads to the semidefinite constraint Φ -φφ 0 in the relaxation [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF]. Now, the following two inequalities are equivalent,

Φ -φφ 0 (26) M 1 φ φ Φ 0. ( 27
)
This equivalence is based on the Schur complement formula (Boyd & Vandenberghe 2004, §A.5.5). The semidefinite inequality (25c) along with the non-convex rank-1 constraint (25d) lead to an equivalent representation of Φ = φφ . The sdp relaxation is obtained by dropping this rank-1 constraint. Further, the constraint Φ(i;

x i , i; x i ) = φ i (x i ) is inspired by the original ilp formulation of the problem. According to (24c), Φ(i; x i , i; x i ) = φ i (x i ) 2 . If φ i (x i ) takes integral values, i.e., {0, 1}, then Φ(i; x i , i; x i ) = φ i (x i ) 2 = φ i (x i ).
This constraint tries to compensate for the removal of the rank-1 constraint by encouraging the desired structure in the output variables. Thus, the sdp relaxation for map inference takes the following form,

minimize φ, Φ i xi θ i (x i )φ i (x i ) + i,j xi,xj θ ij (x i , x j )Φ(i; x i , j; x j ) (28a) subject to xi φ i (x i ) = 1, φ i (x i ) ∈ [0, 1] ∀i ∈ V (28b) 1 φ φ Φ 0 (28c) Φ(i; x i , i; x i ) = φ i (x i ) ∀i ∈ V. (28d)
In the sdp relaxation, the elements of Φ are equivalent to pseudomarginals of pairs of nodes, φ ij (x i , x j ), that we came across in the local polytope. The matrix M (27) contains pseudomarginals corresponding to nodes and pairs of nodes and it is called the moment matrix Wainwright & Jordan (2004a). M is a square matrix of side, 1 + nl. Similar to the local polytope, L(G), the above constraints define a convex outer bound to the marginal polytope, M(G). We will denote it as SDP(G). Unlike, L(G), SDP(G) has a curved boundary. Note, in our formulation of the local polytope, we explicitly represented pseudomarginals only for pairs of nodes that correspond to the edges. However, it is possible to associate pseudomarginals with respect to all pairs of nodes and the sdp relaxation explicitly represents the pseudomarginals for all node pairs. The constraints (28c) and (28d) play a role similar to the marginalization constraints (5b) in the lp relaxation. Earlier we have seen that in the lp relaxation if the optimal variables are integer valued, we have obtained the exact map solution. Similarly, if the matrix M is of rank-1 in the sdp relaxation, we have obtained the exact map solution (Wang et al. 2016, Prop. 2). Despite the computational challenge involving the semidefinite constraint (28c), there have been several works in recent years that have explored sdp relaxations for map inference. For several of these methods, the main thrust has been the efficient low-rank Burer-Monteiro approach [START_REF] Burer | A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization[END_REF]. The Burer-Monteiro approach is an efficient way to solve semidefinite programs through a low-rank factorization based approximation of the matrix variable. Suppose, M is the matrix variable, it is substituted by Y Y everywhere in the problem formulation. We obtain an optimization problem with Y , which is of low-rank, as the decision variable. One of the motivating reasons for this approach is that if an sdp satisfies certain mild conditions, the rank of the optimal decision variable is bounded by √ 2 • #constraints [START_REF] Pataki | On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues[END_REF]. Thus the optimal decision variable is guaranteed to be of considerably low-rank for many practical sdp formulations. Further, even though the Burer-Monteiro approach is non-convex, for several problems the local minimum returned by the approach is also a global minimum or is within a bounded value from the global minimum. Over the years, there has been progress in characterizing conditions which lead to these guarantees [START_REF] Burer | Local minima and convergence in low-rank semidefinite programming[END_REF], [START_REF] Boumal | The non-convex burer-monteiro approach works on smooth semidefinite programs[END_REF], [START_REF] Mei | Solving sdps for synchronization and maxcut problems via the grothendieck inequality[END_REF], [START_REF] Boumal | Deterministic guarantees for burermonteiro factorizations of smooth semidefinite programs[END_REF].

Given a hierarchy of lp relaxations and a hierarchy of sdp relaxations, (Wainwright & Jordan 2008, §9.3) has shown that at any given level, the corresponding lp relaxation and the sdp relaxation are mutually incomparable. As mentioned earlier, this is an important motivation to pursue sdp relaxations. L(G) and SDP(G) are the lowest levels of the lp relaxation and the sdp relaxation hierarchies, respectively. Since, these two feasible regions are incomparable, for some problems L(G) could be tighter and for some others SDP(G) could be tighter. Thus, the intersection of L(G) and SDP(G) is a better bound on M(G) than either of them separately. [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF] has pursued this idea and presented a dual based algorithm. The variables φ and Φ are pseudomarginals or beliefs and we will denote them together as one large sized variable b. We could plug b within the lp relaxation objective (5a), which we will denote as F (b). Then, [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF] solves the following problem,

minimize b 1 ∈L(G),b 2 F (b 1 ) + 1 b 2 ∈ SDP(G) subject to b 1 = b 2 . (29)
In other words, the objective function in (5a) is minimized within the intersection of L(G) and SDP(G). The Lagrangian dual of this problem nicely decomposes according to b 1 and b 2 , as follows,

maximize δ min. b 1 ∈L(G) F (b 1 ) + δ b 1 + min. b 2 ∈SDP(G) -δ b 2 . ( 30
)
Thus, while maximizing the dual w.r.t. δ, the two subproblems could be minimized w.r.t. b 1 and b 2 separately. Since, the dual problem is non-smooth, the minimizing b 1 * of subproblem 1 and the minimizing b 2 * of subproblem 2, give us a valid supergradient (b 1 * -b 2 * ) to update the dual variable δ [START_REF] Komodakis | MRF energy minimization and beyond via dual decomposition[END_REF], Lemma 1). The first subproblem is equivalent to the lp relaxation ( 5) with an additional linear term in the objective. [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF] solves it using convex belief propagation [START_REF] Hazan | Convergent message-passing algorithms for inference over general graphs with convex free energies[END_REF].

The second subproblem is a semidefinite program, a linear objective with a semidefinite constraint. It involves the decision variable b 2 , composed of φ and Φ, which can be written as a moment matrix M , like we saw in (27). Taking inspiration from the Burer-Monteiro approach, [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF] replace M by the low-rank factorization Y Y , where Y ∈ R (1+nl)×r . Here, r is the low valued rank of Y and the moment matrix representing b 2 . Expecting the moment matrix in the sdp relaxation to be low-rank makes intuitive sense because we came across a rank-1 constraint in the intractable formulation given in [START_REF] Braverman | The grothendieck constant is strictly smaller than krivine's bound[END_REF]. Further, this low-rank representation ensures that the moment matrix that is implicitly computed as Y Y is positive semidefinite by definition. Thus, the semidefinite constraint M 0 in SDP(G) need not be explicitly enforced. This simplification afforded by the Burer-Monteiro approach appears repeatedly in sdp literature. The explicitly enforced constraints are (28d). Note that the constraints (28b) are also enforced in L(G) and they need not be part of the second subproblem. [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF] takes an augmented Lagrangian based approach to solve this subproblem. Generally, with the low-rank representation, the question of setting the rank r needs to be addressed. In [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF], r was set to various values and all the results are reported. r was at most 50, in their experiments.

Let us keep in mind that the decision variables of the sdp relaxation could either be represented as a moment matrix, M or explicitly through the parts, φ and Φ, which make up M . The underlying problem is the same in both cases. The constraints (28b), ( 28c) and (28d) could be expressed in a suitable manner in both cases. In case the decision variables are represented by the moment matrix, the constraint M (0, 0) = 1 should be explicitly enforced, also.

Intersecting L(G) with SDP(G) is one instance of a general way to get better results with the sdp relaxation. The general approach is about adding suitable linear equality and/or inequality constraints to the semidefinite program [START_REF] Hazan | Convergent message-passing algorithms for inference over general graphs with convex free energies[END_REF]. This idea has been explored since the early works studying the sdp relaxation Wainwright & Jordan (2004a). [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF] presents one other approach along these lines. It adds to the formulation in [START_REF] Hazan | Convergent message-passing algorithms for inference over general graphs with convex free energies[END_REF], the following non-negativity constraints on the matrix Φ,

Φ(i; x i , j; x j ) ≥ 0 ∀(i, j) ∈ E. (31)
Empirically, these inequality constraints improve the performance of sdp relaxations, when submodular edge potentials are present. We have mentioned earlier that submodular potentials are a type of attractive potentials. Also, [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF] has shown that the semidefinite constraint (28c) along with the linear constraints (28d) and (28b), implicitly ensure the satisfaction of the marginalization constraints (3b) that we come across in the lp relaxation. For their formulation, [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF] has shown an admm based approach [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]. The challenge with admm based algorithms is the task of proving convergence. [START_REF] Wen | Alternating direction augmented lagrangian methods for semidefinite programming[END_REF] has presented an admm based algorithm for solving semidefinite programs, where convergence is guaranteed only if equality constraints are present. Interestingly, the equality constraints and the inequality constraints in the sdp relaxation proposed by [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF] are decoupled. Specifically, the equality constraints concern the vector φ and the diagonal blocks of Φ, while the inequality constraints concern the edges of the graph, i.e., off-diagonal blocks of Φ. Hence, [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF] is able to prove convergence by using the same admm approach as [START_REF] Wen | Alternating direction augmented lagrangian methods for semidefinite programming[END_REF].

A big challenge with sdps is the memory intensive representation of the optimization variables. One needs to look for structure in the problem at hand, to reduce the number of variables. For example, [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF] has to deal with the primal decision variables, φ and Φ and the dual variables corresponding to the augmented Lagrangian. These dual variables correspond to the positive semidefinite constraint, the linear equality constraints and the linear inequality constraints. Interestingly, for their problem formulation, the matrix valued dual variable corresponding to the positive semidefinite constraint need not be explicitly represented. Since, it could be expressed in terms of the other dual variables and the primal variables. Still, the representation of the matrix Φ is a challenge. Similar to [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF], φ and Φ are represented in terms of a moment matrix M (27) and Burer-Monteiro is invoked to represent M through a low-rank factorization Y Y . In [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF], this low-rank representation led to the disappearance of the positive semidefinite constraint in the algorithm. However, in this case, one of the admm steps still involves projection of Y onto the positive semidefinite cone. However, Y is of rank r, only the top r eigenvalues and eigenvectors of an intermediate matrix needs to be computed using the Lanczos algorithm [START_REF] Golub | Matrix computations[END_REF]. The complexity of the Lanczos algorithm is governed by a matrix-vector multiplication operation, involving this intermediate matrix. Interestingly, the sparsity pattern of this matrix is driven by that of the graph G, which can be advantageous for sparse graphs like grid graphs. Apart from these aspects, there is ample scope to parallelize this matrix-vector product. Similar to [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF], setting the rank parameter r is an open question. [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF] proposes to solve the problem to optimality repeatedly, doubling the value of r each time. The quality of the solution could be assessed based on the primal-dual gap of the original integral problem and the relaxed dual problem. Also, as the algorithm proceeds, the label for some of the nodes are fixed according to a reliability criterion. The label of a node is fixed if φ i (x i ) is greater than a high threshold, like 0.99 or if φ i (x i ) is the maximum ∀i and ∀x i . This heuristic improves the scalability of the algorithm.

Upon closer observation, one could notice that [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF] and [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF] are essentially having the same set of constraints. Both enforce the normalization and marginalization constraints of the lp relaxation and the constraints corresponding to the sdp relaxation. However, in the case of [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF] the marginalization constraints of the lp relaxation are enforced implicitly through other constraints. This enabled them to approach the optimization with a different algorithmic approach. Even though [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF] prove the convergence of their admm scheme when the moment matrix M is considered explicitly, they don't prove convergence when it is represented through the low-rank factorization, Y Y . However, they report good empirical performance for the latter approach for various datasets.

So far, we have been seeing a way to tighten the sdp relaxation by adding linear constraints inspired by the lp relaxation. In the context of the lp relaxation, we saw that it could be increasingly tightened by a hierarchy of problems, called the Sherali-Adams hierarchy. A similar hierarchy exists for the sdp relaxation called the sum-of-squares or the Lasserre hierarchy [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF][START_REF] Parrilo | Semidefinite programming relaxations for semialgebraic problems[END_REF]. Earlier we saw that even though, in theory, a given level of the Sherali-Adams hierarchy will involve all possible subsets of a given size, in practice, one could work with a smaller set of subsets like triplets or the faces of a grid. A similar idea to tighten the sdp relaxation in an efficient manner has been presented by [START_REF] Erdogdu | Inference in graphical models via semidefinite programming hierarchies[END_REF]. To understand their approach, we will look at a general way to characterize the moment matrix, M . The following equations hold for the case, where the nodes are binary valued and take values 1 or -1. It is possible to extend them to the multi-label case based on larger moment matrices. In (27), the moment matrix carried the unary and pairwise pseudomarginals. In general, it could carry higher-order terms that will lead to a tighter relaxation Wainwright & Jordan (2004a). In more detail, given an even number d, we will consider all possible node subsets of size up to d 2 , this included the null-set (∅). We will have n ≤ d 2 such subsets. Thus, M is a square matrix of side n ≤ d

2

. We see that the moment matrix grows exponentially in the size of d. The elements of M are indexed according to pairs of subsets of the nodes. Suppose, S and T are two such subsets, then, we index the corresponding element of M as M (S, T ). The moment matrix M is desired to be a symmetric matrix. This constraints the elements of M to be a function of S∆T only, where, ∆ denotes the symmetric difference between two sets. The symmetry requirement can be expressed as follows,

S 1 ∆T 1 = S 2 ∆T 2 ⇒ M (S 1 , T 1 ) = M (S 2 , T 2 ) ∀S 1 , T 1 , S 2 , T 2 ⊆ V : |S 1 |, |T 1 |, |S 2 |, |T 2 | ≤ d 2 . ( 32
)
The moment matrix that we saw in (27) corresponds to the case of d = 2. In that case, we can see how the elements of φ and Φ are indexed by (S, T ), where S, T ∈ ∅ ∪ V. [START_REF] Erdogdu | Inference in graphical models via semidefinite programming hierarchies[END_REF] works with the case d = 4 and enforces the constraints on the elements of M dictated by (32). They achieve an efficient algorithm by invoking Burer-Monteiro and represent M through a low-rank factorization. They represent each row of the low-rank matrix as a vector σ S ∈ R r , where S ⊆ V : |S| ≤ 2. Thus, there will be n ≤ 2 such vectors.

We will denote the set of node subsets as S and it will be made of nodes and pairs of nodes.

We will see soon about the effect of the vector length r on the quality of the optimization result. Thus, we could express the constraints on the moment matrix M in terms of these vectors, as follows,

σ i = 1 ∀i ∈ S (33a) σ i • σ j = σ ij • σ ∅ ∀i, j ∈ S (33b)
σ i • σ ij = σ j • σ ∅ ∀i, j ∈ S (33c)
σ i • σ jk = σ k • σ ij ∀i, j, k ∈ S (33d)
σ ij • σ jk = σ ik • σ ∅ ∀i, j, k ∈ S (33e)
σ ij • σ kl = σ ik • σ jl ∀i, j, k, l ∈ S (33f)
where . • . is the dot product operation and i, j, k, l ∈ V. The constraint (33a) is a constraint on the diagonal elements of M , which are all a function of the null-set (∅). Similar to the ilp inspired constraint (28d), the diagonal elements of M are constrained to take the value 1, since, the nodes take labels in {-1, 1}. Note that the above equations are for the case of d = 4, when nodes take binary labels. When the same Burer-Monteiro approach is used for d = 2 with binary valued nodes, we will only have the constraint (33a), just like we saw in the case of [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF].

We would like to point out that the sets of nodes that are associated with the moment matrix, carry a similar meaning to clusters, which we came across in the lp relaxation. For example, if we are tightening the lp relaxation, we will be working with pseudomarginals corresponding to nodes, pairs of nodes, triplets of nodes etc. In an sdp (sum-of-squares) relaxation, we will have a moment matrix with elements corresponding to nodes, pairs of nodes, triplets of nodes, quadruplets of nodes etc. If we consider only upto quadruplets of nodes, we will denote the relaxation as sos(4). We can see that sos(2), leads to a moment matrix with elements corresponding to nodes and pairs of nodes. This is what we saw in [START_REF] Hazan | Convergent message-passing algorithms for inference over general graphs with convex free energies[END_REF]. Also, sos(2) corresponds to the pioneering sdp relaxation work of [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF]. It will be a good exercise to verify the structure of the moment matrix for sos (2) and sos(4).

The set of vectors σ S satisfying the constraints in ( 33) is denoted as Ω(S). Thus, the sos(4) sdp relaxation for a binary valued pairwise graph takes the following form,

minimize σ S ,S∈S (i,j)∈E θ ij σ i • σ j + i∈V θ i σ i • σ ∅ (34a)
subject to σ S ∈ Ω(S) ∀S ∈ S : |S| ≤ 2.

(34b)

The set S is very big. Even when d = 4, it is of size n ≤ 2 , i.e., we are considering all subsets S : |S| ≤ 2. This is because we are considering all possible pairs of nodes. Just like we did in lp relaxation, while considering clusters, we could restrict the pairs of nodes that we consider. We could divide the graph into triplets of adjacent nodes. We can always create triplets by introducing edges with zero potential and we require these triplets to cover all the nodes and edges of the original graph. We will define a σ S , only if S, which is size 1 or 2, is contained in one of the triplets. We will call this restricted set as Ŝ. [START_REF] Erdogdu | Inference in graphical models via semidefinite programming hierarchies[END_REF] attempts to solve the following more tractable problem,

minimize σ S ,S∈ Ŝ (i,j)∈E θ ij σ i • σ j + i∈V θ i σ i • σ ∅ (35a) subject to σ S ∈ Ω( Ŝ) ∀S ∈ Ŝ : |S| ≤ 2. ( 35b
)
We will now see more about the effect of the low-rank parameter r, which is the length of the vectors, σ S . If r = n ≤ d

2

, then the sdp relaxation is convex. However, we could set r to low values and get acceptable results, while improving the memory footprint. [START_REF] Erdogdu | Inference in graphical models via semidefinite programming hierarchies[END_REF] have obtained good results in their experiments when r = 10. [START_REF] Erdogdu | Inference in graphical models via semidefinite programming hierarchies[END_REF] optimizes the resulting non-convex version of ( 35) by constructing an augmented Lagrangian, where only constraint (33a) is explicitly retained. This augmented Lagrangian is optimized in a coordinate descent fashion, where each time the minimization is with respect to one vector σ S . Once, optimality is reached, some of the nodes are assigned a label of 1 or -1 based on a rounding scheme that we will describe in section (5.1). Based on this, the σ S vectors are fixed as x * i σ ∅ for those particular nodes and x * i x * j σ ∅ for edges between such nodes. Then, ( 35) is again optimized with respect to the remaining σ S vectors. This process is repeated until all nodes are reliably labelled. We have seen similar shrinking of problem size in [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF].

There have been a few efforts to understand the Burer-Monteiro approach in the context of map inference. [START_REF] Frostig | Simple map inference via low-rank relaxations[END_REF] has presented an analysis of the following setting: sos(2) sdp relaxation of the binary pairwise graph. In other words, optimizing [START_REF] Hazan | Convergent message-passing algorithms for inference over general graphs with convex free energies[END_REF] over SDP(G {0,1} ). In this setting, they are able to prove that the output of the non-convex problem saturates for a low value of the rank r. Thus, it is possible to ensure that the non-convex Burer-Monteiro approach matches the convex sdp relaxation with a reasonably small rank r. Another work [START_REF] Mei | Solving sdps for synchronization and maxcut problems via the grothendieck inequality[END_REF] analysing sos (2), has shown that it is possible to achieve O( 1 r ) relative error with respect to the global optimum for specific choices of the node and edge potentials. Generally, sdp relaxations become more useful with the addition of more linear constraints, either borrowed from lp relaxation or by going up the sos hierarchy. It will be interesting to analyse the Burer-Monteiro approximation in more involved settings.

So far, we have been looking at how Burer-Monteiro based low-rank approximation leads to scalable sdp algorithms. We will now see another algorithmic approach to achieve a scalable sdp algorithm that is suitable for tighter map inference. We will look into the dual based approach called sdcut. It is an algorithm presented by Wang et al. (2013) to solve an sdp relaxation for binary quadratic programs (bqps). A bqp is a special case of the quadratic programming problem in (24), where nodes take only binary labels. Their approach, which is called sdcut, could be extended to multi-label nodes and thus used for map inference, as they show in [START_REF] Wang | Efficient sdp inference for fully-connected crfs based on low-rank decomposition[END_REF][START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF]. The advantages of this approach are its scalability and flexibility to accommodate additional linear inequality constraints to tighten the relaxation optimization community, while studying the polyhedral nature of graphs with binary variables (G {0,1} ) Schrijver ( 2003), [START_REF] Deza | Geometry of cuts and metrics[END_REF]. The cycle inequalities that we came across earlier ( 6) is an example of constraints that could be enforced on a graph with binary variables. [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF] has considered these cycle inequalities and also, triangular and odd-wheel inequalties. Consider, three nodes i, j, k and let δ i,j 1[x i = x j ] indicate whether two nodes disagree in their labelling, then the triangle inequalities take the following form,

δ i,j + δ j,k + δ k,i ≤ 2 δ i,j -δ j,k -δ k,i ≤ 0 -δ i,j + δ j,k -δ k,i ≤ 0 -δ i,j -δ j,k + δ k,i ≤ 0. (39)
Just like a cycle inequality, an odd-wheel inequality is defined on a cycle C with odd length of at least 3. These, inequalities take the following form,

(i,j)∈C δ i,j - i∈V(C) δ i,k ≤ |C| -1 2 ( 40
)
where k is a node of the graph that is not in C but encircled by it. Like cycle inequalities, there are an exponential number of odd-wheel inequalities. Also, similar, to cycle inequalities there is a polynomial time separation algorithm for finding the cycle that most violate the odd-wheel inequality [START_REF] Deza | Geometry of cuts and metrics[END_REF]. Thus, [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF] has presented a tighter map inference algorithm based on the dual given in (37a), along with suitable linear equality and inequality constraints. One of the issues to address is making this approach work for a graph with multi-label nodes. [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF] finds a solution by constructing the l-projection graph [START_REF] Sontag | New outer bounds on the marginal polytope[END_REF] that we saw in section (1.1) and by considering the above constraints w.r.t. that graph. However, this leads to another issue to be addressed. It is the huge problem size that happens with large graphs and nodes with multiple labels. They take a branch and bound approach to reduce the set of active labels for each node [START_REF] Sun | Efficient and exact map-mrf inference using branch and bound[END_REF]. Also, the huge number of constraints are handled in a cutting-planes framework. Thus, the dual problem is solved several times in this framework, where the label space is pruned each time, by updating lower and upper bounds for each node. The overall algorithm stops when these bounds are sufficiently close for all nodes.

To further improve the scalability, [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF] removes nodes based on persistency of a node label with respect to the optimal labelling. There have been several works regarding persistency in mrf inference [START_REF] Kovtun | Partial optimal labeling search for a np-hard subclass of (max,+) problems[END_REF], [START_REF] Kohli | On partial optimality in multi-label mrfs[END_REF], [START_REF] Swoboda | Partial optimality by pruning for map-inference with general graphical models[END_REF]. Even though, obtaining the optimal labelling of all the nodes is an NP-hard problem, it is possible to identify whether a node has attained its optimal label or not. If it is true, we say this node has attained its persistent label. With this guarantee, it is possible to reduce the problem size and repeat the inference algorithm for the remaining nodes. Through this process, it is possible to obtain better overall labelling. Among various approaches, there is an algorithm that is referred to as qpbo (Blake et al. 2011, §2.3). It works with binary valued graphs and assigns labels that are one of {0, 0.5, 1}. Whenever, a node receives an integral label, it is guaranteed to be its optimal label. [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF] has chosen qpbo based on its simplicity and efficiency.

The third important issue to be addressed, is an efficient way to handle the various linear equality and inequality constraints. This step is the most important from a tighter relaxation point of view. Some of the constraints are limited in total number and the violated ones are found by enumeration. This is applicable to non-negativity [START_REF] Mcauley | Faster algorithms for max-product message-passing[END_REF], marginalization (3b) and triangle inequality (39) constraints. Cycle inequalities are added based on the seperation algorithm given in [START_REF] Deza | Geometry of cuts and metrics[END_REF]. If no violated cycle inequalities are present, then the algorithm searches for violated odd-wheel inequalities. The separation algorithm for the latter is also described in [START_REF] Deza | Geometry of cuts and metrics[END_REF]. Each added constraint corresponds to a new dual variable and it is important to control the problem size. Thus, it is important to remove inactive constraints. The heuristic used by [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF] is to remove constraints which are satisfied by the current primal variables and whose dual variables are zero. We would like to point out that [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF] has shown how the marginalization constraints are implicitly enforced by the semidefinite constraint along with the normalization and non-negativity constraints. Even though [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF] works with a perturbed problem, this condition will hold with more guarantee as the algorithm reaches the optimum. Thus, marginalization constraints need not be considered at later stages of the algorithm.

Rounding schemes for sdp relaxation

sdp relaxations have a rich array of rounding schemes to obtain integral labels for the nodes of the graph [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF], [START_REF] Chazelle | A semidefinite programming approach to side chain positioning with new rounding strategies[END_REF], [START_REF] Charikar | Near-optimal algorithms for maximum constraint satisfaction problems[END_REF][START_REF] Raghavendra | Generic techniques to round sdp relaxations[END_REF]. Some sdp relaxation algorithms are designed such that we obtain pseudomarginals for the nodes [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF], [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF], [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF]. Then, we could assign a label to the node by sampling according to the probability distribution defined by the pseudomarginals. In fact, this is one of the possible rounding schemes for lp relaxations working with pseudomarginals [START_REF] Ravikumar | Message-passing for graphstructured linear programs: Proximal methods and rounding schemes[END_REF]. This naive randomized scheme works better when the distribution of the graphical model is more concentrated.

Several rounding schemes are based on low-rank representation of the moment matrix, i.e., M = Y Y , where Y is of rank r. So far, we have come across two kinds of node labels: binary ({1, -1}) or multi-label. For binary labels only one row of Y is needed per node. For the multi-label case, one row of Y is needed for each node and each label. While discussing the work of [START_REF] Erdogdu | Inference in graphical models via semidefinite programming hierarchies[END_REF], we used σ i;xi to denote the row of Y corresponding to node i and label x i . We could design rounding schemes based on projecting σ i;xi onto a suitable vector. For some of the rounding schemes, we also need the vector σ ∅ that corresponds to the first row of Y .

First, we will discuss some rounding schemes for binary valued nodes. The seminal work [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF] proposed to draw a random vector w ∈ R 1×r such that w = 1 and assigns to node i the label sign(σ i • w). This is called the random hyperplane rounding scheme. Shifted random projection rounding extends this idea further and has proved to be a necessary step within approximation algorithms for max-2sat [START_REF] Charikar | Near-optimal algorithms for maximum constraint satisfaction problems[END_REF]. [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF] has shown results based on this scheme. A perturbation vector p ∈ R 1×r is constructed with i.i.d. normally distributed elements. Then node i is assigned the label sign(σ i • ((1 -β)σ ∅ + βp). We should refer [START_REF] Charikar | Near-optimal algorithms for maximum constraint satisfaction problems[END_REF] about setting β to a value between 0 and 1. Note that σ ∅ itself is of unit length. So, there are rounding schemes that work with σ ∅ , instead of generating a random vector w of unit length. [START_REF] Erdogdu | Inference in graphical models via semidefinite programming hierarchies[END_REF] also works with σ ∅ and it fixes the label of a node as sign(σ i • σ ∅ ), if |σ i • σ ∅ | exceeds a confidence threshold. We saw that [START_REF] Erdogdu | Inference in graphical models via semidefinite programming hierarchies[END_REF] optimizes (35) several times, each time with a smaller set of σ S vectors. Suppose there is an outer iteration, where no node exceeds the confidence threshold, then the nodes with the highest |σ i • σ ∅ | value are picked for pruning. [START_REF] Erdogdu | Inference in graphical models via semidefinite programming hierarchies[END_REF] presented their work for nodes taking binary labels but these rounding schemes could be extended to multi-label nodes. For example, we could assign the node i the label x i that maximizes |σ i;xi • σ ∅ | or that maximizes |σ i;xi • ((1 -β)σ ∅ + βp)|. Also, there are other advanced rounding schemes, like those based on Grothendieck's inequality [START_REF] Braverman | The grothendieck constant is strictly smaller than krivine's bound[END_REF] which we will not discuss here.

Problems where sdp relaxation has helped

We will discuss problem instances where sdp relaxation based algorithms lead to better map labelling. Usually, these algorithms achieve a tighter relaxation by moving up the Lasserre/sos hierarchy or by adding constraints that tighten the lp relaxation like cycle or cluster based constraints. [START_REF] Wang | Efficient sdp inference for fully-connected crfs based on low-rank decomposition[END_REF][START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF] have shown that sdp relaxation based methods perform better for densely connected graphs with weak unary potentials and for graphs that have a large fraction of non-submodular (also, called non-attractive) pairwise potentials. [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF] was able to perform better than daoopt [START_REF] Otten | Anytime and/or depth-first search for combinatorial optimization[END_REF] in a problem with a fully connected graph and no unaries from the Probabilistic Inference Challenge, 2011 pic (2011). daoopt was a top performer in pic-2011. [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF] has also observed that their method performs well on dense problems from pic-2011. They were able to do better that ficolofo [START_REF] Cooper | Soft arc consistency revisited[END_REF], a top performer with dense problems in pic-2011. [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF] has also observed that problems where edge potentials are strong are solved better by their approach. Also, when the edge potentials are not so strong, they observed that the cluster based tightening of lp relaxation by [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF] performed better. It is readily possible to define a feasible set that is the intersection of the sdp relaxation with the cluster based tighter lp relaxation that we saw in section (2). To achieve this one could use the optimization scheme given in [START_REF] Sontag | Tightening lp relaxations for map using message passing[END_REF] instead of convex belief propagation to solve the subproblem within the dual optimization scheme of [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF].

Scalable and efficient sdp algorithms for map inference are still evolving. The four main algorithms that we have discussed [START_REF] Peng | Approximate inference by intersecting semidefinite bound and local polytope[END_REF], [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF], [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF], [START_REF] Erdogdu | Inference in graphical models via semidefinite programming hierarchies[END_REF] are good starting points to further explore this topic. At this moment, we would like to point out one particular area of research: the intersection between spectral graph theory and semidefinite programming. For the map labelling problems discussed so far, we could explore algorithms based on spectral methods [START_REF] Cour | Solving markov random fields with spectral relaxation[END_REF], [START_REF] Olsson | Solving large scale binary quadratic problems: Spectral methods vs. semidefinite programming[END_REF]. Even though spectral methods are computationally more efficient, the optimum of the sdp relaxation can be characterized better. There have been attempts to combine the advantages of the two methods and it is an active area of research in combinatorial optimization [START_REF] Kolla | Merging Techniques for Combinatorial Optimization: Spectral Graph Theory and Semidefinite Programming[END_REF], icerm (2014), Simons Institute (2017).

Characterizing Tight Relaxations

In section (4), we came across particular graph topologies and clique potentials, which by themselves or in combination lead to exact map inference. It will be interesting to understand more general settings. Especially, settings where the relaxation tightening algorithms that we have discussed, will lead to exact map inference.

So far, we have been discussing about various ways to tighten lp and sdp relaxations. The Sherali-Adams hierarchy and the Lasserre hierarchy provide a guaranteed approach to tighten the lp relaxation and the sdp relaxation, respectively. There have been efforts to characterize graph topologies and/or clique potentials that could be solved exactly with schemes that are at lower levels of these hierarchies. However, these hierarchies are computationally heavy even at the lower levels and they are enforced only partially. Surprisingly, there are many problem instances which are solved exactly with such partial schemes.

In the Sherali-Adams hierarchy, a level r corresponds to enforcing the marginalization constraint (5b) over all clusters of variables of size ≤ r and we will denote the resulting polytope as SA r (G). The local polytope, L(G) is related to SA 2 (G). Even though, L(G) enforces marginalization constraints only on edges of the graph and not on all possible pairs of nodes, it can be shown to be exactly equivalent to SA 2 (G) (Rowland et al. 2017, §3.3). [START_REF] Rowland | Conditions beyond treewidth for tightness of higher-order lp relaxations[END_REF] have shown a similar result for SA 3 (G): the polytope obtained by considering the marginalization constraints of L(G) together with the marginalization constraints of triplets obtained by triangulating the graph, is equivalent to SA 3 (G).

Further, it is desirable to characterize the tightness of SA r (G) for various values of r. Initially, there were efforts to study conditions for tightness based on the graph topology. [START_REF] Wainwright | Treewidth-based conditions for exactness of the sherali-adams and lasserre relaxations[END_REF] proved that a sufficient condition for SA r (G) to be tight is to have a graph with treewidth ≤ r -1. We can immediately see that L(G) is tight for trees. Since, trees have treewidth 1. [START_REF] Chandrasekaran | Complexity of inference in graphical models[END_REF] proved that in the more difficult problem of inferring the marginal probabilities, if there are no restrictions on the clique potentials, then bounded treewidth is necessary for tractability. Similar studies focusing on clique potentials have also been pursued. [START_REF] Thapper | The complexity of finite-valued csps[END_REF] showed that for a given family of potentials (finite multi-label nodes and any clique size), either L(G) is tight, i.e., all such problems are tractable irrespective of the graph topology or the problem set is np-hard. Tractability for graphical models containing only submodular clique potentials is a result that fits in this line of work.

In recent years, settings combining restrictions on graph topology and clique potentials have been studied [START_REF] Weller | Tightness of lp relaxations for almost balanced models[END_REF], [START_REF] Rowland | Conditions beyond treewidth for tightness of higher-order lp relaxations[END_REF]. [START_REF] Rowland | Conditions beyond treewidth for tightness of higher-order lp relaxations[END_REF] and related works have considered binary pairwise models in their analysis. In this setting, every graph is associated with a signed graph of the same topology, where an edge is considered even if it is attractive and it is odd if it is not attractive. A balanced graph is one that could be partitioned into two exhaustive sets, such that all edges with both endpoints within any one set are even and edges with one endpoint in each set is odd. In other words, any cycle in a balanced graph, will have an even number of odd edges. Thus, a balanced graph does not have frustrated cycles. Many results that are satisfied by models with attractive potentials may be proven for balanced models, which form a wider class. An almost balanced graph contains no frustrated cycles except through one privileged node, s. Thus, removing that node makes the remaining graph balanced. Note, it is possible to efficiently test whether a graph is almost balanced. [START_REF] Weller | Tightness of lp relaxations for almost balanced models[END_REF][START_REF] Rowland | Conditions beyond treewidth for tightness of higher-order lp relaxations[END_REF] have shown that for balanced graphs, SA 3 (G) as defined in the above more compact manner is sufficient to achieve a tight relaxation. This is useful for applications like foreground/background subtraction, which involve binary labels and the foreground and background form the two sets of the balanced graph. For an almost balanced graph, we could define a polytope SA s 3 (G): the polytope obtained by considering the marginalization constraints of L(G) together with the marginalization constraints over only triplets which contain s, the privileged node. [START_REF] Rowland | Conditions beyond treewidth for tightness of higher-order lp relaxations[END_REF] has shown that SA s 3 (G) is tight for an almost balanced graph with a privileged node s.

Similar results have been obtained for the sos hierarchy for sdps. While discussing the work of [START_REF] Erdogdu | Inference in graphical models via semidefinite programming hierarchies[END_REF], we discussed about the more tractable problem given in (35). Here, Ŝ is made of a set of regions such that together they cover all the nodes of the graph. If each chordless cycle of the graph is contained in at least one region in Ŝ, we say that the set of regions is circular. To present their result, [START_REF] Erdogdu | Inference in graphical models via semidefinite programming hierarchies[END_REF] makes the assumptions that the graph has zero valued unary potentials and its topology is not contractible to K 5 . Given these assumptions they show that the problem in (35) defined over a circular set of covering regions is tight. They also show how to convert a graph with non-zero unary potentials to a graph with zero unary potentials but the resulting graph could be contractible to K 5 . Note that the empirical results in [START_REF] Erdogdu | Inference in graphical models via semidefinite programming hierarchies[END_REF] concern graphs which do not satisfy the assumptions, the set of covering regions do not contain all chordless cycles and they work with graphs having non-zero unary potentials for which the conversion to zero unary potentials could result in a graph that could be contractible to K 5 . Their empirical results have exceeded the theoretical expectation and need further investigation.

We have given here only a taste for an active area of research. For example, [START_REF] Wainwright | Treewidth-based conditions for exactness of the sherali-adams and lasserre relaxations[END_REF] gave only a sufficient condition based on treewidth regarding the tightness of the Sherali-Adams hierarchy. [START_REF] Rowland | Conditions beyond treewidth for tightness of higher-order lp relaxations[END_REF] has presented analytical results which indicate that there are conditions beyond treewidth. Also, it is not necessary to study relaxation hierarchies based on exactness of the relaxation. Even if we manage to achieve low approximation error at a given level of the relaxation hierarchy, rounding schemes can be used to further improve the output [START_REF] Chlamtac | Convex relaxations and integrality gaps[END_REF].

Conclusion

Continuous relaxations for map inference in mrfs are an important topic of study with wide applications. Obtaining better map labelling in an efficient manner is the ultimate objective of this line of work. The possibility of better labelling will increase the scope of applications for mrfs with various graph topologies and clique potentials. In this survey we especially better understood approaches based on lp and sdp relaxations. We discussed various algorithmic steps that could lead to tighter relaxation in both cases. In the process, we understood the theoretical underpinnings better. This is a topic where there is scope for further research both from an algorithmic point of view and from a theoretical analysis point of view. A very important perspective is provided by applications, which explore novel clique potentials and graph topologies. The effect of tighter relaxation based inference within learning of structured prediction models is also an important avenue of research. [START_REF] Meshi | Train and test tightness of lp relaxations in structured prediction[END_REF] presents an interesting analysis about the empirical observation of tight lp relaxations within structured prediction applications. Learning a structured prediction model is computationally heavy, which involves inference in each iteration of the process (called loss augmented inference). Efficient algorithms for tighter relaxation could further the study of this topic. At this juncture, we would like to highlight the scope for further research in sdp relaxation based algorithms. The literature is much more evolving in that topic compared to algorithms based on lp relaxation.

Figure 1 :

 1 Figure 1: A toy graphical model with nodes 1, 2, 3 and 4 and cliques a and b.

Figure 2 :

 2 Figure 2: A cartoonish illustration of the relationship between the marginal polytope M(G) and the local polytope L(G). All the vertices of M(G) are also vertices of L(G). L(G) also has fractional vertices. The fact that L(G) has lesser number of facets than M(G) is difficult to visualize. Image courtesy Wainwright & Jordan (2008).

 [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF]. sdcut has also been useful for map inference in fully connected graphs [START_REF] Wang | Efficient sdp inference for fully-connected crfs based on low-rank decomposition[END_REF], which we will not discuss in detail here. First, we will briefly see the derivation of sdcut. We observe that the constraint, Φ(i; x i , i; x i ) = φ i (x i ) (28d), along with the normalization constraint on φ i (x i ) (28b), could be equivalently expressed as the constraint, tr M = n + 1, where n is the number of nodes. Where M is the moment matrix (27). M is also constrained to be symmetric and positive semidefinite. As a result of all these constraints, the following result holds true: M F ≤ n + 1 [START_REF] Malick | The spherical constraint in boolean quadratic programs[END_REF]. This inequality condition could be made a part of the objective in the sdp (28a) as a regularization term, σ( M 2 F -(n + 1) 2 ) with σ > 0. Thus, we have a regularized problem with the following form, minimize

Here, A is a matrix such that tr M A is equal to the objective in (28a). The linear equality constraints (36b) and the linear inequality constraints (36c) are written in a generic manner. They represent the linear constraints that are imposed in the sdp. For map inference, they are necessarily composed of the sdp relaxation constraints, (28b) and (28d). They could also consist of constraints borrowed from the lp relaxation literature. The dual to this problem takes the following form,

where,

Computing the gradient for this problem, involves svd, since, C(u) -is computed by considering only the negative eigenvalues of C(u). This is an expensive part of other algorithms based on sdp relaxation like [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF], also. [START_REF] Huang | Scalable semidefinite relaxation for maximum a posterior estimation[END_REF] ameliorated this problem by computing only the top eigenvectors and eigenvalues that is dictated by low-rank representation and also, by exploiting sparse matrix-vector product driven by the graph structure. [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF] resorts to a parallel eigendecomposition algorithm to achieve speed-up of the svd. [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF] continues with the theme of adding more linear constraints to the basic sdp problem [START_REF] Hazan | Convergent message-passing algorithms for inference over general graphs with convex free energies[END_REF], in order to obtain a tighter relaxation. So far, we have come across various linear constraints that are part of the local polytope based lp relaxation. Additionally, [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF] considers the following linear constraints that could be enforced. For the main diagonal blocks of Φ, apart from the constraints (28d), we could enforce the following constraints,

Intuitively, the off-diagonal blocks of Φ correspond to the pseudomarginals of pairs of nodes and we could enforce marginalization constraints and non-negativity constraints on them, like it is done in the lp relaxation. However, the main diagonal blocks of Φ are not suitable for similar constraints. The main diagonal blocks are an artifact of the semidefinite relaxation.

We have already seen the constraints (28d) that could be enforced on the main diagonal. In a similar spirit, (38) enforces desired structure on Φ.

Further [START_REF] Wang | Efficient semidefinite branch-and-cut for map-mrf inference[END_REF] enforces cycle based contraints that we came across in tighter lp relaxations (6, ??). These cycle based constraints were obtained by the combinatorial