Paddle Graph Learning (PGL)图学习之图游走类模型[系列四]

更多详情参考：Paddle Graph Learning 图学习之图游走类模型[系列四]
https://aistudio.baidu.com/aistudio/projectdetail/5002782?contributionType=1

相关项目参考：

关于图计算&图学习的基础知识概览：前置知识点学习（PGL）[系列一] https://aistudio.baidu.com/aistudio/projectdetail/4982973?contributionType=1

图机器学习(GML)&图神经网络(GNN)原理和代码实现(前置学习系列二）：https://aistudio.baidu.com/aistudio/projectdetail/4990947?contributionType=1

图学习【参考资料1】词向量word2vec https://aistudio.baidu.com/aistudio/projectdetail/5009409?contributionType=1

图学习【参考资料2】-知识补充与node2vec代码注解 https://aistudio.baidu.com/aistudio/projectdetail/5012408?contributionType=1

1.图游走类算法原理前言

1.1 Graph Embedding

在开始介绍图游走算法之前，先来学习一下什么是Graph Embedding。

图嵌入是一种将图数据（通常为高维稠密的矩阵）映射为低微稠密向量的过程，如下图所示。图嵌入需要捕捉到图的拓扑结构，顶点与顶点的关系，以及其他的信息 （如子图，连边等）。如果有更多的信息被表示出来，那么下游的任务将会获得更好的表现。在嵌入的过程中存在着一种共识：向量空间中保持连接的节点彼此靠近。

总的来说图嵌入技术大致可以分为两种：节点嵌入和图嵌入。

• 当需要对节点进行分类，节点相似度预测，节点分布可视化时一般采用节点的嵌入；
• 当需要在图级别（graph-level）上进行预测或者整个图结构决策，需要将整个图表示为一个向量进行嵌入表示。

图学习的方法，大部分都可以应用到图嵌入问题中，所以图嵌入问题属于图学习中的一个非常重要的应用领域，不同的方法涉及了多方面知识。

我们可以将图嵌入的这些方法简要分为以下这些类别：

基于矩阵分解传统方法	基于游走策略	基于游走策略和其他信息	基于深度学习	基于GAN
Laplacian Eigenmaps	deepwalk	CENE	GCN	GraphGAN
Locally Linear Embedding	node2vec	CANE	SDNE	ANE
Graph Factorization	struc2vec	Trans-Net
	LINE
	GraRep
	GraphSAGE

1.1.1 为什么要使用图嵌入（graph embedding）

图是一种简单、易于理解的表示形式，但是由于下面的原因，我们需要对图进行嵌入表示：

• 在graph上直接进行机器学习具有一定的局限性，我们都知道图是由节点和边构成，这些向量关系一般只能使用数学，统计或者特定的子集进行表示，但是嵌入之后的向量空间具有更加灵活和丰富的计算方式。
• 图嵌入能够压缩数据， 我们一般用邻接矩阵描述图中节点之间的连接。 连接矩阵的维度是$|V| \times|V|$，其中$|V|$ 是图中节点的个数。矩阵中的每一列和每一行都代表一个节点。矩阵中的非零值表示两个节点已连接。将邻接矩阵用用大型图的特征空间几乎是不可能的。一个具有1M节点和1M $\times$ 1M的邻接矩阵的图该怎么表示和计算呢？但是嵌入可以看做是一种压缩技术，能够起到降维的作用。
• 向量计算比直接在图上操作更加的简单、快捷

但是图嵌入也需要满足一定的要求

• 学习属性的选择：不同的向量化表示方法，都是对网络信息的一种摘要。有时我们会倾向于保存网络中节点的近邻关系，有时倾向学习节点在网络中的角色（比如中心节点）。不同的应用对“学习属性”的选择有不同的要求，故而引发了各类算法的爆发。
• 规模化：现实应用中有很多网络包含了大量的节点和边，高效的向量化方法，能够在短时间内处理超大规模的网络，才比较有实际应用的可能性。
• 向量维度：如何确定合适的向量表示维度，是一个很难的问题，并且也是和具体场景相关的。事实上，越高的维度可能带来越好的效果，但是会极大降低应用性能。平衡性能和效果，在不同的应用中需要因地制宜。

1.2 词语嵌入方法(word2vec)

node2vec是节点嵌入方法中的代表，而节点的嵌入方法借鉴了自然语言处理（NLP）中很一个重要的方法——word2vec。更多资料可以参考词向量word2vec

该方法能够成立的核心原因是：图中的节点和语料库中的单词的分布都遵循幂定律，我们可以利用基于大量数据的学习方法来找出节点之间、单词之间的规律。

图游走算法：在图上进行游走得到游走序列，通过图表示学习利用节点之间的关系得到节点的一维表示，进而用这些一维表示进行下游人物。

图游走类算法的目标，就是学习出图中每一个节点的低维表示，称为 Node Embeddings，在得到这些 embeddings 之后，就可以利用这些低维表示来进行接下来的下游任务，比如节点分类之类的等等。

为什么可以用这个低维表示来做下游任务呢？

因为可以利用一些方法，使得每个节点的 embeddings 可以学习到节点跟它的邻居的关系，更好的表示图结构和图特征的信息。

图游走算法最先参考的是NLP的Word2vec模型，Word2vec模型的其中一种方法是Skip Gram，即根据中心词预测上下文，之后通过负采样的方式进行优化。

将Word2vec的思想和图结合起来就会得到了图游走类算法

算法思想

假设，如果只给出苹果这一个词，而没有其他的信息，那么，这个词的词义其实是模糊的。因为苹果可能指的是水果，又或者是手机，但如果给出有关于苹果的很多个句子：通过多个句子的上下文，其实可以大概了解到，上面所展示的苹果这个词的语义，是一种水果、一种食物。通过这个例子，可以得出这样的一个结论，即词的语义由其上下文决定。Word2vec 其实就是利用了这样的一个思想。

整体架构

Word2vec 模型，可以简单的理解为 Skip Gram + 负采样

1.1.1 Skip Gram模型——根据中心词预测上下文

在Word2vec 中，提出了两种模型结构用于学习词向量，分别是 CBOW 和 Skip Gram。由于图游走类算法用的多是 skip-gram 模型，因此这里只介绍 skip-gram 模型。Skip Gram的目的很简单，就是根据中心词，预测对应中心词的上下文词。这样做不仅仅能够利用了词共现关系，同时也体现了 Word2vec的本质，即词的语义由其上下文来决定。

以下面这张图片的句子为例，假设 neighbors 为中心词，同时我们设置了window size为3. 这个窗口大小表示左右两边的上下文词数，因此 neighbors 的 context 为 uniformly from the，以及 of the last。

Skip gram 的模型结构很简单，输入层就是中心词的 one hot 表示，经过中间一个投影层后，在输出层预测对应的context word，因此最后一层就是一个softmax分类层。

需要补充的一点是，使用 Skipgram语言模型的本质并不是为了说多么准确的预测 context words，而是为了得到模型的副产物，也就是词向量。

通常在训练结束后，隐层的权重 W 会作为词向量矩阵。

Word2Vec模型实际上分为了两个部分：

1. 第一部分为建立模型得到隐层参数，
2. 第二部分是通过模型获取嵌入词向量。

Word2Vec的整个建模过程实际上与自编码器（auto-encoder）的思想很相似，即先基于训练数据构建一个神经网络，当这个模型训练好以后，我们并不会用这个训练好的模型处理新的任务，我们真正需要的是这个模型通过训练数据所学得的参数，例如隐层的权重矩阵——后面我们将会看到这些权重在Word2Vec中实际上就是我们试图去学习的“word vectors”。基于训练数据建模的过程，我们给它一个名字叫“Fake Task”，意味着建模并不是我们最终的目的。

上面提到的这种方法实际上会在无监督特征学习（unsupervised feature learning）中见到，最常见的就是自编码器（auto-encoder）：通过在隐层将输入进行编码压缩，继而在输出层将数据解码恢复初始状态，训练完成后，我们会将输出层“砍掉”，仅保留隐层。

我们在上面提到，训练模型的真正目的是获得模型基于训练数据学得的隐层权重。为了得到这些权重，我们首先要构建一个完整的神经网络作为我们的“Fake Task”，后面再返回来看通过“Fake Task”我们如何间接地得到这些词向量。

模型的输出概率代表着到我们词典中每个词有多大可能性跟input word同时出现。举个栗子，如果我们向神经网络模型中输入一个单词“Soviet“，那么最终模型的输出概率中，像“Union”， ”Russia“这种相关词的概率将远高于像”watermelon“，”kangaroo“非相关词的概率。因为”Union“，”Russia“在文本中更大可能在”Soviet“的窗口中出现。
我们将通过给神经网络输入文本中成对的单词来训练它完成上面所说的概率计算。下面的图中给出了一些我们的训练样本的例子。

我们选定句子“The quick brown fox jumps over lazy dog”，设定我们的窗口大小为2，也就是说我们仅选输入词前后各两个词和输入词进行组合。下图中，蓝色代表input word，方框内代表位于窗口内的单词。

我们的模型将会从每对单词出现的次数中习得统计结果。例如，我们的神经网络可能会得到更多类似（“fox”，“quick”）这样的训练样本对，而相对而言，对于（“fox”，“lazy”）这样的组合却看到的很少。因此，当我们的模型完成训练后，给定一个单词“fox”作为输入，输出的结果中“quick”或者“jumps”要比“lazy”被赋予更高的概率。可以看到，我们总是以中间词放在第一个位置，然后跟着我们的前后相邻词。可以看到，每一对词都是一个输入和一个输出组成的数据对(X,Y)。其中，X是feature，Y是label。

我们都知道神经网络只能接受数值输入，我们不可能把一个单词字符串作为输入，因此我们得想个办法来表示这些单词。最常用的办法就是基于训练文档来构建我们自己的词汇表（vocabulary）再对单词进行one-hot编码。模型的输入如果为一个10000维的向量，那么输出也是一个10000维度（词汇表的大小）的向量，它包含了10000个概率，每一个概率代表着当前词是输入样本中output word的概率大小。

我们把这样的词组对分别表示成one-hot向量，input word的向量作为Fake Task网络的输入，output word的向量作为学习的目标。

这样，我们基于成对的单词来对神经网络进行训练，训练样本是 ( input word, output word ) 这样的单词对，input word和output word都是one-hot编码的向量。最终模型的输出是一个概率分布。
如果我们现在想用300个特征来表示一个单词（即每个词可以被表示为300维的向量）。那么隐层的权重矩阵应该为10000行，300列（隐层有300个结点）。

Fake Task的训练过程，我们最终的目标就是学习这个隐层的权重矩阵。

这个隐层的权重矩阵，便成了一个“查找表（lookup table）”，进行矩阵计算时，直接去查输入向量中取值为1的维度下对应的那些权重值。隐层的输出就是每个输入单词的“嵌入词向量”。

Word2Vec模型

经过神经网络隐层的计算，ants这个词会从一个1 x 10000的向量变成1 x 300的向量，再被输入到输出层。输出层是一个softmax回归分类器，它的每个结点将会输出一个0-1之间的值（概率），这些所有输出层神经元结点的概率之和为1。

现在，我们拥有10000个单词的词汇表，我们如果想嵌入300维的词向量，那么我们的输入-隐层权重矩阵和隐层-输出层的权重矩阵都会有 10000 x 300 = 300万个权重，在如此庞大的神经网络中进行梯度下降是相当慢的。更糟糕的是，你需要大量的训练数据来调整这些权重并且避免过拟合。百万数量级的权重矩阵和亿万数量级的训练样本意味着训练这个模型将会是个灾难。

Word2Vec论文提出了三个创新点：

1. 将常见的单词组合（word pairs）或者词组作为单个“words”来处理。
2. 对高频次单词抽样来减少训练样本的个数。
3. 对优化目标采用“negative sampling”方法，这样每个训练样本的训练只会更新一小部分的模型权重，从而降低计算负担。

更多资料可以参考[词向量word2vec]

1.1.2 Negative Sampling——负采样

假设，给定中心词 orange，预测其上下文词中的 juice：

Softmax 层在 Skipgram 模型中是用来计算词表的概率的。

为了能够预测出 juice，不仅要预测它的概率，还要预测整个词表中所有单词的概率。但这样做的计算量是非常大的，因此，这里使用负采样的方法进行优化。

负采样的思想很简单。将中心词和对应的上下文词作为正样本，比如这里的 (orange, juice)。同时，选取一定数量的负样本，比如3个。

确定要正样本和负样本之后，就不再需要计算所有词的概率，而只需要对这几个样本进行分类，如果 Y=1，意味着是正样本，Y=0，意味着是负样本。从而减少了计算量。

也就是把 softmax 层修改为了多个 sigmoid 函数，从而大大减少了计算量和参与权重更新的参数数目。

1.1.3 应用到图嵌入领域

近朱者赤，近墨者黑。

也就是说，周遭的环境对于我们来说会有一定的影响，因此也可以表现为，图中的节点会受到其邻居的影响。

当然，这种情况也不仅仅只存在社交网络这个范围内，在很多其他的图，比如推荐系统等等，节点都会受到邻居的影响。

这也是为什么可以将Word2vec这个方法迁移到图嵌入领域的原因

2.DeepWalk（原理+实践）

游走模型的鼻祖是DeepWalk模型，它也是第一个将 NLP 领域的思想运用到图嵌入领域的模型。

2.1 节点嵌入方法（Node embeddings）

首先为什么要用DeepWalk。我们可以观察到，Word2Vec中，处理的是语句数据，词语之间只有前后之间的联系，可以很自然的将句子中的词语分成不同的词组。但是在图数据中，节点与节点之前的联系——边，边的构成使得图数据能够比语句数据构成节点之间更加复杂的关系。通过游走策略，我们可以将一个复杂的图数据转换为多个之后前后关联的链路数据。

DeepWalk通过随机游走(truncated random walk)学习出一个网络的表示，在网络标注顶点很少的情况也能得到比较好的效果。随机游走起始于选定的节点，然后从当前节点移至随机邻居，并执行一定的步数，该方法大致可分为四个步骤：

1. 图a展示了原始的用户行为序列。
2. 图b基于这些用户行为序列构建了物品相关图，可以看出，物品A，B之间的边产生的原因就是因为用户U1先后购买了物品A和物品B，所以产生了一条由A到B的有向边。如果后续产生了多条相同的有向边，则有向边的权重被加强。在将所有用户行为序列都转换成物品相关图中的边之后，全局的物品相关图就建立起来了。
3. 图c采用随机游走的方式随机选择起始点，重新产生物品序列。
4. 图d最终将这些物品序列输入word2vec模型，生成最终的物品Embedding向量。

在上述DeepWalk的算法流程中，核心是第三步，其中唯一需要形式化定义的是随机游走的跳转概率，也就是到达节点$v_i$后，下一步遍历$v_i$的临接点$v_j$的概率。如果物品的相关图是有向有权图，那么从节点$v_i$跳转到节点$v_j$的概率定义如下：

$$P(v_{j}|v_{i})=\left{\begin{matrix}
\frac{M_{ij}}{\sum_{j\in N_+(v_{i})}M_{ij}} & , v_{j} \in N_+(v_{i}),\
0&, e_{ij}\notin \varepsilon
\end{matrix}\right.$$

其中$N_+(v_i)$是节点$v_i$所有的出边集合，$M_{ij}$是节点$v_i$到节点$v_j$边的权重。

如果物品相关图是无相无权重图，那么跳转概率将是上面公式的一个特例，即权重$M_{ij}$将为常数1，且$N_+(v_i)$应是节点$v_i$所有“边”的集合，而不是所有“出边”的集合。

DeepWalk通过随机游走去可以获图中点的局部上下文信息，因此学到的表示向量反映的是该点在图中的局部结构，两个点在图*有的邻近点（或者高阶邻近点）越多，则对应的两个向量之间的距离就越短

整体架构

DeepWalk就相当于随机游走+Skip Gram+负采样的结合

与 Word2vec 的不同，其实就是多了一个采样节点序列的随机游走部分。因此这两者实现起来其实是非常类似的。

在DeepWalk中，将每个节点看作是单词，节点序列看作是句子。如下图

Random Walk

不同于NLP中可以获取很多的语料，DeepWalk采用了随机游走的方法来获取节点序列（可回头的深度优先搜索）。下式中的π是节点的转移概率分布，Z是归一化系数，在DeepWalk中可以理解成转移到每一个邻居节点的概率都是相同的。

具体过程

从图中的某个节点出发，游走的每一步都从与当前节点相连的边中随机选择一条，沿着选定的边移动到下一个顶点，不断重复这个过程，直到得到的序列无法继续往下走或者到达指定最大长度。

在走了多趟之后，便可以得到多个游走序列，此时就可以类比 NLP 中的句子了。

随机游走的本质，其实就是可以“回头”的深度优先搜索

DeepWalk选取随机游走序列中下一个节点的方式是均匀随机分布的，因此对于与当前节点有边相连的节点，都有相同的概率被选择。

在 DeepWalk 中，会针对图中的每个节点采样多条序列，得到这些节点序列之后，就可以直接套用 Word2vec 模型了。

2.2 DeepWalk代码实现

%matplotlib inline
import matplotlib.pyplot as plt
import networkx as nx # networkx是一个常用的绘制复杂图形的Python包。
import pgl
def build_graph():
    # 定义节点的个数；每个节点用一个数字表示，即从0~9
    num_node = 10
    # 添加节点之间的边，每条边用一个tuple表示为: (src, dst)
    edge_list = [(2, 0), (2, 1), (3, 1),(4, 0), (0, 5), 
             (6, 0), (6, 4), (5, 6), (7, 0), (1, 7),
             (2, 7), (7, 3), (8, 0), (9, 7)]

    g = pgl.graph.Graph(num_nodes = num_node, edges = edge_list)

    return g

# 创建一个图对象，用于保存图网络的各种数据。
g = build_graph()

def display_graph(g):
    nx_G = nx.Graph()
    nx_G.add_nodes_from(range(g.num_nodes))
    nx_G.add_edges_from(g.edges)
    
    pos = nx.spring_layout(nx_G, iterations=50)
    
    nx.draw(nx_G, 
            pos,
            with_labels=True,
            node_color=['y','g','g','g','y','y','y','g','y','g'], 
            node_size=1000)

    plt.show()

display_graph(g)

def deepwalk(graph, start_node, walk_len):
    walk = [start_node] # 初始化游走序列

    for d in range(walk_len): # 最大长度范围内进行采样
        current_node = walk[-1] 
        successors = graph.successor(np.array([current_node])) # graph.successor: 获取当前节点的后继邻居
        print("当前节点: %d" % current_node)
        print("后继邻居", successors[0])
        succ = successors[0]
        if len(succ) == 0:
            break
        next_node = np.random.choice(succ, 1)
        walk.extend(next_node)
        
    return walk

from pgl.graph import Graph

import numpy as np

class UserDefGraph(Graph):
    def random_walk(self, nodes, walk_len):
        """
        输入：nodes - 当前节点id list (batch_size,)
             walk_len - 最大路径长度 int
        输出：以当前节点为起点得到的路径 list (batch_size, walk_len)

        用到的函数
        1. self.successor(nodes)
           描述：获取当前节点的下一个相邻节点id列表
           输入：nodes - list (batch_size,)
           输出：succ_nodes - list of list ((num_successors_i,) for i in range(batch_size))
        2. self.outdegree(nodes)
           描述：获取当前节点的出度
           输入：nodes - list (batch_size,)
           输出：out_degrees - list (batch_size,)
        """
        walks = [[node] for node in nodes]   # 首先获得当前节点列表对应的一个向量

        walks_ids = np.arange(0, len(nodes))  # 游走路径中节点对应id号
        cur_nodes = np.array(nodes)          # 当前节点情况
        for l in range(walk_len):   # 根据游走长度进行遍历--破出条件：1. range结束；2. outdegree==0【出度为零，没有可继续的节点】
            """选取有下一个节点的路径继续采样，否则结束"""
            outdegree = self.outdegree(cur_nodes)  # 计算当前节点的出度--也就是对应有哪些位置的邻近节点
            walk_mask = (outdegree != 0)           # 根据出度来确定掩码--True， False--将出度为0的部分复制为False，反之True
            if not np.any(walk_mask):              # 判断是否没有可继续的节点情况--出度为0
               break
            cur_nodes = cur_nodes[walk_mask]       # 根据掩码获取可继续前进的节点，作为后边讨论的当前可前行节点
            walks_ids = walks_ids[walk_mask]       # 获取掩码下，原节点id，组成新的work_ids用于后边讨论，但本身还是作为一个节点的标记，对应这是第几个节点
            outdegree = outdegree[walk_mask]       # 根据掩码获取相应的不为0的出度--用于后边计算前行的路径

            ######################################
            # 请在此补充代码采样出下一个节点
            '''
               [注解有点多，所以放外边了]
               PS:
                 1. successor 可获取当前节点的下一个相邻节点id列表，
                    那么successor 计算出下一节点的集合后，我们需要从中随机取出一个节点--所以我们要创建随机采样的index_list（索引序列集）
                 2. 创建index_list=>为了才到合适的index信息，采用np.floor与np.random,rand()实现：
                    eg: np.floor(np.random.rand(outdegree.shape[0]) * outdegree).astype('int64')
                        np.random.rand(outdegree.shape[0]): 根据出度集的形状来取得相应形状的随机数--这里体现游走的随机性
                        np.random.rand(outdegree.shape[0]) * outdegree：利用生成的随机数与出度集对应元素相乘——这里得到一些列的随机数，随机数范围在0~最大出度值--保证路径有效
                        np.floor(np.random.rand(outdegree.shape[0]) * outdegree)——实现向下取整，这样就得到了相应游走路径中接下来那个点的索引
                    具体实例：
                         np.floor(np.random.rand(20) * 3).astype('int64')
                         result: array([0, 1, 2, 1, 0, 0, 0, 0, 1, 1, 1, 2, 0, 2, 2, 2, 2, 1, 2, 0])
                 3. 既然知道了随机采样的序列集了，那么接下就是分配新的游走路径了
                    next_nodes = []  # 用于后边存放—— 装配有下一个节点的新路径
                    # 参数说明：
                        succ_nodes：相邻节点id列表
                        sample_index：对应出度生成的随即索引集
                        walks_ids：游走路径中节点对应id号
                    # 接下来的循环指的是，将节点列表、随机采样序列、游走路径中节点对应id号一一对应进行填充--得到一个游走情况
                    for s, ind, walk_id in zip(succ_nodes, sample_index, walks_ids):
                        walks[walk_id].append(s[ind])    # 注意： 从开始已经知道walks=>[[], [], []]是这种形式的，这样这里的append，就很容易理解成为相应节点添加可以继续前行的节点，形成一条路径
                        next_nodes.append(s[ind])        # 同时获取接下来要重新讨论游走时所需的新节点--即：如：从1走到了2，从3走到了7: [[1], [3]]=>[[1, 2], [3, 7]]
                                                         # 接下来自然就该考虑把新的2, 7 作为下一次游走时讨论出度的节点啦
            '''
            succ_nodes = self.successor(cur_nodes)  # 返回可继续的节点集合
            # next_nodes = ...
            sample_index = np.floor(np.random.rand(outdegree.shape[0]) * outdegree).astype('int64')
            next_nodes = []
            for s, ind, walk_id in zip(succ_nodes, sample_index, walks_ids):
               walks[walk_id].append(s[ind])
               next_nodes.append(s[ind])
            ######################################
            cur_nodes = np.array(next_nodes)  # 将节点转换为np类型，方便一些操作运算--同时保证前后数据类型
        
        # 遍历完游走长度的次数，就可以返回得到的随机游走路径啦
        return walks

因存在多版本问题（基于PGL1.2.1 paddle1.8），这部分的详细实现参考链接：图学习【参考资料2】-知识补充与node2vec代码注解 https://aistudio.baidu.com/aistudio/projectdetail/5012408?contributionType=1

结果展示：

[INFO] 2022-11-11 14:28:21,009 [my_deepwalk.py:  250]:	Step 1170 DeepWalk Loss: 0.189346  0.239437 s/step.
[INFO] 2022-11-11 14:28:23,367 [my_deepwalk.py:  250]:	Step 1180 DeepWalk Loss: 0.186947  0.230984 s/step.
[INFO] 2022-11-11 14:28:25,729 [my_deepwalk.py:  250]:	Step 1190 DeepWalk Loss: 0.193626  0.233627 s/step.
[INFO] 2022-11-11 14:28:28,099 [my_deepwalk.py:  250]:	Step 1200 DeepWalk Loss: 0.198106  0.242671 s/step.
[INFO] 2022-11-11 14:28:30,539 [my_deepwalk.py:  250]:	Step 1210 DeepWalk Loss: 0.187183  0.309996 s/step.
[INFO] 2022-11-11 14:28:33,171 [my_deepwalk.py:  250]:	Step 1220 DeepWalk Loss: 0.189533  0.244672 s/step.
[INFO] 2022-11-11 14:28:35,537 [my_deepwalk.py:  250]:	Step 1230 DeepWalk Loss: 0.202293  0.232859 s/step.
[INFO] 2022-11-11 14:28:37,920 [my_deepwalk.py:  250]:	Step 1240 DeepWalk Loss: 0.189366  0.244727 s/step.
[INFO] 2022-11-11 14:28:40,450 [my_deepwalk.py:  250]:	Step 1250 DeepWalk Loss: 0.188601  0.254400 s/step.
[INFO] 2022-11-11 14:28:42,875 [my_deepwalk.py:  250]:	Step 1260 DeepWalk Loss: 0.191343  0.247985 s/step.
[INFO] 2022-11-11 14:28:45,286 [my_deepwalk.py:  250]:	Step 1270 DeepWalk Loss: 0.186549  0.255688 s/step.
[INFO] 2022-11-11 14:28:47,653 [my_deepwalk.py:  250]:	Step 1280 DeepWalk Loss: 0.188638  0.240493 s/step.

[INFO] 2022-11-11 14:29:40,063 [link_predict.py:  223]:			Step 160 Test Loss: 0.403480 Test AUC: 0.960065 
[INFO] 2022-11-11 14:29:42,963 [link_predict.py:  199]:	Step 170 Train Loss: 0.399953 Train AUC: 0.960795 
[INFO] 2022-11-11 14:29:43,092 [link_predict.py:  223]:			Step 170 Test Loss: 0.400902 Test AUC: 0.960164 
[INFO] 2022-11-11 14:29:45,898 [link_predict.py:  199]:	Step 180 Train Loss: 0.398023 Train AUC: 0.960870 
[INFO] 2022-11-11 14:29:46,023 [link_predict.py:  223]:			Step 180 Test Loss: 0.399052 Test AUC: 0.960234 
[INFO] 2022-11-11 14:29:48,816 [link_predict.py:  199]:	Step 190 Train Loss: 0.396805 Train AUC: 0.960916 
[INFO] 2022-11-11 14:29:48,951 [link_predict.py:  223]:			Step 190 Test Loss: 0.397910 Test AUC: 0.960275 
[INFO] 2022-11-11 14:29:51,783 [link_predict.py:  199]:	Step 200 Train Loss: 0.396290 Train AUC: 0.960936 
[INFO] 2022-11-11 14:29:51,913 [link_predict.py:  223]:			Step 200 Test Loss: 0.397469 Test AUC: 0.960292 

3. node2vec（原理+实践）

3.1 node2vec原理

Node2vec是图表征学习的一个重要的算法框架。

框架图：

2016年，斯坦福大学在DeepWalk的基础上更进一步，通过调整随机游走权重的方法使graph embedding的结果在网络的同质性（homophily）和结构性（structural equivalence）中进行权衡权衡。
具体来讲，网络的“同质性”指的是距离相近节点的embedding应该尽量近似，如下图所示，节点u与其相连的节点s1、s2、s3、s4的embedding表达应该是接近的，这就是“同质性“的体现。“结构性”指的是结构上相似的节点的embedding应该尽量接近，图中节点u和节点s6都是各自局域网络的中心节点，结构上相似，其embedding的表达也应该近似，这是“结构性”的体现。

DeepWalk存在的问题是比较简单直接，而图结构往往是一个复杂结构，需要考虑很多因素，在深度优先搜索方法之外，还有广度优先搜索，结合以上两种方式可以更好的探索图模型，即node2vec。

node2vec和DeepWalk相比主要修改的是转移概率分布，不同于随机游走相邻节点转移的概率相同，node2vec考虑了边的权值和节点之间的距离，具体如下：

• 为了使Graph Embedding的结果能够表达网络的同质性，在随机游走的过程中，需要让游走的过程更倾向于宽度优先搜索（BFS），因为BFS更喜欢游走到跟当前节点有直接连接的节点上，因此就会有更多同质性信息包含到生成的样本序列中，从而被embedding表达；
• 另一方面，为了抓住网络的结构性，就需要随机游走更倾向于深度优先搜索（DFS），因为DFS会更倾向于通过多次跳转，游走到远方的节点上，使得生成的样本序列包含更多网络的整体结构信息。

那么在node2vec算法中，是怎样控制BFS和DFS的倾向性的呢？主要是通过节点间的跳转概率。下图显示了node2vec算法从节点t跳转到节点v后，下一步从节点v跳转到周围各点的跳转概率。

形式化来讲，从节点v跳转到下一个节点x的概率为

$$\pi _{VX}=\alpha _{pq}(t,x)\cdot \omega _{vx}$$

其中$\omega _{vx}$是边vx的权重，$\alpha _{pq}(t,x)$的定义如下：

$$\alpha {pq}(t,x)=\left{\begin{matrix}
\frac{1}{p} & if \ d{tx}=0 & \
1 & if \ d_{tx}=1 & \
\frac{1} {q} & if \ d_{tx}=2 &
\end{matrix}\right.$$

其中，$d_{tx}$指的是节点$t$到节点$x$的距离，参数$p$和$q$共同控制着随机游走的倾向性。参数$p$被称为返回参数（return parameter），$p$越小，随机游走回节点$t$的可能性越大，node2vec就更注重表达网络的同质性，参数$q$被称为进出参数（in-out parameter），$q$越小，则随机游走到远方节点的可能性越大，node2vec更注重表达网络的结构性，反之，当前节点更可能在附近节点游走。

上式中的p和q是算法中的超参数，通过控制两个参数来确定图的游走程度。参数p控制随机游走以多大的概率游走回上一个节点，参数q控制游走的策略是偏向DFS还是BFS，q较大时偏向于BFS，q较小时偏向于DFS。当p=q=1时，π=w

node2vec所体现的网络的同质性和结构性在推荐系统中也是可以被很直观的解释的。同质性相同的物品很可能是同品类、同属性、或者经常被一同购买的物品，而结构性相同的物品则是各品类的爆款、各品类的最佳凑单商品等拥有类似趋势或者结构性属性的物品。毫无疑问，二者在推荐系统中都是非常重要的特征表达。由于node2vec的这种灵活性，以及发掘不同特征的能力，甚至可以把不同node2vec生成的embedding融合共同输入后续深度学习网络，以保留物品的不同特征信息。

因存在多版本问题（基于PGL1.2.1 paddle1.8），这部分的详细实现参考链接：图学习【参考资料2】-知识补充与node2vec代码注解 https://aistudio.baidu.com/aistudio/projectdetail/5012408?contributionType=1

结果展示：

[INFO] 2022-11-11 14:37:32,694 [my_node2vec.py:  358]:	Step 670 Node2vec Loss: 0.184862  0.288450 s/step.
[INFO] 2022-11-11 14:37:35,643 [my_node2vec.py:  358]:	Step 680 Node2vec Loss: 0.180727  0.291284 s/step.
[INFO] 2022-11-11 14:37:39,554 [my_node2vec.py:  358]:	Step 690 Node2vec Loss: 0.169635  0.441471 s/step.
[INFO] 2022-11-11 14:37:42,473 [my_node2vec.py:  358]:	Step 700 Node2vec Loss: 0.172884  0.245686 s/step.
[INFO] 2022-11-11 14:37:45,268 [my_node2vec.py:  358]:	Step 710 Node2vec Loss: 0.161657  0.261186 s/step.
[INFO] 2022-11-11 14:37:48,225 [my_node2vec.py:  358]:	Step 720 Node2vec Loss: 0.167449  0.260464 s/step.
[INFO] 2022-11-11 14:37:51,188 [my_node2vec.py:  358]:	Step 730 Node2vec Loss: 0.172065  0.297069 s/step.
[INFO] 2022-11-11 14:37:54,039 [my_node2vec.py:  358]:	Step 740 Node2vec Loss: 0.168043  0.174017 s/step.

[INFO] 2022-11-11 14:38:49,260 [link_predict.py:  223]:			Step 170 Test Loss: 0.454974 Test AUC: 0.954118 
[INFO] 2022-11-11 14:38:51,997 [link_predict.py:  199]:	Step 180 Train Loss: 0.452219 Train AUC: 0.955133 
[INFO] 2022-11-11 14:38:52,122 [link_predict.py:  223]:			Step 180 Test Loss: 0.453069 Test AUC: 0.954312 
[INFO] 2022-11-11 14:38:54,851 [link_predict.py:  199]:	Step 190 Train Loss: 0.450969 Train AUC: 0.955254 
[INFO] 2022-11-11 14:38:54,978 [link_predict.py:  223]:			Step 190 Test Loss: 0.451892 Test AUC: 0.954428 
[INFO] 2022-11-11 14:38:57,714 [link_predict.py:  199]:	Step 200 Train Loss: 0.450440 Train AUC: 0.955305 
[INFO] 2022-11-11 14:38:57,842 [link_predict.py:  223]:			Step 200 Test Loss: 0.451436 Test AUC: 0.954473 

4.基于PGL2.2版本算法实现

4.1 数据集介绍

4.1.1 引文网络（Cora、PubMed、Citeseer）

引文网络，顾名思义就是由论文和他们的关系构成的网络，这些关系包括例如引用关系、共同的作者等，具有天然的图结构，数据集的任务一般是论文的分类和连接的预测，比较流行的数据集有三个，分别是Cora、PubMed、Citeseer，它们的组成情况如图1所示，Nodes也就是数据集的论文数量，features是每篇论文的特征，数据集中有一个包含多个单词的词汇表，去除了出现频率小于10的词，但是不进行编码，论文的属性是由一串二进制码构成，只用0和1表示该论文有无这个词汇。

文件构成

• 以cora数据集为例，数据集包含两个文件，cora.cites和cora.content，cora.cites文件中的数据如下：

• 即原论文和引用的论文，刚好构成了一条天然的边，cora.content文件的数据如下：

• 有论文id、上面说到的二进制码和论文对应的类别组成，其余两个数据集类似。

4.1.2 社交网络（BlogCatalog、Reddit、Epinions）

BlogCatalog数据集是一个社会关系网络，图是由博主和他（她）的社会关系（比如好友）组成，labels是博主的兴趣爱好。Reddit数据集是由来自Reddit论坛的帖子组成，如果两个帖子被同一人评论，那么在构图的时候，就认为这两个帖子是相关联的，labels就是每个帖子对应的社区分类。Epinions是一个从一个在线商品评论网站收集的多图数据集，里面包含了多种关系，比如评论者对于另一个评论者的态度（信任/不信任），以及评论者对商品的评级。

文件构成

BlogCatalog数据集的结点数为10312，边条数为333983，label维度为39，数据集包含两个文件：

• Nodes.csv：以字典的形式存储用户的信息，但是只包含节点id。

• Edges.csv：存储博主的社交网络（好友等），以此来构图。

Epinions数据集包含文件如下：

• Ratings_data.txt：包含用户对于一件物品的评级，文件中每一行的结构为user_id

• item_id rating_value。

• Trust_data.txt：存储了用户对其他用户的信任状态，存储方式为source_user_id

• target_user_id trust_statement_value，其中信任状态只有信任和不信任（1、0）。

由于Reddit comments 数据集的文件太多，所以这里略过了，如果需要或者感兴趣的话，可以从文末的连接进入查看。

相关论文：

Rossi, R. A. , & Ahmed, N. K. . (2015). The Network Data Repository with Interactive Graph Analytics and Visualization. Twenty-ninth Aaai Conference on Artificial Intelligence. AAAI Press.

4.1.3.生物化学结构（PPI、NCI-1、NCI-109、MUTAG、QM9、Tox21）

PPI是蛋白质互作网络，数据集*有24张图，其中20张作为训练，2张作为验证，2张作为测试，每张图对应不同的人体组织，实例如图3，该数据是为了从系统的角度研究疾病分子机制、发现新药靶点等等。

平均每张图有2372个结点，每个结点特征长度为50，其中包含位置基因集，基序集和免疫学特征。基因本体集作为labels（总共121个），labels不是one-hot编码。

NCI-1、NCI-109和MUTAG是关于化学分子和化合物的数据集，原子代表结点，化学键代表边。NCI-1和NCI-109数据集分别包含4100和4127个化合物，labels是判断化合物是否有阻碍癌细胞增长得性质。MUTAG数据集包含188个硝基化合物，labels是判断化合物是芳香族还是杂芳族。

QM9数据集包括了13万有机分子的构成,空间信息及其对应的属性. 它被广泛应用于各类数据驱动的分子属性预测方法的实验和对比。

Toxicology in the 21st Century 简称tox21，任务是使用化学结构数据预测化合物对生物化学途径的干扰，研究、开发、评估和翻译创新的测试方法，以更好地预测物质如何影响人类和环境。数据集有12707张图，12个labels。

文件构成
PPI数据集的构成：

train/test/valid_graph.json：保存了训练、验证、测试的图结构数据。

train/test/valid_feats.npy ：保存结点的特征，以numpy.ndarry的形式存储，shape为[n, v]，n是结点的个数，v是特征的长度。

train/test/valid_labels.npy：保存结点的label，也是以numpy.ndarry的形式存储，形为n*h，h为label的长度。

train/test/valid/_graph_id.npy ：表示这个结点属于哪张图，形式为numpy.ndarry，例如[1, 1, 2, 1...20].。

NCI-1、NCI-109和MUTAG数据集的文件构成如下：（用DS代替数据集名称）

n表示结点数，m表示边的个数，N表示图的个数

DS_A.txt (m lines)：图的邻接矩阵，每一行的结构为(row, col)，即一条边。

DS_graph_indicator.txt (n lines)：表明结点属于哪一个图的文件。

DS_graph_labels.txt (N lines)：图的labels。

DS_node_labels.txt (n lines)：结点的labels。

DS_edge_labels.txt (m lines)：边labels。

DS_edge_attributes.txt (m lines)：边特征。

DS_node_attributes.txt (n lines)：结点的特征。

DS_graph_attributes.txt (N lines)：图的特征，可以理解为全局变量。

QM9的文件结构如下：

QM9_nano.npz：该文件需要用numpy读取,其中包含三个字段：

'ID' 分子的id，如:qm9:000001；

'Atom' 分子的原子构成，为一个由原子序数的列表构成,如[6,1,1,1,1]表示该分子由一个碳(C)原子和4个氢(H)原子构成.；

'Distance' 分子中原子的距离矩阵,以上面[6,1,1,1,1]分子为例,它的距离矩阵即为一个5x5的矩阵,其中行列的顺序和上述列表一致,即矩阵的第N行/列对应的是列表的第N个原子信息.

'U0' 分子的能量属性(温度为0K时),也是我们需要预测的值（分类的种类为13）

Tox21文件夹中包含13个文件，其中12个文件夹就是化合物的分类

4.1.4 ArXiv

http://snap.stanford.edu/data/ca-AstroPh.html

Arxiv ASTRO-PH（天体物理学）协作网络是来自电子版预影印平台arXiv，涵盖了提交到Astro Physics类别的论文，包含了不同作者之间的科学合作信息。 如果作者i与作者j共同撰写了论文，则该图包含从i到j的无向边。 如果论文由k位作者共同撰写，则将在k个节点上生成完全连接的（子）图。

数据涵盖了1993年1月至2003年4月（124个月）期间的论文。 它始于arXiv成立后的几个月内，因此基本上代表了其ASTRO-PH部分的完整历史。

ArXiv数据集的结点数为18772，边条数为198110。

相关论文
J. Leskovec, J. Kleinberg and C. Faloutsos. Graph Evolution: Densification and Shrinking Diameters. ACM Transactions on Knowledge Discovery from Data (ACM TKDD), 1(1), 2007.

4.1.5 下载地址

Cora：https://s3.us-east-2.amazonaws.com/dgl.ai/dataset/cora_raw.zip

Pubmed：https://s3.us-east-2.amazonaws.com/dgl.ai/dataset/pubmed.zip

Citeseer：https://s3.us-east-2.amazonaws.com/dgl.ai/dataset/citeseer.zip

BlogCatalog：http://socialcomputing.asu.edu/datasets/BlogCatalog

Reddit：https://github.com/linanqiu/reddit-dataset

Epinions：http://www.trustlet.org/downloaded_epinions.html

PPI：http://snap.stanford.edu/graphsage/ppi.zip

NCI-1：https://ls11-www.cs.uni-dortmund.de/people/morris/graphkerneldatasets/NCI1.zip

NCI-109：https://ls11-www.cs.uni-dortmund.de/people/morris/graphkerneldatasets/NCI109.zip

MUTAG：https://ls11-www.cs.uni-dortmund.de/people/morris/graphkerneldatasets/MUTAG.zip

QM9：https://github.com/geekinglcq/QM9nano4USTC

Tox21：https://tripod.nih.gov/tox21/challenge/data.jsp

4.2deepwalk(多类别预测任务)

数据集为：BlogCatalog

Paddle2.0+是动态图了，为了进一步简化使用，将GraphWrapper的概念去掉了，目前可以直接在Graph上进行Send/Recv

#uninstall pgl 2.1
python -m pip uninstall pgl
#install pgl 1.2.1
python -m pip install pgl==1.2.1

部分结果展示：

[INFO] 2022-11-13 22:44:29,956 [    train.py:   81]:	Batch 7990 train-Loss 0.456979
[INFO] 2022-11-13 22:44:30,900 [    train.py:   81]:	Batch 8000 train-Loss 0.457403
[INFO] 2022-11-13 22:44:31,791 [    train.py:   81]:	Batch 8010 train-Loss 0.456784
[INFO] 2022-11-13 22:44:32,675 [    train.py:   81]:	Batch 8020 train-Loss 0.453279
[INFO] 2022-11-13 22:44:33,593 [    train.py:   81]:	Batch 8030 train-Loss 0.455351
[INFO] 2022-11-13 22:44:34,529 [    train.py:   81]:	Batch 8040 train-Loss 0.455643
[INFO] 2022-11-13 22:44:35,388 [    train.py:   81]:	Batch 8050 train-Loss 0.456534

100%|███████████████████████████████████████▊| 996/1000 [01:40<00:00,  9.86it/s][INFO] 2022-11-13 22:46:22,662 [multi_class.py:  150]:	Train Loss: 0.095118 Train Macro F1: 0.440330 Train Micro F1: 0.473333 
[INFO] 2022-11-13 22:46:22,710 [multi_class.py:  187]:			Test Loss: 0.124781 Test Macro F1: 0.224703 Test Micro F1: 0.367081 
100%|███████████████████████████████████████▉| 997/1000 [01:41<00:00,  9.88it/s][INFO] 2022-11-13 22:46:22,763 [multi_class.py:  150]:	Train Loss: 0.095118 Train Macro F1: 0.440330 Train Micro F1: 0.473333 
[INFO] 2022-11-13 22:46:22,812 [multi_class.py:  187]:			Test Loss: 0.124784 Test Macro F1: 0.224703 Test Micro F1: 0.367081 
100%|███████████████████████████████████████▉| 998/1000 [01:41<00:00,  9.88it/s][INFO] 2022-11-13 22:46:22,864 [multi_class.py:  150]:	Train Loss: 0.095117 Train Macro F1: 0.440330 Train Micro F1: 0.473333 
[INFO] 2022-11-13 22:46:22,913 [multi_class.py:  187]:			Test Loss: 0.124788 Test Macro F1: 0.224703 Test Micro F1: 0.367081 
100%|███████████████████████████████████████▉| 999/1000 [01:41<00:00,  9.89it/s][INFO] 2022-11-13 22:46:22,965 [multi_class.py:  150]:	Train Loss: 0.095116 Train Macro F1: 0.440344 Train Micro F1: 0.473373 
[INFO] 2022-11-13 22:46:23,013 [multi_class.py:  187]:			Test Loss: 0.124791 Test Macro F1: 0.224703 Test Micro F1: 0.367081 
100%|███████████████████████████████████████| 1000/1000 [01:41<00:00,  9.89it/s]
[INFO] 2022-11-13 22:46:23,014 [multi_class.py:  247]:	Best test macro f1 is 0.2269956056437573.

4.3node2vec多类别预测任务)

部分结果展示：

[INFO] 2022-11-13 23:01:59,675 [    train.py:   81]:	Batch 3950 train-Loss 0.569241
[INFO] 2022-11-13 23:02:01,468 [    train.py:   81]:	Batch 3960 train-Loss 0.569519
[INFO] 2022-11-13 23:02:03,191 [    train.py:   81]:	Batch 3970 train-Loss 0.569199
[INFO] 2022-11-13 23:02:04,906 [    train.py:   81]:	Batch 3980 train-Loss 0.570791
[INFO] 2022-11-13 23:02:06,510 [    train.py:   81]:	Batch 3990 train-Loss 0.569951
[INFO] 2022-11-13 23:02:08,249 [    train.py:   81]:	Batch 4000 train-Loss 0.570624
[INFO] 2022-11-13 23:02:09,876 [    train.py:   81]:	Batch 4010 train-Loss 0.567852
[INFO] 2022-11-13 23:02:11,495 [    train.py:   81]:	Batch 4020 train-Loss 0.570603

100%|███████████████████████████████████████▉| 997/1000 [01:42<00:00,  9.85it/s][INFO] 2022-11-13 23:03:59,728 [multi_class.py:  150]:	Train Loss: 0.096447 Train Macro F1: 0.352921 Train Micro F1: 0.471340 
[INFO] 2022-11-13 23:03:59,777 [multi_class.py:  187]:			Test Loss: 0.119648 Test Macro F1: 0.233598 Test Micro F1: 0.383243 
100%|███████████████████████████████████████▉| 998/1000 [01:42<00:00,  9.83it/s][INFO] 2022-11-13 23:03:59,830 [multi_class.py:  150]:	Train Loss: 0.096443 Train Macro F1: 0.352921 Train Micro F1: 0.471340 
[INFO] 2022-11-13 23:03:59,879 [multi_class.py:  187]:			Test Loss: 0.119651 Test Macro F1: 0.233497 Test Micro F1: 0.383210 
100%|███████████████████████████████████████▉| 999/1000 [01:42<00:00,  9.83it/s][INFO] 2022-11-13 23:03:59,932 [multi_class.py:  150]:	Train Loss: 0.096440 Train Macro F1: 0.352921 Train Micro F1: 0.471340 
[INFO] 2022-11-13 23:03:59,980 [multi_class.py:  187]:			Test Loss: 0.119654 Test Macro F1: 0.233497 Test Micro F1: 0.383210 
100%|███████████████████████████████████████| 1000/1000 [01:42<00:00,  9.84it/s]
[INFO] 2022-11-13 23:03:59,981 [multi_class.py:  247]:	Best test macro f1 is 0.2342214269132497.

4.4 结果对比

Dataset	model	Task	Metric	PGL Result
BlogCatalog	deepwalk	multi-label classification	MacroF1	0.2269
BlogCatalog	node2vec	multi-label classification	MacroF1	0.23422

这里使用默认的参数，需要调优一下，0.260最佳效果。.
更多详情参考：Paddle Graph Learning 图学习之图游走类模型[系列四]
https://aistudio.baidu.com/aistudio/projectdetail/5002782?contributionType=1