12 ms·

Quasi-Polynomial Algorithm for Graph Isomorphism

137 points by johncolanduoni 11y ago

andrewla 11y ago
Original title "Quasi-Polynomial Algorithm for Graphic Isomorphism Proposed" should be "Graph" instead of "Graphic"
- johncolanduoni 11y ago
  You know you've been up too long when you write graph as graphic, even though you've written a paper on graph theory XD.
- duaneb 11y ago
  Ahh yea that makes a lot more sense
- dang 11y ago
  Yes. Fixed.
  - jsprogrammer 11y ago
    ...except you dropped off the key piece: "Proposed" As far as I can tell, the page at the link contains no quasi-polynomial running time algorithm for solving graph isomorphisms, yet that is exactly what the title of this posting now states. There is only a claimed, or, "proposed", algorithm, as far as I can tell. The details won't be revealed until November 10, apparently.
    - dang 11y ago
      That seems a bit nitpicky. The post doesn't contain a proposal either.
      - jsprogrammer 11y ago
        I agree. I only used the word because it was the apparent original title (according to the person you responded to). Possible Quasi-Polynomial Graph Isomorphism Problem Algorithm Upcoming?
harperlee 11y ago
Could anyone provide a good pointer to an introduction more amenable than e.g. Wikipedia? A brief googling provides a lot of material, but I could use a little curation... and that's the sort of thing that sometimes HN is best for. Thanks!
- JD557 11y ago
  Disclaimer: I don't know much about the subject, but I'll try to help. Two graphs are isomorphic if they are "the same" graph, as in, if you renamed the edges, the graph would be the same. For example, if you have the graphs: G1: A -> B <-> C G1: C -> B <-> A The only difference between those graphs is the name of the vertices. If you rename them, you get exactly the same graph back. The first example from the wikipedia page seems like a nice one: https://en.wikipedia.org/wiki/Graph_isomorphism https://en.wikipedia.org/wiki/Graph_isomorphism While the two graphs look different, they are exactly the same. Quasi-polynomial algorithms, as the name implies, are algorithms that are "almost-polynomial" (ie. slower than polynomial, but faster than exponential). According to https://en.wikipedia.org/wiki/Time_complexity#Quasi-polynomial_time https://en.wikipedia.org/wiki/Time_complexity#Quasi-polynomi..., the worst case for a quasi-polynomial algorithm is 2^O(log (n)^c).
  - tinco 11y ago
    From the example it looks as if this can be solved linearly, because the structures obviously match. To intuit that the algorithm must be exponential, imagine the vertices to be balls on wire. You grab one ball pull it up as the root from which you start to compare. Now it is obvious you have to pick a vertex from the other graph as well to be the root nice from which to begin the comparison, if you pick the wrong one the graphs won't match. So you will have to pick every ball and see if its structure matches. For a tree (a graph without cycles) it's plain to see it's exponential: in the worst case you have to pick each vertex from one graph and then compare its children with the other graph, that's N * N operations. When the graph does have cycles, the problem becomes more complex. How much more complex is what this scientist perhaps put a new upper limit on.
- Someone 11y ago
gone35 11y ago
What. A. Bombshell. Sorry for the low-content post; but it is no exaggeration to say that this "might be the theoretical computer science result of the decade". I'm dying to see how Babai managed to pull it off.
- yk 11y ago
  With the news of the EM drive today, probably he confused himself with unclear notation on line 57 of the proof. ( It would be cool if he pulled it off, but even highly respected scientists make mistakes, and a blog post based on the title of a seminar is nothing to get excited about.)
  - davidamarquis 11y ago
    Good mathematical work is rarely an all or nothing proposition. Many independent ideas are required and when the mathematician is very good it is rare that there will be many mistakes. So even if there are issues with some aspect of the proof there is usually lots of interesting stuff that can be salvaged. The proof of Fermat's last theorem as originally given is an example. It was wrong, though it got patched later, but the original work was still very exciting I think.
- fitzwatermellow 11y ago
  Yes, it's a rarity indeed!
