Brain-Inspired Chaotic Graph Backpropagation for Combinatorial Optimization.

Area of Science:

• Artificial Intelligence
• Machine Learning
• Computational Science

Background:

• Graph neural networks (GNNs) offer efficient approximate solutions for combinatorial optimization problems (COPs).
• Current backpropagation methods in GNNs often fall into local minima, limiting optimization performance.
• Existing methods struggle to match the state-of-the-art (SOTA) in solving large-scale COPs.

Purpose of the Study:

• To develop a novel training algorithm for GNNs that overcomes the limitations of traditional backpropagation.
• To improve the optimization performance of GNNs for solving complex combinatorial optimization problems.
• To introduce a training method inspired by chaotic dynamics for enhanced GNN learning.

Main Methods:

• Introduced Chaotic Graph Backpropagation (CGBP), a new training algorithm for GNNs.
• Incorporated a local loss function within the GNN training process to induce chaotic dynamics.
• Leveraged the global ergodicity and pseudorandomness of chaotic dynamics for effective GNN learning.

Main Results:

• CGBP demonstrates efficient and global learning of GNNs for solving COPs.
• Applied CGBP to Maximum Independent Set (MIS), Maximum Cut (MC), and Graph Coloring (GC) problems.
• Achieved competitive or superior performance compared to SOTA methods on large-scale benchmark datasets.

Conclusions:

• CGBP effectively addresses the local minima problem in GNN training for COPs.
• The chaotic dynamics in CGBP enable efficient and global optimization.
• CGBP serves as a universal plug-in module to enhance existing learning methods for improved searching and performance.