In graph neural network , The transmission of information and the transformation of characteristics , Users can customize . Of course. DGL in , There are also advanced API For calling .
Now let's look at a simple model of web page ranking . Every node has the same PV value ,PV=0.01, Each node will first distribute its own PV Value to surrounding nodes . New at each node PV The value is equal to the aggregation of surrounding nodes , At the same time, it is adjusted by the damping factor . therefore , Every iteration , node PV The value changes as follows ：

among ,d Is the damping factor ,N For the node number .N Is the adjacent node of the node ,D Is the output degree of the node （deg）

Purpose ： see 10 After iterations , Of each node PV value

First , Import the required modules

import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
import dgl
import torch
import dgl.function as fn

One 、 Build a diagram

N = 100 # Number of nodes 
DAMP=0.85 # Formula d
K = 10 # The number of iterations 
g = nx.nx.erdos_renyi_graph(N, 0.1) # Random erdos_renyi chart 
g = dgl.DGLGraph(g)
# visualization 
nx.draw(g.to_networkx(), with_labels=True, nodes_size=50)
plt.show()

Initialize node PV Value and output degree :

g.ndata['PV'] = torch.ones(N)/N # The initial data of each node is 0.01
g.ndata['deg'] = g.out_degrees(g.nodes()).float() # Output degree of each node 
print(g.ndata)

Two 、 Information transmission 、 Four methods of aggregation

（1） Fully user-defined mode

There are four steps ：

1. The output of the node PV Value function

def pagerank_message_func(edges):
    '''  Information output function  :param edges:  chart g Edge object of , Multiple edges （ Edge objects have src, dst, data Three attributes ,  Each represents the starting node of the edge , Termination node , Edge feature ）  Here, only the output nodes are iterated PV value  :return: '''
    return {
    'PV': edges.src['PV'] / edges.src['deg']}

2. node PV Information aggregation function

def pagerank_reduce_func(nodes):
    '''  Aggregation of information （ attenuation ） function  :param nodes:  Input node object  :return: '''
    megs = torch.sum(nodes.mailbox['PV'], dim=1)
    pv = (1-DAMP)/N + DAMP*megs
    return {
    'PV': pv}

3. Node output function 、 Information aggregation function import graph

# For information transfer function and information aggregation （ attenuation ） Function is registered in g In the network .
g.register_message_func(pagerank_message_func)
g.register_reduce_func(pagerank_reduce_func)

4. Spread forward

# Information is spreading forward 
def pagerank_naive(g):
    # Stage 1 ： Messages send all messages along the node 
    for u, v in zip(*g.edges()):
        g.send((u,v)) # The input is edge 
    # Stage two ： Receiving information , Calculate the new PV value 
    for v in g.nodes():
        g.recv(v) # The input is the termination node 

（2) Batch processing method suitable for large drawings

And （1) The method in is similar to , You also need to define the information propagation function first 、 Information aggregation function , And pass these two functions into the graph g in . The difference is the fourth step . Replace step 4 with the following ：

ef pagerank_batch(g):
    g.send(g.edges())
    g.recv(g.nodes())

The principle of batch production ：
“ You may want to know whether it is possible to execute in parallel on all nodes reduce, Because each node may have a different number of incoming messages ,
And you can't really put tensors of different lengths “ The stack ” together . Usually ,DGL By grouping nodes according to the number of incoming messages and calling reduce Function to solve the problem .”

（3） Use dgl in level 2 Of API

And （1) similar , The first three steps , All the same , Just modify the fourth step , as follows ：

#DGL You can use more advanced API Update diagram  (level-2 APIs)
def pagerank_level2(g):
    g.update_all()

（4) Use more efficient built-in functions directly from beginning to end

# There is a more effective way , Use dgl Built in functions for . This method performs faster .
def pagerank_builtin(g):
    ''' 1. fn.copy_src：  Build information output function , Spread the information of the starting node  2. fn.sum： Information aggregation  :param g:  Picture object  :return: '''
    g.ndata['PV'] = g.ndata['PV']/g.ndata['deg']
    g.update_all(message_func=fn.copy_src(src='PV', out='m'),
                 reduce_func=fn.sum(msg='m', out='m_sum'))
    g.ndata['PV'] = (1-DAMP)/N + DAMP * g.ndata['m_sum']

3、 ... and 、 Conduct N Sub iteration

# Conduct K Sub iteration 
for k in range(K):
    pagerank_builtin(g)
print(g.ndata['PV'])