Title: Contrastive Neural Algorithmic Reasoning for Graph Coloring

Abstract:

Graph coloring involves assigning colors to a graph's vertices such that no two connected nodes share the same hue, with the primary objective of minimizing the total number of colors used. In this work, we investigate the problem of approximate $k$-coloring, which aims to restrict the palette to no more than $k$ colors while simultaneously reducing the count of monochromatic edges. This challenge is fundamental to graph theory and holds significant practical value in domains like resource allocation and scheduling.

While recent unsupervised Graph Neural Network (GNN) methods optimize solutions for individual instances, they fail to generalize across varying graph sizes and distributions. To address this limitation, we introduce a contrastive learning framework designed to acquire transferable coloring geometries. Within this framework, node embeddings corresponding to the same color are aligned, whereas representations of adjacent nodes are driven toward divergent directions.

We examine the population objective derived from this approach on graphs with bounded sizes. Specifically, for embeddings with unit norms, we demonstrate that the optimal solutions exhibit a line-prototype structure. In this configuration, nodes sharing a color converge onto a common one-dimensional subspace, while edges link these subspaces orthogonally. This geometric arrangement satisfies stationarity conditions found in supervised settings and remains invariant under projected subgradient dynamics, provided a balanced-coloring assumption holds. Furthermore, in an unnormalized variant, gradient descent exhibits a max-margin bias that is dictated by a hard-margin problem defined on a quotient graph.

Our experiments, conducted on both synthetic and real-world datasets, indicate that contrastive GNN encoders achieve strong generalization capabilities. They generate colorings with minimal conflicts, performing on par with, and occasionally surpassing, traditional greedy algorithms.

Source: arXiv Generated at: 2026-06-03 00:00:00 UTC