图上 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 nx
import numpy as np
import os
import pandas as pd
import tensorflow.compat.v1 as tf
import time
import itertools
import math
import pandas as pd
import random
from joblib import Parallel, delayed
tf.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.0
print(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_map
print(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=2
all_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=10000
embedding_size=16
batch_size = 4
skip_window = 2
num_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官方完成 github.com/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 = 1
learning_rate = 0.1
def 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文件 里，就能够 完美运转起来 。本文的代码是一个 小型的商业能够用的工程项目 ，希望能够对你有 参阅作用 ～
码字不易，觉得有收获就动动小手转载一下吧，你的支撑是我写下去的最大动力 ～
更多更全更新内容，欢迎重视作者的大众号： 算法全栈之路
