Position: Neural Approximation Is Rarely Justified for Hard Combinatorial Problems

In recent years, there has been a surge in the application of neural approaches to NP-hard combinatorial problems such as subgraph isomorphism, maximum clique and the travelling salesman problem in graphs. These approaches are often evaluated as complete replacements of established combinatorial solver tools, with emphasis on solution quality and runtime. In this position paper, we argue that such wholesale replacements for touted faster inference or better solution quality should not be considered the primary motivation for neural surrogates, and a systematic evaluation of when neural methods are appropriate is required. Given our observations, we contend that in the absence of system-level requirements dictated by the task at hand, such as vector indexing and retrieval, or without the need for end-to-end differentiability, neural surrogates rarely offer compelling advantages over the standard combinatorial solver. In this vein, we develop a comprehensive report of where current neural methods fall short, and subsequently devise a diagnostic checklist for when neural methods are truly applicable.