图嵌入算法
- 一、背景
- 1.提出
- 2.应用
- 3.特点
- 二、DeepWalk
- RandomWalk
- 三、node2vec
- 引言
- node2walk
- skip-gram(用中心词预测周围词)
一、背景
1.提出
①使用邻接矩阵表示网络时，由于矩阵中大多数元素是0，难以体现节点间关系，同时数据的稀疏性使得计算效率很低
②为此提出图嵌入算法：将图节点或子图以低维向量形式表达，供现有模型直接使用。
2.应用
①节点分类任务，预测网络中某节点最可能的标签。如社交网络：用户感兴趣对象；蛋白质网络：蛋白质功能
②边预测任务，预测网络中两节点是否应该相连。如社交网络：两用户是否朋友
3.特点
①节点的向量表达仅考虑节点间关系，没考虑节点本身特征
二、DeepWalk
RandomWalk
DeepWalk使用随机游走(RandomWalk)的方式在图中进行节点采样。
RandomWalk：给定当前访问起始节点，从其邻居中随机采样节点作为下一个访问节点，重复此过程，直到访问序列长度满足预设条件。原则是可重复访问已访问节点的深度优先遍历算法。
RandomWalk采样的过程：
①打乱顶点集合V
②自顶点vi开始在图G中进行步数为t的随机游走，得到游走序列Wvi=（vi,…,vj）
③窗口大小w，将序列Wvi输入SkipGram中用于训练隐藏层参数Φ
④重复上述过程，直到每一个vi都做过起始点
如下图：
选择如打乱集合中各个顶点后，先选择了顶点1，然后随机游走（即随机选择下一个定点），依次走到了3,1，5,…窗口大小就是游走序列的长度。顶点1游走完之后再从顶点2开始随机游走，依次走到了1,3，4,…。顶点2游走完之后再从顶点6开始游走，依次走到了1,5，1，…一直到所有顶点都作为起点游走过后，这时我们会得到顶点个数个长度为窗口大小的游走序列，然后用这些序列去训练。deepwalk和node2vec的不同之后在于游走的方法不同，而二者的序列训练方法基本相同，下面介绍node2vec
三、node2vec
引言
前文所介绍的DeepWalk获得游走序列是基于DFS邻域，基于BFS获得游走序列的是LINE。node2vec种综合考虑DFS邻域和BFS邻域的graph embedding方法。简单来说，node2walk可以看作是deepwalk的一种扩展，即结合了DFS和BFS随机游走的deepwalk。
注意：node2vec是利用node2walk获取的序列。deepwalk是利用randomwalk获取的序列。
node2walk
node2walk的游走策略（已经由节点t游走到节点v，下一步如何抉择），根据下面公式，计算出每个每个邻近节点的“值”，然后折算成概率，最后别名采样（alias sample）算法最终游走到的目标节点（p越小，embedding越倾向于表达同质性；q越小，embedding越倾向于表达结构性）
下图的含义是上一步在顶点t，当前在顶点v，下一步走到顶点x的“权重”。dtx=0,1,2分别表示下一步走回t，走到x1，走到x2或x3的权重。（对应距离上一步位置t与下一步位置x的距离分别是0,1，2）
skip-gram(用中心词预测周围词)
经过node2vec后，我们得到了若干序列，我们认为在同一个序列中出现的词之间是有关联的，所以我们希望用同一个序列中按照某个规则，两两取顶点，将一个顶点作为输入值，另一个顶点作为标签，经过神经网络训练后，取出网络中的某个矩阵，那个这个矩阵就是这些顶点的嵌入词向量，即能表示某个词，有了向量就能通过计算向量间距离来判断某两个顶点之间的距离（关系度）了。
假设网络中一共有1194个结点，算法的步骤为：
①对每个结点进行维数1194的独热编码
②初始化embedding矩阵，形状（1194,128）
③用一个batch的train_inputs(128,1194)点乘embedding矩阵，得到这些输入样本的嵌入词向量组成的矩阵embed(128,128)。
注意：embedding矩阵（嵌入图矩阵）是由所有词的嵌入词向量组成的。
如下图，左边是一个batch的train_inputs矩阵的一个行向量（1x1194），代表编号为3的顶点的独热编码。右边是embedding矩阵（1194x128），每一列对应一个顶点的嵌入词向量，那么运算结果为该顶点对应的嵌入词向量。那么用一个batch（设batch_size=128）的train_inputs矩阵点乘embedding矩阵，得到这些输入样本的嵌入词向量组成的矩阵embed(128,128)。
④初始化weights矩阵，形状（1194,128）以及biases（biases初始值0）
⑤用embed（128,128）点乘转置的weights（128,1194）并加上biases，得到隐藏层输出hidden_out（128,1194）
hidden_out的含义是这128个输入样本中每个样本对每个其他样本的相似度。
⑥128个标签组成了一个（128,1194）的矩阵labels
⑦用训练值hidden_out和标签值labels求损失，然后生成优化器
⑧经过迭代后，得到训练完成后的embedding(1194,128)，用每个结点的独热编码乘以该矩阵，得到的表示这个结点的嵌入词向量（128维）。
附上一段在某处看到的代码（我添加了注释）：
这段代码的作用是给一篇文章，然后输出与每个单词关联度最高的单词。
# 1.导入所依赖的库
import time
import collections
import math
import os
import random
import zipfile
import numpy as np
import urllib
import pprint
import tensorflow as tf
import matplotlib.pyplot as plt
os.environ["TF_CPP_MIN_LOG_LEVEL"] = "2"# 2.准备数据集url = "http://mattmahoney.net/dc/"def maybe_download(filename, expected_bytes):"""判断文件是否已经下载，如果没有，则下载数据集"""if not os.path.exists(filename):# 数据集不存在，开始下载# 按网址：http://mattmahoney.net/dc/text8.zip下载文件，同时以名字filename(在这里是text8.zip)保存在当前目录filename, _ = urllib.request.urlretrieve(url + filename, filename)# 有关函数urllib.request.urlretrieve的详解博客https://blog.csdn.net/pursuit_zhangyu/article/details/80556275# 核对文件尺寸stateinfo = os.stat(filename)# 有关系统stat调用的详细解释链接https://www.cnblogs.com/fmgao-technology/p/9056425.htmlif stateinfo.st_size == expected_bytes:print("数据集已存在，且文件尺寸合格！", filename)else :print(stateinfo.st_size)raise Exception("文件尺寸不对 !请重新下载，下载地址为："+url)return filename"""
测试文件是否存在
"""
filename = maybe_download("text8.zip", 31344016)# 3.解压文件def read_data(filename):# 有关zipfile模块的详细使用介绍博客https://www.cnblogs.com/ManyQian/p/9193199.htmlwith zipfile.ZipFile(filename) as f: # 提取压缩文件并用f表示该文件# 有关python中split()函数的详细解释博客https://www.runoob.com/python/att-string-split.htmldata = tf.compat.as_str(f.read(f.namelist()[0])).split() # 取压缩文件里面的第一个文件（索引为0）'''使用 zipfile.ZipFile（）来提取压缩文件，然后我们可以使用zipfile 模块中的读取器功能。首先，namelist（）函数检索该档案中的所有成员——在本例中只有一个成员，所以我们可以使用 0 索引对其进行访问。然后，我们使用 read（）函数读取文件中的所有文本，并传递给 TensorFlow 的 as_str 函数，以确保文本保存为字符串数据类型。最后，我们使用 split（）函数创建一个列表，该列表包含文本文件中所有的单词，并用空格字符分隔'''return datafilename = "text8.zip"
words = read_data(filename)
print("总的单词个数：", len(words))# 4.构建词汇表，并统计每个单词出现的频数，同时用字典的形式进行存储，取频数排名前50000的单词
vocabulary_size = 50000def build_dataset(words): # words是输入的原文count = [["UNK", -1]] # 这里不可以用unknown，因为原文中有unknown，所以会出错# collections.Counter()返回的是形如[["unkown",-1],("the",4),("physics",2)]count.extend(collections.Counter(words).most_common(vocabulary_size - 1))# 有关collection模块中counter类的详细解释链接http://www.pythoner.com/205.html# most_common()函数用来实现Top n 功能 即截取counter结果的前多少个子项# 对于列表的一些常见基本操作详细链接https://blog.csdn.net/ywx1832990/article/details/78928238# print(count[:10]) # 这时候count中存放的是频次前50000的单词以及它们出现的频次，其余的认为是unknown，频次为-1dictionary = {}# 将全部单词转为编号（以频数排序的编号），我们只关注top50000的单词，并记UNK编号为0，同时统计一下这类词汇的数量for word, _ in count:dictionary[word] = len(dictionary)# len(dictionary)是输出字典中元素个数，即键的个数# 开始时字典为空，len(dictionary)为0，第一个键是unknown，则有"unknown"：0# 第二个键是the,此时字典中只有一个元素，则有"the"：1# 形如：{"the"：1，"UNK"：0，"a"：12}# print(dictionary["UNK"])data = []unk_count = 0 # 准备统计top50000以外的单词的个数for word in words:# 对于其中每一个单词，首先判断是否出现在字典当中if word in dictionary:# 如果已经出现在字典中，则转为其编号index = dictionary[word]else:# 如果不在字典，则转为编号0index = 0unk_count += 1data.append(index) # data存放的是words即原文中所有单词对应的编号"""print(data[:10])[5234, 3081, 12, 6, 195, 2, 3134, 46, 59, 156]"""count[0][1] = unk_count # 将统计好的unknown的单词数，填入count中# 将字典进行翻转,形如：{3:"the",4:"an"}，字典翻转有很多方法，可以百度选择一种即可reverse_dictionary = dict(zip(dictionary.values(), dictionary.keys()))return data, count, dictionary, reverse_dictionary# 返回值意义分别是data:words即原文中所有单词对应的编号# count:二维数组，频次前50000的单词以及它们出现的频次，其余的认为是unknown，频次为-1，并放在第一个# dictionary：对count中内容按序编号# reverse_dictionary:翻转dictionary# 为了节省内存，将原始单词列表进行删除
data,count,dictionary,reverse_dictionary = build_dataset(words)
del words
# 将部分结果展示出来
# print("出现频率最高的单词（包括未知类别的）：",count[:10])
# 将已经转换为编号的数据进行输出，从data中输出频数，从翻转字典中输出编号对应的单词
# print("样本数据(排名)：",data[:10],"\n对应的单词",[reverse_dictionary[i] for i in data[:10]])# 5.生成Word2Vec的训练样本，使用skip-gram模式
data_index = 0def generate_batch(batch_size, num_skips, skip_window):""":param batch_size: 每个训练批次的数据量，8:param num_skips: 每个单词生成的样本数量，不能超过skip_window的两倍，并且必须是batch_size的整数倍,2:param skip_window: 单词最远可以联系的距离，设置为1则表示当前单词只考虑前后两个单词之间的关系，也称为滑窗的大小,1:return:返回每个批次的样本以及对应的标签"""global data_index # 声明为全局变量，方便后期多次使用# 使用Python中的断言函数，提前对输入的参数进行判别，防止后期出bug而难以寻找原因assert batch_size % num_skips == 0assert num_skips <= skip_window * 2batch = np.ndarray(shape=(batch_size), dtype=np.int32) # 创建一个batch_size大小的数组，数据类型为int32类型，数值随机labels = np.ndarray(shape=(batch_size, 1), dtype=np.int32) # 数据维度为[batch_size,1]span = 2 * skip_window + 1 # 入队的长度，左右滑窗大小+本身buffer = collections.deque(maxlen=span) # 创建双向队列。最大长度为span"""print(batch,"\n",labels)batch :[0 ,-805306368 ,405222565 ,1610614781 ,-2106392574 ,2721-,2106373584 ,163793]labels: [[ 0][-805306368][ 407791039][ 536872957][ 2][ 0][ 0][ 131072]]"""# 对双向队列填入初始值for _ in range(span):buffer.append(data[data_index])data_index = (data_index+1) % len(data)"""print(buffer,"\n",data_index) 输出：deque([5234, 3081, 12], maxlen=3)3"""# 进入第一层循环，i表示第几次入双向队列for i in range(batch_size // num_skips): # i:0->3target = skip_window # 定义buffer中第skip_window个单词是目标targets_avoid = [skip_window] # 定义生成样本时需要避免的单词，因为我们要预测的是语境单词，不包括目标单词本身，因此列表开始包括第skip_window个单词for j in range(num_skips): # j:0->1"""第二层循环，每次循环对一个语境单词生成样本，先产生随机数，直到不在需要避免的单词中，也即需要找到可以使用的语境词语"""while target in targets_avoid:target = random.randint(0, span-1)# print(target) # 找到2时退出一次，2作为可使用的语境词语。第二次for j时，只能找0,0作为可使用的语境词语。（0和2顺序可变）targets_avoid.append(target) # 因为该语境单词已经被使用过了，因此将其添加到需要避免的单词库中batch[i * num_skips + j] = buffer[skip_window] # 目标词汇 i=0时：0,1 i=1时:2,3 i=2时：4,5labels[i * num_skips + j, 0] = buffer[target] # 语境词汇# 此时buffer已经填满，后续的数据会覆盖掉前面的数据buffer.append(data[data_index])data_index = (data_index + 1) % len(data)# print(batch,labels)return batch, labels# 举例子看看是否正确
batch, labels = generate_batch(8, 2, 1)# for i in range(8):
# print("目标单词："+reverse_dictionary[batch[i]]+"对应编号为：".center(20)+str(batch[i])+" 对应的语境单词为: ".ljust(20)+reverse_dictionary[labels[i,0]]+" 编号为",labels[i,0])
"""
for i in range(8):print("目标单词："+reverse_dictionary[batch[i]]+"对应编号为：".center(20)+str(batch[i])+" 对应的语境单词为: ".ljust(20)+reverse_dictionary[labels[i,0]]+" 编号为",labels[i,0])
测试结果：
目标单词：originated 对应编号为： 3080 对应的语境单词为: as 编号为 12
目标单词：originated 对应编号为： 3080 对应的语境单词为: anarchism 编号为 5233
目标单词：as 对应编号为： 12 对应的语境单词为: originated 编号为 3080
目标单词：as 对应编号为： 12 对应的语境单词为: a 编号为 6
目标单词：a 对应编号为： 6 对应的语境单词为: as 编号为 12
目标单词：a 对应编号为： 6 对应的语境单词为: term 编号为 195
目标单词：term 对应编号为： 195 对应的语境单词为: of 编号为 2
目标单词：term 对应编号为： 95 对应的语境单词为: a 编号为 6
"""# 6.定义训练数据的一些参数
batch_size = 128 # 训练样本的批次大小
embedding_size = 128 # 单词转化为稠密词向量的维度
skip_window = 1 # 单词可以联系到的最远距离
num_skips = 1 # 每个目标单词提取的样本数# 7.定义验证数据的一些参数
valid_size = 16 # 验证的单词数
valid_window = 100 # 指验证单词只从频数最高的前100个单词中进行抽取
valid_examples = np.random.choice(valid_window, valid_size, replace=False) # 进行随机抽取
num_sampled = 64 # 训练时用来做负样本的噪声单词的数量# 8.开始定义Skip-Gram Word2Vec模型的网络结构
# 8.1创建一个graph作为默认的计算图，同时为输入数据和标签申请占位符，并将验证样例的随机数保存成TensorFlow的常数
graph = tf.Graph()
with graph.as_default():# 生成了一个占位符，这样申请位置对后面运算可以加速，此时还没有存东西# tf.placeholder()函数作为一种占位符用于定义过程，可以理解为形参，在执行的时候再赋具体的值。train_inputs = tf.compat.v1.placeholder(tf.int32, [batch_size]) # 128行，多少列未知，每一行都是独热编码train_labels = tf.compat.v1.placeholder(tf.int32, [batch_size, 1]) # 128行，1列valid_dataset = tf.constant(valid_examples, tf.int32) # 16行，多少列未知，valid_dataset是包含16个编号的数组# 选择运行的device为CPUwith tf.device("/cpu:0"):# 单词大小为50000，向量维度为128，随机采样在（-1，1）之间的浮点数embeddings = tf.Variable(tf.compat.v1.random_uniform([vocabulary_size, embedding_size], -1.0, 1.0)) #（50000,128）# 使用tf.nn.embedding_lookup()函数查找train_inputs对应的向量embed，根据索引选择对应的元素，避开了对输入值的独热，本篇仅对输出值独热embed = tf.nn.embedding_lookup(embeddings, train_inputs) # 根据train_inputs中的id号，寻找（独热编码与之点积）embeddings中的对应元素，（128,128），即输入的128个词的嵌入词向量。# 使用截断正太函数初始化权重,偏重初始化为0weights = tf.Variable(tf.compat.v1.truncated_normal([vocabulary_size, embedding_size], stddev=1.0 /math.sqrt(embedding_size))) # （50000,128）biases = tf.Variable(tf.zeros([vocabulary_size]))# 隐藏层实现hidden_out = tf.matmul(embed, tf.transpose(weights)) + biases # embed与转置后的weights点积，得到（128,50000）# 将标签使用one-hot方式表示，便于在softmax的时候进行判断生成是否准确train_one_hot = tf.one_hot(train_labels, vocabulary_size) # (128,50000),500000表示向量维度。根据train_labels的不同，在vocabulary_size中分配独热编码，每轮训练分配的都不一样# print(train_one_hot)cross_entropy = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(logits=hidden_out, labels=train_one_hot)) # 两个(128,50000)计算损失# 优化选择随机梯度下降optimizer = tf.compat.v1.train.GradientDescentOptimizer(1.0).minimize(cross_entropy)# 为了方便进行验证，采用余弦定理验证相似性 链接https://blog.csdn.net/u012160689/article/details/15341303# 归一化norm = tf.compat.v1.sqrt(tf.compat.v1.reduce_sum(tf.square(weights), 1, keepdims=True))normalized_embeddings = weights / norm # 这两行的目的是将embeddings的每行的向量归一化 (50000,128)valid_embeddings = tf.nn.embedding_lookup(normalized_embeddings, valid_dataset) # 根据这16个编号去查询验证归一化的单词嵌入向量，(16,128)# 计算验证单词的嵌入向量与词汇表中所有单词的相似性similarity = tf.matmul(valid_embeddings, normalized_embeddings, transpose_b=True # (16,50000)，这16个验证单词与所有50000个单词的相似性)init = tf.compat.v1.global_variables_initializer() # 因为tf中建立的变量是没有初始化的,执行init后便可开始定义参数的初始化# 9.启动训练
num_steps = 150001 # 进行15W次的迭代计算
t0 = time.time()
# 创建一个回话并设置为默认
with tf.compat.v1.Session(graph=graph) as session:init.run() # 启动参数的初始化print("初始化完成！")average_loss = 0 # 计算误差# 开始迭代训练for step in range(num_steps):batch_inputs, batch_labels = generate_batch(batch_size, num_skips, skip_window) # 调用生成训练数据函数生成一组batch和labelfeed_dict = {train_inputs: batch_inputs, train_labels: batch_labels} # 待填充的数据# 启动回话，运行优化器optimizer和损失计算函数，并填充数据# sess.run(函数名，feed_dict = {字典形式的给形参赋值})，这个时候才给，这是才开始往batch_inputs和batch_labels里面填充值，没run之前里面还没放值# 只是一个对应形状的占位符，所以若要直接获取值，则需要 matrix.eval()optimizer_trained, loss_val = session.run([optimizer, cross_entropy], feed_dict=feed_dict) # optimizer_trained没用，可以直接改为：_,loss_val=average_loss += loss_val # 统计NCE损失# 为了方便，每2000次计算一下损失并显示出来if step % 2000 == 0:if step > 0:average_loss /= 2000print('第%d轮迭代用时：%s' % (step, time.time() - t0))t0 = time.time()print("第{}轮迭代后的损失为：{}".format(step, average_loss))average_loss = 0# 每10000次迭代，计算一次验证单词与全部单词的相似度，并将于验证单词最相似的前8个单词呈现出来if step % 10000 == 0:sim = similarity.eval() # 把张量的值给算出来，否则里面是占位符# 从频次最高的100个单词里抽16个验证单词，并分别找出与这16个验证单词相似度最接近的8个单词for i in range(valid_size):valid_word = reverse_dictionary[valid_examples[i]] # 得到对应的验证单词top_k = 8# argsort()函数是将矩阵中的元素从小到大排列，提取其对应的index(索引)，然后输出到y。# 50000个值进行排序，本质上是根据相似度排序# -sim即把矩阵中的所有值变成负数，再从小到大排序，本质上是从大到小排序，取下标1到top_k+1，因为0是这个词本身，其余top_k个词是与这个词最接近的8个词的编号# 那么输入的8个词就是按相似度从大到小输出的了，如果用sim画，后面会面临顺序反了的问题nearest = (-sim[i, :]).argsort()[1:top_k+1] # 计算每一个验证单词相似度最接近的前8个单词# nearest = (sim[i, :]).argsort()[49991:49999] # 这时的nearest的顺序是相反的log_str = "与单词 {} 最相似的： ".format(str(valid_word))for k in range(top_k):close_word = reverse_dictionary[nearest[k]] # 相似度高的单词log_str = "%s %s, " % (log_str, close_word)print(log_str)final_embeddings = normalized_embeddings.eval() # 最终的嵌入词向量# 这里暂不了解
# 10.可视化Word2Vec效果def plot_with_labels(low_dim_embs, labels, filename = "tsne.png"):# assert是如果满足条件，则继续运行，否则抛出AssertionError错误assert low_dim_embs.shape[0] >= len(labels), "标签数超过了嵌入向量的个数！！"plt.figure(figsize=(20, 20))for i, label in enumerate(labels):x, y = low_dim_embs[i, :]plt.scatter(x, y)plt.annotate(label,xy = (x, y),xytext=(5, 2),textcoords="offset points",ha="right",va="bottom")plt.savefig(filename)
from sklearn.manifold import TSNE
tsne = TSNE(perplexity=30, n_components=2, init="pca", n_iter=5000)
plot_only = 100
low_dim_embs = tsne.fit_transform(final_embeddings[:plot_only, :])
Labels = [reverse_dictionary[i] for i in range(plot_only)]
plot_with_labels(low_dim_embs, Labels)
plt.show()
"""
第142000轮迭代后的损失为：4.46674475479126
第144000轮迭代后的损失为：4.460033647537231
第146000轮迭代后的损失为：4.479593712329865
第148000轮迭代后的损失为：4.463101862192154
第150000轮迭代后的损失为：4.3655951328277585
与单词 can 最相似的： may, will, would, could, should, must, might, cannot,
与单词 were 最相似的： are, was, have, had, been, be, those, including,
与单词 is 最相似的： was, has, are, callithrix, landesverband, cegep, contains, became,
与单词 been 最相似的： be, become, were, was, acuity, already, banded, had,
与单词 new 最相似的： repertory, rium, real, ursus, proclaiming, cegep, mesoplodon, bolster,
与单词 their 最相似的： its, his, her, the, our, some, these, landesverband,
与单词 when 最相似的： while, if, where, before, after, although, was, during,
与单词 of 最相似的： vah, in, neutronic, widehat, abet, including, nine, cegep,
与单词 first 最相似的： second, last, biggest, cardiomyopathy, next, cegep, third, burnt,
与单词 other 最相似的： different, some, various, many, thames, including, several, bearings,
与单词 its 最相似的： their, his, her, the, simplistic, dativus, landesverband, any,
与单词 from 最相似的： into, through, within, in, akita, bde, during, lawless,
与单词 would 最相似的： will, can, could, may, should, might, must, shall,
与单词 people 最相似的： those, men, pisa, lep, arctocephalus, protectors, saguinus, builders,
与单词 had 最相似的： has, have, was, were, having, ascribed, wrote, nitrile,
与单词 all 最相似的： auditum, some, scratch, both, several, many, katydids, two,
"""
