NeuroLifting: Neural Inference on Markov Random Fields at Scale

Q12：The time limit is set to 1200 seconds, consistent with the settings used in Toulbar2. We also employ 100 iterations, and the stopping criteria remain the same as those in our synthetic problems, which include an absolute tolerance of 1e-4 and a patience parameter of 10. We apologize for any ambiguity in the previous presentation.

MInor comments: Thank you for the reminders; we will correct them in the final version of our paper. The learning rate of 1×10−4 is denoted as 1e-4.

W stands for weakness, Q stands for question.

W1/Q2: We didn't provide the result of LBP and TRBP since it is hard for them to deal with high order MRFs with this magnitude. They reported error message even for the toy examples. That is why we have no test on the hard problems that listed in Tabel 2 and Table 3. You can see the result dsiplay on the website of OpenGM (http://old.ilastik.org/opengm/index.php?l0=benchmark)(the source of LBP and TRBP) , they only test these two methods on very simple high order MRFs.

W2: We have listed these statistics in the general response.

W3: The time limit is set to 1200 seconds, consistent with the settings used in Toulbar2. We also employ 100 iterations, and the stopping criteria remain the same as those in our synthetic problems, which include an absolute tolerance of 1e-4 and a patience parameter of 10. I apologize for any ambiguity in the previous presentation.

W4: We made this decision due to the page limit imposed at this stage, as we wanted to present as much content as possible in our paper. We will reorganize the structure in the official version to enhance clarity and presentation.

W5: See the answers for Q9 and Q10.

Q1: The tricks of GNNs won't change the properties of the original model since we have already transferred from the original problem to the optimization problem on the GNN.

Q3: Yes, the programme will terminate if the time exceeds the timelimit for all these methods.

Q4: The effects of different network structures are evident in the ablation study. The primary difference observed relates to convergence speed rather than the final results. We tested various initialization methods for the GNN, including uniform, Kaiming, and Xavier, but the differences between Xavier and Kaiming were minor(see Table 6 in the general response), which is why we did not include these results in the ablation study. Additionally, the initialization of the embeddings is also not particularly sensitive, as the results across the five trials in our experiments show minimal variation in most cases.**

Q5: The results presented in Table 2 indicate that as the graph density increases, it becomes more challenging for Toulbar2 to identify a feasible solution. This behavior is expected, given that Toulbar2 employs a branch-and-cut algorithm, and the difficulty may be linked to the specific techniques they apply to graphical models; however, we are not privy to their implementation details.

Q6: It is a typo here. The gap between these two terms is close given the experiment results, since after convergence, the GNN will assign very small probabilities to other labels. The contribution of these parts is minor. You can refer to the data we provide in the next question.

Q7 : We have listed all the losses and energies in tables in general response.

Q8: The computation of our model is straightforward. It consists of the time taken for the GNN to process the graph and the time required for loss calculation. For the GNN component, the time complexity is linear with respect to the number of nodes, which is evident. Similarly, the loss calculation involves simple tensor multiplication, resulting in a linear time complexity in relation to the number of items.

We are primarily analyzing the time complexity of our model. Notably, the time complexity for the LBP is also linear with respect to the node size, while the time complexity for the solver remains unknown."

Q9：In our experiments, we explored multiple padding strategies, including the approach of padding with infinities. While we discovered that our current padding strategy emerged as the most effective solution based on our evaluations. We have provided an explanation of our chosen method in the Remarks section of 3.2.

Additionally, we would like to propose another possible issue associated with padding using infinities. Specifically, when infinities are employed as padding values, even minor fluctuations in the neural network's output can lead to significant variations in the loss function. This sensitivity can complicate the optimization process, making convergence more difficult.

Q10: In our scenario, a situation may arise where the selection of different labels results in the same energy, indicating that the choice of label becomes irrelevant; we could simply choose one at random. However, this occurrence is not observed during our process, suggesting that it is uncommon. Consequently, the rounding scheme we employed is sufficient to select a valid configuration.

