### Computing SODO

### Brendan McKay

### Australian National University

### Adolfo Piperno University of Rome

computing sodo — 1

### Isomorphism and Automorphism

We have some finite objects consisting of some finite sets and some relations on them.

An isomorphism between two objects is a bijection between their sets so that the relations are preserved. Hopefully, isomorphism is an equivalence relation on the set of all objects.

computing sodo — 2

### Isomorphism and Automorphism

We have some finite objects consisting of some finite sets and some relations on them.

An isomorphism between two objects is a bijection between their sets so that the relations are preserved. Hopefully, isomorphism is an equivalence relation on the set of all objects.

Isomorphisms from an object to itself are automorphisms. If we didn’t do anything silly, the set of automorphisms forms a group under composition.

Of course we call it the automorphism group.

8

1

7 6 5

3 4 2

computing sodo — 2

### Isomorphism and Automorphism

We have some finite objects consisting of some finite sets and some relations on them.

An isomorphism between two objects is a bijection between their sets so that the relations are preserved. Hopefully, isomorphism is an equivalence relation on the set of all objects.

Isomorphisms from an object to itself are automorphisms. If we didn’t do anything silly, the set of automorphisms forms a group under composition.

Of course we call it the automorphism group.

8

1

7 6 5

3 4 2

(1)

(1 4)(2 3)(5 8)(6 7) (1 8)(2 7)(3 6)(4 5) (1 5)(2 6)(3 7)(4 8)

computing sodo — 2

### Ubiquity of graph isomorphism

Very many isomorphism problems can be eﬃciently expressed as graph isomorphism problems. For convenience, we usecoloured graphs, in which the vertices (and possibly the edges) are coloured. Isomorphisms must preserve vertex and edge colour.

###

###

### 1 3 5 4 1 5 4 3 3 4 5 1

###

###

Say two matrices are isomorphic if one can be obtained from the

other by permuting rows and columns.

computing sodo — 3

### Ubiquity of graph isomorphism

Very many isomorphism problems can be eﬃciently expressed as graph isomorphism problems. For convenience, we usecoloured graphs, in which the vertices (and possibly the edges) are coloured. Isomorphisms must preserve vertex and edge colour.

= 4

= 5

= 3

= 1

###

###

### 1 3 5 4 1 5 4 3 3 4 5 1

###

###

Say two matrices are isomorphic if one can be obtained from the

other by permuting rows and columns.

computing sodo — 3

### Hadamard equivalence

###

###

### 1 − ^{1} ^{1} 1 − ^{1} ^{1}

### − ^{1} − ^{1} ^{1}

###

###

Say isomorphism of two ±^{1 matrices}
allows permutation and negation
of rows and columns.

computing sodo — 4

### Hadamard equivalence

###

###

### 1 − ^{1} ^{1} 1 − ^{1} ^{1}

### − ^{1} − ^{1} ^{1}

###

###

Say isomorphism of two ±^{1 matrices}
allows permutation and negation
of rows and columns.

computing sodo — 4

### Isotopy

###

###

### 1 3 2 2 1 3 3 2 1

###

###

Say isomorphism of two matrices allows permutation of rows, columns and symbols.

computing sodo — 5

### Isotopy

1 2

3 1

2

3

1 3 2

### Row

### Column

### Symbol

###

###

### 1 3 2 2 1 3 3 2 1

###

###

Say isomorphism of two matrices allows permutation of rows, columns and symbols.

computing sodo — 5

### Isotopy

1 2

3 1

2

3

1 3 2

### Row

### Column

### Symbol

1 2

3 1

2

3

1 3 2

### Row

### Column

### Symbol

###

###

### 1 3 2 2 1 3 3 2 1

###

###

Say isomorphism of two matrices allows permutation of rows, columns and symbols.

computing sodo — 5

### Group isomorphism

###

###

###

###

### e g

1### g

2### g

3### g

1### e g

3### g

