acceptodds
Under review as a conference paper at ICLR 2027

Neural Algorithmic Reasoning for Graph Saddle-Point Problems

Abstract

Neural algorithmic reasoning, or aligning a neural network with an algorithmic paradigm, has emerged as an approach to solving polynomial-time-solvable and computationally harder combinatorial optimization problems. We propose a new message-passing framework based on the Chambolle-Pock Primal–Dual Hybrid Gradient (PDHG) method called GraphPDHG for solving general graph saddle-point problems. Theoretically, we show that GraphPDHG can efficiently solve a family of graph saddle-point problems by simulating PDHG. We also show that our network can learn an accelerated PDHG algorithm. Experimentally, we support our results on accelerated PDHG by evaluating the performance of our model as a learned warm start for second-order optimization techniques (SSNAL). We also show that alignment with PDHG leads to stronger size generalization than non-aligned graph neural network (GNN) baselines. Overall, we propose a novel architecture for solving a general family of optimization problems on graphs.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, neural algorithmic reasoning, primal-dual algorithms, convex clustering

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_4Li9OpenReview ↗
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 λ\lambda parameter is specified but not introduced; presumably it relates to λe\lambda_e -- how should be specified.
  • L497 typo: in the supplementary materials
1 comment

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 min⁡u;G(u)+F(Ku),\min_u ; G(u)+F(Ku), where KK is a graph operator, GG admits efficient node-local proximal updates, and FF 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 GG decomposes over nodes, FF 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∣N\times |E| dual variable updates in (7) to independent updates for each e∈Ee \in 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.

Reviewer_2V82OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

GraphPDHG is a learnable framework that integrates a primal–dual optimization algorithm into graph neural networks. It solves convex optimization problems on graphs by emulating the iterations of PDHG, and it is trained without supervision by minimizing the primal–dual gap. On tasks such as convex clustering, the authors use the output of GraphPDHG as a warm start for the classical solver SSNAL and compare it with several GNN baselines. The results show that the method yields better initializations and reduces the number of iterations needed by the subsequent solver. Theoretically, the authors show that the architecture can represent one step of preconditioned PDHG and, in a linearized regime, heavy-ball acceleration.

Critical strengths

The method is effective in its application, and the ablations indicate that the model is useful. The ablation in Table 4 shows that removing the dual projection substantially increases the initial gap, and that an unrolled classical PDHG with a fixed number of iterations performs much worse than the learned model.

Critical weaknesses

The paper has several obvious writing and consistency issues.

  1. The introduction contains a duplicated passage (Lines 047–061 and 063–077).

  2. The proofs are titled “Theorem 3.4,” “Theorem 3.5,” “Theorem 3.6,” and “Theorem 3.7,” whereas the corresponding results in the main text are stated as propositions or corollaries.

  3. The reported results are inconsistent. In Appendix A.5 (Lines 1275–1284), the text does not match Table 8:

    • The NMSE of the noisy signal is reported as 1.57e-1 in the text but 3.922e-2 in the table.
    • The text claims that GraphPDHG-MM achieves the best result with an NMSE of 3.33e-2, whereas Table 8 reports 1.098e-2 for the same method.
  4. Furthermore, Tables 7 and 8 report experiments on different datasets and graphs with different numbers of nodes, yet the runtimes reported for the same methods are exactly identical. This raises concerns about the consistency and reliability of the reported experimental results.

Questions for authors

How do the authors plan to address the obvious writing problems and the inconsistencies between the text and the reported results identified above, and how would any further issues of this kind be resolved? I recommend carefully cross-checking the main text against all tables before resubmission.

2 comments

We thank the reviewer for identifying these inconsistencies in the main text. We agree that these discrepancies need to be corrected and we correct them in the revision of our manuscript. Note that we include all experimental code with our submission for reproducibility.

We thank the reviewer for pointing out inconsistencies. The original submission inadvertently combined Table 8 results obtained with noise standard deviation σ=0.2\sigma=0.2 and the prose which describes σ=0.4\sigma=0.4. We apologize for this error. The updated table reports ten independent evaluation trials at σ=0.4\sigma=0.4, matching the noise setting described in the prose. All evaluations use the saved models without retraining or retuning.

