Task05 DeepWalk论文精读

1 DeepWalk简介

1.1 相关概念

• DeepWalk首要将Graph的每一个节点编码成一个D维向量，Embedding中隐式包括了Graph中的社群、衔接、结构信息，可用于后续节点分类等下游使命

• Embedding：例如Word2Vec，将单词转化为词向量，保留单词的语义联系

• 图嵌入：将节点空间编码成向量空间

• 图嵌入的运用：MNIST手写数字数据集的神经网络编码后降维可视化、修建图画数据集VGG编码后降维可视化

1.2 Word2Vec词向量、词嵌入

假定：相邻单词应该具有类似的Embedding。

• CBOW（接连词袋使命）：输入周围词猜测中心词
• Skip-Gram：输入中心词猜测周围词

运用上述两个方法，结构自监督的使命，能够编码成词向量

1.3 随机游走Ramdom Walk

• 假定：相邻节点应该具有类似的Embedding
• 随机游走：有一个醉汉在节点中游走，构成随机游走序列

1.4 官方PPT解说

• 机器学习的第一步需要提取图特征，得到节点、衔接，转换为邻接矩阵，能够进行降维操作

• 长处：

  • 不需要重新练习，只需要输入新节点和新衔接联系，再进行增量练习
  • 能够套用NLP
  • 练习效果很好

• 言语模型：运用Word2Vec将词变成词向量

• Short random walks = sentences

• Deepwalk步骤：

  1. 输入图
  2. 随机游走，采样随机游走序列
  3. 用随机游走序列练习成Word2Vec
  4. 运用Softmax（霍夫曼编码数）
  5. 得到节点的图嵌入向量表明

Deepwalk具体步骤：

1. Random Walks：生成 \gamma 条随机游走序列，每个随机游走序列长度为$t$
2. Representation Mapping：结构Skip-gram使命，输入中心词猜测周围词Pr(vj∣(vi))Pr(v_j|\Phi(v_i))Pr(vj​∣(vi​))
3. Hierarchical Softmax：运用霍夫曼树，输入节点的嵌入表明，进行逻辑二分类
4. Learning：需要两个参数，每一个节点的嵌入表、二分类的权重

• 改进办法：
  • Steaming：不需要知道全图数据
  • Non-Random Walks：能够选用不同办法，能够不选用随机

1.5 DeepWalk总结

• 首个将深度学习和自然言语处理的思维用于图机器学习
• 在稀少标示节点分类场景下，嵌入性能杰出
• 均匀随机游走，没有倾向的游走方向
• 需要很多随机游走序列练习
• 根据随机游走，管中窥豹，距离较远的两个节点无法相互影响。看不到全图信息。
• 无监督，仅编码图的衔接信息，没有运用节点的属性特征。
• 没有真实用到神经网络和深度学习

2 论文精读

论文标题：《DeepWalk：Online Learning of Social Representations》（DeepWalk：用于图节点嵌入的在线机器学习算法）

2.1 摘要

• DeepWalk用于学习隐式表征的表明学习方法，将节点在图中的衔接联系进行编码，构成稠密低维接连的向量空间，可用于统计机器学习
• 在多类别网络分类使命上体现不错，例如BlogCatalog、Flickr和YouTube
• DeepWalk根据随机游走的，适用于稀少标示的场景

2.2 介绍

• 布景：传统机器学习在稀少性的数据上很难进行处理
• DeepWalk能够经过随机游走序列（邻域信息和社群信息），学习网络的衔接结构信息，将节点转换为向量
• DeepWalk能用在标示数据稀少的场景中，能够结合线性分类器，具备并行加快能力
• 贡献：
  1. DeepWalk能够经过随机游走序列，学习节点在网络中的相关和规律
  2. 在多个节点分类数据集上，DeepWalk在标示数据稀少场景下能进步5%~10%
  3. 可扩展性非常好，能够适用在YouTube数据集上

2.3 问题定义