2### g

2### g

3### e g

1### g

3### g

2### g

1### e

###

###

###

###

computing sodo — 6

### Group isomorphism

###

###

###

###

### e g

1### g

2### g

3### g

1### e g

3### g

2### g

2### g

3### e g

1### g

3### g

2### g

1### e

###

###

###

###

The group elements are edge colours and vertices.

The black vertex is the identity element.

Preserve vertex colours but allow permutation of edge colours.

computing sodo — 6

### Group isomorphism

###

###

###

###

### e g

1### g

2### g

3### g

1### e g

3### g

2### g

2### g

3### e g

1### g

3### g

2### g

1### e

###

###

###

###

The group elements are edge colours and vertices.

The black vertex is the identity element.

Preserve vertex colours but allow permutation of edge colours.

The fastest known algorithm for group isomorphism is trivial and has time

### n

^{O}

^{(log}

^{n}

^{)}.

computing sodo — 6

### Permutation equivalence of linear codes

###

###

###

###

###

### 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0

###

###

###

###

###

computing sodo — 7

### Permutation equivalence of linear codes

###

###

###

###

###

### 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0

###

###

###

###

### ?

Suppose isomorphism of two 0-1 matrices means that their columns can be permu- tated so that the rows generate the same vector space over

### GF

(2).Nobody knows how to make an equivalent graph problem of size which is polynomial in the size of the generator matrix.

computing sodo — 7

### Isomorphism and automorphism are much the same

computing sodo — 8

### Isomorphism and automorphism are much the same

**G** **H**

**G**

**H**

computing sodo — 8

### Isomorphism and automorphism are much the same

**G** **H** **H** **G**

**G**

**H**

**H**

**G**

computing sodo — 8

### Isomorphism and automorphism are much the same

**G** **H** **H** **G**

**G**

**H**

**H**

**G**

computing sodo — 8

### Isomorphism and automorphism are much the same

**G** **H** **H** **G**

**G**

**H**

**H**

**G**

computing sodo — 8

### Isomorphism and automorphism are much the same

**G** **H** **H** **G**

**G**

**H**

**H**

**G**

computing sodo — 8

### Isomorphism and automorphism are much the same

**G** **H** **H** **G**

**G**

**H**

**H**

**G**

computing sodo — 8

### Theoretical complexity

The graph isomorphism problem is:

### GI: Given two graphs, determine whether they are isomorphic.

### •

The fastest known algorithm for GI is exp�### O

(√### n

log### n

)�time; no polynomial time algorithm is known (despite many claims).

### •

GI is not known to be NP-complete.### •

GI is not known to be in co-NP.### •

There are polynomial time algorithms for many special classes of graphs (bounded degree, bounded genus, classes with excluded minors or topological subgraphs).Few of these are practical, planar graphs being a notable exception.

computing sodo — 9

### Minor-closed classes

computing sodo — 10

### Minor-closed classes

computing sodo — 10

### Minor-closed classes

### C

4### as a minor

computing sodo — 10

### Minor-closed classes

### C

4### as a topological minor

computing sodo — 10

### Minor-closed classes

### C

4### as a topological minor

Martin Grohe (2012) showed that GI is solvable in polynomial time for any class of graphs that avoid any fixed graph as a topological minor.

computing sodo — 10

### Problems

1. Prove any of these inequalities are equalities:

### P

≤ Group isomorphism ≤ Graph isomorphism≤ Code isomorphism ≤^{NP}Graph isomorphism≤ Set-stabiliser in permutation group

computing sodo — 11

### Problems

1. Prove any of these inequalities are equalities:

### P

≤ Group isomorphism ≤ Graph isomorphism≤ Code isomorphism ≤^{NP}Graph isomorphism≤ Set-stabiliser in permutation group

2. Improve

### n

^{O}

^{(log}

^{n}

^{)}time for group isomorphism. (Best result so far: polynomial time for groups without abelian normal subgroups: Babai, Codenotte, Gorchow and Qiao, unpublished).

