Grand Isomorphisms

Subgraph isomorphism is a resource-heavy (but branch-parallelizable) algorithm that is hugely impactful for large graph analysis. SotA algorithms for this (Ullmann, VF2, BB-Graph) are heavily RAM-bound, but this is due to a large number of small processes each of which hold a small portion of a traversal tree in memory.

Grand-Iso is a subgraph isomorphism algorithm that exchanges this resource-limitation for a parallelizable partial-match queue structure.

It performs favorably compared to other pure-python (and even some non-pure-python!) implementations:

Example Usage

from grandiso import find_motifs
import networkx as nx

host = nx.fast_gnp_random_graph(10, 0.5)

motif = nx.Graph()
motif.add_edge("A", "B")
motif.add_edge("B", "C")
motif.add_edge("C", "D")
motif.add_edge("D", "A")

len(find_motifs(motif, host))

Directed graph support:

from grandiso import find_motifs
import networkx as nx

host = nx.fast_gnp_random_graph(10, 0.5, directed=True)

motif = nx.DiGraph()
motif.add_edge("A", "B")
motif.add_edge("B", "C")
motif.add_edge("C", "D")
motif.add_edge("D", "A")

len(find_motifs(motif, host))

Counts-only

For very large graphs, you may use a good chunk of RAM not only on the queue of hypotheses, but also on the list of results. If all you care about is the NUMBER of results, you should pass count_only=True to the find_motifs function. This will dramatically reduce your RAM overhead on higher-count queries.

All Arguments to find_motifs

Using Hints

GrandIso optionally accepts an argument hints which is a list of valid partial mappings to use to seed the search. For example, in this code:

host = nx.DiGraph()
nx.add_path(host, ["A", "B", "C", "A"])
motif = nx.DiGraph()
nx.add_path(motif, ["a", "b", "c", "a"])

find_motifs(motif, host)

There are three valid mappings (because each of A, B, and C can map to a, b, or c).

We can declare that node A maps to node a or b like this:

host = nx.DiGraph()
nx.add_path(host, ["A", "B", "C", "A"])
motif = nx.DiGraph()
nx.add_path(motif, ["a", "b", "c", "a"])

find_motifs(
    motif, host,
    hints=[{"A": "a"}, {"A", "b"}]
)

Pseudocode for "Grand-Iso" algorithm

- Accept a motif M, and a host graph H.
- Create an empty list for result storage, R.
- Create an empty queue, Q.
- Preprocessing
    - Identify the most "interesting" node in motif M, m1.
    - Add to Q a set of mappings with a single node, with one map for all
        nodes in H that satisfy the requirements of m1: degree, attributes, etc
- Motif Search
    - "Pop" a backbone B from Q
        - Identify as m1 the most interesting node in motif M that does not yet
            have a mapping assigned in B.
        - Identify all nodes that are valid mappings from the backbone to m1,
            based upon degree, attributes, etc.
        - If multiple nodes are valid candidates, add each new backbone to Q.
        - Otherwise, when all nodes in M have a valid mapping in B to H, add
            the mapping to the results set R.
    - Continue while there are still backbones in Q.
- Reporting
    - Return the set R to the user.

Hacking on this repo

Running Tests

coverage run --source=grandiso -m pytest

Citing

If this tool is helpful to your research, please consider citing it with:

# https://doi.org/10.1101/2020.06.08.140533
@article{matelsky_2020_dotmotif,
    title={{DotMotif: An open-source tool for connectome subgraph isomorphism search and graph queries}},
    url={http://dx.doi.org/10.1101/2020.06.08.140533},
    DOI={10.1101/2020.06.08.140533},
    publisher={Cold Spring Harbor Laboratory},
    author={Matelsky, Jordan K. and Reilly, Elizabeth P. and Johnson, Erik C. and Stiso, Jennifer and Bassett, Danielle S. and Wester, Brock A. and Gray-Roncal, William},
    year={2020},
    month={Jun}
}