arachne/subgraph_matching_with_random_graphs_sample.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f651e065",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    _         _                   _       \n",
      "   / \\   _ __| | _____  _   _  __| | __ _ \n",
      "  / _ \\ | '__| |/ / _ \\| | | |/ _` |/ _` |\n",
      " / ___ \\| |  |   < (_) | |_| | (_| | (_| |\n",
      "/_/   \\_\\_|  |_|\\_\\___/ \\__,_|\\__,_|\\__,_|\n",
      "                                          \n",
      "\n",
      "Client Version: v2024.06.21+0.gcf6eeacde.dirty\n"
     ]
    }
   ],
   "source": [
    "import arkouda as ak\n",
    "import arachne as ar\n",
    "import scipy as sp\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "import os"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "671cb378",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "connected to arkouda server tcp://*:5555\n"
     ]
    }
   ],
   "source": [
    "# NOTE: Make sure to change the server name to whatever is applicable in your environment. If running locally, then use only ak.connect().\n",
    "ak.connect(\"n28\", 5555)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e0ab4242",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 100\n",
    "m = 1000\n",
    "s = 2\n",
    "x = 2\n",
    "y = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "36d90c88",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Building property graph with 100 vertices and 949 edges took 3.51 seconds.\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "### Build graph from randomly generated source and destination arrays.\n",
    "# 1. Use Arkouda's randint to generate the random edge arrays.\n",
    "src = ak.randint(0, n, m, seed=s*2)\n",
    "dst = ak.randint(0, n, m, seed=s*4)\n",
    "\n",
    "# 2. Build temporary property graph to get sorted edges and nodes lists.\n",
    "temp_prop_graph = ar.PropGraph()\n",
    "start = time.time()\n",
    "temp_prop_graph.add_edges_from(src, dst)\n",
    "end = time.time()\n",
    "build_time = end - start\n",
    "print(f\"Building property graph with {len(temp_prop_graph)} vertices and \"\n",
    "        f\"{temp_prop_graph.size()} \"\n",
    "        f\"edges took {round(build_time,2)} seconds.\")\n",
    "\n",
    "### Generate node labels and edge relationships for the graph.\n",
    "# 1. Extract node and edge information.\n",
    "num_edges = temp_prop_graph.size()\n",
    "num_nodes = len(temp_prop_graph)\n",
    "edges = temp_prop_graph.edges()\n",
    "nodes = temp_prop_graph.nodes()\n",
    "\n",
    "# 2. Generate random integer attributes.\n",
    "node_labels_1 = ak.randint(1, x+1, num_nodes)\n",
    "node_labels_2 = ak.randint(1, x+1, num_nodes)\n",
    "edge_rels_1 = ak.randint(1, y+1, num_edges)\n",
    "edge_rels_2 = ak.randint(1, y+1, num_edges)\n",
    "\n",
    "# 3. Create dataframe to load into a new property graph.\n",
    "edge_df = ak.DataFrame({\"src\":edges[0], \"dst\":edges[1], \"rels1\":edge_rels_1, \"rels2\":edge_rels_2})\n",
    "node_df = ak.DataFrame({\"nodes\":nodes, \"lbls1\":node_labels_1, \"lbls2\":node_labels_2})\n",
    "\n",
    "# 4. Create new property graph with node labels and edge relationships.\n",
    "prop_graph = ar.PropGraph()\n",
    "prop_graph.load_edge_attributes(edge_df, source_column=\"src\", destination_column=\"dst\",\n",
    "                                relationship_columns=[\"rels1\", \"rels2\"])\n",
    "prop_graph.load_node_attributes(node_df, node_column=\"nodes\", label_columns=[\"lbls1\", \"lbls2\"])\n",
    "\n",
    "### Create the subgraph we are searching for.\n",
    "# 1. Create labels and relationships to search for.\n",
    "src_list = [0, 1, 2, 2, 3]\n",
    "dst_list = [1, 2, 0, 3, 0]\n",
    "src_subgraph = ak.array(src_list)\n",
    "dst_subgraph = ak.array(dst_list)\n",
    "\n",
    "subgraph_nodes = list(set(src_list) | set(dst_list))\n",
    "subgraph_nodes.sort()\n",
    "\n",
    "labels1_subgraph = ak.array([1, 1, 1, 1])\n",
    "labels2_subgraph = ak.array([2, 2, 2, 2])\n",
    "rels1_subgraph = ak.array([1, 1, 1, 1, 1])\n",
    "rels2_subgraph = ak.array([2, 2, 2, 2, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d176e508",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We found 218.0 isos inside of the graph\n"
     ]
    }
   ],
   "source": [
    "\"\"\"TEST VERTEX PICKER\"\"\"\n",
    "subgraph = ar.PropGraph()\n",
    "edge_df_h = ak.DataFrame({\"src\":src_subgraph, \"dst\":dst_subgraph})\n",
    "node_df_h = ak.DataFrame({\"nodes\": ak.array(subgraph_nodes), \"lbls1\":labels1_subgraph,\n",
    "                          \"lbls2\":labels2_subgraph})\n",
    "subgraph.load_edge_attributes(edge_df_h, source_column=\"src\", destination_column=\"dst\")\n",
    "subgraph.load_node_attributes(node_df_h, node_column = \"nodes\", \n",
    "                                label_columns = [\"lbls1\",\"lbls2\"])\n",
    "\n",
    "isos_as_vertices = ar.subgraph_isomorphism(prop_graph, subgraph, \n",
    "                                           semantic_check=\"or\", algorithm_type=\"si\", return_isos_as=\"vertices\"\n",
    ")\n",
    "print(f\"We found {len(isos_as_vertices[0])/len(subgraph)} isos inside of the graph\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "f4c138bc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We found 169.0 isos inside of the graph\n"
     ]
    }
   ],
   "source": [
    "\"\"\"TEST EDGE PICKER\"\"\"\n",
    "subgraph = ar.PropGraph()\n",
    "edge_df_h = ak.DataFrame({\"src\":src_subgraph, \"dst\":dst_subgraph,\n",
    "                        \"rels1\":rels1_subgraph, \"rels2\":rels2_subgraph})\n",
    "subgraph.load_edge_attributes(edge_df_h, source_column=\"src\", destination_column=\"dst\",\n",
    "                                relationship_columns=[\"rels1\",\"rels2\"])\n",
    "\n",
    "isos_as_vertices = ar.subgraph_isomorphism(prop_graph, subgraph, \n",
    "                                           semantic_check=\"or\", algorithm_type=\"si\", return_isos_as=\"vertices\"\n",
    ")\n",
    "print(f\"We found {len(isos_as_vertices[0])/len(subgraph)} isos inside of the graph\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "36aa6159",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We found 71.0 isos inside of the graph\n"
     ]
    }
   ],
   "source": [
    "\"\"\"TEST COMBINED PICKER\"\"\"\n",
    "subgraph = ar.PropGraph()\n",
    "edge_df_h = ak.DataFrame({\"src\":src_subgraph, \"dst\":dst_subgraph,\n",
    "                        \"rels1\":rels1_subgraph, \"rels2\":rels2_subgraph})\n",
    "node_df_h = ak.DataFrame({\"nodes\": ak.array(subgraph_nodes), \"lbls1\":labels1_subgraph,\n",
    "                          \"lbls2\":labels2_subgraph})\n",
    "subgraph.load_edge_attributes(edge_df_h, source_column=\"src\", destination_column=\"dst\",\n",
    "                                relationship_columns=[\"rels1\",\"rels2\"])\n",
    "subgraph.load_node_attributes(node_df_h, node_column = \"nodes\", \n",
    "                                label_columns=[\"lbls1\",\"lbls2\"])\n",
    "\n",
    "isos_as_vertices = ar.subgraph_isomorphism(prop_graph, subgraph, \n",
    "                                           semantic_check=\"or\", algorithm_type=\"si\", return_isos_as=\"vertices\"\n",
    ")\n",
    "print(f\"We found {len(isos_as_vertices[0])/len(subgraph)} isos inside of the graph\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "9e49df46",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We found 670.0 isos inside of the graph\n"
     ]
    }
   ],
   "source": [
    "\"\"\"TEST NO PICKER\"\"\"\n",
    "subgraph = ar.PropGraph()\n",
    "edge_df_h = ak.DataFrame({\"src\":src_subgraph, \"dst\":dst_subgraph})\n",
    "subgraph.load_edge_attributes(edge_df_h, source_column=\"src\", destination_column=\"dst\")\n",
    "\n",
    "isos_as_vertices = ar.subgraph_isomorphism(prop_graph, subgraph, \n",
    "                                           semantic_check=\"or\", algorithm_type=\"si\", return_isos_as=\"vertices\"\n",
    ")\n",
    "print(f\"We found {len(isos_as_vertices[0])/len(subgraph)} isos inside of the graph\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "f2ab4c8a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We found 218.0 isos inside of the graph\n"
     ]
    }
   ],
   "source": [
    "\"\"\"VF2-PS VERTEX PICKER GROUND TRUTH\"\"\"\n",
    "subgraph = ar.PropGraph()\n",
    "edge_df_h = ak.DataFrame({\"src\":src_subgraph, \"dst\":dst_subgraph})\n",
    "node_df_h = ak.DataFrame({\"nodes\": ak.array(subgraph_nodes), \"lbls1\":labels1_subgraph,\n",
    "                          \"lbls2\":labels2_subgraph})\n",
    "subgraph.load_edge_attributes(edge_df_h, source_column=\"src\", destination_column=\"dst\")\n",
    "subgraph.load_node_attributes(node_df_h, node_column = \"nodes\", \n",
    "                                label_columns = [\"lbls1\",\"lbls2\"])\n",
    "\n",
    "isos_as_vertices = ar.subgraph_isomorphism(prop_graph, subgraph, \n",
    "                                           semantic_check=\"or\", algorithm_type=\"ps\", return_isos_as=\"vertices\"\n",
    ")\n",
    "print(f\"We found {len(isos_as_vertices[0])/len(subgraph)} isos inside of the graph\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "487c288b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We found 169.0 isos inside of the graph\n"
     ]
    }
   ],
   "source": [
    "\"\"\"VF2-PS EDGE PICKER GROUND TRUTH\"\"\"\n",
    "subgraph = ar.PropGraph()\n",
    "edge_df_h = ak.DataFrame({\"src\":src_subgraph, \"dst\":dst_subgraph,\n",
    "                        \"rels1\":rels1_subgraph, \"rels2\":rels2_subgraph})\n",
    "subgraph.load_edge_attributes(edge_df_h, source_column=\"src\", destination_column=\"dst\",\n",
    "                                relationship_columns=[\"rels1\",\"rels2\"])\n",
    "\n",
    "isos_as_vertices = ar.subgraph_isomorphism(prop_graph, subgraph, \n",
    "                                           semantic_check=\"or\", algorithm_type=\"ps\", return_isos_as=\"vertices\"\n",
    ")\n",
    "print(f\"We found {len(isos_as_vertices[0])/len(subgraph)} isos inside of the graph\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "2940d068",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We found 71.0 isos inside of the graph\n"
     ]
    }
   ],
   "source": [
    "\"\"\"VF2-PS COMBINED GROUND TRUTH\"\"\"\n",
    "subgraph = ar.PropGraph()\n",
    "edge_df_h = ak.DataFrame({\"src\":src_subgraph, \"dst\":dst_subgraph,\n",
    "                        \"rels1\":rels1_subgraph, \"rels2\":rels2_subgraph})\n",
    "node_df_h = ak.DataFrame({\"nodes\": ak.array(subgraph_nodes), \"lbls1\":labels1_subgraph,\n",
    "                          \"lbls2\":labels2_subgraph})\n",
    "subgraph.load_edge_attributes(edge_df_h, source_column=\"src\", destination_column=\"dst\",\n",
    "                                relationship_columns=[\"rels1\",\"rels2\"])\n",
    "subgraph.load_node_attributes(node_df_h, node_column = \"nodes\", \n",
    "                                label_columns=[\"lbls1\",\"lbls2\"])\n",
    "\n",
    "isos_as_vertices = ar.subgraph_isomorphism(prop_graph, subgraph, \n",
    "                                           semantic_check=\"or\", algorithm_type=\"ps\", return_isos_as=\"vertices\"\n",
    ")\n",
    "print(f\"We found {len(isos_as_vertices[0])/len(subgraph)} isos inside of the graph\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "842b82a8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We found 670.0 isos inside of the graph\n"
     ]
    }
   ],
   "source": [
    "\"\"\"VF2-PS NO ATTRIBUTES GROUND TRUTH\"\"\"\n",
    "subgraph = ar.PropGraph()\n",
    "edge_df_h = ak.DataFrame({\"src\":src_subgraph, \"dst\":dst_subgraph})\n",
    "subgraph.load_edge_attributes(edge_df_h, source_column=\"src\", destination_column=\"dst\")\n",
    "\n",
    "isos_as_vertices = ar.subgraph_isomorphism(prop_graph, subgraph, \n",
    "                                           semantic_check=\"or\", algorithm_type=\"ps\", return_isos_as=\"vertices\"\n",
    ")\n",
    "print(f\"We found {len(isos_as_vertices[0])/len(subgraph)} isos inside of the graph\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "arkouda-dev",
   "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.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}