Ordering arc-reversal operations when eliminating variables in lazy AR propagation

This paper considers the problem of ordering arc-reversal operations and breaking ties in cost measures when eliminating variables in Lazy AR Propagation (LPAR). In particular, the paper presents the BreakTies algorithm for breaking ties in cost measures when selecting the next arc to reverse in a variable elimination operation. BreakTies is based upon using a sequence of cost measures instead of randomly selecting an arc to reverse when multiple arcs share the same cost. The paper reports on an experimental evaluation of LPAR for belief update in Bayesian networks considering six sequences of five cost measures for breaking ties using BreakTies. The experimental results show that using BreakTies to select the next arc to reverse in a variable elimination operation can improve performance of LPAR.

► We consider arc-reversal cost measures in Lazy propagation using arc-reversal (LPAR) as the message and marginal computation algorithm.
► We introduce the BreakTies algorithm for breaking ties in cost measures when selecting the next arc to reverse in a variable elimination operation.
► The experimental results show that there can be a difference in performance when using different cost measures for ordering arc-reversal operations in LPAR.