Neural Algorithmic Reasoning for Graph Saddle Point Problems

Motivation

• PDHG is efficient for graph saddle-point problems when objective terms have separable structure and simple proximal operators, enabling local message-passing updates instead of expensive global subproblems.Its practical performance also depends on instance-specific choices such as step sizes, preconditioning, momentum, and stopping criteria.Source: §1 · p. 2

A message passing PDHG network

• GraphPDHG is a PDHG-inspired message-passing network for graph saddle-point problems with convex or nonconvex penalties, using sparse graph operators and proximal updates without costly inner solves.A single layer can implement one preconditioned PDHG step.Source: §1 · p. 3

GraphPDHG and learned acceleration

• With edge memory, GraphPDHG’s linearized recurrence recovers heavy-ball acceleration, while its memoryless update reduces to preconditioned graph-Laplacian dynamics.These behaviors are characterized in Propositions 3.5 and 3.4, respectively.Source: §1 · p. 3

Empirical performance

• GraphPDHG generalizes better than GNN baselines to larger test graphs and produces high-quality warm starts for PDHG and second-order methods.The reported evaluation is on convex clustering.Source: §1 · p. 3

Contributions

• Unlike prior neural primal–dual work focused on discrete schemes, linear programs, or other specific problems, GraphPDHG targets continuous primal–dual optimization and trains end-to-end on the primal–dual gap without intermediate supervision.The cited prior frameworks include [43], [23], and.Source: §1 · pp. 2–3

Graph saddle-point problems

• Graph saddle-point objectives use vertex and edge functions linked by a weighted incidence operator that collects weighted differences across edges.Under standard qualification conditions, the saddle formulation has the same optimal value as the primal problem, and its saddle points satisfy the original problem’s KKT system.Source: §2 · p. 4

Primal–dual gap

• The primal–dual gap is nonnegative, and when the primal objective is strongly convex it bounds distance to the unique primal optimizer, supporting unsupervised training without solutions or intermediate iterates.The cited PDHG convergence result gives an O(1/N) gap rate under its assumptions.Source: §2 · pp. 4–5

Convex clustering and graph neural networks

• Convex clustering is presented as a special case of the graph-structured objective, while shared GNN aggregation and update maps allow layers to run on graphs of different sizes and topologies.The supplied convex-clustering passage refers to an appendix illustration.Source: §2 · p. 4

Primal–Dual Hybrid Gradient (PDHG)

• PDHG alternates local edge-dual updates and node-primal updates, matching message passing from node differences to edges and corrective messages back to nodes.The updates become fully local under separability assumptions on the functions and their proximal maps.Source: §2 · p. 5
• GraphPDHG can learn parts of PDHG’s fixed updates to adapt effective preconditioning and acceleration to graph topologies and feature statistics.Classical PDHG convergence is guaranteed when the inverse step sizes satisfy the stated operator-norm condition.Source: §2 · p. 5

3 Message passing PDHG

• GraphPDHG represents primal and dual variables as node and edge features, using an encoder–processor–decoder trained end-to-end to minimize the primal–dual gap.The processor composes PDHG message-passing layers; its transformations are learned from training graph instances rather than fixed as in classical PDHG.Source: §3 · p. 6
• With node-decomposable G, edge-decomposable F, and separable proximal maps, GraphPDHG can achieve any target primal–dual gap at a depth depending on the weighted incidence matrix’s spectral norm.The theorem states an arbitrarily small ergodic gap for a suitable parameter configuration.Source: §3 · p. 7

3.1 Feedforward dynamics of GraphPDHG

• In the linear regime, a memoryless parameterization can eliminate error in a chosen nonzero graph-Laplacian eigen-direction in one layer.This supports rapid convergence on graphs with fast eigenvalue decay; the stated rate is O(κ).Source: §3.1 · p. 8
• Retaining edge memory yields a second-order recurrence matching Polyak Heavy Ball dynamics, enabling GraphPDHG to learn accelerated algorithms with O(√κ) convergence.The recurrence uses a learnable effective step-size matrix.Source: §3.1 · p. 8
• For graph families with bounded condition number κ, the results imply convergence independent of graph size; Corollary 3.7 gives a depth O(κ) parameterization under its stated initial-error assumption.The corollary assumes the network’s first-layer solution incurs error c for each vertex.Source: §3.1 · p. 8

3.2 PDHG for convex clustering

• For convex clustering, GraphPDHG specializes PDHG to local node–edge updates, with each primal update combining the prior iterate, data, and aggregated incident-edge dual variables.Diagonal node- and edge-wise preconditioners make the proximal updates decouple locally.Source: §3.2 · pp. 8–9

