Holoscope.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## HoloScope: detecting collective anoamlies of constract suspiciousness\n",
    "\n",
    "HoloScope is topology-and-spike aware fraud detection.\n",
    "HoloScope detect a subgraph of highly constrast suspicousness on topological, temporal, and categorical (e.g. rating score, topic, tag) infomation. \n",
    "\n",
    "Temporal spike of retweeting a message:\n",
    "\n",
    "<img src=\"./images/msgspike.png\" alt=\"drawing\" width=\"300\"/>\n",
    "\n",
    "### Abstract\n",
    "As online fraudsters invest more resources, including purchasing large pools of fake user accounts and dedicated IPs, fraudulent attacks become less obvious and their detection becomes increasingly challenging. Existing approaches such as average degree maximization suffer from the bias of including more nodes than necessary, resulting in lower accuracy and increased need for manual verification. Hence, we propose HoloScope, which uses information from graph topology and temporal spikes to more accurately detect groups of fraudulent users. In terms of graph topology, we introduce contrast suspiciousness, a dynamic weighting approach, which allows us to more accurately detect fraudulent blocks, particularly low-density blocks. In terms of temporal spikes, HoloScope takes into account the sudden bursts and drops of fraudsters' attacking patterns. In addition, we provide theoretical bounds for how much this increases the time cost needed for fraudsters to conduct adversarial attacks. Additionally, from the perspective of ratings, HoloScope incorporates the deviation of rating scores in order to catch fraudsters more accurately. Moreover, HoloScope has a concise framework and sub-quadratic time complexity, making the algorithm reproducible and scalable. Extensive experiments showed that HoloScope achieved significant accuracy improvements on synthetic and real data, compared with state-of-the-art fraud detection methods."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import spartan as st"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can configure the backend to use GPU or CPU only. \\\n",
    "Default is using backend cpu. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# load graph data\n",
    "tensor_data = st.loadTensor(path = \"./inputData/yelp.tensor.gz\", header=None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\"tensor_data.data\" has multiple-colum attributes, and a single-colum values (optional). The following table shows an example of 10000 four-tuple (user, object, date, score) and the 5th-colum is the frequency. \n",
    "\n",
    "|row id |    0\t|   1\t|         2    \t|   3 \t|   4  \t|\n",
    "|-----:\t|-----:\t|----:\t|-----------:\t|----:\t|-----\t|\n",
    "|    0 \t|    0 \t|   0 \t| 2012-08-01 \t|   4 \t|   1 \t|\n",
    "|    1 \t|    1 \t|   0 \t| 2014-02-13 \t|   5 \t|   1 \t|\n",
    "|    2 \t|    2 \t|   0 \t| 2015-10-31 \t|   5 \t|   1 \t|\n",
    "|    3 \t|    3 \t|   0 \t| 2015-12-26 \t|   3 \t|   1 \t|\n",
    "|    4 \t|    4 \t|   0 \t| 2016-04-08 \t|   2 \t|   1 \t|\n",
    "|  ... \t|  ... \t| ... \t|        ... \t| ... \t| ... \t|\n",
    "| 9995 \t| 4523 \t| 508 \t| 2013-03-06 \t|   5 \t|   1 \t|\n",
    "| 9996 \t|  118 \t| 508 \t| 2013-03-07 \t|   4 \t|   1 \t|\n",
    "| 9997 \t| 5884 \t| 508 \t| 2013-03-07 \t|   1 \t|   1 \t|\n",
    "| 9998 \t| 2628 \t| 508 \t| 2013-04-08 \t|   5 \t|   1 \t|\n",
    "| 9999 \t| 5885 \t| 508 \t| 2013-06-17 \t|   5 \t|   1 \t|"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "stensor = tensor_data.toSTensor(hasvalue=True, mappers={2:st.TimeMapper(timeformat='%Y-%m-%d')})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#stensor._data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sparse tensor \"stensor\" is a multi-mode constructed from tensor_data. users, objects, date time, and score are all mapped into $[0, N]$ integers. \\\n",
    "This example constructs a tensor of $5886 \\times 509 \\times 3857 \\times 6$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = st.Graph(stensor, bipartite=True, weighted=True, modet=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get a Graph instance from a sparse tensor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Run HoloScope as a single model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hs = st.HoloScope(graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(hs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Default parameters are:\n",
    "{'alg': 'fastgreedy', 'eps': 1.6, 'numSing': 10, 'qfun': 'exp', 'b': 32, 'level': 0}\n",
    "You can change them be passing <key>=<value> as the doc shows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "res = hs.run(level=0, k=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Running level can be  \n",
    "0: topology only;  \n",
    "1: topology with time;   \n",
    "2: topology with category (e.g. rating score);  \n",
    "3: all three.  \n",
    "Use k for number of dense blocks you want to get.  \n",
    "res is a list of each block. Each block constains $((rows, nnzcols), susp\\_score, levelcols, nnzcol\\_scores)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Run holoscope from anomaly detection task"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a anomaly detection model\n",
    "ad_model = st.AnomalyDetection.create(graph, st.ADPolicy.HoloScope, 'holoscope')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# run the model\n",
    "#default k=2, eps=1.6\n",
    "res = ad_model.run(k=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The results is a list of top-k suspicious blocks.\n",
    "For each block, the resulting tuple contains $(user~nodes, object~nodes)$,  suspicious score, and suspicious scores of all object nodes.\\\n",
    "Then we can visualize the subgraphs as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "#viusal of graphs by networkx\n",
    "import matplotlib.pyplot as plt\n",
    "for r in res:\n",
    "    rows, cols = r[0]\n",
    "    # to subgraph\n",
    "    sg = graph.get_sub_graph(rows, cols)\n",
    "    # networkx plot\n",
    "    fig = st.plot_graph(sg, bipartite=True, labels=[*rows, *cols])\n",
    "    fig = st.plot_graph(sg, layout='circular', bipartite=True, labels=[*rows, *cols])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The results are two layouts of dense subgraph:\n",
    "    <img src=\"images/hsresult-bi.png\" width=\"300\"/> \n",
    "    <img src=\"images/hsresult-cir.png\" width=\"300\"/> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Experimental results:\n",
    "------\n",
    "\n",
    "HoloScope (topology)       |  HoloScope (holistic signals)\n",
    ":-------------------------:|:-------------------------:\n",
    "<img src=\"images/performCmpDensity.png\" width=\"300\"/>  |   <img src=\"images/performancecmpall.png\" width=\"300\"/>\n",
    "<b>HoloScope detection on real Sina Weibo data |  <b>HoloScope is near linear\n",
    "<img src=\"images/wbexp.png\" width=\"200\"/> |   <img src=\"images/effeciencyexpelec.png\" width=\"300\"/>\n",
    "\n",
    "\n",
    "### Cite:\n",
    "------\n",
    "1. Liu, Shenghua, Bryan Hooi, and Christos Faloutsos. \"Holoscope: Topology-and-spike aware fraud detection.\" In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp. 1539-1548. 2017.\n",
    "\n",
    "    <details>\n",
    "    <summary><span style=\"color:blue\">click for BibTex...</span></summary>\n",
    "\n",
    "    ```bibtex\n",
    "    @inproceedings{liu2017holoscope,\n",
    "      title={Holoscope: Topology-and-spike aware fraud detection},\n",
    "      author={Liu, Shenghua and Hooi, Bryan and Faloutsos, Christos},\n",
    "      booktitle={Proceedings of the 2017 ACM on Conference on Information and Knowledge Management},\n",
    "      pages={1539--1548},\n",
    "      year={2017}\n",
    "    }\n",
    "    ```\n",
    "    </details>  \n",
    "\n",
    "2. Liu, Shenghua, Bryan Hooi, and Christos Faloutsos. \"A contrast metric for fraud detection in rich graphs.\" IEEE Transactions on Knowledge and Data Engineering 31, no. 12 (2018): 2235-2248.\n",
    "\n",
    "    <details>  \n",
    "    <summary><span style=\"color:blue\">click for BibTex...</span></summary>\n",
    "\n",
    "    ```bibtex\n",
    "    @article{liu2018contrast,\n",
    "      title={A contrast metric for fraud detection in rich graphs},\n",
    "      author={Liu, Shenghua and Hooi, Bryan and Faloutsos, Christos},\n",
    "      journal={IEEE Transactions on Knowledge and Data Engineering},\n",
    "      volume={31},\n",
    "      number={12},\n",
    "      pages={2235--2248},\n",
    "      year={2018},\n",
    "      publisher={IEEE}\n",
    "    }\n",
    "    ```\n",
    "    </details>  \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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}