Publication
Efficient Lifting of MAP LP Relaxations Using k-Locality
Martin Mladenov; Kristian Kersting; Amir Globerson
In: Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics. International Conference on Artificial Intelligence and Statistics (AISTATS-2014), April 22-25, Reykjavik, Iceland, Pages 623-632, JMLR Workshop and Conference Proceedings, Vol. 33, JMLR.org, 2014.
Abstract
Inference in large scale graphical models is an important task in many domains, and in particular for probabilistic relational models (eg,. Markov logic networks). Such models often exhibit considerable symmetry, and it is a challenge to devise algorithms that exploit this symmetry to speed up inference. Here we address this task in the context of the MAP inference problem and its linear programming relaxations. We show that symmetry in these problems can be discovered using an elegant algorithm known as the k-dimensional Weisfeiler-Lehman (k-WL) algorithm. We run k-WL on the original graphical model, and not on the far larger graph of the linear program (LP) as proposed in earlier work in the field. Furthermore, the algorithm is polynomial and thus far more practical than other previous approaches which rely on orbit partitions that are GI complete to find. The fact that k-WL can be used in this manner follows from the recently introduced notion of k-local LPs and their relation to Sherali Adams relaxations of graph automorphisms. Finally, for relational models such as Markov logic networks, the benefits of our approach are even more dramatic, as we can discover symmetries in the original domain graph, as opposed to running lifting on the much larger grounded model.