Brain-inspired Chaotic Graph Backpropagation for Large-scale Combinatorial Optimization
This addresses performance limitations in GNN-based combinatorial optimization, offering a plug-in improvement for various applications, though it appears incremental as an enhancement to existing training methods.
The paper tackles the problem of graph neural networks (GNNs) falling into local minima when solving large-scale combinatorial optimization problems (COPs), introducing a chaotic graph backpropagation (CGBP) algorithm that outperforms existing GNN and state-of-the-art methods on benchmarks like maximum independent set, maximum cut, and graph coloring.
Graph neural networks (GNNs) with unsupervised learning can solve large-scale combinatorial optimization problems (COPs) with efficient time complexity, making them versatile for various applications. However, since this method maps the combinatorial optimization problem to the training process of a graph neural network, and the current mainstream backpropagation-based training algorithms are prone to fall into local minima, the optimization performance is still inferior to the current state-of-the-art (SOTA) COP methods. To address this issue, inspired by possibly chaotic dynamics of real brain learning, we introduce a chaotic training algorithm, i.e. chaotic graph backpropagation (CGBP), which introduces a local loss function in GNN that makes the training process not only chaotic but also highly efficient. Different from existing methods, we show that the global ergodicity and pseudo-randomness of such chaotic dynamics enable CGBP to learn each optimal GNN effectively and globally, thus solving the COP efficiently. We have applied CGBP to solve various COPs, such as the maximum independent set, maximum cut, and graph coloring. Results on several large-scale benchmark datasets showcase that CGBP can outperform not only existing GNN algorithms but also SOTA methods. In addition to solving large-scale COPs, CGBP as a universal learning algorithm for GNNs, i.e. as a plug-in unit, can be easily integrated into any existing method for improving the performance.