computing sodo — 11

### Problems

1. Prove any of these inequalities are equalities:

### P

≤ Group isomorphism ≤ Graph isomorphism≤ Code isomorphism ≤^{NP}Graph isomorphism≤ Set-stabiliser in permutation group

2. Improve

### n

^{O}

^{(log}

^{n}

^{)}time for group isomorphism. (Best result so far: polynomial time for groups without abelian normal subgroups: Babai, Codenotte, Gorchow and Qiao, unpublished).

3. Show that group isomorphism is in co-NP.

computing sodo — 11

### Problems

1. Prove any of these inequalities are equalities:

### P

≤ Group isomorphism ≤ Graph isomorphism≤ Code isomorphism ≤^{NP}Graph isomorphism≤ Set-stabiliser in permutation group

2. Improve

### n

^{O}

^{(log}

^{n}

^{)}time for group isomorphism. (Best result so far: polynomial time for groups without abelian normal subgroups: Babai, Codenotte, Gorchow and Qiao, unpublished).

3. Show that group isomorphism is in co-NP.

4. Show that graph isomorphism is in co-NP.

computing sodo — 11

### Problems

1. Prove any of these inequalities are equalities:

### P

≤ Group isomorphism ≤ Graph isomorphism≤ Code isomorphism ≤^{NP}Graph isomorphism≤ Set-stabiliser in permutation group

2. Improve

### n

^{O}

^{(log}

^{n}

^{)}time for group isomorphism. (Best result so far: polynomial time for groups without abelian normal subgroups: Babai, Codenotte, Gorchow and Qiao, unpublished).

3. Show that group isomorphism is in co-NP.

4. Show that graph isomorphism is in co-NP.

5. Improve the exp(

### O

(√### n

log### n

)) worst case for graph isomorphism.computing sodo — 11

### Canonical labelling

Given a class of objects, and a definition of “isomorphism”, we can choose one member of each isomorphism class and call it the canonical member of the class.

The process of finding the canonical member of the isomorphism class containing a given object is called “canonical labelling”.

computing sodo — 12

### Canonical labelling

Given a class of objects, and a definition of “isomorphism”, we can choose one member of each isomorphism class and call it the canonical member of the class.

The process of finding the canonical member of the isomorphism class containing a given object is called “canonical labelling”.

Two labelled objects which are isomorphic become identical when they are canonically labelled. Since identity of objects is usually far easier to check than isomorphism, canonical labelling is the preferred method of sorting a collection of objects into isomorphism classes.

computing sodo — 12

### Canonical labelling

Given a class of objects, and a definition of “isomorphism”, we can choose one member of each isomorphism class and call it the canonical member of the class.

The process of finding the canonical member of the isomorphism class containing a given object is called “canonical labelling”.

Two labelled objects which are isomorphic become identical when they are canonically labelled. Since identity of objects is usually far easier to check than isomorphism, canonical labelling is the preferred method of sorting a collection of objects into isomorphism classes.

A possible definition of the canonical member of an isomorphism class would be the member which maximises some linear representation (such as a list of edges).

In practice, most programs compute a canonical member which is easy for computers to find rather than easy for humans to define.

computing sodo — 12

### Software for graph isomorphism

This task was already described as a disease in 1970, and programs still appear regularly. The most successful programs still supported are:

### • nauty

(McKay, 1976–) canonical label and automorphism group### • VF2

(Cordella, Foggia, Sansone and Vento, 1999–) comparison of two graphs### • saucy

(Darga, Sakallah and Markov, 2004–) automorphism group### • bliss

(Juntilla and Kaski, 2007–) canonical label and automorphism group### • Traces

(Piperno, 2008–) canonical label and automorphism group### • conauto

(L´opez-Presa, Anta and Chiroque, 2009–) automorphism group and comparison of two graphsMany similar principles appear in these programs.