Q11: It is straightforward to see the scalability of NeuroLifting from the PCI instances and the synthetic problems. We get remarkable results for the cases from a few hundred nodes to 50k nodes and we test different densities for each of these cases under the same network settings. For efficiency part, each of these test has the same time limits as the competitors.

Thank you for your rebuttal. You have adequately addressed weaknesses W2 through W4, so I have adjusted my score to a 5. However, I still have questions regarding the remaining weaknesses, which I need you to address to increase your score further.

W1/Q2,

I appreciate why you cannot compare with LBP and TRBP in Table 2. Thanks for clarifying this. However, with the evaluation you've provided, W1 still stands. The claim that your method provides better solution quality against all baselines does not hold. For example, considering the error, Toulbar2 energy is well within the energy NeuroLifting achieves on H Instances 1 and 5. See the table below.

Q11

Regarding scalability, you have a strong case for outperforming approximate and exact methods. This is evident from your ability to perform inferences on all the graphs, whereas the other methods cannot. However, this point has not been stated clearly in your responses or the paper itself.

I can't entirely agree with your claim of achieving remarkable results. Your performance is worse than the baseline on smaller instances and only comparable to the exact method on 2 out of the 5 large graphs.

When it comes to efficiency, time-constrained experiments are not suitable for supporting this claim. To support the claim, you should provide timings.

Q9

Could you provide a reference or more details to support the claim that: "Specifically, when infinities are employed as padding values, even minor fluctuations in the neural network's output can lead to significant variations in the loss function."?

It is still unclear why your padding scheme is the only one that avoids pathological behavior. In Section 3.2, you mention that your scheme discourages selection from padded states by incentivizing the algorithm to choose the original, non-padded states with lower energies. You argue that the issue with alternative padding schemes is their tendency to dramatically alter the loss landscape, potentially leading to the selection of non-padded states. However, from my understanding, using a larger padding value should further incentivize the selection of low-energy, non-padded states.

Could you clarify what this dramatical alteration that can happen is?

First, I would like to thank the authors for the substantial additional evidence they have provided.

W1

"We achieved better results in the worst case among the five trials." This seems unusual, given that you report the standard error. However, the issue remains that the article asserts superior performance across the board without sufficient evidence to substantiate these claims. I recommend that the authors revise their manuscript to reflect their actual results more accurately, as this would significantly enhance the quality of the paper.

Q11

Thank you for sharing the timings. I would expect an efficient method to produce better results quicker than its alternatives. However, based on the experiment presented in Table 7, Toulbar2 consistently outperforms the NeuroLifting method at 200 seconds, indicating this expectation is not met. That said, I would agree with your perspective if efficiency were interpreted as the ability to integrate observations to achieve superior results.

Q9

Thanks for clarifying this point.

With the authors' latest rebuttal, I have no further questions. I would like to keep my score as is.

W stands for weakness.

W1: In this work, we do not transform the problem using traditional methods such as imposing relaxation or other transformations. Instead, we focus on transforming the original energy minimization problem by optimizing the neural network parameters to achieve the best mapping of node labels, thereby minimizing the loss. The lifting is accomplished through multiple layers of GNNs, which elevate the problem from node-level inference to the neural network parameters.

