8 ms·

Algorithm Solves Graph Isomorphism in Record Time (2015)

212 points by howard941 7y ago

wolfgke 7y ago
(2015)
- aDfbrtVt 7y ago
  Technically 2017 was the latest update to the paper, but still not as groundbreaking as the submission title.
aDfbrtVt 7y ago
Here's the updated paper with some significant corrections http://people.cs.uchicago.edu/~laci/upcc-fix.pdf http://people.cs.uchicago.edu/~laci/upcc-fix.pdf
- chmod775 7y ago
  Those are just the corrections, not the full paper.
  - dmix 7y ago
    This is the full paper the OP was referring to: http://people.cs.uchicago.edu/~laci/17groups/version2.1.pdf http://people.cs.uchicago.edu/~laci/17groups/version2.1.pdf The fixes linked above are mentioned in the WARNING below the abstract and explained at 18.1.
- svat 7y ago
  There's an expository paper by Harald Helfgott that goes into earlier work, more foundational stuff, etc — even has exercises: https://arxiv.org/abs/1710.04574 https://arxiv.org/abs/1710.04574 (Originally presented for the Bourbaki Seminar, so not exactly for the non-mathematician, but has more context than reading the paper directly.)
- zemptime 7y ago
  On page 2, in the "coherent configuration" section, what does the x with the - through it mean? I haven't been able to search my way to an answer
