图表示学习笔记（一）_最小生成树 随机游走

图表示学习笔记（一）

DeepWalk:算法原理和应用

图表示学习

目前提到的图算法一般指：
1.经典数据结构与算法层面的：最小生成树，最短路径、拓扑结构、关键路径
2.概率模型，涉及图的表示学习，推断和学习
3.图神经网络，主要包括Graph Embedding（基于随机游走） 和==Graph CNN(基于邻居汇聚)==两部分。
Graph Emmbedding技术将图中的节点以低维稠密向量的形式进行表达，要求在原始图中相似(不同方法对相似的定义不同)的节点其在低维空间也接近。得到的表达向量可以用来进行下游任务：节点分类，链路预测，可视化或重构原始图等。

DeepWalk算法原理 (KDD 2014)

DeepWalk是了解Graph Embedding重要方法。
在NLP中，word2Vec是一种常用的word embedding方法，word2vec通过语料库中的句子序列来描述词与词之间的共现关系，进而学习到词语的向量表示。
Word2vec也叫word embedding，中文名叫“词向量”,作用就是将自然语言中的字词转换为计算机可以理解的稠密向量（Dense Vector). 在word2vec出现之前，自然语言通常把字词转换成为离散的单独的符号，也就是one-hot编码。

如 上图，在语料库中，杭州，上海，宁波，北京各对应一个向量，向量中只有一个值为1，其余都为0. 但是使用One-hot编码会有以下问题，首先，城市编码是随机的，向量之间相互独立，看不出城市之间可能存在的关联性。其次，向量维度取决于语料库中字词的多少。如果将世界所有城市名称对应的向量合为一个矩阵的化，那这个矩阵过于稀疏，并且 会造成维度灾难。（维度灾难: 我们在训练样本的时候，在样本数目不变的情况下，随着维度的增高，我们的模型效果会随着维度的增高而降低）。
用向量表示可以有效地解决这个问题。Word2vec可以将One-hot编码转化为低维稠密向量，其中相近的词将被映射到向量空间中相近的位置。
将嵌入后的城市向量通过PCA降维可视化如下：

Wordvec中的两个重要模型：CBOW和Skip-gram模型

CBOW模型

• 拿一个词语的上下文作为输入，来预测这个词语本身，就是CBOW模型。
  
  上图可以理解为C个输入单词的维度是V维（可以理解为词库共有V个词，V维onehot向量就可以唯一地表示这个词语），当语料库中单词数量很多时，V值会超级大。
  对应上图：输入有x_1k,x_2k,…这些上下文词语共C个，每一个的长度是V，输出就是y这个中心词1个，长度为V。在这个网络中我们的目的不是跟一般的神经网络一样去预测标签，而是想要得到完美的参数：权重，X和这个权重相乘能够唯一的表示这个词语，同时需要提到一点的是，这个词向量的维度（与隐含层节点数一致）一般情况下要远远小于词语总数 V 的大小，所以 Word2vec 本质上是一种降维操作。

Skip-gram 模型

如果是用一个词语作为输入，用来预测它周围的上下文。

DeepWalk思想类似word2vec，使用图中节点与节点的共现关系来学习表示节点的向量表示。那么关键问题就是如何来描述节点与节点之间的共现关系，Deepwalk给出的方法是使用随机游走（RandomWalk）的方式在图中进行节点采样。
RandomWalk是一种可重复访问已访问节点的深度优先遍历的算法。给定当前访问起始节点，从其邻居中随机采样节点作为下一个访问节点，重复此过程，直到访问序列长度满足预设条件。
获取足够数量的节点访问序列后，使用skip-gram进行向量学习。

DeepWalk 核心代码：

第一步：随机游走采样节点序列，第二步使用skip-gram学习表达向量。

①构建同构网络，从网络中的每个节点开始分别进行Random Walk 采样，得到局部相关联的训练数据； ②对采样数据进行SkipGram训练，将离散的网络节点表示成向量化，最大化节点共现，使用Hierarchical Softmax来做超大规模分类的分类器。（通过 gensim 的 word2vec 模型对上述随机游走获得的训练语料进行训练，获取词嵌入。）

步骤

1.构造图

import networkx as nx
import random
from genism.models import Word2Vec

G=nx.read_edgelist('Enron.txt',create_using=nx.DiGraph())
1
2
3
4
5

2.随机游走

# 生成随机游走序列的代码
# 从 start_node 开始随机游走
def deepwalk_walk(walk_length, start_node):
    walk = [start_node]
    while len(walk) < walk_length:
        cur = walk[-1]
        cur_nbrs = list(G.neighbors(cur))
        if len(cur_nbrs) > 0:
            walk.append(random.choice(cur_nbrs))
        else:
            break
    return walk

# 产生随机游走序列
def _simulate_walks(nodes, num_walks, walk_length):
    walks = []
    for _ in range(num_walks):
        random.shuffle(nodes)
        for v in nodes:
            walks.append(deepwalk_walk(walk_length=walk_length, start_node=v))
    return walks
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.嵌入

# 默认嵌入到100维
w2v_model = Word2Vec(walks,sg=1,hs=1)
# 打印其中一个节点的嵌入向量
print(w2v_model['1'])
1
2
3
4

总结

1.DeepWalk的思想与Word2Vec类似，从一个初始节点沿着图中的边随机游走一定的步数，将经过的节点序列视为句子。那么从不同的起点开始的不同游走路线就构成了不同的句子，当获取到足够数量的句子（节点访问序列）后，可以使用skip-gram模型对每个节点学习其向量表示。
2.根据 skip-gram 模型的思想，假设节点2，3的局部上下文语境比较相似，于是最终学习到的节点2、3的Embedding表示也就比较相似。这也意味着，当两个节点共有的邻居节点越多，那么这两个节点就越相似。

参考链接：
DeepWalk：算法原理，实现和应用.
GraphEmbedding - DeepWalk 图文详解.
DeepWalk原理与代码实战.