图神经网络-图游走算法核心代码SkipGram、Node2Vec实现

图神经网络-图游走算法核心代码SkipGram、Node2Vec实现

1. DeepWalk采样算法

对于给定的节点，DeepWalk会等概率的选取下一个相邻节点加入路径，直至达到最大路径长度，或者没有下一个节点可选。

2. SkipGram模型训练

在得到节点路径后，node2vec会使用SkipGram模型学习节点表示，给定中心节点，预测局部路径中还有哪些节点。模型中用了negative sampling来降低计算量。

loss的计算过程可参考 PGL/examples/node2vec/node2vec.py中的 node2vec_model 函数。

%%writefile userdef_model.py
import paddle.fluid.layers as l


def userdef_loss(embed_src, weight_pos, weight_negs):
    """
    输入：embed_src   - 中心节点向量 list (batch_size, 1, embed_size)
         weight_pos  - 标签节点向量 list (batch_size, 1, embed_size)
         weight_negs - 负样本节点向量 list (batch_size, neg_num, embed_size)
    输出：loss - 正负样本的交叉熵 float
    """
    
    ##################################
    # 请在这里实现SkipGram的loss计算过程 
    ### 负采样计算部分——Multi Sigmoids
    # 分别计算正样本和负样本的 logits（概率）
    pos_logits = l.matmul(
        embed_src, weight_pos, transpose_y=True)  # [batch_size, 1, 1] -- matmul:矩阵相乘
    neg_logits = l.matmul(
        embed_src, weight_negs, transpose_y=True)  # [batch_size, 1, neg_num]


    # 设置正样本标签，并计算正样本loss
    ones_label = pos_logits * 0. + 1.
    ones_label.stop_gradient = True   # 关闭梯度记录
    pos_loss = l.sigmoid_cross_entropy_with_logits(pos_logits, ones_label)  # 交叉熵计算==对应公式2


    # 设置负样本标签，并计算负样本loss
    zeros_label = neg_logits * 0.
    zeros_label.stop_gradient = True
    neg_loss = l.sigmoid_cross_entropy_with_logits(neg_logits, zeros_label)  # 交叉熵计算==对应公式3


    # 总的Loss计算为正样本与负样本loss之和
    loss = (l.reduce_mean(pos_loss) + l.reduce_mean(neg_loss)) / 2   # 得到总的loss
    ##################################
    return loss

运行脚本，可以查看在ArXiv数据集上的效果：

!python my_node2vec.py  --use_my_model --epoch 5 # 使用自己定义的loss函数
!python link_predict.py --ckpt_path ./tmp/node2vec/paddle_model --epoch 100

pgl的官网node2vec_model源代码：

def node2vec_model(graph, hidden_size=16, neg_num=5):


    pyreader = l.py_reader(
        capacity=70,
        shapes=[[-1, 1, 1], [-1, 1, 1], [-1, neg_num, 1]],
        dtypes=['int64', 'int64', 'int64'],
        lod_levels=[0, 0, 0],
        name='train',
        use_double_buffer=True)


    embed_init = fluid.initializer.UniformInitializer(low=-1.0, high=1.0)
    weight_init = fluid.initializer.TruncatedNormal(scale=1.0 /
                                                    math.sqrt(hidden_size))


    src, pos, negs = l.read_file(pyreader)


    embed_src = l.embedding(
        input=src,
        size=[graph.num_nodes, hidden_size],
        param_attr=fluid.ParamAttr(
            name='content', initializer=embed_init))


    weight_pos = l.embedding(
        input=pos,
        size=[graph.num_nodes, hidden_size],
        param_attr=fluid.ParamAttr(
            name='weight', initializer=weight_init))
    weight_negs = l.embedding(
        input=negs,
        size=[graph.num_nodes, hidden_size],
        param_attr=fluid.ParamAttr(
            name='weight', initializer=weight_init))


    pos_logits = l.matmul(
        embed_src, weight_pos, transpose_y=True)  # [batch_size, 1, 1]
    neg_logits = l.matmul(
        embed_src, weight_negs, transpose_y=True)  # [batch_size, 1, neg_num]


    ones_label = pos_logits * 0. + 1.
    ones_label.stop_gradient = True
    pos_loss = l.sigmoid_cross_entropy_with_logits(pos_logits, ones_label)


    zeros_label = neg_logits * 0.
    zeros_label.stop_gradient = True
    neg_loss = l.sigmoid_cross_entropy_with_logits(neg_logits, zeros_label)
    loss = (l.reduce_mean(pos_loss) + l.reduce_mean(neg_loss)) / 2


    return pyreader, loss

