NeuroLifting: Neural Inference on Markov Random Fields at Scale

Authors: Yaomin Wang, Chaolong Ying, Xiaodong Luo, Tianshu Yu
Primary area: optimization
Keywords: Markov Random Fields, unsupervised learning, discrete optimization

Abstract:
Inference in large-scale Markov Random Fields (MRFs) is a critical yet challenging task, traditionally approached through approximate methods like belief propagation and mean field, or exact methods such as the Toulbar2 solver. These strategies often fail to strike an optimal balance between efficiency and solution quality, particularly as the problem scale increases. This paper introduces NeuroLifting, a novel technique that leverages Graph Neural Networks (GNNs) to reparameterize decision variables in MRFs, facilitating the use of standard gradient descent optimization. By extending traditional lifting techniques into a non-parametric neural network framework, NeuroLifting benefits from the smooth loss landscape of neural networks, enabling efficient and parallelizable optimization. Empirical results demonstrate that, on moderate scales, NeuroLifting performs very close to the exact solver Toulbar2 in terms of solution quality, significantly surpassing existing approximate methods. Notably, on large-scale MRFs, NeuroLifting delivers superior solution quality against all baselines, as well as exhibiting linear computational complexity growth. This work presents a significant advancement in MRF inference, offering a scalable and effective solution for large-scale problems.

Decision: reject
Reviewer scores: 3, 6, 3, 5

Reviews and discussion:
<thread>
creation date:
1729875535236

thread_type:
official_review

<thread_object>
creator: reviewer_qpjp

<content>
summary:
The paper investigates approximating Markov random fields (MRF) by optimizing a graph neural network (GNN) to maximize a surrogate to its joint density. 
It suggests using learnable padded embeddings of the MRF decision variables as GNN features, allowing gradient-based optimization. 
The paper claims that:
 1. It is the first to introduce neural network-based lifting to MRF inference.
 2. The approach, called NeuroLifting, simplifies the optimization process for large MRFs.
 3. Loss computation with NeuroLifing scales linearly with the MRF nodes and enables parallelization and GPUs accelerated computation.
 4. It empirically demonstrates that NeuraLifing finds near-optimal solutions on moderate-size MRFs and solutions superior to baselines on large MRFs.

strengths:
- The central idea of embedding decision variables in an MRF to use a GNN is original.
- The selection of GraphSAGE for convolution is well justified and supported by empirical results (Figure 3).

weaknesses:
## Reasons for score
- The abstract states that NeuroLifing "delivers superior solution quality against all baselines" on large-scale MRFs. However, Table 1 does not show this, and two baselines (LBP and TRBP) need to be included in Table 2. Please consider modifying the abstract to reflect your results better. For example, you could restrict your claim to Toulbar2, i.e., exact methods.
- The experimental results lack standard error estimation, which makes method comparison difficult because it's hard to judge the significance of the difference in energy. Considering your method is probabilistic, you could use multiple initializations to estimate the standard error.
- A convergence criterion needs to be clearly stated for NeuroLifting UAI22 dataset. 
- Related work is delegated to the appendix.
- It needs to be clarified whether NeuroLifing is guaranteed to produce a valid solution. In particular,
  - Please explain how the padding scheme suggested produces only valid solutions, but padding with the largest of all energies can produce infeasible solutions.
  - Please explain with evidence (either theoretical or empirical) how the rounding scheme for $p_i(\theta)$ avoids multi-assignment issues.

questions:
1. Does a GNN with jumping knowledge preserve the Markov assumption?
  2. Why does Table 2 not include LBP and TRBP?
  3. Was a hard time constraint of 1200 seconds enforced for LBP, TRBP and NeuroLifing?
  4. Is NeuroLifing sensitive to the initialization of the embeddings and network?
  5. Why does Toulbar2 fail on H_Instances_2? 
  6. Table 1 reports "the final loss given by the loss function," whereas the other tables report the final energy. It needs to be clarified that the distinction between loss and energy exists for the baseline methods. If so, what is the gap between loss and energy?
  7. What is the gap between loss and energy for NeuroLifting on synthetic, UAI and PCI? 
  8. The interpretation of the linear complexity needs to be clarified. By mentioning the linear complexity in node size, is the paper claiming an asymptotic improvement over alternatives? 
  9. How does the suggested padding scheme produce only valid solutions, whereas padding with the largest of all energies can produce infeasible solutions?
  10. How does the rouding scheme for $p_i(\theta)$ avoid multi-assignment issues?
  11. What does "showing remarkable scalability and efficiency" mean in (lines 71-72)? What is the concrete evidence that shows this claim?
  12. What stopping criteria are used for NeuroLifting on UAI?

