04_DGL_02_实现PageRank.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c8dd3704",
   "metadata": {},
   "source": [
    "这一节我们利用DGL来实现一下PageRank算法，关于PageRank的原理，大家可以参考我在ML_Notes中的这个[>>note](https://nbviewer.jupyter.org/github/zhulei227/ML_Notes/blob/master/notebooks/12_07_PGM_%E9%A9%AC%E5%B0%94%E7%A7%91%E5%A4%AB%E9%93%BE_PageRank%E7%AE%97%E6%B3%95.ipynb)  \n",
    "![avatar](./pic/pagerank_demo1.png) "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26d2db1b",
   "metadata": {},
   "source": [
    "如图，以节点A举例，他的PR更新公示可以表示为：   \n",
    "\n",
    "$$\n",
    "PR_A^{(t+1)}=w_{BA}PR_B^{(t)}+w_{CA}PR_C^{(t)}\n",
    "$$  \n",
    "\n",
    "这里，$w_{BA}$表示边$(B,A)$上的权重，在默认情况下，我们可以设置为节点$B$的出度的倒数，而$PR_{*}$则表示某节点的PR值，下面利用DGL来计算PR，节点编号0 ~ 3分别对应上面的节点A ~ D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ffe82394",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Using backend: pytorch\n"
     ]
    }
   ],
   "source": [
    "import dgl\n",
    "import torch"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38741354",
   "metadata": {},
   "source": [
    "**构建图**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "562cef42",
   "metadata": {},
   "outputs": [],
   "source": [
    "u=torch.tensor([0,0,0,1,1,2,3,3])\n",
    "v=torch.tensor([1,2,3,0,3,0,1,2])\n",
    "g=dgl.graph((u,v))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d35fca8",
   "metadata": {},
   "source": [
    "**计算边权重**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "f7251ed2",
   "metadata": {},
   "outputs": [],
   "source": [
    "g.ndata[\"out_degrees\"]=g.out_degrees()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "c97b7ff1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([0.3333, 0.3333, 0.3333, 0.5000, 0.5000, 1.0000, 0.5000, 0.5000])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def message_func(edges):\n",
    "    return {\"weight\":1.0/edges.src[\"out_degrees\"]}\n",
    "g.apply_edges(message_func)\n",
    "g.edata[\"weight\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d5e99fb",
   "metadata": {},
   "source": [
    "**计算PR**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b62bd770",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([0.1702, 0.3912, 0.1391, 0.2994])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#随机初始化一组PR\n",
    "prs=torch.exp(torch.randn(4))\n",
    "prs=prs/torch.sum(prs)\n",
    "prs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "13255fdf",
   "metadata": {},
   "outputs": [],
   "source": [
    "g.ndata[\"pr\"]=prs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ca8b1a93",
   "metadata": {},
   "outputs": [],
   "source": [
    "for _ in range(100):\n",
    "    g.update_all(dgl.function.u_dot_e(\"pr\",\"weight\",\"weighted_pr\"),#将源节点上的pr与边上的weight相乘后放到边上的weighted_pr变量中\n",
    "                 dgl.function.sum(\"weighted_pr\",\"pr\"))#将所有入边上的weighted_pr求和后赋值到目标节点的pr变量中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a6db98d7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([0.3333, 0.2222, 0.2222, 0.2222])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.ndata[\"pr\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93625051",
   "metadata": {},
   "source": [
    "上面的实现不够严谨，为了防止没有出度或者没有入度的节点，其实需要在聚合的时候再添加一个平滑项（见上面链接中的note），接下来继续正题，看看GNN如何用DGL来实现~"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "47ffcb26",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}