What graph invariants are fast to compute? Problem: describe classes of automorphism for the following collection of graphs.
Let $\mathbb{F}$ be a finite field of order $q$; then the vertex set V is defined as $V = \{(x,y) : x\in\mathbb{F},y\in\mathbb{F}\}$; adjacency is defined as follows: there is an arc from  $(x_1,x_2)$ to $(y_1,y_2)$ iff $x_2 + y_2 = x_1^m y_1^n$, where $1\le m,n\le q-1$.
Clearly, $|V|=q^2$, and the number of arcs is about $q^3$. Even for $q=17$ the problem of sorting all $(q-1)^2$ graphs corresponding to possible values of $m$ and $n$ becomes computationally hard. I've managed to obtain explicit formulas for the number of 2- and 3-cycles. So I first sort these graphs out by these parameters: this is done immediately. Then, by their diameter, then by their characteristic polynomial, then by the number of 4-cycles (this is done by brute-force). Only after that I'm checking them directly for isomorphism.
Are there any other invariants that are easy to compute, so that I could separate the $(q-1)^2$ as close to isomorphic classes as possible before actually starting to check them for isomorphism directly. Would the Laplacian spectrum or something like this be "cheap" to compute?
 A: Maybe there is a problem with processing of digraphs in sage.  nauty takes 0.07 seconds to canonically label each of the graphs $(17;1,3)$ and $(17;3,1)$. They are indeed isomorphic. This translates to 20 seconds for sorting all $16^2$ graphs (and probably some pre-preprocessing can cut that down a bit).
The automorphism group of these two graphs has 94 orbits and order $2^{52} 3^{51}$.  I guessed there would be fewer orbits than that.
It seems to scale ok too. Graph $(37;1,3)$ takes 18 seconds, so that size would take about 6 hours altogether.
Feel free to be in touch off-list.  bdm(at)cs.anu.edu.au
A: 2 Jack: Counting 4-cycles after char poly actually does refine these graphs into smaller groups further down. It seems like counting $k$-cycles for $k\ge 5$ after counting 4-cycles doesn't make much sense.
2 Brendan:
I'm using the internal facility of sage (an open source project encompassing GAP, Maxima and other open source math-related projects wrapped into a Python framework). I very much believe it's based on the same ideas from your paper that nauty is. So it can't be much worse. Checking the underlying looped undirected graphs obtained by sage's graph.to_undirected() is indeed an easy problem. However even checking whether a pair of graphs corresponding to parameters $(m,n) = (1,3)$ and $(m,n) = (1,3)$ for $q=17$, are isomorphic to each other, proves to be quite hard. 
