Graph Embedding学习笔记

前言

图是一个常见的数据结构，针对图的研究大致上可以分为以下三类

简单的图算法

这类算法研究简单的如生成树算法、最短路径算法发，复杂的如二分图匹配、费用流问题等等

概率图模型

这是将条件概率表达为图结构，并进一步挖掘，典型的有条件随机场等

概率图理论共分为三个部分，分别为概率图模型表示理论，概率图模型推理理论和概率图模型学习理论

基本的概率图模型包括贝叶斯网络、马尔可夫网络和隐马尔可夫网络。

基本的Graphical Model 可以大致分为两个类别：贝叶斯网络(Bayesian Network)和马尔可夫随机场(Markov Random Field)，它们区别在于采用不同类型的图来表达变量之间的关系。【贝叶斯网络采用有向无环图(Directed Acyclic Graph)来表达因果关系，马尔可夫随机场则采用无向图(Undirected Graph)来表达变量间的相互作用】

图神经网络

这是用于研究图结构数据挖掘的问题，典型的有graph embedding，graph CNN等。

前言2

Embedding

什么是Embedding？

Embedding在数学上是一个函数，它是将一个高维抽象空间的点映射到低维的具体空间。因此它的意义就是将高维数据转换到低维利于算法进行处理，同时解决one-hot向量长度随样本的变化而变化，以及无法表示两个实体之间的相关性这一问题。（one-hot：独热编码，也叫一位有效码，主要采用N位状态寄存器来对N个状态进行编码，每个状态都由他独立的寄存器位，并且在任意时候只有一位有效。one-hot编码是分类变量作为二进制向量的表示，它要求首先将分类值映射到整数值，然后每个整数值被表示为二进制向量，除了整数的索引外，它都是零值，它被标记为1）

最常见的embedding方法就是word2vec，根据语料库中单词的共现关系求出每个单词的embedding，常用的word2vec模型有cbow和skip-gram两种。cbow根据山下问预测中心词，skip-gram根据中心词预测上下文。

Graph Embedding

Graph Embedding的中心思想是找到一种映射函数，该函数将网络中的每个节点转换为低维度的潜在表示

下面列表是graph embeding的几种常见分类

考虑网络结构	DeepWalk	GraRep	struc2vec
	LINE	node2vec	GraphSAGE
考虑结构和其他信息	CENE	CANE	Trans-Net
DL	GCN	SDNE
GAN	GraphGAN	ANE

DeepWalk

DeepWalk 通过将节点视为单词并生成短随机游走作为句子来弥补网络嵌入和单词嵌入之间的差距，接着就可以通过将诸如Skip-gram 之类的神经语言模型应用于这些随机游走以获得网络嵌入。

它的优点是：

①按需生成随机游走

②可扩展的

③引入了深度学习图形的范例

下图展示了DeepWalk的过程

​ DeepWalk的算法流程（引自阿里论文）

整个算法大致可以分为四步走

1. 图a展示了原始的用户行为序列
2. 图b基于这些用户行为序列构建了物品相关图，可以看出，物品A，B之间的边产生的原因就是因为用户U1先后购买了物品A和物品B，所以产生了一条由A到B的有向边。如果后续产生了多条相同的有向边，则有向边的权重被加强。在将所有用户行为序列都转换成物品相关图中的边之后，全局的物品相关图就建立起来了。
3. 图c采用随机游走的方式随机选择起始点，重新产生物品序列。
4. 图d最终将这些物品序列输入word2vec模型（也可以使用skip-gram模型），生成最终的物品Embedding向量。

以上步骤中核心的是第三步，其中唯一需要形式化定义的是随机游走的跳转概率，也就是到达节点vi后，下一步遍历vi的临接点vj的概率。如果物品的相关图是有向有权图，那么从节点vi跳转到节点vj的概率定义如下：

其中N+(vi)是节点vi所有的出边集合，Mij是节点vi到节点vj边的权重。

如果物品相关图是无向无权重图，那么跳转概率将是上面公式的一个特例，即权重Mij将为常数1，且N+(vi)应是节点vi所有“边”的集合，而不是所有“出边”的集合。

随机游走的好处：

• 并行化：随机游走是局部的，对于一个大的网络来说，可以同时在不同的顶点开始进行一定长度的随机游走，多个随机游走同时进行，可以减少采样的时间。
• 适应性：可以适应网络局部的变化。网络的演化通常是局部的点和边的变化，这样的变化只会对部分随机游走路径产生影响，因此在网络的演化过程中不需要每一次都重新计算整个网络的随机游走。

Node2vec

理论

斯坦福大学在deepwalk的基础上更进一步，通过调整随机游走权重的方法使graph embedding的结果在网络的同质性和结构性中进行权衡。

网络的同质性是指距离相近节点的embedding应该尽量相似，如下图所示，节点u与其相连的s1，s2，s3，s4的embedding表达是接近的，这就是同质性。

结构性是指结构上相似的节点的embedding应该尽量接近，如上图的s6和u两个节点都是各自局域网络的中心，从结构上来说，这就是结构上的相似，他们的embedding的表达也应该相似，而着就是结构性。

【看到大佬的一个直观解释：相同性的相似是指从u到s6的路径和从s2到s6的“距离”非常相近；而结构性相似是指节点u和节点s6的“地位作用”比较相似。换句话说，就是从北京去上海和从天津到上海的距离是非常相近的；而北上广深每天都有很多的飞机航班通往全国各地，但其他城市却没有这么多，所以北上广深的地位作用是非常相近的】

所以为了使Graph Embedding的结果能够表达网络的同质性，在随机游走的过程中，需要让游走的过程更倾向于DFS（深度优先搜索），因为对于两个距离比较近的节点，出现在相同上下文序列的几率比较高，因此近距离的节点容易学习出相似的embedding向量。

