Computing SODO

(1)

Computing SODO

Brendan McKay

Australian National University

Adolfo Piperno University of Rome

computing sodo — 1

(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.

(3)

Isomorphism and Automorphism

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

(4)

Isomorphism and Automorphism

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)

(5)

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.

(6)

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.

(7)

Hadamard equivalence



 

1 − ¹ ¹ 1 − ¹ ¹

− ¹ − ¹ ¹



 

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

(8)

Hadamard equivalence



 

1 − ¹ ¹ 1 − ¹ ¹

− ¹ − ¹ ¹



 

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

(9)

Isotopy



 

1 3 2 2 1 3 3 2 1



 

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

(10)

Isotopy

1 2

3 1

2

3

1 3 2

Row

Column

Symbol



 

1 3 2 2 1 3 3 2 1



 

(11)

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



 

(12)

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



 



(13)

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.

(14)

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ⁿ⁾.

(15)

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



 



(16)

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.

(17)

Isomorphism and automorphism are much the same

(18)

Isomorphism and automorphism are much the same

G H

(19)

Isomorphism and automorphism are much the same

G H H G

(20)

Isomorphism and automorphism are much the same

G H H G

(21)

Isomorphism and automorphism are much the same

G H H G

(22)

Isomorphism and automorphism are much the same

G H H G

(23)

Isomorphism and automorphism are much the same

G H H G

(24)

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.

(25)

Minor-closed classes

(26)

Minor-closed classes

(27)

Minor-closed classes

C

4

as a minor

(28)

Minor-closed classes

C

4

as a topological minor

(29)

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.

(30)

Problems

1. Prove any of these inequalities are equalities:

P

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

(31)

Problems

P

2. Improve

n

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

(32)

Problems

P

2. Improve

n

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

(33)

Problems

P

2. Improve

n

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

(34)

Problems

P

2. Improve

n

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

5. Improve the exp(

O

(√

n

log

n

)) worst case for graph isomorphism.

(35)

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”.

(36)

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.

(37)

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.

(38)

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 graphs

Many similar principles appear in these programs.

saucy

^and

bliss

began life as reimplementations of

nauty

but have since diverged.

(39)

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:

(40)

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.

(41)

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

(42)

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.

(43)

Search tree

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

(44)

Search tree

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.

(45)

Search tree

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.

(46)

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

(47)

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

ν

₁^� is a descendant of

ν

1, and

ν

₂^� is a descendant of

ν

2, then

φ

(

ν

1)

< φ

(

ν

2) =⇒

φ

(

ν

₁^�)

< φ

(

ν

₂^�)

.

(48)

Node invariants

φ

