Deep Attentive Belief Propagation: Integrating Reasoning and Learning for Solving Constraint Optimization Problems
Authors: Yanchen Deng
Shufeng Kong
Caihua Liu
Bo An
Venue: NeurIPS 2022 Accept (2022)
Keywords: Constraint Optimization Problems
Belief Propagation
Damping
Attention Mechanism

Abstract: Belief Propagation (BP) is an important message-passing algorithm for various reasoning tasks over graphical models, including solving the Constraint Optimization Problems (COPs). It has been shown that BP can achieve state-of-the-art performance on various benchmarks by mixing old and new messages before sending the new one, i.e., damping. However, existing methods on tuning a static damping factor for BP not only is laborious but also harms their performance. Moreover, existing BP  algorithms treat each variable node's neighbors equally when composing a new message, which also limits their exploration ability. To address these issues, we seamlessly integrate BP, Gated Recurrent Units (GRUs), and Graph Attention Networks (GATs) within the massage-passing framework to reason about dynamic weights and damping factors for composing new BP messages. Our model, Deep Attentive Belief Propagation (DABP), takes the factor graph and the BP messages in each iteration as the input and infers the optimal weights and damping factors through GRUs and GATs, followed by a multi-head attention layer. Furthermore, unlike existing neural-based BP variants, we propose a novel self-supervised learning algorithm for DABP with a smoothed solution cost, which does not require expensive training labels and also avoids the common out-of-distribution issue through efficient online learning. Extensive experiments show that our model significantly outperforms state-of-the-art baselines.

Deep Attentive Belief Propagation: Integrating Reasoning and Learning for Solving Constraint Optimization Problems
Yanchen Deng
Shufeng Kong School of Software Engineering
School of Computer Science and Engineering
Nanyang Technological University yedeng@ntu. edw.ett.eeddd.........ee......
Sun Yat-sen University kongshfomail sysu. edu, en
Caihua Liu
Bo An
School of Artificial Intelligence Guilin University of Electronic Technology caihua. lal@alluunn uts. lits.edd..a. au
School of Computer Science and Engineering Nanyang Technological University boanEntu. edu. sg
Abstract
Belief Propagation (BP) is an important cesssage-psssing algorithm for various reasoning tasks over graphical models, including solving the Constraint Optimiza- tion Problems (COPs). It has been shown that BP can achieve state-of-the-ar performance on various benchmarks by mixing old and new messages before sending the new one, i.e., damping. However, existing methods of tuning static damping factor for BP not only are laborious but also harm their performance. Moreover, existing BP algorithms treat each variable node's neighbors equally when composing a new message, which also limits their exploration ability. To address these issues, we seamlessly integrate BP, Gated Recurrent Units (GRUs), and Graph Attention Networks (GATs) within the message-passing framework to reason about dynamic weights and damping factors for composing new BP messages. Our model, Deep Attentive Belief Propagation (DABP), takes the factor graph and the BP messages each iteration as the input and infers the optimal weights and damping factors through GRUs and GATs, followed by multi-heat attention layer. Furthermore, unlike existing neural- based BP variants, we propose novel superviedd learning algorithm for DABP with smoothed solution cost, which does not require expensive training labels and also avoids the common out-of-distribution issue through efficient online learning. Extensive experiments show that our model significantly outperforms state-of-the-arr baselines.
Introduction
Belief Propagation (BP) 27 36 is important message-passing algorithm for various reasoning tasks over graphical models, e.g., computing partition function of a Markov random field (50), estimating the marginal distribution of given set of random variables [1, and decoding LPDC codes [32]. Constraint Optimization Problems (COPs) [33] 41) are a general mathematical paradigm for modeling many real-worle problems like transportation, supply chain, energy, finance, and scheduling
66 24 25 41I. When solving COPs, BP, also known as Min-sum message passing [16]. seeks to
find cost-optimal solution by propagating cost information the corresponding factor graph.
"Correspondence to: Shufeng Kong <kongshf myi..sysuu.d...c..
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

