- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper aims to develop a neural framework to solve graph coloring problem. The main theme of the paper is studying the symmetries involved while solving the coloring problem. It can be observed that a valid coloring is invariant to permutations of the colors. Also, some nodes may appear symmetrical and solver may assign a similar color but one has to make sure that no adjacent nodes are labelled the same color. The paper targets these symmetries by proposing SCONE , a framework that combines color-permutation equivariance with sequential decoding. The solver uses a message-passing GNN that maintains separate, shared-parameter embeddings for each color, ensuring that its predictions transform consistently under color relabeling. To avoid color conflicts between adjacent nodes, SCONE assigns colors sequentially, one node at a time, allowing previous assignments to break node symmetries and distinguish nodes that are otherwise indistinguishable to an equivariant predictor. Theoretically, the authors characterize the reduction in the effective state space induced by color equivariance and establish expressivity results for sequential coloring on specific graph families. Experimentally, SCONE is evaluated on Sudoku, register-allocation, and examination-timetabling instances as well as on synthetic graph families. The results demonstrate strong solution quality, fast inference and good generalization to graph families not encountered during training. Ablation studies also suggest that architectural color equivariance improves performance especially for graphs with large chromatic number.
Critical strengths
-
The symmetry-aware approach taken is well motivated as one usually observes that using plain GNN does not target these symmetries and often lead to poor coloring solutions. Rather than predicting colors simultaneously for all nodes, the sequential decoding approach helps to distinguish nodes properly as coloring progresses.
-
The proposed color-equivariant message-passing GNN respects color-label permutations by construction, exploiting the inherent symmetries of graph coloring rather than relying solely on data augmentation.
-
The paper’s theoretical approach distinguishes it from other works on neural solvers. From the start, the authors explain graph symmetries using the concepts of automorphisms and orbits. Further, in theoretical analysis, it is discussed how effective state space reduces due to color equivariance. Also the paper establishes expressivity results for sequential coloring on specific graph families.
-
For experimental evaluation, the method is evaluated across diverse graph-coloring applications, including Sudoku, register allocation, examination timetabling and synthetic graph families. The reported results demonstrate strong solution quality and competitive inference times.
Critical weaknesses
-
SCONE requires up to O(n) forward passes to color a graph with n nodes. This sequential dependence may limit its applicability to large-scale graph-coloring instances and the experiments do not fully establish how the method scales with graph size.
-
The model takes number of colors to be used for coloring (k) as input and in cases when one has to particularly find the chromatic number, we need to solve multiple times for different values of k.
-
The method acts as a heuristic and does not provide solution guarantees. It always returns a complete coloring but it does not guarantee that the coloring is proper or certify infeasibility for a given palette.
-
The model is not tested properly against state of the art methods. Comparisons are drawn with heuristics such as greedy and Dsatur. Although we have much stronger heuristics such as Recursive Largest First (RLF) and also a lot of metaheuristics that have demonstrated good performance. Few of these methods should also be considered for comparison.
-
Although it is a positive aspect of the paper that the authors evaluate SCONE on instances drawn from practical applications, it would also be valuable to include standard DIMACS benchmark instances which are widely used in the graph coloring literature. This would facilitate a more direct comparison with existing methods and provide a better assessment of the proposed approach on established benchmarks.
Questions for authors
-
As pointed out in the weaknesses , it would be useful to provide a more detailed scalability analysis. How does the inference time grow with increasing graph size, particularly for graphs containing thousands of vertices? Including experiments on larger instances would help establish the practical scalability of the proposed approach.
-
The experimental evaluation should include state of the art metaheuristics like HEAD or swarm optimization based algorithms and heuristics like Recursive Largest First (RLF) for a fair comparison. Furthermore, for comparison with neural solvers, one can also include the neural solver based on sequential coloring discussed in the paper “graph coloring via metric guided independent set extraction”. How does SCONE perform against these approaches in terms of solution quality and computational time under comparable computational budgets ?
-
The evaluation must be extended to standard DIMACS graph coloring benchmarks. These instances are widely used in the graph coloring literature and would allow a more direct comparison with existing state-of-the-art methods. Evaluating SCONE on these benchmarks would also help assess its effectiveness in dealing with color symmetries on graphs with diverse structural properties and varying levels of difficulty.
-
As a suggestion, the presentation could be made more accessible to a broader audience by simplifying the explanations of technical concepts such as automorphisms, orbits, and stabilizers and providing more intuitive explanations or examples to help readers understand their role in the proposed approach.
4 comments
Dear Reviewer iJhw,
Thanks for your insightful review. We hope that our response has adequately addressed all your comments, particularly with regard to the new scalability experiments and the addition of new datasets and baselines. As the discussion period will end in less than 2 days, we would appreciate it if you could take a look at our rebuttal and let us know if you have any further or follow-up questions so that we can address them in time.
I thank the authors for their response and for addressing the concerns raised in my initial review. From figure 12 included, it is good to observe that the method is scaling well for large graphs. Also I appreciate the inclusion of additional baselines such as RLF,GBS,CSO etc and DIMACS instances in the experimental evaluation. The additional experimental results included helps in better comparison and understanding the novelty of the proposed approach. I will maintain my rating of 3.
Thank you for your reply. We are glad that our responses and additional experiments have addressed your concerns.
Thank you for your insightful review and for your positive remarks, especially on our theoretical approach distinguishing the paper from other works on neural solvers, and on the strong solution quality and competitive inference times. We address your comments one by one below.
As discussed in Appendix A, requiring up to O(n) forward passes to color a graph with n nodes is indeed one of the limitations of Scone, as it can limit scaling inference efficiently to graphs with several thousand nodes. However, this additional computational cost comes with the benefit of allowing sequential decoding to fully exploit information from previous color assignments. Therefore, on graphs with up to several hundred nodes, it is arguably a worthy trade-off. Following your suggestion, we have now added Figure 12, which plots the runtimes of Scone on synthetic graphs with up to 10k nodes, using both greedy decoding and beam search with width 16. As shown by the plot, greedy inference is below one second even for graphs with a thousand nodes.
Your observation is indeed correct, to search for smaller upper bounds on the chromatic number one has to run Scone multiple times for different values of k. This fixed-palette setting is also considered by AnyCSP and ConsFormer, and is standard in CSP and ILP formulations of graph coloring.
Scone can efficiently obtain good upper bounds on the chromatic number. We have added Figure 10 to evaluate this scenario. Starting from a Dsatur coloring, we repeatedly attempt a proper coloring with one fewer color, stopping at the first failure and retaining the best proper coloring found. Across 20 independent searches, Scone reaches the best-known color counts on all three tested hard instances, faster than AnyCSP.
As noted also in the answer above and in Appendix A (Limitations), the comment is correct. Scone, like any other heuristic method, cannot guarantee that it will return a proper coloring given a palette size k, nor certify that no proper coloring exists. Note that since k-coloring is NP-complete for n≥3, no algorithm can decide feasibility correctly on all graphs in polynomial time unless P=NP. However, given a complete coloring returned by Scone, it is easy to certify that it is proper (by checking that there are no monochromatic edges). Moreover, even in scenarios where exact solutions are required, good-quality heuristics are nonetheless important for screening. For example, if we are given a large number of k-coloring problems, a heuristic like Scone can be used to solve cheaply a large fraction of them, and only the unsolved instances can be passed to the expensive complete solvers (e.g., ILP or CSP) to find a solution or certify impossibility.
We would argue that ACE, Gurobi and AnyCSP cover different classes of state-of-the-art solvers. However, we agree that adding more baselines would further strengthen the evaluation. Following your suggestion, we have now added RLF and CSO, a recent swarm optimization algorithm, as classical baselines, and GBS as a learning-based baseline. We have also added two more neural baselines based on another reviewer's comment. As reported in Tables 1,3,4 and Tables 10,11 in the appendix, the most competitive baselines remain ACE and AnyCSP.
Datasets drawn from practical applications are indeed a focus of our evaluation. However, we agree that comparing on well-established benchmarks can help compare to related work. We have now added three more families of graphs from the DIMACS collection (besides the already-present Queens and Mycielski graphs), see Tables 12,13,14,15. In particular, books are graphs where nodes are connected by an edge if the corresponding characters encounter each other in the book, DSJC are Erdos-Renyi graphs and le450 are random graphs with guaranteed coloring size. Results on these graphs confirm the Scone generalizes to unseen instances, often being on par or better than state-of-the-art solvers like ACE and AnyCSP.
Thanks for the suggestion, we have added a few more intuitive explanations for automorphisms and orbits (line 101) and for stabilizer groups (line 297).