Reinforcement Learning for Graph Coloring: Understanding the Power and Limits of Non-Label Invariant Representations
Register allocation is one of the most important problems for modern compilers. With a practically unlimited number of user variables and a small number of CPU registers, assigning variables to registers without conflicts is a complex task. This work demonstrates the use of casting the register allocation problem as a graph coloring problem. Using technologies such as PyTorch and OpenAI Gymnasium Environments we will show that a Proximal Policy Optimization model can learn to solve the graph coloring problem. We will also show that the labeling of a graph is critical to the performance of the model by taking the matrix representation of a graph and permuting it. We then test the model's effectiveness on each of these permutations and show that it is not effective when given a relabeling of the same graph. Our main contribution lies in showing the need for label reordering invariant representations of graphs for machine learning models to achieve consistent performance.
Code (0)
등록된 구현이 없습니다.
Tasks
CPUSimilar Papers 제목 키워드 기반
Rethinking Graph Neural Networks for the Graph Coloring Problem
Graph coloring, a classical and critical NP-hard problem, is the problem of assigning connected nodes as different colors as possible. However, we observe that state-of-the-art GNNs are less successful in the graph color…
Evaluating the Systematic Reasoning Abilities of Large Language Models through Graph Coloring
Contemporary large language models are powerful problem-solving tools, but they exhibit weaknesses in their reasoning abilities which ongoing research seeks to mitigate. We investigate graph coloring as a means of evalua…
BenchmarkingReinforcement learning based local search for grouping problems: A case study on graph coloring
Grouping problems aim to partition a set of items into multiple mutually disjoint subsets according to some specific criterion and constraints. Grouping problems cover a large class of important combinatorial optimizatio…
Combinatorial Optimizationreinforcement-learningReinforcement LearningReinforcement Learning (RL)Rethinking Graph Neural Networks for Graph Coloring
The development of graph neural networks (GNNs) stimulated the interest in GNNs for NP-hard problems, while most works apply GNNs for NP-hard problems by empirical intuition and experimental trials and improve the result…
Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings
Graph isomorphism testing is usually approached via the comparison of graph invariants. Two popular alternatives that offer a good trade-off between expressive power and computational efficiency are combinatorial (i.e., …
Computational EfficiencyIsomorphism TestingOpen-Ended Question Answering