VColRL: Learn to Solve the Vertex Coloring Problem Using Reinforcement Learning
Vertex Coloring Problem;Markov Decision Process;Reinforcement Learning;Graph Neural Networks;Combinatorial Optimization
Yes
No ethics review needed.
1. How does the proposed algorithm decide when to activate the hard-rollback model versus the soft-rollback model?
2. Is the initial number of colors for each instance incremented starting from zero or from a specific given value?
3. The benchmarks in the COLOR02 table can include both DIMACS and COLOR02 instances. The benchmark instances could be more comprehensive, such as including DSJC125.5, DSJC125.9, DSJC250.1，and others.
1. This paper proposes a reinforcement learning framework that integrates the GraphSAGE architecture for the VCP.
2. A novel reward strategy specifically designed for the VCP is introduced.
3. Extensive experiments demonstrate the effectiveness of the proposed algorithm in comparison to state-of-the-art baselines.
This paper proposes a reinforcement learning framework for solving the vertex coloring problem (VCP). The main idea is to use an episodic Markov Decision Process (MDP) to effectively model the dynamics of the coloring process, utilizing both Proximal Policy Optimization (PPO) and GraphSAGE. The writing is clear and well-organized.
1. Please clarify the novel features introduced in the MDP formulation, and how these differ from or build upon existing approaches like the defer action strategy..
2. Gurobi should be set to a consistent execution time across different benchmarks, and it would be beneficial to provide a longer execution time result as a reference for the optimal solution. 
3. Given that the proposed algorithm employs rollback mechanisms similar to iterative search, it would be appropriate to include an iterative search heuristic (i.e., tabuCol) as a comparison.
Yes
No ethics review needed.
1.How does VColRL perform in terms of computational efficiency in real-world applications?
2.What specific factors contribute to VColRL’s limited performance on certain graph types, such as the mug family?
3.What criteria were used to select the final hyperparameter values and model configurations?
1.VColRL outperforms traditional mathematical solvers and baseline methods, particularly for large and dense graphs, by effectively minimizing color usage. 
2.By using a unique reward strategy that prioritizes minimizing the highest-numbered color, VColRL efficiently manages color allocation, reducing convergence time and improving performance. This MDP design is a key factor in achieving both optimal color usage and stable results in the vertex coloring process.
The paper presents VColRL, a novel reinforcement learning framework for solving the Vertex Coloring Problem (VCP). The goal of VCP is to color graph vertices with the minimum number of colors so that no two adjacent vertices share the same color. VColRL uses a custom Markov Decision Process (MDP) to model VCP dynamics, optimizing color usage and generalizing well to diverse graph types.
1.While VColRL demonstrates strong performance on large-scale graphs, its complex architecture and computational demands are relatively high. The paper does not provide sufficient detail on its efficiency or scalability in practical applications, which raises concerns about its usability in resource-limited environments.
2.Although VColRL performs well on most tested graphs, it is less effective on certain types, such as the mug family of graphs. The paper lacks a thorough analysis of why VColRL underperforms on these specific graphs, which slightly weakens its claims of general applicability.
3.The paper discusses important design choices, such as rollback and reward strategies, but does not sufficiently explain the rationale behind these choices. Additionally, while hyperparameter settings and the training process are briefly covered, there is limited explanation on how the final parameter combinations were decided, reducing the model’s reproducibility and interpretability.
Yes
No ethics review needed.
- In the comparison of various MDP configurations results section, was the color count reward with other settings than hard rollback and deferred actions considered? If not isn't it possible that color count with a different setting outperforms HDM?
- The paper is well-written and easy to follow. The related work section highlights existing gaps and shows how the proposed method differs from existing work. The main contribution is also well documented.
- The suggested modifications to the MDP formulation and the feature selection in previous work are an elegant approach to the vertex coloring problem, for example, the different roll-back strategies and the two reward functions.
- The proposed method outperforms existing baselines in the larger graph sizes.
The authors tackle solving the Vertex Coloring Problem which is a known NP-hard problem using reinforcement learning. They formulate the problem as a Markov-Decision Process whose dynamics capture the graph coloring process. The agent is tasked with taking actions which include assigning colors to a subset of nodes and deferring other nodes to be assigned later. Two reward functions are proposed, max-color and color-count. An agent is trained using PPO where the graph neural network GraphSAGE is used as the function approximator. The experimental results show that the proposed methods outperform existing baselines.
- The paper’s contribution, while valuable, may benefit from additional innovation, as it shares similarities with prior work by Ahn et al. which tackles the Maximum Independent Set also using Deep RL and GraphSAGE architecture. Further discussion on how the work is unique and where the overlap lies could strengthen the value of the work.
- There is not a lot of insight into why the method performs the way it does. For example, the results show that the color count reward is not as good as the max-color reward, but no discussion is provided about why that would be the case. 
- In the results section, the selected baselines do not include a machine learning-based approach.
-  In the related work the Vertex coloring problem is described as NP-complete. However, according to my understanding, the vertex coloring problem considered is the optimization version which is NP-hard, and not the decision version.
VColRL is a reinforcement learning framework that solves the vertex coloring problem.
@inproceedings{
anonymous2024vcolrl,
title={{VC}ol{RL}: Learn to Solve the Vertex Coloring Problem Using Reinforcement Learning},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=nIBmwm7ixo},
note={under review}
}
We present VColRL, a reinforcement learning framework designed to solve the vertex coloring problem (VCP), where the objective is to assign colors to the vertices of a graph with the minimum number of colors, such that no two adjacent vertices share the same color. The framework is built on a novel Markov Decision Process (MDP) configuration to effectively capture the dynamics of the VCP, that we develop after evaluating various MDP configurations. Our experimental results demonstrate that VColRL outperforms advanced mathematical solvers and other baseline methods, particularly on large and dense graphs. Additionally, our results show that VColRL generalizes well on different types of graphs.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Vertex Coloring Problem Markov Decision Process Reinforcement Learning Graph Neural Networks Combinatorial Optimization
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/17bc37a6e16b72e4556a11a895e4dff55d7e2502.pdf
reinforcement learning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/38fa2af6a48d1776f5b62094f595d38b02b8e00e.zip
VColRL: Learn to Solve the Vertex Coloring Problem Using Reinforcement Learning
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission