Evaluating Different Node Feature Extraction Methods for Graph Coloring Problem with Graph Neural Network

The graph coloring problem (GCP) is a classical NP-hard problem that aims to assign different colors to adjacent nodes while minimizing the total number of colors used. While previous studies have used graph neural networks (GNNs) to solve GCP, they rely only on randomly initialized node features or a trainable embedding layer, leaving other alternative node feature extraction methods unexplored. Therefore, this study explores eight node feature extraction methods, including positional and structural node features. We assess their impact on GNN performance for GCP and provide insights into why certain methods outperform others. Across 12 COLOR graphs and 3 large citation graphs, experimental results show that both the trainable embedding layer and node2vec achieve the strongest performance. Under different hyperparameter settings, embedding layer demonstrates consistent effectiveness in minimizing conflicts across GNN architectures, while node2vec demonstrates greater average performance and stability on large graphs. Compared to the embedding layer baseline, node2vec reduces mean conflicts by 43.63% and standard deviation by 27.23% on large citation graphs. However, their performance gains involve a computational trade-off: embedding layer requires backpropagation, and node2vec requires pre-computation for its biased random walks. Furthermore, positional node features give better prediction performance than structural ones, having approximately 9.3× lower mean conflicts in the best case.