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?