图上 deepwalk 算法理论与实战，图算法之瑞士军刀篇(一)

书接上文, 在 图机器学习算法 开篇 的 一文揭开图机器学习的面纱，你确定不来看看吗 和 graphSage还是HAN ？吐血力作综述Graph Embeding 经典好文 这两篇文章中，我们均有说到： 近两年的 图表示学习 ，从分类上又可以大致把分成2类： 基于游走的图结构表示学习 和 基于卷积的图深度表示学习。

关注了 作者公众号 的同学 应该清楚，从 前面的 一系列文章中，我们已经 分别介绍了 同/异构图 上的 节点分类与回归 、边分类与回归 、链接预测 等任务，这些其实都可以把归结为 基于卷积的图深度表示 学习。而基于游走的图结构表示学习，一直没有介绍过。

基于 图游走的表示 学习，最 经典 的 莫过于 deepwalk 以及 node2vector 这两种算法。它们应该算是图游走算法 的 开山鼻祖 之作。尽管后来 有了更多各种变种 的 优化算法，但是 万变不离其宗 ，算法设计的 基础思想 都是 一脉相承 的。下面 就让我们开始本文的学习吧～

(1) deepwalk 基础理论介绍

前文我们已经明白了：deepwalk算法 是一种基于图游走训练得到图表示的算法。 图游走，顾名思义，在图上进行游走，获得一系列的游走路径，其实也就是节点序列。再把这些序列丢到word2vec 模型里去，得到节点的embeding ，进行下游别的辅助任务。概括来说，图游走算法一般都遵从的是 Walk + Skip-Gram Loss 架构。

在 深入浅出理解word2vec模型 (理论与源码分析) 文章中，我们也说明过： 输入word2vec模型的 序列非常重要，决定着我们训练得到的embeding的重点 。 具体到图上，对于 同构图 而言，我们可以进行 无偏游走 ，就像 random walk (随机游走) 和 node2vec 的 带倾向游走 (局部探索与全局探索的侧重与融合) 。

在 异构图 上，我们可以采用 graphSage还是HAN ？吐血力作综述Graph Embeding 经典好文 文章中介绍的 metapath 的 节点采样 方法，进行 有偏游走 。

记得 阿里巴巴 以前有一篇论文介绍了 EGES (Enhanced Graph Embedding with Side Information) 算法，其中用到了 side information 来 有效缓解 商品的 冷启动 问题。所谓 side information ，顾名思义，也就是对于商品而言，求某个 item embeding 的时候，不光考虑 itemid , 也要考虑到 该item 对应的 其他的信息，例如 商品 的一级类别，二级类别 等 属性与分类信息。

对应到本文，当我们 基于游走采样到节点序列 之后，对于序列中的每一个itemid, 找到对应的附属属性的id ,然后分别求得该 itemid + side_information 的多个 embeding , 融合到一起作为当前 iitemid 对应的embedding, 去丢到skip gram 损失loss 里进行上下文的itemid 的预测。 这不就是 EGES 算法的一种非常好的实现吗，niubility !!!

得到游走路径之后，直接把 采样到的节点序列 丢入到 word2vec 之一的 skip gram 模型中去训练即可。在前面专门介绍 word2vec 的文章中，我们分析了 skip gram 和 cbow 这两种模型的优劣和异同，曾经分析过：CBOW 是公共课，Skip-gram 是私教 。

对于 互联网 这种 用户或则itemId 这一类 比较稀疏 的节点，显然 skip gram 的效果是比 cbow效果要好 ，并且工业实践也证明事实如此，所以一般 的做法是: 将图上游走采样得到的节点序列丢入到 skip gram 模型中进行训练 。

对于 长期从事 算法工程师 工作的同学来说，图游走算法理论比较简单，但是效果也是非常好用的，很多企业 在才开始 进行 图算法尝试 的时候，都是从 本文介绍的 deepwalk 开始的，然后 后面经过 很多优化，发觉效果 还不如 deepwalk ^-^ 。因为其简单好用，所以 deepwalk 可以称之为 图算法系列 中的 瑞士军刀 了 。

闲言少叙，下面就让我们开始本文的代码部分吧～

(2) 代码时光

因为作者 以前的 工作经验 ，很长时间都是使用的 tensorflow 1.0 的版本 ，所以本文的模型部分也采用 tensorflow 1.0 版本来进行开发。

在下一篇文章中，我们会采用 tensorflow 2.0 keras 的版本进行开发，并结合 keras 的预处理接口进行节点采样 ，对tensorflow 2.0 感兴趣的同学，欢迎关注下一篇文章哈。

