cugraph/Weighted-Jaccard.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Weighted Jaccard Similarity\n",
    "\n",
    "In this notebook, we will use cuGraph to compute the Weighted Jaccard Similarity metric on our training dataset. \n",
    "\n",
    "\n",
    "Notebook Credits\n",
    "* Original Authors: Bradley Rees and James Wyles\n",
    "* Last Edit: 08/13/2019\n",
    "\n",
    "RAPIDS Versions: 0.9.0  \n",
    "\n",
    "\n",
    "Test Hardware\n",
    "* GV100 32G, CUDA 10.0\n",
    "\n",
    "\n",
    "## Introduction\n",
    "Weighted Jaccard is similar to the Jaccard Similarity but takes into account vertex weights placed.  \n",
    "\n",
    "\n",
    "given:\n",
    "The neighbors of a vertex, v, is defined as the set, U, of vertices connected by way of an edge to vertex v, or N(v) = {U} where v ∈V and ∀ u∈U ∃ edge(v,u)∈E.\n",
    "and\n",
    "wt(i) is the weight on vertex i\n",
    "   \n",
    "we can now define weight summing function as<br>\n",
    "$WT(U) = \\sum_{v \\in U} {wt(v)}$\n",
    "\n",
    "$WtJaccard(i, j) = \\frac{WT(N(i) \\cap N(j))}{WT(N(i) \\cup N(j))}$\n",
    "\n",
    "\n",
    "To compute the weighted Jaccard similarity between each pair of vertices connected by an edge in cuGraph use:<br>\n",
    "\n",
    "**jaccard_w(input_graph, vect_weights_ptr)**\n",
    "\n",
    "Input\n",
    "* input_graph: A cugraph.Graph object\n",
    "* vect_weights_ptr: An array of vertex weights\n",
    "\n",
    "Returns: \n",
    "* __df__: cudf.DataFrame with three columns:\n",
    "    * df['source']: The source vertex id.\n",
    "    * df['destination']: The destination vertex id.\n",
    "    * df['jaccard_coeff']: The weighted jaccard coefficient computed between the source and destination vertex.\n",
    " \n",
    "\n",
    "__Note:__ For this example we will be using PageRank as the edge weights.  Please review the PageRank notebook if you have any questions about running PageRank\n",
    "\n",
    "\n",
    "## cuGraph Notice \n",
    "The current version of cuGraph has some limitations:\n",
    "\n",
    "* Vertex IDs need to be 32-bit integers.\n",
    "* Vertex IDs are expected to be contiguous integers starting from 0.\n",
    "\n",
    "cuGraph provides the renumber function to mitigate this problem. Input vertex IDs for the renumber function can be either 32-bit or 64-bit integers, can be non-contiguous, and can start from an arbitrary number. The renumber function maps the provided input vertex IDs to 32-bit contiguous integers starting from 0. cuGraph still requires the renumbered vertex IDs to be representable in 32-bit integers. These limitations are being addressed and will be fixed soon."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Data\n",
    "We will be using the Zachary Karate club dataset \n",
    "*W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of\n",
    "Anthropological Research 33, 452-473 (1977).*\n",
    "\n",
    "\n",
    "![Karate Club](./img/zachary_black_lines.png)\n",
    "\n",
    "This is a small graph which allows for easy visual inspection to validate results.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf\n",
    "from collections import OrderedDict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Read the data using cuDF"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test file   \n",
    "datafile='./data/karate-data.csv'\n",
    "\n",
    "# Read the data file\n",
    "cols = [\"src\", \"dst\"]\n",
    "\n",
    "dtypes = OrderedDict([\n",
    "        (\"src\", \"int32\"), \n",
    "        (\"dst\", \"int32\")\n",
    "        ])\n",
    "\n",
    "gdf = cudf.read_csv(datafile, names=cols, delimiter='\\t', dtype=list(dtypes.values()) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Since the test data has the first vertex starting at index \"1\" and cuGraph is zero based, \n",
    "# adjust the indexies\n",
    "gdf['src_id'] = gdf['src'] -1\n",
    "gdf['dst_id'] = gdf['dst'] -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a Graph \n",
    "G = cugraph.Graph()\n",
    "G.add_edge_list(gdf[\"src_id\"], gdf[\"dst_id\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compute PageRank to use as the vertex weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call Pagerank on the graph to get weights to use:\n",
    "pr_df = cugraph.pagerank(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>vertex</th>\n",
       "      <th>pagerank</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>0.096999</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>0.052877</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>0.057078</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>0.035860</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>0.021979</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   vertex  pagerank\n",
       "0       0  0.096999\n",
       "1       1  0.052877\n",
       "2       2  0.057078\n",
       "3       3  0.035860\n",
       "4       4  0.021979"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pr_df.head().to_pandas()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Now compute the Weighted Jaccard "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call weighted Jaccard using the Pagerank scores as weights:\n",
    "df = cugraph.jaccard_w(G, pr_df['pagerank'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the most similar pair of vertices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vertices 3 and 7 are most similar with score: 0.6644074\n"
     ]
    }
   ],
   "source": [
    "bestEdge = 0\n",
    "for i in range(len(df)):\n",
    "    if df['jaccard_coeff'][i] > df['jaccard_coeff'][bestEdge]:\n",
    "        bestEdge = i\n",
    "        \n",
    "print(\"Vertices \" + str(df['source'][bestEdge]) + \n",
    "      \" and \" + str(df['destination'][bestEdge] ) + \n",
    "      \" are most similar with score: \" + str(df['jaccard_coeff'][bestEdge]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## It is that easy with cuGraph!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "Copyright (c) 2019, NVIDIA CORPORATION.\n",
    "\n",
    "Licensed under the Apache License, Version 2.0 (the \"License\");  you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.\n",
    "___"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}