  Markov Networks are widely used through out computer vision and machine
learning. An important subclass are the Associative Markov Networks which are
used in a wide variety of applications. For these networks a good approximate
minimum cost solution can be found efficiently using graph cut based move
making algorithms such as alpha-expansion. Recently a related model has been
proposed, the associative hierarchical network, which provides a natural
generalisation of the Associative Markov Network for higher order cliques (i.e.
clique size greater than two). This method provides a good model for object
class segmentation problem in computer vision. Within this paper we briefly
describe the associative hierarchical network and provide a computationally
efficient method for approximate inference based on graph cuts. Our method
performs well for networks containing hundreds of thousand of variables, and
higher order potentials are defined over cliques containing tens of thousands
of variables. Due to the size of these problems standard linear programming
techniques are inapplicable. We show that our method has a bound of 4 for the
solution of general associative hierarchical network with arbitrary clique size
noting that few results on bounds exist for the solution of labelling of Markov
Networks with higher order cliques.