• 假定：图$G=(V,E)$，其间$E\subseteq (VV)$，GL=(V,E,X,Y)G_L=(V, E, X, Y)GL​=(V,E,X,Y)表明带标示的交际网络，$Y$表明标签
• 用随机游走序列采样衔接信息，避免迭代发生的误差累计问题
• 目标：经过反映衔接信息的Embedding和反映节点自身的特征，进行学习XE∈R∣V∣dX_E \in R^{|V| \times d}XE​∈R∣V∣d数据集，结合简单的机器学习算法，解决分类问题。

2.4 学习表明

• 特性：

  1. 灵敏可变、弹性扩容（Adaptability）
  2. 反映社群聚类信息（Community aware）：原图中附近的节点嵌入后依然附近
  3. 低维度（Low dimensional）：低纬度嵌入能够避免过拟合
  4. 接连（Continuous）：细微改变会发生影响

• 随机游走：从viv_ivi​点开始，经过随机过程，得到随机游走序列Wvi1,Wvi2,…,WvikW_{v_i}^1, W_{v_i}^2, \dots, W_{v_i}^kWvi​1​,Wvi​2​,…,Wvi​k​；能够运用并行方法，在线增量进行随机游走。

• 幂律分布：在一个无标度网络中，中枢节点的衔接数远高于其他节点，会发生长尾现象，也称为Zipf定律（词频排序名次与词频成正比，只有极少数的词被经常运用）

• 言语模型：用前i-1个词猜测下文的第i个词，经过Pr(vi∣(v1,v2,⋯ ,vi−1))Pr(v_i|(v_1, v_2, \cdots, v_{i-1}))Pr(vi​∣(v1​,v2​,⋯,vi−1​))，运用提取Embedding的函数:v∈V↦R∣V∣d\Phi:v \in V \mapsto R^{|V| \times d}:v∈V↦R∣V∣d，可表明用前$i-1$个节点的Embedding猜测第$i$个节点

• 用周围上下文猜测中心词（CBOW），用中心词猜测周围词（Skip-Gram），可构建自监督学习场景

• DeepWalk（Skip-Gram）丢失函数：

其间

• DeepWalk能够把节点编码成低维、稠密、接连的向量，包括节点的结构、衔接、社群特征，虽然不包括类别信息，但可用于猜测类别信息

2.5 算法

1. DeepWalk算法：$\text{DeepWalk}(G,w,d,,t)$

Input： graph $G(V,E)$
window size $w$（左右窗口宽度）
embedding size $d$（Embedding维度）
walks per vertex \gamma（每个节点作为开始节点生成随机游走的次数）
walk length $t$（随机游走最大长度）
Output： maxtrix of vertex representations ∈R∣V∣d\Phi \in R^{|V| \times d}∈R∣V∣d
1: Initialization: Sample \Phi from U∣V∣d\mathcal{U}^{|V| \times d}U∣V∣d
2: Build a binary Tree $T$ from $V$
3: for $i=0$ to \gamma do
4:  $\mathcal{O}=\text{Shuffle}(V)$ （随机打乱节点次序）
5:  for each vi∈Ov_i \in \mathcal{O}vi​∈O do （遍历graph中的每个点）
6:   Wvi=RandomWalk(G,vi,t)\mathcal{W}_{v_i} = \text{RandomWalk}(G, v_i, t)Wvi​​=RandomWalk(G,vi​,t) （生成一个随机游走序列）
7:   SkipGram(,Wvi,w)\text{SkipGram}(\Phi, \mathcal{W}_{v_i}, w)SkipGram(,Wvi​​,w) （由中心节点Embedding猜测周围节点，更新Embedding）
8:  end for
9: end for

2. SkipGram算法：SkipGram(,Wvi,w)\text{SkipGram}(\Phi, \mathcal{W}_{v_i}, w)SkipGram(,Wvi​​,w)

