assignment_4b.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "accelerator": "GPU",
    "gpuClass": "standard"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/remiverdiesen/NLP_BERT/blob/main/assignment_4b.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aJ_pmgxvGur9"
      },
      "source": [
        "# Assignment 4b - Graph Convolutional Networks\n",
        "## Deep Learning Course - Vrije Universiteit Amsterdam, 2022"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mEneMITS2agU"
      },
      "source": [
        "#### Instructions on how to use this notebook:\n",
        "\n",
        "This notebook is hosted on Google Colab. To be able to work on it, you have to create your own copy. Go to *File* and select *Save a copy in Drive*.\n",
        "\n",
        "You can also avoid using Colab entirely, and download the notebook to run it on your own machine. If you choose this, go to *File* and select *Download .ipynb*.\n",
        "\n",
        "The advantage of using Colab is that you can use a GPU. You can complete this assignment with a CPU, but it will take a bit longer. Furthermore, we encourage you to train using the GPU not only for faster training, but also to get experience with this setting. This includes moving models and tensors to the GPU and back. This experience is very valuable because for many interesting models and large datasets (like large CNNs for ImageNet, or Transformer models trained on Wikipedia), training on GPU is the only feasible way.\n",
        "\n",
        "The default Colab runtime does not have a GPU. To change this, go to *Runtime - Change runtime type*, and select *GPU* as the hardware accelerator. The GPU that you get changes according to what resources are available at the time, and its memory can go from a 5GB, to around 18GB if you are lucky. If you are curious, you can run the following in a code cell to check:\n",
        "\n",
        "```sh\n",
        "!nvidia-smi\n",
        "```\n",
        "\n",
        "Note that despite the name, Google Colab does  not support collaborative work without issues. When two or more people edit the notebook concurrently, only one version will be saved. You can choose to do group programming with one person sharing the screen with the others, or make multiple copies of the notebook to work concurrently.\n",
        "\n",
        "**Submission:** Upload your notebook in .ipynb format to Canvas. The code and answers to the questions in the notebook are sufficient, no separate report is expected. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lBgoJIpdLI2Y",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ec97a4b7-37af-4398-dac2-f456f7c1e2ba"
      },
      "source": [
        "!nvidia-smi"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Fri Dec 23 19:49:38 2022       \n",
            "+-----------------------------------------------------------------------------+\n",
            "| NVIDIA-SMI 460.32.03    Driver Version: 460.32.03    CUDA Version: 11.2     |\n",
            "|-------------------------------+----------------------+----------------------+\n",
            "| GPU  Name        Persistence-M| Bus-Id        Disp.A | Volatile Uncorr. ECC |\n",
            "| Fan  Temp  Perf  Pwr:Usage/Cap|         Memory-Usage | GPU-Util  Compute M. |\n",
            "|                               |                      |               MIG M. |\n",
            "|===============================+======================+======================|\n",
            "|   0  Tesla T4            Off  | 00000000:00:04.0 Off |                    0 |\n",
            "| N/A   65C    P0    29W /  70W |      0MiB / 15109MiB |      0%      Default |\n",
            "|                               |                      |                  N/A |\n",
            "+-------------------------------+----------------------+----------------------+\n",
            "                                                                               \n",
            "+-----------------------------------------------------------------------------+\n",
            "| Processes:                                                                  |\n",
            "|  GPU   GI   CI        PID   Type   Process name                  GPU Memory |\n",
            "|        ID   ID                                                   Usage      |\n",
            "|=============================================================================|\n",
            "|  No running processes found                                                 |\n",
            "+-----------------------------------------------------------------------------+\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tsdc7fDp40rQ"
      },
      "source": [
        "### Introduction\n",
        "\n",
        "Graphs are very useful data structures that allow us to represent sets of entities and the way they are related among each other. In a graph, entities are also known as *nodes*, and any link between entities is also called an *edge*.\n",
        "\n",
        "Examples of real world objects that can be modeled as graphs are social networks, where entities are people and relations denote friendship; and molecules, where entities are atoms and relations indicate a bond between them.\n",
        "\n",
        "There has been increased interest in the recent years in the application of deep learning architectures to graph-structured data, for tasks like predicting missing relations between entities, classifying entities, and classifying graphs. This interest has been spurred by the introduction of Graph Convolutional Networks (GCNs).\n",
        "\n",
        "In this assignment, you will implement and experiment with one of the first versions of the GCN, proposed by Thomas Kipf and Max Welling in their 2017 paper, [Semi-supervised Classification with Graph Convolutional Networks](https://arxiv.org/abs/1609.02907). In particular, the goals of this assignment are to\n",
        "\n",
        "- Understand how GCNs are formulated\n",
        "- Implement the GCN using PyTorch\n",
        "- Train and evaluate a model for semi-supervised node classification in citation networks\n",
        "- Train and evaluate a model for binary classification of molecules"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RvsuVNczG6pP"
      },
      "source": [
        "### Representing graphs\n",
        "\n",
        "Suppose we have the following graph:\n",
        "\n",
        "<img src=\"https://raw.githubusercontent.com/dfdazac/dlvu-a5/main/img/01-graph.png\" width=\"200\">\n",
        "\n",
        "This is an undirected graph (since the edges have no specified direction) with 4 nodes. One way to represent the connectivity structure of the graph is by means of the **adjacency matrix**. The $i$-th row of the matrix contains a 1 in the $j$-th column, if nodes $i$ and $j$ are connected. For an undirected graph like the one above, this means that the adjacency matrix\n",
        "\n",
        "- Is symmetric (e.g. an edge between 0 and 2 is equivalent as an edge between 2 and 0)\n",
        "- Is square, of size $n\\times n$ where $n$ is the number of nodes\n",
        "\n",
        "The adjacency matrix for the graph above is then the following:\n",
        "\n",
        "$$\n",
        "A =\n",
        "\\begin{bmatrix}\n",
        "0 & 0 & 1 & 0 \\\\ \n",
        "0 & 0 & 1 & 0 \\\\\n",
        "1 & 1 & 0 & 1 \\\\\n",
        "0 & 0 & 1 & 0\n",
        "\\end{bmatrix}\n",
        "$$\n",
        "\n",
        "A second matrix of interest is the **degree matrix**. This is a diagonal matrix where the $i$-th element of the diagonal indicates the number of edges connected to node $i$. Note that these can be obtained from $A$ by summing across the columns, or the rows. For our example, the degree matrix is\n",
        "\n",
        "$$\n",
        "D = \\begin{bmatrix}\n",
        "1 & 0 & 0 & 0 \\\\ \n",
        "0 & 1 & 0 & 0 \\\\\n",
        "0 & 0 & 3 & 0 \\\\\n",
        "0 & 0 & 0 & 1\n",
        "\\end{bmatrix}\n",
        "$$\n",
        "\n",
        "For specific applications, each node in the graph will have an associated vector of features $x\\in\\mathbb{R}^c$. If our graph is a social network, then the vector of features can contain information like age, location, and musical tastes, in a specific numeric format. In the case of a molecule, the node could represent an atom and have features like the atomic mass, etc. We can lay out the features in a matrix $X\\in\\mathbb{R}^{n\\times c}$, so that the feature vector for node $i$ is in the $i$-th row."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zCEQ2ffzHCf2"
      },
      "source": [
        "### Loading a citation network\n",
        "\n",
        "To move to a real world example, we will start with the Cora dataset. This dataset represents a citation network, where nodes are scientific publications, edges denote citations between them, and features are a [bag-of-words](https://en.wikipedia.org/wiki/Bag-of-words_model) extracted from their contents.\n",
        "\n",
        "This graph contains labels for nodes, that represent a specific topic. We will use these for a node classification task.\n",
        "\n",
        "To easily load it, we will use [PyTorch Geometric](https://pytorch-geometric.readthedocs.io/en/latest/index.html) (PyG), a deep learning library for graph-structured data."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Yd2bTEBADt-a",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ea49ffbf-b315-4804-f2e2-5f7b2e217815"
      },
      "source": [
        "# Install PyTorch Geometric\n",
        "!pip install torch-scatter torch-sparse torch-cluster torch-spline-conv torch-geometric -f https://data.pyg.org/whl/torch-1.10.0+cu113.html"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Looking in links: https://data.pyg.org/whl/torch-1.10.0+cu113.html\n",
            "Collecting torch-scatter\n",
            "  Downloading torch_scatter-2.1.0.tar.gz (106 kB)\n",
            "\u001b[K     |████████████████████████████████| 106 kB 14.1 MB/s \n",
            "\u001b[?25hCollecting torch-sparse\n",
            "  Downloading torch_sparse-0.6.16.tar.gz (208 kB)\n",
            "\u001b[K     |████████████████████████████████| 208 kB 57.4 MB/s \n",
            "\u001b[?25hCollecting torch-cluster\n",
            "  Downloading https://data.pyg.org/whl/torch-1.10.0%2Bcu113/torch_cluster-1.6.0-cp38-cp38-linux_x86_64.whl (2.5 MB)\n",
            "\u001b[K     |████████████████████████████████| 2.5 MB 38.4 MB/s \n",
            "\u001b[?25hCollecting torch-spline-conv\n",
            "  Downloading https://data.pyg.org/whl/torch-1.10.0%2Bcu113/torch_spline_conv-1.2.1-cp38-cp38-linux_x86_64.whl (750 kB)\n",
            "\u001b[K     |████████████████████████████████| 750 kB 50.5 MB/s \n",
            "\u001b[?25hCollecting torch-geometric\n",
            "  Downloading torch_geometric-2.2.0.tar.gz (564 kB)\n",
            "\u001b[K     |████████████████████████████████| 564 kB 66.7 MB/s \n",
            "\u001b[?25hRequirement already satisfied: scipy in /usr/local/lib/python3.8/dist-packages (from torch-sparse) (1.7.3)\n",
            "Requirement already satisfied: tqdm in /usr/local/lib/python3.8/dist-packages (from torch-geometric) (4.64.1)\n",
            "Requirement already satisfied: numpy in /usr/local/lib/python3.8/dist-packages (from torch-geometric) (1.21.6)\n",
            "Requirement already satisfied: jinja2 in /usr/local/lib/python3.8/dist-packages (from torch-geometric) (2.11.3)\n",
            "Requirement already satisfied: requests in /usr/local/lib/python3.8/dist-packages (from torch-geometric) (2.23.0)\n",
            "Requirement already satisfied: pyparsing in /usr/local/lib/python3.8/dist-packages (from torch-geometric) (3.0.9)\n",
            "Requirement already satisfied: scikit-learn in /usr/local/lib/python3.8/dist-packages (from torch-geometric) (1.0.2)\n",
            "Collecting psutil>=5.8.0\n",
            "  Downloading psutil-5.9.4-cp36-abi3-manylinux_2_12_x86_64.manylinux2010_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (280 kB)\n",
            "\u001b[K     |████████████████████████████████| 280 kB 61.1 MB/s \n",
            "\u001b[?25hRequirement already satisfied: MarkupSafe>=0.23 in /usr/local/lib/python3.8/dist-packages (from jinja2->torch-geometric) (2.0.1)\n",
            "Requirement already satisfied: chardet<4,>=3.0.2 in /usr/local/lib/python3.8/dist-packages (from requests->torch-geometric) (3.0.4)\n",
            "Requirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.8/dist-packages (from requests->torch-geometric) (2022.12.7)\n",
            "Requirement already satisfied: idna<3,>=2.5 in /usr/local/lib/python3.8/dist-packages (from requests->torch-geometric) (2.10)\n",
            "Requirement already satisfied: urllib3!=1.25.0,!=1.25.1,<1.26,>=1.21.1 in /usr/local/lib/python3.8/dist-packages (from requests->torch-geometric) (1.24.3)\n",
            "Requirement already satisfied: joblib>=0.11 in /usr/local/lib/python3.8/dist-packages (from scikit-learn->torch-geometric) (1.2.0)\n",
            "Requirement already satisfied: threadpoolctl>=2.0.0 in /usr/local/lib/python3.8/dist-packages (from scikit-learn->torch-geometric) (3.1.0)\n",
            "Building wheels for collected packages: torch-scatter, torch-sparse, torch-geometric\n",
            "  Building wheel for torch-scatter (setup.py) ... \u001b[?25l\u001b[?25hcanceled\n",
            "\u001b[31mERROR: Operation cancelled by user\u001b[0m\n",
            "Traceback (most recent call last):\n",
            "  File \"/usr/local/lib/python3.8/dist-packages/pip/_internal/cli/base_command.py\", line 180, in _main\n",
            "    status = self.run(options, args)\n",
            "  File \"/usr/local/lib/python3.8/dist-packages/pip/_internal/cli/req_command.py\", line 199, in wrapper\n",
            "    return func(self, options, args)\n",
            "  File \"/usr/local/lib/python3.8/dist-packages/pip/_internal/commands/install.py\", line 345, in run\n",
            "    _, build_failures = build(\n",
            "  File \"/usr/local/lib/python3.8/dist-packages/pip/_internal/wheel_builder.py\", line 336, in build\n",
            "    wheel_file = _build_one(\n",
            "  File \"/usr/local/lib/python3.8/dist-packages/pip/_internal/wheel_builder.py\", line 223, in _build_one\n",
            "    wheel_path = _build_one_inside_env(\n",
            "  File \"/usr/local/lib/python3.8/dist-packages/pip/_internal/wheel_builder.py\", line 262, in _build_one_inside_env\n",
            "    wheel_path = build_wheel_legacy(\n",
            "  File \"/usr/local/lib/python3.8/dist-packages/pip/_internal/operations/build/wheel_legacy.py\", line 92, in build_wheel_legacy\n",
            "    output = call_subprocess(\n",
            "  File \"/usr/local/lib/python3.8/dist-packages/pip/_internal/utils/subprocess.py\", line 194, in call_subprocess\n",
            "    line = proc.stdout.readline()  # type: str\n",
            "KeyboardInterrupt\n",
            "\n",
            "During handling of the above exception, another exception occurred:\n",
            "\n",
            "Traceback (most recent call last):\n",
            "  File \"/usr/local/bin/pip3\", line 8, in <module>\n",
            "    sys.exit(main())\n",
            "  File \"/usr/local/lib/python3.8/dist-packages/pip/_internal/cli/main.py\", line 71, in main\n",
            "    return command.main(cmd_args)\n",
            "  File \"/usr/local/lib/python3.8/dist-packages/pip/_internal/cli/base_command.py\", line 104, in main\n",
            "    return self._main(args)\n",
            "  File \"/usr/local/lib/python3.8/dist-packages/pip/_internal/cli/base_command.py\", line 213, in _main\n",
            "    logger.debug(\"Exception information:\", exc_info=True)\n",
            "  File \"/usr/lib/python3.8/logging/__init__.py\", line 1434, in debug\n",
            "    self._log(DEBUG, msg, args, **kwargs)\n",
            "  File \"/usr/lib/python3.8/logging/__init__.py\", line 1589, in _log\n",
            "    self.handle(record)\n",
            "  File \"/usr/lib/python3.8/logging/__init__.py\", line 1599, in handle\n",
            "    self.callHandlers(record)\n",
            "  File \"/usr/lib/python3.8/logging/__init__.py\", line 1661, in callHandlers\n",
            "    hdlr.handle(record)\n",
            "  File \"/usr/lib/python3.8/logging/__init__.py\", line 954, in handle\n",
            "    self.emit(record)\n",
            "  File \"/usr/lib/python3.8/logging/handlers.py\", line 71, in emit\n",
            "    logging.FileHandler.emit(self, record)\n",
            "  File \"/usr/lib/python3.8/logging/__init__.py\", line 1187, in emit\n",
            "    StreamHandler.emit(self, record)\n",
            "  File \"/usr/lib/python3.8/logging/__init__.py\", line 1085, in emit\n",
            "    msg = self.format(record)\n",
            "  File \"/usr/lib/python3.8/logging/__init__.py\", line 929, in format\n",
            "    return fmt.format(record)\n",
            "  File \"/usr/local/lib/python3.8/dist-packages/pip/_internal/utils/logging.py\", line 130, in format\n",
            "    formatted = super().format(record)\n",
            "  File \"/usr/lib/python3.8/logging/__init__.py\", line 676, in format\n",
            "    record.exc_text = self.formatException(record.exc_info)\n",
            "  File \"/usr/lib/python3.8/logging/__init__.py\", line 626, in formatException\n",
            "    traceback.print_exception(ei[0], ei[1], tb, None, sio)\n",
            "  File \"/usr/lib/python3.8/traceback.py\", line 103, in print_exception\n",
            "    for line in TracebackException(\n",
            "  File \"/usr/lib/python3.8/traceback.py\", line 508, in __init__\n",
            "    self.stack = StackSummary.extract(\n",
            "  File \"/usr/lib/python3.8/traceback.py\", line 366, in extract\n",
            "    f.line\n",
            "  File \"/usr/lib/python3.8/traceback.py\", line 288, in line\n",
            "    self._line = linecache.getline(self.filename, self.lineno).strip()\n",
            "  File \"/usr/lib/python3.8/linecache.py\", line 16, in getline\n",
            "    lines = getlines(filename, module_globals)\n",
            "  File \"/usr/lib/python3.8/linecache.py\", line 47, in getlines\n",
            "    return updatecache(filename, module_globals)\n",
            "  File \"/usr/lib/python3.8/linecache.py\", line 136, in updatecache\n",
            "    with tokenize.open(fullname) as fp:\n",
            "  File \"/usr/lib/python3.8/tokenize.py\", line 394, in open\n",
            "    encoding, lines = detect_encoding(buffer.readline)\n",
            "  File \"/usr/lib/python3.8/tokenize.py\", line 363, in detect_encoding\n",
            "    first = read_or_stop()\n",
            "  File \"/usr/lib/python3.8/tokenize.py\", line 321, in read_or_stop\n",
            "    return readline()\n",
            "KeyboardInterrupt\n",
            "^C\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "V0Nvh_-qEo1q"
      },
      "source": [
        "We can now use the library to download and import the dataset. Initializing the `Planetoid` class returns a `Dataset` object that can contain multiple graphs. In this task we will only use the `Cora` dataset (the citation network) and hence, we will select only the first element."
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "import torch\n",
        "\n",
        "# !pip uninstall torch-scatter torch-sparse torch-geometric torch-cluster  --y\n",
        "!pip install torch-scatter -f https://data.pyg.org/whl/torch-{torch.__version__}.html\n",
        "!pip install torch-sparse -f https://data.pyg.org/whl/torch-{torch.__version__}.html\n",
        "!pip install torch-cluster -f https://data.pyg.org/whl/torch-{torch.__version__}.html\n",
        "!pip install git+https://github.com/pyg-team/pytorch_geometric.git"
      ],
      "metadata": {
        "id": "l4YzMB4nqQCb",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "2fd571cb-bb23-4244-e48f-a3c854b5b16f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Looking in links: https://data.pyg.org/whl/torch-1.13.0+cu116.html\n",
            "Collecting torch-scatter\n",
            "  Downloading https://data.pyg.org/whl/torch-1.13.0%2Bcu116/torch_scatter-2.1.0%2Bpt113cu116-cp38-cp38-linux_x86_64.whl (9.4 MB)\n",
            "\u001b[K     |████████████████████████████████| 9.4 MB 9.8 MB/s \n",
            "\u001b[?25hInstalling collected packages: torch-scatter\n",
            "Successfully installed torch-scatter-2.1.0+pt113cu116\n",
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Looking in links: https://data.pyg.org/whl/torch-1.13.0+cu116.html\n",
            "Collecting torch-sparse\n",
            "  Downloading https://data.pyg.org/whl/torch-1.13.0%2Bcu116/torch_sparse-0.6.16%2Bpt113cu116-cp38-cp38-linux_x86_64.whl (4.5 MB)\n",
            "\u001b[K     |████████████████████████████████| 4.5 MB 50.2 MB/s \n",
            "\u001b[?25hRequirement already satisfied: scipy in /usr/local/lib/python3.8/dist-packages (from torch-sparse) (1.7.3)\n",
            "Requirement already satisfied: numpy<1.23.0,>=1.16.5 in /usr/local/lib/python3.8/dist-packages (from scipy->torch-sparse) (1.21.6)\n",
            "Installing collected packages: torch-sparse\n",
            "Successfully installed torch-sparse-0.6.16+pt113cu116\n",
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Looking in links: https://data.pyg.org/whl/torch-1.13.0+cu116.html\n",
            "Collecting torch-cluster\n",
            "  Downloading https://data.pyg.org/whl/torch-1.13.0%2Bcu116/torch_cluster-1.6.0%2Bpt113cu116-cp38-cp38-linux_x86_64.whl (3.2 MB)\n",
            "\u001b[K     |████████████████████████████████| 3.2 MB 46.8 MB/s \n",
            "\u001b[?25hRequirement already satisfied: scipy in /usr/local/lib/python3.8/dist-packages (from torch-cluster) (1.7.3)\n",
            "Requirement already satisfied: numpy<1.23.0,>=1.16.5 in /usr/local/lib/python3.8/dist-packages (from scipy->torch-cluster) (1.21.6)\n",
            "Installing collected packages: torch-cluster\n",
            "Successfully installed torch-cluster-1.6.0+pt113cu116\n",
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Collecting git+https://github.com/pyg-team/pytorch_geometric.git\n",
            "  Cloning https://github.com/pyg-team/pytorch_geometric.git to /tmp/pip-req-build-soyql55k\n",
            "  Running command git clone -q https://github.com/pyg-team/pytorch_geometric.git /tmp/pip-req-build-soyql55k\n",
            "Requirement already satisfied: tqdm in /usr/local/lib/python3.8/dist-packages (from torch-geometric==2.2.0) (4.64.1)\n",
            "Requirement already satisfied: numpy in /usr/local/lib/python3.8/dist-packages (from torch-geometric==2.2.0) (1.21.6)\n",
            "Requirement already satisfied: scipy in /usr/local/lib/python3.8/dist-packages (from torch-geometric==2.2.0) (1.7.3)\n",
            "Requirement already satisfied: jinja2 in /usr/local/lib/python3.8/dist-packages (from torch-geometric==2.2.0) (2.11.3)\n",
            "Requirement already satisfied: requests in /usr/local/lib/python3.8/dist-packages (from torch-geometric==2.2.0) (2.23.0)\n",
            "Requirement already satisfied: pyparsing in /usr/local/lib/python3.8/dist-packages (from torch-geometric==2.2.0) (3.0.9)\n",
            "Collecting torchmetrics\n",
            "  Downloading torchmetrics-0.11.0-py3-none-any.whl (512 kB)\n",
            "\u001b[K     |████████████████████████████████| 512 kB 40.7 MB/s \n",
            "\u001b[?25hRequirement already satisfied: scikit-learn in /usr/local/lib/python3.8/dist-packages (from torch-geometric==2.2.0) (1.0.2)\n",
            "Collecting psutil>=5.8.0\n",
            "  Using cached psutil-5.9.4-cp36-abi3-manylinux_2_12_x86_64.manylinux2010_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (280 kB)\n",
            "Requirement already satisfied: MarkupSafe>=0.23 in /usr/local/lib/python3.8/dist-packages (from jinja2->torch-geometric==2.2.0) (2.0.1)\n",
            "Requirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.8/dist-packages (from requests->torch-geometric==2.2.0) (2022.12.7)\n",
            "Requirement already satisfied: chardet<4,>=3.0.2 in /usr/local/lib/python3.8/dist-packages (from requests->torch-geometric==2.2.0) (3.0.4)\n",
            "Requirement already satisfied: urllib3!=1.25.0,!=1.25.1,<1.26,>=1.21.1 in /usr/local/lib/python3.8/dist-packages (from requests->torch-geometric==2.2.0) (1.24.3)\n",
            "Requirement already satisfied: idna<3,>=2.5 in /usr/local/lib/python3.8/dist-packages (from requests->torch-geometric==2.2.0) (2.10)\n",
            "Requirement already satisfied: joblib>=0.11 in /usr/local/lib/python3.8/dist-packages (from scikit-learn->torch-geometric==2.2.0) (1.2.0)\n",
            "Requirement already satisfied: threadpoolctl>=2.0.0 in /usr/local/lib/python3.8/dist-packages (from scikit-learn->torch-geometric==2.2.0) (3.1.0)\n",
            "Requirement already satisfied: typing-extensions in /usr/local/lib/python3.8/dist-packages (from torchmetrics->torch-geometric==2.2.0) (4.4.0)\n",
            "Requirement already satisfied: packaging in /usr/local/lib/python3.8/dist-packages (from torchmetrics->torch-geometric==2.2.0) (21.3)\n",
            "Requirement already satisfied: torch>=1.8.1 in /usr/local/lib/python3.8/dist-packages (from torchmetrics->torch-geometric==2.2.0) (1.13.0+cu116)\n",
            "Building wheels for collected packages: torch-geometric\n",
            "  Building wheel for torch-geometric (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
            "  Created wheel for torch-geometric: filename=torch_geometric-2.2.0-py3-none-any.whl size=806401 sha256=a68267e52d0c946867045042e7b2fa1c1b2bd892a8136066774e754027e343d2\n",
            "  Stored in directory: /tmp/pip-ephem-wheel-cache-p7g4glbp/wheels/ba/e1/8e/28297c3201c884d3ea8c47ba71a9e71e547e556c0caa9cf5a2\n",
            "Successfully built torch-geometric\n",
            "Installing collected packages: torchmetrics, psutil, torch-geometric\n",
            "  Attempting uninstall: psutil\n",
            "    Found existing installation: psutil 5.4.8\n",
            "    Uninstalling psutil-5.4.8:\n",
            "      Successfully uninstalled psutil-5.4.8\n",
            "Successfully installed psutil-5.9.4 torch-geometric-2.2.0 torchmetrics-0.11.0\n"
          ]
        },
        {
          "output_type": "display_data",
          "data": {
            "application/vnd.colab-display-data+json": {
              "pip_warning": {
                "packages": [
                  "psutil"
                ]
              }
            }
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vuOvwhsHD2YK",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0f8b83f6-d4f4-404b-ac8b-ebfa7a26b69d"
      },
      "source": [
        "from torch_geometric.datasets import Planetoid\n",
        "data = Planetoid(root='data/Planetoid', name='Cora')[0]"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "Downloading https://github.com/kimiyoung/planetoid/raw/master/data/ind.cora.x\n",
            "Downloading https://github.com/kimiyoung/planetoid/raw/master/data/ind.cora.tx\n",
            "Downloading https://github.com/kimiyoung/planetoid/raw/master/data/ind.cora.allx\n",
            "Downloading https://github.com/kimiyoung/planetoid/raw/master/data/ind.cora.y\n",
            "Downloading https://github.com/kimiyoung/planetoid/raw/master/data/ind.cora.ty\n",
            "Downloading https://github.com/kimiyoung/planetoid/raw/master/data/ind.cora.ally\n",
            "Downloading https://github.com/kimiyoung/planetoid/raw/master/data/ind.cora.graph\n",
            "Downloading https://github.com/kimiyoung/planetoid/raw/master/data/ind.cora.test.index\n",
            "Processing...\n",
            "Done!\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "v4WZkoiHFyZm"
      },
      "source": [
        "\n",
        "#### Question 1 (0.25 pt)\n",
        "\n",
        "The `data` object is an instance of the `Data` class in PyG. Check the [documentation](https://pytorch-geometric.readthedocs.io/en/latest/modules/data.html) and report the following properties of the graph:\n",
        "\n",
        "- Number of nodes\n",
        "- Number of edges \n",
        "- The dimension $c$ of the feature vectors $x\\in\\mathbb{R}^c$\n",
        "- The number of targets for the classification task"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sjVuGJhlJC_7",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ce3a8e3f-7461-4b8e-f52c-45131cac37b4"
      },
      "source": [
        "# Your answer here\n",
        "print(\"The number of nodes is: \", data.num_nodes)\n",
        "print(\"The number of edges is: \", data.num_edges)\n",
        "print(\"The dimension c of the feature vectors is: \", data.x.shape[1])\n",
        "try: \n",
        "    print(\"The number of target classes is: \", data.num_classes)\n",
        "except AttributeError:\n",
        "    data.num_classes = len(data.y.unique())\n",
        "    print(\"The number of target classes is: \", data.num_classes)\n",
        "# num_classes = data.num_classes"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The number of nodes is:  2708\n",
            "The number of edges is:  10556\n",
            "The dimension c of the feature vectors is:  1433\n",
            "The number of target classes is:  7\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "G4DrGDAuJ2YO"
      },
      "source": [
        "#### Question 2 (0.25 pt)\n",
        "\n",
        "In PyG, edges are provided in a tensor of shape (2, number of edges). You can access it via `data.edge_index`. Each column in this tensor contains the IDs for two nodes that are connected in the graph.\n",
        "\n",
        "We saw that in an undirected graph, an edge between nodes $i$ and $j$ adds a value of 1 to positions $(i, j)$ and $(j, i)$ of the adjacency matrix. Is this also true for the edge index? That is, if there is an edge $(i, j)$ in `data.edge_index`, is there also an edge for $(j, i)$? This is important to know for the next steps of the implementation."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jTRfNxibarRZ",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4c6e97ce-25c9-4e2a-9483-211fef305ec1"
      },
      "source": [
        "# Your answer here\n",
        "undirected = data.is_undirected()\n",
        "if undirected:\n",
        "    print(\"The graph is undirected\")\n",
        "else:\n",
        "    print(\"The graph is directed\")\n",
        "\n",
        "# Additional code to check if the graph is undirected\n",
        "undirected = True\n",
        "for edge in data.edge_index.T:\n",
        "    if reversed(edge) not in data.edge_index.T:\n",
        "        undirected = False\n",
        "        print(\"The graph is directed\")\n",
        "        break\n",
        "if undirected:\n",
        "    print(\"The graph is undirected\")\n",
        "\n",
        "print(data.edge_index[:, -5:])\n",
        "        "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The graph is undirected\n",
            "The graph is undirected\n",
            "tensor([[2706, 2707, 2707, 2707, 2707],\n",
            "        [2707,  165,  598, 1473, 2706]])\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YOpS3QTYiOqp"
      },
      "source": [
        "#### Question 3 (0.5 pt)\n",
        "\n",
        "In graphs, especially large ones, the adjacency matrix is **sparse**: most entries are zero. Sparse matrices allow for efficient storage and computation.\n",
        "\n",
        "To prepare and pre-process sparse matrices, we will use [`scipy.sparse`](https://docs.scipy.org/doc/scipy/reference/sparse.html). Once the matrices are ready, we will convert them to PyTorch tensors.\n",
        "\n",
        "We will use the [Sparse COO format](https://en.wikipedia.org/wiki/Sparse_matrix#Coordinate_list_(COO)). We encourage you to first get familiar with how it works after continuing with the assignment.\n",
        "\n",
        "- Use the [`scipy.sparse.coo_matrix()`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.coo_matrix.html) function to build the adjacency matrix. Think of what arguments are needed, and how you can obtain them from the graph data loaded above.\n",
        "- Use the `sum()` method of sparse matrices, together with `scipy.sparse.diags()`, to compute the degree matrix using the definition above.\n",
        "\n",
        "Both resulting matrices must be sparse of type `float32`."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QC01OjbJs92-",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6678f2c3-0b07-4090-b884-6c1cb5a50270"
      },
      "source": [
        "# Your answer here\n",
        "import scipy\n",
        "import scipy.sparse as sp\n",
        "import numpy as np\n",
        "adj = sp.coo_matrix((np.ones(data.edge_index.shape[1]), (data.edge_index[0], data.edge_index[1])), shape=(data.num_nodes, data.num_nodes))\n",
        "degree = sp.diags(adj.toarray().sum(axis=1))\n",
        "print(adj)\n",
        "print(degree)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "  (0, 633)\t1.0\n",
            "  (0, 1862)\t1.0\n",
            "  (0, 2582)\t1.0\n",
            "  (1, 2)\t1.0\n",
            "  (1, 652)\t1.0\n",
            "  (1, 654)\t1.0\n",
            "  (2, 1)\t1.0\n",
            "  (2, 332)\t1.0\n",
            "  (2, 1454)\t1.0\n",
            "  (2, 1666)\t1.0\n",
            "  (2, 1986)\t1.0\n",
            "  (3, 2544)\t1.0\n",
            "  (4, 1016)\t1.0\n",
            "  (4, 1256)\t1.0\n",
            "  (4, 1761)\t1.0\n",
            "  (4, 2175)\t1.0\n",
            "  (4, 2176)\t1.0\n",
            "  (5, 1629)\t1.0\n",
            "  (5, 1659)\t1.0\n",
            "  (5, 2546)\t1.0\n",
            "  (6, 373)\t1.0\n",
            "  (6, 1042)\t1.0\n",
            "  (6, 1416)\t1.0\n",
            "  (6, 1602)\t1.0\n",
            "  (7, 208)\t1.0\n",
            "  :\t:\n",
            "  (2694, 431)\t1.0\n",
            "  (2694, 2695)\t1.0\n",
            "  (2695, 431)\t1.0\n",
            "  (2695, 2694)\t1.0\n",
            "  (2696, 2615)\t1.0\n",
            "  (2697, 986)\t1.0\n",
            "  (2698, 1400)\t1.0\n",
            "  (2698, 1573)\t1.0\n",
            "  (2699, 2630)\t1.0\n",
            "  (2700, 1151)\t1.0\n",
            "  (2701, 44)\t1.0\n",
            "  (2701, 2624)\t1.0\n",
            "  (2702, 186)\t1.0\n",
            "  (2702, 1536)\t1.0\n",
            "  (2703, 1298)\t1.0\n",
            "  (2704, 641)\t1.0\n",
            "  (2705, 287)\t1.0\n",
            "  (2706, 165)\t1.0\n",
            "  (2706, 169)\t1.0\n",
            "  (2706, 1473)\t1.0\n",
            "  (2706, 2707)\t1.0\n",
            "  (2707, 165)\t1.0\n",
            "  (2707, 598)\t1.0\n",
            "  (2707, 1473)\t1.0\n",
            "  (2707, 2706)\t1.0\n",
            "  (0, 0)\t3.0\n",
            "  (1, 1)\t3.0\n",
            "  (2, 2)\t5.0\n",
            "  (3, 3)\t1.0\n",
            "  (4, 4)\t5.0\n",
            "  (5, 5)\t3.0\n",
            "  (6, 6)\t4.0\n",
            "  (7, 7)\t1.0\n",
            "  (8, 8)\t3.0\n",
            "  (9, 9)\t2.0\n",
            "  (10, 10)\t2.0\n",
            "  (11, 11)\t2.0\n",
            "  (12, 12)\t4.0\n",
            "  (13, 13)\t2.0\n",
            "  (14, 14)\t5.0\n",
            "  (15, 15)\t4.0\n",
            "  (16, 16)\t4.0\n",
            "  (17, 17)\t5.0\n",
            "  (18, 18)\t5.0\n",
            "  (19, 19)\t1.0\n",
            "  (20, 20)\t5.0\n",
            "  (21, 21)\t2.0\n",
            "  (22, 22)\t5.0\n",
            "  (23, 23)\t1.0\n",
            "  (24, 24)\t7.0\n",
            "  :\t:\n",
            "  (2683, 2683)\t1.0\n",
            "  (2684, 2684)\t2.0\n",
            "  (2685, 2685)\t4.0\n",
            "  (2686, 2686)\t2.0\n",
            "  (2687, 2687)\t2.0\n",
            "  (2688, 2688)\t3.0\n",
            "  (2689, 2689)\t2.0\n",
            "  (2690, 2690)\t1.0\n",
            "  (2691, 2691)\t2.0\n",
            "  (2692, 2692)\t1.0\n",
            "  (2693, 2693)\t1.0\n",
            "  (2694, 2694)\t2.0\n",
            "  (2695, 2695)\t2.0\n",
            "  (2696, 2696)\t1.0\n",
            "  (2697, 2697)\t1.0\n",
            "  (2698, 2698)\t2.0\n",
            "  (2699, 2699)\t1.0\n",
            "  (2700, 2700)\t1.0\n",
            "  (2701, 2701)\t2.0\n",
            "  (2702, 2702)\t2.0\n",
            "  (2703, 2703)\t1.0\n",
            "  (2704, 2704)\t1.0\n",
            "  (2705, 2705)\t1.0\n",
            "  (2706, 2706)\t4.0\n",
            "  (2707, 2707)\t4.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AIEJyQi2TzyY"
      },
      "source": [
        "You might wonder why we suggest to use a scipy sparse matrix, while also PyTorch supports them. The reason is that in the next step, we will be multiplying two sparse matrices, an operation not supported in PyTorch. PyTorch only allows multiplying a sparse matrix with a dense one, something which we will be doing at a later stage.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YlmzSb0up4LB"
      },
      "source": [
        "### The Graph Convolutional Network\n",
        "\n",
        "The goal of the graph convolution is to take the feature vectors of all nodes $X\\in\\mathbb{R}^{n\\times c}$, and propagate them along the existing edges, to obtain updated representations $Z\\in\\mathbb{R}^{n\\times d}$.\n",
        "\n",
        "\n",
        "The GCN is initially motivated as performing a convolution, similarly as it is done in CNNs for images, for graph-structured data. In Kipf and Welling (2017), a theoretical derivation leads to the following formula:\n",
        "\n",
        "$$\n",
        "Z = \\tilde{D}^{-\\frac{1}{2}}\\tilde{A}\\tilde{D}^{-\\frac{1}{2}}XW\n",
        "$$\n",
        "\n",
        "where\n",
        "\n",
        "- $W\\in\\mathbb{R}^{c\\times d}$ is a matrix of parameters to be learned via gradient descent\n",
        "- $\\tilde{A} = A + I_n$, where $I_n$ is an $n\\times n$ identity matrix\n",
        "- $\\tilde{D}$ is the degree matrix computed with $\\tilde{A}$ as the adjacency matrix\n",
        "\n",
        "If we define $\\hat{A} = \\tilde{D}^{-\\frac{1}{2}}\\tilde{A}\\tilde{D}^{-\\frac{1}{2}}$, the graph convolution can be written as $Z = \\hat{A}XW$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LL4b-MTvysBp"
      },
      "source": [
        "#### Question 4 (0.25 pt)\n",
        "\n",
        "Given the formula for the GCN, explain why it operates by propagating feature vectors across the graph. To answer this, it might be useful to recall the definitions of the adjacency and degree matrices, and how they are involved in the formula."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Vgx2SkTTyiSN"
      },
      "source": [
        "*Answer:*\n",
        "The adjacency matrix $A$ of a graph defines the connections between nodes in the graph, such that $A_{ij}$ is non-zero if and only if there is an edge between node $i$ and node $j$. The degree matrix $D$ is a diagonal matrix where the $i$-th diagonal element is the degree of the $i$-th node in the graph. In other words, it is a measure of how many connections each node has.\n",
        "\n",
        "In the GCN formula, the adjacency matrix is first augmented with an identity matrix, resulting in $\\tilde{A}$. This addition allows the formula to take into account self-connections, or connections between a node and itself. The degree matrix is then computed using $\\tilde{A}$ as the adjacency matrix, resulting in $\\tilde{D}$.\n",
        "\n",
        "The resulting matrices, $\\tilde{A}$ and $\\tilde{D}$, are then used to compute $\\hat{A} = \\tilde{D}^{-\\frac{1}{2}}\\tilde{A}\\tilde{D}^{-\\frac{1}{2}}$. This operation effectively scales the adjacency matrix by the inverse square root of the degree matrix, which has the effect of \"normalizing\" the connections between nodes. The inverse square root of the degree matrix is computed element-wise, so for a given element $d_{ij}$ in the degree matrix, its inverse square root is computed as $\\frac{1}{\\sqrt{d_{ij}}}$.\n",
        "\n",
        "Finally, the graph convolution is computed as $Z = \\hat{A}XW$. Since $\\hat{A}$ encodes the connections between nodes in the graph, this operation effectively \"propagates\" the feature vectors of the nodes across the graph, taking into account the normalized connections between nodes. In other words, the updated feature vectors $Z$ will incorporate information from the neighboring nodes, weighted by the normalized connections between them. This is how the GCN operates by propagating feature vectors across the graph."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QUGABEqxylsd"
      },
      "source": [
        "#### Question 5 (0.5 pt)\n",
        "\n",
        "Compute the **normalized adjacency matrix** $\\hat{A}$. The result should be a sparse matrix."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GPZbnSaSyDzO",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "77c0c8e6-b242-4532-8fa0-b507ab049d5c"
      },
      "source": [
        "# Your answer here\n",
        "adj_norm = degree.power(-1/2) @ adj @ degree.power(-1/2)\n",
        "print(adj_norm)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "  (0, 633)\t0.3333333333333333\n",
            "  (0, 1862)\t0.28867513459481287\n",
            "  (0, 2582)\t0.3333333333333333\n",
            "  (1, 2)\t0.2581988897471611\n",
            "  (1, 652)\t0.408248290463863\n",
            "  (1, 654)\t0.5773502691896257\n",
            "  (2, 1)\t0.2581988897471611\n",
            "  (2, 332)\t0.19999999999999998\n",
            "  (2, 1454)\t0.4472135954999579\n",
            "  (2, 1666)\t0.18257418583505536\n",
            "  (2, 1986)\t0.05547001962252291\n",
            "  (3, 2544)\t1.0\n",
            "  (4, 1016)\t0.19999999999999998\n",
            "  (4, 1256)\t0.15811388300841897\n",
            "  (4, 1761)\t0.16903085094570333\n",
            "  (4, 2175)\t0.19999999999999998\n",
            "  (4, 2176)\t0.15811388300841897\n",
            "  (5, 1629)\t0.3333333333333333\n",
            "  (5, 1659)\t0.408248290463863\n",
            "  (5, 2546)\t0.28867513459481287\n",
            "  (6, 373)\t0.28867513459481287\n",
            "  (6, 1042)\t0.10425720702853739\n",
            "  (6, 1416)\t0.11785113019775792\n",
            "  (6, 1602)\t0.15811388300841897\n",
            "  (7, 208)\t1.0\n",
            "  :\t:\n",
            "  (2694, 431)\t0.5000000000000001\n",
            "  (2694, 2695)\t0.5000000000000001\n",
            "  (2695, 431)\t0.5000000000000001\n",
            "  (2695, 2694)\t0.5000000000000001\n",
            "  (2696, 2615)\t0.7071067811865476\n",
            "  (2697, 986)\t1.0\n",
            "  (2698, 1400)\t0.5000000000000001\n",
            "  (2698, 1573)\t0.5000000000000001\n",
            "  (2699, 2630)\t0.7071067811865476\n",
            "  (2700, 1151)\t0.7071067811865476\n",
            "  (2701, 44)\t0.408248290463863\n",
            "  (2701, 2624)\t0.5000000000000001\n",
            "  (2702, 186)\t0.2886751345948129\n",
            "  (2702, 1536)\t0.3535533905932738\n",
            "  (2703, 1298)\t1.0\n",
            "  (2704, 641)\t1.0\n",
            "  (2705, 287)\t1.0\n",
            "  (2706, 165)\t0.25\n",
            "  (2706, 169)\t0.3535533905932738\n",
            "  (2706, 1473)\t0.25\n",
            "  (2706, 2707)\t0.25\n",
            "  (2707, 165)\t0.25\n",
            "  (2707, 598)\t0.08703882797784893\n",
            "  (2707, 1473)\t0.25\n",
            "  (2707, 2706)\t0.25\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LLLdGdZoMEy-"
      },
      "source": [
        "#### Question 6 (0.5 pt)\n",
        "\n",
        "So far we have used scipy to build and compute sparse matrices. Since we want to train a GCN with PyTorch, we need to convert $\\hat{A}$ into a sparse PyTorch tensor. You can do this with the [`torch.sparse_coo_tensor()`](https://pytorch.org/docs/stable/generated/torch.sparse_coo_tensor.html) function, making sure to specify `torch.float` as the type."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dgDsVHzEM32F",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "bdd47182-ff9d-400e-a51e-15c26109d514"
      },
      "source": [
        "# Your answer here\n",
        "import torch\n",
        "adj_norm = torch.sparse_coo_tensor(indices=adj_norm.nonzero(), values=adj_norm.data, size=adj_norm.shape, dtype=torch.float)\n",
        "adj_norm"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "<ipython-input-8-0dac29c2fbab>:3: UserWarning: Creating a tensor from a list of numpy.ndarrays is extremely slow. Please consider converting the list to a single numpy.ndarray with numpy.array() before converting to a tensor. (Triggered internally at ../torch/csrc/utils/tensor_new.cpp:230.)\n",
            "  adj_norm = torch.sparse_coo_tensor(indices=adj_norm.nonzero(), values=adj_norm.data, size=adj_norm.shape, dtype=torch.float)\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "tensor(indices=tensor([[   0,    0,    0,  ..., 2707, 2707, 2707],\n",
              "                       [ 633, 1862, 2582,  ...,  598, 1473, 2706]]),\n",
              "       values=tensor([0.3333, 0.2887, 0.3333,  ..., 0.0870, 0.2500, 0.2500]),\n",
              "       size=(2708, 2708), nnz=10556, layout=torch.sparse_coo)"
            ]
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eAlRVT5aODkX"
      },
      "source": [
        "#### Question 7 (0.5 pt)\n",
        "\n",
        "We now have all the ingredients to build a GCN layer. Implement a class (inheriting from `torch.nn.Module`) with a learnable matrix of weights $W\\in\\mathbb{R}^{c\\times d}$. Make sure to\n",
        "\n",
        "- Call this class `GCNLayer`\n",
        "- The `__init__()` constructor should take as argument the number of input and output features.\n",
        "- Use `torch.nn.init.kaiming_uniform_` to initialize $W$.\n",
        "- Define the `forward` method, which takes as input $X$ and $\\hat{A}$ and returns $Z$. Note that multiplications involving the sparse matrix $\\hat{A}$ have to be done with `torch.spmm`. \n",
        "\n",
        "Once you have implemented the class, instantiate a layer with the correct number of input features for the Cora dataset, and a number of output features of your choice. Do a forward pass and report the shape of the output tensor."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JFCohhhwPpTT",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "07903c39-d74a-4e06-9186-7d08d4dcc5bf"
      },
      "source": [
        "# Your answer here\n",
        "class GCNLayer(torch.nn.Module):\n",
        "    def __init__(self, in_features, out_features):\n",
        "        super(GCNLayer, self).__init__()\n",
        "        self.linear = torch.nn.Linear(in_features, out_features)\n",
        "        torch.nn.init.kaiming_uniform_(self.linear.weight)\n",
        "        \n",
        "    def forward(self, x, adj_norm):\n",
        "        x = self.linear(x)\n",
        "        x = torch.spmm(adj_norm, x)\n",
        "        return x\n",
        "\n",
        "out_features = 100\n",
        "\n",
        "cgn = GCNLayer(data.num_features, out_features)\n",
        "print(f\"Output shape: numebr of nodes x number of output features\")\n",
        "print(cgn.forward(data.x, adj_norm).shape)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Output shape: numebr of nodes x number of output features\n",
            "torch.Size([2708, 100])\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1ptAiizZUKaM"
      },
      "source": [
        "#### Question 8 (0.5 pt)\n",
        "\n",
        "As we have seen so far, the GCN layer implements a special type of linear transformation of the inputs. However, it is often beneficial in deep learning to stack multiple, non-linear transformations of the input features. Implement a second module class for a model with two GCN layers (use the module you implemented in the previous question).\n",
        "\n",
        "- Call this class `GCN`\n",
        "- The constructor must now take as input the number of input features, the output dimension of the first layer (this is the hidden layer), and the output dimension of the output layer.\n",
        "- In the forward pass, add a ReLU activation function after the first layer."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2zhyu3S9Vj3b"
      },
      "source": [
        "# Your answer here\n",
        "class GCN(torch.nn.Module):\n",
        "    def __init__(self, in_features, hidden_features, out_features):\n",
        "        super().__init__()\n",
        "        self.layer1 = GCNLayer(in_features, hidden_features)\n",
        "        self.layer2 = GCNLayer(hidden_features, out_features)\n",
        "        self.relu = torch.nn.ReLU()\n",
        "\n",
        "    def forward(self, x, adj):\n",
        "        x = self.layer1(x, adj)\n",
        "        x = self.relu(x)\n",
        "        x = self.layer2(x, adj)\n",
        "        x = self.relu(x)\n",
        "        return x\n",
        "\n",
        "    @staticmethod\n",
        "    def fit(x, y, train_idx, val_idx, adj_norm, n_hidden, epochs=100, batch_size=32, lr=0.001):\n",
        "        gcn = GCN(in_features=x.shape[1], hidden_features=n_hidden, out_features=len(y.unique()))\n",
        "        \n",
        "        criterion = torch.nn.CrossEntropyLoss()\n",
        "        optimizer = torch.optim.Adam(gcn.parameters(), lr=lr)\n",
        "\n",
        "        for epoch in range(epochs+1):\n",
        "            # Forward pass\n",
        "            yhat = gcn(x, adj_norm)\n",
        "            _, predictions = torch.max(yhat, 1)\n",
        "            predictions = predictions[val_idx]\n",
        "            acc_val = (predictions == y[val_idx]).sum().item() / len(y[val_idx])\n",
        "            print(f\"Epoch: {epoch}\\nValidation accuracy: {acc_val}\")\n",
        "            \n",
        "            optimizer.zero_grad()\n",
        "            yhat = gcn(x, adj_norm)\n",
        "            loss = criterion(yhat[train_idx], y[train_idx])\n",
        "            loss.backward()\n",
        "            optimizer.step()\n",
        "        \n",
        "        return gcn"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6NVB-3I5Wfkf"
      },
      "source": [
        "### GCNs for semi-supervised node classification\n",
        "\n",
        "Now that we have a GCN with two layers, we can test its performance in a node classification task. We will pass the input node features $X$ through the GCN layers, and the output will be of size $n\\times k$ where $k$ is the number of classes (which you found in question 1). The label denotes the topic an article in the citation network belongs to (e.g. physics, computer science, etc.)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "trc4dSa7cuQj"
      },
      "source": [
        "#### Question 9 (1.5 pt)\n",
        "\n",
        "Note that the `data` object contains all labels (for all splits) in `data.y`, and binary masks for the train, validation, and test splits in `data.train_mask`, `data.val_mask`, and `data.test_mask`, respectively. These masks are the same size as `data.y`, and indicate which labels belong to which split.\n",
        "\n",
        "- Create a GCN with two layers (using the class from the previous question), with 32 as the hidden dimension, and the number of output features equal to the number of classes in the Cora dataset.\n",
        "\n",
        "- Use the Adam optimizer with a learning rate of 0.01.\n",
        "\n",
        "- Implement a training loop for the GCN. At each step, pass $X$ and $\\hat{A}$ to the GCN to obtain the logits. Compute the mean cross-entropy loss **only for the training instances**, using the binary masks.\n",
        "\n",
        "- After each training step, evaluate the accuracy for the validation instances.\n",
        "\n",
        "- Train for 100 epochs. Once training is finished, plot the training loss and validation accuracy (in a graph in function of the epoch number), and report the accuracy in the test set.\n",
        "\n",
        "You should obtain an accuracy over 75% on both the validation and test sets. You can also compare your results with the original paper, which also contains results for the Cora dataset. Give a brief discussion on the results of your experiments.\n",
        "\n",
        "Note that in contrast with other tasks, like image classification on some datasets, we don't use mini-batches here. The whole matrix of features and the adjacency is passed to the GCN in one step."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5Z2OP_ZRWlmo",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1009f382-cb33-4c69-eabb-0e90ab051c39"
      },
      "source": [
        "# Your answer here\n",
        "train_idx = data.train_mask\n",
        "val_idx = data.val_mask\n",
        "test_idx = data.test_mask\n",
        "\n",
        "# Split data\n",
        "xtrain = data.x[train_idx]\n",
        "ytrain = data.y[train_idx]\n",
        "xval = data.x[val_idx]\n",
        "yval = data.y[val_idx]\n",
        "xtest = data.x[test_idx]\n",
        "ytest = data.y[test_idx]\n",
        "\n",
        "# Split adjacency matrix\n",
        "gcn = GCN.fit(\n",
        "    x=data.x,\n",
        "    y=data.y,\n",
        "    train_idx=train_idx,\n",
        "    val_idx=val_idx,\n",
        "    adj_norm = adj_norm,\n",
        "    n_hidden=32,\n",
        "    epochs=100,\n",
        "    lr=0.01)\n",
        "    "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Epoch: 0\n",
            "Validation accuracy: 0.102\n",
            "Epoch: 1\n",
            "Validation accuracy: 0.384\n",
            "Epoch: 2\n",
            "Validation accuracy: 0.488\n",
            "Epoch: 3\n",
            "Validation accuracy: 0.492\n",
            "Epoch: 4\n",
            "Validation accuracy: 0.494\n",
            "Epoch: 5\n",
            "Validation accuracy: 0.512\n",
            "Epoch: 6\n",
            "Validation accuracy: 0.528\n",
            "Epoch: 7\n",
            "Validation accuracy: 0.544\n",
            "Epoch: 8\n",
            "Validation accuracy: 0.564\n",
            "Epoch: 9\n",
            "Validation accuracy: 0.58\n",
            "Epoch: 10\n",
            "Validation accuracy: 0.612\n",
            "Epoch: 11\n",
            "Validation accuracy: 0.662\n",
            "Epoch: 12\n",
            "Validation accuracy: 0.734\n",
            "Epoch: 13\n",
            "Validation accuracy: 0.77\n",
            "Epoch: 14\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 15\n",
            "Validation accuracy: 0.802\n",
            "Epoch: 16\n",
            "Validation accuracy: 0.798\n",
            "Epoch: 17\n",
            "Validation accuracy: 0.796\n",
            "Epoch: 18\n",
            "Validation accuracy: 0.792\n",
            "Epoch: 19\n",
            "Validation accuracy: 0.794\n",
            "Epoch: 20\n",
            "Validation accuracy: 0.8\n",
            "Epoch: 21\n",
            "Validation accuracy: 0.8\n",
            "Epoch: 22\n",
            "Validation accuracy: 0.8\n",
            "Epoch: 23\n",
            "Validation accuracy: 0.8\n",
            "Epoch: 24\n",
            "Validation accuracy: 0.798\n",
            "Epoch: 25\n",
            "Validation accuracy: 0.79\n",
            "Epoch: 26\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 27\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 28\n",
            "Validation accuracy: 0.782\n",
            "Epoch: 29\n",
            "Validation accuracy: 0.782\n",
            "Epoch: 30\n",
            "Validation accuracy: 0.782\n",
            "Epoch: 31\n",
            "Validation accuracy: 0.782\n",
            "Epoch: 32\n",
            "Validation accuracy: 0.782\n",
            "Epoch: 33\n",
            "Validation accuracy: 0.78\n",
            "Epoch: 34\n",
            "Validation accuracy: 0.78\n",
            "Epoch: 35\n",
            "Validation accuracy: 0.78\n",
            "Epoch: 36\n",
            "Validation accuracy: 0.78\n",
            "Epoch: 37\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 38\n",
            "Validation accuracy: 0.79\n",
            "Epoch: 39\n",
            "Validation accuracy: 0.79\n",
            "Epoch: 40\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 41\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 42\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 43\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 44\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 45\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 46\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 47\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 48\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 49\n",
            "Validation accuracy: 0.79\n",
            "Epoch: 50\n",
            "Validation accuracy: 0.79\n",
            "Epoch: 51\n",
            "Validation accuracy: 0.79\n",
            "Epoch: 52\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 53\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 54\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 55\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 56\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 57\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 58\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 59\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 60\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 61\n",
            "Validation accuracy: 0.782\n",
            "Epoch: 62\n",
            "Validation accuracy: 0.782\n",
            "Epoch: 63\n",
            "Validation accuracy: 0.784\n",
            "Epoch: 64\n",
            "Validation accuracy: 0.784\n",
            "Epoch: 65\n",
            "Validation accuracy: 0.784\n",
            "Epoch: 66\n",
            "Validation accuracy: 0.784\n",
            "Epoch: 67\n",
            "Validation accuracy: 0.784\n",
            "Epoch: 68\n",
            "Validation accuracy: 0.784\n",
            "Epoch: 69\n",
            "Validation accuracy: 0.784\n",
            "Epoch: 70\n",
            "Validation accuracy: 0.784\n",
            "Epoch: 71\n",
            "Validation accuracy: 0.784\n",
            "Epoch: 72\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 73\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 74\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 75\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 76\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 77\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 78\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 79\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 80\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 81\n",
            "Validation accuracy: 0.788\n",
            "Epoch: 82\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 83\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 84\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 85\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 86\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 87\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 88\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 89\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 90\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 91\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 92\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 93\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 94\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 95\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 96\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 97\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 98\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 99\n",
            "Validation accuracy: 0.786\n",
            "Epoch: 100\n",
            "Validation accuracy: 0.786\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vb5YjHVClCqo"
      },
      "source": [
        "#### Question 10 (0.5 pt)\n",
        "\n",
        "The paper introduces GCNs as a way to solve a *semi-supervised* classification problem.\n",
        "\n",
        "- What makes this problem semi-supervised?\n",
        "- What is the proportion of labeled data used for training with respect to labeled data in the validation and test sets? What is difference in this context with other benchmark tasks in machine learning, like image classification with MNIST?\n",
        "- Why do you think the GCN performs well in this semi-supervised scenario?"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7qw58r1MmCUJ",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "29aa1665-0cce-48b2-c0a5-dcfee74a3e07"
      },
      "source": [
        "# Your answer here\n",
        "print(\"See text below\")"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "See text below\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "In a semi-supervised classification problem, only a portion of the training data is labeled. This means that while some of the data points in the training set have labels indicating their correct classification, many others do not. The proportion of labeled data in the training set with respect to the validation and test sets can vary, but it is typically much lower than the proportion of labeled data in a fully supervised classification problem.\n",
        "\n",
        "For example, in the MNIST image classification task, all of the data points in the training, validation, and test sets are labeled with the correct digit classification. In contrast, in a semi-supervised classification task, there might be only a few hundred labeled training examples out of a dataset with tens of thousands of examples.\n",
        "\n",
        "GCNs (Graph Convolutional Networks) are a type of neural network that can effectively make use of both labeled and unlabeled data in a semi-supervised classification setting. They do this by incorporating graph structure into the model, which can capture the relationships between different data points and help the model make better predictions for the unlabeled examples. This is especially useful in a semi-supervised setting where there is limited labeled data available for training."
      ],
      "metadata": {
        "id": "TSqW62oZoVzp"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4ihrjZddvz5d"
      },
      "source": [
        "### Loading a dataset of proteins\n",
        "\n",
        "In the previous sections you learned how to pass the adjacency matrix of a graph with a couple of thousand of nodes, to classify each node with a particular label. A different and useful application of GCNs is graph classification.\n",
        "\n",
        "In contrast with the previous part, where there was a single, big graph, in graph classification we have multiple graphs, and each graph can be assigned a label. In this part of the assignment you will implement a classifier for proteins.\n",
        "\n",
        "[Proteins](https://en.wikipedia.org/wiki/Protein_(nutrient)) are parts of the buildings block of life. They consist of chains of amino acids, and can take many shapes. In the PROTEINS dataset, proteins are represented as graphs, where the nodes are amino acids, and an edge between them indicates that they are 6 [Angstroms](https://en.wikipedia.org/wiki/Angstrom) apart. All graphs have a binary label, where 1 means that the protein is not an enzyme.\n",
        "\n",
        "We will start by loading and examining this dataset."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xmqweMcvnUH6"
      },
      "source": [
        "from torch_geometric.datasets import TUDataset\n",
        "dataset = TUDataset(root='data/TU', name='PROTEINS', use_node_attr=True)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_oF1gyKPXiz-"
      },
      "source": [
        "#### Question 11 (0.25 pt)\n",
        "\n",
        "Unlike in the previous part, where we selected the first element returned by the loading function, note that here we get all the elements returned by `TUDataset()`. `dataset` is an interable object, that has some similar behaviors as a Python list: you can call `len()` on it, and you can takes slices from it.\n",
        "\n",
        "Each element in `dataset` is a `Data` object containing a graph that represents a protein. This is the same type of object that we used in the previous part to store the Cora citation network.\n",
        "\n",
        "Knowing this, answer the following:\n",
        "\n",
        "- How many proteins (graphs) are there in `dataset`?\n",
        "- Take any protein from `dataset`. How many nodes and edges does it contain? What is its label? How many features does each node have?"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZNPsnXXbbHHe",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4219f9c9-87ea-4d8c-a8a3-cc9460b85eb2"
      },
      "source": [
        "# Your answer here\n",
        "print(\"Number of proteins (graphs):\", len(dataset))\n",
        "print(\"Number of nodes:\", dataset[0].x.shape[0])\n",
        "print(\"Number of edges:\", dataset[0].edge_index.shape[1])\n",
        "print(\"Label:\", dataset[0].y.item())\n",
        "print(\"Number of features:\", dataset[0].x.shape[1])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Number of proteins (graphs): 1113\n",
            "Number of nodes: 42\n",
            "Number of edges: 162\n",
            "Label: 0\n",
            "Number of features: 4\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kHSklBZXpKpR"
      },
      "source": [
        "#### Question 12 (0.5 pt)\n",
        "\n",
        "To properly train and evaluate our model, we need training, validation, and test splits.\n",
        "\n",
        "For reproducibility purposes, we generate a random tensor of indices for you. Use it to extract the three splits from `dataset`.\n",
        "\n",
        "For training, take 80% of the indices (starting from the first element in `indices`), then the following 10% for validation, and the remaining 10% for testing. You can use the indices to index `dataset`.\n",
        "\n",
        "Call the resulting splits `train_dataset`, `valid_dataset`, and `test_dataset`."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ttY4d1GInn08"
      },
      "source": [
        "# Don't erase the following three lines\n",
        "import torch\n",
        "torch.random.manual_seed(0)\n",
        "indices = torch.randperm(len(dataset))\n",
        "\n",
        "# Your answer here\n",
        "first_split_index = int(round((len(dataset)*0.8)))\n",
        "second_split_index = int(round((len(dataset)*0.9)))\n",
        "\n",
        "train_dataset = dataset[indices[:first_split_index]]\n",
        "valid_dataset = dataset[indices[first_split_index:second_split_index]]\n",
        "test_dataset = dataset[indices[second_split_index:]]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rDJbB4CQqsfp"
      },
      "source": [
        "### Working with a batch of graphs\n",
        "\n",
        "When working with the Cora dataset, you used the information in `data.edge_index` to build the sparse normalized adjacency matrix $\\hat{A}$ that is required by the GCN. We could do something similar here: for each graph, we build $\\hat{A}$, and pass it to the GCN. However, if the number of graphs is big, this can really slow down training.\n",
        "\n",
        "To avoid this, we will resort to a very useful trick that also allows us to reuse the same GCN you implemented previously. The trick makes it possible to do a forward pass through the GCN for multiple, disconnected graphs at the same time (instead of only one), much like when you train with mini-batches for other kinds of data.\n",
        "\n",
        "Let's first revisit the propagation rule of the GCN, $Z = \\hat{A}XW$, with an illustration (we have omitted the cells of $X$ and $W$ for clarity):\n",
        "\n",
        "<img src=\"https://raw.githubusercontent.com/dfdazac/dlvu-a5/main/img/02-gcn-forward.png\">\n",
        "\n",
        "If we have multiple graphs, we can still use the same propagation rule, if we\n",
        "\n",
        "- Set $\\hat{A}$ to be a block diagonal matrix, where the blocks are the different adjacency matrices of the graphs\n",
        "- Concatenate the feature matrices along the first dimension\n",
        "\n",
        "This is illustrated in the following figure, for a batch of 3 graphs. Note that the elements outside of the blocks are zero.\n",
        "\n",
        "<img src=\"https://raw.githubusercontent.com/dfdazac/dlvu-a5/main/img/02-gcn-batch-forward.png\">\n",
        "\n",
        "The resulting adjacency matrix $\\hat{A}_B$ can also be built as a sparse matrix, and once we have it together with the concatenated matrix of features, the computation of the graph convolution is exactly the same as before. Note how this trick also allows us to process graphs with different sizes and structures.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0DLPJ62b2mQ6"
      },
      "source": [
        "#### Question 13 (0.5 pt)\n",
        "\n",
        "\n",
        "Just as the citation network, the graphs in each of the datasets you created in Question 12 also have an `edge_index` attribute, which can be used to compute the normalized adjacency matrix $\\hat{A}$, for each graph.\n",
        "\n",
        "Reusing your code for Questions 3 and 5, define a function `get_a_norm()` that takes as input an element of a dataset (e.g. `train_dataset[0]`), and returns a `scipy.sparse` matrix containing $\\hat{A}$.\n",
        "\n",
        "Note that an element of a dataset has properties like `num_edges`, `num_nodes`, etc. which you can use here."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4nvPX2GB8oXp",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7d33bf99-260a-4f72-b6b2-ad619146f7f2"
      },
      "source": [
        "import scipy\n",
        "import scipy.sparse as sp\n",
        "import numpy as np\n",
        "\n",
        "# Your answer here\n",
        "def get_a_norm(protein):\n",
        "  adj = sp.coo_matrix((\n",
        "      np.ones(protein.edge_index.shape[1]), \n",
        "      (protein.edge_index[0], protein.edge_index[1])), \n",
        "      shape=(protein.num_nodes, protein.num_nodes)\n",
        "    )\n",
        "  degree = sp.diags(adj.toarray().sum(axis=1))\n",
        "\n",
        "  # normalized adjacency matrix\n",
        "  adj_norm = degree.power(-1/2) @ adj @ degree.power(-1/2)\n",
        "  return adj_norm\n",
        "\n",
        "# Check if is indeed symetric:\n",
        "A = get_a_norm(train_dataset[0])\n",
        "\n",
        "def is_symmetric(adj_matrix):\n",
        "    # Check if the matrix is square (has the same number of rows and columns)\n",
        "    if adj_matrix.shape[0] != adj_matrix.shape[1]:\n",
        "        return False\n",
        "    # Check if the matrix is symmetric\n",
        "    return (adj_matrix - adj_matrix.transpose()).nnz == 0\n",
        "\n",
        "print(\"is_symmetric:\", is_symmetric(A))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "is_symmetric: True\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cBrmYBY3AfhW"
      },
      "source": [
        "#### Question 14 (1 pt)\n",
        "\n",
        "To prepare the batch of graphs, we need to collect multiple adjacency matrices, feature matrices, and labels.\n",
        "\n",
        "When using the trick described in the last figure, we see that we have to keep track of when a graph starts and when it ends, so that we can later differentiate the outputs due to $X^{(0)}$, $X^{(1)}$, etc. To achieve this, we will additionally collect a 1D array of batch indices, one for each $X^{(i)}$.\n",
        "\n",
        "The 1D array has as many elements as rows in $X^{(i)}$, and it is filled with the value $i$ (the position of $X^{(i)}$ in the batch):\n",
        "\n",
        "<img src=\"https://raw.githubusercontent.com/dfdazac/dlvu-a5/main/img/03-batch-indices.png\">\n",
        "\n",
        "We will later concatenate all the 1D arrays along the first dimension, just as we will do with all the $X^{(i)}$.\n",
        "\n",
        "Define a function `prepare_graphs_batch()` that takes as input a dataset (e.g. `train_dataset`), and does the following\n",
        "\n",
        "- Create four empty lists:\n",
        "  - `adj_matrices`\n",
        "  - `feature_matrices`\n",
        "  - `batch_indices`\n",
        "  - `labels`\n",
        "- Iterate over the input dataset, getting one graph at a time. At each step, use your function from Question 13 to append the adjacency matrix to `adj_matrices`, append the matrix of input features to `feature_matrices`, create the array of batch indices (as explained above) and append it to `batch_indices`, and append the label of the graph to `labels`. **Make sure to convert the label to float**.\n",
        "- Once the loop is over, use `scipy.sparse.block_diag()` to build the block diagonal matrix $\\hat{A}_B$. Convert it to the COO format, and then use your answer to Question 6 to turn it into a sparse PyTorch tensor.\n",
        "- Use `torch.cat()` to concatenate the tensors in `feature_matrices` along the first dimension. Do this also for `batch_indices` and `labels`.\n",
        "- Return the 4 tensors computed in the previous two items."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SsQ0-JjSqFgD"
      },
      "source": [
        "# Your answer here\n",
        "def prepare_graphs_batch(dataset):\n",
        "  adj_matrices = []\n",
        "  feature_matrices = []\n",
        "  batch_indices = []\n",
        "  labels = []\n",
        "\n",
        "  for i, protein in enumerate(dataset):\n",
        "    adj_matrices.append(get_a_norm(protein))\n",
        "    feature_matrices.append(protein.x)\n",
        "    batch_indices.append(torch.tensor(np.ones(protein.x.shape[0])*i))\n",
        "    labels.append(protein.y)\n",
        "\n",
        "  Ab = scipy.sparse.block_diag(adj_matrices)\n",
        "\n",
        "  _norm = torch.sparse_coo_tensor(indices=Ab.nonzero(), values=Ab.data, size=Ab.shape, dtype=torch.float)\n",
        "  _features = torch.cat(feature_matrices)\n",
        "  _batch_idx = torch.cat(batch_indices)\n",
        "  _labels = torch.cat(labels).float()\n",
        "\n",
        "  return _norm, _features, _batch_idx, _labels\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "i73P_EU0MSPX"
      },
      "source": [
        "Once your answer for the previous question is ready, you can run the next cell to prepare all the required information, for the train, validation, and test splits."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Iol5FxJGMmAU",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "86d8bb8f-82ea-4084-b085-000d6a5a38df"
      },
      "source": [
        "train_a_norm, train_features, train_batch_idx, train_labels = prepare_graphs_batch(train_dataset)\n",
        "valid_a_norm, valid_features, valid_batch_idx, valid_labels = prepare_graphs_batch(valid_dataset)\n",
        "test_a_norm, test_features, test_batch_idx, test_labels = prepare_graphs_batch(test_dataset)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "/usr/local/lib/python3.8/dist-packages/scipy/sparse/data.py:117: RuntimeWarning: divide by zero encountered in power\n",
            "  return self._with_data(data ** n)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "R6q-JU87NClh"
      },
      "source": [
        "### GCNs for graph classification\n",
        "\n",
        "We now have all the ingredients to pass a batch of graphs to a GCN. However, for each graph in the batch, the output $Z^{(i)}$ contains one row for each node in the graph. If the goal is to do classification at the graph level, we have to *pool* these vectors to then compute the required logits for classification.\n",
        "\n",
        "This operation is similar as how pooling works in a CNN. We could consider taking the mean of the vectors, the sum, or use max-pooling. The difference with respect to CNNs is that in our case, we have a batch of graphs, each potentially with a different number of nodes.\n",
        "\n",
        "To implement this specific pooling, we can use the scatter operation in the `torch_scatter` library, which comes when installing PyG. We will use it, together with the tensor of batch indices from the previous two questions, to pool the outputs of the GCN for each graph, into a single vector:\n",
        "\n",
        "<img src=\"https://raw.githubusercontent.com/dfdazac/dlvu-a5/main/img/04-scatter.png\">\n",
        "\n",
        "You can check more details in the [documentation](https://pytorch-scatter.readthedocs.io/en/latest/functions/scatter.html)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QY87DX1uRhnY"
      },
      "source": [
        "#### Question 15 (1.0 pt)\n",
        "\n",
        "Implement a `GraphClassifier` module using PyTorch.\n",
        "\n",
        "- The constructor should take as arguments the number of input features, the hidden dimension, and the number of classes.\n",
        "- The model should contain a instance of the `GCN` module (as you implemented it in Question 8). Use the same value for the hidden dimension and the number of output features (recall that your `GCN` module from Question 8 has two GCN layers).\n",
        "- The model should also contain a `torch.nn.Linear` layer, with the hidden dimension as the input features, and the number of classes as the output.\n",
        "- The forward method receives the concatenated matrix of features, the sparse block diagonal adjacency matrix, and the batch indices (the latter is used when calling `scatter`).\n",
        "- Use the following architecture in the forward pass:\n",
        "  - GCN $\\to$ ReLU $\\to$ scatter (max) $\\to$ Linear.\n",
        "\n",
        "The output of the forward should be a 1D tensor (you might need to call `squeeze` to get rid of extra dimensions) containing the logits for all graphs in the batch, for the binary classification task."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "750WraywwYDH"
      },
      "source": [
        "from torch_scatter import scatter\n",
        "# Your answer here\n",
        "class GraphClassifier(GCN):\n",
        "    def __init__(self, in_features, hidden_features, out_features):\n",
        "        super(GraphClassifier, self).__init__(in_features, hidden_features, out_features)\n",
        "        self.layer_gcn = GCNLayer(in_features, hidden_features)\n",
        "        self.layer_linear = torch.nn.Linear(hidden_features, out_features)\n",
        "        self.relu = torch.nn.ReLU()\n",
        "\n",
        "    def forward(self, x, adj, idx):\n",
        "        x = self.layer_gcn(x, adj)\n",
        "        x = self.relu(x)\n",
        "        x = scatter(x, idx)\n",
        "        x = self.layer_linear(x)\n",
        "        return x\n",
        "\n",
        "    @staticmethod\n",
        "    def fit(x, y, train_idx, adj_norm, n_hidden, epochs=100, batch_size=32, lr=0.001):\n",
        "        gcn = GCN(in_features=x.shape[1], hidden_features=n_hidden, out_features=len(y.unique()))\n",
        "\n",
        "        criterion = torch.nn.BCEWithLogitsLoss()\n",
        "        optimizer = torch.optim.Adam(gcn.parameters(), lr=lr)\n",
        "\n",
        "        for epoch in range(epochs+1):\n",
        "            # Forward pass\n",
        "            yhat = gcn(x, adj_norm)\n",
        "            _, predictions = torch.max(yhat, 1)\n",
        "            predictions = predictions[val_idx]\n",
        "            acc_val = (predictions == y[val_idx]).sum().item() / len(y[val_idx])\n",
        "            print(f\"Epoch: {epoch}\\nValidation accuracy: {acc_val}\")\n",
        "            \n",
        "            optimizer.zero_grad()\n",
        "            yhat = gcn(x, adj_norm)\n",
        "            torch_scatter.scatter(yhat,)\n",
        "            loss = criterion(yhat[train_idx], y[train_idx])\n",
        "            loss.backward()\n",
        "            optimizer.step()\n",
        "        \n",
        "        return gcn"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "h0QHnn6dV87J"
      },
      "source": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "C1PHy-_vTjgh"
      },
      "source": [
        "#### Question 16 (1.5 pt)\n",
        "\n",
        "Implement a training loop for the graph classifier. Use the data from Question 14 to train and evaluate the model.\n",
        "\n",
        "We encourage you to use a GPU in this section for faster training. Note that if you change the runtime at this point, you must re-execute several of the cells above, including the ones that install PyG.\n",
        "\n",
        "- Instantiate a classifier with 32 as the hidden dimension\n",
        "- Use Adam with a learning rate of 1e-3.\n",
        "- Use `torch.nn.BCEWithLogitsLoss` as the loss function.\n",
        "- Train for 5,000 epochs. Once training is done, plot the loss curve and the accuracy in the validation set. Then report the accuracy in the test set.\n",
        "\n",
        "**Note:** the logits from the output of the classifier come from a linear layer. To compute actual predictions for the calculation of the accuracy, pass the logits through `torch.sigmoid()`, and set the predicted values to 1 whenever they are greater than 0.5, and to 0 otherwise.\n",
        "\n",
        "You should get an accuracy equal to or higher than 70% in the validation and test sets. Can you beat the [state-of-the-art](https://paperswithcode.com/sota/graph-classification-on-proteins)? Feel free to modify your architecture and experiment with it.\n",
        "\n",
        "Discuss what you observe during training and your results."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9DbGAs8W2Xja",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 364
        },
        "outputId": "9f955650-7219-4277-96f2-a7a1beb20277"
      },
      "source": [
        "# If your runtime is GPU-enabled, use .to(device) to move the model\n",
        "# and all the relevant tensors to the GPU. You have to move tensors back to CPU\n",
        "# when computing metrics like accuracy, using .cpu().\n",
        "device = torch.device('cuda') if torch.cuda.is_available() else 'cpu'\n",
        "\n",
        "# Your answer here\n",
        "train_a_norm, train_features, train_batch_idx, train_labels = prepare_graphs_batch(train_dataset)\n",
        "valid_a_norm, valid_features, valid_batch_idx, valid_labels = prepare_graphs_batch(valid_dataset)\n",
        "test_a_norm, test_features, test_batch_idx, test_labels = prepare_graphs_batch(test_dataset)\n",
        "\n",
        "n_hidden = 32\n",
        "lr = 0.001\n",
        "\n",
        "model = GraphClassifier(in_features=train_features.shape[1], hidden_features=n_hidden, out_features=len(train_labels.unique()))\n",
        "\n",
        "criterion = torch.nn.BCEWithLogitsLoss()\n",
        "optimizer = torch.optim.Adam(gcn.parameters(), lr=lr)\n",
        "\n",
        "acc_val_list = []\n",
        "\n",
        "for epoch in range(5000):\n",
        "    # Forward pass\n",
        "    yhat = model(valid_features, valid_a_norm, valid_batch_idx)\n",
        "    _, predictions = torch.max(yhat, 1)\n",
        "    yhat[torch.sigmoid(yhat) > 0.5] = 1\n",
        "    yhat[torch.sigmoid(yhat) <= 0.5] = 0\n",
        "    acc_val = (predictions == valid_labels).sum().item() / len(valid_labels)\n",
        "    acc_val_list.append(acc_val)\n",
        "    print(f\"Epoch: {epoch}\\nValidation accuracy: {acc_val}\")\n",
        "    \n",
        "    optimizer.zero_grad()\n",
        "    yhat = gcn(train_features, train_a_norm)\n",
        "    loss = criterion(yhat, train_labels)\n",
        "    loss.backward()\n",
        "    optimizer.step()\n",
        "\n",
        "# Forward pass\n",
        "yhat = model.forward(test_features, test_a_norm, test_batch_idx)\n",
        "_, predictions = torch.max(yhat, 1)\n",
        "yhat[torch.sigmoid(yhat) > 0.5] = 1\n",
        "yhat[torch.sigmoid(yhat) <= 0.5] = 0\n",
        "acc_test = (predictions == test_labels).sum().item() / len(test_labels)\n",
        "print(f\"Epoch: {epoch}\\Test accuracy: {acc_test}\")\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "error",
          "ename": "RuntimeError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mRuntimeError\u001b[0m                              Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-222-708f298bfd3f>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     21\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mepoch\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m5000\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     22\u001b[0m     \u001b[0;31m# Forward pass\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 23\u001b[0;31m     \u001b[0myhat\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmodel\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mvalid_features\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvalid_a_norm\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvalid_batch_idx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     24\u001b[0m     \u001b[0m_\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpredictions\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtorch\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmax\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0myhat\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     25\u001b[0m     \u001b[0myhat\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mtorch\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msigmoid\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0myhat\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m>\u001b[0m \u001b[0;36m0.5\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/local/lib/python3.8/dist-packages/torch/nn/modules/module.py\u001b[0m in \u001b[0;36m_call_impl\u001b[0;34m(self, *input, **kwargs)\u001b[0m\n\u001b[1;32m   1188\u001b[0m         if not (self._backward_hooks or self._forward_hooks or self._forward_pre_hooks or _global_backward_hooks\n\u001b[1;32m   1189\u001b[0m                 or _global_forward_hooks or _global_forward_pre_hooks):\n\u001b[0;32m-> 1190\u001b[0;31m             \u001b[0;32mreturn\u001b[0m \u001b[0mforward_call\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0minput\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1191\u001b[0m         \u001b[0;31m# Do not call functions when jit is used\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1192\u001b[0m         \u001b[0mfull_backward_hooks\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mnon_full_backward_hooks\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-220-207b93de1a6a>\u001b[0m in \u001b[0;36mforward\u001b[0;34m(self, x, adj, idx)\u001b[0m\n\u001b[1;32m     11\u001b[0m         \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlayer_gcn\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0madj\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     12\u001b[0m         \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrelu\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 13\u001b[0;31m         \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mscatter\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0midx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     14\u001b[0m         \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlayer_linear\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     15\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/local/lib/python3.8/dist-packages/torch_scatter/scatter.py\u001b[0m in \u001b[0;36mscatter\u001b[0;34m(src, index, dim, out, dim_size, reduce)\u001b[0m\n\u001b[1;32m    150\u001b[0m     \"\"\"\n\u001b[1;32m    151\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mreduce\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m'sum'\u001b[0m \u001b[0;32mor\u001b[0m \u001b[0mreduce\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m'add'\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 152\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mscatter_sum\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msrc\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mindex\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdim\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mout\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdim_size\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    153\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mreduce\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m'mul'\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    154\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mscatter_mul\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msrc\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mindex\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdim\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mout\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdim_size\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/local/lib/python3.8/dist-packages/torch_scatter/scatter.py\u001b[0m in \u001b[0;36mscatter_sum\u001b[0;34m(src, index, dim, out, dim_size)\u001b[0m\n\u001b[1;32m      9\u001b[0m                 \u001b[0mout\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mOptional\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mtorch\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mTensor\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     10\u001b[0m                 dim_size: Optional[int] = None) -> torch.Tensor:\n\u001b[0;32m---> 11\u001b[0;31m     \u001b[0mindex\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mbroadcast\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mindex\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msrc\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdim\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     12\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mout\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     13\u001b[0m         \u001b[0msize\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlist\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msrc\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msize\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/local/lib/python3.8/dist-packages/torch_scatter/utils.py\u001b[0m in \u001b[0;36mbroadcast\u001b[0;34m(src, other, dim)\u001b[0m\n\u001b[1;32m     10\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0m_\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msrc\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdim\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mother\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdim\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m         \u001b[0msrc\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msrc\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0munsqueeze\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m     \u001b[0msrc\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msrc\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mexpand\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mother\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msize\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0msrc\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mRuntimeError\u001b[0m: The expanded size of the tensor (32) must match the existing size (4625) at non-singleton dimension 1.  Target sizes: [4625, 32].  Tensor sizes: [1, 4625]"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MvmAfDNMcnKD"
      },
      "source": [
        "## The end\n",
        "\n",
        "If you have made it all the way here successfully, congratulations! 🎉 \n",
        "\n",
        "You have implemented your own GCN and tested it on a node classification task, and a more challenging classification task over multiple graphs.\n",
        "\n",
        "We hope you can use this knowledge to apply GCNs not only to the tasks described here, but other applications where data can be modeled as a graph.\n",
        "\n",
        "If you are interested in applying graph neural networks to larger graphs, or try newer architectures, you can dive deeper into [PyTorch Geometric](https://pytorch-geometric.readthedocs.io/en/latest/), a library with fast implementations for a wide range of architectures. It also comes with custom code that takes care of aspects that you dealt with manually for this assignment, like a more efficient implementation of the adjacency matrix multiplication via message-passing methods, and Data Loaders that relieve you from having to build block diagonal sparse matrices.\n",
        "\n",
        "You can also check the [Deep Graph Library](https://docs.dgl.ai/) another powerful library for deep learning on graphs which also integrates with other backends like TensorFlow."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "l7QhyAMms8-L"
      },
      "source": [
        "# Grading (10pt)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "juIdxXhos-mV"
      },
      "source": [
        "- Question 1: 0.25pt \n",
        "- Question 2: 0.25pt \n",
        "- Question 3: 0.5pt \n",
        "- Question 4: 0.25pt \n",
        "- Question 5: 0.5pt \n",
        "- Question 6: 0.5pt \n",
        "- Question 7: 0.5pt \n",
        "- Question 8: 0.5pt \n",
        "- Question 9: 1.5pt \n",
        "- Question 10: 0.5pt \n",
        "- Question 11: 0.25pt \n",
        "- Question 12: 0.5pt \n",
        "- Question 13: 0.5pt \n",
        "- Question 14: 1pt\n",
        "- Question 15: 1pt\n",
        "- Question 16: 1.5pt"
      ]
    }
  ]
}