Are Graph Neural Networks Optimal Approximation Algorithms?

Morris Yau, Nikolaos Karalias, Eric Lu +2

In this work we design graph neural network architectures that capture optimal approximation algorithms for a large class of combinatorial optimization problems, using powerful alg…