Annealing Machine-assisted Learning of Graph Neural Network for Combinatorial Optimization

Pablo Loyola, Kento Hasegawa, Andres Hoyos-Idobro, Kazuo Ono, Toyotaro Suzumura, Yu Hirate, Masanao Yamaoka

Introduction: The Scaling Wall of Combinatorial Optimization

Combinatorial optimization (CO) is a fundamental challenge in fields ranging from logistics to chip design. Currently, two primary technologies are used to tackle these NP-hard problems: Annealing Machines (AM) and Graph Neural Networks (GNN).

AMs, such as D-Wave or CMOS-based annealers, provide high-precision solutions but are limited by a "scaling wall"—they can typically only handle a finite number of variables (e.g., 100k). Conversely, GNNs scale efficiently to millions of nodes but often produce "noisy" probabilistic assignments that lack the precision of traditional solvers. This paper introduces a hybrid framework that bridges this gap, enabling AM-level precision on problems that far exceed the hardware's physical variable limits.

Methodology: AM-Assisted GNN Learning

The authors propose a multi-step workflow called AM-assisted GNN learning (mrGNN+AM). This framework uses an AM to solve compressed versions of a graph and uses those high-quality solutions to "guide" a GNN student.

Overview of the AM-assisted GNN learning framework, showing the progression from graph compression to guided initialization of the main solver.

The workflow follows these key stages:

  1. Graph Compression: Louvain decomposition is used to create a hierarchy of smaller, "compressed" versions of the original large graph.
  2. Local AM Solving: These compressed graphs fit within AM hardware limits and are solved using a Quadratic Unconstrained Binary Optimization (QUBO) formulation.
  3. The Guiding Block (GB): This is the core innovation where the AM acts as a "teacher." Its solutions are used as labels to supervise local GNNs, infusing the network with high-precision knowledge.
  4. Feature Mapping & Aggregation: Learned node representations from the small graphs are mapped back to the original large-scale graph.
  5. Guided Initialization: A "Main GNN" is initialized with these AM-informed features rather than random noise, leading to more stable and confident convergence.

Key Insights: The Teacher-Student Paradigm

The central breakthrough is treating the AM not as the final solver, but as a high-quality teacher. This allows the system to bypass the physical qubit limits of current annealing hardware. Furthermore, the authors found that AM guidance significantly reduces "late shifts"—a common issue in GNN solvers where node values flip-flop late in training—resulting in more stable optimization.

Experimental Results

The study utilized synthetic d-regular graphs with up to 150,000 nodes to test three canonical problems: Maximum Independent Set (MIS), Maximum Cut (MaxCut), and Graph Partitioning (GP).

Performance comparison across different graph sizes (n) and degrees (d), highlighting the relative improvement in solution quality and time savings.

Key results include:

  • Scaling Beyond Limits: The framework successfully solved 150k-node problems using an AM limited to 100k variables.
  • Superior Quality: For the MIS problem on 150k nodes, the hybrid approach achieved loss values 34.7% better than a standard multiresolution GNN without AM guidance.
  • Beating Heuristics: The model outperformed classical heuristics like Greedy Search. On large graphs (100k+), classical heuristics often failed to finish within a 2-hour window, while the hybrid model completed the task in roughly 12 minutes.
  • Constraint Handling: AM-guided versions consistently produced fewer constraint violations compared to pure GNN approaches.

Limitations and Future Work

While the solution quality is significantly higher, the AM-based local solving step introduces a computational overhead, making it roughly 9x slower than a pure GNN approach. Future research will focus on creating an end-to-end differentiable framework and investigating how partial solutions can be reused across different but structurally similar optimization problems.

Summary updated

BibTeX
@inproceedings{loyola2024annealing,
  author = {Pablo Loyola and Kento Hasegawa and Andres Hoyos-Idobro and Kazuo Ono and Toyotaro Suzumura and Yu Hirate and Masanao Yamaoka},
  title = {{Annealing Machine-assisted Learning of Graph Neural Network for Combinatorial Optimization}},
  booktitle = {MLNCP @ NeurIPS},
  year = {2024},
  url = {https://openreview.net/forum?id=zQndC6Uovb},
}
Figure