GraphPDHG: a PDHG-aligned message-passing network solves graph saddle-point problems, accelerating convergence and improving size generalization

GraphPDHG is a node-edge message-passing layer that directly corresponds to one preconditioned PDHG iteration: node states send differences to edges and edge states send corrective messages back to nodes, yielding scalable local updates on sparse graph operators and avoiding costly global inner solves. Earlier primal-dual neural algorithmic reasoning work (PDNAR, PDHG-Net) targeted discrete primal-dual approximation algorithms or linear programs; this work targets continuous primal-dual composite objectives on point clouds and graphs, covering linear, nonlinear, and nonsmooth graph-structured saddle-point problems. Appendix Lemma B.2 gives a constructive representation proof: under a specific parameter configuration and activation, one layer exactly recovers PDHG iterates; Theorem 3.1 further bounds the required depth in terms of the spectral norm of the weighted incidence matrix so the ergodic primal-dual gap becomes arbitrarily small.

The linearized feedforward dynamics are characterized: in the memoryless regime the update reduces to preconditioned graph-Laplacian dynamics, with each layer eliminating error along one eigen-direction; with edge memory, the primal error satisfies the Polyak heavy-ball second-order recurrence, giving the network capacity to learn an accelerated algorithm. This offers a spectral explanation for why algorithmic alignment aids generalization, connecting learned updates to classical acceleration ideas such as heavy-ball momentum rather than leaving it as an empirical observation. Propositions 3.4 and 3.5 and Corollaries 3.6 and 3.7 give constructive parameterizations and rates under the Linear Regime assumptions (identity activation, projection acting as identity on inactive edges); for graph families with bounded condition number the rate is independent of graph size.

On convex clustering, GraphPDHG as a learned warm start substantially reduces the iterations SSNAL needs to reach a target primal-dual gap, and achieves lower primal objective values than GCN and GAT baselines as graph size increases. Unlike node-only GNN baselines, GraphPDHG explicitly maintains edge-dual states; ablations show that removing the edge projection or the edge memory degrades initialization quality, indicating the gains are not merely from generic message passing or fixed unrolling. Evaluated on a hierarchical Gaussian synthetic dataset and k-nearest-neighbor graphs from MNIST, Fashion-MNIST, and CIFAR-10; all models share the encoder-processor-decoder template and the same primal-dual gap objective, trained for 500 epochs on 1000 graphs of 100 nodes with Adam at learning rate 0.001.

Training minimizes the primal-dual gap in an unsupervised manner: when the node objective is strongly convex, the gap bounds the distance from the primal iterate to the unique optimizer, so no ground-truth solutions or step-by-step algorithmic supervision are needed. Compared with NAR work that generally requires intermediate layer hints or algorithmic supervision, this objective reduces supervision needs and directly targets optimality conditions. Corollary B.1 proves the gap-to-iterate-error relationship; experiments observe this theoretical relationship empirically, though the theory assumes ergodic iterates while experiments use last-layer readouts.

The results target graph-structured composite saddle-point problems that can be written as a node objective plus an edge penalty with separable proximal maps, typically when many related graph problems must be solved under tight compute budgets or when good preconditioners are expensive to design. Intended users include researchers and engineers working on convex clustering, network lasso, and graph total-variation denoising, as well as those wanting learned primal-dual variables to warm-start classical solvers such as PDHG or SSNAL. The theoretical guarantees hold under the Linear Regime assumptions (identity activation and projection acting as identity on inactive edges), and the acceleration results concern graph families with bounded condition number.

The theoretical analysis relies on the Linear Regime assumptions and ergodic iterates, while experiments use last-layer readouts, so the gap between the two is worth watching. Acceleration gains plateau as depth increases, which the authors attribute to oversmoothing, oversquashing, and optimization difficulty in deep GNNs, an explanation that remains an open question. Some appendix table values are not fully rendered in the text, so specific iteration counts and gap values can only be judged from the prose. The edge-memory ablation also shows smaller differences at larger regularization, which the authors note is because the objective collapses to the global mean, limiting the informativeness of comparison in that degenerate regime.