3. Node2Vec采样算法

Node2Vec会根据与上个节点的距离按不同概率采样得到当前节点的下一个节点。

PGL/pgl/graph_kernel.pyx 中用Cython语言实现了节点采样函数node2vec_sample，以下使用numpy实现自己的node2vec_sample函数 ，用于随机游走后得到的路径，然后对这些路径进行吸收学习，训练图结构

%%writefile userdef_sample.py
def node2vec_sample(succ, prev_succ, prev_node, p, q):
    """
    输入：succ - 当前节点的下一个相邻节点id列表 list (num_neighbors,)
         prev_succ - 前一个节点的下一个相邻节点id列表 list (num_neighbors,)
         prev_node - 前一个节点id int
         p - 控制回到上一节点的概率 float
         q - 控制偏向DFS还是BFS float
    输出：下一个节点id int
    """
    ##################################
    # 请在此实现node2vec的节点采样函数
    #sampled_succ = 
    ################################## 
    succ_len = len(succ)                # 获取相邻节点id列表节点长度（相对当前）
    prev_succ_len = len(prev_succ)      # 获取相邻节点id列表节点长度（相对前一个节点）
    prev_succ_set = np.asarray([])   # 前一节点的相邻节点id列表


    for i in range(prev_succ_len):     # 遍历得到前一节点的相邻节点id列表的新list——prev_succ_set 
        # 将前一节点list，依次入新的list中
        prev_succ_set = np.append(prev_succ_set,prev_succ[i])   
    
    # 概率参数信息
    probs = []     # 保存每一个待前往的概率
    prob = 0   # 记录当前讨论的节点概率
    prob_sum = 0.  # 所有待前往的节点的概率之和


    # 遍历当前节点的相邻节点
    for i in range(succ_len):    # 遍历每一个当前节点前往的概率
        if succ[i] == prev_node:  # case 1 ：采样节点与前一节点一致，那么概率为--1/q（原地）
            prob = 1. / p
        elif np.where(prev_succ_set==succ[i]):   # case 2  ：采样节点在前一节点list内，那么概率为--1  
            prob = 1.
        elif np.where(prev_succ_set!=succ[i]):   # case 3  ：采样节点不在前一节点list内，那么概率为--1/q
            prob = 1. / q
        else:
            prob = 0.       # case 4 ：other


        probs.append(prob)  # 将待前往的每一个节点的概率押入保存
        prob_sum += prob    # 计算所有节点的概率之和
    
    RAND_MAX = 65535   # 这是一个随机数的最值 
    rand_num = float(np.random.randint(0, RAND_MAX+1)) / RAND_MAX * prob_sum  # 计算一个随机概率 


    sampled_succ = 0.   # 当前节点的相邻节点中确定的采样点


 
    for i in range(succ_len):   # 遍历当前节点的所有相邻节点
        rand_num -= probs[i]    # 利用rand_num这个随机获得的概率值 ，进行一个循环概率检验
        if rand_num <= 0:   # 停止检验条件 
            sampled_succ = succ[i]   # 并把当前节点作为确定的节点
    return sampled_succ

运行脚本

!python my_node2vec.py  --use_my_sample --epoch 5 # 用自己实现的采样函数训练模型
!python link_predict.py --ckpt_path ./tmp/node2vec/paddle_model --epoch 100 # 测试

pgl官网node2vec_sample源代码

@cython.boundscheck(False)
@cython.wraparound(False)
def node2vec_sample(np.ndarray[np.int64_t, ndim=1] succ,
        np.ndarray[np.int64_t, ndim=1] prev_succ, long long prev_node,
        float p, float q):
    """Fast implement of node2vec sampling
    """
    cdef long long i
    cdef succ_len = len(succ)
    cdef prev_succ_len = len(prev_succ)


    cdef vector[float] probs
    cdef float prob_sum = 0


    cdef unordered_set[long long] prev_succ_set
    for i in xrange(prev_succ_len):
        prev_succ_set.insert(prev_succ[i])


    cdef float prob
    for i in xrange(succ_len):
        if succ[i] == prev_node:
            prob = 1. / p
        elif prev_succ_set.find(succ[i]) != prev_succ_set.end():
            prob = 1.
        else:
            prob = 1. / q
        probs.push_back(prob)
        prob_sum += prob


    cdef float rand_num = float(rand())/RAND_MAX * prob_sum


    cdef long long sample_succ = 0
    for i in xrange(succ_len):
        rand_num -= probs[i]
        if rand_num <= 0:
            sample_succ = succ[i]
            return sample_succ