{"id":4148,"date":"2010-08-04T14:48:26","date_gmt":"2010-08-04T21:48:26","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=4148"},"modified":"2024-10-30T00:32:25","modified_gmt":"2024-10-30T00:32:25","slug":"reading-list-graph-isomorphism","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2010\/08\/04\/reading-list-graph-isomorphism\/","title":{"rendered":"Reading List: Graph Isomorphism"},"content":{"rendered":"<p><em>Warning: this idiosyncratic list of reading material is in no way meant to be comprehensive nor does is it even guaranteed to focus on the most important papers concerning graph isomorphism.\u00a0 Suggestions for other papers to add to the list are greatly appreciated: leave a comment!<br \/>\n<\/em><br \/>\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Graph_isomorphism_problem\">The graph isomorphism<\/a> problem is an intriguing problem. A graph is a set of vertices along with the edges connecting these vertices. The graph isomorphism problem is to determine, given the description of two graphs, whether these descriptions are really the same graph. For example, is it possible to relabel and move the vertices in the two graphs below so as to make them look the same?<br \/>\n<a href=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/g11.png?ssl=1\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-4174\" title=\"g1\" src=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/g11-300x202.png?resize=243%2C164&#038;ssl=1\" alt=\"\" width=\"243\" height=\"164\" \/><\/a><a href=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/g21.png?ssl=1\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-4175\" title=\"g2\" src=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/g21-300x205.png?resize=243%2C167&#038;ssl=1\" alt=\"\" width=\"243\" height=\"167\" \/><\/a><br \/>\nGive up? Okay, well it wasn&#8217;t so hard this one, but yes these graphs are isomorphic \ud83d\ude42 Usually we aren&#8217;t given two pictures of the graphs, but instead are given a succinct description of what vertices are connected to each other. This is given by either and <a href=\"https:\/\/en.wikipedia.org\/wiki\/Adjacency_matrix\">adjacency matrix<\/a> or and <a href=\"https:\/\/en.wikipedia.org\/wiki\/Adjacency_list\">adjacency list<\/a>.\u00a0 The adjacency matrix of a graph with $latex n$ vertices is a $latex n times n$ matrix whose $latex (i,j)$th entry is the number of edges from vertex $latex i$ to $latex j$.\u00a0 An algorithm is efficient for the graph isomorphism problem if it takes a running time that is polynomial in the number of vertices of the graphs involved.<br \/>\nOne reason why graph isomorphism is interesting is it current status in computational complexity. It is not likely to be <a href=\"https:\/\/en.wikipedia.org\/wiki\/NP-complete\">NP-complete<\/a> (as <a href=\"http:\/\/link.springer.com\/chapter\/10.1007%2FBFb0039599\">this would cause<\/a> a collapse of the polynomial hierarchy), yet despite a considerable amount of work, there is no known polynomial time algorithm for this problem. Graph isomorphism is known to be in the complexity class NP intersect co-AM, which is kind of similar to where the decision version of factoring lies (NP intersect co-NP.) This similarity, along with the fact that a natural generalization of the quantum problem solved by factoring (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Hidden_subgroup_problem\">the hidden subgroup problem<\/a>) is related to graph isomorphism (efficiently solving the hidden subgroup problem for the symmetric group would yield an efficient algorithm for graph isomorphism) has led to the hope that quantum computers might be able to efficiently solve graph isomorphism. I will admit, over the years, I have slowly but surely developed quite a severe of <a href=\"http:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.3190010410\/abstract\">the graph isomorphism disease<\/a>, albeit my case appears to be of the quantum kind. Like any disease, it is important to spread the disease. So here is a collection of readings about the graph isormophism problem.<br \/>\nOne interesting aspect of the graph isomorphism problem is that there are classes of graphs for which there do exist efficient polynomial time algorithms for deciding isomorphism of graphs in these classes. Because one can get downbeat pretty quickly bashing your head against the problem, I think it would be nice to start out with an easy case: tree isomorphism.\u00a0 The efficient algorithm for this is usually attributed to Aho, Hopcroft and Ullman (1974), but I really like<\/p>\n<ul id=\"journalInfo\">\n<li>&#8220;Tree Isomorphism Algorithms: Speed vs. Clarity&#8221; by Douglas M. Campbell and David Radford<cite>, Mathematics Magazine<\/cite>, Vol. 64, No. 4 (Oct., 1991), pp. 252-261 (<a href=\"http:\/\/www.jstor.org\/action\/cookieAbsent\">paper here<\/a>)<\/li>\n<\/ul>\n<p>It&#8217;s a fun easy read that will get you all excited about graph isomorphism, I&#8217;m sure.<br \/>\nOkay well after that fun start, maybe staying within the realm of polynomial time algorithms continues to feel good.\u00a0 One of the classic ways to attempt to solve graph isomorphism is as follows: compute the eigenvalues of the adjacency matrices of the two graphs, and sort these eigenvalues.\u00a0 If the eigenvalues are different, then the graphs cannot be isomorphic.\u00a0 Why?\u00a0 Well if the graphs are isomorphic, there exists a $latex n times n$ permutation matrix $latex P$ (a matrix made of zeros and ones that has only a single one in each row and in each column) such that $latex A_2=PA_1 P^{-1}$ (here $latex A_1$ and $latex A_2$ are the adjacency matrices of the two graphs.)\u00a0 And recall that the eigenvalues of $latex X$ and $latex MXM^{-1}$ are the same for invertible matrices $latex M$.\u00a0 Thus isomorphic graphs must have the same eigenvalues.\u00a0 Note, however, that this does not imply that non-isomorphic graphs have different eigenvalues.\u00a0 For example, consider the following two trees<br \/>\n<a href=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/t11.png?ssl=1\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-4176\" title=\"t1\" src=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/t11-266x300.png?resize=239%2C270&#038;ssl=1\" alt=\"\" width=\"239\" height=\"270\" \/><\/a><a href=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/t21.png?ssl=1\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-4177\" title=\"t2\" src=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/t21-300x288.png?resize=270%2C259&#038;ssl=1\" alt=\"\" width=\"270\" height=\"259\" \/><\/a><br \/>\nThese trees are clearly not isomorphic.\u00a0 On the other hand, if you take the eigenvalues of their adjacency matrices you will find out that they are both given by<\/p>\n<p style=\"text-align: center;\">$latex \\left{frac{1}{2} \\left(-1-sqrt{13}\\right),frac{1}{2} \\left(1+sqrt{13}\\right),frac{1}{2} \\left(1-sqrt{13}\\right),frac{1}{2} \\left(-1+sqrt{13}right),0,0,0,0\\right}$.<\/p>\n<p style=\"text-align: left;\">So there exists isospectral (same eigenvalues of the adjacency matrix) but non-isomorphic graphs.\u00a0 Thus taking the eigenvalues of the graph isn&#8217;t enough to distinguish non-isomorphic graph.\u00a0 In practice, however, this usually works pretty good.\u00a0 Further, if we consider graphs where the maximum multiplicity of the eigenvalues (recall that an eigenvalue may appear multiple times in the list of eigenvalues of a matrix&#8212;the multiplicity is the number of times an eigenvalue appears) is bounded (that is the multiplicity does not grow with the graph size), then there is an efficient algorithm for graph isomorphism.\u00a0 This was first shown for multiplicity one graphs, i.e. where all the eigenvalues are distinct, by Leighton and Miller.\u00a0 This work is unpublished, but you can find the hand written notes at Gary Miller&#8217;s website:<\/p>\n<ul>\n<li>&#8220;Certificates for Graphs with Distinct Eigen Values,&#8221; by F. Thomson Leighton and Gary l. Miller, unpublished, 1979 (<a href=\"http:\/\/www.cs.cmu.edu\/~glmiller\/Publications\/b2hd-LeightonMiller79.html\">paper here<\/a>)<\/li>\n<\/ul>\n<p>Another place to learn about this, without all the smudge marks, is at the Yale course site of Dan Spielman:<\/p>\n<ul>\n<li>Spectral Graph Theory, Dan Spielman, Fall 2009 (<a href=\"http:\/\/www.cs.yale.edu\/homes\/spielman\/561\/\">course website<\/a> , <a href=\"http:\/\/www.cs.yale.edu\/homes\/spielman\/561\/lect22-09.pdf\">notes<\/a> on multiplicity free graph isomorphism)<\/li>\n<\/ul>\n<p>Here would be a good place to mention the general case for bounded multiplicity<\/p>\n<ul>\n<li>&#8220;Isomorphism of graphs with bounded eigenvalue multiplicity&#8221; by Laszlo Babai, D. Yu. Grigoryev, and David M. Mount, STOC 1982 (<a href=\"http:\/\/dl.acm.org\/citation.cfm?id=802206\">paper here<\/a>)<\/li>\n<\/ul>\n<p>Though jumping in to that paper after the previous ones is a bit of a leap.<br \/>\nOkay, so now your all warmed up.\u00a0 Indeed you&#8217;re probably so stoked that you think a polynomial time classical algorithm is just around the corner.\u00a0 Time to put a damper in those thoughts.<br \/>\nFirst lets start with the paper that is, currently the best algorithm for general graphs.\u00a0 Well actually for the original best algorithm, I&#8217;m not sure if there is an actual paper, but there is a paper which achieves a similar bound see<\/p>\n<ul>\n<li>&#8220;Canonical labeling of graph&#8221; by L\u00e1szl\u00f3 Babai and Eugene M. Luks STOC 1983 (<a href=\"http:\/\/dl.acm.org\/citation.cfm?id=808746\">paper here<\/a>)<\/li>\n<\/ul>\n<p>This describes a subexponential (or, err, what did <a href=\"http:\/\/www.scottaaronson.com\/blog\/?p=394\">Scott decide to call this<\/a>?), $latex exp(-n^{frac{1}{2}+c})$, time algorithm for a graph with $latex n$ vertices.\u00a0 Now as a reading list I don&#8217;t recommend jumping into this paper quite yet, but I just wanted to douse your optimism for a classical algorithm by showing you (a) the best we have in general is a subexponential time algorithm, (b) that record has stood for nearly three decades, and (c) that if you look at the paper you can see it&#8217;s not easy.\u00a0 Abandon hope all ye who enter?<br \/>\nOkay, so apparently you haven&#8217;t been discouraged, so you&#8217;re pressing onward.\u00a0 So what to read next?<br \/>\nWell one strategy would be to go through the list of all the graphs for which there are efficient known algorithms.\u00a0 This is quite a list, and it is useful to at least gain some knowledge of these papers, if at least to no re-solve one of these cases (above we noted the paper for bounded eigenvalue multiplicity):<\/p>\n<ul>\n<li><strong>Planar graphs: <\/strong>&#8220;Linear time algorithm for isomorphism of planar graphs&#8221; by J.E. Hopcroft and J.K. Wong, STOC 1974 (<a href=\"http:\/\/dl.acm.org\/citation.cfm?id=800119.803896\">paper here<\/a>)<\/li>\n<li>or more generally <strong>graphs of bounded genus: <\/strong> &#8220;Isomorphism testing for graphs of bounded genus&#8221; by Gary Miller, STOC 1980 (<a href=\"http:\/\/dl.acm.org\/citation.cfm?id=800141.804670\">paper here<\/a>)<\/li>\n<li><strong>Graphs with bounded degree: <\/strong>&#8220;Isomorphism of graphs of bounded valence can be tested in polynomial time&#8221; by Eugene M. Luks,\u00a0Journal of Computer and System Sciences 25: 42\u201365, 1982 (<a href=\"http:\/\/www.sciencedirect.com\/science\/article\/pii\/0022000082900095?via=ihub\">paper here<\/a>)<\/li>\n<\/ul>\n<p>Along a similar vein, there is a subexponential time algorithm for strongly regular graphs that is better than the best general algorithm described above:<\/p>\n<ul>\n<li>&#8220;Faster Isomorphism Testing of Strongly Regular Graphs&#8221; by Daniel A. Spielman STOC 1996 (paper here)<\/li>\n<\/ul>\n<p>At this point, you&#8217;re probably overloaded, so a good thing to do when you&#8217;re overloaded is to find a book.\u00a0 One interesting book is<\/p>\n<ul>\n<li>&#8220;Group-Theoretic Algorithms and Graph Isomorphism &#8221; by C.M. Hoffman 1982 (<a href=\"http:\/\/link.springer.com\/book\/10.1007%2F3-540-11493-9\">link here<\/a>)<\/li>\n<\/ul>\n<p>As you can see this paper was written before the best algorithms were announced.\u00a0 Yet this book is fairly readable and begins to set up the group theory you&#8217;ll need if you want to conquer the later papers.\u00a0 Another book with some nice results is<\/p>\n<ul>\n<li>&#8220;The graph isomorphism problem: its structural complexity&#8221; by Johannes K\u00f6bler, Uwe Sch\u00f6ning, Jacobo Tor\u00e1n (1993) (<a href=\"http:\/\/dl.acm.org\/citation.cfm?id=SERIES9185.180891\">buy it here<\/a>)<\/li>\n<\/ul>\n<p>where you will find some nice basic complexity theory results about graph isomorphism.<br \/>\nWell now that you&#8217;ve gone and starting learning about some computational complexity in relationship to graph isomorphism, it&#8217;s probably a good time to stop and look at actual practical algorithms for graph isomorphism.\u00a0 The king of the hill here, as far as I know, is the program <a href=\"http:\/\/cs.anu.edu.au\/people\/bdm\/nauty\/\">nauty<\/a> (No AUTomorphism, Yes?) by Brendan D. McKay.\u00a0 Sadly a certain search engine seems to be a bit too weighted to the word &#8220;naughty&#8221; (note to self, consider porn related keyword when naming a software package):<\/p>\n<p style=\"text-align: left;\"><a href=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/Screen-shot-2010-08-04-at-10.22.58-AM1.png?ssl=1\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-4208\" title=\"Screen shot 2010-08-04 at 10.22.58 AM\" src=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/Screen-shot-2010-08-04-at-10.22.58-AM1.png?resize=525%2C118&#038;ssl=1\" alt=\"\" width=\"525\" height=\"118\" \/><\/a>Nauty&#8217;s main task is determining the automorphism group of a graph (the group of permutations that leave the graph representation unchanged) but nauty also produces a canonical label that can be used for testing isomorphism.\u00a0 Nauty can perform isomorphism tests of graphs of 100 vertices in about a second.\u00a0 There is an accompanying paper describing how nauty works:<\/p>\n<ul>\n<li>&#8220;Practical Graph Isomorphism&#8221;, by Brendan D. McKay, Congressus Numerantium, 30, 45-87, 1981. (<a href=\"http:\/\/cs.anu.edu.au\/people\/bdm\/nauty\/pgi.pdf\">paper here<\/a>)<\/li>\n<\/ul>\n<p>A canonical label for a graph is a function from graphs to a set of labels such that for two graphs the label is the same if and only if the two graphs are isomorphic.\u00a0 This is what nauty produces: if you want to know whether the graphs are isomorphic you just compute the canonical forms for these graphs and compare the results.\u00a0 If they have the same canonical form they are isomorphic, if they don&#8217;t they are not isomorphic.<\/p>\n<p style=\"text-align: left;\">Which leads one to thinking about other labeling schemes for solving graph isomorphism.\u00a0 One of the simplest attempts (attempt because it does not work) to make a canonical labeling scheme is the following: begin by labeling the vertices of the two graphs by their degrees.\u00a0 If you then sort this list and they are different sorted lists, then the graphs cannot be isomorphic.\u00a0 Next one can replace the vertex label by a label made up of the multiset of the current vertex label and the labels of the neighboring vertices (recall a multiset is a set where entries can appear multiple times.)\u00a0 One can then sort these multisets lexographically and compare the two sorted lists for both graphs.\u00a0 Again if the lists are not the same the graphs are not isomorphic.\u00a0 If you still haven&#8217;t discovered that the graphs are not isomorphic you can continue, but first, to keep the labels small, you should replace the lexographically ordered labels by a small integer representing the sorted order of the label.\u00a0 Then one can iterate the construction of a new multiset labeling from these new integer labelings.\u00a0 This is a simple scheme to implement.\u00a0 Below, for example, I perform it for two very simple graphs.\u00a0 First:<\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/l1.png?ssl=1\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-4219 alignnone\" title=\"l1\" src=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/l1.png?resize=360%2C186&#038;ssl=1\" alt=\"\" width=\"360\" height=\"186\" \/><\/a><\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/r1.png?ssl=1\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-4221 alignnone\" title=\"r1\" src=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/r1.png?resize=360%2C125&#038;ssl=1\" alt=\"\" width=\"360\" height=\"125\" \/><\/a><\/p>\n<p style=\"text-align: left;\">Next:<\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/l21.png?ssl=1\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-4223\" title=\"l2\" src=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/l21.png?resize=360%2C196&#038;ssl=1\" alt=\"\" width=\"360\" height=\"196\" \/><\/a><\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/r2.png?ssl=1\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-4222\" title=\"r2\" src=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/r2.png?resize=360%2C137&#038;ssl=1\" alt=\"\" width=\"360\" height=\"137\" \/><\/a><\/p>\n<p style=\"text-align: left;\">At which point we stop because if we compare the sorted lists of these multisets they are different (one has $latex {2,2,2}$ while the one on the right does not.) \u00a0 One can show that the above labeling procedure will always stabilize after a polynomial number of iterations (can you see why?) but also it&#8217;s quite clear that it doesn&#8217;t work in general (i.e. it doesn&#8217;t provide a canonical labeling for all graphs) since it gets stuck right off the bat with regular graphs (graphs whose degree is the same across the entire graph.)\u00a0 Here are two 3-regular graphs that are not isomorphic:<\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/i1.png?ssl=1\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-4226\" title=\"i1\" src=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/i1.png?resize=259%2C248&#038;ssl=1\" alt=\"\" width=\"259\" height=\"248\" \/><\/a><a href=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/i2.png?ssl=1\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-4227\" title=\"i2\" src=\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2010\/08\/i2.png?resize=259%2C196&#038;ssl=1\" alt=\"\" width=\"259\" height=\"196\" \/><\/a><\/p>\n<p>The above algorithm doesn&#8217;t even get off the ground with these non-isomorphic graphs \ud83d\ude42\u00a0 One can imagine, however, more sophisticated versions of the above algorithm, for example by labeling edges instead of vertices.\u00a0 It turns out there is a very general set of algorithms of this form, known as the k-dimension Weisfeiler-Lehman algorithm, that work along the lines of what we have described above.\u00a0 Boris Weisfeiler, as I mentioned in a previous post, went <a href=\"http:\/\/weisfeiler.com\/boris\/\">missing in Chile<\/a> in 1985 under presumably nefarious circumstances.\u00a0 For a good introduction to the WL algorithm, I recommend the paper<\/p>\n<ul>\n<li>&#8220;On Construction and Identification of Graphs (with contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler. Edited by B. Weisfeiler)&#8221;, Lecture Notes in Mathematics, 558 1976 (<a href=\"http:\/\/weisfeiler.com\/boris\/papers\/1976-lnm.pdf\">paper here<\/a>)<\/li>\n<\/ul>\n<p>The dimension $latex k$ in the WL algorithm refers to whether the basic object being considered are subsets with cardinality $latex k$ of $latex {1,2,dots,n}$.\u00a0 If the k dimensional WL algorithm solved graph isomorphism for k constant, then this would give an efficient algorithm for graph isomorphism.\u00a0 For many years whether this was true or not was not known, and a large body of work was developed (mostly in Russia) around this method, including the introduction of topics such as cellular algebras and coherent configurations.\u00a0 However in 1991, Cai, Furer, and Immerman showed that this approach to efficiently solving graph isomorphism does not yield an efficient graph isomorphism algorithm.\u00a0 The paper where they do that is very readable and gives a good history of the WL algorithm<\/p>\n<ul>\n<li>&#8220;An optimal lower bound on the number of variables for graph identification&#8221; by Jin-Yi\u00a0Cai, Martin\u00a0F\u00fcrer, and Neil\u00a0Immerman, Combinatorica, 12, 389-410 1991 (<a href=\"http:\/\/link.springer.com\/article\/10.1007%2FBF01305232\">paper here<\/a>)<\/li>\n<\/ul>\n<p>At this point you might be thinking to yourself, &#8220;Hey, isn&#8217;t this the Quantum Pontiff?\u00a0 Where is the discussion of quantum approaches to graph isomorphism?&#8221;\u00a0 Okay, maybe that&#8217;s not what you&#8217;re thinking, but what the hell, now is as good as time as any to talk about quantum approaches to the problem.\u00a0 There are two main approaches to attacking the graph isomorphism problem on quantum computers.\u00a0 The first is related to the hidden subgroup problem and the second is related to state preparation and the swap test.\u00a0 A third &#8220;spin-off&#8221;, inspired by quantum physics also exists, which I will also briefly mention.<br \/>\nRecall that the hidden subgroup problem is as follows:<\/p>\n<blockquote><p>Hidden Subgroup Problem (HSP): You are given query access to a function $latex f$ from a group $latex G$ to a set $latex S$ such that $latex f$ is constant and distinct on an left cosets of an unkown subgroup $latex H$.\u00a0 Find $latex H$ by querying $latex f$.<\/p><\/blockquote>\n<p>Quantum computers can efficiently (efficiently here means in a time polynomial in the logarithm of the size of the group) solve the hidden subgroup problem when the group $latex G$ is a finite Abelian group.\u00a0 Indeed Shor&#8217;s algorithm for factoring and discrete logarithm can be seen as solving such Abelian HSPs.\u00a0 A nice introduction to the Abelian version of this problem, though it is now a little out of date is<\/p>\n<ul>\n<li>&#8220;The Hidden Subgroup Problem &#8211; Review and Open Problems&#8221; by Chris Lomont 2004 <a href=\"http:\/\/arxiv.org\/abs\/quant-ph\/0411037\">arXiv:quant-ph\/0411037<\/a><\/li>\n<\/ul>\n<p>A more up to date introduction to the problem is provided by<\/p>\n<ul>\n<li>&#8220;Quantum algorithms for algebraic problems&#8221; by Andrew Childs and Wim van Dam, Reviews of Modern Physics 82, 1-52 2010 <a href=\"http:\/\/arxiv.org\/abs\/0812.0380\">arXiv:0812.0380<\/a><\/li>\n<\/ul>\n<p>What is the connection to the graph isomorphism problem?\u00a0 Well the basic result is that if one could efficiently solve the HSP over the symmetric group (or the wreath product group $latex S_n wr S_2$) then one would be able to efficiently solve graph isomorphism.\u00a0 A place to find this is in<\/p>\n<ul>\n<li>&#8220;A Quantum Observable for the Graph Isomorphism Problem,&#8221; by Mark Ettinger and Peter Hoyer (1999) <a href=\"http:\/\/arxiv.org\/abs\/quant-ph\/9901029\">arXiv:quant-ph\/9901029<\/a><\/li>\n<\/ul>\n<p>This paper establishes that there is a measurement one can perform on a polynomial number of qubits that solves the graph isomorphism problem.\u00a0 Unfortunately it is not known how to efficiently implement this measurement (by a circuit of polynomial depth.)\u00a0 Even more unfortunately there is a negative result that says that you really have to do something non-trivial across the entire system when you implement this measurement.\u00a0 This is the culminating work reported in<\/p>\n<ul>\n<li>&#8220;Limitations of quantum coset states for graph isomorphism&#8221; by Sean Hallgren, Cristopher Moore, Martin Rotteler, Alexander Russell, and Pranab Sen, STOC 2006 (<a href=\"http:\/\/www.cse.psu.edu\/~sjh26\/multireg.pdf\">paper here)<\/a><\/li>\n<\/ul>\n<p>At this point it seems that new ideas are needed to make progress along this line of attack.\u00a0 I have tried my own <a href=\"http:\/\/arxiv.org\/abs\/quant-ph\/0612107\">pseudo-new ideas<\/a>, but alas they have come up wanting.<br \/>\nAt this point it is useful to mention that there is a variation on the hidden subgroup problem, the hidden shift problem, which is arguably more naturally connected to the graph isomorphism problem.\u00a0 You can learn about this here<\/p>\n<ul>\n<li>&#8220;On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems,&#8221; by Andrew Childs and Pawel Wocjan, Quantum Information and Computation, 7 (5-6) 504-521, 2007 <a href=\"http:\/\/arxiv.org\/abs\/quant-ph\/0510185\">arXiv:quant-ph\/0510185<\/a><\/li>\n<\/ul>\n<p>I could go on and on about the hidden subgroup problem, but I think I&#8217;ll spare you.<br \/>\nBeyond the hidden subgroup problem, what other approaches are there to finding efficient quantum algorithms for the graph isomorphism problem?\u00a0 A lesser studied, but very interesting approach relates graph isomorphism to state preparation.\u00a0 Let $latex A_1$ and $latex A_2$ denote the adjacency matrices of the two graphs to be tested.\u00a0 Now imagine that we can create the states<\/p>\n<p style=\"text-align: center;\">$latex |P_irangle = sqrt{|Aut(G_i)| over n!} sum_{P} |PA_iP^{-1}rangle$<\/p>\n<p style=\"text-align: left;\">where $latex Aut(G_i)$ is the automorphism group of graph $latex G_i$, and the sum is over all $latex n times n$ permutation matrices.\u00a0 Now notice that if $latex G_1$ and $latex G_2$ are isomorphic, then these two states are identical.\u00a0 If, on the other hand, $latex G_1$ and $latex G_2$ are not isomorphic then these states are orthogonal $latex langle P_1|P_2rangle=0$, since the superpositions above cannot contain the same term or this would yield and isomorphism.\u00a0 Using this fact one can use the swap test to solve graph isomorphism&#8230;given the ability prepare $latex |P_1rangle$ and $latex |P_2rangle$.\u00a0 (See <a href=\"https:\/\/dabacon.org\/pontiff\/?p=3764\">here<\/a> for a discussion of the swap test.)\u00a0 Unfortunately, no one knows how to efficiently prepare $latex |P_1rangle$ and $latex |P_2rangle$!\u00a0 A good discussion, and one attack on this problem is given in the paper<\/p>\n<ul>\n<li>&#8220;Adiabatic quantum state generation and statistical zero knowledge&#8221; by Dorit Aharonov and Amnon Ta-ShmaSTOC 2003 <a href=\"http:\/\/arxiv.org\/abs\/quant-ph\/0301023\">arXiv:quant-ph\/0301023<\/a><\/li>\n<\/ul>\n<p>Finally let me mention a &#8220;quantum inspired&#8221; approach to graph isomorphism which has recently led to a sort of dead end, but that I find interesting.\u00a0 This is the approach is described in<\/p>\n<ul>\n<li>&#8220;Constructing physically intuitive graph invariants&#8221; by Terry Rudolph 2002 <a href=\"http:\/\/arxiv.org\/abs\/quant-ph\/0206068\">arXiv:quant-ph\/0206068<\/a><\/li>\n<\/ul>\n<p>The basic idea is as follows.\u00a0 As I described above, using the spectra (the list of eigenvalues) of an adjacency matrix is not enough to distinguish non-ismorphic graphs.\u00a0 Now the adjacency matrix is closely related to random walks on the graph being considered.\u00a0 Indeed from the adjacency matrix and diagonal matrix one can construct what is called the Laplacian of a graph and this is the infinitesimal generator of a random walk on the graph (I&#8217;m being sketchy here.)\u00a0 So thinking about this, one can ask: well what graph describes two random walkers?\u00a0 Well if these walkers take turns moving, then one can see that two random walkers on a graph walk on the graph described by<\/p>\n<p style=\"text-align: center;\">$latex A otimes I\u00a0 + I otimes A$<\/p>\n<p style=\"text-align: left;\">where $latex A$ is the original one walker adjacency matrix.\u00a0 But of course the spectra of this new walk doesn&#8217;t help you in making a better invariant for graphs as the eigenvalues of this new walk are just the various sums of the prior eigenvalues.\u00a0 But, aha!, you say, what if we think like a quantum physicist and make these walkers either fermions or bosons.\u00a0 This corresponds to either anti-symmeterizing the above walk or symmeterizing it:<\/p>\n<p style=\"text-align: center;\">$latex S_{pm} (A otimes I\u00a0 + I otimes A) S_{pm}$<\/p>\n<p style=\"text-align: left;\">where $latex S_{pm}={1 over 2}(I+SWAP)$ where $latex SWAP$ swaps the two subsystems.\u00a0 Well it is easy to check that this doesn&#8217;t help either: if you look at all of the eigenvalues of the fermion and boson walks you really just have the original eigenvalue information and no more.\u00a0 What Terry did, however, was to think more like a physicist.\u00a0 He said: well what if we consider the walkers to be bosons but now I make them what physicists call hard-core bosons (I wouldn&#8217;t recommend googling that): bosons that can&#8217;t sit on top of each other.\u00a0 This means that in addition to symmetrizing the $latex A otimes I\u00a0 + I otimes A$ matrix, you also remove the part of matrix where the two walkers sit on the same vertex.\u00a0 Terry shows that when he does this for certain non-isomorphic strongly regular graphs that are isospectral, if he considers three walkers, the eigenvalues are no longer the same.\u00a0 Very cool.\u00a0 Some follow up papers examined this in more detail<\/p>\n<ul>\n<li>&#8220;Symmetric Squares of Graphs&#8221; by Koenraad Audenaert, Chris Godsil, Gordon Royle, Terry Rudolph Journal of Combinatorial Theory, Series B, 97, 74-90 2007 <a href=\"http:\/\/arxiv.org\/abs\/math\/0507251\">arXiv:math\/0507251<\/a><\/li>\n<li>&#8220;Physically-motivated dynamical algorithms for the graph isomorphism problem&#8221; by Shiue-yuan Shiau, Robert Joynt, and S.N. Coppersmith, Quantum Information and Computation, 5 (6) 492-506 2005 <a href=\"http:\/\/arxiv.org\/abs\/quant-ph\/0312170\">arXiv:quant-ph\/0312170<\/a><\/li>\n<\/ul>\n<p>(Also note another line of sort of similar investigation <a href=\"http:\/\/arxiv.org\/abs\/quant-ph\/0505026\">arXiv:quant-ph\/0505026<\/a>.)\u00a0 So does this method lead anywhere?\u00a0 Unfortunately the answer appears to be negative.\u00a0 Here is a paper<\/p>\n<ul>\n<li>&#8220;Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements&#8221; by Alfredo Alzaga, Rodrigo Iglesias, and Ricardo Pignol <a href=\"http:\/\/arxiv.org\/abs\/0801.2322\">arXiv:0801.2322<\/a><\/li>\n<\/ul>\n<p>that demonstrates that the $latex k$ hard-core boson walker matrix provides no more information than the $latex 2k$ dimensional WL algorithm (which Cai, Furer, and Immerman showed cannot work.\u00a0 Strangely it appears that Greg Kuperberg, like Babe Ruth before him, <a href=\"http:\/\/www.scottaaronson.com\/blog\/?p=112#comment-3058\">called this one<\/a>.\u00a0 Nice!)\u00a0 Recently a different approach has also emerged to showing that this doesn&#8217;t work<\/p>\n<ul>\n<li style=\"text-align: left;\">&#8220;Non-Isomorphic Graphs with Cospectral Symmetric Powers&#8221; by Amir Rahnamai Barghi and Ilya Ponomarenko, The Electronic Journal of Combinatorics, 16(1) R120 2009 (<a href=\"http:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v16i1r120\/pdf\">paper here<\/a>)<\/li>\n<\/ul>\n<p>using the nice theory of schemes.\u00a0 So a good physicist inspired idea, but so far, no breakthrough.<br \/>\nWell I&#8217;ve gone on for a long while now.\u00a0 Perhaps one final reading to perform is related to graph isomorphism complete problems.\u00a0 Since graph isomorphism is not known to be in P nor is it known to be NP-complete, it is &#8220;natural&#8221; to define the complexity class related to graph isomorphism, GI, which is made up of problems with a polynomial time reduction to the graph isomorphism problem.\u00a0 Then, similar to NP-complete problems, there are GI-complete problems.\u00a0 Wikipedia has a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Graph_isomorphism_problem#GI-complete_and_GI-hard_problems\">nice list<\/a> of such problems, but it doesn&#8217;t contain my favorite.\u00a0 I like this one because it doesn&#8217;t seem similar to graph isomorphism upon first reading:<\/p>\n<ul>\n<li>&#8220;The Complexity of Boolean Matrix Root Computation&#8221; by Martin Kutz, Theoretical Computer Science, 325(3) 373-390, 2004 (<a href=\"http:\/\/www.mpi-inf.mpg.de\/alumni\/d1\/2009\/mkutz\/\/pubs\/Kutz_MatrixRoots1.ps\">paper here<\/a>)<\/li>\n<\/ul>\n<p>Sadly <a href=\"http:\/\/www.mpi-inf.mpg.de\/alumni\/d1\/2009\/mkutz\/\/\">Martin Kutz<\/a> passed away in 2007 at what appears to be a quite young age, considering his condensed publication record.\u00a0 Read his paper for a nice square root of matrices problem that is graph isomorphism complete.<br \/>\nSo see how much fun studying graph isomorphism can be?\u00a0 Okay, for some definition of fun!\u00a0 Please feel free to post other papers in the comment section.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Warning: this idiosyncratic list of reading material is in no way meant to be comprehensive nor does is it even guaranteed to focus on the most important papers concerning graph isomorphism.\u00a0 Suggestions for other papers to add to the list are greatly appreciated: leave a comment! The graph isomorphism problem is an intriguing problem. A &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/dabacon.org\/pontiff\/2010\/08\/04\/reading-list-graph-isomorphism\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Reading List: Graph Isomorphism&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[20,32,41,65],"tags":[],"class_list":["post-4148","post","type-post","status-publish","format-standard","hentry","category-computer-science","category-general","category-mathematics","category-quantum-computing"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/4148","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/comments?post=4148"}],"version-history":[{"count":3,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/4148\/revisions"}],"predecessor-version":[{"id":12132,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/4148\/revisions\/12132"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=4148"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=4148"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=4148"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}