### saucy

^{and}

### bliss

began life as reimplementations of### nauty

but have since diverged.computing sodo — 13

### Partition refinement

A key concept used by

### nauty

is partition refinement. (“partition” = “colouring”) An equitable partition is one where every two vertices of the same colour are adjacent to the same number of vertices of each colour.Two examples of equitable partitions:

computing sodo — 14

Refinement of a partition means to subdivide its cells.

Given a partition (colouring)

### π

, there is a unique equitable partition that is a refinement of### π

and has the least number of colours.computing sodo — 15

Refinement of a partition means to subdivide its cells.

Given a partition (colouring)

### π

, there is a unique equitable partition that is a refinement of### π

and has the least number of colours.Count green neighbours Initial

Count pink neighbours Count yellow neighbours

computing sodo — 15

### Search tree

All competitive isomorphism programs generate a tree based on partition refinement.

The nodes of the tree correspond to partitions (colourings).

The root of the tree corresponds to the initial colouring, refined.

If a node corresponds to a discrete partition (each vertex with a diﬀerent colour), it has no children and is a leaf.

Otherwise we choose a colour used more than once (the target cell), individualize one of those vertices by giving it a new unique colour, and refine to get a child.

computing sodo — 16

### Search tree

All competitive isomorphism programs generate a tree based on partition refinement.

The nodes of the tree correspond to partitions (colourings).

The root of the tree corresponds to the initial colouring, refined.

If a node corresponds to a discrete partition (each vertex with a diﬀerent colour), it has no children and is a leaf.

Otherwise we choose a colour used more than once (the target cell), individualize one of those vertices by giving it a new unique colour, and refine to get a child.

Each leaf lists the vertices in some order (since colours have a predefined order), so it corresponds to a labelling of the graph.

computing sodo — 16

### Search tree

All competitive isomorphism programs generate a tree based on partition refinement.

The nodes of the tree correspond to partitions (colourings).

The root of the tree corresponds to the initial colouring, refined.

If a node corresponds to a discrete partition (each vertex with a diﬀerent colour), it has no children and is a leaf.

Otherwise we choose a colour used more than once (the target cell), individualize one of those vertices by giving it a new unique colour, and refine to get a child.

Each leaf lists the vertices in some order (since colours have a predefined order), so it corresponds to a labelling of the graph.

If we have two leaves giving the same labelled graph, we have found an automorphism.

If we define an order on labelled graphs, such as lexicographic order, then the greatest labelled graph corresponding to a leaf is a canonical graph.

computing sodo — 16

### Search tree

All competitive isomorphism programs generate a tree based on partition refinement.

The nodes of the tree correspond to partitions (colourings).

The root of the tree corresponds to the initial colouring, refined.

Each leaf lists the vertices in some order (since colours have a predefined order), so it corresponds to a labelling of the graph.

If we have two leaves giving the same labelled graph, we have found an automorphism.

If we define an order on labelled graphs, such as lexicographic order, then the greatest labelled graph corresponding to a leaf is a canonical graph.

However the tree can be much too large to generate completely.

computing sodo — 16

4 5 [ 4 | | 5 | 2 7 | 6 | 3 ]1 8 [ 1 4 5 8 | 2 3 6 7 ]

3 4 1 2

8 7 6 5

[ 1 | 4 | 5 | 8 | 6 | 3 | 7 | 2 ] [ 1 | 5 | 4 | 8 | 3 | 6 | 7 | 2 ] [ 4 | 1 | 8 | 5 | 7 | 2 | 6 | 3 ] [ ... ] [ ... ] [ ... ]

[ ... ] [ ... ] [ ... ] [ ... ]

1

7

2

4 5 3

6

8 1

7 6

3

2 5

8 2 1

3 5 4

6 8

### (1) (3 6)(4 5) (1 4)(2 3)(5 8)(6 7)

4