1: for each vi∈Wviv_i \in \mathcal{W}_{v_i}vi​∈Wvi​​ do（遍历当时随机游走序列的每个字节）
2:  for each uk∈Wvi[j−w,j+w]u_k \in \mathcal{W}_{v_i}[j-w, j+w]uk​∈Wvi​​[j−w,j+w] do（遍历该节点周围窗口里的每个点）
3:   J()=−log⁡Pr(uk∣(vj))J(\Phi)=-\log \text{Pr}(u_k | \Phi(v_j))J()=−logPr(uk​∣(vj​))（核算丢失函数）
4:   =−∗∂J∂\displaystyle \Phi = \Phi – \alpha * \frac{\partial J}{\partial \Phi}=−∗∂∂J​（梯度下降更新Embedding矩阵）
5:  end for
6: end for

3. 分层Sofmax（Hierachical Softmax）

核算公式：

4. 多线程异步并行：加快练习，性能不变

• 变种：
  • Streaming：在不知道全图时，直接用采样出的随机游走练习Embedding
  • Non-random walk：不随机的自然游走

2.6 评价目标

• TRT_RTR​表明有标示数据的份额
• Macro-F1\text{Macro-}F_1Macro-F1​：将每一类的F1F_1F1​取平均
• Micro-F1\text{Micro-}F_1Micro-F1​：用整体的TP、FN、FP、TN核算F1F_1F1​

2.7 相关工作

1. 该算法经过机器学习得到的，而非人工统计结构得到的
2. 该算法是无监督的，不考虑节点的label信息，只靠graph衔接信息
3. 在线学习，仅运用graph的局部信息
4. 将无监督学习（深度学习）运用在图上

• DeepWalk将自然言语处理推广到了图，把随机游走序列作为特别的句子，把节点作为特别的单词，言语模型是对不可见的隐式Graph建模，对于可见Graph的剖析方法能够促进非可见Graph的研讨

3 代码实战

3.1 导入工具包

import networkx as nx
import pandas as pd
import numpy as np
import random
from tqdm import tqdm
import matplotlib.pyplot as plt
%matplotlib inline
plt.rcParams['font.sans-serif']=['SimHei']  # 用来正常显现中文标签  
plt.rcParams['axes.unicode_minus']=False  # 用来正常显现负号

3.2 加载维基百科词条数据，并构建无向图

df = pd.read_csv("data/wiki/seealsology-data.tsv", sep = "\t")
df.head()

# 构建无向图
G = nx.from_pandas_edgelist(df, "source", "target", 
                            edge_attr=True, create_using=nx.Graph())

# 生成随机游走节点序列的函数
def get_randomwalk(node, path_length):
    '''
    输入开始节点和途径长度，生成随机游走节点序列
    '''
    random_walk = [node]
    for i in range(path_length-1):
        # 汇总邻接节点
        temp = list(G.neighbors(node))
        temp = list(set(temp) - set(random_walk))    
        if len(temp) == 0:
            break
        # 从邻接节点中随机选择下一个节点
        random_node = random.choice(temp)
        random_walk.append(random_node)
        node = random_node
    return random_walk

all_nodes = list(G.nodes())

# 每个节点作为开始点生成随机游走序列个数
gamma = 10 
# 随机游走序列最大长度
walk_length = 5 

# 生成随机游走序列
random_walks = []
for n in tqdm(all_nodes):
    # 将每个节点作为开始点生成gamma个随机游走序列
    for i in range(gamma): 
        random_walks.append(get_randomwalk(n, walk_length))

100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 8560/8560 [00:00<00:00, 14216.12it/s]

len(random_walks)

85600

3.3 练习Word2Vec模型

# 导入自然言语处理包
from gensim.models import Word2Vec

model = Word2Vec(
    vector_size=256, # Embedding维数
    window=4, # 窗口宽度
    sg=1, # Skip-Gram
    hs=0, # 不加分层softmax
    negative=10, # 负采样
    alpha=0.03,  # 初始学习率
    min_alpha=0.0007, # 最小学习率
    seed=14 # 随机数种子
)

# 用随机游走序列构建词汇表
model.build_vocab(random_walks, progress_per=2)

