{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    },
    "gpuClass": "standard"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# Hypergraph Neural Networks\n",
        "\n",
        "This tutorial illustrates what is hypergraph and how to build a Hypergraph Neural Network using DGL's sparse matrix APIs.\n",
        "\n",
        "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/dmlc/dgl/blob/master/notebooks/sparse/hgnn.ipynb) [![GitHub](https://img.shields.io/badge/-View%20on%20GitHub-181717?logo=github&logoColor=ffffff)](https://github.com/dmlc/dgl/blob/master/notebooks/sparse/hgnn.ipynb)"
      ],
      "metadata": {
        "id": "eiDu3XgReCt4"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Install required packages.\n",
        "import os\n",
        "import torch\n",
        "os.environ['TORCH'] = torch.__version__\n",
        "os.environ['DGLBACKEND'] = \"pytorch\"\n",
        "\n",
        "# TODO(Steve): change to stable version.\n",
        "# Uncomment below to install required packages.\n",
        "#!pip install --pre dgl -f https://data.dgl.ai/wheels-test/repo.html > /dev/null\n",
        "#!pip install torchmetrics > /dev/null\n",
        "\n",
        "try:\n",
        "    import dgl\n",
        "    installed = True\n",
        "except ImportError:\n",
        "    installed = False\n",
        "print(\"DGL installed!\" if installed else \"Failed to install DGL!\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "__2tKqL0eaB0",
        "outputId": "bfd8f958-511b-47a5-b44f-8823421a62e4"
      },
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Collecting torchmetrics\n",
            "  Downloading torchmetrics-0.11.0-py3-none-any.whl (512 kB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m512.4/512.4 KB\u001b[0m \u001b[31m8.8 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hRequirement already satisfied: typing-extensions in /usr/local/lib/python3.8/dist-packages (from torchmetrics) (4.4.0)\n",
            "Requirement already satisfied: numpy>=1.17.2 in /usr/local/lib/python3.8/dist-packages (from torchmetrics) (1.21.6)\n",
            "Requirement already satisfied: torch>=1.8.1 in /usr/local/lib/python3.8/dist-packages (from torchmetrics) (1.13.0+cu116)\n",
            "Requirement already satisfied: packaging in /usr/local/lib/python3.8/dist-packages (from torchmetrics) (21.3)\n",
            "Requirement already satisfied: pyparsing!=3.0.5,>=2.0.2 in /usr/local/lib/python3.8/dist-packages (from packaging->torchmetrics) (3.0.9)\n",
            "Installing collected packages: torchmetrics\n",
            "Successfully installed torchmetrics-0.11.0\n",
            "DGL installed!\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Hypergraphs\n",
        "\n",
        "A [**hypergraph**](https://en.wikipedia.org/wiki/Hypergraph) consists of *nodes* and *hyperedges*.  Contrary to edges in graphs, a *hyperedge* can connect arbitrary number of nodes.  For instance, the following figure shows a hypergraph with 11 nodes and 5 hyperedges drawn in different colors.\n",
        "![](https://data.dgl.ai/tutorial/img/hgnn/hypergraph4.PNG)\n",
        "\n",
        "A hypergraph is usually characterized by its *incidence matrix* $H$, whose rows represent nodes and columns represent hyperedges.  An entry $H_{ij}$ is 1 if hyperedge $j$ includes node $i$, or 0 otherwise.  For example, the hypergraph in the figure above can be characterized by a $11 \\times 5$ matrix as follows:\n",
        "\n",
        "$$\n",
        "H = \\begin{bmatrix}\n",
        "1 & 0 & 0 & 0 & 0 \\\\\n",
        "1 & 0 & 0 & 0 & 0 \\\\\n",
        "1 & 1 & 0 & 1 & 1 \\\\\n",
        "0 & 0 & 1 & 0 & 0 \\\\\n",
        "0 & 1 & 0 & 0 & 0 \\\\\n",
        "1 & 0 & 1 & 1 & 1 \\\\\n",
        "0 & 0 & 1 & 0 & 0 \\\\\n",
        "0 & 1 & 0 & 1 & 0 \\\\\n",
        "0 & 1 & 0 & 1 & 0 \\\\\n",
        "0 & 0 & 1 & 0 & 1 \\\\\n",
        "0 & 0 & 0 & 0 & 1 \\\\\n",
        "\\end{bmatrix}\n",
        "$$\n",
        "\n",
        "One can construct the hypergraph incidence matrix by specifying two tensors `nodes` and `hyperedges`, where the node ID `nodes[i]` belongs to the hyperedge ID `hyperedges[i]` for all `i`.  In the case above, the incidence matrix can be constructed below.\n"
      ],
      "metadata": {
        "id": "unL_mAj-TqC6"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import dgl.sparse as dglsp\n",
        "import torch\n",
        "\n",
        "H = dglsp.from_coo(\n",
        "    torch.LongTensor([0, 1, 2, 2, 2, 2, 3, 4, 5, 5, 5, 5, 6, 7, 7, 8, 8, 9, 9, 10]),\n",
        "    torch.LongTensor([0, 0, 0, 1, 3, 4, 2, 1, 0, 2, 3, 4, 2, 1, 3, 1, 3, 2, 4, 4])\n",
        ")\n",
        "\n",
        "print(H.to_dense())"
      ],
      "metadata": {
        "id": "I_cExvtIJD1F",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4cc9fa37-7726-42e5-f01a-018c409044be"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "tensor([[1., 0., 0., 0., 0.],\n",
            "        [1., 0., 0., 0., 0.],\n",
            "        [1., 1., 0., 1., 1.],\n",
            "        [0., 0., 1., 0., 0.],\n",
            "        [0., 1., 0., 0., 0.],\n",
            "        [1., 0., 1., 1., 1.],\n",
            "        [0., 0., 1., 0., 0.],\n",
            "        [0., 1., 0., 1., 0.],\n",
            "        [0., 1., 0., 1., 0.],\n",
            "        [0., 0., 1., 0., 1.],\n",
            "        [0., 0., 0., 0., 1.]])\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "The degree of a node in a hypergraph is defined as the number of hyperedges including the node.  Similarly, the degree of a hyperedge in a hypergraph is defined as the number of nodes included by the hyperedge.  In the example above, the hyperedge degrees can be computed by the sum of row vectors (i.e. all 4), while the node degree can be computed by the sum of column vectors."
      ],
      "metadata": {
        "id": "p-shCPQPHvBB"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "node_degrees = H.sum(1)\n",
        "print(\"Node degrees\", node_degrees)\n",
        "\n",
        "hyperedge_degrees = H.sum(0)\n",
        "print(\"Hyperedge degrees\", hyperedge_degrees)"
      ],
      "metadata": {
        "id": "wjKm9gkTOnU9",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "bb6538aa-26f8-42ee-8d54-a2ea5a4fbd51"
      },
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Node degrees tensor([1., 1., 4., 1., 1., 4., 1., 2., 2., 2., 1.])\n",
            "Hyperedge degrees tensor([4., 4., 4., 4., 4.])\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "\n",
        "## Hypergraph Neural Network (HGNN) Layer\n",
        "\n",
        "The **[HGNN layer](https://arxiv.org/pdf/1809.09401.pdf)** is defined as:\n",
        "$$\n",
        "f(X^{(l)}, H; W^{(l)}) = \\sigma(L X^{(l)} W^{(l)}) \\\\\n",
        "L = D_v^{-1/2} H B D_e^{-1} H^\\top D_v^{-1/2}\n",
        "$$\n",
        "where\n",
        "* $H \\in \\mathbb{R}^{N \\times M}$ is the incidence matrix of hypergraph with $N$ nodes and $M$ hyperedges.\n",
        "* $D_v \\in \\mathbb{R}^{N \\times N}$ is a diagonal matrix representing node degrees, whose $i$-th diagonal element is $\\sum_{j=1}^M H_{ij}$.\n",
        "* $D_e \\in \\mathbb{R}^{M \\times M}$ is a diagonal matrix representing hyperedge degrees, whose $j$-th diagonal element is $\\sum_{i=1}^N H_{ij}$.\n",
        "* $B \\in \\mathbb{R}^{M \\times M}$ is a diagonal matrix representing the hyperedge weights, whose $j$-th diagonal element is the weight of $j$-th hyperedge.  In our example, $B$ is an identity matrix."
      ],
      "metadata": {
        "id": "7kxrINkVHrAi"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\"\"\"\n",
        "Hypergraph Neural Networks (https://arxiv.org/pdf/1809.09401.pdf)\n",
        "\"\"\"\n",
        "import dgl.sparse as dglsp\n",
        "import torch\n",
        "import torch.nn as nn\n",
        "import torch.nn.functional as F\n",
        "import tqdm\n",
        "from dgl.data import CoraGraphDataset\n",
        "from torchmetrics.functional import accuracy\n",
        "\n",
        "\n",
        "class HGNN(nn.Module):\n",
        "    def __init__(self, H, in_size, out_size, hidden_dims=16):\n",
        "        super().__init__()\n",
        "\n",
        "        self.Theta1 = nn.Linear(in_size, hidden_dims)\n",
        "        self.Theta2 = nn.Linear(hidden_dims, out_size)\n",
        "        self.dropout = nn.Dropout(0.5)\n",
        "\n",
        "        ###########################################################\n",
        "        # (HIGHLIGHT) Compute the Laplacian with Sparse Matrix API\n",
        "        ###########################################################\n",
        "        d_V = H.sum(1)  # node degree\n",
        "        d_E = H.sum(0)  # edge degree\n",
        "        n_edges = d_E.shape[0]\n",
        "        D_V_invsqrt = dglsp.diag(d_V**-0.5)  # D_V ** (-1/2)\n",
        "        D_E_inv = dglsp.diag(d_E**-1)  # D_E ** (-1)\n",
        "        W = dglsp.identity((n_edges, n_edges))\n",
        "        self.laplacian = D_V_invsqrt @ H @ W @ D_E_inv @ H.T @ D_V_invsqrt\n",
        "\n",
        "    def forward(self, X):\n",
        "        X = self.laplacian @ self.Theta1(self.dropout(X))\n",
        "        X = F.relu(X)\n",
        "        X = self.laplacian @ self.Theta2(self.dropout(X))\n",
        "        return X\n",
        "\n",
        "\n",
        "def train(model, optimizer, X, Y, train_mask):\n",
        "    model.train()\n",
        "    Y_hat = model(X)\n",
        "    loss = F.cross_entropy(Y_hat[train_mask], Y[train_mask])\n",
        "    optimizer.zero_grad()\n",
        "    loss.backward()\n",
        "    optimizer.step()\n",
        "\n",
        "\n",
        "def evaluate(model, X, Y, val_mask, test_mask, num_classes):\n",
        "    model.eval()\n",
        "    Y_hat = model(X)\n",
        "    val_acc = accuracy(\n",
        "        Y_hat[val_mask], Y[val_mask], task=\"multiclass\", num_classes=num_classes\n",
        "    )\n",
        "    test_acc = accuracy(\n",
        "        Y_hat[test_mask],\n",
        "        Y[test_mask],\n",
        "        task=\"multiclass\",\n",
        "        num_classes=num_classes,\n",
        "    )\n",
        "    return val_acc, test_acc\n",
        "\n",
        "\n",
        "def load_data():\n",
        "    dataset = CoraGraphDataset()\n",
        "\n",
        "    graph = dataset[0]\n",
        "    # The paper created a hypergraph from the original graph. For each node in\n",
        "    # the original graph, a hyperedge in the hypergraph is created to connect\n",
        "    # its neighbors and itself. In this case, the incidence matrix of the\n",
        "    # hypergraph is the same as the adjacency matrix of the original graph (with\n",
        "    # self-loops).\n",
        "    # We follow the paper and assume that the rows of the incidence matrix\n",
        "    # are for nodes and the columns are for edges.\n",
        "    src, dst = graph.edges()\n",
        "    H = dglsp.from_coo(dst, src)\n",
        "    H = H + dglsp.identity(H.shape)\n",
        "\n",
        "    X = graph.ndata[\"feat\"]\n",
        "    Y = graph.ndata[\"label\"]\n",
        "    train_mask = graph.ndata[\"train_mask\"]\n",
        "    val_mask = graph.ndata[\"val_mask\"]\n",
        "    test_mask = graph.ndata[\"test_mask\"]\n",
        "    return H, X, Y, dataset.num_classes, train_mask, val_mask, test_mask\n",
        "\n",
        "\n",
        "def main():\n",
        "    H, X, Y, num_classes, train_mask, val_mask, test_mask = load_data()\n",
        "    model = HGNN(H, X.shape[1], num_classes)\n",
        "    optimizer = torch.optim.Adam(model.parameters(), lr=0.001)\n",
        "\n",
        "    with tqdm.trange(500) as tq:\n",
        "        for epoch in tq:\n",
        "            train(model, optimizer, X, Y, train_mask)\n",
        "            val_acc, test_acc = evaluate(\n",
        "                model, X, Y, val_mask, test_mask, num_classes\n",
        "            )\n",
        "            tq.set_postfix(\n",
        "                {\n",
        "                    \"Val acc\": f\"{val_acc:.5f}\",\n",
        "                    \"Test acc\": f\"{test_acc:.5f}\",\n",
        "                },\n",
        "                refresh=False,\n",
        "            )\n",
        "\n",
        "    print(f\"Test acc: {test_acc:.3f}\")\n",
        "\n",
        "\n",
        "if __name__ == \"__main__\":\n",
        "    main()"
      ],
      "metadata": {
        "id": "58WnPtPvT2mx",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "e27529b5-a097-4fe2-e1d6-7ae89484dd23"
      },
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "  NumNodes: 2708\n",
            "  NumEdges: 10556\n",
            "  NumFeats: 1433\n",
            "  NumClasses: 7\n",
            "  NumTrainingSamples: 140\n",
            "  NumValidationSamples: 500\n",
            "  NumTestSamples: 1000\n",
            "Done loading data from cached files.\n"
          ]
        },
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "100%|██████████| 500/500 [00:48<00:00, 10.24it/s, Val acc=0.76600, Test acc=0.76000]"
          ]
        },
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Test acc: 0.760\n"
          ]
        },
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "For the complete example of HGNN, please refer to https://github.com/dmlc/dgl/blob/master/examples/sparse/hgnn.py."
      ],
      "metadata": {
        "id": "59pCzjpBOyEW"
      }
    }
  ]
}