[ 1 | | 8 | 3 6 | 7 | 2 ]

7

computing sodo — 17

### Node invariants

A node invariant is a value

### φ

(### ν

) attached to each node in the tree that depends only on the combinatorial properties of### ν

and its ancestors in the search tree (not on the labelling of the graph).Moreover, the order of node invariants must be preserved by descendants:

Let

### ν

1### , ν

2 be nodes at the same level in the search tree. If### ν

_{1}

^{�}is a descendant of

### ν

1, and### ν

_{2}

^{�}is a descendant of

### ν

2, then### φ

(### ν

1)### < φ

(### ν

2) =⇒### φ

(### ν

_{1}

^{�})

### < φ

(### ν

_{2}

^{�})

### .

computing sodo — 18

### Node invariants

A node invariant is a value

### φ

(### ν

) attached to each node in the tree that depends only on the combinatorial properties of### ν

and its ancestors in the search tree (not on the labelling of the graph).Moreover, the order of node invariants must be preserved by descendants:

Let

### ν

1### , ν

2 be nodes at the same level in the search tree. If### ν

_{1}

^{�}is a descendant of

### ν

1, and### ν

_{2}

^{�}is a descendant of

### ν

2, then### φ

(### ν

1)### < φ

(### ν

2) =⇒### φ

(### ν

_{1}

^{�})

### < φ

(### ν

_{2}

^{�})

### .

For example,

### φ

(### ν

) = �### c

(### ν

^{�})

### , c

(### ν

^{��})

### , . . . , c

(### ν

)�is a node invariant with lexicographic ordering, where

### ν

^{�}

### , ν

^{��}

### , . . . , ν

is the path from the root of the tree to### ν

, and### c

( ) is the number of colours.computing sodo — 18

### Node invariants

A node invariant is a value

### φ

(### ν

) attached to each node in the tree that depends only on the combinatorial properties of### ν

and its ancestors in the search tree (not on the labelling of the graph).Moreover, the order of node invariants must be preserved by descendants:

Let

### ν

1### , ν

2 be nodes at the same level in the search tree. If### ν

_{1}

^{�}is a descendant of

### ν

1, and### ν

_{2}

^{�}is a descendant of

### ν

2, then### φ

(### ν

1)### < φ

(### ν

2) =⇒### φ

(### ν

_{1}

^{�})

### < φ

(### ν

_{2}

^{�})

### .

For example,

### φ

(### ν

) = �### c

(### ν

^{�})

### , c

(### ν

^{��})

### , . . . , c

(### ν

)�is a node invariant with lexicographic ordering, where

### ν

^{�}

### , ν

^{��}

### , . . . , ν

is the path from the root of the tree to### ν

, and### c

( ) is the number of colours.Let φ^{∗} be the greatest node invariant of a leaf. Then the lexicographically greatest
labelled graph corresponding to a leaf ν with φ(ν) =φ^{∗} is a canonical graph.

computing sodo — 18

### Pruning operations

Node invariants, together with automorphisms, allow us to remove parts of the search tree without generating them.

1. If

### ν

1### , ν

2 are nodes at the same level in the search tree and### φ

(### ν

1)### < φ

(### ν

2), then no canonical labelling is descended from### ν

1.2. If

### ν

1### , ν

2 are nodes at the same level in the search tree and### φ

(### ν

1) �^{=}

### φ

(### ν

2), then no labelled graph descended from### ν

1 is the same as one descended from### ν

2. 3. If### ν

1### , ν

2 are nodes with### ν

2 =### ν

_{1}

^{g}for an automorphism

### g

, then### g

maps the subtreedescended from

### ν

1 onto the subtree descended from### ν

2.computing sodo — 19

### Pruning operations

Node invariants, together with automorphisms, allow us to remove parts of the search tree without generating them.

1. If

### ν

1### , ν

2 are nodes at the same level in the search tree and### φ

(### ν

1)### < φ

