basics/4_link_predict.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 그래프 뉴럴 네트워크를 사용한 링크 예측\n",
    "\n",
    "GNN은 그래프 데이터에 대한 많은 머신러닝 task를 해결하는 데 강력한 툴입니다.  \n",
    "이 튜토리얼에서는, 링크 예측을 위해 GNN을 사용하는 기본적인 워크플로우를 배울 수 있습니다.  \n",
    "여기서 Zachery의 카라테 클럽 그래프를 다시 사용합니다. 하지만, 이번에는 두 멤버 사이의 관계를 예측하는 작업을 시도해 봅니다.\n",
    "\n",
    "이 튜토리얼에서, 다음을 배울 수 있습니다.\n",
    "* 링크 예측을 위한 학습/테스트 셋을 준비하는 방법\n",
    "* GNN 기반 링크 예측 모델을 구축하는 법\n",
    "* 모델을 학습하고, 그 결과를 검증하는 법\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "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": [
    "## 그래프와 피처 로드\n",
    "\n",
    "최근 튜토리얼 [세션](./3_gnn.ipynb)에 이어, Zachery의 카라테 클럽 그래프를 불러들여 노드 임베딩을 만듭니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Graph(num_nodes=34, num_edges=156,\n",
      "      ndata_schemes={'club': Scheme(shape=(), dtype=torch.int64), 'club_onehot': Scheme(shape=(2,), dtype=torch.int64)}\n",
      "      edata_schemes={})\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "Parameter containing:\n",
       "tensor([[ 0.3916, -0.0327, -0.1260, -0.2869,  0.2973],\n",
       "        [ 0.3182,  0.0220,  0.1522, -0.2716,  0.2918],\n",
       "        [ 0.1206, -0.1165, -0.3727,  0.0779, -0.1156],\n",
       "        [-0.1390, -0.1939,  0.1905, -0.3710,  0.3080],\n",
       "        [ 0.1564, -0.1069, -0.0932, -0.0339, -0.0070],\n",
       "        [-0.1578,  0.2431, -0.0528,  0.0016,  0.0280],\n",
       "        [ 0.0519, -0.3260, -0.1438, -0.0300, -0.3647],\n",
       "        [-0.2717, -0.0301, -0.1534,  0.1794, -0.1963],\n",
       "        [ 0.3325, -0.1624,  0.0535,  0.1135,  0.0627],\n",
       "        [-0.1526, -0.2020,  0.3215,  0.2962,  0.1816],\n",
       "        [-0.3414, -0.1588,  0.3631,  0.2354,  0.0751],\n",
       "        [ 0.0152,  0.0471,  0.3071, -0.2435,  0.2512],\n",
       "        [-0.2102, -0.2189, -0.3463, -0.3863, -0.3508],\n",
       "        [-0.3871,  0.2010,  0.2501, -0.3321, -0.2337],\n",
       "        [ 0.1315, -0.2012, -0.0101, -0.3694,  0.2327],\n",
       "        [ 0.1247,  0.3643,  0.2281,  0.3333,  0.2420],\n",
       "        [ 0.0464,  0.0643,  0.2621, -0.0140, -0.3357],\n",
       "        [-0.2679,  0.1186, -0.0057,  0.0680, -0.3183],\n",
       "        [ 0.2513,  0.2763, -0.0192,  0.2784,  0.2850],\n",
       "        [-0.2071,  0.3648, -0.2017,  0.0965, -0.2182],\n",
       "        [ 0.0360,  0.1442,  0.2142,  0.1483,  0.0775],\n",
       "        [-0.1826, -0.1986, -0.2250,  0.2691,  0.1778],\n",
       "        [ 0.0243,  0.3686,  0.0827,  0.2662, -0.3841],\n",
       "        [ 0.1415,  0.1779, -0.2522, -0.0017,  0.3368],\n",
       "        [-0.1565,  0.3861,  0.2884,  0.0710,  0.0044],\n",
       "        [-0.3624,  0.2424, -0.3842,  0.3670, -0.3307],\n",
       "        [-0.2098, -0.2707, -0.0492,  0.1154,  0.2686],\n",
       "        [-0.3806,  0.0607,  0.3294,  0.1253,  0.0544],\n",
       "        [-0.3274,  0.0050,  0.2674,  0.1631,  0.1791],\n",
       "        [ 0.3784,  0.0215, -0.2735, -0.2311, -0.2277],\n",
       "        [ 0.2785,  0.3565,  0.1780,  0.3515, -0.3060],\n",
       "        [ 0.3370,  0.2554,  0.2643, -0.2294, -0.0243],\n",
       "        [-0.3900, -0.0826,  0.3686, -0.1113, -0.2340],\n",
       "        [-0.0703, -0.0797,  0.3513,  0.3304, -0.2040]], requires_grad=True)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from tutorial_utils import load_zachery\n",
    "\n",
    "# ----------- 0. load graph -------------- #\n",
    "g = load_zachery()\n",
    "print(g)\n",
    "\n",
    "# ----------- 1. node features -------------- #\n",
    "node_embed = nn.Embedding(g.number_of_nodes(), 5) # 각 노드는 5차원의 임베딩을 가지고 있습니다.\n",
    "inputs = node_embed.weight                         # 노드 피처로써 이 임베딩 가중치를 사용합니다.\n",
    "nn.init.xavier_uniform_(inputs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 학습/테스트 셋을 준비 합니다"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "일반적으로, 링크 예측 데이터셋은 *positive*와 *negative* 엣지라는 2 타입의 엣지를 포함하고 있습니다.  \n",
    "positive 엣지는 보통 그래프 내에 이미 존재하는 엣지로부터 가져옵니다.  \n",
    "이 예제에서, 50개의 임의의 엣지를 골라 테스트에 사용하고 나머지는 학습에 사용합니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 학습과 테스트를 위해 엣지 셋을 분할합니다.\n",
    "u, v = g.edges()\n",
    "eids = np.arange(g.number_of_edges())\n",
    "eids = np.random.permutation(eids)\n",
    "test_pos_u, test_pos_v = u[eids[:50]], v[eids[:50]]\n",
    "train_pos_u, train_pos_v = u[eids[50:]], v[eids[50:]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "negative 엣지의 수가 크기때문에, 보통 샘플링 해주는 것이 좋습니다.   \n",
    "적절한 negative 샘플링 알고리즘을 선택하는 방법에 대한 문제는 널리 연구되는 주제로, 이 튜토리얼의 범위를 벗어납니다.  \n",
    "우리의 예제 그래프는 상당히 작기 때문에(노드 34개뿐), 모든 결측 엣지를 나열해 임의로 50개를 테스트에 사용하고, 150개를 학습에 사용합니다.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 모든 negative 엣지를 찾아 학습과 테스트용으로 분할\n",
    "adj = sp.coo_matrix((np.ones(len(u)), (u.numpy(), v.numpy())))\n",
    "adj_neg = 1 - adj.todense() - np.eye(34)\n",
    "neg_u, neg_v = np.where(adj_neg != 0)\n",
    "neg_eids = np.random.choice(len(neg_u), 200)\n",
    "test_neg_u, test_neg_v = neg_u[neg_eids[:50]], neg_v[neg_eids[:50]]\n",
    "train_neg_u, train_neg_v = neg_u[neg_eids[50:]], neg_v[neg_eids[50:]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Put positive and negative edges together and form training and testing sets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create training set.\n",
    "train_u = torch.cat([torch.as_tensor(train_pos_u), torch.as_tensor(train_neg_u)])\n",
    "train_v = torch.cat([torch.as_tensor(train_pos_v), torch.as_tensor(train_neg_v)])\n",
    "train_label = torch.cat([torch.zeros(len(train_pos_u)), torch.ones(len(train_neg_u))])\n",
    "\n",
    "# Create testing set.\n",
    "test_u = torch.cat([torch.as_tensor(test_pos_u), torch.as_tensor(test_neg_u)])\n",
    "test_v = torch.cat([torch.as_tensor(test_pos_v), torch.as_tensor(test_neg_v)])\n",
    "test_label = torch.cat([torch.zeros(len(test_pos_u)), torch.ones(len(test_neg_u))])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## GraphSAGE 모델 정의하기\n",
    "\n",
    "우리의 모델은 2개 레이어로 구성되어 있는데, 각각 새로운 노드 표현(representation)을 이웃의 정보를 통합함으로써 계산합니다.  \n",
    "수식은 다음과 같습니다.  ([이전 튜토리얼](./3_gnn.ipynb)과 약간 다릅니다.)\n",
    "\n",
    "$$\n",
    "h_{\\mathcal{N}(v)}^k\\leftarrow \\text{AGGREGATE}_k\\{h_u^{k-1},\\forall u\\in\\mathcal{N}(v)\\}\n",
    "$$\n",
    "\n",
    "$$\n",
    "h_v^k\\leftarrow \\text{ReLU}\\left(W^k\\cdot \\text{CONCAT}(h_v^{k-1}, h_{\\mathcal{N}(v)}^k) \\right)\n",
    "$$\n",
    "\n",
    "DGL은 많은 유명한 이웃 통합(neighbor aggregation) 모듈의 구현체를 제공합니다. 모두 쉽게 한 줄의 코드로 호출하여 사용할 수 있습니다.  \n",
    "지원되는 모델의 전체 리스트는 [graph convolution modules](https://docs.dgl.ai/api/python/nn.pytorch.html#module-dgl.nn.pytorch.conv)에서 보실 수 있습니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dgl.nn import SAGEConv\n",
    "\n",
    "# ----------- 2. create model -------------- #\n",
    "# 2개의 레이어를 가진 GraphSAGE 모델 구축\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\n",
    "    \n",
    "# 주어진 차원의 모델 생성\n",
    "# 인풋 레이어 차원: 5, 노드 임베딩\n",
    "# 히든 레이어 차원: 16\n",
    "net = GraphSAGE(5, 16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "그 뒤, 모델을 아래의 손실함수를 사용해 최적화합니다.\n",
    "\n",
    "$$\n",
    "\\hat{y}_{u\\sim v} = \\sigma(h_u^T h_v)\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\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)\n",
    "$$\n",
    "\n",
    "기본적으로, 모델은 엣지의 두 끝지점(노드)의 표현을 내적함으로써 각 엣지에 대한 점수를 계산합니다.  \n",
    "그 뒤 타겟 y가 0 혹은 1인 binary cross entropy loss를 계산합니다. 여기서 0 혹은 1은 해당 엣지가 positive인지 아닌지를 나타냅니다.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In epoch 0, loss: 2.790684938430786\n",
      "In epoch 5, loss: 0.699927568435669\n",
      "In epoch 10, loss: 0.6101277470588684\n",
      "In epoch 15, loss: 0.577601969242096\n",
      "In epoch 20, loss: 0.5298259854316711\n",
      "In epoch 25, loss: 0.46006080508232117\n",
      "In epoch 30, loss: 0.3879762589931488\n",
      "In epoch 35, loss: 0.3463674783706665\n",
      "In epoch 40, loss: 0.32085341215133667\n",
      "In epoch 45, loss: 0.29568690061569214\n",
      "In epoch 50, loss: 0.27307477593421936\n",
      "In epoch 55, loss: 0.25122061371803284\n",
      "In epoch 60, loss: 0.2311725616455078\n",
      "In epoch 65, loss: 0.21075379848480225\n",
      "In epoch 70, loss: 0.19010187685489655\n",
      "In epoch 75, loss: 0.1696164608001709\n",
      "In epoch 80, loss: 0.15120071172714233\n",
      "In epoch 85, loss: 0.13269738852977753\n",
      "In epoch 90, loss: 0.11472604423761368\n",
      "In epoch 95, loss: 0.09768754243850708\n"
     ]
    }
   ],
   "source": [
    "# ----------- 3. set up loss and optimizer -------------- #\n",
    "# 이 경우, 학습 루프의 손실\n",
    "optimizer = torch.optim.Adam(itertools.chain(net.parameters(), node_embed.parameters()), lr=0.01)\n",
    "\n",
    "# ----------- 4. training -------------------------------- #\n",
    "all_logits = []\n",
    "for e in range(100):\n",
    "    # forward\n",
    "    logits = net(g, inputs)\n",
    "    pred = torch.sigmoid((logits[train_u] * logits[train_v]).sum(dim=1))\n",
    "    \n",
    "    # 손실 계산\n",
    "    loss = F.binary_cross_entropy(pred, train_label)\n",
    "    \n",
    "    # backward\n",
    "    optimizer.zero_grad()\n",
    "    loss.backward()\n",
    "    optimizer.step()\n",
    "    all_logits.append(logits.detach())\n",
    "    \n",
    "    if e % 5 == 0:\n",
    "        print('In epoch {}, loss: {}'.format(e, loss))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "결과를 확인해 봅니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accuracy 0.83\n"
     ]
    }
   ],
   "source": [
    "# ----------- 5. check results ------------------------ #\n",
    "pred = torch.sigmoid((logits[test_u] * logits[test_v]).sum(dim=1))\n",
    "print('Accuracy', ((pred >= 0.5) == test_label).sum().item() / len(pred))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}