Monomorphisms vs Isomorphisms: Three Search Approaches in Python

Monomorphisms-and-Isomorphisms-In-Python.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip3 install networkx grandiso dotmotif"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Three Ways of Searching for Subgraph Motifs\n",
    "\n",
    "A comparison of three different ways to search for subgraph motifs.\n",
    "\n",
    "1. [DotMotif](https://github.com/aplbrain/dotmotif):  A visual motif design system. Possible to search in a variety of different graph types.\n",
    "2. NetworkX, built-in. Very slow and memory-hungry compared to alternatives, but built right into the library you're already using.\n",
    "3. [GrandIso](https://github.com/aplbrain/grandiso-networkx): A drop-in replacement for the NetworkX isomorphism algorithms. Dramatically faster than Nx, but still uses NetworkX graphs. This is what goes on behind the scenes in DotMotif."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Setup:\n",
    "\n",
    "import networkx as nx\n",
    "\n",
    "g = nx.fast_gnp_random_graph(100, .050)\n",
    "motif_graph = nx.path_graph(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1: Using DotMotif\n",
    "\n",
    "We use `Executor#count` here instead of `Executor#find` to save on memory."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dotmotif import Motif, GrandIsoExecutor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "E = GrandIsoExecutor(graph=g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Monomorphisms:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2588"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E.count(Motif(\n",
    "\"\"\"\n",
    "A -> B\n",
    "B -> C\n",
    "\"\"\", ignore_direction=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Isomorphisms:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2474"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E.count(Motif(\n",
    "\"\"\"\n",
    "A -> B\n",
    "B -> C\n",
    "\n",
    "A !> C\n",
    "C !> A\n",
    "\"\"\", ignore_direction=True, exclude_automorphisms=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2: Using NetworkX (Slow!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "gm = nx.isomorphism.GraphMatcher(g, motif_graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Monomorphisms:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2588"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len([i for i in gm.subgraph_monomorphisms_iter()])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Isomorphisms:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2474"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len([i for i in gm.subgraph_isomorphisms_iter()])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3: Using GrandIso\n",
    "\n",
    "We use `count_only=True` here to further reduce the memory cost of running the algorithm. Leaving it out will return a mapping, just like NetworkX or GrandIso does."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "from grandiso import find_motifs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Monomorphisms:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2588"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_motifs(motif_graph, g, count_only=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Isomorphisms:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2474"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_motifs(motif_graph, g, count_only=True, isomorphisms_only=True)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}