##  Minor comments (did not affect score)
  1. Tables 1, 2, 3 and 4 would be more legible and convey the same results if reported as whole numbers instead.
  2. Capitalize the titles of the references.
  3. Use only one of: `DOI:`, `ISBN` or neither for book references. 
  4. The caption for Figure 1 should describe the stages in the diagram. Figure 2 does this well. 
  5. In Figure 1 $\mathcal{P}$ and $H$ are not defined. 
  6. Cross entropy is not defined.
  7. In eq. 5, $v_i(\theta)$ is a mapping, but above $v_i$ is defined as a bit string (not a mapping).
  8. Cliques should be capitalized in Tables 1, 2, 4 and 5.
  9. $\mathcal{X}$ is not clearly defined. From the padding paragraph and section 3.4, it looks like it should be $x_i \in \mathcal{X}_i$ and $\mathcal{X} = \cup_i \mathcal{X}_i$.
  10. Table 5 should use scientific notation.
  11. Is the learning rate really $1e^{-4} \approx 0.018$ in 4.1?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730147124183

thread_type:
official_review

<thread_object>
creator: reviewer_hycv

<content>
summary:
This paper focuses on the inference in large-scale Markov Random Fields (MRF), where conventional methods often suffer from either efficiency or solution accuracy. To address this issue, this paper advocates mapping the inference of MRF to a Graph Neural Networks (GNNs), which enables smooth loss landscape and scalable inference. Numerical experiments on several datasets showcases that the proposed NeuroLifting presents comparable performance to the non-scalable exact solver Toulbar2.

strengths:
1. The organization of this paper is clear, and the writing is easy to understand. 

2. The figures and the example provided in figure 1 are helpful for understanding the paper.

weaknesses:
Several parts of the paper are confusing, as listed one-by-one below. 

1. When introducing Lifting in Section 2, it is stated that "Lifting reformulates an optimization problem into a more tractable form by introducing auxiliary variables or constraints, making the optimal solutions more accessible." However in Section 3.3, the high-dimensional feature vectors are learnable and randomly initialized, without any guarantee on the equivalence between the original problem and the alternative GNN optimization problem. It would be beneficial if some theoretical analysis can be provided to ensure the GNN is actually/approximately solving the original problem, or an equivalent problem. In the current version, there is not even an objective function for the alternative optimization problem, making it hard to connect this paper with "Lifting". 

2. This paper claims that NeuroLifting is a "non-parametric" method. Nevertheless, line 249 argued that "we optimize both the GNN parameters and those of the encoder," which conflicts with the proceeding claim.  

3. Line 61 says that NeuroLifting "outperforms all existing approximate inference strategies in terms of solution quality without sacrificing computational efficiency." In the experiments, only the time limit for the exact solver Toulbar2 is reported, while it is unclear how NeuroLifting compares to conventional approaches in terms of both time and space complexities. 

4. No codes or supplementary files are provided along with the submission. As a result, the reviewers cannot verify the results reported in the manuscript. 

Since I'm not quite familiar with Lifting and MRFs, I will keep a low confidence score.

questions:
See Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730561026263

thread_type:
official_review

<thread_object>
creator: reviewer_fwqz

<content>
summary:
The paper introduces NEUROLIFTING, a novel inference method that leverages Graph Neural Networks (GNNs) to optimize decision variables in large-scale MRFs. in contrast traditional methods, such as belief propagation and Toulbar2, which struggles to balance efficiency and solution quality as MRFs scale, NEUROLIFTING reparameterizes MRF variables with GNNs which enables efficient optimization using gradient descent while taking advantage of the smooth neural network landscape. This approach shows competitive results against exact solvers on smaller problems and superior performance on larger ones, with linear computational complexity growth.

strengths:
* NEUROLIFTING introduces a new way to approach MRF inference by incorporating GNNs, enhancing scalability and parallelism compared to traditional methods.

*  Empirical results indicate that NEUROLIFTING consistently outperforms approximate inference methods in terms of solution quality and closely matches exact solvers on smaller instances.

*  The model shows linear growth in computational complexity, making it well-suited for large-scale MRFs.

