ISMAGS Algorithm#

Provides a Python implementation of the ISMAGS algorithm. [1]

ISMAGS does a symmetry analysis to find the constraints on isomorphisms if we preclude yielding isomorphisms that differ by a symmetry of the subgraph. For example, if the subgraph contains a 4-cycle, every isomorphism would have a symmetric version with the nodes rotated relative to the original isomorphism. By encoding these symmetries as constraints we reduce the search space for isomorphisms and we also simplify processing the resulting isomorphisms.

ISMAGS finds (subgraph) isomorphisms between two graphs, taking the symmetry of the subgraph into account. In most cases the VF2 algorithm is faster (at least on small graphs) than this implementation, but in some cases there are an exponential number of isomorphisms that are symmetrically equivalent. In that case, the ISMAGS algorithm will provide only one isomorphism per symmetry group, speeding up finding isomorphisms and avoiding the task of post-processing many effectively identical isomorphisms.

>>> petersen = nx.petersen_graph()
>>> ismags = nx.isomorphism.ISMAGS(petersen, petersen)
>>> isomorphisms = list(ismags.isomorphisms_iter(symmetry=False))
>>> len(isomorphisms)
120
>>> isomorphisms = list(ismags.isomorphisms_iter(symmetry=True))
>>> answer = [{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9}]
>>> answer == isomorphisms
True

In addition, this implementation also provides an interface to find the largest common induced subgraph [2] between any two graphs, again taking symmetry into account. Given graph and subgraph the algorithm will remove nodes from the subgraph until subgraph is isomorphic to a subgraph of graph. Since only the symmetry of subgraph is taken into account it is worth thinking about how you provide your graphs:

>>> graph1 = nx.path_graph(4)
>>> graph2 = nx.star_graph(3)
>>> ismags = nx.isomorphism.ISMAGS(graph1, graph2)
>>> ismags.is_isomorphic()
False
>>> largest_common_subgraph = list(ismags.largest_common_subgraph())
>>> answer = [{1: 0, 0: 1, 2: 2}, {2: 0, 1: 1, 3: 2}]
>>> answer == largest_common_subgraph
True
>>> ismags2 = nx.isomorphism.ISMAGS(graph2, graph1)
>>> largest_common_subgraph = list(ismags2.largest_common_subgraph())
>>> answer = [
...     {1: 0, 0: 1, 2: 2},
...     {1: 0, 0: 1, 3: 2},
...     {2: 0, 0: 1, 1: 2},
...     {2: 0, 0: 1, 3: 2},
...     {3: 0, 0: 1, 1: 2},
...     {3: 0, 0: 1, 2: 2},
... ]
>>> answer == largest_common_subgraph
True

However, when not taking symmetry into account, it doesn’t matter:

>>> largest_common_subgraph = list(ismags.largest_common_subgraph(symmetry=False))
>>> answer = [
...     {1: 0, 0: 1, 2: 2},
...     {1: 0, 2: 1, 0: 2},
...     {2: 0, 1: 1, 3: 2},
...     {2: 0, 3: 1, 1: 2},
...     {1: 0, 0: 1, 2: 3},
...     {1: 0, 2: 1, 0: 3},
...     {2: 0, 1: 1, 3: 3},
...     {2: 0, 3: 1, 1: 3},
...     {1: 0, 0: 2, 2: 3},
...     {1: 0, 2: 2, 0: 3},
...     {2: 0, 1: 2, 3: 3},
...     {2: 0, 3: 2, 1: 3},
... ]
>>> answer == largest_common_subgraph
True
>>> largest_common_subgraph = list(ismags2.largest_common_subgraph(symmetry=False))
>>> answer = [
...     {1: 0, 0: 1, 2: 2},
...     {1: 0, 0: 1, 3: 2},
...     {2: 0, 0: 1, 1: 2},
...     {2: 0, 0: 1, 3: 2},
...     {3: 0, 0: 1, 1: 2},
...     {3: 0, 0: 1, 2: 2},
...     {1: 1, 0: 2, 2: 3},
...     {1: 1, 0: 2, 3: 3},
...     {2: 1, 0: 2, 1: 3},
...     {2: 1, 0: 2, 3: 3},
...     {3: 1, 0: 2, 1: 3},
...     {3: 1, 0: 2, 2: 3},
... ]
>>> answer == largest_common_subgraph
True

Notes#

  • Node and edge equality is assumed to be transitive: if A is equal to B, and B is equal to C, then A is equal to C.

  • With a method that yields subgraph isomorphisms, we can construct functions like is_subgraph_isomorphic by checking for any yielded mapping. And functions like is_isomorphic by checking whether the subgraph has the same number of nodes as the graph and is also subgraph isomorphic. This subpackage also allows a symmetry bool keyword argument so you can find isomorphisms with or without the symmetry constraints.

  • For more information, see [2] and the documentation for ISMAGS which includes a description of the algorithm.

References#

[1]

M. Houbraken, S. Demeyer, T. Michoel, P. Audenaert, D. Colle, M. Pickavet, “The Index-Based Subgraph Matching Algorithm with General Symmetries (ISMAGS): Exploiting Symmetry for Faster Subgraph Enumeration”, PLoS One 9(5): e97896, 2014. https://doi.org/10.1371/journal.pone.0097896

ISMAGS object#

ISMAGS(graph, subgraph[, node_match, ...])

Implements the ISMAGS subgraph matching algorithm.