Are Graph Neural Networks Optimal Approximation Algorithms?

Graph Neural Networks are provably optimal approximation algorithms for large class of combinatorial optimization problems, which we also demonstrate empirically.