Most naive approaches to graph isomorphism end up being dominated by the k-dim Weisfeiler Leman method, for some small k. The same is true for the message passing approach proposed in the paper you link. I wrote such an answer to a similar question before, let me not repeat it here.
Let me instead quote from Pascal Schweitzer's thesis:
The Weisfeiler-Lehman algorithm subsumes almost all combinatorial graph algorithms that are not based on the group theoretic method, (see Section 2.5). An exception to this might be the problem of deciding isomorphism of graphs of bounded eigenvalue multiplicity, for which Fürer gave a combinatorial algorithm .
 Martin Fürer. Graph isomorphism testing without numerics for graphs of bounded eigenvalue multiplicity. In SODA ’95: Proceedings of the sixth annual ACM-SIAM symposium on discrete algorithms, pages 624–631, San Francisco, CA, USA, 1995. SIAM. 25
The ScrewBox algorithm developed in that thesis doesn't use group theoretic methods:
The ScrewBox replaces this backtracking by repeatedly drawing random vertices. The ScrewBox also replaces group theoretical with statistical instruments. Though the ScrewBox is a practical algorithm, the aim of the chapter is to attract theoretical interest in alternatives to the classical approach taken to graph isomorphism.
The assumption that slight variation of WL are unable to resolve graph isomorphism has been challenged even more explicitly (I am not yet able to follow their argument) in [arXiv:1101.5211] The Weisfeiler-Lehman Method and Graph Isomorphism Testing by B. L. Douglas:
Indeed, following the work of , the question of whether the WL method or some minor variation might solve GI has (to the knowledge of the author) been considered closed. However by analysing the effects of a slight variant of the WL method presented in these works, this paper intends to re-open the question as to whether the general WL approach might be used to solve the GI problem.
The above might explain why I still decided to explicitly read and review the paper you linked. This answer is a community wiki and doesn't contain that review, because the Q&A format is simply not suited for that purpose. I actually don't know which format would be suitable, or whether it is even a good idea to publicly review papers (before publication in peer reviewed journals). I created now a chat room where such question can be discussed, and where I (or anybody else who feels like it) will also do some amateur reviews (as opposed to peer reviews):