# 练习Word2Vec模型
model.train(random_walks, total_examples=model.corpus_count, epochs=50, report_delay=1)

(16581624, 16586750)

# 检查某个节点的Embedding
model.wv.get_vector('random forest').shape

(256,)

# 找类似词语
model.wv.similar_by_word('decision tree')

[('decision list', 0.6669241786003113), ('decision tree model', 0.6467953324317932), ('behavior tree (artificial intelligence, robotics and control)',  0.6441066265106201), ('decision stump', 0.6315082907676697), ('comparison sort', 0.6225860118865967), ('behavior trees (artificial intelligence, robotics and control)',  0.6196629405021667), ('minimum spanning tree', 0.6157709956169128), ('drakon', 0.6057607531547546), ('goal structuring notation', 0.6029132008552551), ('self-documenting code', 0.5985974073410034)]

3.4 PCA降维可视化

X = model.wv.vectors

# 将Embedding用PCA降维到2维
from sklearn.decomposition import PCA
pca = PCA(n_components=2)
embed_2d = pca.fit_transform(X)

plt.figure(figsize=(10,10))
plt.scatter(embed_2d[:, 0], embed_2d[:, 1])
plt.show()

# 核算PageRank重要度
pagerank = nx.pagerank(G)
# 从高到低排序
node_importance = sorted(pagerank.items(), key=lambda x:x[1], reverse=True)
# 取最高的前n个节点
n = 30
terms_chosen = []
for each in node_importance[:n]:
    terms_chosen.append(each[0])

# 输入词条，输出词典中的索引号
term2index = model.wv.key_to_index

# 可视化悉数词条和关键词条的二维Embedding
plt.figure(figsize=(10,10))
plt.scatter(embed_2d[:,0], embed_2d[:,1])
for item in terms_chosen:
    idx = term2index[item]
    plt.scatter(embed_2d[idx,0], embed_2d[idx,1],c='r',s=50)
    plt.annotate(item, xy=(embed_2d[idx,0], embed_2d[idx,1]),c='k',fontsize=12)
plt.show()

3.5 TSNE降维可视化

# 将Embedding用TSNE降维到2维
from sklearn.manifold import TSNE
tsne = TSNE(n_components=2, n_iter=1000)
embed_2d = tsne.fit_transform(X)

plt.figure(figsize=(10,10))
plt.scatter(embed_2d[:,0], embed_2d[:,1])
for item in terms_chosen:
    idx = term2index[item]
    plt.scatter(embed_2d[idx,0], embed_2d[idx,1],c='r',s=50)
    plt.annotate(item, xy=(embed_2d[idx,0], embed_2d[idx,1]),c='k',fontsize=12)
plt.show()

3.6导出TSEN降维到二维之后的Embedding

terms_chosen_mask = np.zeros(X.shape[0])
for item in terms_chosen:
    idx = term2index[item]
    terms_chosen_mask[idx] = 1
df = pd.DataFrame()
df['X'] = embed_2d[:,0]
df['Y'] = embed_2d[:,1]
df['item'] = model.wv.index_to_key
df['pagerank'] = pagerank.values()
df['chosen'] = terms_chosen_mask
# 将二维数据保存到txt文件中
a=df[['X','Y','pagerank']]
data=a.values
fo = open("tsne_vis_2d.txt", "w")
for i in range(len(data)):
    x=",".join(str(i) for i in data[i])
    x='['+x+'],'+'\n'
    fo.write(x)
fo.close()

4 本章总结

本章首要解说了DeepWalk算法，包括：

• DeepWalk简介：图嵌入、Word2Vec词嵌入、PPT内容解说
• DeepWalk论文精读：DeepWalk能够把节点编码成低维、稠密、接连的向量，包括节点的结构、衔接、社群特征，虽然不包括类别信息，但可用于猜测类别信息
• DeepWalk代码实战：运用维基百科词条数据构建无向图，生成随机游走节点序列，练习Word2Vec模型，经过核算PageRank得到关键词条，并进行可视化展示