而对于BFS（宽度优先搜索）来说，对于两个结构性比较类似的节点，BFS构建两个节点在类似位置的上下文序列的概率更高，因此可以更好的学习到结构性；进一步假设，如果两个点有大量相同的邻居节点，那么w2v（word2vec）训练时，具有相同上下文的概率更高，embedding向量应该更接近；

而node2vec算法中，主要是通过节点间的跳转概率来控制BFS和DFS的倾向性的。

下图显示了node2vec算法从节点t跳转到节点v后，下一步从节点v跳转到周围个点的跳转概率

其中p和q的定义论文作者给出的解释如下：

• Return parameter pp:
  Return back to the previous node
• In-out parameter qq:
  Moving outwards (DFS) vs. inwards (BFS)
  Intuitively, qq is the “ratio” of BFS vs. DFS

翻译一下就是p是返回参数，q是进出参数，q是BFS和DFS的比值

可能很多人看不懂这里说的是什么意思（实际上它的解释我也看得不是恒明白），下面来说明一下

当下一个节点x与前一个节点t和当前节点v等距时，$\alpha$=1; 当下一个节点xx是上一个节点时，$\alpha$=$\frac{1}{p}$;在其他情况下，α=$\frac{1}{q}$

从节点v跳转到下一个节点x的概率计算公式如下：

其中$\omega_{vx}$是边vx的权重， $\alpha_{pq}(t,x)$的定义如下：

dtx指的是节点t到节点x的距离，参数p和q共同控制着随机游走的倾向性。p越小，随机游走回节点t的可能性越大，node2vec就更注重表达网络的同质性，q越小，则随机游走到远方节点的可能性越大，node2vec更注重表达网络的结构性，反之，当前节点更可能在附近节点游走。

代码解读与学习

安装库

node2vec需要用到gensim库

安装gensim库前需要安装numpy和scipy两个库

安装gensim库建议使用这个镜像源，其他的基本都会出现该死的爆红现象

pip install -i https://pypi.mirrors.ustc.edu.cn/simple gensim

最后在安装node2vec库就好了

代码使用学习

导库

import networkx as nx
import gensim
from node2vec import Node2Vec

这里需要用到三个库，第一个是生成图用的networkx库，第二个是用于自然语言的gensim库，第三个是node2vec算法所用的库

建图

G = nx.fast_gnp_random_graph(n=100, p=0.5)

我们先利用fast_gnp_random_graph（）生成一个随机图，这个函数的用法在下面有解释

nx.fast_gnp_random_graph（n, p, seed=None, directed=False）
#这里的n为节点数，p为边创建的概率，seed为随机数生成的种子（默认为无），directed为有向图，默认为False，如果是True则返回的是有向图

node2vec应用

node2vec = Node2Vec(G, dimensions=64, walk_length=30, num_walks=200, workers=1)

这行代码用于预计算概率并生成行走，其中按照学习文章的作者所说的，该方法如果在windows上运行的话建议workers=1

下图是Node2Vec（）的总体流程图

其中它的代码如下：

def __init__(self, graph, dimensions=128, walk_length=80, num_walks=10, p=1, q=1, weight_key='weight', workers=1, sampling_strategy=None, quiet=False, temp_folder=None):
 
      self.graph = graph
      self.dimensions = dimensions
      self.walk_length = walk_length
      self.num_walks = num_walks
      self.p = p
      self.q = q
      self.weight_key = weight_key
      self.workers = workers
      self.quiet = quiet
      self.d_graph = defaultdict(dict)
 
      if sampling_strategy is None:
          self.sampling_strategy = {}
      else:
          self.sampling_strategy = sampling_strategy
 
      self.temp_folder, self.require = None, None
      if temp_folder:
          if not os.path.isdir(temp_folder):
              raise NotADirectoryError("temp_folder does not exist or is not a directory. ({})".format(temp_folder))
 
          self.temp_folder = temp_folder
          self.require = "sharedmem"
 
      self._precompute_probabilities()
      self.walks = self._generate_walks()

通过这个代码我们可以了解到它的输入参数：

1. graph: 第1个位置的参数必须是 networkx 图。节点名必须都是整数或都是字符串。在输出模型上，它们始终是字符串。
2. dimensions: 嵌入维度（默认值：128）
3. walk_length: 每个路径的节点数（默认值：80）
4. num_walks: 经过每个节点的次数（默认值：10）
5. p: 返回超参数（默认值：1）# p 和 q 是决定采用DFS或者BFS的关键参数
6. q: 输入输出参数（默认值：1）
7. weight_key: 在加权图上，这是 权重属性的关键字（默认值：“weight”）。
8. workers: 并行执行的工作者数目（默认值：1）
9. sampling_strategy: 特定节点的采样策略, 支持设置节点特定的“q”、“p”、“num_walks”和“walk_length” 参数。请准确地使用这些关键字。如果未设置，将默认为对象初始化时传递的全局参数。
10. quiet: 控制布尔值长度。（默认值：false）
11. temp_folder: 指向文件夹的字符串路径，用于保存图形的共享内存副本 - 在算法执行过程中处理过大而无法放入内存的图时提供。

model = node2vec.fit(window=10, min_count=2, batch_words=1)
model.save('node2vec_test.model') # 保存训练好的模型到当前文件夹
new_model = gensim.models.Word2Vec.load('node2vec_test.model') # 调用模型

下面的node2vec.fit()的源码：

def fit(self, **skip_gram_params):
 
    if 'workers' not in skip_gram_params:
        skip_gram_params['workers'] = self.workers
 
    if 'size' not in skip_gram_params:
        skip_gram_params['size'] = self.dimensions
 
    return gensim.models.Word2Vec(self.walks, **skip_gram_params)