acceptodds
Under review as a conference paper at ICLR 2027

Contrastive Neural Algorithmic Reasoning for Graph Coloring

Abstract

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 -coloring, where the goal is to use at most 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
neural algorithmic reasoning, contrastive learning, graph neural networks, graph coloring, representation geometry, combinatorial optimization, Lovász theta function

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_u5kfOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

Graph coloring is a classic optimization problem in graph theory. This paper proposes a contrastive learning framework to study the k-graph coloring problem, such that the embeddings of nodes with the same color converge to the same straight line and become aligned, while the embeddings of adjacent nodes tend to be pushed apart in orthogonal directions. Theoretically, this paper proves an exact lower bound for the contrastive loss and presents the global convergence results of projection optimization under Gram parameterization and the convergence analysis of the shared encoder. Experiments on synthetic and real graphs verify the transferability of the method on different graph sizes and datasets, showing that the method can achieve low-conflict assignments but allows for a small number of monochromatic edges.

Critical strengths
  1. The research approach is relatively novel. This paper transforms the relationships in graph coloring into node embedding optimization through contrastive learning, aligning the embeddings of nodes with the same color and pushing the embedding representations of adjacent nodes towards orthogonality.

  2. The theoretical analysis is relatively comprehensive. This paper provides a lower bound for the contrastive loss and presents the global convergence results of projection optimization under Gram parameterization, as well as the convergence analysis of the shared encoder. The theoretical foundation is quite solid.

Critical weaknesses
  1. The paper proposes embedding nodes of the same color onto a single line, with adjacent nodes embedded in orthogonal directions. However, the experiments did not measure the distance between nodes of the same color or the degree of orthogonality between adjacent nodes, thus failing to fully demonstrate that the performance stems from this geometry.

  2. Although the paper emphasizes scalability, it does not provide a formal time or space complexity analysis of the entire algorithm. Actual runtime alone cannot determine how the proposed method varies with graph size, embedding dimensions, etc.

Questions for authors
  1. The core mechanism of the paper is line collapse of nodes of the same color and the tendency of adjacent nodes to become orthogonal. Could the authors directly report the intra-class distance and the orthogonal directions of different classes?

  2. In the ablation experiments, the authors extracted some subgraphs from Cora for training and testing. The training and testing center nodes are different, but do they share the same nodes during sampling?

  3. The experiments used DSATUR coloring. Is the representation learned by the model sensitive to the quality of these supervised colorings?

  4. How was the 5% conflict threshold determined? Was it the optimal value obtained experimentally or derived from theoretical analysis?

1 comment

Thank you to the authors for their response. The clarifications have adequately addressed my concerns. I will therefore maintain my positive assessment of the paper.

Reviewer_J9rWOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies supervised contrastive representations for approximate graph coloring. Same-color vertices are positives and graph neighbors are negatives. An absolute-inner-product objective has global optima in which nontrivial color classes collapse to lines and adjacent classes are orthogonal. The paper develops excess-loss bounds, convergence results for specified Gram-space and frozen-feature readout updates, a nonlinear extension of a low-rank SDP landscape inequality, and spectral and prototype-based certificates. Experiments train GNN encoders on supplied colorings and decode embeddings by clustering, evaluating the tradeoff between palette size, conflicts, and inference time on citation graphs, COLOR families, and synthetic graphs.

Critical strengths

The representation analysis is precise about what the loss enforces. The equality characterization distinguishes proper from optimal supervision, handles isolated classes, and does not confuse fitting a supplied partition with minimizing its number of colors. The excess-loss analysis also treats the implemented logarithmic objective and identifies its singleton-class coverage limitation. These distinctions make the theoretical contribution more useful than an informal analogy with neural collapse.

The analysis goes beyond the exact optimum. The radial domination argument, nonlinear Gram-curvature extension, and signed spectral correction provide concrete optimization and certification results. The paper also includes a suboptimal absolute-margin example rather than asserting unrestricted global optimization. Relative to the unconstrained-feature analysis of Behnia and Thrampoulidis (2024) and the linear-SDP analysis of Mei et al. (2017), the graph-restricted negatives, absolute scores, and nonlinear objectives require additional arguments.

Critical weaknesses

