4_link_predict.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Link Prediction using Graph Neural Networks\n",
    "===========================================\n",
    "\n",
    "In the [introduction](1_introduction.ipynb), you have already learned\n",
    "the basic workflow of using GNNs for node classification,\n",
    "i.e. predicting the category of a node in a graph. This tutorial will\n",
    "teach you how to train a GNN for link prediction, i.e. predicting the\n",
    "existence of an edge between two arbitrary nodes in a graph.\n",
    "\n",
    "By the end of this tutorial you will be able to\n",
    "\n",
    "-  Build a GNN-based link prediction model.\n",
    "-  Train and evaluate the model on a small DGL-provided dataset.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Using backend: pytorch\n"
     ]
    }
   ],
   "source": [
    "import dgl\n",
    "import torch\n",
    "import torch.nn as nn\n",
    "import torch.nn.functional as F\n",
    "import itertools\n",
    "import numpy as np\n",
    "import scipy.sparse as sp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Overview of Link Prediction with GNN\n",
    "------------------------------------\n",
    "\n",
    "Many applications such as social recommendation, item recommendation,\n",
    "knowledge graph completion, etc., can be formulated as link prediction,\n",
    "which predicts whether an edge exists between two particular nodes. This\n",
    "tutorial shows an example of predicting whether a citation relationship,\n",
    "either citing or being cited, between two papers exists in a citation\n",
    "network.\n",
    "\n",
    "This tutorial formulates the link prediction problem as a binary classification\n",
    "problem as follows:\n",
    "\n",
    "-  Treat the edges in the graph as *positive examples*.\n",
    "-  Sample a number of non-existent edges (i.e. node pairs with no edges\n",
    "   between them) as *negative* examples.\n",
    "-  Divide the positive examples and negative examples into a training\n",
    "   set and a test set.\n",
    "-  Evaluate the model with any binary classification metric such as Area\n",
    "   Under Curve (AUC).\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "    \n",
    "**Note**: The practice comes from\n",
    "   [SEAL](https://papers.nips.cc/paper/2018/file/53f0d7c537d99b3824f0f99d62ea2428-Paper.pdf),\n",
    "   although the model here does not use their idea of node labeling.\n",
    "\n",
    "</div>\n",
    "\n",
    "In some domains such as large-scale recommender systems or information\n",
    "retrieval, you may favor metrics that emphasize good performance of\n",
    "top-K predictions. In these cases you may want to consider other metrics\n",
    "such as mean average precision, and use other negative sampling methods,\n",
    "which are beyond the scope of this tutorial.\n",
    "\n",
    "Loading graph and features\n",
    "--------------------------\n",
    "\n",
    "Following the [introduction](1_introduction.ipynb), this tutorial\n",
    "first loads the Cora dataset.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  NumNodes: 2708\n",
      "  NumEdges: 10556\n",
      "  NumFeats: 1433\n",
      "  NumClasses: 7\n",
      "  NumTrainingSamples: 140\n",
      "  NumValidationSamples: 500\n",
      "  NumTestSamples: 1000\n",
      "Done loading data from cached files.\n"
     ]
    }
   ],
   "source": [
    "import dgl.data\n",
    "\n",
    "dataset = dgl.data.CoraGraphDataset()\n",
    "g = dataset[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prepare training and testing sets\n",
    "---------------------------------\n",
    "\n",
    "This tutorial randomly picks 10% of the edges for positive examples in\n",
    "the test set, and leave the rest for the training set. It then samples\n",
    "the same number of edges for negative examples in both sets.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Split edge set for training and testing\n",
    "u, v = g.edges()\n",
    "\n",
    "eids = np.arange(g.number_of_edges())\n",
    "eids = np.random.permutation(eids)\n",
    "test_size = int(len(eids) * 0.1)\n",
    "train_size = g.number_of_edges() - test_size\n",
    "test_pos_u, test_pos_v = u[eids[:test_size]], v[eids[:test_size]]\n",
    "train_pos_u, train_pos_v = u[eids[test_size:]], v[eids[test_size:]]\n",
    "\n",
    "# Find all negative edges and split them for training and testing\n",
    "adj = sp.coo_matrix((np.ones(len(u)), (u.numpy(), v.numpy())))\n",
    "adj_neg = 1 - adj.todense() - np.eye(g.number_of_nodes())\n",
    "neg_u, neg_v = np.where(adj_neg != 0)\n",
    "\n",
    "neg_eids = np.random.choice(len(neg_u), g.number_of_edges() // 2)\n",
    "test_neg_u, test_neg_v = neg_u[neg_eids[:test_size]], neg_v[neg_eids[:test_size]]\n",
    "train_neg_u, train_neg_v = neg_u[neg_eids[test_size:]], neg_v[neg_eids[test_size:]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When training, you will need to remove the edges in the test set from\n",
    "the original graph. You can do this via ``dgl.remove_edges``.\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "    \n",
    "**Note**: ``dgl.remove_edges`` works by creating a subgraph from the\n",
    "   original graph, resulting in a copy and therefore could be slow for\n",
    "   large graphs. If so, you could save the training and test graph to\n",
    "   disk, as you would do for preprocessing.\n",
    "\n",
    "</div>\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_g = dgl.remove_edges(g, eids[:test_size])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define a GraphSAGE model\n",
    "------------------------\n",
    "\n",
    "This tutorial builds a model consisting of two\n",
    "[GraphSAGE](https://arxiv.org/abs/1706.02216) layers, each computes\n",
    "new node representations by averaging neighbor information. DGL provides\n",
    "``dgl.nn.SAGEConv`` that conveniently creates a GraphSAGE layer.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dgl.nn import SAGEConv\n",
    "\n",
    "# ----------- 2. create model -------------- #\n",
    "# build a two-layer GraphSAGE model\n",
    "class GraphSAGE(nn.Module):\n",
    "    def __init__(self, in_feats, h_feats):\n",
    "        super(GraphSAGE, self).__init__()\n",
    "        self.conv1 = SAGEConv(in_feats, h_feats, 'mean')\n",
    "        self.conv2 = SAGEConv(h_feats, h_feats, 'mean')\n",
    "    \n",
    "    def forward(self, g, in_feat):\n",
    "        h = self.conv1(g, in_feat)\n",
    "        h = F.relu(h)\n",
    "        h = self.conv2(g, h)\n",
    "        return h"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The model then predicts the probability of existence of an edge by\n",
    "computing a score between the representations of both incident nodes\n",
    "with a function (e.g. an MLP or a dot product), which you will see in\n",
    "the next section.\n",
    "\n",
    "\\begin{align}\\hat{y}_{u\\sim v} = f(h_u, h_v)\\end{align}\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Positive graph, negative graph, and ``apply_edges``\n",
    "---------------------------------------------------\n",
    "\n",
    "In previous tutorials you have learned how to compute node\n",
    "representations with a GNN. However, link prediction requires you to\n",
    "compute representation of *pairs of nodes*.\n",
    "\n",
    "DGL recommends you to treat the pairs of nodes as another graph, since\n",
    "you can describe a pair of nodes with an edge. In link prediction, you\n",
    "will have a *positive graph* consisting of all the positive examples as\n",
    "edges, and a *negative graph* consisting of all the negative examples.\n",
    "The *positive graph* and the *negative graph* will contain the same set\n",
    "of nodes as the original graph.  This makes it easier to pass node\n",
    "features among multiple graphs for computation.  As you will see later,\n",
    "you can directly fed the node representations computed on the entire\n",
    "graph to the positive and the negative graphs for computing pair-wise\n",
    "scores.\n",
    "\n",
    "The following code constructs the positive graph and the negative graph\n",
    "for the training set and the test set respectively.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_pos_g = dgl.graph((train_pos_u, train_pos_v), num_nodes=g.number_of_nodes())\n",
    "train_neg_g = dgl.graph((train_neg_u, train_neg_v), num_nodes=g.number_of_nodes())\n",
    "\n",
    "test_pos_g = dgl.graph((test_pos_u, test_pos_v), num_nodes=g.number_of_nodes())\n",
    "test_neg_g = dgl.graph((test_neg_u, test_neg_v), num_nodes=g.number_of_nodes())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The benefit of treating the pairs of nodes as a graph is that you can\n",
    "use the ``DGLGraph.apply_edges`` method, which conveniently computes new\n",
    "edge features based on the incident nodes’ features and the original\n",
    "edge features (if applicable).\n",
    "\n",
    "DGL provides a set of optimized builtin functions to compute new\n",
    "edge features based on the original node/edge features. For example,\n",
    "``dgl.function.u_dot_v`` computes a dot product of the incident nodes’\n",
    "representations for each edge.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "import dgl.function as fn\n",
    "\n",
    "class DotPredictor(nn.Module):\n",
    "    def forward(self, g, h):\n",
    "        with g.local_scope():\n",
    "            g.ndata['h'] = h\n",
    "            # Compute a new edge feature named 'score' by a dot-product between the\n",
    "            # source node feature 'h' and destination node feature 'h'.\n",
    "            g.apply_edges(fn.u_dot_v('h', 'h', 'score'))\n",
    "            # u_dot_v returns a 1-element vector for each edge so you need to squeeze it.\n",
    "            return g.edata['score'][:, 0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can also write your own function if it is complex.\n",
    "For instance, the following module produces a scalar score on each edge\n",
    "by concatenating the incident nodes’ features and passing it to an MLP.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MLPPredictor(nn.Module):\n",
    "    def __init__(self, h_feats):\n",
    "        super().__init__()\n",
    "        self.W1 = nn.Linear(h_feats * 2, h_feats)\n",
    "        self.W2 = nn.Linear(h_feats, 1)\n",
    "\n",
    "    def apply_edges(self, edges):\n",
    "        \"\"\"\n",
    "        Computes a scalar score for each edge of the given graph.\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        edges :\n",
    "            Has three members ``src``, ``dst`` and ``data``, each of\n",
    "            which is a dictionary representing the features of the\n",
    "            source nodes, the destination nodes, and the edges\n",
    "            themselves.\n",
    "\n",
    "        Returns\n",
    "        -------\n",
    "        dict\n",
    "            A dictionary of new edge features.\n",
    "        \"\"\"\n",
    "        h = torch.cat([edges.src['h'], edges.dst['h']], 1)\n",
    "        return {'score': self.W2(F.relu(self.W1(h))).squeeze(1)}\n",
    "\n",
    "    def forward(self, g, h):\n",
    "        with g.local_scope():\n",
    "            g.ndata['h'] = h\n",
    "            g.apply_edges(self.apply_edges)\n",
    "            return g.edata['score']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-info\">\n",
    "    \n",
    "**Note**: The builtin functions are optimized for both speed and memory.\n",
    "   We recommend using builtin functions whenever possible.\n",
    "\n",
    "</div>\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "    \n",
    "**Note**: If you have read the [message passing\n",
    "   tutorial](3_message_passing.ipynb), you will notice that the\n",
    "   argument ``apply_edges`` takes has exactly the same form as a message\n",
    "   function in ``update_all``.\n",
    "\n",
    "</div>\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Training loop\n",
    "-------------\n",
    "\n",
    "After you defined the node representation computation and the edge score\n",
    "computation, you can go ahead and define the overall model, loss\n",
    "function, and evaluation metric.\n",
    "\n",
    "The loss function is simply binary cross entropy loss.\n",
    "\n",
    "\\begin{align}\\mathcal{L} = -\\sum_{u\\sim v\\in \\mathcal{D}}\\left( y_{u\\sim v}\\log(\\hat{y}_{u\\sim v}) + (1-y_{u\\sim v})\\log(1-\\hat{y}_{u\\sim v})) \\right)\\end{align}\n",
    "\n",
    "The evaluation metric in this tutorial is AUC.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "model = GraphSAGE(train_g.ndata['feat'].shape[1], 16)\n",
    "# You can replace DotPredictor with MLPPredictor.\n",
    "#pred = MLPPredictor(16)\n",
    "pred = DotPredictor()\n",
    "\n",
    "def compute_loss(pos_score, neg_score):\n",
    "    scores = torch.cat([pos_score, neg_score])\n",
    "    labels = torch.cat([torch.ones(pos_score.shape[0]), torch.zeros(neg_score.shape[0])])\n",
    "    return F.binary_cross_entropy_with_logits(scores, labels)\n",
    "\n",
    "def compute_auc(pos_score, neg_score):\n",
    "    scores = torch.cat([pos_score, neg_score]).numpy()\n",
    "    labels = torch.cat(\n",
    "        [torch.ones(pos_score.shape[0]), torch.zeros(neg_score.shape[0])]).numpy()\n",
    "    return roc_auc_score(labels, scores)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The training loop goes as follows:\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "    \n",
    "**Note**: This tutorial does not include evaluation on a validation\n",
    "   set. In practice you should save and evaluate the best model based on\n",
    "   performance on the validation set.\n",
    "\n",
    "</div>\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In epoch 0, loss: 0.6184065937995911\n",
      "In epoch 5, loss: 0.6056914925575256\n",
      "In epoch 10, loss: 0.5802127122879028\n",
      "In epoch 15, loss: 0.5393418073654175\n",
      "In epoch 20, loss: 0.48020118474960327\n",
      "In epoch 25, loss: 0.4126580059528351\n",
      "In epoch 30, loss: 0.36391153931617737\n",
      "In epoch 35, loss: 0.32281294465065\n",
      "In epoch 40, loss: 0.2892597019672394\n",
      "In epoch 45, loss: 0.2589336931705475\n",
      "In epoch 50, loss: 0.23045368492603302\n",
      "In epoch 55, loss: 0.2066962718963623\n",
      "In epoch 60, loss: 0.18129807710647583\n",
      "In epoch 65, loss: 0.1579950898885727\n",
      "In epoch 70, loss: 0.1354110985994339\n",
      "In epoch 75, loss: 0.11393584311008453\n",
      "In epoch 80, loss: 0.0939987450838089\n",
      "In epoch 85, loss: 0.07589612156152725\n",
      "In epoch 90, loss: 0.0597052127122879\n",
      "In epoch 95, loss: 0.04581739008426666\n",
      "AUC 0.8605017856741763\n"
     ]
    }
   ],
   "source": [
    "# ----------- 3. set up loss and optimizer -------------- #\n",
    "# in this case, loss will in training loop\n",
    "optimizer = torch.optim.Adam(itertools.chain(model.parameters(), pred.parameters()), lr=0.01)\n",
    "\n",
    "# ----------- 4. training -------------------------------- #\n",
    "all_logits = []\n",
    "for e in range(100):\n",
    "    # forward\n",
    "    h = model(train_g, train_g.ndata['feat'])\n",
    "    pos_score = pred(train_pos_g, h)\n",
    "    neg_score = pred(train_neg_g, h)\n",
    "    loss = compute_loss(pos_score, neg_score)\n",
    "    \n",
    "    # backward\n",
    "    optimizer.zero_grad()\n",
    "    loss.backward()\n",
    "    optimizer.step()\n",
    "    \n",
    "    if e % 5 == 0:\n",
    "        print('In epoch {}, loss: {}'.format(e, loss))\n",
    "\n",
    "# ----------- 5. check results ------------------------ #\n",
    "from sklearn.metrics import roc_auc_score\n",
    "with torch.no_grad():\n",
    "    pos_score = pred(test_pos_g, h)\n",
    "    neg_score = pred(test_neg_g, h)\n",
    "    print('AUC', compute_auc(pos_score, neg_score))"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}