mlsanityData to 7 Oct 2026

Graph Coloring with Physics-Inspired Graph Neural Networks

arXiv 2202.01606 ↗First posted 3 Feb 2022cs.LG cond-mat.dis-nn cs.AIcited by 29

Not on the map. Why?

Abstract (arXiv)

We show how graph neural networks can be used to solve the canonical graph coloring problem. We frame graph coloring as a multi-class node classification problem and utilize an unsupervised training strategy based on the statistical physics Potts model. Generalizations to other multi-class problems such as community detection, data clustering, and the minimum clique cover problem are straightforward. We provide numerical benchmark results and illustrate our approach with an end-to-end application for a real-world scheduling use case within a comprehensive encode-process-decode framework. Our optimization approach performs on par or outperforms existing solvers, with the ability to scale to problems with millions of variables.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). Builds on 13 of its 51 references that are in the map. First posted on arXiv 3 Feb 2022.

Builds on

13 of 51 references.

References · 13

  1. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  2. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  3. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  4. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  5. 2013Ising formulations of many NP problemscited by 204
  6. 2021End-to-End Constrained Optimization Learning: A Surveycited by 154
  7. 2020DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphscited by 139
  8. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  9. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 107
  10. 2016Community detection in networks: A user guidecited by 105
  11. 2019Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problemscited by 40
  12. 2020Utilising Graph Machine Learning within Drug Discovery and Developmentcited by 26
1 more
  1. 2019Solving Multi-Coloring Combinatorial Optimization Problems Using Hybrid Quantum Algorithmscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 8; 2024: 10; 2025: 5; 2026: 6.

29 papers.

Sort:

By area:

  1. 2023Controlling Continuous Relaxation for Combinatorial Optimizationcited by 16
  2. 2023Are Graph Neural Networks Optimal Approximation Algorithms?cited by 10
  3. 2023Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setcited by 9
  4. 2024Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and Morecited by 6
  5. 2024Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Samplingcited by 6
  6. 2023A Graph Neural Network with Negative Message Passing for Graph Coloringcited by 5
  7. 2023Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problemscited by 5
  8. 2023Maximum Independent Set: Self-Training through Dynamic Programmingcited by 5
  9. 2024Message Passing Variational Autoregressive Network for Solving Intractable Ising Modelscited by 5
  10. 2024A Unified Framework for Combinatorial Optimization Based on Graph Neural Networkscited by 4
  11. 2024Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Updatecited by 4
  12. 2025Geometric Algorithms for Neural Combinatorial Optimization with Constraintscited by 4
17 more
  1. 2024Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problemscited by 3
  2. 2023Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~citeschuetz2022combinatorial,citeangelini2023modern,citeschuetz2023replycited by 1
  3. 2024Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphscited by 1
  4. 2024Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problemscited by 1
  5. 2024Scalable Parameter Design for Superconducting Quantum Circuits with Graph Neural Networkscited by 1
  6. 2025Nonlocal Monte Carlo via Reinforcement Learningcited by 1
  7. 2026Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problemscited by 1
  8. 2023Unsupervised Graph-based Learning Method for Sub-band Allocation in 6G Subnetworkscited by 0
  9. 2024Graph Neural Networks as Ordering Heuristics for Parallel Graph Coloringcited by 0
  10. 2025Efficient Optimization Accelerator Framework for Multistate Ising Problemscited by 0
  11. 2025Binarizing Physics-Inspired GNNs for Combinatorial Optimizationcited by 0
  12. 2025Unsupervised Graph Neural Network Framework for Balanced Multipatterning in Advanced Electronic Design Automation Layoutscited by 0
  13. 2026Neural Algorithmic Reasoning for Approximate k-Coloring with Recursive Warm Startscited by 0
  14. 2026Eidolon: A Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networkscited by 0
  15. 2026Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?cited by 0
  16. 2026Crystal structure prediction using graph neural combinatorial optimizationcited by 0
  17. 2026Distribution-Aware Algorithm Design with LLM Agentscited by 0