Can message passing algorithms like those used in https://arxiv.org/pdf/1704.00395.pdf be useful in showing GI testing is in P?

Note message passing is prominent in AI and has been tried in decoding problem for linear codes which is an NP hard problem and natural obstructions have been identified. However GI cannot be NP hard under some reasonable hypothesis and possibly message passing could be a reasonable approach.

  • 1
    $\begingroup$ I am not thrilled by this sort of question. The first one is a 55 page paper. It was mentioned at H. A. Helfgott's blog, without being torn to pieces immediately. Do you want people (like me) to admit that they started reading that paper, and then stopped at some point without finding a major mistake, but also way before even reading through the paper once? The second paper is much shorter and hence can probably be evaluated with reasonable effort, but I would still be uneasy to answer here... $\endgroup$ – Thomas Klimpel Apr 6 '17 at 1:34
  • 1
    $\begingroup$ If your question is a query on message passing, then why does the title of your question does not reflect this? And why do you ask about a 55 page paper unrelated to message passing then? Yes, I am not thrilled! $\endgroup$ – Thomas Klimpel Apr 6 '17 at 2:20
  • 1
    $\begingroup$ Polynomial and quasipolynomial graph isomorphism papers on arxiv are a dime a dozen. There is no evidence that this particular claim is in any way notable (or possibly correct), so the paragraph on Wikipedia was inappropriate, and I've removed it. By the way, be that kind and don't call Wikipedia “wiki”. That word has a different meaning. It is like calling someone’s blog “WordPress”. $\endgroup$ – Emil Jeřábek Apr 6 '17 at 7:24
  • 4
    $\begingroup$ @Turbo: Not really. arXiv moderators barely seem to filter out claims of P=NP, as part of the purpose of the arxiv is minimal filtering. And actually, claims of poly-time algorithms for GI are often harder to filter out because sometimes the analysis of the algorithm may clearly contain a flaw, but proving that the algorithm takes super-poly time may not be easy - certainly beyond the amount of time/energy that is supposed to be required of arxiv moderators. $\endgroup$ – Joshua Grochow Apr 9 '17 at 4:17
  • 1
    $\begingroup$ @Turbo: I wasn't meaning that as a reason to close (as I think even your question had changed since Emil made his comments), it was just FYI. $\endgroup$ – Joshua Grochow Apr 9 '17 at 22:30

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 [43].

[43] 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 [10], 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):



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.