Separate but Equal: Equality in Belief Propagation for Single Cycle Graphs


  • Erel Cohen Ben-Gurion University
  • Omer Lev Ben-Gurion University
  • Roie Zivan Ben-Gurion University



CSO: Constraint Optimization, CSO: Distributed CSP/Optimization


Belief propagation is a widely used incomplete optimization algorithm, whose main theoretical properties hold only under the assumptions that beliefs are not equal. Nevertheless, there is much evidence that equality between beliefs does occur. A method to overcome belief equality by using unary function-nodes is assumed to resolve the problem. We focus on Min-sum, the belief propagation version for solving constraint optimization problems. We prove that on a single cycle graph, belief equality can be avoided only when the algorithm converges to the optimal solution. In any other case, the unary function methods will not prevent equality, rendering some existing results in need of reassessment. We differentiate between belief equality, which includes equal beliefs in a single message, and assignment equality, that prevents a coherent selection of assignments to variables. We show the necessary and satisfying conditions for both.




How to Cite

Cohen, E., Lev, O., & Zivan, R. (2023). Separate but Equal: Equality in Belief Propagation for Single Cycle Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4), 3924-3931.



AAAI Technical Track on Constraint Satisfaction and Optimization