图嵌入

首先介绍通用的图嵌入框架：图经过信息提取器生成含有图关键信息的I；图域可经过嵌入映射得到嵌入域，为测试嵌入域对图域的保留程度，基于嵌入域进行重构，生成I’，并使重构结果逼近生成器的现象。

本文只针对保留节点共现的图嵌入方法，也即random walk。对应上述部件，提取器基于random walk，映射为one hot编码，重构即计算共现对的概率。

提取器

提取器是random walk，选定出发点，随机选中下个点，往复执行，直到生成一条长度为v的路径，若图中共有N个点，则会生成N*v条路径，并在此基础上，提取共现节点对，这个节点对有中心点与邻居点的地位差别。

node2vec是一种有偏重的二阶random walk，可以通过控制p，q的大小，在当前位置，上一步位置的基础上决定下一步去哪的概率，下图是未归一化的游走方向概率：若p大q小，趋近于远离上一步的位置；若p小q大，趋近于回到上一步的位置。生成随机游走后，其余步骤与random walk一样。

重构器

重构器基于共现对，最大化他们出现的概率:首先定义两个矩阵，存储着各节点的对应中心点向量，上下文向量；根据softmax计算先验概率，定义优化函数使其最大。在4-8式中，#()是取该节点对的出现次数。

但是针对每个共现都要计算一次softmax，分母的计算很困难。因此有两种简化的算法。分层softmax和负采样。

(1)分层softmax是把所有图节点映射到一个完全二叉树的叶子节点，上述先验概率变成了二叉树向下层某个方向(left,right)的移动概率。同时学习的参数也不再是Wcen和Wcon，而是二叉树的叶子映射和内部映射。

(2)负采样是采样一些非共现的元组对，优化目标则不再计算相对概率softmax，而是共现对取log(sigmoid())，负采样对取log(sigmoid(-))。由于不计算softmax，计算量大大减小。

Line算法是在上式基础上，将所有共现对替换为图的边集epsilon。