Consequently, these two problems are not equivalent; we utilize the transformed problem to approximate the original one. In the paper by Yann Dauphin et al. (2014), titled 'Identifying and Attacking the Saddle Point Problem in High-Dimensional Non-Convex Optimization' (https://arxiv.org/abs/1406.2572), the authors discuss the prevalence of saddle points in the landscape of neural networks, leading to ease of optimization using gradients. This insight highlights why gradient-based optimization is more manageable, forming the foundation of our method, and also somewhat inspired us to solve complex MRFs using neural networks with gradient backpropagation.

W2: The term 'non-parametric' does not imply the absence of tunable parameters within the model. Rather, it signifies that we do not require assumptions about the underlying population. Non-parametric methods do not depend on any specific parametric group of probability distributions and are often referred to as distribution-free tests due to the lack of assumptions regarding any underlying population. In our paper, we present a method that is distribution-free, making no assumptions about the MRF instances fed into our model. For further reading on non-parametric statistics, one can refer to the following resources:

• Non-parametric statistics - Wikipedia[https://en.wikipedia.org/wiki/Nonparametric_statistics]
• "Nonparametric Methods: The History, the Reality, and the Future (with Special Reference to Statistical Selection Problems)," page 63-83, available at: Springer Link.[https://link.springer.com/chapter/10.1007/978-3-642-46893-3_7]

W3: We apologize for the misleading wording used in the abstract, where we stated that we outperform the baselines in all cases. We actually outperform them in nearly all cases, and we will clarify this in the final version of the paper. In our experiments, we conducted a qualitative analysis focused on the number of iterations to compare convergence speed. The reason we did not compare execution time is that we are utilizing unoptimized Python code, while the baselines are implemented with fine-tuned C++ code even over decades. Therefore, directly comparing the execution times would not be fair.

W4:Sorry for that, 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 You are welcome to run the code and we look forward to your further suggestions. Since I'm not quite familiar with Lifting and MRFs, I will keep a low confidence score.

Q3: Even though Toulbar2 has Python 3 APIs, its backend code was written in C++ and has been kept optimized for decades. It means that the efficiency of Toulbar2 is attributed to the persistent contribution of researchers, programmers, and developers for a long period of time.

In our time comparison, we conducted tests on the inference times using Toulbar2 with the PCI instances, and the results are presented in Table 7, which you can find in our latest response to reviewer qPjP. We demonstrated improvements in both time efficiency and solution quality at scale, as reflected in the trends shown in the results.

The primary goal of our work is to validate the effectiveness of our method. While time efficiency is indeed a critical aspect, it is also a key focus for future development of our NeuroLifting method.

However, your advice on this point is valuable to us. The method clearly demonstrates the potential for efficient inference in large-scale problems, and there is significant room for further improvements in its efficiency. We will revise our manuscript to provide a more thorough discussion and presentation regarding the efficiency of our approach.

1. Regarding W1, could you please theoretically justify your statement "we utilize the transformed problem to approximate the original one"? It remains unclear how the alternative GNN optimization problem effectively approximates the original problem. Can you present any analysis, such as an approximation error bound or formal guarantees, to support the validity of the advocated NeuroLifting framework?

2. I disagree with the authors' claim that the GNN used in this manuscript is a non-parametric model. GNNs do make the assumption that the data are drawn from an unknown parametric distribution; see e.g., [1, 2]. A parametric model is a family of probability distributions that has a finite number of parameters [3]. The architecture of a GNN is fixed and independent of the dataset size, and thus belong to parametric models.

3. Toulbar2 also provides corresponding Python3 APIs. It is indeed unfair that no numerical tests are conducted to state that NeuroLifting "outperforms all existing approximate inference strategies in terms of solution quality without sacrificing computational efficiency".

The reason we did not compare execution time is that we are utilizing unoptimized Python code

Why don't you optimize your Python codes? This rationale does not justify omitting such a crucial comparison.

4. Thanks for the link, which addressed my concerns.

[1] S. Fan, X. Wang, C. Shi, P. Cui and B. Wang, "Generalizing Graph Neural Networks on Out-of-Distribution Graphs," T-PAMI.
[2] Y. Qin, X. Wang, Z. Zhang, P. Xie, W. Zhu, "Graph Neural Architecture Search Under Distribution Shifts", ICML.
[3] Parametric model - Wikipedia.

W stands for weakness, Q stands for question

W1: From the magnitude of instances in the UAI dataset and the real-world PCI instances, it is evident that the common MRF instances are not as large as those we have generated. For problems of this scale(up to 10k nodes with average degree 10), a single NVIDIA GeForce RTX 3090 24Gis capable of handling the computations effectively. In contrast, for larger-scale problems (50k nodes with average degree 10 or 100k nodes average degree 5), a single A100 80G is sufficient to manage the increased demands. Additionally, it's important to note that our current implementation of the code is written in Python (for research purpose) and has not been fully optimized, leaving significant room for further improvements. With targeted optimizations, we anticipate even better efficiency and scalability in handling these instances.

We believe that a neural-network-driven optimization framework for traditional MRFs is promising for even larger scale problems, especially with the fast development of modern AI chips.

W3:The primary motivation of our work is to address problems at scale, which are generally difficult for any traditional methods to our best knowledge. Such large-scale MRF problems broadly existing in the real world, but we are yet far from solving them nicely. This is why we include very dense graphs and graphs with a large number of nodes in the experiments conducted in Sections 4.1 and 4.3. For less challenging small problems beyond our main focus, existing solvers can readily be applied. The capability and flexibility of our model are well-suited to meet the large-scale needs of the current generation.

Q1/W2: In all the experiments presented in Sections 4.1 and 4.3, we utilized 5-layer GNNs with a maximum of 150 iterations, while Section 4.2 employed 8-layer GNNs with a maximum of 100 iterations. The other settings were kept consistent across all experiments. Our ablation study in Section 4.4 illustrates the performance differences using various GNN backbones, showing that the primary variation arises from convergence speed rather than final results. We also experimented with different initialization strategies for the network parameters, but they did not significantly affect the outcomes, which is why those details are not included in the main paper. This suggests that our method is not particularly sensitive to these factors.

Furthermore, our approach can be generalized to various MRF problems without extensive tuning, as demonstrated in Sections 4.1 and 4.3, where we applied the same settings to tackle MRFs of differing sizes, densities, and energy formulations.

Q2:We are making significant efforts to encompass a wide variety of graph types in our experiments. The performance tests for our method utilize cases from the UAI dataset, which includes a diverse range of MRF problems and represents a commonly accepted dataset in the community. For the generated problems, we experimented with Erdős–Rényi (ER) graphs of varying densities and different energy functions. Additionally, we incorporated real-world PCI problems, which feature distinct graph structures, alongside the generated problems and those from the UAI dataset. We are continuously working to acquire more real-world problems to further evaluate the performance of our method.

Q3: As discussed in Section 3.2 of our paper, we attempted to mask the padding portion and explored various padding strategies, including using infinities for padding. Unfortunately, none of these methods were able to produce a feasible solution. Our evaluations revealed that our current padding strategy has emerged as the most effective and suitable approach to be equipped with GNNs. The computation related to energy or loss is a challenging engineering problem, and addressing it would indeed be beneficial for enhancing the performance of our method.

Q4: This is indeed an excellent question and presents a valuable avenue for future work. We can define the energy function as $E(X) = \sum \theta_t(C)$. In this context, we differentiate between two types of time-varying MRFs. The first type features only minor changes in the $\theta_t$ parameters at each time step. In these scenarios, our method can be effectively applied, since MRFs are defined on local structures; thus, a small change in a specific part of the graph can significantly influence other areas. This enables us to leverage previous results as starting solutions.

Conversely, when a majority of the $\theta_t$ parameters are changing—regardless of whether these changes are smooth or abrupt—we will need to retrain the model, as the objective function itself is also evolving. Currently, our main focus is on static MRFs.

Q4 :In the paper you mentioned, the authors propose a self-supervised model capable of solving MPE (Most Probable Explanation) problems, similar to our approach. However, our perspectives are fundamentally different. Their motivation stems from the Learning to Optimize (L2O) method, which primarily involves inputting a problem instance into a neural network (NN) that then outputs a solution. In contrast, we employ Graph Neural Networks (GNNs) to perform the lifting process.

This distinction also leads to significant differences in our loss functions. Their loss function derives from traditional optimization techniques, specifically utilizing Lagrange multipliers to formulate an unconstrained problem. Our approach, however, is more straightforward; we ensure that the constraints inherent to Markov Random Fields (MRFs) are met through a carefully designed padding and rounding scheme. A detailed explanation of this aspect can be found in response to question 10 from reviewer qPjP. Moreover, our model is applicable to a broader range of MRFs, including high-order MRFs, while the authors of the other paper only test on smaller instances, all of which are restricted to pairwise MRFs.

We can include a discussion of these differences in the final version of our paper and have more papers in the related work.

W stands for weakness, Q stands for Question

W1: In this paper, we propose a method for performing MAP inference on large-scale Markov Random Fields (MRFs) based on Graph Neural Network (GNN) modeling and gradient-based Belief Propagation (BP). In this sense, our goal aligns with optimizating energies over MRFs in its standard context. Unlike traditional methods that rely solely on BP, which empirically demonstrate suboptimal performance with large-scale clique-based MRFs, our approach effectively addresses this issue especially on complex MRF instances at scale. Our method is applicable to any problem instance, and it demonstrates superior performance on large-scale MRFs, as shown in Tables 3, 4, and 5. If any aspects of our writing have caused confusion, we will revise them in the final version of this paper.

W2: We stated in the manuscript that MRFs can be factorized over both cliques and edges because we aim to explain the implementation details of our method rather than claim our novelty on this part. Empirically, problems defined on cliques tend to be more challenging to solve than those defined on edges. In Sections 4.1 and 4.2, we test our method on both pairwise MRFs and high-order MRFs to demonstrate its applicability to both types.

In essence, Equation (4) illustrates how LBP updates its node beliefs. We include this formula to highlight the message-passing scheme in LBP, which is an analogy in the message passing of GNNs. While there are significant differences in the message aggregation methods used in GNNs and LBP, within the LBP framework, nodes communicate by sending and receiving messages to and from their neighbors simultaneously in a parallel manner, akin to the approach employed in GNNs.

Q1: In Section 3.1, we provide a brief explanation of the figure, and here we would like to offer a more detailed version. Figure 1 illustrates the graph in both clique graph form and edge graph form, using a six-node graph that consists of three cliques as an example. The energy function displayed above the figure indicates that we only have clique energy in this case. Next, the graph is input into the Neural Networks. The Multi-Layer Perceptron (MLP) encodes the nodes, after which the graph passes through the Graph Neural Network (GNN). The final output is processed by a softmax layer. After obtaining the output, we round the network outputs to derive a configuration. Subsequently, we update the network parameters to minimize the loss function, such as the energy function.

We will revise the figure to ensure that it clearly conveys our ideas in the final version.

Q2: While lifting has indeed been established in the MRF domain, as briefly mentioned at the end of Section 2, this is not our main claim in this paper. However, we are the first to propose the application of Neural Networks for lifting to MRFs using multiple GNN layers, whereas existing works have primarily focused on lifting from a traditional optimization perspective (not a stack of GNN layers). This is why we refer to our approach as Neurolifting

The concept of the loss function is based on the traditional relaxation method of optimization. However, this approach may not be effective if we do not adequately address the challenges associated with high-dimensional problems and inconsistent dimensionalities. In the cited paper, the authors focus on pairwise relationships, which are relatively straightforward to implement.

In short, NeuroLifting seeks to lift original MRF problems with extra optimizable variables in GNN layers.

Q3/W3: In the field of machine learning, padding is a widely adopted technique that serves practical purposes in model training and data processing. Rather than being solely rooted in theoretical considerations, padding addresses various engineering challenges that arise during model implementation.

In our experiments, we explored multiple padding strategies, including the approach of padding with infinities. While we discovered that our current padding strategy emerged as the most effective solution based on our evaluations. We have provided an explanation of our chosen method in the Remarks section of 3.2.

Additionally, we would like to propose another possible issue associated with padding using infinities. Specifically, when infinities are employed as padding values, even minor fluctuations in the neural network's output can lead to significant variations in the loss function. This sensitivity can complicate the optimization process, making convergence more difficult. Of course, this instability originates from neural network itself.

We anticipate that this topic warrants a more thorough exploration, and we plan to include a detailed discussion on this matter in the final version of our paper.

Dear Reviewer jC41,

We appreciate your valuable time and thorough review. Our rebuttal is concise due to space limitations. However, if you have any remaining concerns or questions, we are more than willing to provide additional clarification. We greatly value your input and would appreciate any further suggestions or comments you may have regarding enhancing our manuscript.

Best regards.