(### ν

2), then no canonical labelling is descended from### ν

1.2. If

### ν

1### , ν

2 are nodes at the same level in the search tree and### φ

(### ν

1) �^{=}

### φ

(### ν

2), then no labelled graph descended from### ν

1 is the same as one descended from### ν

2. 3. If### ν

1### , ν

2 are nodes with### ν

2 =### ν

_{1}

^{g}for an automorphism

### g

, then### g

maps the subtreedescended from

### ν

1 onto the subtree descended from### ν

2.Each of these observations enables us to prune parts of the search tree.

The hope is that the remaining parts will be small enough to compute.

computing sodo — 19

### Variations between programs

The competing programs vary from each other in ways that include:

1. Data structures

2. Strength of the refinement procedure 3. Order of traversal of the search tree 4. Means of discovering automorphisms 5. Processing of automorphisms

computing sodo — 20

### Stronger refinement — nauty “invariants”

Sometimes refinement to equitable partition is insuﬃcient to separate vertices with clearly diﬀerent combinatorial properties. Those properties can be used to make the refinement stronger.

computing sodo — 21

### Stronger refinement — nauty “invariants”

Sometimes refinement to equitable partition is insuﬃcient to separate vertices with clearly diﬀerent combinatorial properties. Those properties can be used to make the refinement stronger.

For example, we can count the number of 3-cycles and 4-cycles through each vertex:

computing sodo — 21

### Stronger refinement — nauty “invariants”

Sometimes refinement to equitable partition is insuﬃcient to separate vertices with clearly diﬀerent combinatorial properties. Those properties can be used to make the refinement stronger.

For example, we can count the number of 3-cycles and 4-cycles through each vertex:

computing sodo — 21

### Stronger refinement — nauty “invariants”

For example, we can count the number of 3-cycles and 4-cycles through each vertex:

computing sodo — 21

### Example of stronger refinement performance

Consider random quartic graphs with 1000 vertices.

### • nauty

(dense data structures) 5.6 seconds### • nauty

(sparse data structures) 0.5 seconds### • nauty

(count vertices at distance 2) 0.0014 secondscomputing sodo — 22

### Example of stronger refinement performance

Consider random quartic graphs with 1000 vertices.

### • nauty

(dense data structures) 5.6 seconds### • nauty

(sparse data structures) 0.5 seconds### • nauty

(count vertices at distance 2) 0.0014 secondsThe big problem with these methods is that the best refinement technique varies from one graph class to another.

The user has to know which one to choose, which few do.

computing sodo — 22

### Tree traversal order — a Traces ^{innovation}

computing sodo — 23

### Tree traversal order — a Traces ^{innovation}

computing sodo — 23

### Tree traversal order — a Traces ^{innovation}

### Classical order: depth-first search

computing sodo — 23

### Tree traversal order — a Traces ^{innovation}

### Traces order: breadth-first search

computing sodo — 23

### Tree traversal order — a Traces ^{innovation}

### Traces order: breadth-first search

The problem with BFS is that automorphisms are discovered at leaves.

computing sodo — 23

### Tree traversal order — a Traces ^{innovation}

computing sodo — 24

### Tree traversal order — a Traces ^{innovation}

computing sodo — 24

### Tree traversal order — a Traces ^{innovation}

### Traces: experimental paths

Experimental paths allow automorphism detection during breadth-first search.

computing sodo — 24

### Refinement traces – a Traces ^{innovation}

In all programs, for almost all graphs, most of the work involves partition refinement.

However, the result of partition refinement is often thrown away because the node invariant of the resulting node is unsuitable.

computing sodo — 25

### Refinement traces – a Traces ^{innovation}

In all programs, for almost all graphs, most of the work involves partition refinement.

However, the result of partition refinement is often thrown away because the node invariant of the resulting node is unsuitable.

To alleviate this problem,

### Traces

