Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set

Maria Chiara Angelini, Federico Ricci-Tersenghi

The recent work ``Combinatorial Optimization with Physics-Inspired Graph Neural Networks'' [Nat Mach Intell 4 (2022) 367] introduces a physics-inspired unsupervised Graph Neural Ne…