Understanding Graph Representation Learning in Reinforcement Learning Based Logic Synthesis

Computer chips ought to be as small as possible for cost efficiency. The problem of minimizing chip size while preserving the chip's functionality has been studied through the prism of and-inverter graphs (AIGs), since any Boolean function can be represented by an AIG. Because the complexity of AIG size minimization is unknown---it is an instance of the minimum circuit size problem, which lies in NP but is not known to be NP-hard---no procedure returns optimal AIGs at the sizes of interest, and there is therefore no supervision signal in the form of optimal AIGs to imitate. Reinforcement learning, and more generally planning, have been used to minimize AIGs in the absence of such a signal. Meanwhile, graph representation learning has been applied to train machine learning models to perform tasks on graph data. More recently, those two technologies have been combined and reported to outperform state-of-the-art logic synthesis heuristics, but the relative importance of graph representation learning in those methods remains unknown. Is graph representation learning useful when minimizing and-inverter graphs with reinforcement learning?