defines the node invariant to be a vector whose components are computed incrementally during the refinement. Then the refinement can often be aborted early. (This extends a technique introduced by### bliss

.)computing sodo — 25

### Refinement traces – a Traces ^{innovation}

In all programs, for almost all graphs, most of the work involves partition refinement.

However, the result of partition refinement is often thrown away because the node invariant of the resulting node is unsuitable.

To alleviate this problem,

### Traces

defines the node invariant to be a vector whose components are computed incrementally during the refinement. Then the refinement can often be aborted early. (This extends a technique introduced by### bliss

.)Count green neighbours Initial

Count pink neighbours Count yellow neighbours

A possible trace (not

### Traces

’ trace) is the number of colours at each step: (2,3,5,6).computing sodo — 25

### Sparse automorphism detection — a saucy ^{innovation}

*x*

*w*
*v*

*y*

equitable partition

(no other blue or green)

computing sodo — 26

### Sparse automorphism detection — a saucy ^{innovation}

*x*

*w*
*v*

*y*

equitable partition

(no other blue or green)

*x*

*w*
*v*

*y*

individualize

### v

*x*

*w*
*v*

*y*

individualize

### w

computing sodo — 26

### Sparse automorphism detection — a saucy ^{innovation}

*x*

*w*
*v*

*y*

equitable partition

(no other blue or green)

*x*

*w*
*v*

*y*

individualize

### v

*x*

*w*
*v*

*y*

individualize

### w

This discovers the automorphism (

### v w

)(### x y

) without comparing leaves.computing sodo — 26

### Automorphism group handling

Programs using depth-first search naturally produce automorphisms in the form of a base and strong generating set.

Other programs, like

### Traces

, produce less predictable generators.In order to perform automorphism-based pruning of the search tree, we need to eﬃciently (usually) determine if two sequences of vertices are equivalent under the group generated by the automorphisms found so far.

computing sodo — 27

### Automorphism group handling

Programs using depth-first search naturally produce automorphisms in the form of a base and strong generating set.

Other programs, like

### Traces

, produce less predictable generators.In order to perform automorphism-based pruning of the search tree, we need to eﬃciently (usually) determine if two sequences of vertices are equivalent under the group generated by the automorphisms found so far.

### Traces

uses a technique called the random Schreier method to perform this compu- tation probabiliistically.### nauty

also uses this in circumstances where the basic group handling is insuﬃcient.computing sodo — 27

10^{1} 10^{2} 10^{3}
10^{−}^{5}

10^{−}^{4}
10^{−}^{3}
10^{−}^{2}
10^{−}^{1}

Vertices

