Vertex Coloring By Subgraph Expansıon In Unsupervised Graph Neural Networks: Constructing A Curriculum By Iterative Growth Of Subgraphs Of An Input Graph

Vertex coloring is a classic combinatorial optimization problem in which each vertexof a graph must be assigned a color so that no two adjacent vertices share thesame color. This problem is known to be NP-complete for determining whethera graph can be colored with k colors, and finding the minimum number of colorswithout conflicts is NP-hard (Garey & Johnson, 1990). It has important applicationsin scheduling, register allocation, timetabling, and other domains. In recentyears, Graph Neural Networks (GNNs) have emerged as powerful models for graphstructuredlearning, and can tackle vertex coloring by framing it as an unsupervisednode-classification task. In particular, Schuetz, Brubaker, Zhu & Katzgraber (2022)show that a physics-inspired approach optimized a Potts-based loss to encouragevalid colorings. This GNN-based method has achieved performance on par with orbetter than classical solvers, even scaling to graphs with millions of vertices.In this thesis, I propose a novel curriculum-inspired training strategy for vertexcoloring using unsupervised GNNs. The method begins by training on a smallsubgraph and incrementally expands the training set (through layer-by-layer BFSbased,Breadth-First-Search, expansion, degree-first BFS-based expansion, or randomwalk expansion) to cover the entire graph. This curriculum-like incrementaltraining exposes the network learn in stages, leveraging pre-trained embeddings andpre-trained model weights from the subgraph of the previous stage.Two GNN architectures (a Graph Convolution model and a GraphSAGE model) were implementedand trained with a continuous Potts-based loss. We evaluated our approach ona subset of the COLOR benchmark dataset (including Mycielski graphs, n-queengraphs, and a social network graph). The experiments show that the subgraphexpansion methods—especially the degree-first BFS variant—reduces total trainingtime by 30–35% while maintaining statistically comparable conflict counts. Theseresults suggest that the curriculum-like incremental training is a promising directionfor leveraging GNNs in combinatorial graph tasks.