<p>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 <a href="https://cs.stackexchange.com/questions/65856/literature-about-a-naive-approach-to-graph-isomorphism-by-inspecting-polynomials/65871#65871">answer to a similar question</a> before, let me not repeat it here.</p>
<p>Let me instead quote from <a href="http://users.cecs.anu.edu.au/%7Epascal/docs/thesis_pascal_schweitzer.pdf" rel="nofollow noreferrer">Pascal Schweitzer's thesis</a>:</p>
<blockquote>
<p>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].</p>
<p>[43] Martin Fürer. Graph isomorphism testing without numerics for graphs of bounded eigenvalue multiplicity. In <em>SODA ’95: Proceedings of the sixth annual ACM-SIAM symposium on discrete algorithms</em>, pages 624–631, San Francisco, CA, USA, 1995. SIAM. 25</p>
</blockquote>
<p>The ScrewBox algorithm developed in that thesis doesn't use group theoretic methods:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>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 <a href="https://arxiv.org/abs/1101.5211" rel="nofollow noreferrer">[arXiv:1101.5211] The Weisfeiler-Lehman Method and Graph Isomorphism Testing</a> by <a href="https://arxiv.org/find/math/1/au:+Douglas_B/0/1/0/all/0/1" rel="nofollow noreferrer">B. L. Douglas</a>:</p>
<blockquote>
<p>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.</p>
</blockquote>
<hr />
<p>The above might explain why I still decided to explicitly <a href="http://chat.stackexchange.com/transcript/message/36565120#36565120">read and review the paper</a> you linked. This answer is a community wiki and doesn't contain that review, because the Q&amp;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):</p>
<p><a href="http://chat.stackexchange.com/rooms/56634/amateur-reviews">http://chat.stackexchange.com/rooms/56634/amateur-reviews</a></p>

CC BY-SA 3.0
2017-04-09T13:38:17.750Z
2017-04-09T13:38:17.750Z
2020-06-17T09:38:08.363Z
Thomas Klimpel
<p>Can message passing algorithms like those used in <a href="https://arxiv.org/pdf/1704.00395.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1704.00395.pdf</a> be useful in showing GI testing is in P?</p>

<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.</p>

CC BY-SA 3.0
2017-04-06T01:34:39.050Z
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](https://valuevar.wordpress.com/2017/01/04/graph-isomorphism-in-subexponential-time/#comment-945), 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...
Thomas Klimpel
CC BY-SA 3.0
2017-04-06T01:41:23.670Z
@ThomasKlimpel honest neutral answers are welcome and also my query is not about the specific paper but a query on using message passing as a strategy as used in the paper (I think it is known message passing cannot solve NPC problems but GI is not NPC AFAWK)
Turbo
CC BY-SA 3.0
2017-04-06T02:20:24.020Z
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!
Thomas Klimpel
CC BY-SA 3.0
2017-04-06T05:29:55.890Z
@ThomasKlimpel Ideally it should have been split as 2 questions. The title reflects the first query. I saw the second paper first and it seemed to use message passing (which I know is popular in AI and I am also aware of its limitations (such as decoding codes with parity check matrices that have small  girth - but decoding is in general is NPC but GI is not and thus seemed interesting)) and then second I checked wiki which had a claim on quasipoly time which I have never even heard about. So wanted to know whether claimed achievements have any utility and are they secluded or related?
Turbo
CC BY-SA 3.0
2017-04-06T07:24:33.117Z
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”.
Emil Jeřábek
CC BY-SA 3.0
2017-04-06T08:45:52.850Z
@EmilJeřábek thank you but I thought arxiv moderator filter these things out
Turbo
CC BY-SA 3.0
2017-04-09T04:17:25.143Z
@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.
Joshua Grochow
CC BY-SA 3.0
2017-04-09T07:03:08.940Z
@JoshuaGrochow thank you however I will just leave the query open in case someone knowledgeable on message passing has a good remark and is inclined to give an opinion here
Turbo
CC BY-SA 3.0
2017-04-09T22:30:43.637Z
@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.
Joshua Grochow
<big-picture><big-list>
Can message passing help in GI related problems?
Turbo
# Can message passing help in GI related problems?

(Asked by: username_0 on 2017-04-05)

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.

**Tags:** big-picture, big-list

> **Comments:**
> **username_1**: 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](https://valuevar.wordpress.com/2017/01/04/graph-isomorphism-in-subexponential-time/#comment-945), 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...  
> **username_0**: @ThomasKlimpel honest neutral answers are welcome and also my query is not about the specific paper but a query on using message passing as a strategy as used in the paper (I think it is known message passing cannot solve NPC problems but GI is not NPC AFAWK)  
> **username_1**: 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!  
> **username_0**: @ThomasKlimpel Ideally it should have been split as 2 questions. The title reflects the first query. I saw the second paper first and it seemed to use message passing (which I know is popular in AI and I am also aware of its limitations (such as decoding codes with parity check matrices that have small  girth - but decoding is in general is NPC but GI is not and thus seemed interesting)) and then second I checked wiki which had a claim on quasipoly time which I have never even heard about. So wanted to know whether claimed achievements have any utility and are they secluded or related?  
> **username_2**: 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”.  
> **username_0**: @EmilJeřábek thank you but I thought arxiv moderator filter these things out  
> **username_3**: @username_0: 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.  
> **username_0**: @JoshuaGrochow thank you however I will just leave the query open in case someone knowledgeable on message passing has a good remark and is inclined to give an opinion here  
> **username_3**: @username_0: 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.  

---

## 1 answers

### Answer by username_1 on 2017-04-09. Score: 2 | Accepted answer

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](https://cs.stackexchange.com/questions/65856/literature-about-a-naive-approach-to-graph-isomorphism-by-inspecting-polynomials/65871#65871) before, let me not repeat it here.

Let me instead quote from [Pascal Schweitzer's thesis](http://users.cecs.anu.edu.au/%7Epascal/docs/thesis_pascal_schweitzer.pdf):

> 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](https://arxiv.org/abs/1101.5211) by [B. L. Douglas](https://arxiv.org/find/math/1/au:+Douglas_B/0/1/0/all/0/1):

> 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](http://chat.stackexchange.com/transcript/message/36565120#36565120) 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):

<http://chat.stackexchange.com/rooms/56634/amateur-reviews>


---

