A Delayed Column Generation Strategy for Exact k-Bounded MAP Inference in Markov Logic Networks
This work addresses inference challenges in probabilistic graphical models for applications like graph matching, but it appears incremental as it builds on existing MAP inference methods with a parameterized constraint.
The paper tackles the problem of MAP inference in Markov logic networks by introducing k-bounded MAP states and a delayed column generation algorithm, achieving efficient computation for real-world graph matching problems.
The paper introduces k-bounded MAP inference, a parameterization of MAP inference in Markov logic networks. k-Bounded MAP states are MAP states with at most k active ground atoms of hidden (non-evidence) predicates. We present a novel delayed column generation algorithm and provide empirical evidence that the algorithm efficiently computes k-bounded MAP states for meaningful real-world graph matching problems. The underlying idea is that, instead of solving one large optimization problem, it is often more efficient to tackle several small ones.