The new evaluation preserves the observed trends: both GraphPDHG variants achieve lower median NMSE than the classical TV and capped-MM baselines. GraphPDHG-MM has the lowest median NMSE (0.033020.03302), followed by GraphPDHG-TV (0.033310.03331). The runtime pattern also persists: GraphPDHG requires approximately 4.14.1 ms/graph, more than GCN but less than GAT and classical PDHG-MM.

MethodNMSE (×10−2\times 10^{-2})SNR gain (dB)CPU (ms/graph)
Noisy15.958±0.09915.958 \pm 0.0990.00±0.000.00 \pm 0.000.000±0.0000.000 \pm 0.000
PDHG-TV-165.707±0.06655.707 \pm 0.06654.49±0.044.49 \pm 0.042.924±0.00752.924 \pm 0.0075
PDHG-MM-163.921±0.0913.921 \pm 0.0916.12±0.076.12 \pm 0.0710.681±0.02710.681 \pm 0.027
GraphPDHG-TV3.331±0.05853.331 \pm 0.05856.82±0.0756.82 \pm 0.0754.105±0.00754.105 \pm 0.0075
GraphPDHG-MM3.302±0.05653.302 \pm 0.05656.85±0.086.85 \pm 0.084.124±0.00754.124 \pm 0.0075
MLP13.565±0.089513.565 \pm 0.08950.72±0.020.72 \pm 0.020.661±0.0020.661 \pm 0.002
GCN3.518±0.0563.518 \pm 0.0566.69±0.0656.69 \pm 0.0652.863±0.00852.863 \pm 0.0085
GAT3.555±0.0523.555 \pm 0.0526.77±0.0856.77 \pm 0.0855.482±0.0115.482 \pm 0.011
GraphSAGE3.591±0.05353.591 \pm 0.05356.72±0.086.72 \pm 0.082.031±0.0022.031 \pm 0.002
EdgeConv3.525±0.06553.525 \pm 0.06556.55±0.086.55 \pm 0.085.019±0.01155.019 \pm 0.0115

Thank you again for your helpful and constructive comments. We believe addresses our revision addresses all of your comments and would appreciate if you would update your score.

Reviewer_a9WZOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes GraphPDHG, which trains a GNN to simulate the Primal-Dual Hybrid Gradient (PDHG) method to solve graph-based saddle-point problems with convex and nonconvex penalties. GraphPDHG establishes an alignment between the message-passing mechanism and the PDHG algorithm. The training is done in an unsupervised manner by minimizing the primal–dual gap via message passing between the primal and dual variables. Empirical evidence shows that GraphPDHG provides higher-quality warm starts for SSNAL and generalizes better to larger graphs than several other GNN baselines. The paper also provides theoretical justifications for GraphPDHG's expressivity in implementing PDHG and for learning an accelerated algorithm in a linear regime.

Critical strengths
  1. The motivation for using GraphPDHG to learn instance-dependent choices over plain PDHG, whose practical performance depends on these settings, is clearly explained. This justifies why an NAR model can be desirable for PDHG.
  2. Two strengths of GraphPDHG are (i) trained in an unsupervised manner by a primal-dual gap, thereby bypassing the need to generate intermediate steps; (ii) applicable to continuous primal-dual optimization settings, broadening the applicability of prior NAR works.
  3. The paper provides both theoretical justification for GraphPDHG's expressivity and efficiency, and empirical validation on synthetic and image datasets.
  4. The overall writing of the paper is clear and easy to follow.
Critical weaknesses
  1. [Major] The formulation of GraphPDHG is applicable to both graph-structured convex and non-convex problems. However, the paper uses only convex clustering as a case study and validates it empirically. While the theoretical results cover both types of problems, the empirical component is more limited. The evaluation would benefit from a broader selection of problems and coverage of both convex and nonconvex penalties.
  2. [Medium] GraphPDHG is compared with other GNN baselines (GAT, GCN, etc.), in both warm starts for SSNAL and image datasets. However, there is no direct comparison with PDHG to justify the primary motivation that GraphPDHG may learn better instance-level distributions.
  3. [Medium] GraphPDHG is trained by minimizing the primal-dual gap in an unsupervised manner. While Figure 1 shows the correlation between the primal-dual gap and the distance from optimal, how would teacher-forcing training with intermediate steps generated by running PDHG compare to this unsupervised setting?
  4. [Minor] The primary motivation to show that GraphPDHG can learn an accelerated version of PDHG in specific settings is not clear. Is there empirical evidence to back up the theoretical scenario?
  5. [Minor] The introduction seems to have duplicated paragraphs (lines 48-61) and (lines 67-77).