It is known that vanilla BP does not guarantee convergence on factor graph containing loops and thus, it often explores luw-quality solutions on COPs with cyclic factor graphs due to excessive loopy propagation. Therefore, considerable research efforts 7 9 38
40, 54 have been devoted to tackling the convergence issue of loopy BP. Among them, Damped BP (DBP
has drawn significant attention recently. By mixing the new message composed in each iteration with the old message composed in the previous iteration, i.c., damping, it has been shown that DBP with a suitable damping factor will often converge and achieve state-of-the-art performance in practice. In fact, damping can be considered as a degree freedom to balance exploration and exploitation in BP (
Due to the significant impact of damping on BP [53], damping factor is often treated as a hyperpa- rameter and requires laborious case-by-case tuning. Besides, existing works often use homogeneous and static damping factor for all variable-nodes which limits DBP's capability. Moreover, DBP simply treats each variable-node' s neighbors equally when composing a new message, which fails to explore optimal composition strategy. On the other hand, Deep Neural Networks (DNNs) have been applied to boost the performance of BP 28 43 51 However, existing DNN-based BP variants often require supervised learning and expensive training labels and thus, they cannot be directly applied to solve COPs when training labels are not available. They also manipulate or simulate the BP messages with some black-box DNN components, which destroys the semantic of BP message being the weighted sum of cost functions' marginalizations and thus, the variable meeiiinn-making rule of BP for COPs is no longer applied (i.e., selecting the assignments with the minimum beliefs).
To address the above issues, we propose the first supervueeee -NNe- BP for solving COPs by seamlessly integrating BP, Gated Recurrent Units (GRUs) [8) and Graph Attention Networks (GAT's) [46] within the massage-passing framework to reason about dynamic weights and damping factors for composing new BP messages. Specifically, we make the following key contributions:
We extend DBP by allowing dynamic damping factors and different neighbor weights for each variable-node. Consequently, we have more fine-grained control for composing new messages to trigger effective exploration without altering the semantic of BP messages.
We infer the optimal damping factors and neighbor weights for each iteration automatically by seamlessly integrating BP and DNNs. Our model, Deep Attentive Belief Propagation (DABP firstly embeds respectively the factor graph and BP messages with GATs and GRUs, and infers damping factors and neighbor weights through a multi-head attention layer; Then, BP runs with those updated factors and weights to compose and propagate new messages, and
2 4
Note that integrating GRUs can capture the dynamics of BP messages and avoid the gradient vanishing/cxploding issue in long BP reasoning sequences.
We further equip our DABP with a novel self- learning loss which is smoothed surrogate for the cost under BP decision-makiin rule. Therefore, unlike existing DNN-hased BP variants, we do not require expensive training labels which are often not available in practice, and also our model can avoid out-of-distribution issue with efficient online learning.
We conduct extensive experimental evaluations on four standard benchmarks. The results show that our DABP achieves significantly higher convergence rate, where it successfully converges on average 96.25% instances given 1000 iterations, and it also outperforms the state-of-the the-hhhrrr art baselines by considerable margins.
2 Related Work
Although COP is NP-hard in general [41), many algorithms have been proposed to solve it in the last several decades, such as BP, local search (2I) branch and bound [30]. and bucket elimination
18]. Among them, Min-sum BP is an effective approximate algorithm for solving COPs and has been successfully applied many real-world scenarios [16] 22 31. However, vanilla BP offers no convergence guarantee and usually returns low-quality solutions on problems with cyclic factor graphs. Rogers et al. proposed ensure convergence and have lower bound on solution quality by relaxing the problem, i.c., removing edges to have acyclic factor graphs (38] through minimization marginalization. Further, Rollon et al. improved the bounding scheme by
12
I 'The method is referred as "Damped Max-sum" in D We use Damped BP for coherent presentation.
2 The implementation is publicly available at https:/ggihubb..ooocddeennn//uuu
2

---

considering both minimization and maximization marginalization [39] and decomposing high-arity factors into unary functions (40] On the other hand, Zivan et al. proposed to avoid loopy message propagation by strictly controlling the paasage-passing direction [54]. They also introduced the Value Propagation (VP) scheme enforce exploitation. To balance exploration and exploitation, set of non-consecutive VP strategies are proposed 77] as well. Recently, Damped BP (DBP) [9] has been proposed to enhance convergence as well as solution quality in loopy BP by mixing the new messages composed in each iteration with the old messages in previous iterations with a suitable damping factor. However, selecting a good damping factor often requires expertise and laborious case-by-case tuning [53], and DBP uses static damping factor and treats each node's 's neighbors equally when composing a new message, which limits its exploration. Our DABP overcomes the aforementioned issues by learning to attend neighbors with dynamic damping factors and neighbor weights when composing new BP messages. Obviously, DABP generalizes DBP since DBP can be considered as a statie version of DABP. Moreover, equipped with a self-supervised learning algorithm, our DABP is able to infer the optimal damping factors and weights to enhance the performance of DBP.
On the other hand, LP-based methods solve a COP by leveraging message-passingg to solve Linear Program (LP) relaxation of the combinatorial problem. MPLP [9] is a simple BP variant that solves the convex-dual of the LP relaxation via block gradient descent. Unfortunately, the global convergence not always guaranteed since coordinate descent may get stuck in suboptimal points. Tree-teweighted belief propagation (TRBP) [48] and Fractional Belief Propagation [49] consider respectively a linear combination of free energies defined on spanning trees of the factor graph and a fractional free energy that generalizes the well-known Bethe free energy. Finally, Norm- Product (20] provides a uniform framework that generalizes Max-product, Sum-product and their TRBP counterpart. Unlike these methods, our DABP directly solve the problem by learning optimal hyperparameters for DBP, and does not require any form of LP relaxation which may either induce intractable number of constraints or only offer lower bound [29].
Recently, there has been increasing interest in applying DNNs to boost the performance of BP. The most relevant works including: NEBP 43 learns to refine BP messages with some black-box DNN components in each iteration and is applied to solve the error correction decoding task; In the same vein, BPNN (28) uses damping layers to modify factor-to-variabll messages and is applied to estimate the partition function of Probabilistic Graphical Models (PGMs); FGNN [51) generalizes Graph Neural Networks (GNNs) to represent Max-Produs BP and is applied to find approximate Maximum Posteriori (MAP) assignment of a PGM. However, all these methods require supervised learning and cannot be directly applied to solve COPs when training labels are not available; They also destroy the semantic of a BP message being the weighted sum of cost functions' marginalizations. Contrarily, we only learn optimal dynamic factors and neighbor weights with DNNs to generalize DBP, which preserves the semantic of the BP messages and also enables us using a self-supervised manner to train our model. Therefore, our model does not require expensive training labels which are often not available in practice due to the heavy computation of exact solvers; and also avoids out-of distriiiittiiittonn issue and enjoys a nice anytime property (52) through efficient online learning.
Our method is also closely related to using DNNs to solve combinatorial problems 5
14 26
In the context of COP solving, Neural RM-RRS [15] uses Multi-layer Perceptrons (MLPs) to parameterize high-dimensional regret tables produced by context-based regret-matching. Similarly, Deep Bucket Elimination (DBE) [37] uses MLPs to approximate the large bucket functions (II. Recently, Deng et al. [4] proposed a pretrained cost model which predicts the optimal cost of a given partially instantiated COP. The predicted cost is then used construct heuristics for various COP algorithms such as Large Neighborhood Search (LNS) 21 and backtracking search. These methods either replace some heavy computation components of COP algorithms by fast DNN approximation. or learn effective heuristics (or hyperparameters) to boost the performance of COP algorithms, and our method falls into the second category.
3 Backgrounds
In this section, we review the backgrounds of COPs, factor graphs, and Min-sum BP.
3

---

3.1 Constraint Optimization Problems and Factor Graph
Constraint Optimization Problem (COP) 33 is defined by triplet (X, D, F), which corresponds to the set of variables, domains, and constraint functions, respectively. Each variable r; E X is associated with a finite domain D, D. Each constraint function ft with scope scp(fe) S X specifies the cost for each possible assignment of the variables in its scope. The objective is to find solution T" = (T]..... 7xx)) IT 2 x Dj such that the total cost minimized:
arg min relle;ex Di feeF
Σ Se(Tlocptta).
(I)
where T/zcp(fe) is the projection of scp(St). A COP can be represented by a factor graph which is a bipartite graph consisting of variable-nodes and function-nodes. Variable-nodes correspond to the variables, and funetion-nodes correspond to the constraint functions in COP. An edge between variable-node and a function-node is established if the variable belongs to the scope of the function.
3.2 Min-sum Belief Propagation
Min-sum Belief Propagation (Min-sum BP) [6] is an important algorithm for COPs which performs message-passing on factor graphs. More specifically, the message sent from variable-node 2; to its neighbor ft in iteration / is a function - Di IK computed by
Σ
A-1 Sm
where N₁ is the neighbors of in the factor graph, and fmm Dr + R is the message sent from fm z; in the previous iteration. Similarly, fe computes message for its neighbor æ; by
min NeMlz.)
fe+
E
May-te
(3)
Finally, variable-node x; makes decision by choosing a value with minimum belief cost:
7/ = arg min
Σ (1),
(4)
T.ED
SEEN
where -t, (Ti) is the belief cost of assignment 7; the message p/e-
However, vanilla Min-sum BP usually suffers from non-convergence and explores low-quality solutions on cyclic COPs due excessive loopy propagation. Damped BP (DBP) (9] attempts to alleviate the issues by damping the messages sent from variable-nodes to function-nodes. Formally,
P = -1111 A1
Σ f. ENG(fe)
(5)
fm
By choosing suitable damping factor À (0, 1]. DBP can drastically increase the chance of convergence as well as the performance of vanilla Min-sum BP.
Deep Attentive Belief Propagation
Although message damping has proved to be an effective technique to improve the performance of BP on COPs [ it still suffers from various issues. First, selecting a damping factor largely accomplished by empirical tuning, which could be laborious and the number of trials is limited by computational resources and/or runtime. Second, using a homogeneous and static damping factor for all srriable-nodes may limit DBP's capability. Finally, DBP simply treats each variable- node's neighbors equally when composing new message, which fails to explore optimal message composition strategy.
We address the above limitations by allowing dynamic damping factors and different neighbor weights for each variable-node. More specifically, in our framework a variable-node x; computes a message function-nol node fe iteration by
14 -
- + ((V.-
-1)
Σ
"n fm
(6)

---

1a (0
fx
ft
D Σ
Nior
(a) Vanilla BP
(b) DBP
(c) DABP
Figure 1: Comparison of BP variants. Obviously, our DABP generalizes both vanilla BP and DBP.
where > E [0, 1] and (C) E [0. are learnable damping factor and neighbor weights for the message from 24 fe at iteration f, respectively. Particularly, we require f.. w (m) =
and use [ - to rescale the weighted sum of the messages from neighbors. Consequently. we have more fine-grained control for composing altering the semantic BP messages. Fig. [ compares three different BP variants.
messages to trigger effective exploration without
A key challenge of our framework is to determine the values of large number of lime-varying damping factors and neighbor weights (cf. Eq. (6)). Given a factor graph with [X] variables and maximum degree of d, rumning for T iterations would require to select (TT) |x{x) hyperparameters from the continuous range [0, 1]. which obviously cannot be done by the traditional triel-based hyperparameter tuning methods (e.g.. grid search, evolutionary optimization).
Therefore, we propose to automatically infer the optimal hyperparameters for Eq. (6) in each iteration by seamlessly integrating BP and DNNs within the parallel message meessage-passnng passing framework. Our model, Deep Attentive Belief Propagation (DABP), directly outputs the optimal damping factors and weights by learning to attend neighbors given the factor graph and the BP messages in each iteration:
o0 =M (FG, M ff-
1:t-1 1:t-1)
where FG is the factor graph, Kz-z function-nodes and from function-nodes to variable-nodes in the previous iterations, respectively.
1:t-1 are the BP messages from variable-nodes to 1:t-1 and 2
However, implementing such DNN-based model requires perform inference along with BP message-passing iterations (cf. Eq. (7)). which could incur severe gradient vanishing or gradient exploding problem long reasoning sequence. Moreover, obtaining optimal training labels can be extremely expensive for COPs due to the heavy computation of exact solvers, making it impracticable to perform supervised model training on large instances. In Sect. 4.1 we address the first problem by introducing GRUs as part of our encoder, while we design novel supervuper loss function and an efficient online learning framework in Sect. 4.2 to address the second issue.
4.1 Model Architecture
Fig. 2 gives the overall architecture of DABP. It consists of encoder to embed the factor graph and the BP messages, and an attention module to infer the dynamic optimal hyperparameters.
Encoder. The purpose of our encoder is to embed the factor graph given a sequence BP mes- sages (cf. Fig. aa)d).. Therefore. capture the BP message dynamics and avoid gradient van- ishing/exploding issue, we first use two GRUs to embed the BP messages from variable-nodes to function-nodes and the ones from function-nodes to variable-nodes into g-dimensional vectors, respectively (cf. Fig. bb)):
h h/ GRU ( hラ GRU's (h : p
where h h prxq are the message hiddens for iteration and the number of edges in the factor graph.
To consider both the topology of a factor graph and the message dynamics, we insert set of message nodey that carry the message hiddens (i.e., the brown and green dots in Fig. (c)) and make the graph directions. Then the augmented factor graph is embedded
directed to reflect the through G layers of GAT (cf. Fig, 2 d)). Formally, in the g {L...., G) layer GAT
5

---

f
f
I
f
BP Messages
Mussage hiddens
Iteration t-1
GRUs
Ma--1 pi--
n h
(6)
Compute Loss
GAT'
Compute pa-- Mi
f
f
Hyperparamneters
Iterstion è
= A
Iteration
(b) To update the message hidden vectors with the messages from iteration t 1. Note that these message hidden vectors capture the dynamies of sequence of BP messages; (c) To insert message nodes with the hidden vectors into the factor graph; (d) To embed the augmented factor graph; (e) To infer optimal hyperparameters by using multi-head attention layer (MHA); and (f) To compose and propagate new messages with updated hyperparameters and compute training loss in iteration l.
Figure 2: The overall architecture of DABP: (a) The BP messages from iteration
compute the embedding e/110) for node i according to
exp(x!))
f.(0) e, e:
LeakyReLU
Σ JEN,
w
(9)
ai
EjeN, exp(s (0))
where (s)) E bi is a learnable matrix, 11 aهه (W (.10-1) W ((0-1)) is the attention score between nodes and j, and (9) is single-layer feed-forward neural network.
Attention Module. Given the embedding (.(G) for each ft F, we update the damping factors and neighbor weights by using multi-head attention (MHA) layer [44] (cf. Fig. (e)), where queries and keys are the embeddings the target and corresponding neighboring function-nodes, respectively, Specifically, for each variable-node x, and a target function-node fe E Nr. we first compute an attention score for each neighboring function-node fm E Nr in l E (1....,K) K}-th head Att., by:
dm
(.(R) (L)
(w)
(k)
W
(G( (k) Ee
(w (k) e(((())))
(10)
where a is the Sigmoid function, || is the concatenation operation and W(k) are learnable matrices, respectively. Then the attention scores normalized to compute neighbor weights respect to target function-node fe:
(k) ((k) (( E ÇA
exp (.(K))
(E)
(k) (f) +5
Vfm EMMS)..
(11)
Σ, EMAEE exp
(.(K) Omm
(1)
Similarly, the damping factor is computed by normalizing the attention score of Se w.r.t. the mean attention score the remaining neighboring manction-nodes
exp (a. (2) (e)
(12)
exp
ag
(.(k) (.(K) (1)
exp [ EI
A.(k) a m
(t)
Finally, both the neighbor weights and damping factors are normalized across different heads, i.c.,
(.(K)
EK
Afm E N&ffe)),
(13)
K
K
and are plugged into Eq. 6 to compute new BP messages for iteration t (cf. Fig. 2))

---

Algorithm A self-supervised online learning algorithm for the DABP model Ma
Input: A COP instance P = (X, D, F), the number of restart R. the maximal iteration limit Taax, the update interval Tupa < Tmax. and the number of effective iterations Tar E {1,.... Tupe
1: r² nil; FG factor graph of
for rs 1,-1,.. R do
3: Me + 0 Oi +
O, Va, EX,SEEN,
4: for = I,..., Tmx do
5:
w², X + Mo FG, -- 5
6:
compute - according to Eq.
6
with hyperparameters w', Vr, Va, E X, e e.
compute -/,-x; according to Eq.
Va, X2 N.
8:
compute solution 7' (Tí, (Ti....,77))
x
according to Eq.
9:
if ('cos("))>cos((""" then 7"
10:
if % Tupt then
11:
I" select the best Tin iterations according to cost(r') ), Tupa < St compute (()) according to Eq. (16). ADAMM(,, VL(())
12:
13:
if BP messages converge then break
return
7"
4.2
A Novel Self-supervised Learning Algorithm for Solving COPs
Recall that our objective is to find cost-optimal solution (ef. Eq. 1 natural choice of the loss
function would be the cost of the solution induced by BP messages in each iteration. Unfortunately. such loss function is not differentiable since variables are greedily assigned via argmin (cf. Eq. (4) Instead, we propose to use a smoothed cost as the surrogate objective. Formally, for each iteration t we consider the following self-supervised objective:
loss' Σ
Σ (7h (7h Th, Elll,, Dr
fe Tin)) II pl, pi.(
(14)
SEEF
j=1m
where pT():) the probability of x4 7Ü under the current belief, i.c..
(T.)) (l(T)) Σ EFEDD exp( exp(-b((r)))
((())) = Mie-oz (T:).
(15)
SEEN
Intuitively, assignment rÚ is associated with high probability if it has low belief cost by (7:). which simulates the behavior of argmin in Eq. 44) and is in alignment with the objective in Eq.
We now theoretically show the error bound of the smoothed cost. Proof is given in Appendix A. Theorem Let A = (r..sa) Ton
min (re v...) .) fe(Tr,,..., Ti.)) be the max- imum difference between cost values of each constraint function ft and 7 (Tí..... Txx) be the assignment induced by Eq. 44. We have
Ti.)) fe(
loss'
Σ FelF'lsopise)
Σ Ae feeF
I-III
IIIII
II
Di|
JIFF
#.Esc((fee
Given the smoothed objective for each iteration, we define the following loss function:
((0) = T
loss',
(16)
RET
where 0 = [01 d2 [/,,...,, IS...... <x]> } is the model parameters and T* is a selected subset of iterations used for optimizing, respectively. Particularly, rank each iteration according to the quality solution r¹ and select the best Tex iterations as effective iterations T This way, we encourage exploration by considering only good-enough solutions.
Since our model self- self-supervised by the smoothed cost, there is no need for costly label generation for each instance and thus, DABP can be directly applied to solve COPs via online learning without
7

---

any pre- vre-training procedure. That is, from an initial DABP model Mg. we continuously improve it by training on the instance multiple rounds (i.e., restart) on the COP to be solved and return the best solution as the result. Therefore, our DABP avoids the duttii-distiibuttin issue and has nice anytime property [52]. The procedure is detailed in Alg. |
Specifically, each round of restart begins with resetting BP messages to zero vectors (line 3), followed by a sequence of cressage-passingg iterations (line 4-13). In each iteration, we query our DABP for the damping factors and neighbor weights (line 5), perform BP message passing according to the updated hyperparameters (line 6-7), and finally update the current best solution (line 8-9). Particularly, we perform model update every Tupa iterations (line 10- 12) and thus, we further alleviate the gradient vanishing/explodin issue by restricting the maximum length of reasoning sequence to Tup.. Lastly, we early stop each round whenever BP messages converge (line 13) and return the best solution.
Empirical Evaluations
In this section, we perform extensive empirical studies. We begin with introducing the details of experiments and implementation. Then we analyze the impact of the number of selected effective iterations in Alg. Finally, we show the great superiority of our DABP over the state-of state-of-the-arty aats.
Benchmarks & Baselines. We consider four types of standard benchmarks in our experiments, i.c., random COPs, scale-free networks, small-world networks, and Weighted Graph Coloring Problems (WGCPs). For random COPs and WGCPs, constraints are randomly established according to graph density P1 E (0, 1]. For scale-free networks, we use the BA model [4] with parameters mo, mi E Z, to generate constraints. Finally, we generate constraints for small-world networks by using Newman- Watts-Strogatz model (35] with parameters
Z4.P= E [0, 1).
For baselines, we compare our DABP with the following state-of-the-art COP solvers: (1) DBP with a damping factor of 0.9 and its splitting constraint factor graph version (DBP-SCFG) with splitting ratio of 0.95 [9] (2) GAT-PCM-LLE PCS with a destroy probability of 0.2 14: (3) Mini-bucket Elimination (MBE) with an i-bound of 9 [3), and (4) Toulbar2 with timeout of 1200s [TO.
All experiments are conducted on an Intel 19-9820X workstation with GeForce RTX 3090 GPUs and 384GB memory. We report the best solution cost for each run, and for each experiment average the results over 100 random problem instances. Due to the space constraint, we defer the details of benchmarks and baselines to Appendix B.1 and B.2, respectively.
Implementation. Our DABP consists of two GRUs which embeds BP messages into 8- 8-dimensional hidden vectors, followed by G = 4 layers of GAT, each of them has 8 output channels and 4 attention- heads. We then infer the optimal damping factors and neighbor weights by using multi-head attention layer with K- = 4 attention-heads. Finally, we also adopt the SCFG scheme with the splitting ratio of 0.95 (9] Our model was implemented with the Py PyTorch Geometric framework [17] and the model was trained with the Adam optimizer (23) using a learning rate of 10-4 and a weight decay ratio of 10-5, For each instance, we perform R 20 restarts with iteration limit T Tiaax 1000 and update the model every Tipd 20 iterations.
Performance Comparison. Table I compares the performance of different methods on the four standard benchmarks. We observe that, although given relatively high timeout (i.e., 20 minutes), Toulbar2 still performs poorly on the most test cases. This is not surprising because it systematically explores the whole solution space, which is often infeasible for large problem instances. Also, highlights the extreme difficulty of obtaining optimal labels with an exact solver for the existing DNN- based BP variants. MBE, on the other hand, performs memory- bounded inference and thus runs much faster than Toulbar. However, MBE fails to find good solutions and is strictly dominated by the other algorithms. GAT-PCM-LNS performs iterative large neighborhood search with a machine-learne repair heuristic and often outperforms DBP. However, GAT-PCM-LNS requires significant longer runtime than DBP since it needs to perform multiple times of model inference in each iteration to re-assign the destroyed variables. With small modification in a factor graph, DBP-SCFG drastically improves the performance of DBP but computationally heavier. That is because the number of maction-nnoes in DBP-SCFG is doubled due to constraint function splitting.
8

---

Table 1: The performance of different methods. Costs are normalized by the number of constraints [F]. Gap is the ratio of cost difference w.r.t. the best result. The best results are shown in bold.
Random COPs (p1
0.25)
X
60
[X]
80
[X] Gap
100
Methods
Cost
Gup
Time
Cost
Gap
Time
Cost
Time
Toulbar2
29.26
7.88%
20m
32.49
8.23%
20m
34.36
7.23%
20m
MBE
32.04
18.11%
4m2s
34.85
16.10%
8m38s
36.76
14.72%
Im58s
GAT-PCMM-LN
28.00
3.21%
5m27s
30.80
2.59%
12m55s
32.78
2.31%
24m47s
DBP
27.86
2.72%
Imlls
30.79
2.58%
2m25s
33.06
3.17%
4m18s
DBP-SCFG
27.60
1.77%
52s
30.50
1.60%
2m6s
32.45
1.28%
3m59s
DABP (Rt- 5)
27.19
0.24%
1m4s
30.09
0.23%
1m20s
32.12
0.26%
1m49s
DABP (R-
27.16
0.12%
2m2s
30.05
0.10%
2m41s
32.07
0.10%
3m37s
DABP (R= 20)
27.12
0.00%
4m
30.02
0.00%
5m20s
32,04
0.00%
7m20s
WGCPs (p)
0.25)
Toulbar2
0.18
0.00%
20m
1.23
41.06%
20m
2.11
42.09%
20m
MBE GAT-PCM-LNS
1.98
69%
Us
2.81
223.13%
Os
3.43
131.05%
1s
0.51
191.35%
57s
1.16
33,98%
2m40s
1.79
20.47%
5m56s
DBP
1.78
913.53%
29g
3.03
249.36%
1m4s
3.79
15%.99%
lm55s
DRP-SCFG
0.40
130.39%
30s
1.04
19.77%
1m59s
1.69
13.97%
4m29s
DABP (R= = 5)
0.32
80,52%
Im9s
0.89
2.39%
2m53s
1.57
5.50%
5m47s
DABP (R= = 10)
0.30
73.80%
2m 5s
0.88
0.92%
5m37s
1.50
0.69%
1m19s
DABP (R= 20)
0.29
67. 17.1
4m26s
0.87
0.00%
11
1.49
0.00%
22m35s
Scale-fres freee-free networks (my = mm]
10)
Toulbar2
31.01
7.51%
20m
31.70
8.07%
20m
32.69
10.51%
20m
MBE GAT-PCM-LNS
33.70
16.85%
4m8s
34.26
16.82%
5m43s
34.58
16.91%
7m9s
29.62
2.70%
6m25s
30.41
3.66%
10m55s
31.10
5.16%
17m7s
DBP DCP-SCFG
29.32
1.65%
1m166
30.11
2.66%
2m8s
30.47
3.04%
2m57s
29.27
1.46%
Im18s
29.76
1.47%
1m51s
30.01
1.48%
2mn7s
DABP (R- 5)
28.93
0.30%
Im2s
29.43
0.32%
Im15s
29.67
0.33%
1m
DABP (R= 10)
28.87
0.10%
2m2s
29.38
0.17%
2m33s
29.62
0.15%
2m37s
DABP (R- 20)
28.84
0.00%
4m3s
29.33
0.00 %
5m9s
29.58
0.00%
5m12s
Small-world networks (k = 10.p
0.3)
Toulbar2
27.98
8.72%
20m
28.28
10.37%
20m
28.36
10.60%
20m
MBE GAT-PCM-LNS
29.67
15.26%
2m466
29.39
14.71%
3m39s
29.54
15.17%
4m50s
26.75
3.93%
4m
26.65
4.04%
6m19s
26.68
4.02%
9m12s
DBP DBP-SCFG
26.77
4.02%
Im
27.03
5.52%
Im23s
27.40
6.83%
1m50s
26.30
2.17%
1m4s
26.09
1.83%
1m31s
26.13
1.90%
2m 10s
DABP (R= 5)
25.84
0.39%
Im15s
25.70
0.33%
Im31s
25.73
0.34%
1m56s
DABP (R= 10)
25.78
0.15%
2m36s
25.65
0.14%
3mfs
25.70
0.20%
3m49s
DABP (R= 20)
25.74
0.00%
5m8s
25.62
0.00%
6m200
25.65
0.00%
7s
Our DABP exhibits great superiority in various benchmarks. Specifically, given 5 times of restart, DABP substantially outperforms DBP-SCFG, which is currently the strongest approximate solver for COPs, on all test cases and the gap is widened with the increasing It. This demonstrates the merits of our learned dynamic damping factors and neighbor weights over the static and homogeneous counterpart. Importantly, although our DABP requires to perform online learning when solve each instance, our DABP's runtime results are still comparable to DBP-SCFG and also scales up well to large problem instances, thanks to our seamlessly integration of BP and DNNs within the message-passing framework which enables efficient parallel computation on GPUs In fact, when applied to scale-free networks, DABP (R- = 5) requires less runtime for all configurations, and has much lower growing rate (~~23811%) than DBP- self-supervised loss function for minimizing the smoothed cost, our DABP is able to infer the optimal hyperparameters that foster fast convergence, which also improves our model's efficiency.
k~37.37% )). Besides, equipped with the
Further Performance Analysis. We further compare the solution quality of different methods in each iteration and analyze the convergence rate of BP variants on the problem instances with X 803 in Fig. and Fig. 4 respectively. We omit the cases of DABP with R = 10 and R = 20 in Fig. 4 since they are similar to the one of DABP (R = 5). can be seen that DBP improves slowly and fails to find good solutions within 1000 iterations, especially on WGCPs, DBP-SCFG
'Tee results for the instances with |X| 60 and X
100 can be found in Appendix B.4

---

vEe
3.0-
Normat 500
2.5
Alt.alllen C012
-2
2.0
(1-10)
30
200
600
100
1.0
Eoratin
Bo utinn
Eoratonn
Ecrason
(a) Random COPs
(b) WGCPs
(c) SF networks
(d) SW networks
Figure 3: Solution quality comparison. Shaded areas show the 95% confidence intervals.
100
DRP
Colnee gonce (ME
DSP SCRG
CS gignt Tan (34
DABP (K-5)
02-
Ch OeAi
23
8
80
20
300
252
1000
100
250
520
1000
52
250
1000
120
250
930
2000
lmit
Raration
(a) Random COPs
(h) WGCPs
(c) SF networks
(d) SW networks
Figure 4: Convergence rates under different iteration limits.
substantially improves the convergence as well as solution quality of DBP by introducing another degree of freedom through asymmetric function splitting [9] On the other hand, our DABP allows more flexibility in composing BP messages by reasoning optimal dynamic hyperparameters through seamlessly integrating BP and DNNs, and it also significantly outperforms and converges much faster than both DBP and DBP-SCFG.
6 Conclusion
In this paper, propose DABP, the first self-supervised DNN-based BP for solving COPs. By allowing dynamic damping factors and different neighbor weights for each variable-node, our DABP strictly generalizes the state-of-ther DBP and has more fine- fineggriined control for composing new messages to trigger effective exploration without altering the semantic of BP messages. Moreover, by seamlessly integrating BP. GRUs and GATs within the massage-passaa to infer the optimal hyperparameters automatically according to the BP message dynamics. Finally, equipped with novel self-supervised loss function, our DABP does not require expensive training labels and can avoid out-of off-offiiittttiionn issue with efficient online learning. Extensive experiments confirm the great superiority of our DABP over the slate-of-the-at baselines.
framework, DABP is able
Since relies smoothed costs as the self-supervised loss function, our DABP is dedicated to solve COPs and is not trivial to be adapted for other scenarios. Therefore, in future will explore more training paradigms to extend our model to solve other important reasoning tasks over graphical models, e.g., computing partition function [50], and finding constrained most probable explanation [42]. It is also interesting to further boost the performance of our model by incorporating popular deep learning techniques such contrastive learning 3 and transformer [5
Acknowledgement
This research is supported by the National Research Foundation, Singapore under its Industry Align- Fund preppooitioning (IAF-PP) Funding Initiative. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore. The work of Caihua Liu supported and funded by Humanities and Social Sciences Youth Foundation, Ministry of Education of the People's Republic of China (Grant NJC800.C),,0,9. We also sincerely thank Professor Rina Dechter University of California, Irvine for her helpful discussions and suggestions.
10

---

References
[1] Srinivas M Aji and Robert McEliece. The generalized distributive law. JEEE Transactions on Information Theory, 46(2):325-34) 333, 2000.
[2] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In ICLR, 2015.
[3] Junwen Bai, Shufeng Kong, and Carla P Gomes. Gaussian mixture variational autoencoder with contrastive learning for multi-label classification. In ICML, pages 1383-1399 2022.
[4] Álszrt-Lászıó Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509-512 1999.
[5] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d' d'horizon. European Journal of Operational Research, 490-2):405-421, 2021.
[6] Dimitri P Bertsekas. Constrained Optimization and Lagrange Multiplier Methods. Academic Press, 2014.
[7] Ziyu Chen, Yanchen Deng, Tengfei Wu, and Zhongshi He. A class of iterative refined max- sum algorithms via non-consecutive value propagation strategies. Autonomous Agents and Multi-Agent Systems, 32(6):822-860) 2018.
[8] Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder- decoder for statistical machine translation. EMNLP, pages 1724-1734, 2014.
[9] Liel Cohen, Rotem Galiki, and Roie Zivan. Governing convergence of max-sum on DCOPs through damping and splitting. Artificial Intelligence, 279:103212, 2020.
[10] S. de Givry D. Allouche and T. Schiex. Toulbar2, an open source exact cost function network solver. Technical report, INRA, 2010.
[11] Rina Dechter. Bucket climination: A unifying framework for probabilistic inference. Learning in Graphical Models, 89:75-104, 1998.
[12] Rina Dechter, Kalev Kask, William Lam, and Javier Larrosa. Look-ahead with mini-bucket heuristies for MPE. In AAAI, 2016.
[13] Rina Dechter and Irina Rish. Mini-buckets: general scheme for bounded inference. Journal of the ACM, 5072) 2003.
[14] Yanchen Deng, Shufeng Kong, and Bo An. Pretrained cost model for distributed constraint optimization problems. In AAAI, pages 9331-9340, 2022.
[15] Yanchen Deng, Runsheng Yu, Xinrun Wang, and Bo An. Neural regret- matching for distributed constraint optimization problems. In ISCAI, pages 146-153, 2021.
[16] Alessandro Farinelli, Alex Rogers, Adrian Petcu, and Nicholas R Jennings. Decentralised coordination of low- low-power embedded devices using the Max-sum algorithm. In AAMAS, pages 639-646, 2008
[17] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[18] Natalia Flerova, Radu Marinescu, and Rina Dechter. Weighted heuristic anytime search: new schemes for optimization over graphical models. Annals of Mathematics and Artificial Intelligence, 79(1):7-1128 2017.
[19] Amir Globerson and Tommi S. Jaakkola. Fixing max- max-product: Convergent message passing algorithms for MAP LP-relxxations. In NIPS, pages 553-560, 2007.

---

[20] Tamir Hazan and Amnon Shashua. Norm corm-product belief propagation: Primal-dual message- passing for approximate inference. IEEE Transactions on Information Theory, 56(12):6294- 6316, 2010.
[21] Khoi D Hoang, Ferdinando Fioretto, William Yeoh, Enrico Pontelli, and Roie Zivan. A large neighboring search schema for multi-agent optimization. In CP, pages 688-706, 2018.
[22] Yoonheui Kim, Michael Krainin, and Victor Lesser. Effective variants of the max-sum algorithm for radar coordination and scheduling. In WI/IAT, pages 357-364, 2011.
[23] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXtv:1412.6980, 2014.
[24] Shufeng Kong, Jae Hee Lee, and Sanjiang Li. A deterministic distributed algorithm for reasoning with connected row-convex constraints. In AAMAS, pages 20
[25] Shufeng Kong, Jac Hee Lee, and Sanjiang Li. Multiagent simple temporal problem: The are-consistency approach. In AAAI, 2018.
[26] Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn to solve routing problems! In ICLR, 2019.
[27] Frank R Kschischang, Brendan Frey, and H-A Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions Information Theory, (77(2):48-5513 2001.
[28] Jonathan Kuck, Shuvam Chakraborty, Hao Tang, Rachel Luo, Jiaming Song, Ashish Sabharwal, and Stefano Ermon. Belief propagation neural networks. In NeurlPS, pages 667-678, 2020.
[29] Akshat Kumar and Shlomo Zilberstein. MAP estimation for graphical models by likelihood maximization. In NIPS, pages 180--1888, 2010.
[30] Eugene L Lawler and David E Wood, Research, 14(4):699-719, 1966.
methods: A survey. Operations
[31] Kathryn S. Macarthur, Ruben Stranders, Sarvapali D. Ramchurn, and Nicholas R. Jennings. A distributed anytime algorithm for dynamic task allocation in multi-agent systems. In AAAI, pages 701-706, 2011.
[32] David JC MacKay and David JC Mac Kay. Information theory, Inference and Learning Algorithms. Cambridge University Press, 2003.
[33] Pragnesh Jay Modi, Wei-Min Shen, Milind Tambe, and Makoto Yokoo. ADOPT: Asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence, 161(1-2):149 180, 2005.
[34] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' D'onoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012. 2020.
[35] Mark EJ Newman and Duncan J Watts. Renormalization group analysis of the small-world network model. Physics Letters A, 263(4-6):341-36, 1999.
[36] Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan kaufmann, 1988.
[37] Yasaman Razeghi, Kalev Kask, Yadong Lu, Pierre Baldi, Sakshi Agarwal, and Rina Dechter. Deep bucket elimination. In IJCAI, pages 4235-4242, 2021.
[38] Alex Rogers, Alessandro Farinelli, Ruben Stranders, and Nicholas R Jennings. Bounded approximate decentralised coordination via the max-sum algorithm. Artificial Intelligence, 175(2):700-759, 2011.
[39] Emma Rollon and Javier Larrosa. Improved bounded max-sum for distributed constraint optimization. In CP, pages 624-632, 2012.
12

---

[40] Emma Rollon and Javier Larrosa. Decomposing utility functions in bounded max-sum for distributed constraint optimization. In CP, pages 646 646-654, 2014.
[41] Francesca Rossi, Peter van Beek, and Toby Walsh. Handbook of Constraint Programming. Elsevier Science Inc., USA, 2006.
[42] Sara Rouhani, Tahrima Rahman, and Vibhav Gogate. A novel approach for constrained optimization in graphical models. In NeurlPS, pages 11949-119909 2020.
[43]
Victor Garcia Satorras and Max Welling. Neural enhanced belief propagation on factor graphs. In AISTATS, pages 685-693, 2021.
[44] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NeurlPS, pages 9998-6008,
2017.
[45] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. NeurIPS, 30, 2017.
[46] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[47] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In NeurlPS, pages 2692-2700, 2015.
[48] Martin Wainwright, Tommi Jaakkola, and Alan S Willsky. Tree-reweighted belief propa- gation algorithms and approximate ml estimation by pscudo-moment matching. In A/STATS, pages 308-315, 2003.
[49] Wim Wiegerinck and Tom Heskes. Fractional belief propagation. In NIPS, pages 438-445, 2002.
[50] Jonathan Yedidia, William T Freeman, and Yair Weiss. Constructing free-energy approxima- tions and generalized belief propagation algorithms. IEEE Transactions on Information Theory, 51(7):2282-2312 2005.
[51] Zhen Zhang. Fan Wu, and Wee Sun Lee. Factor graph neural networks. In NeurlPS, pages 8577-8587, 2020.
[52] Shlomo Zilberstein. Using anytime algorithms in intelligent systems. Al Magazine, 17(3):33-73 1996.
[53) Roie Zivan, Omer Lev, and Rotem Galiki. Beyond trees: Analysis and convergence of belief propagation in graphs with multiple cycles. AAAI, pages 7333-7340, 2020.
[54] Roie Zivan, Tomer Parash, Liel Cohen, Hilla Peled, and Steven Okamoto. Balancing exploration and exploitation in incomplete min/max-sui sum inference for distributed constraint optimization. Autonomous Agents and Multi-Agent Systems, 1655)1116- 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Sect. and Sect. S
(b) Did you describe the limitations of your work? [Yes] We have described our limitation in Sect. 6
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work theoretical and we do not see any potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
13

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Theorem page 7.
1
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes) See the Github
URL in page 2.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the Implementation paragraph in page 8.
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] We display the box-plot or the 95% confidence intervals when presenting cost performance.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] See the Benchmarks & Baselines paragraph.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "nJJ4X0k-_Zi", "reviewer": "Reviewer_jt6S", "summary": "The authors augment the max-sum algorithm with learning in order to solve COPs. The augmentation involves the used GRUs and GATs to produce an alternative, heavily parametric version of max-sum. The cost function can be expressed in terms of one-hot encodings of the solutions for each variable. A softened version of this cost is obtained by using the soft-max of the computed beliefs instead. The parameters of the GRUs and GATs can now be chosen to optimize this softened cost, thus directly using the cost to drive the learning, and not some golden target beliefs.", "questions": "1. Can you clarify if a single trained DABP is used in _all_ the experiments, or if a different one is used for each model type (or other approach)? Also, how many examples is it trained on? Or is it \"trained\" separately on each new instance to solve? All this wasn't clear to me from reading the paper.\n\n2. The provided time for DABP is the time to run inference only, or does it include the \"learning\" time?\n\n3. Why not test DBP with other damping parameters?\n\n4. Between DBP (essentially one parameter) and DABP (many many parameters), there seems to be a world of \"slightly flexible\" DBPs. Given the slim advantage of DABP over DBP, is DABP really the minimum amount of sophistication necessary to improve on DBP?\n\nMinor comment:\n- nature choice -> natural choice", "limitations": "Described above.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Technically correct\n- Clear presentation\n- Interesting problem \n- Does not rely on training data with correct solutions; thus potential to solve COPs that aren't solvable by other methods\n\nWeaknesses:\n\n- The competitor DBP is not pushed hard enough, for instance by exploring more damping factors\n- The small advantage obtained wrt DBP doesn't seem to justify all the additional machinery deployed. Also, DBP doesn't require training, can be deployed directly for any new architecture.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hEtc543WXkg", "reviewer": "Reviewer_DKJk", "summary": "The paper proposes a new belief propagation algorithm for COPs (constraint optimization problems), called DABP (deep attentive BP). DABP increases the granularity of the damping factors and neighbor weights by allowing them to be dynamic and specific for every variable node. The dynamic damping factors and neighbor weights are automatically inferred for each iteration by DNN, using GRUs (gated recurrent units) and GATs (graph attention network) and a multi-head attention layer. DABP uses novel smooth self-supervised learning loss, therefore avoiding the need for expensive training labels. The experimental evaluation shows that DABP achieves a high convergence rate and performs better than some SOTA baselines.", "questions": "1) It would be useful to include the memory consumption of the algorithms. In particular, how much memory does DABP use, main memory and GPU memory? Memory availability can impact the performance of some of the algorithms.\n\n- why did you limit MB i-bound to 9? Am I correct to assume that domain size 15, and i-bound 9 reaches the main memory limit? \nJust as a reference, for a more fair comparison, there are MB implementations that exploit GPU, e.g.:\nF. Bistaffa, N. Bombieri and A. Farinelli, \"An Efficient Approach for Accelerating Bucket Elimination on GPUs,\" in IEEE Transactions on Cybernetics, vol. 47, no. 11, pp. 3967-3979\n\n- My understanding is that Toulbar2 is a search based algorithm. Is Toulbar2 using caching during search? Do you know its memory usage?\n\n2) How many GPUs do you use in your setup? Do they have 24GB memory each? \n\n3) The networks are relatively small. How does DABP scale for bigger networks?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper combines and refines several existing schemes, while adding novelty items. The damping scheme is refined as much as possible by allowing node specific values for damping factors and neighbor weights. These values are learned for each instance, and the use of GRUs prevents the gradient vanishing issue. A smoothed cost is proposed as a surrogate objective, allowing the learning to happen in the absence of labels. \n\nThe presentation is clear, considering the need for relatively involved notation. The Figure 2 and the Algorithm 1 description are very useful. \n\nWeaknesses:\nThe significance of the proposal depends a lot on the experimental evaluation, which is quite extensive, but could benefit from some more clarifications, see questions. The size of the networks is still small, how far can DABP scale?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "bKU3YrpIsCM", "reviewer": "Reviewer_1zWz", "summary": "This paper proposed a deep attentive belief propagation (DABP) model for solving constraint optimization problems (COPs). The proposed DABP generalizes over damping belief propagation by considering dynamic damping factors. In addition, DABP considers different neighbor weights for optimal message composition. Both damping factors and neighbor weights are estimated via neural network units. DABP is trained in a self-supervised manner and the training loss is defined based on a smoothed surrogate of the original objective of COPs. Extensive experiments are performed to demonstrate the effectiveness of the proposal DABP. ", "questions": "## Theoretical justifications are insufficient\n1. It is not clear how dynamic damping factors improve the inference performance theoretically.\n\n2. Though weighted neural messages under a graph neural network framework have been shown to be effective in improving performance by existing works, the messages in belief propagation algorithm are not weighted for aggregation by theory. There is a lack of justification on weighting messages. Furthermore, it is not clear to me why the message weights should vary from iteration to iteration.\n\n3. Is there any theoretical justification on how the inference performance is affected by message weights? \n\n4. Since the proposed smoothed cost can be considered as a relaxation of the original objective of COPs, it would be good if the authors can provide theoretical justifications on how the inference error is introduced by the relaxation. \n\n## Some related works are missing\nExisting optimization-based algorithms are developed based on belief propagation algorithm. Messages and beliefs are improved from the variational belief propagation point of view, e.g., the tree-reweighted belief propagation [a] and factional belief propagation [b]. It would be better if the authors can provide a comparison between the proposed method and related works in revising messages / beliefs. \n\n> [a] Wainwright, Martin J., Tommi S. Jaakkola, and Alan S. Willsky. \"Tree-reweighted belief propagation algorithms and approximate ML estimation by pseudo-moment matching.\" International Workshop on Artificial Intelligence and Statistics. PMLR, 2003.\n\n> [b] Wiegerinck, Wim, and Tom Heskes. \"Fractional belief propagation.\" Advances in Neural Information Processing Systems 15 (2002).\n\n## Computational complexity\nThe training objective (Eq. 14) requires a summation over all $\\tau$ and $f$, which would be of high computational complexity. Can the proposed method scale up to large models?\n\n**Minor question:**\n1. In line 10, 'massage' should be 'message'.\n2. $M_\\theta$ in Eq. 7 is not explained. \n", "limitations": "The authors provide discussions on possible limitations of the proposed method.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths: \n**Clarity:** The paper is overall well written. The paper is easy to follow. \n\n**Novelty:** A smoothed cost objective is defined based on COPs. It is an interesting idea to leverage the smoothed cost objective for training without requiring annotations. Leveraging neural networks for improving classical well-established algorithms becomes an attractive topic recently. This paper introduces attention mechanism for improving belief propagation on factor graph, which could be of interest to other related researchers. \n\n## Weaknesses: \n**Technical originality:** The technical originality of the paper is marginal. The proposed method is an extension to damping belief propagation. Leveraging attentions to weight messages has been widely explored in different tasks [a].\n> [a] Zhang, Li, et al. \"Dynamic graph message passing networks.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2020. \n\n**Quality:** The quality of the paper can be improved in two aspects: 1) there are missing related works; 2) the proposed method is overall lack of theoretical justifications. \n\n**Significance:** The proposed DABP outperforms SOTA baselines only marginally while the computing time is significantly longer than SOTA baselines. In Table 1, on small-work networks with |X|=100, DABP achieves cost 25.65 which is slightly better than DBP-SCFG (cost = 26.13). However, DABP takes 7m31s while DBP-SCFG only takes 2m10s. The proposed training objective (Eq. 14) seems to be of high computational complexity. \n\n***I detail my comments on the weaknesses in the Question section below.*** \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2I5yS8kyQUN", "reviewer": "Reviewer_rbQp", "summary": "The authors propose a self-supervised DNN Based Belief Propagation solver for Constraint Optimization Problem. \nThey start from the Dumping Belief Propagation and define an approach to have a dynamic Dumping factor and neighbor weights for the computation of the messages.", "questions": "Rows 40-46 --> Please cite properly\n\nEquations --> The formalism used to describe the message could be misleading. Also to be coherent with the summation I suggest to use:\n$\\mu_{f_m \\rightarrow x_i}^{t-1}$ for message sent from factor node $f_m$ to variable node $x_i$. In the same way for the message from the variable node to the factor node.\n\nEquation 3 --> $\\mu_{x_j \\rightarrow f_l}^{t-1}$ is not introduced\n\nEquation 4 --> what is the meaning of the dependence $\\mu_{l \\rightarrow i}^{t-1}(\\tau_i)$ by $\\tau_i$? It is not described.\n\nUsually in the damping BP the weights of the old estimate and of the new estimate sum to 1. \n\nIn Eq.6 authors introduce a scaling factor that increases the contribution of the new estimates on the basis of the number of the neighbor nodes. This means that if there are a lot of neighbors the new estimate has higher contribution. The authors should describe better the rationale behind this choice.\n\nRow 217 --> Do the authors mean in term of time? The given motivation is related to the time to reach a solution.\n\nTable 1 - WGCP --> The test on this benchmark requires more discussion. The Toulbar2 outperforms other methods dramatically for |X|=60 and MBE require 0s... please check the results on this benchmark and discuss a little bit more on it.\n\nDBP presents little bit worse results (except for WGCP). Do the authors have used 0.9 as Dumping Factor but, since it is necessary to fine-tune this parameter (as they in stated in section 3), I'd like to see a test with different dumping factor because the selected dumping factor could be not a good choice. The same for DBP-SCFG.\n\nFig. 5 I suggest to increase the bars' width.", "limitations": "Authors described the main limitation, that the extension to other scenarios is not straightforward. \nThe extension will be study in the future works because deserve more investigations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The work is well organized and there are extensive experiments with different benchmarks and models.\nSome other experiments should be performed to have a fair comparison with simple DBP.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept