Brain-inspired Chaotic Graph Backpropagation for Large-scale\n Combinatorial Optimization

Tao Peng, Kazuyuki Aihara, Luonan ChenarXiv 2024 · DOI · arXiv

TL;DR

Researchers have developed Chaotic Graph Backpropagation (CGBP), a brain-inspired training algorithm that helps Graph Neural Networks (GNNs) solve massive combinatorial optimization problems. By injecting controlled "chaos" into the learning process, the algorithm escapes the local minima that plague standard backpropagation, outperforming existing deep learning methods and rivaling specialized state-of-the-art solvers on graphs with up to a million nodes.

What Problem Does This Paper Address?

Combinatorial Optimization Problems (COPs)—such as finding the Maximum Independent Set (MIS) or the Maximum Cut (MC) in a graph—are foundational to logistics, circuit design, and drug discovery. However, as datasets grow to "big data" scales, traditional operations research methods (like branch-and-bound) become computationally prohibitive.

Recently, Physics-Inspired GNNs (PI-GNNs) emerged as a fast, unsupervised alternative. They map a COP's objective function to a GNN's loss function. The catch? Standard training algorithms like Adam or SGD are gradient-based and notoriously prone to getting stuck in local minima. This means that while PI-GNNs are fast, the quality of their solutions often falls short of specialized, non-neural solvers. The authors aim to bridge this performance gap by rethinking how GNNs explore the solution space.

Methods

The authors introduce Chaotic Graph Backpropagation (CGBP). Inspired by the chaotic dynamics observed in real biological brains (which help neurons remain "plastic" and receptive to new patterns), CGBP adds a novel local chaotic loss function ($loss_C$) to the standard task-specific loss ($loss_H$).

Key Technical Components:

  • The Chaotic Term: The algorithm introduces a cross-entropy-style local loss that creates negative feedback for weight updates. When a specific hyperparameter ($z$, chaotic strength) is high, the system exhibits Marotto chaos (high-dimensional topological chaos).
  • Chaotic Simulated Annealing: To ensure the model eventually settles on a solution, the authors use an annealing strategy. They start with high chaos to globally explore the "energy landscape" of the problem and gradually reduce it (using an annealing constant $\beta$) until the dynamics transition back into standard gradient descent.
  • Plug-in Architecture: CGBP isn't a new GNN architecture; it's a training logic. It can be integrated as a "plug-in" into existing architectures like GCN or GraphSAGE and combined with standard optimizers like Adam.

Datasets

The researchers evaluated CGBP across several rigorous benchmarks:

  • 3-regular Graphs: Synthetic graphs ranging from 100 to 100,000 nodes to test scalability and theoretical bounds.
  • Gset: A standard benchmark for the Maximum Cut (MC) problem.
  • Queen Dataset: A set of dense graphs used to test Graph Coloring (GC) performance.
  • Citation Datasets (Cora, Citeseer, Pubmed): Large-scale, sparse real-world networks used for multi-classification (Graph Coloring) tasks.

Key Insights and Ideas

  • Chaos as a Search Tool: Instead of viewing randomness as noise, the paper treats chaos as a mechanism for global ergodicity. Because chaotic systems are "pseudo-random" but deterministic, they can sweep through a fractal space of potential solutions more effectively than simple random restarts.
  • Biological Plausibility: Unlike other methods that generate chaos by simply jittering the learning rate, CGBP’s local loss mimics synaptic plasticity mechanisms like spike-timing-dependent plasticity (STDP).
  • Linear Scalability: The algorithm maintains a time complexity of $O(n)$, meaning it scales linearly with the number of nodes. This allows it to handle "super-large-scale" problems (millions of variables) that would choke traditional solvers.

Key Results

  • Superiority over BP: On 100-node 3-regular graphs, CGBP consistently found lower minimum losses and larger Maximum Independent Sets compared to standard backpropagation, regardless of whether they used SGD, SGDM, or Adam.
  • Rivaling SOTA: On the Gset (Max-Cut), CGBP-trained GNNs came within a razor-thin margin (29–41 edges) of specialized state-of-the-art solvers like BLS and KHLWG, and actually matched the optimal results on larger instances (G49, G50).
  • Graph Coloring Breakthrough: On the Pubmed dataset (approx. 19,000 nodes), CGBP achieved a conflict count ($N_{GC}$) of 2. For context, standard GNN approaches yielded 17, and specialized GNNs yielded 13. CGBP reduced the error by nearly an order of magnitude.

Limitations and Future Work

While CGBP represents a significant leap, the authors note a few areas for improvement:

  • Manual Hyperparameters: The chaotic strength ($z$) and annealing rate ($\beta$) currently require manual tuning. Developing an adaptive mechanism to adjust these parameters mid-training is a key goal for future research.
  • Loss Encoding: The "Physics-inspired" Hamiltonian loss ($loss_H$) used to define the COP isn't always perfect; sometimes a lower loss doesn't strictly translate to a better real-world solution. Refining how COPs are mathematically encoded into GNNs remains an open challenge.
  • Optimizer Synergy: While it works well with Adam and GraphSAGE, exploring more advanced optimizers (like Adabelief) could further push the performance ceiling.

Summary updated

Abstract

Graph neural networks (GNNs) with unsupervised learning can solve large-scale\ncombinatorial optimization problems (COPs) with efficient time complexity,\nmaking them versatile for various applications. However, since this method maps\nthe combinatorial optimization problem to the training process of a graph\nneural network, and the current mainstream backpropagation-based training\nalgorithms are prone to fall into local minima, the optimization performance is\nstill inferior to the current state-of-the-art (SOTA) COP methods. To address\nthis issue, inspired by possibly chaotic dynamics of real brain learning, we\nintroduce a chaotic training algorithm, i.e. chaotic graph backpropagation\n(CGBP), which introduces a local loss function in GNN that makes the training\nprocess not only chaotic but also highly efficient. Different from existing\nmethods, we show that the global ergodicity and pseudo-randomness of such\nchaotic dynamics enable CGBP to learn each optimal GNN effectively and\nglobally, thus solving the COP efficiently. We have applied CGBP to solve\nvarious COPs, such as the maximum independent set, maximum cut, and graph\ncoloring. Results on several large-scale benchmark datasets showcase that CGBP\ncan outperform not only existing GNN algorithms but also SOTA methods. In\naddition to solving large-scale COPs, CGBP as a universal learning algorithm\nfor GNNs, i.e. as a plug-in unit, can be easily integrated into any existing\nmethod for improving the performance.\n
BibTeX
@misc{peng2024brain,
  author = {Tao Peng and Kazuyuki Aihara and Luonan Chen},
  title = {{Brain-inspired Chaotic Graph Backpropagation for Large-scale\textbackslash\{\}n Combinatorial Optimization}},
  year = {2024},
  eprint = {2412.09860},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.09860},
}

Loading related content...

Figure