- bmh100 11y ago
  Since you seem knowledgeable about this area, do you know a good algorithm for generating isomorphic forms of a given weighted acyclic directional graph? I would be looking to reduce nesting level and/or total edge count.
  - gone35 11y ago
    Sorry not my field! But I would first give NAUTY[1] a try before trying more exotic, structure-exploiting stuff. [1] http://www3.cs.stonybrook.edu/~algorith/implement/nauty/implement.shtml http://www3.cs.stonybrook.edu/~algorith/implement/nauty/impl...
leecarraher 11y ago
woozers, really excited to see this. hope videolectures.net picks up the presentation soon afterward.
eximius 11y ago
I know a guy who may have independently come up with the same or a similar result. He's been keeping it under wraps because he's not a mathematician and hasn't proved it, just come up with the method. I've advised him to upload his results somewhere as soon as possible because he's been working on this for several years. I'll be very interested to see how their methods differ.
- JadeNB 11y ago
  Giving false proofs that GI is in P or a related time class is, I think, a common occupation (see, for example, https://rjlipton.wordpress.com/2009/11/04/on-mathematical-diseases https://rjlipton.wordpress.com/2009/11/04/on-mathematical-di... ); so, if all you know is that this guy thinks he has a solution to the problem, and if the guy is not a mathematician and doesn't have a proof, then the balance of probabilities is that he's probably mistaken (but there's no harm in making the work publicly available, just in case).
  - eximius 11y ago
    I've seen the method and I have a background in math, just not enough to really help prove it. I was never claiming that he succeeded, just that he had something similar that worked in all our tests, at least. Even if his solution isn't polynomial it might be quasi polynomial like this result, in which case the differences would be enlightening. The most likely case is that my friends work is polynomial but wrong in some obscure way. But it will be interesting nonetheless.
    - JadeNB 11y ago
      > I was never claiming that he succeeded, just that he had something similar that worked in all our tests, at least. It's hard to tell the running time of an algorithm by testing; an O(1) algorithm is indistinguishable from an O(2^(2^n)) algorithm if you only run them on inputs up to n = 10^(10^(10^(34))), say. (That sounds facetious, and it kind of is, but it cuts the other way, too: I seem to remember that polynomial-time primality testing isn't used in practice because the constants are so huge that, on 'real-life' inputs, it's impractically worse than probabilistic testing.)
ThePhysicist 11y ago
That's super fascinating! I have been studying the graph isomorphism problem for a while now since I actually needed it for a real-world use case, so I'm really psyched to hear that there is a good solution now. About our use case: We developed an algorithm for creating "semantic diffs" between two source code trees. Starting from a graphical (AST) representation of the source code of an entire software project, such a diff would basically tell you how you can transform one tree into the other using a range of edit operations (e.g. insert, delete, copy, paste, modify). The advantage compared to line-by-line diffs is that the latter work only on the text-level (i.e. "this line has been removed, this other line has been added"), whereas the former can actually tell you what changed on a semantic level (i.e. "this argument was inserted into this function and this variable name was changed"). For big projects, this is quite a computational challenge and can (could) only be solved using approximations and shortcuts. Having a polynomial-time algorithm for this would therefore be a huge deal. I hope that the proof will soon lead to practical implementations of the algorithm.
- deleted 11y ago
  [deleted]
- espes 11y ago
  Why is general graph isomorphism needed for that?
  - ThePhysicist 11y ago
    Probably it isn't, but if there was a general-purpose algorithm that I could just use without doing any hand-crafted optimizations that would be a huge win. As you said, finding a good solution is usually possible but it requires applying a lot of (reasonable) approximations and shortcuts.
    - espes 11y ago
      But it sounds like your model isn't a general graph? DAG and tree isomorphism is in P (and pretty straightforward), and so is tree edit distance...
oofabz 11y ago
Can anyone give an example of real-world problems that graph isomophism can be used to solve? I am out of my depth here and I might be able to make more sense of it if I had a concrete example to relate these concepts to.
- johncolanduoni 11y ago
  One application is electronic circuit verification. A conceptual circuit diagram needs to be mapped to a specific geometry of components and conductive paths between them. The verification that the circuit diagram matches the layout is a graph isomorphism problem; you need to ensure that you can assign the pre-layout components to the ones in the specific layout, such that all the edges line up with those in the original diagram.
amelius 11y ago
I wonder if bits of the proof could be used for other graph problems. For instance the "clique problem" [1], which is NP complete. [1] https://en.wikipedia.org/wiki/Clique_problem https://en.wikipedia.org/wiki/Clique_problem

137 points by johncolanduoni 11y ago

andrewla 11y ago

Original title "Quasi-Polynomial Algorithm for Graphic Isomorphism Proposed" should be "Graph" instead of "Graphic"

johncolanduoni 11y ago
You know you've been up too long when you write graph as graphic, even though you've written a paper on graph theory XD.
duaneb 11y ago
Ahh yea that makes a lot more sense
dang 11y ago
Yes. Fixed.
- jsprogrammer 11y ago
  ...except you dropped off the key piece: "Proposed" As far as I can tell, the page at the link contains no quasi-polynomial running time algorithm for solving graph isomorphisms, yet that is exactly what the title of this posting now states. There is only a claimed, or, "proposed", algorithm, as far as I can tell. The details won't be revealed until November 10, apparently.
  - dang 11y ago
    That seems a bit nitpicky. The post doesn't contain a proposal either.
    - jsprogrammer 11y ago
      I agree. I only used the word because it was the apparent original title (according to the person you responded to). Possible Quasi-Polynomial Graph Isomorphism Problem Algorithm Upcoming?

harperlee 11y ago

Could anyone provide a good pointer to an introduction more amenable than e.g. Wikipedia? A brief googling provides a lot of material, but I could use a little curation... and that's the sort of thing that sometimes HN is best for. Thanks!

JD557 11y ago
Disclaimer: I don't know much about the subject, but I'll try to help. Two graphs are isomorphic if they are "the same" graph, as in, if you renamed the edges, the graph would be the same. For example, if you have the graphs: G1: A -> B <-> C G1: C -> B <-> A The only difference between those graphs is the name of the vertices. If you rename them, you get exactly the same graph back. The first example from the wikipedia page seems like a nice one: https://en.wikipedia.org/wiki/Graph_isomorphism https://en.wikipedia.org/wiki/Graph_isomorphism While the two graphs look different, they are exactly the same. Quasi-polynomial algorithms, as the name implies, are algorithms that are "almost-polynomial" (ie. slower than polynomial, but faster than exponential). According to https://en.wikipedia.org/wiki/Time_complexity#Quasi-polynomial_time https://en.wikipedia.org/wiki/Time_complexity#Quasi-polynomi..., the worst case for a quasi-polynomial algorithm is 2^O(log (n)^c).
- tinco 11y ago
  From the example it looks as if this can be solved linearly, because the structures obviously match. To intuit that the algorithm must be exponential, imagine the vertices to be balls on wire. You grab one ball pull it up as the root from which you start to compare. Now it is obvious you have to pick a vertex from the other graph as well to be the root nice from which to begin the comparison, if you pick the wrong one the graphs won't match. So you will have to pick every ball and see if its structure matches. For a tree (a graph without cycles) it's plain to see it's exponential: in the worst case you have to pick each vertex from one graph and then compare its children with the other graph, that's N * N operations. When the graph does have cycles, the problem becomes more complex. How much more complex is what this scientist perhaps put a new upper limit on.
Someone 11y ago

gone35 11y ago

What. A. Bombshell. Sorry for the low-content post; but it is no exaggeration to say that this "might be the theoretical computer science result of the decade". I'm dying to see how Babai managed to pull it off.

yk 11y ago
With the news of the EM drive today, probably he confused himself with unclear notation on line 57 of the proof. ( It would be cool if he pulled it off, but even highly respected scientists make mistakes, and a blog post based on the title of a seminar is nothing to get excited about.)
- davidamarquis 11y ago
  Good mathematical work is rarely an all or nothing proposition. Many independent ideas are required and when the mathematician is very good it is rare that there will be many mistakes. So even if there are issues with some aspect of the proof there is usually lots of interesting stuff that can be salvaged. The proof of Fermat's last theorem as originally given is an example. It was wrong, though it got patched later, but the original work was still very exciting I think.
fitzwatermellow 11y ago
Yes, it's a rarity indeed!
bmh100 11y ago
Since you seem knowledgeable about this area, do you know a good algorithm for generating isomorphic forms of a given weighted acyclic directional graph? I would be looking to reduce nesting level and/or total edge count.
- gone35 11y ago
  Sorry not my field! But I would first give NAUTY[1] a try before trying more exotic, structure-exploiting stuff. [1] http://www3.cs.stonybrook.edu/~algorith/implement/nauty/implement.shtml http://www3.cs.stonybrook.edu/~algorith/implement/nauty/impl...

leecarraher 11y ago

woozers, really excited to see this. hope videolectures.net picks up the presentation soon afterward.

eximius 11y ago

I know a guy who may have independently come up with the same or a similar result. He's been keeping it under wraps because he's not a mathematician and hasn't proved it, just come up with the method. I've advised him to upload his results somewhere as soon as possible because he's been working on this for several years. I'll be very interested to see how their methods differ.

JadeNB 11y ago
Giving false proofs that GI is in P or a related time class is, I think, a common occupation (see, for example, https://rjlipton.wordpress.com/2009/11/04/on-mathematical-diseases https://rjlipton.wordpress.com/2009/11/04/on-mathematical-di... ); so, if all you know is that this guy thinks he has a solution to the problem, and if the guy is not a mathematician and doesn't have a proof, then the balance of probabilities is that he's probably mistaken (but there's no harm in making the work publicly available, just in case).
- eximius 11y ago
  I've seen the method and I have a background in math, just not enough to really help prove it. I was never claiming that he succeeded, just that he had something similar that worked in all our tests, at least. Even if his solution isn't polynomial it might be quasi polynomial like this result, in which case the differences would be enlightening. The most likely case is that my friends work is polynomial but wrong in some obscure way. But it will be interesting nonetheless.
  - JadeNB 11y ago
    > I was never claiming that he succeeded, just that he had something similar that worked in all our tests, at least. It's hard to tell the running time of an algorithm by testing; an O(1) algorithm is indistinguishable from an O(2^(2^n)) algorithm if you only run them on inputs up to n = 10^(10^(10^(34))), say. (That sounds facetious, and it kind of is, but it cuts the other way, too: I seem to remember that polynomial-time primality testing isn't used in practice because the constants are so huge that, on 'real-life' inputs, it's impractically worse than probabilistic testing.)

ThePhysicist 11y ago

That's super fascinating! I have been studying the graph isomorphism problem for a while now since I actually needed it for a real-world use case, so I'm really psyched to hear that there is a good solution now. About our use case: We developed an algorithm for creating "semantic diffs" between two source code trees. Starting from a graphical (AST) representation of the source code of an entire software project, such a diff would basically tell you how you can transform one tree into the other using a range of edit operations (e.g. insert, delete, copy, paste, modify). The advantage compared to line-by-line diffs is that the latter work only on the text-level (i.e. "this line has been removed, this other line has been added"), whereas the former can actually tell you what changed on a semantic level (i.e. "this argument was inserted into this function and this variable name was changed"). For big projects, this is quite a computational challenge and can (could) only be solved using approximations and shortcuts. Having a polynomial-time algorithm for this would therefore be a huge deal. I hope that the proof will soon lead to practical implementations of the algorithm.

deleted 11y ago
[deleted]
espes 11y ago
Why is general graph isomorphism needed for that?
- ThePhysicist 11y ago
  Probably it isn't, but if there was a general-purpose algorithm that I could just use without doing any hand-crafted optimizations that would be a huge win. As you said, finding a good solution is usually possible but it requires applying a lot of (reasonable) approximations and shortcuts.
  - espes 11y ago
    But it sounds like your model isn't a general graph? DAG and tree isomorphism is in P (and pretty straightforward), and so is tree edit distance...

oofabz 11y ago

Can anyone give an example of real-world problems that graph isomophism can be used to solve? I am out of my depth here and I might be able to make more sense of it if I had a concrete example to relate these concepts to.

johncolanduoni 11y ago
One application is electronic circuit verification. A conceptual circuit diagram needs to be mapped to a specific geometry of components and conductive paths between them. The verification that the circuit diagram matches the layout is a graph isomorphism problem; you need to ensure that you can assign the pre-layout components to the ones in the specific layout, such that all the edges line up with those in the original diagram.

amelius 11y ago

I wonder if bits of the proof could be used for other graph problems. For instance the "clique problem" [1], which is NP complete. [1] https://en.wikipedia.org/wiki/Clique_problem https://en.wikipedia.org/wiki/Clique_problem