Time(sec)(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

10^{1} 10^{2} 10^{3}

10^{−}^{5}
10^{−}^{4}
10^{−}^{3}
10^{−}^{2}
10^{−}^{1}

Vertices

Time(sec)(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 1: Random graphs with

### p

=^{1}

_{2}

computing sodo — 28

10^{2} 10^{3} 10^{4} 10^{5}
10^{−}^{4}

10^{−}^{3}
10^{−}^{2}
10^{−}^{1}
10^{0}
10^{1}

10^{2} ^{>}^{600}^{s}

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

10^{2} 10^{3} 10^{4} 10^{5}
10^{−}^{4}

10^{−}^{3}
10^{−}^{2}
10^{−}^{1}
10^{0}
10^{1}

10^{2} ^{>}^{600}^{s}

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 2: Random cubic graphs

computing sodo — 29

10^{1} 10^{2} 10^{3} 10^{4} 10^{5}
10^{−}^{5}

10^{−}^{3}
10^{−}^{1}
10^{1}

>600s

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

10^{1} 10^{2} 10^{3} 10^{4} 10^{5}
10^{−}^{5}

10^{−}^{3}
10^{−}^{1}
10^{1}

>600s

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 3: Random trees

computing sodo — 30

10^{1} 10^{2} 10^{3} 10^{4} 10^{5} 10^{6}
10^{−}^{5}

10^{−}^{3}
10^{−}^{1}

10^{1} ^{>}^{400}^{s}

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

10^{1} 10^{2} 10^{3} 10^{4} 10^{5} 10^{6}
10^{−}^{5}

10^{−}^{3}
10^{−}^{1}
10^{1}

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 4: Hypercubes

computing sodo — 31

10^{1} 10^{2} 10^{3} 10^{4}
10^{−}^{5}

10^{−}^{4}
10^{−}^{3}
10^{−}^{2}
10^{−}^{1}
10^{0}

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

10^{1} 10^{2} 10^{3} 10^{4}
10^{−}^{5}

10^{−}^{4}
10^{−}^{3}
10^{−}^{2}
10^{−}^{1}
10^{0}

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 5: Miscellaneous vertex-transitive graphs

computing sodo — 32

10^{1} 10^{2} 10^{3} 10^{4}
10^{−}^{5}

10^{−}^{4}
10^{−}^{3}
10^{−}^{2}
10^{−}^{1}
10^{0}

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

10^{1} 10^{2} 10^{3} 10^{4}

10^{−}^{5}
10^{−}^{4}
10^{−}^{3}
10^{−}^{2}
10^{−}^{1}

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 6: 2-dimensional and 3-dimensional grids

computing sodo — 33

0 200 400 600 800
10^{−}^{5}

10^{−}^{4}
10^{−}^{3}
10^{−}^{2}
10^{−}^{1}

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

0 200 400 600 800

10^{−}^{5}
10^{−}^{4}
10^{−}^{3}
10^{−}^{2}
10^{−}^{1}

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 7: Latin square graphs

computing sodo — 34

10^{1} 10^{2} 10^{3}
10^{−}^{5}

10^{−}^{4}
10^{−}^{3}
10^{−}^{2}
10^{−}^{1}
10^{0}
10^{1}

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

10^{1} 10^{2} 10^{3}

10^{−}^{5}
10^{−}^{4}
10^{−}^{3}
10^{−}^{2}
10^{−}^{1}
10^{0}
10^{1}

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 8: Strongly regular graphs

computing sodo — 35

0 200 400 600 800 1,000
10^{−}^{5}

10^{−}^{3}
10^{−}^{1}
10^{1}

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Traces 2.0

10^{1} 10^{2} 10^{3}

10^{−}^{5}
10^{−}^{4}
10^{−}^{3}
10^{−}^{2}
10^{−}^{1}
10^{0}
10^{1}
10^{2}

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 9: Hadamard matrix graphs

computing sodo — 36

10^{4} 10^{5}
10^{−}^{1}

10^{0}
10^{1}
10^{2}

>600s

Group Size

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Traces 2.0

10^{4} 10^{5}

10^{−}^{1}
10^{0}
10^{1}
10^{2}

>600s

Group Size

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 10: Projective planes of order 16

computing sodo — 37

10^{2}^{.}^{4} 10^{2}^{.}^{6} 10^{2}^{.}^{8} 10^{3} 10^{3}^{.}^{2}
10^{−}^{3}

10^{−}^{2}
10^{−}^{1}
10^{0}

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Traces 2.0

10^{2}^{.}^{4} 10^{2}^{.}^{6} 10^{2}^{.}^{8} 10^{3} 10^{3}^{.}^{2}
10^{−}^{3}

10^{−}^{2}
10^{−}^{1}
10^{0}
10^{1}

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 11: Cai-F¨urer-Immermann graphs

computing sodo — 38

10^{2} 10^{3}
10^{−}^{4}

10^{−}^{3}
10^{−}^{2}
10^{−}^{1}
10^{0}
10^{1}
10^{2}

>100s

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

10^{2} 10^{3}

10^{−}^{3}
10^{−}^{2}
10^{−}^{1}
10^{0}
10^{1}
10^{2}

>100s

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 12: Miyazaki graphs

computing sodo — 39