What are the current state of art approximation algorithm for NP-Hard problems?
First, there are two aspects to separate here: theoretical approximation and practical approximation (i.e., heuristics). With heuristics, such as in the NIPS paper you mention, the goal is roughly to propose some method, take a large bunch of actual instances of a problem, benchmark empirically the method, and draw conclusions as to how well we did in terms of approximation.

This is in contrast to (theoretical) approximation algorithms that give a formal guarantee on solution quality, on all possible instances. For example, the guarantee could be "the solution returned by this algorithm is either optimal or at most three less than the optimal". But as you might know, there is an enormous amount of hard problems that can be wildly different in terms of approximation. Maximum clique or chromatic number, for instance, are very hard to approximate theoretically.