Structured M-layer Graph Lifting Applied to Combinatorial Optimization and Machine Learning
POSTER
Abstract
We show that a structured M‑layer lift of a frustrated probabilistic graphical model smooths the MAP (maximum a posteriori) landscape and speeds search to optimal solutions.
In standard M-layer lifts each replica is connected by random rewiring. Our version constrains those permutations through a row-stochastic kernel Q, which imposes structured correlations between layers rather than full randomness. With annealed permutations, information moves on two graphs: the original interaction graph and the Q‑defined layer graph. On combinatorial optimization problems, simple greedy dynamics on the lift reaches lower residual energies and needs less compute.
We derive belief propagation with mixing and explain the mechanism of this rapid relaxation to lower energy states. Layer‑to‑layer fluctuations first amplify coherent directions that escape metastable minima. Mixing then synchronizes layers and contracts those fluctuations. To leading order the motion is stochastic dynamics on the Bethe free energy with small loop corrections.
The scheme is algorithm‑agnostic and hardware‑friendly because only inter‑layer wiring changes. We apply it to Boolean satisfiability, q‑coloring, and simple machine learning models. It improves solution quality and, in the case of machine learning, generalization.
In standard M-layer lifts each replica is connected by random rewiring. Our version constrains those permutations through a row-stochastic kernel Q, which imposes structured correlations between layers rather than full randomness. With annealed permutations, information moves on two graphs: the original interaction graph and the Q‑defined layer graph. On combinatorial optimization problems, simple greedy dynamics on the lift reaches lower residual energies and needs less compute.
We derive belief propagation with mixing and explain the mechanism of this rapid relaxation to lower energy states. Layer‑to‑layer fluctuations first amplify coherent directions that escape metastable minima. Mixing then synchronizes layers and contracts those fluctuations. To leading order the motion is stochastic dynamics on the Bethe free energy with small loop corrections.
The scheme is algorithm‑agnostic and hardware‑friendly because only inter‑layer wiring changes. We apply it to Boolean satisfiability, q‑coloring, and simple machine learning models. It improves solution quality and, in the case of machine learning, generalization.
Presenters
-
Timothée G LELEU
- NTT Research, Inc.