NeuroLifting: Neural Inference on Markov Random Fields at Scale
This provides a scalable solution for MRF inference problems, which is incremental as it builds on traditional lifting techniques with neural networks.
The paper tackles the challenge of efficient and high-quality inference in large-scale Markov Random Fields (MRFs) by introducing NeuroLifting, a method that uses Graph Neural Networks to reparameterize variables for gradient descent optimization. Results show it performs close to an exact solver on moderate scales and surpasses all baselines on large scales with linear computational complexity growth.
Inference in large-scale Markov Random Fields (MRFs) is a critical yet challenging task, traditionally approached through approximate methods like belief propagation and mean field, or exact methods such as the Toulbar2 solver. These strategies often fail to strike an optimal balance between efficiency and solution quality, particularly as the problem scale increases. This paper introduces NeuroLifting, a novel technique that leverages Graph Neural Networks (GNNs) to reparameterize decision variables in MRFs, facilitating the use of standard gradient descent optimization. By extending traditional lifting techniques into a non-parametric neural network framework, NeuroLifting benefits from the smooth loss landscape of neural networks, enabling efficient and parallelizable optimization. Empirical results demonstrate that, on moderate scales, NeuroLifting performs very close to the exact solver Toulbar2 in terms of solution quality, significantly surpassing existing approximate methods. Notably, on large-scale MRFs, NeuroLifting delivers superior solution quality against all baselines, as well as exhibiting linear computational complexity growth. This work presents a significant advancement in MRF inference, offering a scalable and effective solution for large-scale problems.