Experimental setup

• GraphPDHG is evaluated on hierarchical Gaussian cluster graphs and k-nearest-neighbor graphs built from MNIST, Fashion-MNIST, and CIFAR-10 features.The experiments focus on whether PDHG alignment provides learned warm starts and promotes size generalization.Source: §4 · p. 9

Training objective

• The model is trained unsupervised by minimizing the primal–dual gap, which the cited result bounds as an upper bound on distance to the optimal solution.Experiments use last-layer readouts, whereas the theoretical results assume ergodic iterates.Source: §4 · p. 10, Figure 1 · p. 10

Baselines

• Baselines include GCN, GAT, GIN, GraphSAGE, and EdgeConv, with the same encoder–processor–decoder template, gap objective, and experimental protocol.Source: §4 · p. 10

Initializing a High-Accuracy Solver with GraphPDHG

• GraphPDHG yields better SSNAL warm starts than data or baseline-GNN initializations on hierarchical Gaussian graphs, and reduces SSNAL iterations on image datasets.Figure 2 evaluates time to a primal–dual gap ≤10^-6, gap as λ increases, and the fraction of validation graphs where an initialization is at least as fast as the best method.Source: Figure 2 · p. 10, §4 · pp. 10–11, Table 1 · p. 11

Size generalization

• Across datasets, GraphPDHG achieves substantially lower primal objective values than GAT and GCN as test-graph size increases.The evaluation uses a fixed λ for all graphs.Source: Figure 3 · p. 11, §4 · p. 11

5 Conclusion

• GraphPDHG exactly represents preconditioned PDHG updates, admits interpretations involving Laplacian spectra and acceleration, and improves size generalization and classical-solver warm starts on convex clustering.The authors suggest learned primal–dual message passing can also accelerate classical optimization algorithms.Source: §5 · p. 12

AI use statement

• The authors report using generative AI for editing, writing, experiments, and figure-generating code, with AI-generated code verified and tested by two authors.They state that they reviewed the AI-assisted work and take responsibility for the final content.Source: AI use statement · p. 12

A.1 Convex clustering

• Convex clustering balances fidelity to data points against fusion of neighboring centroids, with increasing λ producing coarser hierarchical clusterings.Its edge penalties connect it to network lasso, semi-supervised learning, and graph total-variation methods.Source: §A.1 · p. 18

A.2 Related Work

• Prior work includes learned primal–dual networks, but the paper targets generic saddle-point objectives and learns from the primal–dual gap without additional supervision.The framework connects message passing to preconditioned PDHG and learned dynamics to acceleration ideas such as heavy-ball momentum.Source: §A.2 · p. 20

A.3 Other penalties and their proximal maps (NORMALIZE)

• For separable edge penalties, the normalization operator and associated proximal computations can be performed edgewise.The appendix lists examples of separable convex and nonconvex penalties with simple proximal operators.Source: §A.3 · pp. 20–21

A.3.1 Convex penalties

• For convex penalties, the ℓ2 case projects onto a dual-norm ball, while the ℓ1 case uses coordinatewise clipping.The ℓ2 projection is independent of σ.Source: §A.3.1 · p. 21

A.3.2 Nonconvex penalties

• For nonconvex penalties, the standard convex-conjugate PDHG formulation does not apply directly, so the appendix defines normalization using direct proximal maps.Examples include thresholding and group firm-thresholding maps.Source: §A.3.2 · pp. 22–23

• All models were trained for 500 epochs on 1,000 graphs of 100 nodes, using Adam at learning rate 0.001 on eight NVIDIA RTX A6000 GPUs.The models were implemented with PyTorch and PyTorch-Geometric.Source: §A.4 · p. 23
• Node-state GNN baselines use projected pairwise edge differences as surrogate dual variables when trained against the primal–dual gap.The compared architectures are GIN, GraphSAGE, GCN, GAT, and EdgeConv, with different aggregation or edge-message mechanisms.Source: §A.4 · p. 23

• The Hierarchical Gaussian Benchmark samples features from a recursive Gaussian hierarchy and connects them with a Gaussian-weighted k-nearest-neighbor graph.Each point’s hierarchical label records its full path through the latent tree.Source: §A.4.1 · p. 23
• MNIST and Fashion-MNIST use learned VAE embeddings, while CIFAR-10 uses publicly available SimCLR embeddings.The VAEs have three fully connected encoder layers and were trained for 100 epochs.Source: §A.4.1 · p. 24
• Image-derived graphs use all available data, with 70,000 nodes for MNIST and Fashion-MNIST and 60,000 for CIFAR-10; training graphs are subsampled at 100 nodes.The graphs are k-nearest-neighbor graphs with Gaussian weights; k = 10 in all experiments.Source: §A.4.1 · p. 24

