5. 图学习【参考资料 2】- 知识补充与 node2vec 代码注解

作者：汀丶

2022-11-15
浙江
本文字数：18389 字
阅读完需：约 60 分钟

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

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

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

1.1 Graph Embedding

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

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

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

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

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

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

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 模型实际上分为了两个部分：

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

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

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

我们在上面提到，训练模型的真正目的是获得模型基于训练数据学得的隐层权重。为了得到这些权重，我们首先要构建一个完整的神经网络作为我们的“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 论文提出了三个创新点：

将常见的单词组合（word pairs）或者词组作为单个“words”来处理。
对高频次单词抽样来减少训练样本的个数。
对优化目标采用“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)学习出一个网络的表示，在网络标注顶点很少的情况也能得到比较好的效果。随机游走起始于选定的节点，然后从当前节点移至随机邻居，并执行一定的步数，该方法大致可分为四个步骤：

图 a 展示了原始的用户行为序列。
图 b 基于这些用户行为序列构建了物品相关图，可以看出，物品 A，B 之间的边产生的原因就是因为用户 U1 先后购买了物品 A 和物品 B，所以产生了一条由 A 到 B 的有向边。如果后续产生了多条相同的有向边，则有向边的权重被加强。在将所有用户行为序列都转换成物品相关图中的边之后，全局的物品相关图就建立起来了。
图 c 采用随机游走的方式随机选择起始点，重新产生物品序列。
图 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_{i j}$ 是节点 $v_{i}$ 到节点 $v_{j}$ 边的权重。

如果物品相关图是无相无权重图，那么跳转概率将是上面公式的一个特例，即权重 $M_{i j}$ 将为常数 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 inlineimport matplotlib.pyplot as pltimport networkx as nx # networkx是一个常用的绘制复杂图形的Python包。import pgldef 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 的概率为

π_{V X} = α_{p q} (t, x) \cdot ω_{v x}

其中 $ω_{v x}$ 是边 vx 的权重， $α_{p q} (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_{t x}$ 指的是节点 $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 融合共同输入后续深度学习网络，以保留物品的不同特征信息。

结果展示：

[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 数据集的文件太多，所以这里略过了，如果需要或者感兴趣的话，可以从文末的连接进入查看。

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.1python -m pip uninstall pgl#install pgl 1.2.1python -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 结果对比

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

发布于: 刚刚阅读数: 3

汀丶

关注

还未添加个人签名 2022-01-06 加入

还未添加个人简介

发布

暂无评论

创作场景

5. 图学习【参考资料 2】- 知识补充与 node2vec 代码注解

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

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

1.1 Graph Embedding

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

1.2 词语嵌入方法(word2vec)

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

1.1.2 Negative Sampling——负采样

1.1.3 应用到图嵌入领域

2.DeepWalk（原理+实践）

2.1 节点嵌入方法（Node embeddings）

2.2 DeepWalk 代码实现

3. node2vec（原理+实践）

3.1 node2vec 原理

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

4.1 数据集介绍

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

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

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

4.1.4 ArXiv

4.1.5 下载地址

4.2deepwalk(多类别预测任务)

4.3node2vec 多类别预测任务)

4.4 结果对比

汀丶

评论