I'm not sure how well the reported comparisons establish performance beyond model selection. Appendix I states that model choices used reported evaluation scores, that an untouched selection/test split is not documented, and that individual predictions and checkpoints are unavailable. The separation of selection and final evaluation is therefore unclear, though this does not establish that no split existed. Appendix L explicitly reports OOD-based selection and differing aggregates for identically named configurations. The authors disclose these differences and exclude Table 35 from best-configuration conclusions, although the same selected summary also appears in Table 1. Tables 25–26 likewise mark potentially sentinel-affected summaries as NR, but per-seed failure counts remain unavailable. These disclosures appropriately limit the generalization claims. The main transfer conclusions need support from a fixed configuration on graphs not used for selection, with per-instance outcomes and failures recorded separately. Seed standard deviations cannot resolve the selection and provenance questions.

It is unclear how much the analyzed geometry contributes to practical performance. The shared-encoder convergence theorem uses constructed full-rank frozen features, a smooth surrogate, preconditioned updates, and output dimension at least the largest training graph. These assumptions are explicit and the result is conditional, but the setup differs from the experiments' end-to-end GNN training. The main text explicitly acknowledges that learned line collapse is not directly measured, and the experiments do not report how often the certificate conditions hold. The ablations are extensive. Table 7's controlled signed/absolute comparison lowers mean conflicts while increasing the mean palette, and the selected COLOR configurations use signed losses. This shows a palette–conflict tradeoff but does not isolate a benefit of the absolute-line geometry. Direct measurements of the learned geometry and certificate applicability would help connect the analysis to decoding quality.

Questions for authors

Which run records and aggregates are authoritative for Tables 1 and 35–38, and what is the intended role of each? How were selection and final evaluation separated? Are fixed-configuration results on an untouched test set available, with per-instance outcomes and failures recorded separately?

For the implemented absolute-loss models, can you report within-class line dispersion, edge overlaps, and how often the prototype-affinity conditions yield nonvacuous certificates? How do these relate to decoding quality?

Reviewer_cfuvOpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a supervised contrastive learning framework for approximate graph coloring. Given proper coloring labels, the method encourages same-color node embeddings to align along common unoriented lines and adjacent embeddings to become orthogonal. At inference, embeddings are decoded through sign canonicalization and clustering, with palette selection based on the observed conflict rate. The paper characterizes the geometry of loss minimizers, establishes convergence results under specified optimization and encoder assumptions, and derives conditional decoding certificates. Experiments evaluate coloring performance and transfer across graph sizes and datasets.

Critical strengths

The paper provides an informative geometric interpretation of contrastive coloring supervision.

Under proper coloring supervision and sufficient embedding dimension, the analysis characterizes how the objective produces common lines for color classes and orthogonality across adjacent classes. The connections between excess loss, representation geometry, and conditional decoding certificates provide a useful account of what the learned representations can establish. This theoretical perspective is an appealing aspect of the contribution, although its assumptions limit direct applicability to the complete experimental pipeline.

Critical weaknesses

W1. The experiments do not sufficiently establish the method’s practical advantages in solution quality and computational cost.

The primary success criterion permits up to 5% monochromatic edges. This is a valid approximate optimization setting, but it can leave substantial violations in applications requiring feasible assignments, such as scheduling. Although the paper provides theoretical repair bounds, the experiments do not establish the resulting palette size and runtime after repairing the predicted assignments. Consequently, the practical value of the reported low-conflict solutions remains insufficiently demonstrated.

Palette size must be assessed jointly with feasibility. Using fewer colors while allowing conflicts does not directly establish an improvement over a proper coloring. In the paper’s own solver evaluation, HEA produces proper assignments in all 484 attempts and reaches the prescribed target in 480. These results leave the practical trade-off insufficiently resolved: the evaluation should more clearly establish when the learned method offers a compelling advantage at comparable solution quality.

W2. The generalization evaluation is weakened by model-selection practices and unresolved reporting inconsistencies.

The caption of Table 1 explicitly states that configuration selection uses OOD scores. Selecting configurations using the reported target evaluation results prevents those results from serving as an independent assessment of generalization. The paper needs a clearer separation between validation-based selection and evaluation on an untouched test set.

The COLOR evaluation contains only two Book graphs, two Myciel graphs, and seven Queen graphs. Reporting ten random seeds helps characterize training variability, but does not compensate for the limited number of independent graph instances. This small evaluation set limits the strength of the conclusions about generalization across graph instances and sizes.

Questions for authors

What palette sizes and runtimes are obtained after repairing the predicted assignments into proper colorings? How does the resulting quality–cost trade-off compare with HEA and the greedy coloring reference?

Which data are used for configuration selection, and which results come from a final test set untouched during selection? In particular, how should the OOD-based selection reported in Table 1 be interpreted?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.