node2vec: Scalable Feature Learning for Networks

直接上图。可以看到在network中有两个community，u和s1属于同一个community，u和s6属于不同的community，
node2vec基于的两个原则：
•属于同一个community的节点之间的embedding应该是接近的（如u和s1）。
•share相似的structural role的节点的embedding应该是接近的（如u和s6）。

node2vec的一些参数表示了不同的网络探索策略，并且这些参数可以使用一部分标注数据学习得到（半监督学习）。
node2vec还可以通过对于两个node representation简单的二元运算，得到边的representation。

node2vec是基于random walk的，以前的一些基于random walk的算法（比如deepwalk）的搜索策略是单一固定的，而node2vec提供了参数来调整搜索策略。

FEATURE LEARNING FRAMEWORK

G=(V,E)表示图
目标：学到一个|V|*d的feature representation矩阵，其中d是embedding的维度。
对于每个节点u∈V，定义集合Ns(u)包含于V表示u在neighborhood采样策略S下的neighborhood。
目标函数为：

f(u)是u节点的embedding，也就是说通过调整f来最大化given f(u)的情况下，能够观测到u的实际neighborhood节点集合Ns(u)的概率。
为了让优化问题tractable，给出两个假设：
•条件独立。假设给出f(u)的情况下，观察到u的各个neighbor的概率是独立的，于是有

•特征空间对称性。假设在特征空间中，u节点和其neighbor节点ni直接的影响是相互的。用u和ni的feature的点积为参数的softmax来表示Pr(ni|f(u))，即

根据上述两个假设，等式(1)可以化简为

其中Zu可以理解为节点u的配分函数(partition function)

由(1)到(2)的具体推导如下：

配分函数Zu对于大规模的网络来说计算量过大，因此使用负采样来近似。
通过随机梯度上升来最大化likelihood得到最优的f。

Classic search strategies

下面需要一种方式来获得node sequence。
目标：对于节点u，采样包含k个nodes 的neighbor set Ns。
一般来说有两种采样策略：
•BFS
•DFS

对于network embedding而言，一般有两种相似性：
•homophily
•structural equivalence
homophily指的是节点之间互相连接并且属于同一个网络簇，则它们的embedding应该是接近的。比如图中的s1和u。
structural equivalence指的是有相似的structural role的节点的embedding应该是接近的。比如图中的u和s6都是作为一个community的中心。

需要强调的是，与homophily不同，structural equivalence不强调连接，两个节点即使在network中离得很远，仍然可以有相似的structural role。
BFS更多的在考虑structural equivalence，而DFS更多的在考虑homophily。

node2vec

node2vec的采样策略同时考虑了BFS和DFS。

Random Walks

以u为其实节点，开始长度为l的随机游走。ci表示随机游走中的第i个节点，c0=u.
ci由下式产生，

其中πvx为节点v和x之间的未归一化概率，Z是归一化常数。

Search bias α

最简单的方法是令πvx=Wvx，如果是无向图，就令Wvx=1，但是这样做的效果并不好。我们希望能找到一种方式，可以结合BFS和DFS。

在node2vec中定义参数p和q来引导walk。

如图所示，random walk刚从t走到v，接下来考虑往哪边走。
令

其中

dtx表示节点t和x之间的最短距离。直觉上，参数p和q控制random walk探索或者离开节点v的neighborhood。

增大p的值，表示我们不太希望random walk回到刚刚进来时的节点。
q>1，random walk偏好于靠近t的节点，也就是偏好于在小区域探索，可以看作BFS的想法。
q<1，random walk偏好于远离t的节点，可以看作DFS的想法。
整个random walk可以看作一个二阶马尔科夫链(t与x2有关，因此是二阶。需要注意的是，这里的说法与MCMC中的markov chain是完全不同的，markov chain本质是概率图模型，每个节点表示的是一个随机变量)。

The node2vec algorithm

总结node2vec，三个步骤：
•预处理计算转换概率
•产生random walk
•SGD优化求解

DeepWalk可以看作是特殊的node2vec，也就是p=1,q=1的情况

对于p和q，可以在部分标注数据上用网格搜索比如p,q∈{0.25,0.50,1,2,4}学习到。

在一些问题中，比如说link prediction，需要边的representation。
对于节点u和v，在f(u)和f(v)上定义一个二元操作o，来产生g(u,v)表示d'维的边representation。即使u和v直接在network上没有边，做edge embedding的时候也认为有一条false edge。
操作o的定义可以从下面的表格中选取，并且d=d'