experiment_scalability.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scalability Experiment (Section 5.3)\n",
    "\n",
    "The experiment is designed to compare the execution time of different coarsening schemes over increasingly large graphs.\n",
    "\n",
    "* For consistency, we use a regular graph of increasing size (vertices, edges) but always the same degree\n",
    "* The reduction is fixed to 0.5. The execution time will only slightly increase for larger ratios (since the problem that has to be solved becomes easier at consecutive levels where the graph is smaller)\n",
    "* If the execution time exceeds a budget (set to 100 sec), computation is skipped.\n",
    "\n",
    "The code accompanies the preprint: [Graph reduction with spectral and cut guarantees](https://arxiv.org/abs/1808.10650). The final version of the paper will appear at JMLR.\n",
    "\n",
    "Depedencies: pygsp, matplotlib, numpy, scipy, networkx, sortedcontainers\n",
    "\n",
    "This work was kindly supported by the Swiss National Science Foundation (grant number PZ00P2 179981).\n",
    "\n",
    "15 March 2019\n",
    "\n",
    "[Andreas Loukas](https://andreasloukas.wordpress.com)\n",
    "\n",
    "Released under the MIT license "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.core.display import display, HTML\n",
    "display(HTML(\"<style>.container { width:80% !important; }</style>\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from libraries.coarsening_utils import *\n",
    "import libraries.graph_lib as graph_lib\n",
    "import libraries.graph_utils as graph_utils\n",
    "\n",
    "import numpy as np\n",
    "import scipy as sp\n",
    "from scipy import io\n",
    "from scipy.linalg import circulant\n",
    "import time\n",
    "import os \n",
    "\n",
    "import matplotlib\n",
    "import matplotlib.pylab as plt\n",
    "\n",
    "import pygsp as gsp\n",
    "from pygsp import graphs, filters\n",
    "gsp.plotting.BACKEND = 'matplotlib'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Experiment parameters\n",
    "N_all        = np.logspace(2, 6, 30, dtype=np.int)\n",
    "methods      = ['heavy_edge', 'variation_edges', 'variation_neighborhoods', 'algebraic_JC', 'affinity_GS', 'kron'] \n",
    "K_all        = [10,80] #[10, 20, 40]\n",
    "r            = 0.5\n",
    "budget       = 100 # don't run anything that takes longer than this (in seconds)\n",
    "n_iterations = 10\n",
    "deg          = 10\n",
    "algorithm    = 'greedy'  \n",
    "n_methods    = len(methods)\n",
    "# print(deg*N_all/2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The actual experiment code (this will take long)\n",
    "If one needs to just see the results, skip running this part."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rerun_all = False\n",
    "rewrite_results = False\n",
    "if rerun_all:\n",
    "\n",
    "    timings = np.zeros((len(N_all), len(K_all), n_methods, n_iterations)) * np.NaN\n",
    "    skip    = np.zeros(len(methods))\n",
    "\n",
    "    for NIdx, N in enumerate(N_all):\n",
    "\n",
    "        G = graph_lib.models(N, 'regular', k=deg) \n",
    "\n",
    "        for KIdx, K in enumerate(K_all):\n",
    "            for methodIdx,method in enumerate(methods):\n",
    "\n",
    "                if skip[methodIdx] == 1 :\n",
    "                    timings[NIdx, KIdx, methodIdx] = np.NaN\n",
    "                    print('skipping: {}, {}, {}'.format(N, method, K))\n",
    "                    continue\n",
    "\n",
    "                timing = 0\n",
    "                for iteration in range(n_iterations):\n",
    "                    if method == 'kron':\n",
    "                        start = time.time()\n",
    "                        _, tmp  = kron_coarsening(G, r=r, m=None)\n",
    "                        end = time.time()\n",
    "                        if tmp == None: \n",
    "                            print('kron failed... skipping')\n",
    "                            continue\n",
    "                    else:\n",
    "                        start = time.time()\n",
    "                        _, _, Call, _ = coarsen(G, K=K, r=r, max_levels=4, method=method, algorithm=algorithm)\n",
    "                        end = time.time()\n",
    "\n",
    "                        if len(Call) >= 4: print('warning: too many levels for {}, r:{}, K:{}'.format(method, r, K) )\n",
    "\n",
    "                    timings[NIdx, KIdx, methodIdx, iteration] = end-start\n",
    "\n",
    "                timing = np.mean(timings[NIdx, KIdx, methodIdx, :])            \n",
    "                skip[methodIdx] = 1 if (timing > budget) else 0\n",
    "\n",
    "        print('N = {}, done!'.format(N))\n",
    "\n",
    "        if sum(skip) == len(methods): break\n",
    "\n",
    "    if rewrite_results:\n",
    "        filepath = os.path.join('.', 'results', 'experiment_scalability.npz')\n",
    "        print('.. saving to \"' + filepath + '\"')\n",
    "        np.savez(filepath, methods=methods, K_all=K_all, N_all=N_all, timings=timings, deg=deg, budget=budget)\n",
    "\n",
    "print('done!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Load results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "filepath = os.path.join('.', 'results', 'experiment_scalability.npz')\n",
    "data = np.load(filepath)\n",
    "\n",
    "methods, K_all, N_all, timings, deg, budget = data['methods'], data['K_all'], data['N_all'], data['timings'], data['deg'], data['budget'] "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Visualize them\n",
    "\n",
    "The produced figures are used in the paper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "matplotlib.rcParams.update({'font.size': 25})\n",
    "\n",
    "from matplotlib import cm\n",
    "colors = [ cm.ocean(x) for x in np.linspace(0, 0.95, len(methods)+1)]\n",
    "colors[1] = [0.8,0,0] \n",
    "colors[-2] = (np.array([127, 77, 34])/255).tolist()  \n",
    "\n",
    "size = 2.7*2.7; \n",
    "\n",
    "print('The figures are drawn in the following in order:')\n",
    "for KIdx, K in enumerate(K_all):\n",
    "        \n",
    "    fig, axes = plt.subplots(1, 1, figsize=(1.618*size, size)); \n",
    "    for methodIdx,method in reversed(list(enumerate(methods))):\n",
    " \n",
    "        lineWidth = 1.5; marker = 's'\n",
    "        method = method.replace('_', ' ')                \n",
    "        if method == 'heavy edge':\n",
    "            method = 'heavy edge'\n",
    "            cIdx, line, marker = 0, ':', 's'\n",
    "        elif 'variation edges' in method:\n",
    "            method = 'local var. (edges)'\n",
    "            cIdx, line, marker, lineWidth = 2, '-', 'o', 1.5\n",
    "        elif (method == 'variation neighborhoods') or (method == 'variation neighborhood'):\n",
    "            method = 'local var. (neigh)'\n",
    "            cIdx, line, marker, lineWidth = 1, '-', 'o', 1.5 \n",
    "        elif 'algebraic' in method:\n",
    "            method = 'algebraic dist.'\n",
    "            cIdx, line = 3, ':'\n",
    "        elif 'affinity' in method:\n",
    "            method = 'affinity'\n",
    "            cIdx, line = 4, ':'\n",
    "        elif method == 'kron':\n",
    "            method = 'kron'\n",
    "            cIdx, line, marker = 5, '--', 'x'\n",
    "        else:\n",
    "            continue\n",
    "            \n",
    "        style = line + marker \n",
    "        color = colors[cIdx]\n",
    "        \n",
    "        tmp = np.mean(timings[:,KIdx,methodIdx,:], 1)\n",
    "        tmp[tmp>budget] = np.NaN\n",
    "        axes.plot(N_all*deg/2, tmp, style, label='{}'.format(method), color=color, lineWidth=lineWidth, markersize=6)\n",
    "\n",
    "    axes.plot(np.array([10, N_all[-1]])*deg/2, [budget, budget], 'k:')\n",
    "    \n",
    "    axes.set_xscale('log')\n",
    "    axes.set_yscale('log')\n",
    "    axes.set_xlabel('number of edges (M)')\n",
    "    axes.set_ylabel('execution time (sec)')\n",
    "    axes.set_ylim([0.02, budget+30])\n",
    "    axes.set_xlim([300, N_all[-1]])\n",
    "    \n",
    "    legend0 = axes.legend(fontsize=22, loc='lower right', edgecolor=[1,1,1])\n",
    "\n",
    "    axes.text(500, 63, 'max execution time', fontsize=21)\n",
    "    axes.spines['right'].set_visible(False)\n",
    "    axes.spines['top'].set_visible(False)\n",
    "        \n",
    "    fig.tight_layout()\n",
    "    \n",
    "    print('* experiment_scalability_K='+ str(K))\n",
    "#     fig.savefig(os.path.join('.', 'results', 'experiment_scalability_K='+ str(K) +'.pdf'))"
   ]
  }
 ],
 "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}