kzrdude 7y ago
Is the algo practical, implemented by say major generic graph libraries?
- sischoel 7y ago
  No, graph libraries usually relay on some variation of VF2 and maybe (but I haven't checked) in some cases on the more complicated nauty/traces algorithms.
  - CJefferson 7y ago
    (basically speaking) no-one does Graph Isomorphism with VF2, they use (as you say) Nauty, or some system which derives from that. Things like VF2 can be used for sub-graph isomorphism (and various variants of that problem). Nauty (and this paper) are useless for solving that problem. I work in this area, and it's interesting (to me at least) that you would imagine the algorithms for graph isomorphism and sub-graph isomorphism would be quite similar and they really aren't.
    - sischoel 7y ago
      Still, the more well known graph libraries seem to avoid Nauty, probably because it is not that easy to implement. From a quick search: - NetworkX: VF2 - JGraphT: VF2 and some newer algorithm called "color refinement algorithm" - seems to resemble Nauty - BGL: VF2 - SnapGraph: Does not seem to contain graph isomporphism - Igaph: Bliss and VF2 So are you convinced that Nauty is still the best thing that we have nowadays? I was looking at the paper last summer with the intention to implement it for Julia, but then got sidetracked with other stuff. Maybe I should resume that.
      - CJefferson 7y ago
        Nauty is I think the best trade-off. The improvements in Saucy and Bliss (which have mostly been added to Nauty now) are useful. The basic algorithm isn't that hard -- I have a few implementations lying around (nothing in Julia). Traces is better, but is much harder to implement and it isn't clear the improvement is worth it for someone implementing from scratch. There are some improvements, particularly for graph isomorphism (as opposed to automorphism), but the basic algorithm framework is the same.
rsp1984 7y ago
even small graphs can be made to look very different just by moving their nodes around I'm curious: for the graph isomorphism problem, how are the graphs defined then? It seems there must be a geometric component in there because if they were defined just in terms of abstract sets of vertices and edges between them, it would be rather trivial to show if two graphs are the same, wouldn't it?
- DominikPeters 7y ago
  Graphs are given as abstract sets of vertices and sets of edges (as adjacency lists or matrices). The problem is that corresponding vertices in the two graphs may not have the same label, so to solve graph isomorphism naively, one would need to try all n! possible bijections between the vertex sets (where n is the number of vertices).
  - sischoel 7y ago
    Wikipedia has a nice picture of two graphs that are isomorph: https://en.wikipedia.org/wiki/Graph_isomorphism https://en.wikipedia.org/wiki/Graph_isomorphism. It should be noted than one of the common used algorithms, called VF2, and descendants of it basically just check all possible bijections, although they use some heuristics to prune the search tree.
    - shawnz 7y ago
      I think pictorial representations are what is confusing the grandparent. The problem isn't about comparing two graphs that look different visually, it's about comparing two graphs which have differently named labels (but might still have the same structure). The graph isomorphism algorithm doesn't know anything about where on the page you drew the nodes, just what is connected to what
  - rsp1984 7y ago
    Thanks much for the clarification. I didn't know that one was "allowed" to change labels. It makes sense now.
- 7y ago
skunkworker 7y ago
"That would be the most interesting possibility, Trevisan said, since it would make graph isomorphism the first natural problem to have a quasi-polynomial algorithm but no polynomial algorithm. " "Proving it would amount to solving the P versus NP problem, since it would mean that graph isomorphism separates the problems in P from the NP-complete problems." (exp((log n)^O(1))) Interesting that there could be a much more varied landscape than was previously thought.
- mehrdadn 7y ago
  One thing that's bothered me ever since I heard about complexity theory is why there is no explanation given as to why polynomial and exponential complexities are given such special status. It's just taken for granted that polynomials and exponential are the 2 classes you care about... with no explanation as to why the rest aren't interesting. EDIT: Edited to clarify, sorry the question was unclear. Thanks for all the replies, but yes, I know the basics :-) I'm not asking about why polynomial complexities themselves are special. Rather, I was trying to ask why we only ever talk about polynomials and exponentials. The only thing that's ever justified is polynomial-time reducibility within a class (which also inherently defines the P class itself). That part is fine. But then once that's established, people suddenly start talking about exponentials. Sorry, but what just happened? There are an infinite number of complexities in between to consider! Why should I suddenly not care about everything in between? Why am I not taught a single algorithm whose complexity is between these? is my question.
  - kevinventullo 7y ago
    I think it's just that many natural algorithms happen to have polynomial time complexity, since it's basically the complexity of iterated loops. Same with logarithms.
  - dragontamer 7y ago
    Because O(e^x) > O(x^n), for all Integer values of "n". So Polynomial is simply a class that we know is strictly "faster" (well, asymptotically faster) than any exponential function. In practice, I think real-life humans only care for "small polynomials". An algorithm with complexity (x^5000) will be growing too quickly to be used in practice, even if its big-Oh is technically polynomial. Well, I say that, except 3SAT solvers are a thing and that's provably NP-complete. So lots of people bang their heads against the NP-complete problems anyway.
ggggtez 7y ago
(2017). This is old news, I thought for a moment he had a new paper. Please add the year.
- howard941 7y ago
  OK
jmmcd 7y ago
Slightly off-topic, this article has one of the best expositions I've seen (the Arthur-Merlin stuff) of P, NP, NP-complete, witnesses, and the idea of "evidence" for what complexity class the problem is in.
- mpoteat 7y ago
  Unfortunately I found all of the story-like exposition infuriating: they never even say what the new conjectured lower bound is.
  - nine_k 7y ago
    Likely it's the lower bound (of something) that an important conjecture in the paper gives? That is, it's not some new kind of a lower bound, but a way to refer to it?
- evrydayhustling 7y ago
  100% this. One of the cleanest descriptions of key insights and broader scientific landscape ("glide path" from quasipolynomial to P) I have seen. Erica, if you are seeing this, nice work and I'll be watching for more.
- dbchiem 7y ago
  Absolutely, I think the author did a magnificent job!. Reading the article, all the intricacies (P/NP, polynomial/exponential, blind test, graph coloring) are quite clear and easy to comprehend. Here are some gentle articles on the zero-knowledge in case anyone is curious: https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ https://blog.cryptographyengineering.com/2014/11/27/zero-kno... https://blockgeeks.com/guides/what-is-zksnarks/ https://blockgeeks.com/guides/what-is-zksnarks/
- meuk 7y ago
  Agreed! I was already prepared to be annoyed by sketchy metaphors that didn't quite make sense, but this was delightful and very informative to read.
B3QL 7y ago
Explanation of the current state of review: https://cstheory.stackexchange.com/a/40373 https://cstheory.stackexchange.com/a/40373
penguin_booze 7y ago
"Monads are monoids in the category of endofunctors. What's the problem?" -- that's how every paper looks at me!

212 points by howard941 7y ago

wolfgke 7y ago

(2015)

aDfbrtVt 7y ago
Technically 2017 was the latest update to the paper, but still not as groundbreaking as the submission title.

aDfbrtVt 7y ago

Here's the updated paper with some significant corrections http://people.cs.uchicago.edu/~laci/upcc-fix.pdf http://people.cs.uchicago.edu/~laci/upcc-fix.pdf

chmod775 7y ago
Those are just the corrections, not the full paper.
- dmix 7y ago
  This is the full paper the OP was referring to: http://people.cs.uchicago.edu/~laci/17groups/version2.1.pdf http://people.cs.uchicago.edu/~laci/17groups/version2.1.pdf The fixes linked above are mentioned in the WARNING below the abstract and explained at 18.1.
svat 7y ago
There's an expository paper by Harald Helfgott that goes into earlier work, more foundational stuff, etc — even has exercises: https://arxiv.org/abs/1710.04574 https://arxiv.org/abs/1710.04574 (Originally presented for the Bourbaki Seminar, so not exactly for the non-mathematician, but has more context than reading the paper directly.)
zemptime 7y ago
On page 2, in the "coherent configuration" section, what does the x with the - through it mean? I haven't been able to search my way to an answer

kzrdude 7y ago

Is the algo practical, implemented by say major generic graph libraries?

sischoel 7y ago
No, graph libraries usually relay on some variation of VF2 and maybe (but I haven't checked) in some cases on the more complicated nauty/traces algorithms.
- CJefferson 7y ago
  (basically speaking) no-one does Graph Isomorphism with VF2, they use (as you say) Nauty, or some system which derives from that. Things like VF2 can be used for sub-graph isomorphism (and various variants of that problem). Nauty (and this paper) are useless for solving that problem. I work in this area, and it's interesting (to me at least) that you would imagine the algorithms for graph isomorphism and sub-graph isomorphism would be quite similar and they really aren't.
  - sischoel 7y ago
    Still, the more well known graph libraries seem to avoid Nauty, probably because it is not that easy to implement. From a quick search: - NetworkX: VF2 - JGraphT: VF2 and some newer algorithm called "color refinement algorithm" - seems to resemble Nauty - BGL: VF2 - SnapGraph: Does not seem to contain graph isomporphism - Igaph: Bliss and VF2 So are you convinced that Nauty is still the best thing that we have nowadays? I was looking at the paper last summer with the intention to implement it for Julia, but then got sidetracked with other stuff. Maybe I should resume that.
    - CJefferson 7y ago
      Nauty is I think the best trade-off. The improvements in Saucy and Bliss (which have mostly been added to Nauty now) are useful. The basic algorithm isn't that hard -- I have a few implementations lying around (nothing in Julia). Traces is better, but is much harder to implement and it isn't clear the improvement is worth it for someone implementing from scratch. There are some improvements, particularly for graph isomorphism (as opposed to automorphism), but the basic algorithm framework is the same.

rsp1984 7y ago

even small graphs can be made to look very different just by moving their nodes around I'm curious: for the graph isomorphism problem, how are the graphs defined then? It seems there must be a geometric component in there because if they were defined just in terms of abstract sets of vertices and edges between them, it would be rather trivial to show if two graphs are the same, wouldn't it?

DominikPeters 7y ago
Graphs are given as abstract sets of vertices and sets of edges (as adjacency lists or matrices). The problem is that corresponding vertices in the two graphs may not have the same label, so to solve graph isomorphism naively, one would need to try all n! possible bijections between the vertex sets (where n is the number of vertices).
- sischoel 7y ago
  Wikipedia has a nice picture of two graphs that are isomorph: https://en.wikipedia.org/wiki/Graph_isomorphism https://en.wikipedia.org/wiki/Graph_isomorphism. It should be noted than one of the common used algorithms, called VF2, and descendants of it basically just check all possible bijections, although they use some heuristics to prune the search tree.
  - shawnz 7y ago
    I think pictorial representations are what is confusing the grandparent. The problem isn't about comparing two graphs that look different visually, it's about comparing two graphs which have differently named labels (but might still have the same structure). The graph isomorphism algorithm doesn't know anything about where on the page you drew the nodes, just what is connected to what
- rsp1984 7y ago
  Thanks much for the clarification. I didn't know that one was "allowed" to change labels. It makes sense now.
7y ago

skunkworker 7y ago

"That would be the most interesting possibility, Trevisan said, since it would make graph isomorphism the first natural problem to have a quasi-polynomial algorithm but no polynomial algorithm. " "Proving it would amount to solving the P versus NP problem, since it would mean that graph isomorphism separates the problems in P from the NP-complete problems." (exp((log n)^O(1))) Interesting that there could be a much more varied landscape than was previously thought.

mehrdadn 7y ago
One thing that's bothered me ever since I heard about complexity theory is why there is no explanation given as to why polynomial and exponential complexities are given such special status. It's just taken for granted that polynomials and exponential are the 2 classes you care about... with no explanation as to why the rest aren't interesting. EDIT: Edited to clarify, sorry the question was unclear. Thanks for all the replies, but yes, I know the basics :-) I'm not asking about why polynomial complexities themselves are special. Rather, I was trying to ask why we only ever talk about polynomials and exponentials. The only thing that's ever justified is polynomial-time reducibility within a class (which also inherently defines the P class itself). That part is fine. But then once that's established, people suddenly start talking about exponentials. Sorry, but what just happened? There are an infinite number of complexities in between to consider! Why should I suddenly not care about everything in between? Why am I not taught a single algorithm whose complexity is between these? is my question.
- kevinventullo 7y ago
  I think it's just that many natural algorithms happen to have polynomial time complexity, since it's basically the complexity of iterated loops. Same with logarithms.
- dragontamer 7y ago
  Because O(e^x) > O(x^n), for all Integer values of "n". So Polynomial is simply a class that we know is strictly "faster" (well, asymptotically faster) than any exponential function. In practice, I think real-life humans only care for "small polynomials". An algorithm with complexity (x^5000) will be growing too quickly to be used in practice, even if its big-Oh is technically polynomial. Well, I say that, except 3SAT solvers are a thing and that's provably NP-complete. So lots of people bang their heads against the NP-complete problems anyway.

ggggtez 7y ago

(2017). This is old news, I thought for a moment he had a new paper. Please add the year.

howard941 7y ago
OK

jmmcd 7y ago

Slightly off-topic, this article has one of the best expositions I've seen (the Arthur-Merlin stuff) of P, NP, NP-complete, witnesses, and the idea of "evidence" for what complexity class the problem is in.

mpoteat 7y ago
Unfortunately I found all of the story-like exposition infuriating: they never even say what the new conjectured lower bound is.
- nine_k 7y ago
  Likely it's the lower bound (of something) that an important conjecture in the paper gives? That is, it's not some new kind of a lower bound, but a way to refer to it?
evrydayhustling 7y ago
100% this. One of the cleanest descriptions of key insights and broader scientific landscape ("glide path" from quasipolynomial to P) I have seen. Erica, if you are seeing this, nice work and I'll be watching for more.
dbchiem 7y ago
Absolutely, I think the author did a magnificent job!. Reading the article, all the intricacies (P/NP, polynomial/exponential, blind test, graph coloring) are quite clear and easy to comprehend. Here are some gentle articles on the zero-knowledge in case anyone is curious: https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ https://blog.cryptographyengineering.com/2014/11/27/zero-kno... https://blockgeeks.com/guides/what-is-zksnarks/ https://blockgeeks.com/guides/what-is-zksnarks/
meuk 7y ago
Agreed! I was already prepared to be annoyed by sketchy metaphors that didn't quite make sense, but this was delightful and very informative to read.

B3QL 7y ago

Explanation of the current state of review: https://cstheory.stackexchange.com/a/40373 https://cstheory.stackexchange.com/a/40373

penguin_booze 7y ago

"Monads are monoids in the category of endofunctors. What's the problem?" -- that's how every paper looks at me!