* The method effectively transforms high-order graphs into a GNN-compatible format, expanding its applicability across various MRF-based problems.

weaknesses:
* The use of GNNs, especially for large graphs, may still introduce significant computational costs and memory requirements, potentially limiting applicability in extremely large or resource-constrained environments.

* The effectiveness of NEUROLIFTING could be sensitive to the choice of GNN architecture, number of layers, and feature dimensions, which might require extensive tuning.

* Although NEUROLIFTING outperforms existing methods on large problems, there may be cases where it still falls short of the accuracy provided by exact solvers, especially on smaller and well-structured graphs.

questions:
1. How sensitive is NEUROLIFTING's performance to different GNN architectures and hyperparameters? Can it be generalized across various MRF problems without extensive tuning?

2. How does the model perform on MRF instances with unique or less common graph structures that differ significantly from those used in the empirical tests?

3. Are there alternative ways to optimize the energy function or refine the padding strategy to further enhance efficiency or solution quality?

4. Could the NEUROLIFTING framework be extended to handle dynamic graphs or incorporate temporal information for applications in time-varying MRFs?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731130859654

thread_type:
official_review

<thread_object>
creator: reviewer_jc41

<content>
summary:
The authors propose a GNN based approach to approximate MAP inference in MRFs.  The contribution definitely follows recent trends in trying to use NNs to approximately solve hard problems, it falls a bit short in its treatment of historical work and references to modern approaches.  Overall, the presentation needs quite a bit of improvement.

strengths:
- The proposed approach is a novel combination of optimization ideas with modern NN approaches.

- The authors provide a wide array of experimental results across different domains and both synthetic and real data.

weaknesses:
- Some of the text looks like it was fed into an MRF for "improvement," but it reads a bit awkwardly and uses imprecise statements.  Even if this isn't the case, I would suggest tidying it up a bit so as to make it read more like a traditional technical paper.

