Speaker
Description
The graph coloring problem is an optimization problem involving the assignment of one of q colors to each vertex of a graph such that no two adjacent vertices share the same color. This problem is computationally challenging and arises in several practical applications. We present a novel algorithm that leverages graph neural networks to tackle the problem efficiently, particularly for large graphs. We propose a physics-inspired approach that leverages tools
used in statistical mechanics to improve the training and performances of the algorithm. The scaling of our method is evaluated for different connectivities and graph sizes. Finally, we demonstrate the effectiveness of our method on a dataset of Erdős–Rényi graphs, showing its applicability also in hard-to-solve connectivity regions, where traditional methods struggle.
| AI keywords | Optimization:Graph Neural Networks:Physics Informed Models:Statistical Mechanics |
|---|
