Neural network improves solving graph optimization problems efficiently
Neural Algorithmic Reasoning for Graph Saddle Point Problems
Machine Learning
Summary
Some problems on graphs can be solved by algorithms that find points balancing multiple competing factors, called saddle points. The authors introduce a new neural network design inspired by a traditional mathematical method (PDHG) to solve these problems efficiently. Their network can even learn to speed up this classical method through training. They show their approach works better than some other neural networks, especially on larger graphs, and can help speed up advanced optimization methods.
What this means in practice
- •For machine learning engineers: Incorporate GraphPDHG to accelerate training or optimization tasks involving graph-structured data by providing better initialization.
- •For operations research teams: Use GraphPDHG to solve complex graph optimization problems faster by leveraging learned acceleration of classical algorithms.
Authors
Samantha Chen, Jesse He, Coleman Clougherty, Gal Mishne, Chester Holtz
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 \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.