notebooks/algorithms/link_prediction/Overlap-Similarity.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Overlap Similarity\n",
    "----\n",
    "\n",
    "In this notebook we will explore the Overlap Coefficient and compare it again Jaccard.  Similarity can be between neighboring vertices (default) or second hop neighbors\n",
    "\n",
    "\n",
    "Notebook Credits\n",
    "\n",
    "| Author Credit |    Date    |  Update          | cuGraph Version |  Test Hardware           |\n",
    "| --------------|------------|------------------|-----------------|--------------------------|\n",
    "| Brad Rees     | 10/14/2019 | created          | 0.08            | GV100, CUDA 10.0         |\n",
    "|               | 08/16/2020 | upadated         | 0.12            | GV100, CUDA 10.0         |\n",
    "|               | 08/05/2021 | tested / updated | 21.10 nightly   | RTX 3090 CUDA 11.4       |\n",
    "| Ralph Liu     | 06/22/2022 | updated/tested   | 22.08 nightly   | DGX Tesla V100 CUDA 11.5 |\n",
    "| Don Acosta    | 08/03/2022 | tested / updated | 22.08 nightly   | DGX Tesla V100 CUDA 11.5 |\n",
    "|  Ralph Liu    | 06/29/2023 | updated | 23.08 nightly   | DGX Tesla V100 CUDA 12.0"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction - Common Neighbor Similarity \n",
    "\n",
    "One of the most common types of vertex similarity is to evaluate the neighborhood of vertex pairs and looks at the number of common neighbors.  That type of similar comes from statistics and is based on set comparison.  Both Jaccard and the Overlap Coefficient operate on sets, and in a graph setting, those sets are the list of neighboring vertices. <br>\n",
    "For those that like math:  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",
    "\n",
    "For the rest of this introduction, set __A__ will equate to _A = N(i)_ and set __B__ will quate to _B = N(j)_.  That just make the rest of the text more readable."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Overlap Coefficient"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Overlap Coefficient between two sets is defined as the ratio of the volume of their intersection divided by the volume of the smaller set.\n",
    "The Overlap Coefficient can be defined as\n",
    "\n",
    "To compute the Overlap Coefficient between all pairs of vertices connected by an edge in cuGraph use: <br>\n",
    "$oc(A,B)=\\frac{|A|\\cap|B|}{min(|A|,|B|)}$\n",
    "\n",
    "__df = cugraph.overlap(G)__\n",
    "\n",
    "    G: A cugraph.Graph object\n",
    "\n",
    "Returns:\n",
    "\n",
    "    df: cudf.DataFrame with three names columns:\n",
    "        df[\"first\"]: The first vertex id of each pair.\n",
    "        df[\"second\"]: The second vertex id of each pair.\n",
    "        df[\"overlap_coeff\"]: The overlap coefficient computed between the vertex pairs.\n",
    "\n",
    "__References__\n",
    "- https://en.wikipedia.org/wiki/Overlap_coefficient\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Refresh on Jaccard\n",
    "The Jaccard similarity between two sets is defined as the ratio of the volume of their intersection divided by the volume of their union. \n",
    "\n",
    "The Jaccard Similarity can then be defined as\n",
    "\n",
    "Jaccard similarity coefficient = $\\frac{|A \\cap B|}{|A \\cup B|}$\n",
    "\n",
    "To compute the Jaccard similarity between all pairs of vertices connected by an edge in cuGraph use: <br>\n",
    "__df = cugraph.jaccard(G)__\n",
    "\n",
    "    G: A cugraph.Graph object\n",
    "\n",
    "Returns:\n",
    "\n",
    "    df: cudf.DataFrame with three names columns:\n",
    "        df[\"first\"]: The first vertex id of each pair.\n",
    "        df[\"second\"]: The second vertex id of each pair.\n",
    "        df[\"jaccard_coeff\"]: The jaccard coefficient computed between the vertex pairs.\n",
    "<br>\n",
    "\n",
    "See the Jaccard notebook for additional information and background"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Additional Reading\n",
    "- [Similarity in graphs: Jaccard versus the Overlap Coefficient](https://medium.com/rapids-ai/similarity-in-graphs-jaccard-versus-the-overlap-coefficient-610e083b877d)\n",
    "- [Wikipedia: Overlap Coefficient](https://en.wikipedia.org/wiki/Overlap_coefficient)\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Some notes about vertex IDs...\n",
    "\n",
    "* cuGraph will automatically renumber graphs to an internal format consisting of a contiguous series of integers starting from 0, and convert back to the original IDs when returning data to the caller. If the vertex IDs of the data are already a contiguous series of integers starting from 0, the auto-renumbering step can be skipped for faster graph creation times.\n",
    "  * To skip auto-renumbering, set the `renumber` boolean arg to `False` when calling the appropriate graph creation API (eg. `G.from_cudf_edgelist(gdf_r, source='src', destination='dst', renumber=False)`).\n",
    "  * For more advanced renumbering support, see the examples in `structure/renumber.ipynb` and `structure/renumber-2.ipynb`\n"
   ]
  },
  {
   "attachments": {},
   "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",
    "<img src=\"../../img/zachary_black_lines.png\" width=\"35%\"/>\n",
    "\n",
    "This is a small graph which allows for easy visual inspection to validate results.  "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Let's get started!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "### Define some Print functions\n",
    "(the `del` are not needed since going out of scope should free memory)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a function for printing the top most similar vertices\n",
    "def print_most_similar_jaccard(df):\n",
    "    \n",
    "    jmax = df['jaccard_coeff'].max()\n",
    "    dm = df.query('jaccard_coeff >= @jmax')    \n",
    "    \n",
    "    #find the best\n",
    "    for i in range(len(dm)):    \n",
    "        print(\"Vertices \" + str(dm['first'].iloc[i]) + \" and \" + \n",
    "              str(dm['second'].iloc[i]) + \" are most similar with score: \" \n",
    "              + str(dm['jaccard_coeff'].iloc[i]))\n",
    "    del jmax\n",
    "    del dm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a function for printing the top most similar vertices\n",
    "def print_most_similar_overlap(df):\n",
    "    \n",
    "    smax = df['overlap_coeff'].max()\n",
    "    dm = df.query('overlap_coeff >= @smax and first < second')      \n",
    "    \n",
    "    for i in range(len(dm)):\n",
    "        print(\"Vertices \" + str(dm['first'].iloc[i]) + \" and \" + \n",
    "          str(dm['second'].iloc[i]) + \" are most similar with score: \" \n",
    "          + str(dm['overlap_coeff'].iloc[i]))\n",
    "        \n",
    "    del smax\n",
    "    del dm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a function for printing jaccard similar vertices based on a threshold\n",
    "def print_jaccard_threshold(_d, limit):\n",
    "    \n",
    "    filtered = _d.query('jaccard_coeff > @limit')\n",
    "    \n",
    "    for i in range(len(filtered)):\n",
    "        print(\"Vertices \" + str(filtered['first'].iloc[i]) + \" and \" + \n",
    "            str(filtered['second'].iloc[i]) + \" are similar with score: \" + \n",
    "            str(filtered['jaccard_coeff'].iloc[i]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a function for printing similar vertices based on a threshold\n",
    "def print_overlap_threshold(_d, limit):\n",
    "    \n",
    "    filtered = _d.query('overlap_coeff > @limit')\n",
    "    \n",
    "    for i in range(len(filtered)):\n",
    "        if filtered['first'].iloc[i] != filtered['second'].iloc[i] :\n",
    "            print(\"Vertices \" + str(filtered['first'].iloc[i]) + \" and \" + \n",
    "                str(filtered['second'].iloc[i]) + \" are similar with score: \" + \n",
    "                str(filtered['overlap_coeff'].iloc[i]))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Import a Dataset Object"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from cugraph.datasets import karate\n",
    "gdf = karate.get_edgelist(download=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's look at the DataFrame. There should be two columns and 156 records\n",
    "gdf.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Look at the first few data records - the output should be two columns: 'src' and 'dst'\n",
    "gdf.head()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a Graph \n",
    "G = karate.get_graph()\n",
    "G = G.to_undirected()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# How many vertices are in the graph?  \n",
    "G.number_of_vertices()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "--- \n",
    "# Jaccard "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#%%time\n",
    "# Call cugraph.nvJaccard \n",
    "jdf = cugraph.jaccard(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Which two vertices are the most similar?\n",
    "print_most_similar_jaccard(jdf)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Most similar shoul be 33 and 34.\n",
    "Vertex 33 has 12 neighbors, vertex 34 has 17 neighbors.  They share 10 neighbors in common:\n",
    "$jaccard = 10 / (10 + (12 -10) + (17-10)) = 10 / 19 = 0.526$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### let's look at all similarities over a threshold\n",
    "print_jaccard_threshold(jdf, 0.4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Since it is a small graph we can print all scores, notice that only vertices that are neighbors are being compared\n",
    "#\n",
    "# Before printing, let's get rid of the duplicates (x compared to y is the same as y compared to x).  We will do that\n",
    "# by performing a query.  Then let's sort the data by score\n",
    "\n",
    "jdf_s = jdf.query('first < second').sort_values(by='jaccard_coeff', ascending=False)\n",
    "\n",
    "print_jaccard_threshold(jdf_s, 0.0)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Overlap Coefficient"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Noticed that the Jaccard score is based on the number of common items over the combined (union) set of items.  That makes sense when the two sets being compared are relativcely close in size.  However, when one set is considerable larger, then it is important to know if one set is a proper subset of the other <br>\n",
    "See:  [Similarity in graphs: Jaccard versus the Overlap Coefficient](https://medium.com/rapids-ai/similarity-in-graphs-jaccard-versus-the-overlap-coefficient-610e083b877d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#%%time\n",
    "# Call cugraph.nvJaccard \n",
    "odf = cugraph.overlap(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# print the top similar pair - this function include code to drop duplicates  \n",
    "print_most_similar_overlap(odf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# print all similarities over a threshold, in this case 0.5\n",
    "# also, drop duplicates\n",
    "odf_s = odf.query('first < second').sort_values(by='overlap_coeff', ascending=False)\n",
    "\n",
    "print_overlap_threshold(odf_s, 0.5)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Expanding similarity scoring to 2-hop vertex pair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get all two-hop vertex pairs\n",
    "p = G.get_two_hop_neighbors()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's look at the Jaccard score\n",
    "ol2 = cugraph.overlap(G, vertex_pair=p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print_most_similar_overlap(odf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# print all similarities over a threshold, in this case 0.5\n",
    "# also, drop duplicates\n",
    "odf_s2 = ol2.query('first < second').sort_values(by='overlap_coeff', ascending=False)\n",
    "\n",
    "print_overlap_threshold(odf_s2, 0.74)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Let's now compare the Overlap Coefficient with the Jaccard Similarity "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call cugraph.nvJaccard \n",
    "jdf = cugraph.jaccard(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Which two vertices are the most similar?\n",
    "print_most_similar_jaccard(jdf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's combine the Jaccard and Overlap scores\n",
    "mdf = jdf.merge(odf, on=['first','second'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Also want to include the vertex degree\n",
    "degree = G.degree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dS = degree.rename(columns={'vertex':'first','degree': 'src_degree'})\n",
    "dD = degree.rename(columns={'vertex':'second','degree': 'dst_degree'})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = mdf.merge(dS, how=\"left\", on='first')\n",
    "m = m.merge(dD, how=\"left\", on='second')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m.query('first < second').sort_values(by='jaccard_coeff', ascending=False).head(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Now sort on the overlap\n",
    "m.query('first < second').sort_values(by='overlap_coeff', ascending=False).head(20)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "Copyright (c) 2019-2023, 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.9.13 ('cugraph_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.9.13"
  },
  "vscode": {
   "interpreter": {
    "hash": "cee8a395f2f0c5a5bcf513ae8b620111f4346eff6dc64e1ea99c951b2ec68604"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}