Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:

- Technically correct
- Clear presentation
- Interesting problem 
- Does not rely on training data with correct solutions; thus potential to solve COPs that aren't solvable by other methods

Weaknesses:

- The competitor DBP is not pushed hard enough, for instance by exploring more damping factors
- 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.

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.

2. The provided time for DABP is the time to run inference only, or does it include the "learning" time?

3. Why not test DBP with other damping parameters?

4. 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?

Minor comment:
- nature choice -> natural choice
limitations: Described above.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
The 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. 

The presentation is clear, considering the need for relatively involved notation. The Figure 2 and the Algorithm 1 description are very useful. 

Weaknesses:
The 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?

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.

- 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? 
Just as a reference, for a more fair comparison, there are MB implementations that exploit GPU, e.g.:
F. 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

- My understanding is that Toulbar2 is a search based algorithm. Is Toulbar2 using caching during search? Do you know its memory usage?

2) How many GPUs do you use in your setup? Do they have 24GB memory each? 

3) The networks are relatively small. How does DABP scale for bigger networks?
limitations: N/A
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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. 
strengths_and_weaknesses: ## Strengths: 
**Clarity:** The paper is overall well written. The paper is easy to follow. 

**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. 

## Weaknesses: 
**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].
> [a] Zhang, Li, et al. "Dynamic graph message passing networks." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2020. 

**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. 

**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. 

***I detail my comments on the weaknesses in the Question section below.*** 

questions: ## Theoretical justifications are insufficient
1. It is not clear how dynamic damping factors improve the inference performance theoretically.

2. 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.

3. Is there any theoretical justification on how the inference performance is affected by message weights? 

4. 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. 

## Some related works are missing
Existing 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. 

> [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.

> [b] Wiegerinck, Wim, and Tom Heskes. "Fractional belief propagation." Advances in Neural Information Processing Systems 15 (2002).

## Computational complexity
The 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?

**Minor question:**
1. In line 10, 'massage' should be 'message'.
2. $M_\theta$ in Eq. 7 is not explained. 

limitations: The authors provide discussions on possible limitations of the proposed method.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors propose a self-supervised DNN Based Belief Propagation solver for Constraint Optimization Problem. 
They 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.
strengths_and_weaknesses: The work is well organized and there are extensive experiments with different benchmarks and models.
Some other experiments should be performed to have a fair comparison with simple DBP.
questions: Rows 40-46 --> Please cite properly

Equations --> The formalism used to describe the message could be misleading. Also to be coherent with the summation I suggest to use:
$\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.

Equation 3 --> $\mu_{x_j \rightarrow f_l}^{t-1}$ is not introduced

Equation 4 --> what is the meaning of the dependence $\mu_{l \rightarrow i}^{t-1}(\tau_i)$ by $\tau_i$? It is not described.

Usually in the damping BP the weights of the old estimate and of the new estimate sum to 1. 

In 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.

Row 217 --> Do the authors mean in term of time? The given motivation is related to the time to reach a solution.

Table 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.

DBP 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.

Fig. 5 I suggest to increase the bars' width.
limitations: Authors described the main limitation, that the extension to other scenarios is not straightforward. 
The extension will be study in the future works because deserve more investigations.
review_title: null

Meta-review: metareview: 4 knowledgable reviewers reviewed the paper, 3 of them recommending weak acceptance, 1 borderline rejection. The reviewers engaged with the authors and a discussion among the reviewers took place. The reviewers appreciate the considered problem, the novelty of the proposed approach and the reported performance improvements. At the same time, there are concerns regading the theoretical justifcation of the method, relation to existing work, and comparison with other existing methods (lacking baselines and pushing the baselines to the limit). There was a discussion regading the need for a theoretical justification and I side more with the reviewers which argue that such a justification is not absolutely necessary -- nevertheless, more motivation and intutition about the proposed approach should still be provided. In summary, the paper is viewerd borderline, which I agree with, but I think there are some relevant contributions which could be interesting to the community. Hence I am recommending acceptance of the paper but strongly encourage the authors to carefully consider all comments and suggestions which came up in the reviews and discussions with the reviewers when preparing the final version of their paper.
confidence: Less certain
Decision: Accept