Questions for authors

See weaknesses.

4 comments

We thank the reviewer for the constructive suggestions and for recognizing the novelty of our work.

Broader evaluation and nonconvex penalties. In Appendix A.5, we include graph-signal de-noising experiments with two different reconstruction objectives: convex total variation and a non-convex capped-fusion proximal problem. We show that GraphPDHG applied to the non-convex capped-fusion proximal problem achieves better reconstruction of the clean signal as compared to both PDHG as well as other GNN methods. This shows the applicability of GraphPDHG to both other types of problems and in particular, highlights its use for optimization problems with non-convex penalties.

Direct comparison with PDHG. 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 4 and a direct comparison on expander graphs in Table 6. In Table 4, we show that GraphPDHG far outperforms the unrolled-PDHG baseline. Furthermore, in Table 6, 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 your other question below) suggest that this effect can be mitigated by additional supervision at every layer (i.e. at every message-passing update).

Motivation and evidence for acceleration. The theoretical results concern the architecture’s capacity to represent accelerated dynamics under specified assumptions. It does not imply that arbitrary trained parameters converge at that rate or that training necessarily discovers the accelerated parameterization. We note that we do investigate whether this acceleration is happening empirically in Table 6. There, we compare the convergence rate of GraphPDHG as compared to vanilla PDHG on expander graphs and show evidence of improved approximation at small computational budgets. We have make these clarifications explicit in our revision.

Teacher forcing. Thank you for your suggestion, we include some preliminary results on teacher forcing (a more extensive version will appear in our final manuscript). We compare four training strategies using a 16-layer GraphPDHG architecture. Gap-only training (the original GraphPDHG training strategy used in our manuscript) rolls out the network autonomously and minimizes its final primal–dual gap. Intermediate supervision retains this rollout but penalizes discrepancies between predicted primal–dual states and the corresponding PDHG iterates at every update. Teacher forcing instead supplies the preceding PDHG state during training and supervises the predicted next state.

Table: Preliminary comparison on the validation set for training seed 0.

MethodTraining objectiveRelative gap ↓
Original GraphPDHGFinal gap7.86×10−27.86 \times 10^{-2}
GraphPDHG + terminal supervisionFinal gap + distance to opt.1.63×10−11.63 \times 10^{-1}
Intermediate supervisionPDHG trajectory matching4.67×10−34.67 \times 10^{-3}
Intermediate gap supervisionFinal + intermediate gaps3.20×10−33.20 \times 10^{-3}

We report the mean relative primal–dual gap at the selected checkpoint (lower is better). All models use 16 updates. Original GraphPDHG propagates latent embeddings, whereas the feedback variants propagate decoded primal–dual predictions. These are single-seed validation results, not final test results.

Duplicated introduction. In the new draft we have removed the repeated passage and use the space to clarify our theoretical guarantees and the empirical comparisons.

However, we note that supervision on intermediary layers (message passing updates) is more expensive than simply training end-to-end.

[W1] Thanks for the pointer; the additional experiment on the non-convex problem addressed my concern.

[W2] I assume Table 6 should be Table 7 (comparison with PDHG on expander graphs). However, Table 4 is "Table 4: Examples of separable convex and nonconvex penalties." Which table should I be looking at?

[W3] Thanks for the additional experiments. It seems that more supervision helps reduce the gap. While I understand that more supervision comes with additional costs, and this paper focuses on unsupervised training, these results are still useful. In the final version, please also add computational analysis/discussion of the three additional supervised training methods, given that they lead to better performance.

[W4] The empirical evidence (Table 7) helped to address my concern.

[W5] Thanks for the fix.

[W2] Yes, Table 6 should be Table 7. The correct table to look at for comparison to PDHG is Table 5. We apologize -- the Table numbers moved in our revision as we moved the graph signal de-noising experiment to the main text as suggested by Reviewer 4Li9.

Thanks for the clarification. My concerns have been addressed, and I maintain my original positive rating.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.