老规矩， 开篇先吼一嗓子 ， talk is cheap , show me the code !!!

本文的代码讲的是 基于 tensorflow 1.0 实现的 deepwalk 算法 ，整个源码流程是一个 小型的工业可用的工程，觉得有用赶紧 收藏 转发 吧 ～

(2.1) 导包

首先导包，把代码跑起来，仅仅需要这些python 包就可以了。

@ 欢迎关注作者公众号 算法全栈之路import networkx as nximport numpy as npimport osimport pandas as pdimport tensorflow.compat.v1 as tfimport timeimport itertoolsimport mathimport pandas as pdimport randomfrom joblib import Parallel, delayedtf.compat.v1.disable_eager_execution()

这里需要注意的是： 我本机安装的 tensorflow 2.6 的版本 ，而这里代码是用的 tensorflow 1.X 系列，所以 我导入的 tf 是 import tensorflow.compat.v1 as tf 。其中，下文有用到placeholder, 所以 记得 关掉 eager 模式，使用代码 tf.compat.v1.disable_eager_execution()。

这里的 图没在使用 dgl 实现，而是用的是 networkx 这个包，简单好用，快速上手～

(2.2) 数据准备

注意，我们这里的代码适用于 同构图，当然你用同构图来处理异构图问题也是可以的，也许 效果更好 呢 ～

@ 欢迎关注作者公众号 算法全栈之路graph_df = pd.DataFrame([['Tom', 'pig',], ['Nancy', 'Tom'], ['Jack', 'Nancy']], columns=['src', 'dst'], index=['0', '1', '2'])graph_df['weight']=1.0print(graph_df)

这里的 节点都是 同一类型 ，基于 某一个关系 构建的 边，这里 pandas 的 dataframe 是 保存的 边的 src 和 dst ，以及 该边对应的权重 ，weight 我们都把设置为 1.0 即可。

（2.3） 同构图节点编码

老规矩，图节点嘛，进行编码, 数字化后 扔到 图框架 里去。

@欢迎关注微信公众号：算法全栈之路#编码方法def encode_map(input_array):    p_map={}    length=len(input_array)    for index, ele in zip(range(length),input_array):        # print(ele,index)        p_map[str(ele)] = index    return p_map#解码方法def decode_map(encode_map):    de_map={}    for k,v in encode_map.items():        # index,ele         de_map[v]=k    return de_mapprint(type(graph_df['src'].values))# 构建 encode/ decode map node_encode_map=encode_map(set(np.append(graph_df['src'].values, graph_df['dst'].values, axis=0)))node_decode_map=decode_map(node_encode_map)print(len(node_encode_map))# 应用编码graph_df['src_node_encoded'] = graph_df['src'].apply(lambda e: node_encode_map.get(str(e),-1))graph_df['dst_node_encoded'] = graph_df['dst'].apply(lambda e: node_encode_map.get(str(e),-1))print(graph_df)

这里的代码非常通俗易懂，我就不再赘述了。

（2.4） networkx 构图

@欢迎关注微信公众号：算法全栈之路G = nx.from_pandas_edgelist(graph_df, 'src_node_encoded', 'dst_node_encoded', ['weight'])print(G)

这里 应用 networkx 进行 内存里逻辑图 的构建。 可以从 pandas 以及多种 数据源 构建，感兴趣的 下去 自行百度 哈 ～

（2.5） random walk 游走算法采样

这里是 算法非常重要 的一块，使用 随机游走算法 random walk 在图上进行节点采样 ，看代码 ～

