Automorphisms of a 76 million vertex graph
I’ve been meaning to write a post about practical graph automorphism finding for a while, and the last few days experience has finally prompted me to do so now.
The problem of finding the automorphism group of a graph — by this, I mean using software to actually determine the group as a permutation group — is pretty fundamental to a whole range of construction and counting problems. It is obviously very closely related to the graph isomorphism problem, which is to determine whether two graphs are isomorphic. This problem, known as GI, is a problem whose complexity is well known to be unknown (if you see what I mean!). Graph isomorphism is in NP, but it is not known to be either NP-complete or in P, so is a prime candidate for the problem of intermediate complexity that would show that P $\not=$ NP. Finding the automorphism group of a graph is at least as hard as graph isomorphism, because you could use an automorphism-finder to resolve whether G and H are isomorphic by computing the automorphism group of the disjoint union of G and H, and seeing whether any automorphisms swapped the components.
In practice, graph automorphism finding is relatively easy and the automorphism group can be calculated for large graphs, indeed enormous graphs! For more than three decades, the “go-to” software for finding automorphisms of graphs has been Brendan McKay’s program “nauty” which has been used by hundreds, even thousands, of researchers at various points. My thesis, nearly 30 years ago, used one of the early versions of nauty. There are other programs available of course, some of which outperform nauty on particular families of graphs, but none of which match the combination that nauty offers in terms of availability, long-term development and maintenance and overall performance.
Around 25 years ago, I noticed that certain graphs were proving particularly difficult for nauty to process, namely the bipartite point-line incidence graphs of non-desarguesian projective planes. At the time I was working with projective planes of order 9, which have 91 points and 91 lines, and so these were only 182 vertex graphs. I can’t remember the exact numbers, but it took about 0.5 seconds cpu time to process PG(2,9), about 10 seconds to process the Hall plane of order 9 and about 200 hours to find the automorphism group of the Hughes plane of order 9. Of course Brendan immediately put some effort into finding new invariants and other tweaks to make computing the automorphism groups of these projective planes graphs tractable, but they are still much more difficult than most graphs of the same size. (Other geometric graphs such as the incidence graphs of GQs are difficult, but not that difficult.)
A few years ago, Brendan and I were at a meeting in Bristol when we were approached by one of the other delegates who was keen to show us his results on computing automorphism groups of projective planes. He had devised a method of computing the search tree using a hybrid mixture of breadth-first and depth-first search — essentially a single run to the maximum depth of the tree yields an automorphism that can then later be effectively used to prune entire branches of the tree at a very early stage. The results were nothing short of spectacular, with huge projective planes now yielding in seconds rather than days. The researcher in question is called Adolfo Piperno, his technique is called Traces and Adolfo and Brendan have combined forces to refine both techniques and implement them robustly, with the final result being the imaginatively-named “nauty/Traces” package.
So how good is this in practice? For what size of graph can you realistically hope to determine the automorphism group? Pretty big is the answer to that question — in the last few days I’ve managed to use nauty/Traces to determine the automorphism group of a graph with just over 76 million vertices! This graph is a 10-regular graph obtained by taking a primitive representation of the group PSp(6,3) of degree 76422528, which has a non-self paired orbital of valency 5, which thus determines a digraph of out-valency 5. Dropping the directions on the arcs gives us a graph of valency 10. For various reasons, we wanted to know whether the full automorphism group of this graph is just the original PSp(6,3) or bigger.
Of course, it is impossible to store a 76 million x 76 million adjacency matrix, even if it is bit-packed, but fortunately Brendan has recently (in the last few years) added the ability to work with adjacency lists, thus basically using space proportional to the number of edges, rather than the square of the number of vertices. Just forming the file that defined the graph was a tedious process because GAP and Magma can’t do anything fast in groups of this degree, and there are many things that they simply cannot do at all (e.g. find the order of the group!). So I had to “hand-roll” lots of little bits of code that did basic things but in roundabout ways that didn’t use up too much memory and didn’t trigger anything that would never finish.
Once I had the file, the rest was simple. I actually just used the program dreadnaut which is a command-line user interface for nauty/Traces. The input file looked like this:
n=76422528 $=1 g 20385294, 22694895, 50999204, 58103886, 74686745 ; 14658604, 27594574, 45288953, 46264591, 69387673 ; (76422525 lines omitted) 3976598, 18300815, 27911643, 64737249, 74506343 . x
The first two lines set the number of vertices, then the base of the numbering (my vertices are numbered 1 to 76422528, rather than 0 to 76422527). The “g” puts it into graph-input mode, and the next 76422528 lines are the neighbours of each vertex — they are only specified in one direction but unless specified otherwise, nauty/Traces will automatically treat the graph as undirected. Finally, the “x” tells the program to compute the automorphism group.
This whole file — of size 3.6Gb — is then piped into the dreadnaut program with suitable flags to tell it to use Traces and the sparse representation. A little while later, after lots of output of the four permutations, I get the result
1 orbit; grpsize=9170703360; 4 gens; 9 nodes (6 peak);maxlev=2 cpu time = 1550.93 seconds
Unfortunately it wasn’t the result I wanted, because the group of the graph has doubled in size from the guaranteed PSp(6,3) and I was really hoping for this not to happen, because it would have yielded a primitive half-arc transitive graph of the lowest possible valency, whose existence is currently unresolved.
However, I am still hugely impressed that it is possible to find the automorphism group of a 76 million vertex non-trivial graph – in fact I’d really have to say that it’s spectacular!
By way of contrast, consider the NP-complete problem of finding the chromatic number of a graph. This problem is theoretically difficult, but it also seems to be practically difficult – already at 100-200 vertices, there are graphs whose chromatic number I simply cannot determine.
Written with StackEdit.