Not Constructing Ramsey Graphs Using Deep Reinforcement Learning
Abstract
We consider the problem of constructing Ramsey graphs using deep reinforcement learning. We introduce a novel permutation invariant architecture that combines ideas from GNNs with self-attention algorithms over the cliques, which shows promising results in a related regression task. To generate graphs, we train our model using established reinforcement learning algorithms such as PPO and A2C. Our results are however very poor compared to traditional local-search algorithms, indicating that this problem is not well-suited for neural networks yet.
Cite
Text
Berghaus. "Not Constructing Ramsey Graphs Using Deep Reinforcement Learning." ICLR 2025 Workshops: ICBINB, 2025.Markdown
[Berghaus. "Not Constructing Ramsey Graphs Using Deep Reinforcement Learning." ICLR 2025 Workshops: ICBINB, 2025.](https://mlanthology.org/iclrw/2025/berghaus2025iclrw-constructing/)BibTeX
@inproceedings{berghaus2025iclrw-constructing,
title = {{Not Constructing Ramsey Graphs Using Deep Reinforcement Learning}},
author = {Berghaus, David},
booktitle = {ICLR 2025 Workshops: ICBINB},
year = {2025},
url = {https://mlanthology.org/iclrw/2025/berghaus2025iclrw-constructing/}
}