Organizations: Oberlin College · Department of Computer Science, Oberlin College · University of California, San Diego · Department of Data Science, University of California, San Diego · OneChronos
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 \textsc{GraphPDHG} for solving general graph saddle-point problems. Theoretically, we show that \textsc{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.
Figures & tables
Figure 1 : Tracking the primal–dual gap and the distance between the predicted and optimal primal variables throughout training. The iterate error shrinks as the gap shrinks.
Figure 2 : Warm-starting SSNAL for the hierarchical Gaussian dataset. Left: Time (seconds) to recover a primal–dual gap ≤10−6 . Middle: The primal–dual gap of different network initializations as λ increases. Right: For each initialization method, the fraction of validation graphs for which SSNAL reaches a primal–dual gap of ≤10−6 at least as fast as the best-performing method.
λ=2.5
λ=10
Dataset
Method
10−4
10−6
10−8
10−4
10−6
10−8
MNIST
Data
2.0±0.0
11.6±4.8
11.6±4.8
2.0±0.0
6.4±2.6
6.4±2.6
GIN
2.0±0.0
12.0±5.8
12.0±5.8
2.2±0.3
8.7±4.8
8.7±4.8
GCN
2.0±0.0
13.4±6.8
13.4±6.8
2.2±0.2
8.5±4.7
8.5±4.7
GAT
2.0±0.0
7.0±3.4
7.0±3.4
2.4±0.2
9.1±5.1
9.1±5.1
GraphSAGE
2.0±0.0
8.8±4.5
8.8±4.5
2.2±0.2
7.4±3.8
7.4±3.8
Table 1 : First-hit times for different initialization methods. Entries report mean ± standard deviation over runs. The best result is bold. Median hit times and ablations are reported in the Appendix.
Figure 3 : Size generalization for each dataset. We track the primal objective as the size of the test graphs increases for all datasets. Note that we test at a fixed λ for all graphs.
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4 : Solutions for convex clustering (( 5 )) as λ increases on a k -NN graph for hierarchical Gaussians.
Object
Graph interpretation
Convex clustering interpretation
ui
node variable
centroid for point xi
(Ku)e
weighted edge difference
discrepancy between neighboring centroids
pe
edge dual variable
fusion forcing term
K⊤p
aggregate incident edge feedback
net force on centroid ui from incident edges
F(Ku)
graph regularizer
penalty encouraging fused centroids
F∗(p)
dual constraint/penalty
feasible range of edge tensions
Appendix
Table 2 : Notation: convex clustering as an instance of ( 2 ).
Name
Penalty Fe(z)
Convex penalties
Group TV ( ℓ2 )
λe∥z∥2
Anisotropic TV ( ℓ1 )
λe∥z∥1
Max-norm TV ( ℓ∞ )
λe∥z∥∞
Nonconvex penalties
ℓ0
λe1{z=0}
Appendix
Table 3 : Examples of separable convex and nonconvex penalties.
Dataset
Method
λ=2.5
λ=10
MNIST
GAT
1931.7±1274.4
2167.9±1544.4
GIN
15.0±4.5
98.0±30.0
GCN
12.6±3.1
89.0±24.9
GraphSAGE
11.0±2.8
82.0±23.0
EdgeConv
9.0±2.0
74.0±18.0
Unrolled PDHG
64.3±28.1
143.2±59.3
Appendix
Table 4: Primal–dual gap at initialization on image-derived convex clustering instances. Entries report mean ± standard deviation over runs. Lower is better, and the best result for each dataset and weight λ is bolded.
Figure 5 : Comparing initializations. Left Column: Mean number of iterations of SSNAL to reach a primal–dual gap ≤10−6 . Right Column: Primal-dual gap at initialization. Top: MNIST. Middle: Fashion-MNIST. Bottom: CIFAR-10.
λ=0.001
λ=0.01
λ=0.10
λ=1.0
With edge memory
16.0
41.0
164.0
176.0
Without edge memory
18.0
53.0
161.0
182.0
Appendix
Table 5 : Ablating the edge memory component of GraphPDHG . We measure the median first hit times for a target primal-dual gap of 0.001 after initializing SSNAL with GraphPDHG with edge memory vs. GraphPDHG without edge memory. Note that initializing SSNAL with GraphPDHG without the edge component, the median first hit is higher than if we had initialized SSNAL with GraphPDHG with an edge component.
k
GraphPDHG empirical gap
PDHG empirical gap
Accelerated theory qκk
PDHG theory 1/k
1
1.90×10−2
5.02×10−1
2.28×10−1
1.00
2
1.60×10−3
3.26×10−1
5.20×10−2
5.00×10−1
4
6.14×10−3
1.41×10−1
2.71×10−3
2.50×10−1
8
1.35×10−3
3.06×10−2
7.33×10−6
1.25×10−1
12
1.48×10−3
7.52×10−3
1.99×10−8
8.33×10−2
16
7.51×10−4
6.89×10−4
5.38×10−11
6.25×10−2
Appendix
Table 6 : Empirical gaps and theoretical convergence rates on expanders with κ=2.53 .
GraphPDHG
GCN
GAT
Training time
1h 20m
1h 26m
1h 12m
Inference time (ms)
4.367
2.977
5.602
Appendix
Table 7 : Training time and inference times for each method on hierarchical Gaussian graphs with 100 nodes.
Method
NMSE
SNR gain (dB)
CPU (ms)
Noisy
3.922×10−2±6.75×10−4
0.00±0.00
0.000
Heat
3.231×10−2±6.85×10−4
0.91±0.08
0.816
PDHG-TV
1.897×10−2±5.65×10−4
3.17±0.15
3.184
PDHG-MM
1.461×10−2±9.10×10−4
4.31±0.28
11.373
GraphPDHG-TV
1.075×10−2±6.20×10−4
5.63±0.20
4.354
GraphPDHG-MM
1.098×10−2±5.80×10−4
5.50±0.18
4.367
Appendix
Table 8 : Graph signal denoising. Comparison of reconstruction methods. Uncertainties are computed as half the reported interval width.
1Davidson School of Chemical Engineering, Purdue University · Faculty of Computer Science, RWTH Aachen University · 3Jacobs Technion-Cornell Institute, Cornell Tech
Faculty of Engineering, The University of Hong Kong, Hong Kong SAR, China · Costello College of Business, George Mason University, VA, USA · Faculty of Business and Economics, The University of Hong Kong, Hong Kong, China +1