Eliminating symmetry from graphs

Question

I have an algorithmic problem in which I have derived a transfer matrix between a lot of states. The next step is to exponentiate it, but it is very large, so I need to do some reductions on it. Specifically it contains a lot of symmetry. Below are some examples on how many nodes can be eliminated by simple observations.

My question is whether there is an algorithm to efficiently eliminate symmetry in digraphs, similarly to the way I've done it manually below.

In all cases the initial vector has the same value for all nodes.

---

In the first example we see that b, c, d and e all receive values from a and one of each other. Hence they will always contain an identical value, and we can merge them.

---

In this example we quickly spot, that the graph is identical from the point of view of a, b, c and d. Also for their respective sidenodes, it doesn't matter to which inner node it is attached. Hence we can reduce the graph down to only two states.

---

Update: Some people were reasonable enough not quite sure what was meant by "State transfer matrix". The idea here is, that you can split a combinatorial problem up into a number of state types for each n in your recurrence. The matrix then tell you how to get from n-1 to n.

Usually you are only interested about the value of one of your states, but you need to calculate the others as well, so you can always get to the next level. In some cases however, multiple states are symmetrical, meaning they will always have the same value. Obviously it's quite a waste to calculate all of these, so we want to reduce the graph until all nodes are "unique".

Below is an example of the transfer matrix for the reduced graph in example 1.

[S_a(n)]   [1  1  1] [S_a(n-1)]
[S_f(n)] = [1  0  0]*[S_f(n-1)]
[S_B(n)]   [4  0  1] [S_B(n-1)]

---

Any suggestions or references to papers are appreciated.

Answer 1

Brendan McKay's nauty ( http://cs.anu.edu.au/~bdm/nauty/) is the best tool I know of for computing automorphisms of graphs. It may be too expensive to compute the whole automorphism group of your graph, but you might be able to reuse some of the algorithms described in McKay's paper "Practical Graph Isomorphism" (linked from the nauty page).

Answer 2

I'll just add an extra answer building on what userOVER9000 suggested, if anybody else are interested. The below is an example of using nauty on Example 2, through the dreadnaut tool.

$ ./dreadnaut 
Dreadnaut version 2.4 (64 bits).
> n=8 d g                                     -- Starting a new 8-node digraph
 0 : 1 3 4;                                   -- Entering edge data
 1 : 0 2 5;
 2 : 3 1 6;
 3 : 0 2 7;
 4 : 0;
 5 : 1;
 6 : 2;
 7 : 3;
> cx                                          -- Calling nauty
(1 3)(5 7)
level 2:  6 orbits; 5 fixed; index 2
(0 1)(2 3)(4 5)(6 7)
level 1:  2 orbits; 4 fixed; index 4
2 orbits; grpsize=8; 2 gens; 6 nodes; maxlev=3
tctotal=8; canupdates=1; cpu time = 0.00 seconds
> o                                           -- Output "orbits"
 0:3; 4:7;

Notice it suggests joining nodes 0:3 which are a:d in Example 2 and 4:7 which are e:h.

The nauty algorithm is not well documented, but the authors describe it as exponential worst case, n^2 average.

Answer 3

Computing symmetries seems to be a bit of a second order problem. Taking just a,b,c and d in your second graph, the symmetry would have to be expressed

a(b,c,d) = b(a,d,c)

and all its permutations, or some such. Consider a second subgraph a', b', c', d' added to it. Again, we have the symmetries, but parameterised differently.

For computing people (rather than math people), could we express the problem like so?

Each graph node contains a set of letters. At each iteration, all of the letters in each node are copied to its neighbours by the arrows (some arrows take more than one iteration and can be treated as a pipe of anonymous nodes).

We are trying to find efficient ways of determining things such as * what letters each set/node contains after N iterations. * for each node the N after which its set no longer changes. * what sets of nodes wind up containing the same sets of letters (equivalence class)

?