@欢迎关注微信公众号：算法全栈之路def partition_num(num, workers):    if num % workers == 0:        return [num//workers]*workers    else:        return [num//workers]*workers + [num % workers]    class RandomWalker:    def __init__(self, G):        """        :param G:        """        self.G = G                def deepwalk_walk(self, walk_length, start_node):        walk = [start_node]        while len(walk) < walk_length:            cur = walk[-1]            cur_nbrs = list(self.G.neighbors(cur))            if len(cur_nbrs) > 0:                walk.append(random.choice(cur_nbrs))            else:                break                    return walk    def simulate_walks(self, num_walks, walk_length, workers=1, verbose=0):        """        :param num_walks: random walks 的次数 (每次都要遍历所有 node )        :param walk_length: 每次 random walk 最大长度        :param workers: 进程数        :param verbose:        :return:        """        G = self.G        nodes = list(G.nodes())        # 并行分区数，        results = Parallel(n_jobs=workers, verbose=verbose, )(            delayed(self._simulate_walks)(nodes, num, walk_length) for num in            partition_num(num_walks, workers))                walks = list(itertools.chain(*results))                # 串行采样路径         # walks= self._simulate_walks(nodes,num_walks,walk_length)        print("walks_len:",len(walks))        return walks        def _simulate_walks(self, nodes, num_walks, walk_length,):        walks = []        for index in range(num_walks):            # 对每一轮            random.shuffle(nodes)            for v in nodes:                walks.append(self.deepwalk_walk(walk_length=walk_length, start_node=v))                        return walks    # 随机游走算法调用     walker = RandomWalker(G)session_reproduce = walker.simulate_walks(num_walks=6, walk_length=3, workers=2,verbose=1)

这里，我们提供了 并行和串行游走 2种方法，注意 看 上文 的 代码注释 。如果 图数据量比较大 ，建议使用 python多线程 进行 路径游走节点采样 哈。

注意： 这里的 session_reproduce 本身就是返回的结果，就是一个 二维数组，数组里每一个元素就是一次采样返回的节点序列，也就是一个路径。

（2.6） skip gram 样本构造

无论在何时，样本构造 都是非常重要的～

@欢迎关注微信公众号：算法全栈之路window_size=2all_pairs = []session_reproduce = list(filter(lambda x: len(x) > 2, session_reproduce))for k in range(len(session_reproduce)):        for i in range(len(session_reproduce[k])):            for j in range(i - window_size, i + window_size + 1):                if i == j or j < 0 or j >= len(session_reproduce[k]) or session_reproduce[k][i] == session_reproduce[k][j]:                    continue                else:                    all_pairs.append([session_reproduce[k][i], session_reproduce[k][j]])                    np.savetxt('./all_pairs.csv', X=np.array(all_pairs, dtype=np.str), fmt="%s", delimiter="\t")

这里，我们将 路径长度小于等于2 的 路径过滤掉。然后 对每一条路径，以当前路径上每一个节点为中心，分别向前向后取 window_size 个元素构成正样本 。 二维数组的某一个元素即为某一个节点的index。最后保存的文件为word2vec 模型输入文件里的 center_word 和 target_word 这样的pair对。

注意： 这里产生的，均为正样本，负样本在下游全局采样得到。

(2.7) 模型构建

这里就是模型的主要结构了，word2vec里的 skip gram 模型。

@欢迎关注微信公众号：算法全栈之路# batch_size是要在单个批次中输入算法的目标和上下文单词对的数量# embedding_size是每个单词的单词向量或嵌入的维度# ptb.skip_window是在两个方向上的目标词的上下文中要考虑的词的数量# n_negative_samples是由 NCE 损失函数生成的负样本数 vocabulary_size=10000embedding_size=16 batch_size = 4skip_window = 2num_sampled = 2# train_inputs中的就是中心词，train_label中的就是语料库中该中心词在滑动窗口内的上下文词。train_inputs = tf.compat.v1.placeholder(tf.int32, shape=[batch_size])train_labels = tf.compat.v1.placeholder(tf.int32, shape=[batch_size, 1])# embddings是词嵌入，就是要学习的词向量的存储矩阵。共有词汇表大小的行数，每一行对应一个词的向量。embeddings = tf.Variable(tf.random_uniform([vocabulary_size, embedding_size], -1.0, 1.0))embed = tf.nn.embedding_lookup(embeddings, train_inputs)nce_weights = tf.Variable(tf.truncated_normal([vocabulary_size, embedding_size],stddev=1.0 / math.sqrt(embedding_size)))    nce_biases = tf.Variable(tf.zeros([vocabulary_size]))# 注意这里用的 tf.nn.nce_loss 是用于skip gram 模型的损失。loss = tf.reduce_mean(            tf.nn.nce_loss(                weights=nce_weights,                biases=nce_biases,                labels=train_labels,                inputs=embed,                num_sampled=num_sampled,                num_classes=vocabulary_size))

对于 word2vec 模型，相比大家都已经非常熟悉了，不熟悉的同学，可以去 深入浅出理解word2vec模型 (理论与源码分析) 去阅读了解一下。在 这篇文章 中，对于 采样进行了详细的设计说明 ，可以具体到 以什么尺度 什么方式对负样本进行采样 ，结合 文章介绍的理论 ，相信会对你的 学习与工作 有所帮助的 ～

这里需要 强调的是 tf.nn.nce_loss 这个loss，和以前 word2vec文章 介绍的不同： 这个损失隐含着帮你进行负采样的操作，而用户不用自己再去进行负采样了 。

提到 tf.nn.nce_loss ，就不得不提到 sampled softmax loss。 nce loss 和 sampled softmax loss 的出发点是一致, 都是想使得模型输出 。它们的不同点在于： sampled softmax loss 只支持 Single-Label 分类，而 nce loss 支持 Multi-Label 分类 。候选类别子集 由 采样类别 和 真实类别 组成。实际输入的标签为正样本，而负样本则是采样得到。

对于 tf.nn.nce_loss 函数，在 sampled_values 这个参数没有传递的时候 sampled_values=None ，即默认情况下，他会用 log_uniform_candidate_sampler 去采样。

当初作者 在用这个 模型 的时候，word2vec 的代码实现 主要参考了 tensorflow官方实现 ，这中间默认就是使用了 log_uniform_candidate_sampler 这个采样函数。

更 通俗的说，TF的word2vec实现 里所用的 负采样函数 的基础逻辑就是：词频越大，词的类别编号也就越大。因此，在TF的word2vec里，负采样的过程其实就是 优先采词频高的词作为负样本 。在 word2vec 原始论文中, 是 c++ 实现的 word2vec , 其中的 负采样逻辑 就是按照 热门度的0.75次方 采样的，这个和 TF的实现 有所区别，但大概的 意思差不多，一个item 越热门，越有可能成为负样本 。

感兴趣的同学可以去阅读 上面地址 的 官方源码 哈 ～

（2.8）数据批量生成与模型训练

终于要开始模型训练了，go !!!

@欢迎关注微信公众号：算法全栈之路all_pairs = np.loadtxt('./all_pairs.csv', dtype=np.long, delimiter='\t')all_pairs_df=pd.DataFrame(all_pairs, columns=["src", "dst"])center_word=all_pairs_df["src"].tolist() context_label=all_pairs_df["dst"].tolist()n_epochs = 1learning_rate = 0.1def generate_sample(df):    pair_list =[]    for index, row in df.iterrows():        center= getattr(row,'src')        target = getattr(row,'dst')        pair_list.append([center,target])    all_pairs = np.array(pair_list)    return all_pairs        def get_batch(pair, batch_size,num_features=1):    while True:        start_idx = np.random.randint(0, len(pair) - batch_size)        batch_idx = np.array(range(start_idx, start_idx + batch_size))        batch_idx = np.random.permutation(batch_idx)  # 生成随机序列        batch = np.zeros((batch_size), dtype=np.int64)        labels = np.zeros((batch_size, 1), dtype=np.int64)        # 这里有大坑等着         batch[:] = pair[batch_idx,0]        labels[:, 0] = pair[batch_idx, 1]        yield batch, labels        pair_all = generate_sample(all_pairs_df)batch_gen = get_batch(pair_all,BATCH_SIZE)optimizer = tf.train.GradientDescentOptimizer(LEARNING_RATE).minimize(loss)with tf.Session() as sess:        sess.run(tf.global_variables_initializer())        total_loss = 0.0  # we use this to calculate the average loss in the last SKIP_STEP steps0        for index in range(NUM_TRAIN_STEPS):            centers, targets = next(batch_gen)            # print("hh:", centers.shape, "xxx:", targets.shape)            train_dict = {train_inputs: centers, train_labels: targets}            _, loss_batch = sess.run([optimizer, loss], feed_dict=train_dict)            total_loss += loss_batch            if (index + 1) % SKIP_STEP == 0:                print('Average loss at step {}: {:5.1f}'.format(                    index, total_loss / SKIP_STEP))                total_loss = 0.0

这里，就是将 上面的 正样本 输入模型进行 训练 的过程了。

这里 隐藏了一个坑 就是 生成batch 数据 的过程，batch数据格式会和 模型的输入相辅相成，不然会因为batch 导致报模型结构的错误 。

以前 写模型 老用 tensorflow 的 dataset 集合keras 或则 estimator 接口 来使用，突然来个 pandas 和 tensorflow 1.0版本 的代码，确实各种坑 ！！ 真是坑了爹了，为了写这个 demo , 为难我这个工作了好几年的算法老同志！！ ，当然，现在 上面的这个 demo 是可以完美运行的。

剩下的就是 模型的训练 了，常规代码，我就不在进行赘述了。

最后代码 跑起来 就是这个样子：

到这里，图上 deepwalk 算法理论与实战，图算法之瑞士军刀篇(一) 的全文就写完了。 上面的 代码demo 在环境没问题的情况下，全部复制到一个 python文件 里，就可以 完美运行起来 。本文的代码是一个 小型的商业可以用的工程项目 ，希望可以对你有 参考作用 ～

码字不易，觉得有收获就动动小手转载一下吧，你的支持是我写下去的最大动力 ～

更多更全更新内容 ： 算法全栈之路

- END -