Dense k-Subgraph, eh? I wrote a dissertation on that in a past life. From a quick read of the paper, it looks like the only classical algorithms they compare t

Dense k-Subgraph, eh? I wrote a dissertation on that in a past life. From a quick read of the paper, it looks like the only classical algorithms they compare to are greedy, random search, and simulated annealing (which is more or less random plus greedy). For random or semi-random instances like those described in this writeup, there are oftentimes substantially better classical algorithms (both random and deterministic) that one can use to try to find dense components (including, ironically, so-called "spectral" algorithms which are entirely classical). They don't provide the specific parameter setting so I can't give a single definitively better method, but I'm relatively unimpressed by their finding that a somewhat heavily engineered approach can defeat a handful of braindead classical algorithms.