Brain-Inspired Chaotic Graph Backpropagation for Combinatorial Optimization

Graph neural networks (GNNs) with unsupervised learning can provide high-quality approximate solutions to large-scale combinatorial optimization problems (COPs) with efficient time complexity, making them versatile for various applications. However, since this method maps the COP to the training process of a GNN, and the current mainstream backpropagation-based training algorithms are prone to falling 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 the possibility of learning through chaotic dynamics of the real brain, 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 pseudorandomness with fractal structure of such chaotic dynamics enable CGBP to learn GNNs effectively and globally, thus solving the COP efficiently. We have applied CGBP to solve various COPs, such as the maximum independent set (MIS), maximum cut (MC), and graph coloring (GC). Results on several large-scale benchmark datasets showcase that CGBP can compete with or outperform SOTA methods. In addition, CGBP can be easily integrated into any existing learning method as an additional universal plug-in module to improve the searching ability and performance.