Reproduce “Combinatorial Optimization with Automated Graph Neural Networks” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Yang Liu, Peng Zhang, Yang Gao, Chuan Zhou, Zhao Li, Hongyang Chen

AutoGNP is an automated Graph Neural Network (GNN) framework developed to tackle NP-hard combinatorial optimization problems by autonomously designing GNN architectures. It demonstrated superior performance on benchmark tasks like MaxCut and Mixed Integer Linear Programming (MILP), often outperforming hand-crafted GNNs and classical solvers.

Key insights

  • Automating GNN architecture design can effectively enhance performance for NP-hard combinatorial optimization problems, moving beyond the limitations of manual design.
  • Specific optimization techniques, such as simulated annealing and strict early stopping, are crucial for successfully navigating the complex and often rugged loss landscapes characteristic of CO problems.
  • Incorporating a two-hop message passing operator into the GNN architecture allows for capturing more global combinatorial information, which is beneficial for solving complex NP-hard problems.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.