notebooks/algorithms/community/Spectral-Clustering.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Spectral Clustering  \n",
    "\n",
    "In this notebook, we will use cuGraph to identify the cluster in a test graph using Spectral Clustering with both the (A) Balance Cut metric, and (B) the Modularity Maximization metric\n",
    "\n",
    "\n",
    "| Author Credit              |    Date    |  Update          | cuGraph Version |  Test Hardware              |\n",
    "| ---------------------------|------------|------------------|-----------------|-----------------------------|\n",
    "| Brad Rees and James Wyles  | 08/01/2019 | created          | 0.14            | GV100 32G, CUDA 10.2        |\n",
    "|                            | 08/16/2020 | updated          | 0.15   | GV100 32G, CUDA 10.2        |\n",
    "| Don Acosta                 | 07/11/2022 | tested / updated | 22.08 nightly   | DGX Tesla V100 CUDA 11.5    |\n",
    "| Ralph Liu                  | 07/26/2022 | updated          | 22.08 nightly   | DGX Tesla V100 CUDA 11.5   |\n",
    "|              | 06/29/2023 | updated | 23.08 nightly   | DGX Tesla V100 CUDA 12.0"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "Spectral clustering uses the eigenvectors of a Laplacian of the input graph to find a given number of clusters which satisfy a given quality metric. Balanced Cut and Modularity Maximization are two such quality metrics. \n",
    "\n",
    "See:  https://en.wikipedia.org/wiki/Spectral_clustering\n",
    "\n",
    "To perform spectral clustering using the balanced cut metric in cugraph use:\n",
    "\n",
    "__df = cugraph.spectralBalancedCutClustering(G, num_clusters, num_eigen_vects)__\n",
    "<br>or<br>\n",
    "__df = cugraph.spectralModularityMaximizationClustering(G, num_clusters, num_eigen_vects)__\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Balanced Cut\n",
    "\n",
    "    Compute a clustering/partitioning of the given graph using the spectral balanced cut method.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    G : cugraph.Graph\n",
    "        cuGraph graph descriptor\n",
    "    num_clusters : integer\n",
    "         Specifies the number of clusters to find\n",
    "    num_eigen_vects : integer\n",
    "         Specifies the number of eigenvectors to use. Must be lower or equal to\n",
    "         num_clusters.\n",
    "    evs_tolerance: float\n",
    "         Specifies the tolerance to use in the eigensolver\n",
    "    evs_max_iter: integer\n",
    "         Specifies the maximum number of iterations for the eigensolver\n",
    "    kmean_tolerance: float\n",
    "         Specifies the tolerance to use in the k-means solver\n",
    "    kmean_max_iter: integer\n",
    "         Specifies the maximum number of iterations for the k-means solver\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    df : cudf.DataFrame\n",
    "        GPU data frame containing two cudf.Series of size V: the vertex\n",
    "        identifiers and the corresponding cluster assignments.\n",
    "\n",
    "        df['vertex'] : cudf.Series\n",
    "            contains the vertex identifiers\n",
    "        df['cluster'] : cudf.Series\n",
    "            contains the cluster assignments\n",
    "\n",
    "            "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Modularity Maximization\n",
    "\n",
    "    Compute a clustering/partitioning of the given graph using the spectral modularity maximization method.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    G : cugraph.Graph\n",
    "        cuGraph graph descriptor. This graph should have edge weights.\n",
    "    num_clusters : integer\n",
    "         Specifies the number of clusters to find\n",
    "    num_eigen_vects : integer\n",
    "         Specifies the number of eigenvectors to use. Must be lower or equal to\n",
    "         num_clusters\n",
    "    evs_tolerance: float\n",
    "         Specifies the tolerance to use in the eigensolver\n",
    "    evs_max_iter: integer\n",
    "         Specifies the maximum number of iterations for the eigensolver\n",
    "    kmean_tolerance: float\n",
    "         Specifies the tolerance to use in the k-means solver\n",
    "    kmean_max_iter: integer\n",
    "         Specifies the maximum number of iterations for the k-means solver\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    df : cudf.DataFrame\n",
    "        df['vertex'] : cudf.Series\n",
    "            contains the vertex identifiers\n",
    "        df['cluster'] : cudf.Series\n",
    "            contains the cluster assignments"
   ]
  },
  {
   "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_graph_clusters.png\" width=\"35%\"/>\n",
    "\n",
    "Because the test data has vertex IDs starting at 1, the auto-renumber feature of cuGraph (mentioned above) will be used so the starting vertex ID is zero for maximum efficiency. The resulting data will then be auto-unrenumbered, making the entire renumbering process transparent to users.\n",
    "\n",
    "\n",
    "Zachary used a min-cut flow model to partition the graph into two clusters, shown by the circles and squares.  Zarchary wanted just two cluster based on a conflict that caused the Karate club to break into two separate clubs.  Many social network clustering methods identify more that two social groups in the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf\n",
    "import numpy as np\n",
    "\n",
    "# Import a built-in dataset\n",
    "from cugraph.datasets import karate"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create Edgelist and Add Edge Weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gdf = karate.get_edgelist(download=True)\n",
    "\n",
    "# The algorithm requires that there are edge weights.  In this case all the weights are being set to 1\n",
    "gdf[\"data\"] = cudf.Series(np.ones(len(gdf), dtype=np.float32))"
   ]
  },
  {
   "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()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# verify data type\n",
    "gdf.dtypes"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Everything looks good, we can now create a graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a Graph \n",
    "G = cugraph.Graph()\n",
    "G.from_cudf_edgelist(gdf, source='src', destination='dst', edge_attr='data')"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "#### Define and print function, but adjust vertex IDs so that they match the illustration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_cluster(_df, id):\n",
    "    \n",
    "    _f = _df.query('cluster == @id')\n",
    "  \n",
    "    part = []\n",
    "    for i in range(len(_f)):\n",
    "        part.append(_f['vertex'].iloc[i])\n",
    "    print(part)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "#### Using Balanced Cut"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call spectralBalancedCutClustering on the graph for 3 clusters\n",
    "# using 3 eigenvectors:\n",
    "bc_gdf = cugraph.spectralBalancedCutClustering(G, 3, num_eigen_vects=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Check the edge cut score for the produced clustering\n",
    "score = cugraph.analyzeClustering_edge_cut(G, 3, bc_gdf, 'vertex', 'cluster')\n",
    "score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# See which nodes are in cluster 0:\n",
    "print_cluster(bc_gdf, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# See which nodes are in cluster 1:\n",
    "print_cluster(bc_gdf, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# See which nodes are in cluster 2:\n",
    "print_cluster(bc_gdf, 2)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "#### Modularity Maximization\n",
    "Let's now look at the clustering using the modularity maximization metric"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call spectralModularityMaximizationClustering on the graph for 3 clusters\n",
    "# using 3 eigenvectors:\n",
    "mm_gdf = cugraph.spectralModularityMaximizationClustering(G, 3, num_eigen_vects=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Check the modularity score for the produced clustering\n",
    "score = cugraph.analyzeClustering_modularity(G, 3, mm_gdf, 'vertex', 'cluster')\n",
    "score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# See which nodes are in cluster 0:\n",
    "print_cluster(mm_gdf, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print_cluster(mm_gdf, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print_cluster(mm_gdf, 2)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the two metrics produce different results"
   ]
  },
  {
   "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.6.9 64-bit",
   "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"
  },
  "vscode": {
   "interpreter": {
    "hash": "31f2aee4e71d21fbe5cf8b01ff0e069b9275f58929596ceb00d14d90e3e16cd6"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}