Contrastive Neural Algorithmic Reasoning for Graph Coloring

Graph coloring seeks to assign colors to a graph's nodes so that adjacent nodes receive different colors, using as few colors as possible. Here, we study approximate $k$-coloring, where the goal is to use at most $k$ colors while minimizing the number of monochromatic edges. This problem is central to graph theory and has applications in areas such as scheduling and resource allocation. Recent unsupervised GNN approaches optimize each instance directly, without amortizing optimization across test graphs. We instead propose a contrastive learning framework that encourages transferable coloring geometry where the embeddings of same-color nodes align up to sign, while adjacent nodes' representations are pushed toward orthogonal directions. With proper labels and sufficient dimension, every optimum of our contrastive loss variant over unit embeddings collapses each color class containing a non-isolated vertex onto a common line, with adjacent vertices lying on orthogonal lines. Under these assumptions, optimizing our InfoNCE variant over unit-norm embeddings approaches the geometry of a global hard-margin solution. On finite graph collections, we prove global convergence for projected subgradient descent in the Gram parameterization. Under suitable conditions, shared ReLU encoders with frozen features converge almost surely to the same global objective value through a smooth surrogate. A signed spectral Lov\'asz theta bound strengthens the local edge-error certificate and complements direct conflict and properness certificates. Experiments on synthetic and real-world graphs evaluate transfer across graph sizes and datasets and yield low-conflict assignments, at the cost of allowing a small number of monochromatic edges.