- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper proposes a method for discrete energy minimization that combines a graph neural network to update free logits through a process called residual GNN lifting. A number of theoretical results are presented with proofs included in the appendix. Experimental results show that the method is competitive with older message passing approaches such as LBP and TRBP, and more recent solvers (toulbar2), although move making (alpha expansion, etc.), primal-dual optimization approaches (e.g., Komodakis et al.) and cutting-plane methods (e.g., Sontag et al.) are missing. The experimental results also do not go so far as to validate details of the theory itself.
Critical strengths
- The paper proposes a novel approach for discrete energy minimization that combines graph neural networks with an efficient second-order pre-conditioner. Moreover, the approach is supported by theoretical statements that are proved.
- Empirical results show that the method is competitive with standard message passing approaches on standard benchmarks.
Critical weaknesses
-
I found the paper very difficult to read. Many technical terms and notation are introduced before they are defined. Moreover, there are several places where the same variable is used in very different contexts. For example, a. Phrases in the abstract such as "this residual bypass is a global change of coordinates, so the lifting preserves the infimum, critical points, local extrema (modulo the GNN-parameter fiber), and Hessian inertia of the free-logit problem" and "the GNN cannot enlarge the feasible set" make no sense out of context. Also , and are all undefined in the abstract. b. The expression is used several times before any of the terms are defined. c. Variables suggest the same cardinality for all variables, which contradicts the earlier suggestion that the work addresses heterogeneous label cardinalities (later corrected by introducing variables ). d. Symbols and are used to represent different objects at different places in the paper.
-
Experimental results are lacking. a. I would have liked to have seen results from primal-dual methods and move-making algorithms reported. b. Table 1 claims REMAP is reported as the best of fix seeds. Other methods should similarly be given the benefit of multiple starting seeds/configurations. c. The experiments don't really validate the theory itself, only that the method is competitive with other approaches. It would be good to link empirical observations to some of the bounds and results derived in Section 4.
Questions for authors
Please address the concerns raised above. Namely, that notation and writing can be improved as evidenced by the quality of the rebuttal, and experimental findings especially with respect to empirical validation of the theory.
2 comments
W2(c) Experimental Validation of the Theory
Response. Thank you for this suggestion. We agree that competitiveness comparisons alone do not directly validate the theoretical mechanism. We have therefore added Section 5.5, “Empirical diagnostics of the theoretical prediction” (Figures 2–3), and Appendix I, “Multi-seed validation of the local descent prediction” (Figure 6). These additions are marked in red in the revised manuscript.
The new experiments directly examine the dissipation identity in Theorem 4.6, Eq. (16). Using the notation of Section 4, we define
,
where , and and are the squared gradient norms associated with node embeddings and shared GNN weights, respectively. Thus, is precisely the diagnostic alignment ratio introduced in Section 4. At a fixed checkpoint, the corresponding first-order predictions for ordinary-gradient probes are
so the predicted extra decrease in the relaxed objective is . We test this connection in three complementary ways:
-
Predicted versus measured extra descent (Section 5.5, Figure 2). At sampled Adam training checkpoints, we initialize the free and residual branches at identical logits and apply independent ordinary-gradient probes, each starting afresh from the checkpoint. Figure 2 displays the individual checkpoint–step-size pairs for seed 1211 on PCI.1–PCI.5. Smaller-step probes closely track , whereas larger steps exhibit greater deviations, including negative extra descent at some checkpoints. Valid nonpositive measurements are retained in the error analysis, although they cannot appear on the logarithmic vertical axis.
-
Multi-seed quantitative agreement on fixed checkpoint subsets (Appendix I, Figure 6). We repeat the analysis for five seeds, , using the relative discrepancy Within each instance–seed pair, we use the same checkpoints at every tested step size: all required diagnostic quantities must be finite and at every step size. This prevents step-size-dependent filtering from changing the checkpoints being compared. We first compute the median error within each seed and then aggregate across seeds, rather than treating checkpoints as independent replicates. Across all five instances, the aggregate error generally decreases as the probe step size is reduced, supporting the local first-order prediction without claiming strict monotonicity or a particular convergence order.
-
Magnitude and source of the additional dissipation (Section 5.5, Figure 3). We report and the components , , , and over the five seeds. Ratios are computed within each seed before aggregation. Across the displayed checkpoints and seeds, remains far above one, and the additional term is dominated by the shared-weight contribution . This shows that the additional dissipation term in Theorem 4.6 is substantial relative to the baseline term on the tested trajectories, rather than merely being present symbolically.
We also clarify the scope of these observations in Section 5.5 and Appendix I. They support the local dissipation mechanism of Theorem 4.6 and quantify its parameter-block contributions; they do not establish a trajectory-wide alignment bound, verify the two-layer four-hop locality claim of Proposition 4.8, or guarantee faster end-to-end Adam training. In particular, the checkpoints are generated by Adam, but the probes test ordinary-gradient updates, matching the local theoretical prediction rather than the Adam update rule.
These additions therefore connect measured quantities directly to a specific theoretical identity and its alignment ratio, going beyond the original performance comparisons.
Thank you for identifying these presentation issues. To meet the page limit, we compressed the exposition too aggressively, particularly in the abstract and the method-to-theory transition. Readers should not need to reconstruct definitions from later sections. We will introduce the method more clearly, define notation before use, and move secondary technical details to the appendix.
The central idea is straightforward:
ReMAP adds graph-neural-network outputs to unrestricted per-node scores and optimizes both for each MRF instance. The unrestricted scores preserve the expressive power of direct score optimization, while the neural component changes the gradient dynamics. Conditional-expectation rounding produces a discrete assignment whose energy is no greater than the resulting distribution’s expected energy.
We will replace the abstract’s discussion of coordinate transformations, parameter fibers, and Hessian inertia with this intuition, reserving formal statements for Section 4. Specifically, “the GNN cannot enlarge the feasible set” means that unrestricted logits already represent every strictly positive categorical distribution over valid labels. The GNN changes the parametrization, not the representable distributions; boundary distributions are approached as limits.
We will make three specific corrections:
W2(a) — Strength and coverage of the baseline comparison (primal-dual and move-making methods)
Additional primal-dual and move-making comparisons could broaden the evaluation, but our current baselines are established, competitive MRF solvers. LBP and TRBP are mainstream message-passing methods; SRMP is a strong dual message-passing method included in our higher-order experiments; and Toulbar2 is a leading complete solver that won all MPE and MMAP task categories in the UAI 2022 Inference Competition.
These methods provide substantial coverage of approximate message passing and complete search. Toulbar2 offers a demanding solution-quality comparison, and we report both instances where ReMAP improves upon its returned solution and those where Toulbar2 is stronger. Our empirical claims therefore rest on strong established solvers, not merely ablations or weak baselines.
The absence of additional solver families does not invalidate this evidence. Moreover, ReMAP directly supports arbitrary finite factor tables without metric or submodularity requirements. Comparisons with specialized methods should identify their supported problem classes and account for required reductions.
Repeated-run selection was not restricted to ReMAP: baseline results were also the best obtained across repeated runs. Thus, ReMAP was not given multiple trials against an arbitrarily selected baseline run.
For ReMAP, Tables 1 and 6 report the best of five seeds, while Table 7 reports mean ± standard deviation over the same trials. Best-of-five measures solution quality with multiple starts; mean ± standard deviation describes typical-run performance and variability.
We will explicitly document each baseline’s run count and initialization or configuration choices, and distinguish best-run from average-run results in the captions and experimental protocol.
Finally, best-of-multiple-run reporting does not itself establish equal-compute performance. We will distinguish solution-quality comparisons under the reported protocols from runtime claims and make the total cost of repeated runs explicit.