{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%matplotlib inline"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n.. currentmodule:: dgl\n\nPageRank with DGL Message Passing\n=================================\n\n**Author**: `Minjie Wang `_, Quan Gan, Yu Gai,\nZheng Zhang\n\nIn this section we illustrate the usage of different levels of message\npassing API with PageRank on a small graph. In DGL, the message passing and\nfeature transformations are all **User-Defined Functions** (UDFs).\n\nThe goal of this tutorial: to implement PageRank using DGL message passing\ninterface.\n\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The PageRank Algorithm\n----------------------\nIn each iteration of PageRank, every node (web page) first scatters its\nPageRank value uniformly to its downstream nodes. The new PageRank value of\neach node is computed by aggregating the received PageRank values from its\nneighbors, which is then adjusted by the damping factor:\n\n\\begin{align}PV(u) = \\frac{1-d}{N} + d \\times \\sum_{v \\in \\mathcal{N}(u)}\n \\frac{PV(v)}{D(v)}\\end{align}\n\nwhere $N$ is the number of nodes in the graph; $D(v)$ is the\nout-degree of a node $v$; and $\\mathcal{N}(u)$ is the neighbor\nnodes.\n\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A naive implementation\n----------------------\nLet us first create a graph with 100 nodes with NetworkX and convert it to a\n:class:`DGLGraph`:\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import networkx as nx\nimport matplotlib.pyplot as plt\nimport torch\nimport dgl\n\nN = 100 # number of nodes\nDAMP = 0.85 # damping factor\nK = 10 # number of iterations\ng = nx.nx.erdos_renyi_graph(N, 0.1)\ng = dgl.DGLGraph(g)\nnx.draw(g.to_networkx(), node_size=50, node_color=[[.5, .5, .5,]])\nplt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"According to the algorithm, PageRank consists of two phases in a typical\nscatter-gather pattern. We first initialize the PageRank value of each node\nto $\\frac{1}{N}$ and store each node's out-degree as a node feature:\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"g.ndata['pv'] = torch.ones(N) / N\ng.ndata['deg'] = g.out_degrees(g.nodes()).float()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We then define the message function, which divides every node's PageRank\nvalue by its out-degree and passes the result as message to its neighbors:\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def pagerank_message_func(edges):\n return {'pv' : edges.src['pv'] / edges.src['deg']}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In DGL, the message functions are expressed as **Edge UDFs**. Edge UDFs\ntake in a single argument ``edges``. It has three members ``src``, ``dst``,\nand ``data`` for accessing source node features, destination node features,\nand edge features respectively. Here, the function computes messages only\nfrom source node features.\n\nNext, we define the reduce function, which removes and aggregates the\nmessages from its ``mailbox``, and computes its new PageRank value:\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def pagerank_reduce_func(nodes):\n msgs = torch.sum(nodes.mailbox['pv'], dim=1)\n pv = (1 - DAMP) / N + DAMP * msgs\n return {'pv' : pv}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The reduce functions are **Node UDFs**. Node UDFs have a single argument\n``nodes``, which has two members ``data`` and ``mailbox``. ``data``\ncontains the node features while ``mailbox`` contains all incoming message\nfeatures, stacked along the second dimension (hence the ``dim=1`` argument).\n\nThe message UDF works on a batch of edges, whereas the reduce UDF works on\na batch of edges but outputs a batch of nodes. Their relationships are as\nfollows:\n\n![](https://i.imgur.com/kIMiuFb.png)\n\n\nWe register the message function and reduce function, which will be called\nlater by DGL.\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"g.register_message_func(pagerank_message_func)\ng.register_reduce_func(pagerank_reduce_func)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The algorithm is then very straight-forward. Here is the code for one\nPageRank iteration:\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def pagerank_naive(g):\n # Phase #1: send out messages along all edges.\n for u, v in zip(*g.edges()):\n g.send((u, v))\n # Phase #2: receive messages to compute new PageRank values.\n for v in g.nodes():\n g.recv(v)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Improvement with batching semantics\n-----------------------------------\nThe above code does not scale to large graph because it iterates over all\nthe nodes. DGL solves this by letting user compute on a *batch* of nodes or\nedges. For example, the following codes trigger message and reduce functions\non multiple nodes and edges at once.\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def pagerank_batch(g):\n g.send(g.edges())\n g.recv(g.nodes())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that we are still using the same reduce function ``pagerank_reduce_func``,\nwhere ``nodes.mailbox['pv']`` is a *single* tensor, stacking the incoming\nmessages along the second dimension.\n\nNaturally, one will wonder if this is even possible to perform reduce on all\nnodes in parallel, since each node may have different number of incoming\nmessages and one cannot really \"stack\" tensors of different lengths together.\nIn general, DGL solves the problem by grouping the nodes by the number of\nincoming messages, and calling the reduce function for each group.\n\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"More improvement with higher level APIs\n---------------------------------------\nDGL provides many routines that combines basic ``send`` and ``recv`` in\nvarious ways. They are called **level-2 APIs**. For example, the PageRank\nexample can be further simplified as follows:\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def pagerank_level2(g):\n g.update_all()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Besides ``update_all``, we also have ``pull``, ``push``, and ``send_and_recv``\nin this level-2 category. Please refer to the :doc:`API reference <../../api/python/graph>`\nfor more details.\n\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Even more improvement with DGL builtin functions\n------------------------------------------------\nAs some of the message and reduce functions are very commonly used, DGL also\nprovides **builtin functions**. For example, two builtin functions can be\nused in the PageRank example.\n\n* :func:`dgl.function.copy_src(src, out) `\n is an edge UDF that computes the\n output using the source node feature data. User needs to specify the name of\n the source feature data (``src``) and the output name (``out``).\n\n* :func:`dgl.function.sum(msg, out) ` is a node UDF\n that sums the messages in\n the node's mailbox. User needs to specify the message name (``msg``) and the\n output name (``out``).\n\nFor example, the PageRank example can be rewritten as following:\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import dgl.function as fn\n\ndef pagerank_builtin(g):\n g.ndata['pv'] = g.ndata['pv'] / g.ndata['deg']\n g.update_all(message_func=fn.copy_src(src='pv', out='m'),\n reduce_func=fn.sum(msg='m',out='m_sum'))\n g.ndata['pv'] = (1 - DAMP) / N + DAMP * g.ndata['m_sum']"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here, we directly provide the UDFs to the :func:`update_all `\nas its arguments.\nThis will override the previously registered UDFs.\n\nIn addition to cleaner code, using builtin functions also gives DGL the\nopportunity to fuse operations together, resulting in faster execution. For\nexample, DGL will fuse the ``copy_src`` message function and ``sum`` reduce\nfunction into one sparse matrix-vector (spMV) multiplication.\n\n`This section `_ describes why spMV can speed up the scatter-gather\nphase in PageRank. For more details about the builtin functions in DGL,\nplease read the :doc:`API reference <../../api/python/function>`.\n\nYou can also download and run the codes to feel the difference.\n\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"for k in range(K):\n # Uncomment the corresponding line to select different version.\n # pagerank_naive(g)\n # pagerank_batch(g)\n # pagerank_level2(g)\n pagerank_builtin(g)\nprint(g.ndata['pv'])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\nUsing spMV for PageRank\n-----------------------\nUsing builtin functions allows DGL to understand the semantics of UDFs and\nthus allows more efficient implementation for you. For example, in the case\nof PageRank, one common trick to accelerate it is using its linear algebra\nform.\n\n\\begin{align}\\mathbf{R}^{k} = \\frac{1-d}{N} \\mathbf{1} + d \\mathbf{A}*\\mathbf{R}^{k-1}\\end{align}\n\nHere, $\\mathbf{R}^k$ is the vector of the PageRank values of all nodes\nat iteration $k$; $\\mathbf{A}$ is the sparse adjacency matrix\nof the graph.\nComputing this equation is quite efficient because there exists efficient\nGPU kernel for the *sparse-matrix-vector-multiplication* (spMV). DGL\ndetects whether such optimization is available through the builtin\nfunctions. If the certain combination of builtins can be mapped to a spMV\nkernel (e.g. the pagerank example), DGL will use it automatically. As a\nresult, *we recommend using builtin functions whenever it is possible*.\n\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Next steps\n----------\n\nIt is time to move on to some real models in DGL.\n\n* Check out the :doc:`overview page<../models/index>`\n of all the model tutorials.\n* Would like to know more about Graph Neural Networks? Start with the\n :doc:`GCN tutorial<../models/1_gnn/1_gcn>`.\n* Would like to know how DGL batches multiple graphs? Start with the\n :doc:`TreeLSTM tutorial<../models/2_small_graph/3_tree-lstm>`.\n* Would like to play with some graph generative models? Start with our tutorial\n on the :doc:`Deep Generative Model of Graphs<../models/3_generative_model/5_dgmg>`.\n* Would like to see how traditional models are interpreted in a view of graph?\n Check out our tutorials on :doc:`CapsuleNet<../models/4_old_wines/2_capsule>` and\n :doc:`Transformer<../models/4_old_wines/7_transformer>`.\n\n"
]
}
],
"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.6.6"
}
},
"nbformat": 4,
"nbformat_minor": 0
}