MyAttempts/CS224W_Colab4.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CS224W_Colab4.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "machine_shape": "hm"
    },
    "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.3"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XuXWJLEm2UWS"
      },
      "source": [
        "# **CS224W - Colab 4**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8gzsP50bF6Gb"
      },
      "source": [
        "In Colab 2 we constructed GNN models by using PyTorch Geometric's built in GCN layer, `GCNConv`. In Colab 3 we implemented the  **GraphSAGE** ([Hamilton et al. (2017)](https://arxiv.org/abs/1706.02216)) layer. In this colab you'll use what you've learned and implement a more powerful layer: **GAT** ([Veličković et al. (2018)](https://arxiv.org/abs/1710.10903)). Then we will run our models on the CORA dataset, which is a standard citation network benchmark dataset.\n",
        "\n",
        "**Note**: Make sure to **sequentially run all the cells in each section** so that the intermediate variables / packages will carry over to the next cell\n",
        "\n",
        "Have fun and good luck on Colab 4 :)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MSaetj53YnT6"
      },
      "source": [
        "# Device\n",
        "We recommend using a GPU for this Colab.\n",
        "\n",
        "Please click `Runtime` and then `Change runtime type`. Then set the `hardware accelerator` to **GPU**."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "67gOQITlCNQi"
      },
      "source": [
        "## Installation"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "J_m9l6OYCQZP",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "f90137ee-f1fa-4ea5-84e1-1bf0f0ae3878"
      },
      "source": [
        "# Install torch geometric\n",
        "import os\n",
        "if 'IS_GRADESCOPE_ENV' not in os.environ:\n",
        "  !pip install torch-scatter -f https://data.pyg.org/whl/torch-1.10.0+cu113.html\n",
        "  !pip install torch-sparse -f https://data.pyg.org/whl/torch-1.10.0+cu113.html\n",
        "  !pip install torch-geometric\n",
        "  !pip install -q git+https://github.com/snap-stanford/deepsnap.git"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Looking in links: https://data.pyg.org/whl/torch-1.10.0+cu113.html\n",
            "Requirement already satisfied: torch-scatter in /usr/local/lib/python3.7/dist-packages (2.0.9)\n",
            "Looking in links: https://data.pyg.org/whl/torch-1.10.0+cu113.html\n",
            "Requirement already satisfied: torch-sparse in /usr/local/lib/python3.7/dist-packages (0.6.12)\n",
            "Requirement already satisfied: scipy in /usr/local/lib/python3.7/dist-packages (from torch-sparse) (1.4.1)\n",
            "Requirement already satisfied: numpy>=1.13.3 in /usr/local/lib/python3.7/dist-packages (from scipy->torch-sparse) (1.19.5)\n",
            "Requirement already satisfied: torch-geometric in /usr/local/lib/python3.7/dist-packages (2.0.3)\n",
            "Requirement already satisfied: networkx in /usr/local/lib/python3.7/dist-packages (from torch-geometric) (2.6.3)\n",
            "Requirement already satisfied: rdflib in /usr/local/lib/python3.7/dist-packages (from torch-geometric) (6.1.1)\n",
            "Requirement already satisfied: pandas in /usr/local/lib/python3.7/dist-packages (from torch-geometric) (1.1.5)\n",
            "Requirement already satisfied: PyYAML in /usr/local/lib/python3.7/dist-packages (from torch-geometric) (3.13)\n",
            "Requirement already satisfied: googledrivedownloader in /usr/local/lib/python3.7/dist-packages (from torch-geometric) (0.4)\n",
            "Requirement already satisfied: tqdm in /usr/local/lib/python3.7/dist-packages (from torch-geometric) (4.62.3)\n",
            "Requirement already satisfied: requests in /usr/local/lib/python3.7/dist-packages (from torch-geometric) (2.23.0)\n",
            "Requirement already satisfied: scikit-learn in /usr/local/lib/python3.7/dist-packages (from torch-geometric) (1.0.2)\n",
            "Requirement already satisfied: scipy in /usr/local/lib/python3.7/dist-packages (from torch-geometric) (1.4.1)\n",
            "Requirement already satisfied: pyparsing in /usr/local/lib/python3.7/dist-packages (from torch-geometric) (3.0.6)\n",
            "Requirement already satisfied: numpy in /usr/local/lib/python3.7/dist-packages (from torch-geometric) (1.19.5)\n",
            "Requirement already satisfied: yacs in /usr/local/lib/python3.7/dist-packages (from torch-geometric) (0.1.8)\n",
            "Requirement already satisfied: jinja2 in /usr/local/lib/python3.7/dist-packages (from torch-geometric) (2.11.3)\n",
            "Requirement already satisfied: MarkupSafe>=0.23 in /usr/local/lib/python3.7/dist-packages (from jinja2->torch-geometric) (2.0.1)\n",
            "Requirement already satisfied: pytz>=2017.2 in /usr/local/lib/python3.7/dist-packages (from pandas->torch-geometric) (2018.9)\n",
            "Requirement already satisfied: python-dateutil>=2.7.3 in /usr/local/lib/python3.7/dist-packages (from pandas->torch-geometric) (2.8.2)\n",
            "Requirement already satisfied: six>=1.5 in /usr/local/lib/python3.7/dist-packages (from python-dateutil>=2.7.3->pandas->torch-geometric) (1.15.0)\n",
            "Requirement already satisfied: isodate in /usr/local/lib/python3.7/dist-packages (from rdflib->torch-geometric) (0.6.1)\n",
            "Requirement already satisfied: setuptools in /usr/local/lib/python3.7/dist-packages (from rdflib->torch-geometric) (57.4.0)\n",
            "Requirement already satisfied: importlib-metadata in /usr/local/lib/python3.7/dist-packages (from rdflib->torch-geometric) (4.10.0)\n",
            "Requirement already satisfied: typing-extensions>=3.6.4 in /usr/local/lib/python3.7/dist-packages (from importlib-metadata->rdflib->torch-geometric) (3.10.0.2)\n",
            "Requirement already satisfied: zipp>=0.5 in /usr/local/lib/python3.7/dist-packages (from importlib-metadata->rdflib->torch-geometric) (3.7.0)\n",
            "Requirement already satisfied: chardet<4,>=3.0.2 in /usr/local/lib/python3.7/dist-packages (from requests->torch-geometric) (3.0.4)\n",
            "Requirement already satisfied: idna<3,>=2.5 in /usr/local/lib/python3.7/dist-packages (from requests->torch-geometric) (2.10)\n",
            "Requirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.7/dist-packages (from requests->torch-geometric) (2021.10.8)\n",
            "Requirement already satisfied: urllib3!=1.25.0,!=1.25.1,<1.26,>=1.21.1 in /usr/local/lib/python3.7/dist-packages (from requests->torch-geometric) (1.24.3)\n",
            "Requirement already satisfied: joblib>=0.11 in /usr/local/lib/python3.7/dist-packages (from scikit-learn->torch-geometric) (1.1.0)\n",
            "Requirement already satisfied: threadpoolctl>=2.0.0 in /usr/local/lib/python3.7/dist-packages (from scikit-learn->torch-geometric) (3.0.0)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PRfgbfTjCRD_",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 36
        },
        "outputId": "5b736531-8a2a-40b4-9214-6364ac236e4d"
      },
      "source": [
        "import torch_geometric\n",
        "torch_geometric.__version__"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'2.0.3'"
            ]
          },
          "metadata": {},
          "execution_count": 2
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZoXlf4MtYrbz"
      },
      "source": [
        "# 1) GNN Layers"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TQy2RBfgYut4"
      },
      "source": [
        "## Implementing Layer Modules\n",
        "\n",
        "In Colab 2, we implemented a GCN model for node and graph classification tasks. However, for that notebook we took advantage of PyG's built in GCN module. For Colabs 3 and 4, we provide a build upon a general Graph Neural Network Stack, into which we will be able to plugin our own module implementations: GraphSAGE and GAT.\n",
        "\n",
        "We will then use our layer implemenations to complete node classification on the CORA dataset, a standard citation network benchmark. In this dataset, nodes correspond to documents and edges correspond to undirected citations. Each node or document in the graph is assigned a class label and features based on the documents binarized bag-of-words representation. Specifically, the Cora graph has 2708 nodes, 5429 edges, 7 prediction classes, and 1433 features per node. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "H4ne6Gw-CT5G"
      },
      "source": [
        "## GNN Stack Module\n",
        "\n",
        "Below is the implementation of a general GNN stack, where we can plugin any GNN layer, such as **GraphSage**, **GAT**, etc. This module is provided for you. Your implementations of the **GraphSage** and **GAT** layers will function as components in the GNNStack Module."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ys8vZAFPCWWe"
      },
      "source": [
        "import torch\n",
        "import torch_scatter\n",
        "import torch.nn as nn\n",
        "import torch.nn.functional as F\n",
        "\n",
        "import torch_geometric.nn as pyg_nn\n",
        "import torch_geometric.utils as pyg_utils\n",
        "\n",
        "from torch import Tensor\n",
        "from typing import Union, Tuple, Optional\n",
        "from torch_geometric.typing import (OptPairTensor, Adj, Size, NoneType,\n",
        "                                    OptTensor)\n",
        "\n",
        "from torch.nn import Parameter, Linear\n",
        "from torch_sparse import SparseTensor, set_diag\n",
        "from torch_geometric.nn.conv import MessagePassing\n",
        "from torch_geometric.utils import remove_self_loops, add_self_loops, softmax, degree\n",
        "\n",
        "class GNNStack(torch.nn.Module):\n",
        "    def __init__(self, input_dim, hidden_dim, output_dim, args, emb=False):\n",
        "        super(GNNStack, self).__init__()\n",
        "        conv_model = self.build_conv_model(args.model_type)\n",
        "        self.convs = nn.ModuleList()\n",
        "        self.convs.append(conv_model(input_dim, hidden_dim))\n",
        "        assert (args.num_layers >= 1), 'Number of layers is not >=1'\n",
        "        for l in range(args.num_layers-1):\n",
        "            self.convs.append(conv_model(args.heads * hidden_dim, hidden_dim))\n",
        "\n",
        "        # post-message-passing\n",
        "        self.post_mp = nn.Sequential(\n",
        "            nn.Linear(args.heads * hidden_dim, hidden_dim), nn.Dropout(args.dropout), \n",
        "            nn.Linear(hidden_dim, output_dim))\n",
        "\n",
        "        self.dropout = args.dropout\n",
        "        self.num_layers = args.num_layers\n",
        "\n",
        "        self.emb = emb\n",
        "\n",
        "    def build_conv_model(self, model_type):\n",
        "        if model_type == 'GraphSage':\n",
        "            return GraphSage\n",
        "        elif model_type == 'GAT':\n",
        "            # When applying GAT with num heads > 1, you need to modify the \n",
        "            # input and output dimension of the conv layers (self.convs),\n",
        "            # to ensure that the input dim of the next layer is num heads\n",
        "            # multiplied by the output dim of the previous layer.\n",
        "            # HINT: In case you want to play with multiheads, you need to change the for-loop that builds up self.convs to be\n",
        "            # self.convs.append(conv_model(hidden_dim * num_heads, hidden_dim)), \n",
        "            # and also the first nn.Linear(hidden_dim * num_heads, hidden_dim) in post-message-passing.\n",
        "            return GAT\n",
        "\n",
        "    def forward(self, data):\n",
        "        x, edge_index, batch = data.x, data.edge_index, data.batch\n",
        "          \n",
        "        for i in range(self.num_layers):\n",
        "            x = self.convs[i](x, edge_index)\n",
        "            x = F.relu(x)\n",
        "            x = F.dropout(x, p=self.dropout,training=self.training)\n",
        "\n",
        "        x = self.post_mp(x)\n",
        "\n",
        "        if self.emb == True:\n",
        "            return x\n",
        "\n",
        "        return F.log_softmax(x, dim=1)\n",
        "\n",
        "    def loss(self, pred, label):\n",
        "        return F.nll_loss(pred, label)"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5nW_XpEwASNZ"
      },
      "source": [
        "## Creating Our Own Message Passing Layer\n",
        "\n",
        "Now let's start implementing our own message passing layers! Working through this part will help us become acutely familiar with the behind the scenes work of implementing Pytorch Message Passing Layers, allowing us to build our own GNN models. To do so, we will work with and implement 3 critcal functions needed to define a PyG Message Passing Layer: `forward`, `message`, and `aggregate`.\n",
        "\n",
        "Before diving head first into the coding details, let us quickly review the key components of the message passing process. To do so, we will focus on a single round of messsage passing with respect to a single central node $x$. Before message passing, $x$ is associated with a feature vector $x^{l-1}$, and the goal of message passing is to update this feature vector as $x^l$. To do so, we implement the following steps: 1) each neighboring node $v$ passes its current message $v^{l-1}$ across the edge $(x, v)$ - 2) for the node $x$, we aggregate all of the messages of the neighboring nodes (for example through a sum or mean) - and 3) we transform the aggregated information by for example applying linear and non-linear transformations. Altogether, the message passing process is applied such that every node $u$ in our graph updates its embedding by acting as the central node $x$ in step 1-3 described above. \n",
        "\n",
        "Now, we extending this process to that of a single message passing layer, the job of a message passing layer is to update the current feature representation or embedding of each node in a graph by propagating and transforming information within the graph. Overall, the general paradigm of a message passing layers is: 1) pre-processing -> 2) **message passing** / propagation -> 3) post-processing. \n",
        "\n",
        "The `forward` fuction that we will implement for our message passing layer captures this execution logic. Namely, the `forward` function handles the pre and post-processing of node features / embeddings, as well as initiates message passing by calling the `propagate` function. \n",
        "\n",
        "\n",
        "The `propagate` function encapsulates the message passing process! It does so by calling three important functions: 1) `message`, 2) `aggregate`, and 3) `update`. Our implementation will vary slightly from this, as we will not explicitly implement `update`, but instead place the logic for updating node embeddings after message passing and within the `forward` function. To be more specific, after information is propagated (message passing), we can further transform the node embeddings outputed by `propagate`. Therefore, the output of `forward` is exactly the node embeddings after one GNN layer.\n",
        "\n",
        "Lastly, before starting to implement our own layer, let us dig a bit deeper into each of the functions described above:\n",
        "\n",
        "1. \n",
        "\n",
        "```\n",
        "def propagate(edge_index, x=(x_i, x_j), extra=(extra_i, extra_j), size=size):\n",
        "```\n",
        "Calling `propagate` initiates the message passing process. Looking at the function parameters, we highlight a couple of key parameters. \n",
        "\n",
        "  - `edge_index` is passed to the forward function and captures the edge structure of the graph.\n",
        "  - `x=(x_i, x_j)` represents the node features that will be used in message passing. In order to explain why we pass the tuple `(x_i, x_j)`, we first look at how our edges are represented. For every edge $(i, j) \\in \\mathcal{E}$, we can differentiate $i$ as the source or central node ($x_{central}$) and j as the neighboring node ($x_{neighbor}$). \n",
        "  \n",
        "    Taking the example of message passing above, for a central node $u$ we will aggregate and transform all of the messages associated with the nodes $v$ s.t. $(u, v) \\in \\mathcal{E}$ (i.e. $v \\in \\mathcal{N}_{u}$). Thus we see, the subscripts `_i` and `_j` allow us to specifcally differenciate features associated with central nodes (i.e. nodes  recieving message information) and neighboring nodes (i.e. nodes passing messages). \n",
        "\n",
        "    This is definitely a somewhat confusing concept; however, one key thing to remember / wrap your head around is that depending on the perspective, a node $x$ acts as a central node or a neighboring node. In fact, in undirected graphs we store both edge directions (i.e. $(i, j)$ and $(j, i)$). From the central node perspective, `x_i`, x is collecting neighboring information to update its embedding. From a neighboring node perspective, `x_j`, x is passing its message information along the edge connecting it to a different central node.\n",
        "\n",
        "  - `extra=(extra_i, extra_j)` represents additional information that we can associate with each node beyond its current feature embedding. In fact, we can include as many additional parameters of the form `param=(param_i, param_j)` as we would like. Again, we highlight that indexing with `_i` and `_j` allows us to differentiate central and neighboring nodes. \n",
        "\n",
        "  The output of the `propagate` function is a matrix of node embeddings after the message passing process and has shape $[N, d]$.\n",
        "\n",
        "2. \n",
        "```\n",
        "def message(x_j, ...):\n",
        "```\n",
        "The `message` function is called by propagate and constructs the messages from\n",
        "neighboring nodes $j$ to central nodes $i$ for each edge $(i, j)$ in *edge_index*. This function can take any argument that was initially passed to `propagate`. Furthermore, we can again differentiate central nodes and neighboring nodes by appending `_i` or `_j` to the variable name, .e.g. `x_i` and `x_j`. Looking more specifically at the variables, we have:\n",
        "\n",
        "  - `x_j` represents a matrix of feature embeddings for all neighboring nodes passing their messages along their respective edge (i.e. all nodes $j$ for edges $(i, j) \\in \\mathcal{E}$). Thus, its shape is $[|\\mathcal{E}|, d]$!\n",
        "  - In implementing GAT we will see how to access additional variables passed to propagate\n",
        "\n",
        "  Critically, we see that the output of the `message` function is a matrix of neighboring node embeddings ready to be aggregated, having shape $[|\\mathcal{E}|, d]$.\n",
        "\n",
        "3. \n",
        "```\n",
        "def aggregate(self, inputs, index, dim_size = None):\n",
        "```\n",
        "Lastly, the `aggregate` function is used to aggregate the messages from neighboring nodes. Looking at the parameters we highlight:\n",
        "\n",
        "  - `inputs` represents a matrix of the messages passed from neighboring nodes (i.e. the output of the `message` function).\n",
        "  - `index` has the same shape as `inputs` and tells us the central node that corresponding to each of the rows / messages $j$ in the `inputs` matrix. Thus, `index` tells us which rows / messages to aggregate for each central node.\n",
        "\n",
        "  The output of `aggregate` is of shape $[N, d]$.\n",
        "\n",
        "\n",
        "For additional resources refer to the PyG documentation for implementing custom message passing layers: https://pytorch-geometric.readthedocs.io/en/latest/notes/create_gnn.html"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qjcfF3RACdLD"
      },
      "source": [
        "## GAT Implementation\n",
        "\n",
        "Attention mechanisms have become the state-of-the-art in many sequence-based tasks such as machine translation and learning sentence representations. One of the major benefits of attention-based mechanisms is their ability to focus on the most relevant parts of the input to make decisions. In this problem, we will see how attention mechanisms can be used to perform node classification over graph-structured data through the usage of Graph Attention Networks (GATs) ([Veličković et al. (2018)](https://arxiv.org/abs/1710.10903)).\n",
        "\n",
        "The building block of the Graph Attention Network is the graph attention layer, which is a variant of the aggregation function. Let $N$ be the number of nodes and $F$ be the dimension of the feature vector for each node. The input to each graph attentional layer is a set of node features: $\\mathbf{h} = \\{\\overrightarrow{h_1}, \\overrightarrow{h_2}, \\dots, \\overrightarrow{h_N}$\\}, $\\overrightarrow{h_i} \\in R^F$. The output of each graph attentional layer is a new set of node features, which may have a new dimension $F'$: $\\mathbf{h'} = \\{\\overrightarrow{h_1'}, \\overrightarrow{h_2'}, \\dots, \\overrightarrow{h_N'}\\}$, with $\\overrightarrow{h_i'} \\in \\mathbb{R}^{F'}$.\n",
        "\n",
        "We will now describe how this transformation is performed for each graph attention layer. First, a shared linear transformation parametrized by the weight matrix $\\mathbf{W} \\in \\mathbb{R}^{F' \\times F}$ is applied to every node. \n",
        "\n",
        "Next, we perform self-attention on the nodes. We use a shared attention function $a$:\n",
        "\\begin{equation} \n",
        "a : \\mathbb{R}^{F'} \\times \\mathbb{R}^{F'} \\rightarrow \\mathbb{R}.\n",
        "\\end{equation}\n",
        "\n",
        "that computes the attention coefficients capturing the importance of node $j$'s features to node $i$:\n",
        "\\begin{equation}\n",
        "e_{ij} = a(\\mathbf{W_l}\\overrightarrow{h_i}, \\mathbf{W_r} \\overrightarrow{h_j})\n",
        "\\end{equation}\n",
        "\n",
        "The most general formulation of self-attention allows every node to attend to all other nodes which drops all structural information. However, to utilize graph structure in the attention mechanisms, we use **masked attention**. In masked attention, we only compute attention coefficients $e_{ij}$ for nodes $j \\in \\mathcal{N}_i$ where $\\mathcal{N}_i$ is some neighborhood of node $i$ in the graph.\n",
        "\n",
        "To easily compare coefficients across different nodes, we normalize the coefficients across $j$ using a softmax function:\n",
        "\\begin{equation}\n",
        "\\alpha_{ij} = \\text{softmax}_j(e_{ij}) = \\frac{\\exp(e_{ij})}{\\sum_{k \\in \\mathcal{N}_i} \\exp(e_{ik})}\n",
        "\\end{equation}\n",
        "\n",
        "For this problem, our attention mechanism $a$ will be a single-layer feedforward neural network parametrized by a weight vectors $\\overrightarrow{a_l} \\in \\mathbb{R}^{F'}$ and $\\overrightarrow{a_r} \\in \\mathbb{R}^{F'}$, followed by a LeakyReLU nonlinearity (with negative input slope 0.2). Let $\\cdot^T$ represent transposition and $||$ represent concatenation. The coefficients computed by our attention mechanism may be expressed as:\n",
        "\n",
        "\\begin{equation}\n",
        "\\alpha_{ij} = \\frac{\\exp\\Big(\\text{LeakyReLU}\\Big(\\overrightarrow{a_l}^T \\mathbf{W_l} \\overrightarrow{h_i} + \\overrightarrow{a_r}^T\\mathbf{W_r}\\overrightarrow{h_j}\\Big)\\Big)}{\\sum_{k\\in \\mathcal{N}_i} \\exp\\Big(\\text{LeakyReLU}\\Big(\\overrightarrow{a_l}^T \\mathbf{W_l} \\overrightarrow{h_i} + \\overrightarrow{a_r}^T\\mathbf{W_r}\\overrightarrow{h_k}\\Big)\\Big)}\n",
        "\\end{equation}\n",
        "\n",
        "For the following questions, we denote `alpha_l` = $\\alpha_l = [...,\\overrightarrow{a_l}^T \\mathbf{W_l} \\overrightarrow{h_i},...] \\in \\mathcal{R}^n$ and `alpha_r` = $\\alpha_r = [..., \\overrightarrow{a_r}^T \\mathbf{W_r} \\overrightarrow{h_j}, ...] \\in \\mathcal{R}^n$.\n",
        "\n",
        "\n",
        "At every layer of GAT, after the attention coefficients are computed for that layer, the aggregation function can be computed by a weighted sum of neighborhood messages, where weights are specified by $\\alpha_{ij}$.\n",
        "\n",
        "Now, we use the normalized attention coefficients to compute a linear combination of the features corresponding to them. These aggregated features will serve as the final output features for every node.\n",
        "\n",
        "\\begin{equation}\n",
        "h_i' = \\sum_{j \\in \\mathcal{N}_i} \\alpha_{ij} \\mathbf{W_r} \\overrightarrow{h_j}.\n",
        "\\end{equation}\n",
        "\n",
        "At this point, we have covered a lot of information! Before reading further about multi-head attention, we encourage you to go again through the excersize of thinking about what components of the attention mechanism correspond with the different functions: 1) `forward`, 2) `message`, and 3 `aggregate`. \n",
        "\n",
        "- Hint 1: Our aggregation is very similar to that of GraphSage except now we are using sum aggregation\n",
        "- Hint 2: The terms we aggregate over again represent the individual message that each neighbor node j sends. Thus, we see that $\\alpha_{ij}$ is part of the message each node sends and is thus computed during the message step. This makes sense since an attention weight is associated with each edge in the graph.\n",
        "- Hint 3: Look at the terms in the definition of $\\alpha_{ij}$. What values do we want to pre-process and pass as parameters to the `propagate` function. The parameters of `message(..., x_j, alpha_j, alpha_i, ...)` should give a good hint.  \n",
        "\n",
        "### Multi-Head Attention\n",
        "To stabilize the learning process of self-attention, we use multi-head attention. To do this we use $K$ independent attention mechanisms, or ``heads'' compute output features as in the above equations. Then, we concatenate these output feature representations:\n",
        "\n",
        "\\begin{equation}\n",
        "    \\overrightarrow{h_i}' = ||_{k=1}^K \\Big(\\sum_{j \\in \\mathcal{N}_i} \\alpha_{ij}^{(k)} \\mathbf{W_r}^{(k)} \\overrightarrow{h_j}\\Big)\n",
        "\\end{equation}\n",
        "\n",
        "where $||$ is concentation, $\\alpha_{ij}^{(k)}$ are the normalized attention coefficients computed by the $k$-th attention mechanism $(a^k)$, and $\\mathbf{W}^{(k)}$ is the corresponding input linear transformation's weight matrix. Note that for this setting, $\\mathbf{h'} \\in \\mathbb{R}^{KF'}$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "w4j45gTpCeXO"
      },
      "source": [
        "class GAT(MessagePassing):\n",
        "\n",
        "    def __init__(self, in_channels, out_channels, heads = 2,\n",
        "                 negative_slope = 0.2, dropout = 0., **kwargs):\n",
        "        super(GAT, self).__init__(node_dim=0, **kwargs)\n",
        "\n",
        "        self.in_channels = in_channels\n",
        "        self.out_channels = out_channels\n",
        "        self.heads = heads\n",
        "        self.negative_slope = negative_slope\n",
        "        self.dropout = dropout\n",
        "\n",
        "        self.lin_l = None\n",
        "        self.lin_r = None\n",
        "        self.att_l = None\n",
        "        self.att_r = None\n",
        "\n",
        "        ############################################################################\n",
        "        # TODO: Your code here! \n",
        "        # Define the layers needed for the message functions below.\n",
        "        # self.lin_l is the linear transformation that you apply to embeddings \n",
        "        # BEFORE message passing.\n",
        "        # \n",
        "        # Pay attention to dimensions of the linear layers, since we're using \n",
        "        # multi-head attention.\n",
        "        # Our implementation is ~1 lines, but don't worry if you deviate from this.\n",
        "        self.lin_l = Linear(in_channels, out_channels*self.heads)\n",
        "        ############################################################################\n",
        "\n",
        "        self.lin_r = self.lin_l\n",
        "\n",
        "        ############################################################################\n",
        "        # TODO: Your code here! \n",
        "        # Define the attention parameters \\overrightarrow{a_l/r}^T in the above intro.\n",
        "        # You have to deal with multi-head scenarios.\n",
        "        # Use nn.Parameter instead of nn.Linear\n",
        "        # Our implementation is ~2 lines, but don't worry if you deviate from this.\n",
        "        self.att_l = Parameter(torch.Tensor(1, self.heads, out_channels))\n",
        "        self.att_r = Parameter(torch.Tensor(1, self.heads, out_channels))\n",
        "        ############################################################################\n",
        "\n",
        "        self.reset_parameters()\n",
        "\n",
        "    def reset_parameters(self):\n",
        "        nn.init.xavier_uniform_(self.lin_l.weight)\n",
        "        nn.init.xavier_uniform_(self.lin_r.weight)\n",
        "        nn.init.xavier_uniform_(self.att_l)\n",
        "        nn.init.xavier_uniform_(self.att_r)\n",
        "\n",
        "    def forward(self, x, edge_index, size = None):\n",
        "        \n",
        "        H, C = self.heads, self.out_channels\n",
        "\n",
        "        ############################################################################\n",
        "        # TODO: Your code here! \n",
        "        # Implement message passing, as well as any pre- and post-processing (our update rule).\n",
        "        # 1. First apply linear transformation to node embeddings, and split that \n",
        "        #    into multiple heads. We use the same representations for source and\n",
        "        #    target nodes, but apply different linear weights (W_l and W_r)\n",
        "        # 2. Calculate alpha vectors for central nodes (alpha_l) and neighbor nodes (alpha_r).\n",
        "        # 3. Call propagate function to conduct the message passing. \n",
        "        #    3.1 Remember to pass alpha = (alpha_l, alpha_r) as a parameter.\n",
        "        #    3.2 See there for more information: https://pytorch-geometric.readthedocs.io/en/latest/notes/create_gnn.html\n",
        "        # 4. Transform the output back to the shape of [N, H * C].\n",
        "        # Our implementation is ~5 lines, but don't worry if you deviate from this.\n",
        "\n",
        "        # print(f\"\\n========Forward========\")\n",
        "        # print(f\"x shape: {x.shape}\")\n",
        "        # print(f\"Edge index shape {edge_index.shape}\")\n",
        "        # print(f\"att_l shape: {self.att_l.shape}\")\n",
        "        # print(f\"att_r shape: {self.att_r.shape}\")\n",
        "\n",
        "\n",
        "        wh_l = self.lin_l(x).view(-1, H, C)\n",
        "        wh_r = self.lin_r(x).view(-1, H, C)\n",
        "        # print(f\"whl shape: {wh_l.shape}\")\n",
        "        # print(f\"whr shape: {wh_r.shape}\")\n",
        "\n",
        "        alpha_l = torch.mul(self.att_l, wh_l)\n",
        "        alpha_r = torch.mul(self.att_r, wh_r)\n",
        "        # print(f\"alpha_l shape: {alpha_l.shape}\")\n",
        "        # print(f\"alpha_r shape: {alpha_r.shape}\")\n",
        "\n",
        "        out = self.propagate(edge_index,x=(wh_l, wh_r), size=size, alpha=(alpha_l, alpha_r))\n",
        "        # print(f\"Shape of propagate out: {out.shape}\")\n",
        "\n",
        "        out = out.view(-1, H*C)\n",
        "        # print(f\"Shape of out after shape transformation to [N, H*C]: {out.shape}\")\n",
        "        ############################################################################\n",
        "\n",
        "        return out\n",
        "\n",
        "\n",
        "    def message(self, x_j, alpha_j, alpha_i, index, ptr, size_i):\n",
        "\n",
        "        ############################################################################\n",
        "        # TODO: Your code here! \n",
        "        # Implement your message function. Putting the attention in message \n",
        "        # instead of in update is a little tricky.\n",
        "        # 1. Calculate the final attention weights using alpha_i and alpha_j,\n",
        "        #    and apply leaky Relu.\n",
        "        # 2. Calculate softmax over the neighbor nodes for all the nodes. Use \n",
        "        #    torch_geometric.utils.softmax instead of the one in Pytorch.\n",
        "        # 3. Apply dropout to attention weights (alpha).\n",
        "        # 4. Multiply embeddings and attention weights. As a sanity check, the output\n",
        "        #    should be of shape [E, H, C].\n",
        "        # 5. ptr (LongTensor, optional): If given, computes the softmax based on\n",
        "        #    sorted inputs in CSR representation. You can simply pass it to softmax.\n",
        "        # Our implementation is ~4-5 lines, but don't worry if you deviate from this.\n",
        "\n",
        "        # print(f\"\\n========Message funnction========\")\n",
        "        # print(f\"x_j shape: {x_j.shape}\")\n",
        "        # print(f\"Alpha_j shape: {alpha_j.shape}\")\n",
        "        # print(f\"Alpha_i shape: {alpha_i.shape}\")\n",
        "        # print(f\"Index: {index.shape}\")\n",
        "        # print(f\"ptr shape: {ptr}\")\n",
        "        # print(f\"size_i: {size_i}\")\n",
        "\n",
        "        att = alpha_i + alpha_j\n",
        "        # print(f\"att shape: {att.shape}\")\n",
        "\n",
        "        att = F.leaky_relu(att, negative_slope=self.negative_slope)\n",
        "        att = softmax(att, ptr if ptr else index)\n",
        "        att = F.dropout(att, self.dropout)\n",
        "        # print(f\"att shape before mull: {att.shape}\")\n",
        "\n",
        "        out = torch.mul(x_j, att)\n",
        "        # print(f\"out shape from message function should be [E, H, C]: {out.shape}\")\n",
        "\n",
        "        ############################################################################\n",
        "\n",
        "        return out\n",
        "\n",
        "\n",
        "    def aggregate(self, inputs, index, dim_size = None):\n",
        "\n",
        "        ############################################################################\n",
        "        # TODO: Your code here! \n",
        "        # Implement your aggregate function here.\n",
        "        # See here as how to use torch_scatter.scatter: https://pytorch-scatter.readthedocs.io/en/latest/_modules/torch_scatter/scatter.html\n",
        "        # Pay attention to \"reduce\" parameter is different from that in GraphSage.\n",
        "        # Our implementation is ~1 lines, but don't worry if you deviate from this.\n",
        "        out = torch_scatter.scatter(inputs, index = index, dim = self.node_dim, dim_size = dim_size, reduce = \"sum\")\n",
        "        ############################################################################\n",
        "    \n",
        "        return out"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "V2dkgSuWCheU"
      },
      "source": [
        "## Building Optimizers\n",
        "\n",
        "This function has been implemented for you. **For grading purposes please use the default Adam optimizer**, but feel free to play with other types of optimizers on your own."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "f_TIQ8NPCjBP"
      },
      "source": [
        "import torch.optim as optim\n",
        "\n",
        "def build_optimizer(args, params):\n",
        "    weight_decay = args.weight_decay\n",
        "    filter_fn = filter(lambda p : p.requires_grad, params)\n",
        "    if args.opt == 'adam':\n",
        "        optimizer = optim.Adam(filter_fn, lr=args.lr, weight_decay=weight_decay)\n",
        "    elif args.opt == 'sgd':\n",
        "        optimizer = optim.SGD(filter_fn, lr=args.lr, momentum=0.95, weight_decay=weight_decay)\n",
        "    elif args.opt == 'rmsprop':\n",
        "        optimizer = optim.RMSprop(filter_fn, lr=args.lr, weight_decay=weight_decay)\n",
        "    elif args.opt == 'adagrad':\n",
        "        optimizer = optim.Adagrad(filter_fn, lr=args.lr, weight_decay=weight_decay)\n",
        "    if args.opt_scheduler == 'none':\n",
        "        return None, optimizer\n",
        "    elif args.opt_scheduler == 'step':\n",
        "        scheduler = optim.lr_scheduler.StepLR(optimizer, step_size=args.opt_decay_step, gamma=args.opt_decay_rate)\n",
        "    elif args.opt_scheduler == 'cos':\n",
        "        scheduler = optim.lr_scheduler.CosineAnnealingLR(optimizer, T_max=args.opt_restart)\n",
        "    return scheduler, optimizer"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hBYdWFwYCkwY"
      },
      "source": [
        "## Training and Testing\n",
        "\n",
        "Here we provide you with the functions to train and test. **Please do not modify this part for grading purposes.**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_tZMWRc8CmGg"
      },
      "source": [
        "import time\n",
        "\n",
        "import networkx as nx\n",
        "import numpy as np\n",
        "import torch\n",
        "import torch.optim as optim\n",
        "from tqdm import trange\n",
        "import pandas as pd\n",
        "import copy\n",
        "\n",
        "from torch_geometric.datasets import TUDataset\n",
        "from torch_geometric.datasets import Planetoid\n",
        "from torch_geometric.data import DataLoader\n",
        "\n",
        "import torch_geometric.nn as pyg_nn\n",
        "\n",
        "import matplotlib.pyplot as plt\n",
        "\n",
        "\n",
        "def train(dataset, args):\n",
        "    \n",
        "    print(\"Node task. test set size:\", np.sum(dataset[0]['test_mask'].numpy()))\n",
        "    print()\n",
        "    test_loader = loader = DataLoader(dataset, batch_size=args.batch_size, shuffle=False)\n",
        "\n",
        "    # build model\n",
        "    model = GNNStack(dataset.num_node_features, args.hidden_dim, dataset.num_classes, \n",
        "                            args)\n",
        "    scheduler, opt = build_optimizer(args, model.parameters())\n",
        "\n",
        "    # train\n",
        "    losses = []\n",
        "    test_accs = []\n",
        "    best_acc = 0\n",
        "    best_model = None\n",
        "    for epoch in trange(args.epochs, desc=\"Training\", unit=\"Epochs\"):\n",
        "        total_loss = 0\n",
        "        model.train()\n",
        "        for batch in loader:\n",
        "            opt.zero_grad()\n",
        "            pred = model(batch)\n",
        "            label = batch.y\n",
        "            pred = pred[batch.train_mask]\n",
        "            label = label[batch.train_mask]\n",
        "            loss = model.loss(pred, label)\n",
        "            loss.backward()\n",
        "            opt.step()\n",
        "            total_loss += loss.item() * batch.num_graphs\n",
        "        total_loss /= len(loader.dataset)\n",
        "        losses.append(total_loss)\n",
        "\n",
        "        if epoch % 10 == 0:\n",
        "          test_acc = test(test_loader, model)\n",
        "          test_accs.append(test_acc)\n",
        "          if test_acc > best_acc:\n",
        "            best_acc = test_acc\n",
        "            best_model = copy.deepcopy(model)\n",
        "        else:\n",
        "          test_accs.append(test_accs[-1])\n",
        "    \n",
        "    return test_accs, losses, best_model, best_acc, test_loader\n",
        "\n",
        "def test(loader, test_model, is_validation=False, save_model_preds=False, model_type=None):\n",
        "    test_model.eval()\n",
        "\n",
        "    correct = 0\n",
        "    # Note that Cora is only one graph!\n",
        "    for data in loader:\n",
        "        with torch.no_grad():\n",
        "            # max(dim=1) returns values, indices tuple; only need indices\n",
        "            pred = test_model(data).max(dim=1)[1]\n",
        "            label = data.y\n",
        "\n",
        "        mask = data.val_mask if is_validation else data.test_mask\n",
        "        # node classification: only evaluate on nodes in test set\n",
        "        pred = pred[mask]\n",
        "        label = label[mask]\n",
        "\n",
        "        if save_model_preds:\n",
        "          print (\"Saving Model Predictions for Model Type\", model_type)\n",
        "\n",
        "          data = {}\n",
        "          data['pred'] = pred.view(-1).cpu().detach().numpy()\n",
        "          data['label'] = label.view(-1).cpu().detach().numpy()\n",
        "\n",
        "          df = pd.DataFrame(data=data)\n",
        "          # Save locally as csv\n",
        "          df.to_csv('CORA-Node-' + model_type + '.csv', sep=',', index=False)\n",
        "            \n",
        "        correct += pred.eq(label).sum().item()\n",
        "\n",
        "    total = 0\n",
        "    for data in loader.dataset:\n",
        "        total += torch.sum(data.val_mask if is_validation else data.test_mask).item()\n",
        "\n",
        "    return correct / total\n",
        "  \n",
        "class objectview(object):\n",
        "    def __init__(self, d):\n",
        "        self.__dict__ = d\n"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "L7-h7jIsCns4"
      },
      "source": [
        "## Let's Start the Training!\n",
        "\n",
        "We will be working on the CORA dataset on node-level classification.\n",
        "\n",
        "This part is implemented for you. **For grading purposes, please do not modify the default parameters.** However, feel free to play with different configurations just for fun!\n",
        "\n",
        "**Submit your best accuracy and loss on Gradescope.**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qe9B45l9Cpz2",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 437
        },
        "outputId": "837042a8-f4c9-49fd-a3fa-68a8758799a1"
      },
      "source": [
        "if 'IS_GRADESCOPE_ENV' not in os.environ:\n",
        "    for args in [\n",
        "        {'model_type': 'GAT', 'dataset': 'cora', 'num_layers': 2, 'heads': 1, 'batch_size': 32, 'hidden_dim': 32, 'dropout': 0.5, 'epochs': 500, 'opt': 'adam', 'opt_scheduler': 'none', 'opt_restart': 0, 'weight_decay': 5e-3, 'lr': 0.01},\n",
        "    ]:\n",
        "        args = objectview(args)\n",
        "        for model in ['GAT']:\n",
        "            args.model_type = model\n",
        "\n",
        "            # Match the dimension.\n",
        "            if model == 'GAT':\n",
        "              args.heads = 2\n",
        "            else:\n",
        "              args.heads = 1\n",
        "\n",
        "            if args.dataset == 'cora':\n",
        "                dataset = Planetoid(root='/tmp/cora', name='Cora')\n",
        "            else:\n",
        "                raise NotImplementedError(\"Unknown dataset\") \n",
        "            test_accs, losses, best_model, best_acc, test_loader = train(dataset, args) \n",
        "\n",
        "            print(\"Maximum test set accuracy: {0}\".format(max(test_accs)))\n",
        "            print(\"Minimum loss: {0}\".format(min(losses)))\n",
        "\n",
        "            # Run test for our best model to save the predictions!\n",
        "            test(test_loader, best_model, is_validation=False, save_model_preds=True, model_type=model)\n",
        "            print()\n",
        "\n",
        "            plt.title(dataset.name)\n",
        "            plt.plot(losses, label=\"training loss\" + \" - \" + args.model_type)\n",
        "            plt.plot(test_accs, label=\"test accuracy\" + \" - \" + args.model_type)\n",
        "        plt.legend()\n",
        "        plt.show()\n"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "/usr/local/lib/python3.7/dist-packages/torch_geometric/deprecation.py:13: UserWarning: 'data.DataLoader' is deprecated, use 'loader.DataLoader' instead\n",
            "  warnings.warn(out)\n"
          ]
        },
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Node task. test set size: 1000\n",
            "\n"
          ]
        },
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "Training: 100%|██████████| 500/500 [01:27<00:00,  5.72Epochs/s]\n"
          ]
        },
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Maximum test set accuracy: 0.8\n",
            "Minimum loss: 0.03517598286271095\n",
            "Saving Model Predictions for Model Type GAT\n",
            "\n"
          ]
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAEICAYAAABRSj9aAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3deXxU1fn48c+TZJIQEtYE2UkUlJ2AEVREQRRQWxS1ilpFvyr9WbGtfmsFtai0tvZra60biohWa8GVRQRZBBTZwxp2AgRIgGyQfZ2Z8/vjToaZZAIDCQRmnvfrNa+ZOXeZc2fuPPfcc889R4wxKKWUClwhDZ0BpZRSZ5cGeqWUCnAa6JVSKsBpoFdKqQCngV4ppQKcBnqllApwGuiVUirAaaBXQU9E7hWRZBEpEpEjIjJfRK5p6HwpVV800KugJiJPAa8DfwEuAjoC7wC3nuZ6wuo/d0rVDw30KmiJSFNgEvC4MeZrY0yxMabSGPONMeZpEYkQkddF5LDr8bqIRLiWHSwi6SLyjIgcBT4UkeYiMldEskXkuOt1+wbdSKXQQK+C21VAJDCzlunPAVcCiUAfoD/wvMf01kALoBMwFuv/9KHrfUegFHjrbGRcqdMh2teNClYich/wD2NM61qm7wWeMMbMc70fDrxnjIkXkcHAQqCJMaasluUTgaXGmOZnZQOU8pPWK6pglgvEikiYMcbuY3pb4IDH+wOutCrZnkFeRKKAfwIjgKrgHiMiocYYR/1mXSn/adWNCmargHLgtlqmH8aqhqnS0ZVWpfrp8P8ClwEDjDFNgGtd6VL3rCp15rREr4KWMSZfRCYCb4uIHasqphK4ARgCTAeeF5F1WEF9IvCfk6wyBqtePk9EWgAvnM38K+UvLdGroGaM+QfwFNZF1mzgEDAOmAX8GUgGtgApwAZXWm1eBxoBOcBq4LuzlnGlToNejFVKqQCnJXqllApwGuiVUirAaaBXSqkAp4FeKaUC3HnZvDI2NtbEx8c3dDaUUuqCsX79+hxjTJyvaedloI+Pjyc5Obmhs6GUUhcMETlQ27RTVt2ISAcRWSoi20Vkm4j81sc8IiJviEiqiGwRkX4e08aIyB7XY8yZb4ZSSqkz4U+J3g78rzFmg4jEAOtFZJExZrvHPDcBXVyPAcBkYIDH3YFJWHcWrheROcaY4/W6FUoppWp1yhK9MeaIMWaD63UhsANoV222W4GPjWU10ExE2gDDgUXGmGOu4L4Iq8MnpZRS58hp1dGLSDzQF1hTbVI7rFvHq6S70mpL97XusVh9etOxY8fTyZZSAa2yspL09HTKynz2hqyCTGRkJO3bt8dms/m9jN+BXkSiga+A3xljCs4gfydljJkCTAFISkrSfhmUcklPTycmJob4+HhEtCPMYGaMITc3l/T0dBISEvxezq929CJiwwrynxpjvvYxSwbQweN9e1dabelKKT+VlZXRsmVLDfIKEaFly5anfXbnT6sbAT4AdhhjXqtltjnAA67WN1cC+caYI8ACYJhrLM3mwDBXmlLqNGiQV1XOZF/wp+pmIHA/kCIim1xpz2INwoAx5l1gHnAzkAqUAA+5ph0TkT8B61zLTTLGHDvtXPqh3O7g3yvT6NuxOVfEtzgbH6GUUhckf1rd/GSMEWNMb2NMousxzxjzrivI42pt87gx5hJjTC9jTLLH8tOMMZ1djw/P1oYYA9N+SuOv83agXS8rVX/y8vJ45513zmjZm2++mby8vJPOM3HiRBYvXnxG668uPj6enJycelnX6Xjttdfo2rUrvXr1ok+fPjz11FNUVla6p2/atAkR4bvvrCEKRo0aRWJiIp07d6Zp06YkJiaSmJjIypUrz0r+Aqavm0hbKL8ecgkbDuaxK7OwobOjVMA4WaC3230NtXvCvHnzaNas2UnnmTRpEjfccMMZ56+hvfvuuyxcuJDVq1eTkpLCunXraNWqFaWlpe55pk+fzjXXXMP06dMBmDlzJps2bWLq1KkMGjSITZs2sWnTJq6++uqzkseACfQAAxJaArDziAZ6perL+PHj2bt3L4mJiTz99NMsW7aMQYMGMXLkSLp37w7AbbfdxuWXX06PHj2YMmWKe9mqEnZaWhrdunXj0UcfpUePHgwbNswdCB988EG+/PJL9/wvvPAC/fr1o1evXuzcuROA7OxsbrzxRnr06MEjjzxCp06dTllyf+211+jZsyc9e/bk9ddfB6C4uJhbbrmFPn360LNnTz777DP3Nnbv3p3evXvz+9///rS+n5dffpnJkye7D2jh4eGMHz+eJk2aAFZLmS+++IKPPvqIRYsWNUgz2fOyr5szdXFcY2yhws6jGuhVYHrpm21sP1y/rZu7t23CCz/vUev0V155ha1bt7Jpk3WJbtmyZWzYsIGtW7e6m/hNmzaNFi1aUFpayhVXXMEdd9xBy5YtvdazZ88epk+fzvvvv89dd93FV199xS9/+csanxcbG8uGDRt45513+Pvf/87UqVN56aWXuP7665kwYQLfffcdH3zwwUm3af369Xz44YesWbMGYwwDBgzguuuuY9++fbRt25Zvv/0WgPz8fHJzc5k5cyY7d+5ERE5Z1eSpoKCAoqKikzZ1XLlyJQkJCVxyySUMHjyYb7/9ljvuuMPvz6gPAVWit4WGcElcNDuO1Hszf6WUh/79+3sFtzfeeIM+ffpw5ZVXcujQIfbs2VNjmYSEBBITEwG4/PLLSUtL87nu22+/vcY8P/30E6NHjwZgxIgRNG/e/KT5++mnnxg1ahSNGzcmOjqa22+/neXLl9OrVy8WLVrEM888w/Lly2natClNmzYlMjKShx9+mK+//pqoqKjT/TrcFixYQGJiIvHx8e769unTp7vzPnr0aHf1zbkUUCV6gKsvieU/qw+QV1JBs6jwhs6OUvXqZCXvc6lx48bu18uWLWPx4sWsWrWKqKgoBg8e7LN6IiIiwv06NDTUqw7b13yhoaGnvAZwui699FI2bNjAvHnzeP755xk6dCgTJ05k7dq1fP/993z55Ze89dZbLFmyxGu54cOHk5mZSVJSElOnTnWnN2nShOjoaPbv309CQgLDhw9n+PDh/OxnP6OiogKHw8FXX33F7Nmzefnll903PBUWFhITE1Ov23YyAVWiBxjVtx0VDidLd2U1dFaUCggxMTEUFtZeHZqfn0/z5s2Jiopi586drF69ut7zMHDgQD7//HMAFi5cyPHjJ+8XcdCgQcyaNYuSkhKKi4uZOXMmgwYN4vDhw0RFRfHLX/6Sp59+mg0bNlBUVER+fj4333wz//znP9m8eXON9S1YsMB98bS6CRMm8Nhjj7mrfIwx7gPd999/T+/evTl06BBpaWkcOHCAO+64g5kzZ9b1KzktAVeiv6SVVdI4ml/ewDlRKjC0bNmSgQMH0rNnT2666SZuueUWr+kjRozg3XffpVu3blx22WVceeWV9Z6HF154gXvuuYdPPvmEq666itatW5+0RNyvXz8efPBB+vfvD8AjjzxC3759WbBgAU8//TQhISHYbDYmT55MYWEht956K2VlZRhjeO212u4L9e2xxx6juLiYAQMGEBERQXR0NAMHDqRv37787ne/Y9SoUV7z33HHHUyePJkHHnjg9L+IMyTnY5vzpKQkU5eBR3pM/I67r+jIxJ93r8dcKdUwduzYQbdu3Ro6Gw2qvLyc0NBQwsLCWLVqFY899pj74nAw8rVPiMh6Y0ySr/kDrkQPEBsTQU6RluiVChQHDx7krrvuwul0Eh4ezvvvv9/QWbqgBGagj44gu1ADvVKBokuXLmzcuLGhs3HBCriLsQBx0VqiV0qpKgEZ6GNjwjXQK6WUS0AG+rjoSI6XVFLpcDZ0VpRSqsEFZKCPjbFulMotqmjgnCilVMMLzEAfbd1Zpxdklaq7unRTDPD6669TUlJSjzm6MNjtdp599lm6dOni7ob45Zdf9ppn1qxZiIi787YBAwaQmJhIx44diYuLcy9XW3cR/grIQB8XYwV6radXqu4CIdDXd1cK/nj++ec5fPgwKSkpbNq0ieXLl3v1UQ81uy9es2YNmzZtYtKkSdx9993u7ovj4+PrlBd/hhKcJiJZIrK1lulPi8gm12OriDhEpIVrWpqIpLimnfkdUKcprqpEr4FeqTqr3k0xwKuvvsoVV1xB7969eeGFFwDfXQC/8cYbHD58mCFDhjBkyJAa6540aRJXXHEFPXv2ZOzYse5Bg1JTU7nhhhvo06cP/fr1Y+/evQD87W9/cw/uMX78eAAGDx5M1Q2WOTk57qD40UcfMXLkSK6//nqGDh1KUVERQ4cOdXeBPHv2bHc+Pv74Y3r37k2fPn24//77KSwsJCEhwR2YCwoKvN6fSklJCe+//z5vvvkmkZGRgNWVxIsvvuiep6ioiJ9++okPPviAGTNm+LXeM+VPO/qPgLeAj31NNMa8CrwKICI/B56sNlzgEGPMOR3yRatuVMCaPx6OptTvOlv3gpteqXVy9W6KFy5cyJ49e1i7di3GGEaOHMmPP/5IdnZ2jS6AmzZtymuvvcbSpUuJjY2tse5x48YxceJEAO6//37mzp3Lz3/+c+677z7Gjx/PqFGjKCsrw+l0Mn/+fGbPns2aNWuIiori2LFTj0q6YcMGtmzZQosWLbDb7cycOZMmTZqQk5PDlVdeyciRI9m+fTt//vOfWblyJbGxsRw7doyYmBh3l8K33XYbM2bM4Pbbb8dms/n1laamptKxY8eTdtMwe/ZsRowYwaWXXkrLli1Zv349l19+uV/rP13+DCX4I+DvOK/3AOe+D85qGoWHEh0RplU3Sp0FCxcuZOHChfTt25d+/fqxc+dO9uzZ47ML4FNZunQpAwYMoFevXixZsoRt27ZRWFhIRkaGu4+YyMhIoqKiWLx4MQ899JC7G+EWLU49NvSNN97ons8Yw7PPPkvv3r254YYbyMjIIDMzkyVLlvCLX/zCfSCqmv+RRx7hww+t0U8//PBDHnroodP/slw+/PBDEhMT6dChA4cOHQLObffF9XZnrIhEASOAcR7JBlgoIgZ4zxgzxefCZ0HTRjbyS/w7zVLqgnGSkve5YoxhwoQJ/OpXv6oxzVcXwLUpKyvj17/+NcnJyXTo0IEXX3zxjEZfCgsLw+l0utfpybM75U8//ZTs7GzWr1+PzWYjPj7+pJ83cOBA0tLSWLZsGQ6Hg549e3pNdzgc7hL4yJEjmTRpknta586dOXjwoLs74oceeoiHHnqInj174nA4OHbsGEuWLCElJQURweFwICK8+uqriMhpfwenUp8XY38OrKhWbXONMaYfcBPwuIhcW9vCIjJWRJJFJDk7O7vOmYmJDKOg7NxfgFEq0FTvpnj48OFMmzaNoqIiADIyMsjKyvLZBbCv5atUBdnY2FiKiorcwwnGxMTQvn17Zs2aBVgdmpWUlHDjjTfy4Ycfui/sVlXdxMfHs379egD3OnzJz8+nVatW2Gw2li5dyoEDBwC4/vrr+eKLL8jNzfVaL8ADDzzAvffe67M0Hxoa6r5Y6hnkAaKionj44YcZN26cezsdDgcVFRXufN5///0cOHCAtLQ0Dh06REJCAsuXL681/3VRn4F+NNWqbYwxGa7nLGAm0L+2hY0xU4wxScaYpLi4uDpnpkmkjcIyLdErVVee3RQ//fTTDBs2jHvvvZerrrqKXr16ceedd1JYWEhKSgr9+/cnMTGRl156ieeffx6AsWPHMmLEiBoXY5s1a8ajjz5Kz549GT58OFdccYV72ieffMIbb7xB7969ufrqqzl69CgjRoxg5MiRJCUlkZiYyN///ncAfv/73zN58mT69u170nFk77vvPpKTk+nVqxcff/wxXbt2BaBHjx4899xzXHfddfTp04ennnrKa5njx49zzz33nPb39vLLL9OmTRt69uxJ3759GTRoEGPGjKFt27ZMnz7dZ/fFZ6v6xq9uikUkHphrjOlZy/SmwH6ggzGm2JXWGAgxxhS6Xi8CJhljvjvV59W1m2KAhz9ax5H8Mub9dlCd1qNUQ9NuihvOl19+yezZs/nkk08aOite6r2bYhGZDgwGYkUkHXgBsAEYY951zTYKWFgV5F0uAma66pvCgP/6E+TrS0xkGLuztESvlDozTzzxBPPnz2fevHkNnZU6O2WgN8ac8pzFGPMRVjNMz7R9QJ8zzVhdxUTaKNQ6eqXUGXrzzTcbOgv1JiDvjAWrRF9YZud8HEFLqdOl+7Gqcib7QgAHehsOp6G00tHQWVGqTiIjI8nNzdVgrzDGkJub677b1l8BOcIUWCV6gKIyO1HhAbuZKgi0b9+e9PR06qPZsbrwRUZG0r59+9NaJmAjYFWgLyiz06pJA2dGqTqw2WwkJCQ0dDbUBSxgq26aRFp9UmhbeqVUsAvYQF9VoteWN0qpYBewgT5aA71SSgEBHOhjtOpGKaWAgA70WqJXSikI4EAfHR6GiJbolVIqYAN9SIgQHa5dFSulVMAGejjRDYJSSgWzAA/02ie9UkoFeKDXEr1SSgV+oC/XEr1SKrgFdKCPCg+jtEJ7r1RKBbeADvQRthDKKp0NnQ2llGpQpwz0IjJNRLJEZGst0weLSL6IbHI9JnpMGyEiu0QkVUTG12fG/dHIFkqZ9kevlApy/pToPwJGnGKe5caYRNdjEoCIhAJvAzcB3YF7RKR7XTJ7uiI10Cul1KkDvTHmR+DYGay7P5BqjNlnjKkAZgC3nsF6zlikLYTSSoeOzKOUCmr1VUd/lYhsFpH5ItLDldYOOOQxT7orzScRGSsiySKSXF8j6TSyheI0UOnQQK+UCl71Eeg3AJ2MMX2AN4FZZ7ISY8wUY0ySMSYpLi6uHrJlVd0AOm6sUiqo1TnQG2MKjDFFrtfzAJuIxAIZQAePWdu70s6ZqkBfroFeKRXE6hzoRaS1iIjrdX/XOnOBdUAXEUkQkXBgNDCnrp93OqoCvTaxVEoFs1MODi4i04HBQKyIpAMvADYAY8y7wJ3AYyJiB0qB0ca6+mkXkXHAAiAUmGaM2XZWtqIWkTbrOKZVN0qpYHbKQG+MuecU098C3qpl2jxg3pllre4auUv0GuiVUsEroO+MjdRAr5RSgR7otepGKaUCPNDrxVillAqKQF9u1xK9Uip4BUWg166KlVLBLKADfZQr0JdooFdKBbGADvRNGtkQgbxSHWVKKRW8AjrQh4YITSJt5JVUNHRWlFKqwQR0oAdoHmUjr0RL9Eqp4BXwgb5pVDjHtUSvlApiAR/otUSvlAp2QRDow8kr1RK9Uip4BXygbxZlI69YS/RKqeAV8IG+eVQ4heV2Kh3aDYJSKjgFfKCPCtfhBJVSwS3gA727YzO9O1YpFaQCPtA30h4slVJB7pSBXkSmiUiWiGytZfp9IrJFRFJEZKWI9PGYluZK3yQiyfWZcX+5S/Tag6VSKkj5U6L/CBhxkun7geuMMb2APwFTqk0fYoxJNMYknVkW68Y9+IhW3SilgpQ/Y8b+KCLxJ5m+0uPtaqB93bNVf3TcWKVUsKvvOvqHgfke7w2wUETWi8jYky0oImNFJFlEkrOzs+stQxE2bXWjlApupyzR+0tEhmAF+ms8kq8xxmSISCtgkYjsNMb86Gt5Y8wUXNU+SUlJpr7ypRdjlVLBrl5K9CLSG5gK3GqMya1KN8ZkuJ6zgJlA//r4vNNRVUevwwkqpYJVnQO9iHQEvgbuN8bs9khvLCIxVa+BYYDPljtnU6NwHU5QKRXcTll1IyLTgcFArIikAy8ANgBjzLvARKAl8I6IANhdLWwuAma60sKA/xpjvjsL23BSkWF6MVYpFdz8aXVzzymmPwI84iN9H9Cn5hLnlnuAcK2jV0oFqYC/MzYizNpELdErpYJVwAf6kBAhIixE74xVSgWtgA/0YF2Q1U7NlFLBKigCfWRYqLajV0oFreAI9LYQvTNWKRW0giLQR4SFUmHXEr1SKjgFRaAPDwuhQocSVEoFqeAJ9FqiV0oFqaAI9BFhIdrXjVIqaAVFoNcSvVIqmAVHoA8NoVwDvVIqSAVFoI+waasbpVTwCopAryV6pVQwC45Ar80rlVJBLCgCfURYCOV6Z6xSKkgFTaDXEr1SKlgFRaCval5pTL2NOa6UUhcMvwK9iEwTkSwR8Tnmq1jeEJFUEdkiIv08po0RkT2ux5j6yvjpiAgLwWnA7tRAr5QKPv6W6D8CRpxk+k1AF9djLDAZQERaYI0xOwDoD7wgIs3PNLNnKtw1ypQ2sVRKBSO/Ar0x5kfg2ElmuRX42FhWA81EpA0wHFhkjDlmjDkOLOLkB4yzIjxUA71SKnjVVx19O+CQx/t0V1pt6TWIyFgRSRaR5Ozs7HrKliXCNUC4tqVXSgWj8+ZirDFmijEmyRiTFBcXV6/r1hK9UiqY1VegzwA6eLxv70qrLf2cctfRO7QtvVIq+NRXoJ8DPOBqfXMlkG+MOQIsAIaJSHPXRdhhrrRzKsIV6HXcWKVUMArzZyYRmQ4MBmJFJB2rJY0NwBjzLjAPuBlIBUqAh1zTjonIn4B1rlVNMsac7KLuWXGiRK+BXikVfPwK9MaYe04x3QCP1zJtGjDt9LNWfyLCrIuxZdoNglIqCJ03F2PPpiaNrONZQam9gXOilFLnXlAE+mZR4QDkl1Y0cE6UUurcC45A38gGQF5JZQPnRCmlzr2gCPRR4aHYQoW8Ug30SqngExSBXkRo2iicvBKtulFKBZ+gCPQAzaNsWnWjlApKQRPom2mgV0oFqaAJ9E0bhWsdvVIqKAVNoG/SKIwCDfRKqSAUNIE+KjyUkgq9YUopFXyCKNCHUVKhXSAopYJP0AT6RrZQyu1OHDpurFIqyARNoI8Ktzo2K9WOzZRSQSZ4An2E1bGZ1tMrpYKNX90UB4Io17ixJeUOiGngzCh1odu7FL5+FBw+WrJd+3u4+gn/11WWDxXFNdMbNQdbozPPo3ILnkDvqro5Kxdkc1Jh7XvgrLZuCYEeo6BVN+/08kLYMQcqy2quq1kHaBxbM715ArS8xP88HdkMR1NqptuiIPZSK2+ewhtD807+r78h2Sugoqhm+tr3re0WsbYvJNR6lhAQj9chrueIGBg8wdr2s+FoCky9Eeyl/i/T9Wcw+tOzk5+T2T4HVrwOptrgPBICcd0gLMI7ff8P1nfa+3bv9H3LYM0USLzPO704G76bAKXVxh1yOiBrOzh9nGk36wRPbIDQamHKUWn9h6qzNTq7BwZjIHcvOKp1pSICsZdZ+9V5KmgCfSN3Hb3HDrV3KaQurjlzeGPoNwYim1g7vnGC03nitXGCcZx4vWgi7FkAkc2811NZCuver7+NCI2wdipPMW2gbSLgmW5g57c1d8hTGbsM2vb1Tlv7Piz8o7VOTyFhcNtk6D7SO33vUvjsfnD6KOld/Ru4/jn/8+Ow11xPWQF8cCPkHfC9TOxlVoB3/26Oar+bR3pxFkQ2hZ53eK8jNAKatqu5bqcT8g9Zv70XgWYdrc/1tH229Rtc9wzev08t0pZb+6PDXjO4JX8Iuak1l2nWCQaMPfW6q2yaDhs+rpl+ZDNEt4LYLt7plaXWvm2q/f4SAjdOgsRqYxJt/BRm/xr+L6HmZ0Q0gY5X1kzvdDXEdfXet4/tgxX/glmPWfmqYoxVSMo/VHM9tsbw203e85+MvQIK0mum56RCyuc1C24Fh+HQat/r6vULuPVtj4JFSM3/agPydyjBEcC/gFBgqjHmlWrT/wkMcb2NAloZY5q5pjmAqqLlQWNMtchwbkSFV9XRe/x4S/8CGclWKddTZQn88LfT+4CrfwPD/uSdVnocts20dqjq4q+xdm5Pxgk5u6w/lyenw9rBSo9Xm9/A4Y1wdGvN9SdcC8P/CrZI7/SiLMivtnPby2HmWKs0Vj3Qb/nc+uP0uM07fetM+P4lOLLJO33XdxAeBX1Ge6cfWmv9cdPXUUPbvtDucu+0imJY8CyU5NScX0Jg6As1f7dmHeCym/3/g70/FJb82XpUd/en0O1n3mkr34DFL/heV+NWENXSOy0/HdpfAUOe9S8/Wy6BAysgZzdc1P1Eeu5emPs7CIu0DrBVnHawl0HCoJpnjbVZ9RYUZdbc9y6+Dob/BVr4CNCno9cvrIOzr7PVi6/zP5+OStj3A+yaV3Nak3ZWXsXjwFp6HH54BXYvgH73e8+/aCKs/6jmeirLwFHu+/OjWkKjFt5pEgKDn4W4y7zT935vHTxTvqi2kpOcWdoaWYWM6mfWUS3gIR/bXEdiqh+pq88gEgrsBm4E0rHGf73HGLO9lvmfAPoaY/7H9b7IGBN9OplKSkoyycnJp7PIKW3NyOdnb/7Ee/dfzvAera3Ed66CFhfXPFU+stkqmXr9QLU8QkIhxAaX3QQRp7WZ55c3kwADCdd5JBpY/2+45ncwdKL3/JtnwJzf1CzdSoj1J+z/qHd63kGY/XjNAFBZCpk+qpjAOlvpP7Zm4G6TCJcM8b3M6cg7CAdW1kz/fpJ1Vhc/yDt951xo2t7Kk6fyQms9vqofLn8QOg/1Lz/Zu+Dt/taZYZjHAdpeap3JPLnN+0yjKAv+cZmVp+oHmcZxcO0fvKulKkth6lDrwHPdH/zL04XCGPhnDyjI8D298401qz5DwqwDT0hYzfRLh1tVe/6wl8OmT62DjXFaealxJuk4Mc04rX2mLL/muiKbwq1v+fe51YjIemNMkq9p/pTo+wOpxph9rpXNAG4FfAZ64B6swcPPK+7mlZ4l+vIi3z9mmz7WI5gk3gur3raqGzzFtIHut9acv8/omqX2k2nWEcZ843vasf2+61ybx1vVZ2dLs47Wo7qKYlj215rfRUiYVaLrckPNZaof2M5E7KXWNYOCwzWnte5VszopupUVtA+trTn/gVXwgY98AnQaWPe8nm9EYNR7kPZTzWlRLeHyMTWvM9SXsAhI+p+zs+564k+gbwd4VoilAwN8zSginYAEYIlHcqSIJAN24BVjzKxalh0LjAXo2NHHn6+Oqqpuij2bV1YUnb0LcReaQU9Zj4ZQ1+qC+nbFw9bjXBOBweNPb5lrn/adfjwNDm+qmR4RbdWJB6KEQdZD1VDfF2NHA18a43U+38kYkyEiFwNLRB8GKlsAACAASURBVCTFGLO3+oLGmCnAFLCqbuo5XycuxnqW6CuKIPwCrm5RqjbN462HUvh3w1QG0MHjfXtXmi+jgemeCcaYDNfzPmAZ0LfmYmdfjeaV9gqrRYQGeqVUgPMn0K8DuohIgoiEYwXzOdVnEpGuQHNglUdacxGJcL2OBQZSe93+WWULDcEWKicCfVU7bK26UUoFuFNW3Rhj7CIyDliA1bxymjFmm4hMApKNMVVBfzQww3g34+kGvCciTqyDyiu1tdY5FxrZQimtqqOvuhPvQm4po5RSfvCrjt4YMw+YVy1tYrX3L/pYbiXQqw75q1eNI8K0RK+UCjrn7z27Z0Gj8FCPQO8q0YdrxzdKqcAWVIHea5SpqnbbWqJXSgW44OjrxukEexnNwuzYy+1QUXKicyWto1dKBbjgCPSf3gF7l/Cfqvd/8ZgWcRbvvFRKqfNAcAT6nFRok8jXFf3JKSpn7KCLrfTGsXpTiVIq4AVHoHdWQuterCj/JauKchh7jZ+dTCmlVAAIjouxjkoIDbcuxuqYsUqpIBM8JfpQG1EhoWdnhCmllDqPBU+JPiSMRuGhVNidOJz13meaUkqdt4In0IfaPDo28zFAhFJKBajAD/TGWFU3ITZiIm0AFJRpoFdKBY/AD/RVA/yG2mjZOByAY0WnOWi2UkpdwIIg0FdazyFhtIy2hhLLKa5lQGCllApAgR/oHa5AH2ojNtoq0ecUaqBXSgWPwA/0Tld9fIiNWFeJPrdYq26UUsEj8AO9R4k+KjyUSFsIuUVaoldKBY8gCPSu0nuoDRGhZeMIcvVirFIqiPgV6EVkhIjsEpFUERnvY/qDIpItIptcj0c8po0RkT2ux5j6zLxf3BdjraaVsdHh5GjVjVIqiJyyCwQRCQXeBm4E0oF1IjLHx9ivnxljxlVbtgXwApAEGGC9a9nj9ZJ7fzhcdfShVqBvGR1BZkHZOft4pZRqaP6U6PsDqcaYfcaYCmAGcKuf6x8OLDLGHHMF90XAiDPL6hnyaF4J0LJxuFbdKKWCij+Bvh1wyON9uiutujtEZIuIfCkiHU5zWURkrIgki0hydna2H9nyk8fFWLBK9LnF5Rij/d0opYJDfV2M/QaIN8b0xiq1//t0V2CMmWKMSTLGJMXFxdVTtvBqXglWHX2lw2g3CEqpoOFPoM8AOni8b+9KczPG5BpjqtosTgUu93fZs85doreqbqra0mcXlmmpXikVFPwJ9OuALiKSICLhwGhgjucMItLG4+1IYIfr9QJgmIg0F5HmwDBX2rlTVUcfat0V29J1d+wNr/3IC3O2ndOsKKVUQzhloDfG2IFxWAF6B/C5MWabiEwSkZGu2X4jIttEZDPwG+BB17LHgD9hHSzWAZNcaeeOw7t5ZfOocPekj1cdOKdZUUqphuDXCFPGmHnAvGppEz1eTwAm1LLsNGBaHfJYN9Wqbpq4uipWSqlgEfh3xla7YSomMjhGT1RKqSqBH+irNa+M1kCvlAoygR/oqzWvtIWe2OTQEGmIHCml1DkV+IG+Wh29p1DRQK+UCnyBH+ir1dF70hK9UioYBH6gd3i3o/ekgV4pFQwCP9BX1dH7qLrROK+UCgaB1QRl3VRwOrzT9i+3nn1U3WgHCEqpYBBYgX7hH6GypGZ641YQFlkjuazSUXNepZQKMIEV6J+spe8aW5RX1c2sxwfy+KcbyMgrpdLh9GpyqZRSgSawIlxUC98Pm3dpPrFDMx4aGA9AqZbqlVIBLrAC/WloFB4KQGmFBnqlVGAL2kAf5Qr0xeU6AIlSKrAFbaCPjrBa4RSXa4leKRXYgjjQWxdnC8srGzgnSil1dgVtoK/qrrhIx45VSgW4oA30VSX6Iq2jV0oFOL8CvYiMEJFdIpIqIuN9TH9KRLaLyBYR+V5EOnlMc4jIJtdjTvVlG0pVv/Qa6JVSge6UgV5EQoG3gZuA7sA9ItK92mwbgSRjTG/gS+D/PKaVGmMSXY+RnCeqSvTvLN1LYZnW0yulApc/Jfr+QKoxZp8xpgKYAdzqOYMxZqkxpqrvgdVA+/rNZv2LCLM2/WhBGa8u2NXAuVFKqbPHn0DfDjjk8T7dlVabh4H5Hu8jRSRZRFaLyG21LSQiY13zJWdnZ/uRrboRj0FH9KYppVQgq9eLsSLySyAJeNUjuZMxJgm4F3hdRC7xtawxZooxJskYkxQXF1ef2TqlL9anM3X5vur50SodpVRA8CfQZwAdPN63d6V5EZEbgOeAkcaY8qp0Y0yG63kfsAzoW4f8njV//naH1/tJc7fT68WF2sOlUuqC50+gXwd0EZEEEQkHRgNerWdEpC/wHlaQz/JIby4iEa7XscBAYHt9Zb6uGru6QajOGMOHK9IAOF5ScQ5zpJRS9e+Ugd4YYwfGAQuAHcDnxphtIjJJRKpa0bwKRANfVGtG2Q1IFpHNwFLgFWPMeRPo1z53g8/04yUnqmy0Lxyl1IXOr/7ojTHzgHnV0iZ6vPYZMY0xK4Fedcng2dQ4wnvztx8uYMG2o/ysdxt3WqHeOauUusAF1sAjdWALFe7/YA25xRV0bhXtTtcbqpRSF7qg7QKhSqTN+grCQkLILbbq49elHXNPT8spZmtGfoPkTSml6kPQB/o5466hbdNIr5Gm1uw7Eej/OHsbP3vzJ5buyvK1uE92h5PJy/Zq/b5S6rwQ9IH+0otiePTai73SdmUW1pjvk1UH/F7nou2Z/O27nXrHrVLqvBD0gR6g0uF0v67qvji62oXan1JzmLkxnSemb8TuMb8vFa7pGXmllFY4eOTfyezLLgKsg4DeiHX++3F3NkfySxs6G0rVCw30wNBuF5HYoRkrx1/PDd0uAqBts0hCQ6xuEi6Oa0yF3cmTn23mm82HufqVJeSX1B6sj7nq+ovL7fyUmsPiHZlMmrud3ZmFPPpxMi/OOW9amLp9vSGdN77f09DZOC84nIYHpq3ljndW+jX/jiMF3P3eKu1KQ523NNADl8RFM+vxgbRt1ohOLaMA6NG2KQ6nAWBAQkuv+bMKy9lw8Hi1tDLu/2ANuzMLySywbgw+XlLpPlsICwnhQK7V79vRgvOnpLh4eyYlFXae+nwzry3a7U6vsDvZdCivAXPWcHKKrN/vcH6ZX/O/9M021uw/VmOfUOp8oYG+mriYCAD6tG/qTruhWyv362HdrRL/9iMFXsutTzvO8j05/OzNn8gqsALEvuwijrqCRViIsNdVfdMsKvykeTiaX3ZOSod7s4t45ONknpu51Z1Wbrc+9x+LdnHb2yvYcPA4h/P8OzAt3p7pdbCoq5yicvfB9lw64iPAH84rdVe/VWeM93MgKKmwM+XHvaesplT159stR+r1/+NJ29FXc1dSBxrZQrk1sR3FFQ6iI8IYclkrRKw/ctc2Tdh+pIAdRwr4YXc2z89KYcbYq9zBocLudAf0cruTZbutnjhTMvIpcwXRqj/Pwm1HSYpvQYvGJwJ/cbmdK//6PbcmtuVfo0/eLZAxxqsXzuoKyyqJibTVOj23yKpimrnxRNdFmfnllFTa2ZZhHchud1VfpL1yi8912B1Ohr/+I78Z2oXfztgEwJM3dDlpvmqTVVhGq5hIwLq+MfCVJTwzoiuPDbb6wVuw7SjREWEM7Bx72uuujTGGVXtz2Zyej8PpZNz1XTjqUTf/zrJUNh/KY/2B4+QUVbDn5ZuwhfouHxU1wPjDry7YyWWtmzCyT9t6Xe8Hy/fzj0W7iY6wce+AjvW67pNZu/8Y3ds2qXGN7Hy0JT2PSocTp4HWTSLp0CKqTutbsjOL1ftyeerGS+sphydoib4aW2gIt/drT2iI8PiQzoy5Op6QEMEWYn1V7Zs1ole7pszdcoQn/ruBQ8dKWbU316vUuzk9n6svsap7fnQF+oy8Upbtsl4v2JbJ72ZsZOwn6/ntjI3u5Ywx/H2h1VJn5d5c3v1hr/vsACAlPZ9fTl3DwFeWkJFXSsKEeXy39ajP7Vi9L5deLy5kZWqOz+lOp2HR9prLvrFkDyNeX85P1ZbLL/UdxA7nlbE3u9gd5AEKz6BZ6YJtR7nqr0s4dMyq3pqz6TAA3+/IdM/zq0/Wc9/UNT6XX7Izk9FTVvl99gEw6ZvtXPfqMu6duoa/fbeTvy/czfbDBV4l+v/7bhcLtmWS4zooLtlpNbMtrXCwdv8xFm/PZM1+qznu8ZJKd3pdGGPYdjgf48cpwttL9/Kb6RtPOR9YhZD5KUdwepwlGWPc15Q8VR2n92TVbIFWZdbGDGZvqtG/4WkxxvD20lQy8kopKrdz13uruGfK6jqt80xlFpzemfTIt1Zwx+RV/OLdVfzygxP7pcNp+Mu8HaSkn7j/psLupMJ+8rOj7KJyYqNPfrZ/ps7/w+Z5Ytz1ndmSns/grnGUVjqYv/UoBWV2GtlC2ZKeR3ZhOXExEWQXWvW744Z05mhBGfuyi32ub5YrkO04cuKPlHzguLsztezCcl6Zv5NX5u/k4rjG/O2O3vzi3VXueedutpZ/5qstjOjZusb6q4LNoh2ZHDpeQtNG4V7zfbwqjfeX76+x3Jfr033md9fRQibO3kr/hBa8NLIHIsL4r7ZwtKBmNUd2YTlNTnIm4cvCbZk4nIYdRwro0CKKBdusg1BRuZ39OcW0b97IPW+lw+kuVX+4Yj99OjTjsf9soNzu5OpXltC5VTT/+EUf+nRoRm5ROesPHGdYj5rf0bQVNbf/zSV7mF/LwRNg2a4shvdozbMzU7zOhMC6CD/470vJLChn1uMD6d2uKT/syWbwpXF8uT6dltHhXN/1olrXvT+nmOJyO7szC3nq88388+4+jOpb+xg+noHjmS+3cO+AjvTp0KzW+d9asoc3lqTytzt6cXFcNAdzS8jIK+W1RbtZ+9xQissdtIqJYF92MV9vsLZt0fZMWkSFM+76zjXO0n73mXVwbxYVznWXnuha/HhxBaWVDto2a8Sp7M8p5tUFu1i8I5O/3m71lpKSkU+F3Ul42OmXQx1OQ6XDSaTNd4eFtXE6DQP+8j39E1rw+a+uOum8doeT/Tne/+sDuSXszS5i7uYjNAoPYcqP+/hhVzYi8MY9fXnsP+sRERY/dR1llQ5+N2MTvx5yCb3bW7/XjLUH+XF3tlc1cX3SQO+n3wzt4n49sLNVWr/z8vYcOlbCx6429oO6xPLuL/ux40ghV13Skv933SX84cstp1izsU7XPttEpdMQIjCoSxw/7D4x+Mq+7GKvIA/w1/k7AaukXVbpqLFj57laBR3OK3UfPPb+5WbW7MtlS0Y+O6tdY/DlivjmrEuzLjDe9Z71+TuPFnJ911bsOFLIjHWHfC63J7OI2MYRNI2yYYxhwbaj2J2GW3q18VmlY4xh+R5re9Nyi/njrK3uC8E7jxYy5O/LvOb/IjmdhduPcuXFLXnF9T14Ss0qYtQ7Kxhzdbx72xc9eS1dLoqhuNzOH77cwv9ck0BoiNS4BlAV5O8d0JHZGzMorlbCW5GaC1gBv7qPVqa5D/TrDxxn19ECnvkqhb//og9Pu/aDzROH0TTqxEHwD19uZkVqLlMeuJxb3vgJgL4drT//m9+ncuXFLWnT1AqY/1i4ixARnnSd2nuWxD9LPsSa/bl8/7+DefzTDdx9RQeGdLWCht3hxGEM/11r/V6Tl+3l0PFSr23fcaSQMdPW0rNdE7ZmnNg30o+X8o9Fu1myK4v3H0giNtq6huXZffeYaWtZ/och/OqT9bw4sgdPfraJjLxS9v3lZkJcLdeMMaTllhDfMsprH6gqKGTml5F+7MTZ2O7MQqYu30dMpI1OLaO4/6pORISFurcHwO407v2+6sxk0tztzN50mP1/vdn9OQdzSyiusNOtTRNKKuxsPJjHn7/dQXZhOVPHJJHYoRn7XIF77f5j7irR2qpGX5izjU/XHKyRPvQfP3i9r7of58MVaex1FfgqHU5mbczgO9d/YuqYJOwOJ+O/TgFwf7/1Tfw5PTzXkpKSTHJyckNn46TWHzhO7/ZN2X64gFvfXgHAb67vzFPDLvOa73hxBSv25vDRijT+88gA/jhrK1+sT2fCTV355+LdlFV6n85dEd+cXu2aMW3FfmyhwtCuF5FTVE7ygeO0a9aIK+Kbs3rfMa+S9OzHB7rOBvbzq2sv5tuUI6zZfwxjrIvAdtcf+v/u7M3bS1PdrX+qPD38Mn517cV0fs4aGOzVO3vTrU0TNh7K44+ztuKvG7q1YvEOKwBGR4QxtFsr5qccdd9X8Pwt3Xhk0MX84cvNHCuuZGRiW0b2acvOowWMeH15jfW9c18/Xvpmm7sVk7+evOFSpq89yNGCMncwf/DqeO7o1561acf409wTzVt/O7QL87ceYXdmEQmxjdmfU0zzKBsbJw5jzubDXtUio6/owIx1h3j25q68umAXlY6a/53e7ZuSVVBO347NiI2O4JPVB7imc6y7KmxEj9ak5RbTonE4JRWOWls29WjbhLScYmIibTwyKIG7ruhA7xcXArD22aG88t1Od6m7NrcltiUlI5/MgnJ3n00PDTxx8PM0vMdFLNiWWSO9ffNGpB8/EYCvuzSOzIIyUrOKsDsNUeGhlFQ46B/fgrVpx+jTvimbXVUWr9zeiy4XxZBXUsHD/7b+z3/8WXdaN4nE7nQysHMsC7dl8uzMFGIiw2jRONy9b3qeHQM8deOlPDb4ElKzihgzbS1ZheW0bBzO5//vKmKjI1iw9Sh/+OpEoer5W7rRpJGNu5I6ED/+WwC+/vXV7mtOnhY/dS2j3lnp7sBw6e8Hs+toIU99volZjw8kOiKM7YcL+H5nJhsP5rHzaO3VWVUGXxbnrqpt16wRGa4qxT7tm1JS4WBPVhFJnZrTqWVjCsoqWbTd+u7HDenM74dfVut6T0ZE1rsGeao5TQN93X227iCvLdrN/N9e63Vh1ZeySgdH8stIiG1MaYWDp7/cTFG5nZV7c6mwO/nzbT05dKyE937c5/7Rf9idzZhpa7krqT3/d2cfAF6cs41yu5Ppa2uWLHzp2jqGXZmFNVqGTLipK7+6zrrY+fysFP6z+iAb/ngjLRqHs/HgcUZV+2N8/D/9eearLQy+LI7ubZqQVVjOou2Z7DxayLe/ucZdKq3SP6EF/To2Z0VqDikZ+YSHhrgDP0C3Nk3o2jqmRjXI2/f245bebSipsGMLDeHVBbuY8uOJUcASOzSrESTHDenMbX3b0blVNMeKK/h+RybDuremz6SFtX4vM8ZeyfoDx3l1wS4eHZTAwM6xtGgcTu/2zVi2K4sHP1zHNZ1jmXBzVy69KIbb3l7BtsMF2ELFZ6D/Ztw1fJZ8kP+srvm7NLKFenW1cTJf/L+rqLA73dckrrq4Jav25fq1bG3iW0ax4Mlruez57/xeJu2VW5i6fB//WrzH57WXBb+7ltvfWVHjzKc2kbaQGoUbf9X2nZ/MV49dzR2TrX24a+sYv4J0TGSYz15rw8NCvKrL/nRrD95fvp+XR/WkU4vGzNyYwT8XW61mfB1Qm0fZvLpA9+WJ6zvzv8M00AesPZmFvLkklVfu6MWUH/fx+uI9TL6vHzf1auOq/sjkyotbeDXNdDoNFz97ovfoyff1Y9z0jdzQrRWtYiLpn9CCJ6ZvJKlTc8Zd35kHP1wHWNUS/11zkNv7tuO1uxPdy9sdTo7kl3m1HtifU0yoCNe+uhSovfWN02kQgYQJJ/Jz3aVxfPTQFYgIL3+73euawMWxjRGBQ8dKqXA4GZDQgj+M6MrsTRlkFZTzzn393Kf9YJ2aZxeV89Kc7XybcsTrDwzWWcgvkjwHQjuhqkR3S682fJtyhMsusg56k+/rx4ierdmSns+tb69g+qNXctUlJ+6ZKKt08ORnm/j98Mu4JC7anbZsVxYdWkTRukkktrAQbn9nJalZRfRs14S5TwyirNLBS99sY/raQ8REhnFrYlvSckq4vV87nvp8MwBjrurEkl1Z9GzblFt6t+HdH/bSqWVjvt1yBIDdf74JW6hw/T9+qFEfXN0T13dmQEJLFm4/ylM3Xsodk1eyN7uYNk0j3ReWl/1+MK2bRhJpC+XiCd/iNPCXUb14dmaKez039WzN/K1HeeHn3Xnpm+1ev3dVvfTyPTkM79mavVlFOIxhyGWtWJmawyerD5BbXMHa/ce4uVdrfj24M7M2ZrBm/zFSMvIZ2actE3/enTsnrySt2hmlp25tmhATEcZaj44F/zU60eti/7ghnbn6kpYcL6nkp9RspruqpF65vReXto6pUWoPDRHCQ0MorXTQvnkjXh7VizHT1gK4z0QeuKoTL43s4bX/Vvfn23py5+XteXtpKmOujvdZzfLinG3Et4zi5t5tmLv5CHuyCpm+9hCXd2rOV49dzaMfJ7NoeybdXa33qnvyhkv57Q1daqT742SBHmPMefe4/PLLTTArrbCbmRvSjdPpPOW8x4rKzZ7MApOaVWiMMaas0u6eVlhWabr9cb55d1mqqbQ7zMi3fjK3v7PCFJdXmrX7c01mfqnfeVq47aiZn3L4lPOlZhWaRduOmv3ZRcbuOJH/b7ccNp2emWtmbkg32YVl7vSM4yVm/FebTVpOkV/5KKu0m2NF5cYYY7Zm5JnjxeXmtYW7THmlo9ZlVuzJNqv25piySrtZsjPT2B1OU1Ba4TVPhb325f1V/ffampFnjnp8x+WVDnPv+6vM/JQjPj/T6XSa/6xOMwdzi91pJeV2M+y1H0ynZ+aaHUfyzZZDeabTM3NNp2fmmu5/nG86PTPX5FfbluS0XDPstR/M8eJy89zMLWbRtqNe02dtTDdX//V7U17pMDmFZWbB1iPmx91ZpqzSbn7cnWWcTqe59Ll5ZtI3205r+7dm5JmX5mwzeSUn8lNUVmn+tXi3e/9MP15i3vsh1Uxfc8DsPlpgnpu5xfxxVopZuO2oScux9hmHw2n+tXi3ufu9le7vZcLXW8ynqw+YhduOmtIKu9fn/umbbe7tsTuc7u/nljd+NL94d6U5nFdi7A6nWbU3xxzOKzHGGPPov9eZ52emmEq7wySn5bp/u+lrDpjBry41I9/6yfx3zQHz8rfbjdPpNBsPHvfr/1jd4bwSM2baGvdvnnG8xDw5Y6PJLSo3/1q82/ywK8tMXb7P7MksNO/9kGpKyu2nWGPtgGRTS0z1q0QvIiOAfwGhwFRjzCvVpkcAHwOXA7nA3caYNNe0CcDDgAP4jTFmwak+LxhL9GdLVmEZLaLCCaul7fe5Yoxh+5ECerRteuqZlZdDx0o4kFvCNV2s+wc++Gk/vdo1pUVjG9/vyHJXvQUrYwxOg7vLkp1HC2jbrNFpt/y60NWp6kZEQoHdwI1AOtYYsvcYjyEBReTXQG9jzP8TkdHAKGPM3SLSHZgO9AfaAouBS40xJ63Q00CvlFKn52SB3p9iXn8g1RizzxhTAcwAbq02z63Av12vvwSGitUu6VZghjGm3BizH0h1rU8ppdQ54k+gbwd4NphOd6X5nMdYg4nnAy39XFYppdRZdN50gSAiY0UkWUSSs7OzT72AUkopv/gT6DMAz3Zr7V1pPucRkTCgKdZFWX+WBcAYM8UYk2SMSYqLi/M1i1JKqTPgT6BfB3QRkQQRCQdGA3OqzTMHGON6fSewxNXcZw4wWkQiRCQB6AKsrZ+sK6WU8scp+7oxxthFZBywAKt55TRjzDYRmYTVbnMO8AHwiYikAsewDga45vsc2A7YgcdP1eJGKaVU/dI7Y5VSKgDUtXmlUkqpC9h5WaIXkWzgwBkuHgv4Hm0jcOk2Bwfd5uBwptvcyRjjsyXLeRno60JEkms7fQlUus3BQbc5OJyNbdaqG6WUCnAa6JVSKsAFYqCf0tAZaAC6zcFBtzk41Ps2B1wdvVJKKW+BWKJXSinlQQO9UkoFuIAJ9CIyQkR2iUiqiIxv6PzUFxGZJiJZIrLVI62FiCwSkT2u5+audBGRN1zfwRYR6ddwOT9zItJBRJaKyHYR2SYiv3WlB+x2i0ikiKwVkc2ubX7JlZ4gImtc2/aZq78pXP1HfeZKXyMi8Q2Z/7oQkVAR2Sgic13vA3qbRSRNRFJEZJOIJLvSzuq+HRCB3jUK1tvATUB34B7X6FaB4CNgRLW08cD3xpguwPeu92BtfxfXYyww+Rzlsb7Zgf81xnQHrgQed/2egbzd5cD1xpg+QCIwQkSuBP4G/NMY0xk4jjUsJ67n4670f7rmu1D9Ftjh8T4YtnmIMSbRo7382d23axtM9kJ6AFcBCzzeTwAmNHS+6nH74oGtHu93AW1cr9sAu1yv38Ma5rHGfBfyA5iNNZRlUGw3EAVsAAZg3SEZ5kp37+dYnQxe5Xod5ppPGjrvZ7Ct7V2B7XpgLiBBsM1pQGy1tLO6bwdEiZ7gG8nqImPMEdfro8BFrtcB9z24Ts/7AmsI8O12VWFsArKARcBeIM9Yo7aB93bVNqrbheZ14A+A0/W+JYG/zQZYKCLrRWSsK+2s7tun7KZYnd+MMUZEArKNrIhEA18BvzPGFFjDEFsCcbuN1YV3oog0A2YCXRs4S2eViPwMyDLGrBeRwQ2dn3PoGmNMhoi0AhaJyE7PiWdj3w6UEr3fI1kFiEwRaQPges5ypQfM9yAiNqwg/6kx5mtXcsBvN4AxJg9YilVt0cw1aht4b1dto7pdSAYCI0UkDZiBVX3zLwJ7mzHGZLies7AO6P05y/t2oAR6f0bBCiSeI3qNwarDrkp/wHWl/kog3+N08IIhVtH9A2CHMeY1j0kBu90iEucqySMijbCuSezACvh3umarvs2+RnW7YBhjJhhj2htj4rH+s0uMMfcRwNssIo1FJKbqNTAM2MrZ3rcb+sJEPV7guBnYjVWv+VxD56cet2s6cASoxKqfexirXvJ7YA+wGGjhmlewWh/tBVKApIbO/xlu8zVY9ZhbgE2ux82BvN1Ab2Cja5u3AhNd6RdjDb+ZCnwBRLjSI13vU13TL27oZ5DJcwAAAFFJREFUbajj9g8G5gb6Nru2bbPrsa0qVp3tfVu7QFBKqQAXKFU3SimlaqGBXimlApwGeqWUCnAa6JVSKsBpoFdKqQCngV4ppQKcBnqllApw/x/cit0oni5BVgAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PlCtBEBLMBkR"
      },
      "source": [
        "## Question 1: What is the maximum accuracy obtained on test set for GAT? (10 points)\n",
        "\n",
        "\n",
        "Running the training cell above will also save your best GAT model predictions as *CORA-Node-GAT.csv*.  \n",
        "\n",
        "When you sumbit your assignment, you will have to download this file and attatch it to your submission. As with the other colabs, please zip this file (DON'T CHANGE ITS NAME) and the .csv file that's generated!\n"
      ]
    }
  ]
}