Performance of Neural Net Heuristics for Maximum Clique on Diverse Highly Compressible Graphs

The problem of finding the size of the largest clique in an undirected graph is NP-hard, even to well-approximate, in the worst case. Simple algorithms, including some we study here, work quite well however, on graphs sampled from u(n), the uniform distribution on n-vertex graphs. It is felt by many, however, that u(n) does not accurately reflect the nature of instances that come up in practice. It is argued that when the actual distribution of instances is unknown, it is more appropriate to suppose that instances come from the Solomonoff-Levin or universal distribution m(x) instead, which assigns higher weight to instances with shorter descriptions (i.e., to those that are structured or compressible). We extend a theorem of Li and Vitanyi to show that the average-case performance ratio of any approximation algorithm on random instances drawn from m(x) has the same asymptotic order as its worst-case performance ratio. Because m(x) is neither computable nor samplable, we employ a realistic analogue q(x) which lends itself to efficient empirical testing. We experimentally evaluate how well certain neural network algorithms for Maximum Clique perform on graphs drawn from q(x), as compared to those drawn from u(n). The experimental results are as follows. All nine algorithms we evaluated performed roughly equally-well on u(n), where as three of them - the simplest ones - performed markedly poorer than the other six on q(x). Our results suggest that q(x), while postulated as a more realistic distribution to test the performance of algorithms than u(n), also discriminates their performance better. Our q(x) sampler can be used to generate compressible instances of any discrete problem.