- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper is in the general area of neural algorithmic reasoning, whose goal is to use neural networks to execute computations that are aligned with classic algorithms, with the goal of obtaining better generalizability, execution speed, and broader applicability. The authors consider a class of problems with a specific optimisation objective and structure, which can be solved via a primal-dual approach. A message-passing architecture is proposed (GraphPDHG) that is aligned with the classic PDHG algorithm but uses learned, as opposed to fixed, parameters for (some) of the update rules. The authors prove theoretical results regarding the expressivity of GraphPDHG (i.e., it is sufficiently expressive to recover PDHG) and that it attains convergence faster on some graph families. Experiments are carried out on a synthetic clustering dataset as well as classic image datasets, showing that the approach performs better than several standard GNN architectures.
Post-rebuttal update
After the rebuttal, I am raising my score to a Weak accept, as the authors have mostly addressed my comments satisfactorily. Overall, the fact that some key experiments were left to the appendix (comparison to PDHG, applications to >1 problem), in addition to other presentational issues, signal that the paper itself is in a fairly immature state. The statistical evidence also remains shaky. In my opinion, this would be a much strong paper with another revision cycle. However, if the authors carry out all the promised changes as suggested, it just about passes the bar.
Critical strengths
S1. The motivation behind the paper is solid and the derivation of the approach follows quite naturally.
S2. The theoretical results are interesting and support the motivation for a method whose parameters are learned from data as opposed to fixed.
Critical weaknesses
W1. The experiments are disconnected from the theoretical results.
W2. There are questions around the statistical significance of the results and how broad / general the method truly is.
W3. Limitations are not discussed.
I detail these weaknesses in the next section of the review.
Questions for authors
Q1. (Related to W1) Could you compare PDHG and GraphPDHG directly, or otherwise justify why they are not compared directly in the main experiments? The narrative of the paper is written around how GraphPDHG, being a "neural" version of PDHG, is a more flexible approach since parameters can be learned for specific problem instance distributions. Indeed, this is what the theoretical results support. However, the main experiment do not compare the two approaches directly; instead using GraphPDHG for the initial parameters for running PDHG. One would hope to see similar performance in-distribution, with better performance / generalisation for GraphPDHG on larger sizes etc.
Q2. (Related to W2) Could you address the following regarding the statistical significance of the results:
- It is not specified how many runs or seeds are used. It may be a low number: the results e.g. in Table 1 are not statistically separable at all, and it is not sound to suggest a method is better than another based on this.
- All tables and figures should contain confidence intervals or error bars; many do not.
- Reporting mean +- sd as in Table 1 is inappropriate; confidence intervals should be computed, which at 95% confidence level corresponds to approximately 1.97 standard deviations. This may make results appear more robust than they truly are.
Q3. (Related to W2) Can you justify why the clustering problem was picked as the main one for the evaluation? It is, frankly, not very exciting or interesting in order to motivate such a complex learning-based approach. Are there more "interesting" / unsolved / hard to solve problems in this class for which the benefits of GraphPDHG would be justified? The denoising problem is interesting and should be promoted to the main text to support the broad applicability. Furthermore, could you discuss in detail what steps one would need to take to apply the framework to a new problem? How general is the blueprint, and how much work is involved?
Q4. (Related to W3) Can you explicitly discuss the limitations of the method, experiments, etc.? This is an important part of any paper but was glossed over.
Smaller comments / suggestions:
- Note that the paragraphs in L063-L077 are a duplicated, slightly edited version of the previous paragraphs. One of these two versions should be cut, and you'll recover 1/3 of a page.
- The abstract doesn't state what graph saddle point problems are and why they're important, before discussing the new solution method proposed.
- Check citation commands: \citet is used instead of \citep in quite a few places, e.g. L028
- In the experiments the parameter is specified but not introduced; presumably it relates to -- how should be specified.
- L497 typo: in the supplementary materials
Thank you for constructive feedback. Regarding the minor comments on writing and clarity, we incorporate your suggestions in our revision of the manuscript.
Response to Q1: We agree that this comparison is important to evaluate whether learning improves performance on a distribution of problem instances. Our original submission includes an unrolled-PDHG baseline in Table 5 and a direct comparison on expander graphs in Table 7. In Table 5, we show that GraphPDHG far outperforms the unrolled-PDHG baseline. Furthermore, in Table 7, we compare GraphPDHG against PDHG on exapnder graphs (for which PDHG has a faster convergence rate in our theoretical results). We show that shallow GraphPDHG achieves a much better primal objective than vanilla PDHG. However, for deeper GraphPDHG architectures that are trained end-to-end on the primal-dual gap, the final primal objective is slightly worse than vanilla PDHG, possibly due to oversmoothing and oversquashing.
Our preliminary experiments with teacher-forcing (see our response to Reviewer a9WZ) suggest that this effect can be mitigated by additional supervision at every layer (i.e. at every message-passing update).
Response to Q2: Thank you for this question. We will make the set-up regarding the number of runs and independent seeds clear in our revision. Our experiments were conducted over 10 runs. We acknowledge that some of the performance differences in Table 1 are small relative to the variability across runs.
Furthermore, in our revision, we will include error bar reporting for all Tables.
Response to Q3: We chose convex clustering as our primary benchmark because it provides a well-defined, nonsmooth graph optimization problem with a nontrivial primal–dual structure. These properties allow us to systematically evaluate the quality of learned primal–dual solutions, their effectiveness as warm starts, and generalization across graph sizes, feature distributions, and regularization parameters.
We note that Appendix A.5 already includes experiments on graph-signal denoising with both convex total-variation regularization and a nonconvex capped-fusion penalty. In particular, the nonconvex experiment uses a majorization–minimization extension, for which traditional convex primal–dual convergence guarantees do not directly apply. Thank you for your suggestion of moving this experiment to our main text. We have done this in our revision.
The general framework targets objectives of the form minu;G(u)+F(Ku), where K is a graph operator, G admits efficient node-local proximal updates, and F admits efficient edge-local dual proximal updates. Applying GraphPDHG to a new problem involves: (i) expressing the objective in this form; (ii) deriving the corresponding node and edge proximal operations; (iii) incorporating these operations into the primal–dual message-passing layers; and (iv) selecting an appropriate training objective and retraining on the relevant problem distribution.
Thus, the underlying node–edge message-passing architecture can be reused across problems, while the proximal operator may require task-specific adaptation. For problems with separable, closed-form proximal operators, these changes are straightforward.
Response to Q4: Thank you for this question. We added the following discussion of the limitations to our revision. In terms of limitations, we note that in order for the universality property in Theorem 3.1 to hold, we require that G decomposes over nodes, F decomposes over edges and that the associated proximal maps are separable. Generalizing GraphPDHG to non-seperable objectives is currently out of scope for this paper but can likely be handled by introducing auxiliary variables and non-local proximal maps. However, we note that part of the advantage of using PDHG, is that the operation is local (see section 3.2). The separability condition simplifies the N×∣E∣ dual variable updates in (7) to independent updates for each e∈E, thus only requiring message passing. If the coupling is non-trivial or its proximal map nonseparable, the advantages due to locality are lost. Furthermore, in our theoretical results, we show that GraphPDHG has the capacity to learn an accelerated version of PDHG. However, this depends on the condition number of the underlying graph and consequently, the potential benefits of GraphPDHG also depends on the spectral properties of the underlying graph and the extent of the learned acceleration will vary across different graph datasets. Finally, experimentally, we see that GraphPDHG suffers from the same oversquashing and oversmoothing problems when the network gets deeper (as expected from deep message-passing neural networks). We see some preliminary evidence that this can be mitigated by teacher-forcing or per-layer supervision and will discuss this in our revision of our paper.