- The descriptions of MRFs and related work is poor.  Some parts of the discussion make it seems like some of the ideas being presented are novel to the community when they aren't really.  For example, the authors define MRFs factorizing over the cliques of a graphs and then claim novel insights that these cliques can be subdivided into edges when representing the graph.  This is, of course, what it means to be a clique in a graph.  Equation (4) isn't the standard loopy BP representation where inference is no longer exact (it isn't even clear why you need this formula anyway).  Saying that message passing looks like GNNs when it is in fact the other way around by design. Among many others.

- Some of the decisions made in the setup, e.g., the padding seem like that could lead to poor results in practice.  There is a comment about this in the paper, but the chosen method seems significantly suboptimal to me especially when the range of values that each potential function can take is small.

questions:
- Figure 1 is really difficult to understand.  

- I don't love calling this approach NeuroLifting because the are already "lifted" methods in relational MRFs.  I'm not sure what else I would call this, but given the long history in that domain optimization lifting strategies are not the first things that come to my mind when I hear the name.  Equation (6) is quite similar to traditional MAP relaxations (some of which are actually cited).  Saying

- Can you further explain the issues that arise with padding?  It seems clear that padding essentially with infinities is the correct theoretical thing to do -- what is the practical issue here?

- Lots of references should probably be added.  Here's one that is somewhat related to help get you started:

Arya, S., Rahman, T. &amp; Gogate, V.. (2024). Learning to Solve the Constrained Most Probable Explanation Task in Probabilistic Graphical Models. <i>Proceedings of The 27th International Conference on Artificial Intelligence and Statistics</i>, in <i>Proceedings of Machine Learning Research</i> 238:2791-2799 Available from https://proceedings.mlr.press/v238/arya24b.html.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731682612292

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Table 4 High-order cases of UAI 
|Graph | Neurolifting Loss | Energy |
|---------------------------------------------------------------------------------|--------------------------------------|------------------------------------|
|Maxsat\_gss-25-s100   |-139904.266 $\pm$ 1717.483 | -139914.341 $\pm$ 1710.139 |
|BN-nd-250-5-10        | 189.395 $\pm$ 5.424 | 187.729 $\pm$ 4.966 |
|Maxsat\_mod4block\_2vars\_10gates\_u2\_autoenc         | -146166.620 $\pm$ 41250.035 | -146166.797 $\pm$ 41249.859|
|Maxsat\_mod2c-rand3bip-sat-240-3.shuffled-as.sat05-2520      | -3511.994 $\pm$ 220.654 | -3511.822 $\pm$ 220.471 |
|Maxsat\_mod2c-rand3bip-sat-250-3.shuffled-as.sat05-2535       |-3686.567 $\pm$ 166.998 | -3686.085 $\pm$ 166.499 |

Table 5 PCI cases with error
|Graph | Neurolifting Loss | Energy |
|-------------------|-----------------------------|-------------------------------|
|PCI\_1             |  18.851 $\pm$ 0.101 |   18.841 $\pm$ 0.095 | 
|PCI\_2             |  100.167 $\pm$ 0.685 | 100.151 $\pm$ 0.693 |
|PCI\_3             |  1010.757 $\pm$ 1.665 | 1010.687 $\pm$ 1.637 |
|PCI\_4             |  421.030$\pm$ 5.650| 420.734 $\pm$ 5.356 |
|PCI\_5             |  1109.976 $\pm$ 22.260 | 1108.144 $\pm$ 20.298 |

Table 6 GNN loss using different parameter initialization
|Graph Type |    Uniform | Kaiming | Xavier |
|--------------------|-------------------------------------------------|---------------------------------------------------|------------------------------------------------|
|Synthetic data |    -62706.173 $\pm$ 12540.261          |     -89331.936 $\pm$ 1059.104           |   -89276.337 $\pm$ 1117.219           |
|UAI                    |     11618.903 $\pm$ 25179.166         |        -39010.959 $\pm$ 372.373        |       11618.903 $\pm$ 25179.166       |
|PCI                    |      3045.851 $\pm$ 202.735        |       2642.396 $\pm$ 9.121        |     2643.387 $\pm$ 8.315       |
</content>
</thread_object>

</thread>
<thread>
creation date:
1731682663375

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
The tables below correspond to their respective tables in the paper, presenting the loss from the loss function we designed alongside the corresponding energy values. Each box includes the standard error to illustrate the sensitivity of our model to the different initializations. As evident from these results, the discrepancy between the loss and the actual energy is minimal. Moreover, almost all the energy errors are below 1% when compared to the average energy values.

Table 6 presents the performance of our model using three different initialization methods: uniform initialization, Kaiming initialization, and Xavier initialization. As observed, the performance with both Kaiming and Xavier initializations is quite similar. Since both methods are commonly used, we did not emphasize this finding in our paper.

Here is the anonymous link to the code of our model.
https://anonymous.4open.science/r/NeuroLifting-Neural-Inference-on-Markov-Random-Fields-at-Scale-160C

Table 1 synthetic pariwise cases with error

|Graph          | Neurolifting loss| Energy |
|-----------------| --------------------------------------|--------------------------------------|
|P_potts_1|      -21791.868 $\pm$ 218.106  | -21799.268 $\pm$ 216.075 |
|P_potts_2|      -105762.092 $\pm$ 434.674    | -106016.855 $\pm$ 168.861 |
|P_potts_3|      -211406.914  $\pm$ 1489.099    |  -210182.681 $\pm$ 275.164 |            
|P_potts_4|      12219.817  $\pm$ 538.969  | 11811.682  $\pm$ 123.877  |
|P_potts_5|      12010.036 $\pm$ 266.610    | 11673.708 $\pm$ 146.513  |
|P_potts_6|      18399.913 $\pm$ 1475.526    | 16988.347 $\pm$ 163.587 |
|P_potts_7|      17480.701 $\pm$ 212.084    | 17265.434 $\pm$ 140.904  |
|P_potts_8|      26115.840 $\pm$ 1677.627   |  24668.087 $\pm$ 163.587 |
|P_potts_9|      26348.525 $\pm$ 1095.319   | 25189.789 $\pm$ 132.693 |
|-----------------| --------------------------------------|------------------------------------- |
|P_random_1 | -4570.079 $\pm$ 31.228 | -4574.664 $\pm$ 31.411|
|P_random_2 | -21774.416 $\pm$ 52.910 | -21798.702 $\pm$ 32.389 |
|P_random_3 | -41953.991  $\pm$ 237.577 | -41972.379 $\pm$ 216.574 |
|P_random_4 | 12552.252 $\pm$ 30.311 | 11983.388$\pm$ 213.454 |
|P_random_5 | 12308.580 $\pm$ 14.045 | 11945.450 $\pm$ 194.481 |
|P_random_6 | 17705.219 $\pm$ 435.560  | 17207.997 $\pm$ 405.217 |
|P_random_7 | 18343.026 $\pm$ 1448.821 | 16971.435 $\pm$ 209.021 |
|P_random_8 | 25949.446 $\pm$ 995.956 | 24787.343 $\pm$ 163.587 |
|P_random_9 | 25871.264 $\pm$ 1087.915 |  24811.354 $\pm$ 171.315 |

Table 2 synthetic high-order cases with error
|Graph | Neurolifting Loss | Energy |
|-----------------| --------------------------------------|------------------------------------- |
|H_Instances_1 |   -29844.092 $\pm$ 450.184 | -29854.202 $\pm$ 450.079 |
|H_Instances_2 |   -20260.289 $\pm$ 143.276 | -20286.571 $\pm$ 143.624 |
|H_Instances_3 |   -3432.3205 $\pm$ 9.520| -3611.379 $\pm$ 9.654 |
|H_Instances_4 |   9975.517 $\pm$ 80.854 | 9754.885 $\pm$ 27.806 |
|H_Instances_5 |   10403.888 $\pm$ 798.812 | 10217.842 $\pm$ 848.029 |

Table 3 UAI cases with error
|Graph | Neurolifting Loss | Energy |
|-----------------| --------------------------------------|------------------------------------- |
|ProteinFolding_11 | -3976.908 $\pm$ 52.047 | -4018.784 $\pm$ 36.491 |
|ProteinFolding_12 | 16137.682 $\pm$ 16.020 | 16090.801 $\pm$ 22.869 |
|Grids_19                 | -2400.251 $\pm$ 20.061 | -2398.078 $\pm$ 16.010 |
|Grids_21                 | -16592.926 $\pm$ 94.368 | -16605.564 $\pm$ 113.096 | 
|Grids_24                 | -16323.767 $\pm$ 171.950 | -16222.104 $\pm$ 222.593 | 
|Grids_25                 | -2361.900 $\pm$ 10.231 | -2361.055 $\pm$ 12.678 | 
|Grids_26                 | -2595.041 $\pm$ 43.306 | -2577.378 $\pm$ 39.370 |
|Grids_27                 | -10898.595 $\pm$ 160.435 | -10771.257 $\pm$ 170.329 |
|Grids_30                 | -2651.035 $\pm$ 35.508 | -2676.246 $\pm$ 19.886 |
|Segmentation_11    | 432.291 $\pm$ 34.208 | 391.971 $\pm$ 40.099 |
|Segmentation_12    | 147.531 $\pm$ 26.215 | 128.759 $\pm$ 36.213 | 
|Segmentation_13    | 147.845 $\pm$ 6.298 | 118.685 $\pm$ 34.864 |
|Segmentation_14    | 105.203 $\pm$ 7.717 | 103.269 $\pm$ 8.121 |
|Segmentation_15    | 417.276 $\pm$ 22.357 | 408.214 $\pm$ 27.037 |
|Segmentation_16    | 113.389 $\pm$ 4.81 | 108.415 $\pm$ 8.77 |
|Segmentation_17    | 494.82 $\pm$ 20.158 | 478.881 $\pm$ 42.455 |
|Segmentation_18    | 104.201 $\pm$ 2.692 | 97.555 $\pm$ 6.364 |
|Segmentation_19    | 96.173 $\pm$ 4.731 | 84.882 $\pm$ 10.063 |
|Segmentation_20    | 358.238 $\pm$ 34.148 | 320.027 $\pm$ 21.219 |
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces NEUROLIFTING, a technique using GNNs to optimize inference in large-scale MRFs. By reparameterizing decision variables and enabling gradient-based optimization, NEUROLIFTING achieves efficient, parallelizable performance. Empirical results show it matches exact solvers on moderate scales and outperforms the existing large-scale MRFs.

Although the paper's approach to inferring large-scale MRFs using GNNs is interesting, the reviewers highlighted the following main weaknesses:

1. One reviewer criticized the poor description of MRFs and related work, noting that some ideas presented as novel are already well-known in the community.
2. Another reviewer questioned the validity of the lifting method, highlighting the lack of theoretical justification for the equivalence between the original problem and the GNN-based optimization.
3. Several reviewers pointed out the absence of thorough experimental evaluation.
4. A reviewer challenged the claim that the proposed method is non-parametric.