(

ν

Let

ν

1

, ν

ν

1, and

ν

2, then

φ

(

ν

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.

(49)

Node invariants

φ

(

ν

Let

ν

1

, ν

ν

1, and

ν

2, then

φ

(

ν

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.

(50)

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

, ν

φ

(

ν

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 =

ν

₁^g for an automorphism

g

, then

g

maps the subtree

descended from

ν

1 onto the subtree descended from

ν

2.

(51)

Pruning operations

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

1. If

ν

1

, ν

φ

(

ν

1)

< φ

(

ν

2), then no canonical labelling is descended from

ν

1.

2. If

ν

1

, ν

φ

(

ν

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 =

ν

₁^g for an automorphism

g

, then

g

maps the subtree

descended 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.

(52)

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

(53)

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.

(54)

Stronger refinement — nauty “invariants”

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

(55)

Stronger refinement — nauty “invariants”

(56)

Stronger refinement — nauty “invariants”

(57)

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 seconds

(58)

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 seconds

The 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.

(59)

Tree traversal order — a Traces ^innovation

(60)

Tree traversal order — a Traces ^innovation

(61)

Tree traversal order — a Traces ^innovation

Classical order: depth-first search

(62)

Tree traversal order — a Traces ^innovation

Traces order: breadth-first search

(63)

Tree traversal order — a Traces ^innovation

Traces order: breadth-first search

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

(64)

Tree traversal order — a Traces ^innovation

(65)

Tree traversal order — a Traces ^innovation

(66)

Tree traversal order — a Traces ^innovation

Traces: experimental paths

Experimental paths allow automorphism detection during breadth-first search.

(67)

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.

(68)

Refinement traces – a Traces ^innovation

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

.)

(69)

Refinement traces – a Traces ^innovation

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).

(70)

Sparse automorphism detection — a saucy ^innovation

x

w v

y

equitable partition

(no other blue or green)

(71)

Sparse automorphism detection — a saucy ^innovation

x

w v

y

equitable partition

x

w v

y

individualize

v

x

w v

y

individualize

w

(72)

Sparse automorphism detection — a saucy ^innovation

x

w v

y

equitable partition

x

w v

y

individualize

v

x

w v

y

individualize

w

This discovers the automorphism (

v w

)(

x y

) without comparing leaves.

(73)

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.

(74)

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.

(75)

10¹ 10² 10³ 10⁻⁵

10⁻⁴ 10⁻³ 10⁻² 10⁻¹

Vertices

Time(sec)(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

10¹ 10² 10³

10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹

Vertices

Time(sec)(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 1: Random graphs with

p

= ¹₂

(76)

10² 10³ 10⁴ 10⁵ 10⁻⁴

10⁻³ 10⁻² 10⁻¹ 10⁰ 10¹

10² ^>⁶⁰⁰^s

Vertices

Time(sec)

Automorphism group

10² 10³ 10⁴ 10⁵ 10⁻⁴

10⁻³ 10⁻² 10⁻¹ 10⁰ 10¹

10² ^>⁶⁰⁰^s

Vertices

Time(sec)

Canonical label

Figure 2: Random cubic graphs

(77)

10¹ 10² 10³ 10⁴ 10⁵ 10⁻⁵

10⁻³ 10⁻¹ 10¹

>600s

Vertices

Time(sec)

Automorphism group

10¹ 10² 10³ 10⁴ 10⁵ 10⁻⁵

10⁻³ 10⁻¹ 10¹

>600s

Vertices

Time(sec)

Canonical label

Figure 3: Random trees

(78)

10¹ 10² 10³ 10⁴ 10⁵ 10⁶ 10⁻⁵

10⁻³ 10⁻¹

10¹ ^>⁴⁰⁰^s

Vertices

Time(sec)

Automorphism group

10¹ 10² 10³ 10⁴ 10⁵ 10⁶ 10⁻⁵

10⁻³ 10⁻¹ 10¹

Vertices

Time(sec)

Canonical label

Figure 4: Hypercubes

(79)

10¹ 10² 10³ 10⁴ 10⁻⁵

10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰

Vertices

Time(sec)

Automorphism group

10¹ 10² 10³ 10⁴ 10⁻⁵

10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰

Vertices

Time(sec)

Canonical label

Figure 5: Miscellaneous vertex-transitive graphs

(80)

10¹ 10² 10³ 10⁴ 10⁻⁵

10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰

Vertices

Time(sec)

Automorphism group

10¹ 10² 10³ 10⁴

10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹

Vertices

Time(sec)

Canonical label

Figure 6: 2-dimensional and 3-dimensional grids

(81)

0 200 400 600 800 10⁻⁵

10⁻⁴ 10⁻³ 10⁻² 10⁻¹

Vertices

Time(sec)

Automorphism group

0 200 400 600 800

10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹

Vertices

Time(sec)

Canonical label

Figure 7: Latin square graphs

(82)

10¹ 10² 10³ 10⁻⁵

10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰ 10¹

Vertices

Time(sec)

Automorphism group

10¹ 10² 10³

10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰ 10¹

Vertices

Time(sec)

Canonical label

Figure 8: Strongly regular graphs

(83)

0 200 400 600 800 1,000 10⁻⁵

10⁻³ 10⁻¹ 10¹

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Traces 2.0

10¹ 10² 10³

10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰ 10¹ 10²

Vertices

Time(sec)

Canonical label

Figure 9: Hadamard matrix graphs

(84)

10⁴ 10⁵ 10⁻¹

10⁰ 10¹ 10²

>600s

Group Size

Time(sec)

Automorphism group

10⁴ 10⁵

10⁻¹ 10⁰ 10¹ 10²

>600s

Group Size

Time(sec)

Canonical label

Figure 10: Projective planes of order 16

(85)

10²^.⁴ 10²^.⁶ 10²^.⁸ 10³ 10³^.² 10⁻³

10⁻² 10⁻¹ 10⁰

Vertices

Time(sec)

Automorphism group

10²^.⁴ 10²^.⁶ 10²^.⁸ 10³ 10³^.² 10⁻³

10⁻² 10⁻¹ 10⁰ 10¹

Vertices

Time(sec)

Canonical label

Figure 11: Cai-F¨urer-Immermann graphs

(86)

10² 10³ 10⁻⁴

10⁻³ 10⁻² 10⁻¹ 10⁰ 10¹ 10²

>100s

Vertices

Time(sec)

Automorphism group

10² 10³

10⁻³ 10⁻² 10⁻¹ 10⁰ 10¹ 10²

>100s

Vertices

Time(sec)

Canonical label

Figure 12: Miyazaki graphs

Computing SODO

Computing SODO

Brendan McKay

Australian National University

Adolfo Piperno University of Rome

Isomorphism and Automorphism

Isomorphism and Automorphism

Isomorphism and Automorphism

Ubiquity of graph isomorphism



 

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



 

Ubiquity of graph isomorphism



 

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



 

Hadamard equivalence



 

1 − 1 1 1 − 1 1

− 1 − 1 1



 

Hadamard equivalence



 

1 − 1 1 1 − 1 1

− 1 − 1 1



 

Isotopy



 

1 3 2 2 1 3 3 2 1



 

Isotopy

Row

Column

Symbol



 

1 3 2 2 1 3 3 2 1



 

Isotopy

Row

Column

Symbol

Row

Column

Symbol



 

1 3 2 2 1 3 3 2 1



 

Group isomorphism



 

 



e g

g

g

g

e g

g

g

g

e g

g

g

g

e



1 − ¹ ¹ 1 − ¹ ¹

− ¹ − ¹ ¹

1 − ¹ ¹ 1 − ¹ ¹

− ¹ − ¹ ¹