sage->nauty->directed graphs isomorphism vs. magma -- smth is very wrong

[Aleksandr Kodess]

As far as I know both sage and magma utilize Brendan McKay's program nauty in order to check whether two given graphs (directed or undirected) are isomorphic. As is demonstrated by the following example, sage and magma greatly differ in the efficiency in which this program is utilized.

# sage code
q = 19
n1 = 7
n2 = 13
F = FiniteField(q, 'xi')
V = [(x,y) for x in F for y in F]
G1 = DiGraph([V, lambda x,y: x[1] + y[1] == x[0]*(y[0]**n1)])
G2 = DiGraph([V, lambda x,y: x[1] + y[1] == x[0]*(y[0]**n2)])
G1.is_isomorphic(G2)

// magma code for the same operation
q := 19;
n1 := 7;
n2 := 13;
F := FiniteField(q);
V := {[x,y] : x,y in F};
G1 := Digraph< V|{ [x,y] : x,y in V | x[2] + y[2] eq ((x[1])^1)*((y[1])^n1)}>;
G2 := Digraph< V|{ [x,y] : x,y in V | x[2] + y[2] eq ((x[1])^1)*((y[1])^n2)}>;
IsIsomorphic(G1,G2);

It takes sage forever to test whether these two directed graphs of order 19^2 are isomorphic (they are in fact not), while it takes magma only a second. The same problem occurs for other values of q, n1 and n2. The version of sage I'm running is 5.12, and the version of magma I'm running is 2.19.10.

Is this a known issue? Is this going to be fixed any time soon?

[Volker Braun]

The license of nauty is not gpl compatible, so we can't distribute it with Sage. There is an optional package that you can try if you want.

[David Joyner]

On Fri, Feb 28, 2014 at 4:18 PM, Aleksandr Kodess <amko...@gmail.com> wrote:
> As far as I know both sage and magma utilize Brendan McKay's program nauty in order to check

That is completely false. Robert Miller implemented from scratch a
number of graph-theory
algorithms independently of the code in nauty.

I don't know the answer to your question below but want to correct you on this
one statement.

> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/groups/opt_out.

[Chris Godsil]

I would not be surprised it it was the finite field arithmetic that is causing the difference.

[Tom Boothby]

Once the graph is constructed, is_isomorphic throws away the vertex
labels and just works with pointers to ints. Constructing the graph
itself happens in a blink. Sadly, the bulk of the time is spent in
is_isomorphic.

The answer to Aleksandr's question is: Yes, this is a known issue --
nauty has been mercilessly optimized over decades, while nice
(Robert's implementation) is still in its infancy. Optimizing it to
be competitive will take years of dedicated effort, and a huge amount
of knowledge in computational group theory (there may be savings to
had with strong integration with libgap). Robert is on hiatus (or
retired altogether) from academia, and hasn't spent much time on nice
in the last few years. So, unfortunately, Sage has no current viable
plan to improve isomorphism checking.

[Volker Braun]

AFAIK both implement the same basic algorithm. My guess is that nauty quickly realizes that it has a huge problem and starts constructing graph invariants in an attempt to answer it to the negative. If you were to compare two graphs that are actually isomorphic I'm pretty sure that you wouldn't find such a big difference. For practical applications it is of course important to have this trick using easily-accessible graph invariants, but its probably not that hard to implement.. 

[Dima Pasechnik]

it's known that most "easy" graph invariants, such as counting
sizes of isomorphism classes of k-vertex subgraphs on each arc,
are only heuristics (cf. Cai-Furer-Immerman results). However,
if you average over sufficiently large classes of graphs, these
heuristics appear to work quite well.

[Tom Boothby]

They do implement the same basic algorithm. However, Robert worked
from McKay's paper describing the algorithm, which was approximately
state-of-the-art when he wrote the paper (but of course, the community
tends to eschew optimizations as superfluous to the math, so...).
Also, nauty has some pretty serious optimizations that Robert hasn't
even attempted: graphs with <=32 vertices are implemented with bit
hacks, for example... and there's the matter of the partition stack
invariant - Robert and I came up with the best thing we could, but
suspect that McKay's is better (but we didn't peek into his
implementation to avoid license issues).

[Dima Pasechnik]

On 2014-03-04, Tom Boothby <tomas....@gmail.com> wrote:
> They do implement the same basic algorithm. However, Robert worked
> from McKay's paper describing the algorithm, which was approximately
> state-of-the-art when he wrote the paper (but of course, the community
> tends to eschew optimizations as superfluous to the math, so...).
> Also, nauty has some pretty serious optimizations that Robert hasn't
> even attempted: graphs with <=32 vertices are implemented with bit
> hacks, for example... and there's the matter of the partition stack
> invariant - Robert and I came up with the best thing we could, but
> suspect that McKay's is better (but we didn't peek into his
> implementation to avoid license issues).

Do you keep track of graph automorphisms that pop up along the way?
This is potentially a huge improvement in the situation graphs do
have nontrivial automorphisms.

Do you attempt to construct isomorphisms directly, or you rather
compute canonical forms? The latter is known to be less efficient in
practice in many cases.

Dima

[Tom Boothby]

Yes automorphisms that pop up along the way are used to prune the
search tree. That's a key feature of McKay's algorithm. Also, you
are correct, checking for isomorphism of two graphs is faster than
computing the canonical forms of each (this is what happens when you
call G.is_isomorphic(H)), but my advice to Aleksandr is that in the
case where you want to make a database, the fastest way to check if
something's new is to use a hash -- and a canonical label is the first
step towards getting an isomorph-invariant hash.