A.4.2 Additional experiments on convex clustering

• Fixed unrolling of classical PDHG performs worse than GraphPDHG in all cases and is especially unstable on Fashion-MNIST and CIFAR-10.The authors attribute the difference to GraphPDHG’s learned message-passing parameters adapting across graph instances.Source: §A.4.2 · p. 24
• Removing GraphPDHG’s edge projection degrades initialization quality, with full-model mean-gap reductions ranging from approximately 10% to 70% across the reported dataset and λ comparisons.The reported reductions are relative to the no-projection ablation.Source: §A.4.2 · p. 25
• Without edge memory, median first-hit times are higher at λ = 0.001 and 0.01, but become comparable as λ grows and the clustering collapses to the global mean.The authors identify the dual-variable edge component as essential to performance.Source: §A.4.2 · p. 25, Table 5 · p. 28
• On expander graphs, GraphPDHG reaches median relative primal–dual gap below 10^-2 in two layers, while canonical PDHG first reaches it at 12 iterations.For median full-Laplacian condition number κ = 2.53, the accelerated theoretical factor is qκ = 0.228.Source: §A.4.2 · p. 25, Table 6 · p. 28
• GraphPDHG yields the fastest or near-fastest SSNAL convergence across MNIST, Fashion-MNIST, and CIFAR-10, with the largest gains at stricter gap thresholds.Its neural initialization also has lower primal–dual gaps than GAT and GCN; CIFAR-10 results are more variable.Source: §A.4.2 · p. 25, Figure 5 · p. 26
• Across all image datasets and both λ levels, GraphPDHG achieves the lowest mean primal–dual initialization gap.Compared with GCN, its mean-gap reductions on MNIST are approximately 42% and 22% for λ = 2.5 and λ = 10, respectively.Source: §A.4.2 · p. 24, Table 4 · p. 27
• GraphPDHG is linear time per forward pass, as is vanilla PDHG, and the baselines also have linear-time forward passes.The appendix reports training and inference times for hierarchical Gaussian graphs with up to 100 nodes.Source: §A.4.2 · p. 27, Table 7 · p. 29

A.5 Total Variation Denoising on Graphs

• For graph-signal denoising, GraphPDHG-MM achieves the lowest NMSE at 3.33e-02 and a 6.85 dB SNR improvement, while requiring approximately 4.12 ms per graph for CPU inference.The task evaluates convex TV and nonconvex capped-fusion regularization on noisy signals; GraphPDHG-TV and GAT have NMSE values of 3.37e-02 and 3.42e-02, respectively.Source: §A.5 · pp. 28–29

• If G is µ-strongly convex, then G(u) + F(Ku) is also µ-strongly convex and has a unique minimizer.Source: B Proofs and additional results · p. 31
• The saddle-point Lagrangian difference is bounded above by the primal-dual gap and below by µ/2 times squared distance from the minimizer.Source: B Proofs and additional results · p. 31
• The proof uses the saddle-point/KKT condition and strong convexity of G at the optimum to establish the lower bound.Source: B Proofs and additional results · p. 31

• A specific parameterization and initialization make each message-passing layer reproduce one preconditioned PDHG iteration exactly.Source: §B.1 · p. 32
• The representation result lets PDHG-derived message passing inherit the approximation and convergence guarantees of PDHG.Source: §B.1 · p. 32
• When τσ∥K∥² < 1, the ergodic average of PDHG iterates satisfies a primal-dual gap bound.Source: §B.1 · p. 32
• With τ = σ = 1/(1 + ∥K∥²), the condition holds and the network achieves ε-optimality in primal-dual gap.Source: §B.1 · p. 32

• In the memoryless regime with A1 = 0 and B1 = Id, the linearized error dynamics recover the Polyak Heavy Ball update.Source: §B.2 · p. 33
• A parameter choice from yields worst-case error decay at an accelerated rate.Source: §B.2 · p. 34
• The analysis extends to symmetric positive definite M by expanding the error in a joint eigenbasis.Source: §B.2 · p. 34

• The recurrence decouples over modes, so each mode is governed by the scalar heavy-ball method.Source: Then each joint mode satisfies the… · p. 35
• Each joint mode follows a scalar heavy-ball recurrence with optimal worst-case asymptotic factor (sqrt(κ) - 1)/(sqrt(κ) + 1).Source: Then each joint mode satisfies the… · p. 35
• The error bound gives a sufficient layer depth proportional to log(1/ε)/log(1/ρ) for reaching ε-optimality.Source: Then each joint mode satisfies the… · p. 35