Comparing a large number of graphs for isomorphism

Question

I am comparing a large set of networkx graphs for isomorphism, where most of the graphs should not be isomorphic (Lets say 0-20% are isomorphic to something in the list, for example).

I have tried the following approach.

graphs = [] # A list of networkx graphs
unique = [] # A list of unique graphs

for new in graphs:
    for old in unique:
        if nx.is_isomorphic(new, old[0]):
            break
    else:
        unique.append([new])

This let me get a much faster reduced set, but I still find it too slow for ideal use. Is there some faster algorithm to handle this type of problem (comparing pairs of transitive commutative properties) or a way to extend this algorithm to a multicore setup (running on a 20 core machine).

I am already filtering these sets of data based on the number of nodes / edges, we can assume that the nx.is_isomorphic function cannot be made faster by any filtering types of operations. I also cannot change tools easily right now, so using a compiled package is not an option.

Additional Information:

Graphs tend to be roughly 16-20 nodes with 24-48 edges total, there is a lot of interconnection so each node has roughly 8 edges. Each edge is labeled as well, but there are only 2-3 types of edges ever used.

If you can think about some normalized way to represent a graph, you can compute a hash of that representation and compare hashes. — wvxvw, Oct 29 '17 at 13:42
Or even `fast_could_be_isomorphic` and `faster_could_be_isomorphic`. — Michel, Nov 01 '17 at 12:01
Even when using those functions, I have to do so many comparisons that it becomes a problem. I am looking for something entirely different to approach this problem. A way to multi thread this comes to mind, but I can't figure out how you would split up a set of data like this in a smart way. — Tristan Maxson, Nov 01 '17 at 12:08
16-20 nodes with 24-48 edges - 2 or 3 types of edges... Can you post an example of a graph? it would be helpful to understand how the set of graphs can be efficiently partitioned for processing. Thanks — Reblochon Masque, Nov 01 '17 at 12:13
You could group the graphs by certain features. Maybe group by tuple(sorted(edge counts)), and then only compare the graphs that could possibly be isomorphic. This would change your initial search from O(N^2) to O(N). — dbn, Nov 01 '17 at 18:21
I am already filtering out based on features, I am more looking for a way to do this type of thing in parallel or a paper that might point me towards something. I am starting to feel that in might not be possible to do without switching libraries mid run, networkx -> graph-tool -> networkx, but that is a non-ideal solution — Tristan Maxson, Nov 02 '17 at 08:46
Have you tried [Zen](http://zen.networkdynamics.org)? Last time I checked it was `networkx` rewritten with Cython, which gives quite a boost to all graph operations. Here are some [benchmarks](http://zen.networkdynamics.org/benchmarks/). — hoefling, Nov 02 '17 at 09:39
Are these graphs directed or normal graphs with symmetric edges? — hynekcer, Nov 02 '17 at 20:04
If you are looking at other libraries as well, you might want to also take a look at the python bindings for [igraph](http://igraph.org/), which also has an [isomorphism-checking function](http://igraph.org/c/doc/igraph-Isomorphism.html#igraph_isomorphic). — CodeSurgeon, Nov 03 '17 at 18:48
Have you tried using `could_be_isomorphic`? It basically does some more advanced filtering (degree distribution, numbers of triangles, ...) you've mentioned and can be used to rule out a lot of pairs. — Joel, Nov 04 '17 at 04:39
@dbw: Indeed. You can use many other features too (cliques, triangles, ...). I wrote an answer using this method. — Eric Duminil, Nov 08 '17 at 09:50
@Joel: Exactly. Please see [my answer](https://stackoverflow.com/questions/46999771/comparing-a-large-number-of-graphs-for-isomorphism/47176177#47176177) — Eric Duminil, Nov 08 '17 at 10:01

score 7 · Answer 1 · answered Nov 06 '17 at 04:35

Can you use nauty (http://users.cecs.anu.edu.au/~bdm/nauty/, available in linux distributions)? That has a canonical label algorithm that is fast and might work for your problem. A canonical labeling makes isomorphic graphs identical (canonization). For example using graph6 format output from a set of random graphs gives the following count of isomorphic graphs

$ cat g6.py
import networkx as nx
for i in range(100000):
    print(nx.generate_graph6(nx.fast_gnp_random_graph(4,0.2),header=False))


$ python g6.py  |nauty-labelg  |sort |uniq -c 
>A labelg
>Z 100000 graphs labelled from stdin to stdout in 0.21 sec.
   4898 C`
    167 C^
     10 C~
  26408 C?
  39392 C@
  19684 CB
   1575 CF
   1608 CJ
   1170 CN
    288 Cr
   4800 CR

Those are the 11 graphs of 4 nodes -

$ cat atlas.py 
import networkx as nx
for g in  nx.atlas.graph_atlas_g()[8:19]:
     print(nx.generate_graph6(g,header=False))
$ python atlas.py  |nauty-labelg  |sort |uniq -c 
>A labelg
>Z 11 graphs labelled from stdin to stdout in 0.00 sec.
      1 C`
      1 C^
      1 C~
      1 C?
      1 C@
      1 CB
      1 CF
      1 CJ
      1 CN
      1 Cr
      1 CR

It would be pretty easy to parallelize this approach if it runs too slow.

Eric Duminil · Accepted Answer · 2017-11-09T08:53:56.897

As others have mentioned, if you want to stay in Python + Networkx, you could use could_be_isomorphic to filter your graphs.

The problem is that this method expects 2 graphs as an input, not millions. If you compare every pair of graphs with this method, it would take an awfully long time.

Looking at the sourcecode of could_be_isomorphic, it compares degree, triangle, and number of cliques sequences for both graphs. If they're not equal, the graphs cannot be isomorphic.

You could pack this fingerprint in a function, sort your graphs according to this fingerprint and group them with itertools.groupby. There will be a huge majority of lone graphs. The few graphs that have the same fingerprints can then be checked for isomorphism.

Using a list of 100 000 random graphs:

many_graphs = [nx.fast_gnp_random_graph(random.randint(16, 22), 0.2) for _ in range(100000)]

There were only 500 fingerprints that were shared by at least 2 graphs. If you add edge types information, there will be even fewer common fingerprints.

Here's an example with 3000 graphs, each having between 10 and 14 nodes:

import networkx as nx
from itertools import groupby
import random

many_graphs = [nx.fast_gnp_random_graph(
    random.randint(10, 14), 0.3) for _ in range(3000)]


def graph_fingerprint(g):
    order = g.order()
    d = g.degree()
    t = nx.triangles(g)
    c = nx.number_of_cliques(g) 
    props = [[d[v], t[v], c[v]] for v in d]
    props.sort()
    # TODO: Add count of edge types.
    return(props)


sorted_graphs = sorted(many_graphs, key=graph_fingerprint)

for f, g in groupby(sorted_graphs, key=graph_fingerprint):
    similar_graphs = list(g)
    n = len(similar_graphs)
    if n > 1:
        print("Found %d graphs which could be isomorphic." % n)
        for i in range(n):
            for j in range(i + 1, n):
                g1, g2 = similar_graphs[i], similar_graphs[j]
                if g1 != g2 and nx.is_isomorphic(g1, g2):
                    print(" %s and %s are isomorphic!" %
                          (nx.generate_graph6(g1,header=False), nx.generate_graph6(g2,header=False)))

It finds 4 isomorphic pairs in less than 1s:

Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
 Id?OGG_C? and IaKO_@?@? are isomorphic!
Found 6 graphs which could be isomorphic.
 I?OWcGG?G and I?OCSa?@_ are isomorphic!
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
 I_uI???JG and II??QDNA? are isomorphic!
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
 IDOCCY@GG and IOGC@`dS? are isomorphic!
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.

Here are the 2 last isomorphic graphs. "IDOCCY@GG":

and "IOGC@\dS?":

Here are 2 graphs which have the same fingerprint but aren't isomorphic:

The fingerprinting could be done in parallel. Sorting and grouping would have to happen on 1 CPU, but the isomorphism check for each group could be done in distinct CPUs.

I am getting the following error `--------------------------------------------------------------------------- KeyError Traceback (most recent call last) in ----> 1 sorted_graphs = sorted(many_graphs, key=graph_fingerprint) in graph_fingerprint(g) 4 t = nx.triangles(g) 5 c = nx.number_of_cliques(g) KeyError: (0, 4) ` — BigDataScientist, Aug 15 '19 at 20:13

score 1 · Answer 3 · answered Nov 01 '17 at 20:04

You can try your code on PyPy which provides just-in-time compilation for pure Python code. For possible performance boost they say it...

...depends greatly on the type of task being performed. The geometric average of all benchmarks is 0.13 or 7.5 times faster than CPython

If your workload is CPU-bound (which seems like so) and Python process is long-running (so JIT compilation can be performed) then performance boost can be significant. NetworkX is pure Python (it has optional dependencies like numpy, but they are needed for extra functionality) and specifically isomorph module. I tried PyPy 5.7.1 and networkx/algorithms/isomorphism/tests/test_isomorphism.py passes. The the suite in general has a few failures:

Ran 2952 tests in 51.311s

FAILED (failures=3, skipped=54)
Test failed: <unittest.runner.TextTestResult run=2952 errors=0 failures=3>

On Python 2.7.12 it's:

Ran 2952 tests in 88.915s

OK (skipped=54)

I will give this a try, easier than switching to a different library but still gives performance ontop of any improvements. — Tristan Maxson, Nov 02 '17 at 08:43

Comparing a large number of graphs for isomorphism

3 Answers3