我们来看下standford的Aditya Grover的《node2vec: Scalable Feature Learning for Networks》。
1.介绍
node2vec是一种半监督算法，用于在网络中的可扩展特征学习。受之前NLP中工作[21]的启发，我们会使用SGD对一个定制的基于图的（graph-based）目标函数进行优化。直觉上，该方法会返回特征表示，对于在d维空间内的节点，会对它们的网络邻节点的似然进行最大化。我们使用2-order的随机游走来为顶点生成（抽样）网络邻节点。
我们的关键贡献是，为一个顶点的网络邻节点定义了一个灵活的概念。通过选择一个合适的概念，node2vec可以学到网络表示，它们可以基于现在的网络角色，或者属于的社群来进行组织。我们通过开发一个有偏的随机游走（biased random walks）的族谱，它可以有效探索一个给定顶点的邻居分布。结果算法很灵活，提供可调参数给我们以对搜索空间进行控制，而不是之前的方法[24,28]进行严格搜索（rigid search）。相应的，我们的方法可以建模网络等价物。参数管理着我们的搜索策略，具有一个直观解释，会让walk朝着不同的网络搜索策略进行偏移。这些参数在一个半监督学习中，只使用很小比例的带标注数据（labeled data）就可以直接学到。
我们也展示了单独节点的特征表示如何被扩展成节点对（pairs of nodes。比如：边）。为了生成边的特征表示，我们将将学到的特征表示与简单的二元操作相组合。这种组合（compositionality）将node2vec引入到关于节点（或者是边）的预测任务上。
我们的试验集中在两个关于网络的公共预测任务上：一个多标签分类任务，其中每个节点被分配一或多个标签；一个链接预测任务，其中给定一个节点对，预测该边是否存在。我们将node2vec与state-of-art的特征学习方法[24,28]进行对比。并从现实中不同领域中的网络进行实验，比如社交网络，信息网络，以及系统生物学网络。对比起state-of-art的方法，实验演示了nod2vec在多标签分类上要好26.7%，在链接预测的任务上要好12.6%。该算法展示了有竞争力的效果，即使只有10%的带标签数据，对于噪声或缺失边的情况下一样健壮。计算上，node2vec的主要过程是并行化的，它可以扩展到带有数百万节点的大网络上，只需要几个小时的计算量。
该paper主要贡献是：
- 1.提出了nod2vec，一种用于网络特征学习的高效的扩展算法，可以通过一种显著的network-aware，neighborhood preserving objectives，使用SGD方法进行高效优化。
- 2.我们展示了node2vec如何适应在网络科学中已确立的准则，提供了在发现表示上的灵活性，并有不同的等价物。
- 3.我们基于neighborhood preserving objectives，扩展了node2vec以及其它特征学习方法，将节点扩展到节点对，来基于边的预测任务。
- 4.在多个真实数据集上，在多标签分类和链接预测上评估node2vec。
2.
在NLP的表征学习的最近进展上，有新方法对离散目标（比如：词）进行特征学习。特别的，Skip-gram模型是目标就是学习连续的特征向量，通过优化一个(neighborhood preserving likelihood objective). 该算法的处理如下：扫描一个文档的词，对于每个词，它的目标是将它进行嵌入，以便该词的特征可以预测邻近词（例如：在一些上下文窗口中的词）。词的特征表示通过使用SGD、negative sampling对likelihood objective进行优化学习得到。skip-gram目标函数是基于分布式假设：有相似上下文的词，趋向于具有相近的意思。也就是说，相似的词趋向于出现在具有相似词邻居的上下文内。
受skip-gram模型的启发，最近的研究确立了一种网络的类比法，将一个网络表示成一个“文档（document）”。相同的方法是，一个有序的词序列，节点序列需要从底层网络上进行采样，将一个网络转化成一个有序的节点序列。然而，对于节点来说，存在许多可能的抽样策略，会从而学到不同的特征表示。事实上，正如我们展示的，对于所有网络和所有预测任务来说，没有明确可胜出的抽样策略可以适用所有场景。以前的方法的主要缺点是，在从一个网络上进行抽样节点时缺乏灵活性。我们的算法node2vec克服了该限制，通过设计一种灵活的目标函数，它不会绑定一个特定的抽样策略，提供参数来调节探索的搜索空间（见第3节）。
最终，对于基于节点和基于边的预测任务，存在许多监督特征学习方法[15,17,31,39]。这些架构直接最小化loss function，使用多层非线性转换来产生更高的accuracy，但扩展开销高，因为训练时间长。
…
3.特征学习框架
我们将网络特征学习看成是一个极大似然优化问题。给定一个网络\(G = (V, E)\)。我们的分析是普适性的，可以应用于任何有向（无向）、加权（不加权）的网络。假设：\(f: V -> R^d\)是映射函数，将节点映射到特征表示。这里的d是特征表示的维度。f是一个size为\(\|V\| \times d\)的参数矩阵。对于每个源节点（srouce node）\(v \in V\)，我们定义了\(N_S(u) \subset V\)作为节点u的一个网络邻节点，它通过邻节点采样策略S来生成。
我们扩展了Skip-Gram架构来处理该网络。我们对下面的目标函数进行最优化，它会基于它的特征表示，对一个节点u的一个网络邻节点\(N_S(u)\)的log概率进行最大化，f给定：
\(max_f \sum_{u \in V} log Pr(N_S(u) | f(u))\) …(1)
为了让最优化变得可处理，我出做出了两个标准假设：
- 条件独立性。我们通过假设：给定源节点的特征表示，观察到一个邻节点的似然，与观察到其它邻节点是独立的：
- 特征空间的对称性。一个源节点和它的邻节点在特征空间中具有对称性的相互影响。因而，我们建模每个（源节点-邻节点）pair的条件似然建模成一个softmax unit，它由它们的特征点积进行参数化：
有了以上假设，等式一的目标可以简化为：
\(max_{f} \sum_{u \in V} [ -log Z_u + \sum_{n_i \in N_S(u)} f(n_i) \cdot f(u) ]\) …(2)
每个节点的分区函数：\(Z_u = \sum_{v \in V} exp(f(u) \cdot f(v))\)，对于大网络来说计算开销很大，我们可以使用负采样[22]来对它做近似。我们使用SGA（ascent）对等式(2)进行优化.
基于skip-gram的特征学习方法，最早源自于NLP上下文学习。文本本身是线性的，一个邻词可以很自然地使用一个在连续词汇上的滑动窗口进行定义。而对于网络，是非线性的，因而需要更丰富。为了解决这一点，我们提出了一个随机过程，它会对给定源节点u抽样许多不同的邻节点。\(N_S(u)\)不局限于它的立即邻节点（immediate neighbors），具体取决于抽样策略S，有不同的结构。
3.1 经典搜索策略
图1
我们将对一个源节点的邻节点进行抽样的问题看成是一种局部搜索（local search）。图1展示了一个图，其中，给定一个源节点u，我们的目标是生成(抽样)它的邻节点\(N_S(u)\)。重要的是，为了比较不同的抽样策略S，我们将邻节点集合\(N_S\)的size限制为k个节点，接着为单个节点u抽样多个集合。总体上，有两种极限抽样策略来生成k个节点的邻节点集合\(N_S\)：
- 广度优化抽样（BFS：Breadth-first Sampling）: 邻节点\(N_S\)被限制到关于源节点的立即领节点上（immediate neighbors）。例如：在图1中，对于一个邻节点的size为 k=3, BFS抽样的节点为：\(s_1, s_2, s_3\)。
- 深度优化抽样（DFS：Depth-first Sampling）：邻节点包含了从源节点开始在增加的距离上按顺序抽样的节点。在图1中，DFS抽样\(s_4, s_5, s_6\)
BFS和DFS表示了根据搜索空间进行探索的两种极限情况。
特别的，在网络上的节点的预测任务通常会是两种类型相似度的混合（shuffle）：同质（homophily）等价 和结构（structural）等价。在同质假设下，节点高度交错连接，并且属于同网络聚类或社群，在embedding上更紧密（例如：图1中的节点\(s_1\)和u属于相同的网络社群）。相反的，结构等价假设下，在网络上具有相似结构角色的节点，应该在embedding上更紧密（例如：节点u和\(s_6\)在图1上分演扮演着相应社群中心的角色）。更重要的是，不同于同质等价，结构等价不强调连通性；在网络中的节点可以离得很远，但它们仍具有相近的网络结构角色。在真实世界中，这些等价概念并是排斥的；网络通常具有两者的行为。
我们观察到，BFS和DFS的策略在处理表示时扮演着重要角色，它影响着上述两种等价。特别的，BFS抽样的邻节点会导致embedding与结构等价更紧密。直觉上，我们注意到，为了探明结构等价，通常会对局部邻节点进行精准的描述。例如，基于网络角色（桥接：bridges、中心：hubs）的结构等价可以通过观察每个节点的立即节点(immediate neighborhoods)观察到。通过将搜索限制到邻近节点，BFS达到了这种characterization， 并且获得了关于每个节点的邻近点的微观视角。另外，在BFS中，在抽样邻节点上的节点趋向于重复多次。这很重要，对于。
3.2 node2vec
基于上述观察，我们设计了一种灵活的邻节点抽样策略，它允许我们在BFS和DFS间进行平衡。我们通过开发一种灵活的有偏随机游走（biased random wolk）过程，它可以以BFS和DFS的方式来探索邻节点。
3.2.1 随机游走
给定一个源节点u，我们进行模拟一个固定长度为l的随机游走。\(c_i\)表示在walk中的第i个节点，从起点\(c_0=u\)开始。节点\(c_i\)通过下面的方式生成：
\[P(c_i=x | c_{i-1}=v) = \begin{cases} \frac{\pi_{vx}}{Z} , if(v,x) \in E \\ 0 , otherwise \end{cases}\]其中\(\pi_{vx}\)是未归一化的节点v和x间的转移概率，而Z是归一化常量。
3.2.2 搜索偏差\(\alpha\)
对我们的随机游走进行bias的最简单方法是，基于一个静态边权重\(w_{vx}\)（例如: \(\pi_{vx} = w_{vx}\)）来抽样下一个节点（无权重图则\(w_{vx}=1\)）。然而，该种情况不能解释网络结构，并指导搜索过程来探索不同类型的网络邻居。另外，不同于BFS和DFS两个极端，我们的随机游走会兼容两者。真实网络中通常也是两者混合。
图2: 在node2vec中的随机游走过程说明。该walk会从t到v进行转移，并在node v准备出去的下一步进行评估。边的labels表示搜索的bias \(\alpha\)
我们定义了一个2阶随机游走，它具有两个参数p和q来指导walk：考虑到一个随机游走，它穿过边(t,v)，现在留在节点v上（图2）。该walk需要决定，在下一步它会评估在边(v,x)上由v产生的转移概率\(\pi_{vx}\)。我们设置未归一化转移概率为\(\pi=\alpha_{pq}(t,x) \cdot w_{vx}\)，其中：
\[\alpha_{pq}(t,x) = \begin{cases} \frac{1}{p} , if d_{tx}=0 \\ 1 , if d_{tx}=1 \\ \frac{1}{q} , if d_{tx}=2 \end{cases}\]其中，\(d_{tx}\)表示在节点t和x上的最短路径距离。注意，\(d_{tx}\)必须是{0, 1, 2}其中之一，因而，两个参数都是必须的，可以充分指导该walk。
直觉上，参数p和q控制着该walk从起始节点u进行探索和离开邻节点的快慢。特别的，该参数允许我们的搜索过程（近似）在BFS和DFS间进行插值，从而影响不同节点等价的紧密关系。
返回（Return）参数：p。参数p控制着在walk中立即访问一个节点的似然。将它设置成一个高值(> max(q,1))，可以确保我们在下两步内对一个已经访问节点进行抽样的可能性变得很小。（除非在walk内的下一个节点没有其它邻居）。这种策略鼓励适度探索，避免在抽样时存在二跳内重复（2-hop redundancy）。另一方面，如果p很小（<min(q,1)），它将导致该walk会回溯(backtrack)一个step（见图2），并且这会让该walk“局部”上保持与起始节点u的接近。
入出（In-out）参数：q。参数q允许搜索在“inward”和”outward”节点间区分。回到图2, 如果q>1, 随机游走会偏向于更接近节点t的节点。这样的walk会根据在walk中各自的起始节点获得一个关于底层graph的局部视图，近似的BFS行为感觉上我们的抽样在一个小的局部内的节点组成。
作为对比，如果 q < 1, 该walk更趋向于访问那些离节点t更远的节点。这样的行为受DFS影响，它会鼓励outward探索。然而，这里的一个基本不同是，我们在随机游走框架内完成DFS-like的探索。因而，被抽中的节点不需要对到给定节点u的距离进行增加才行，反过来，我们受益于对随机游走的回溯预处理和优秀的采样效率。注意，通过将\(\pi_{v,x}\)设置成关于一个在walk t内前继节点的函数，随机游走是2阶markovian。
随机游走的好处。比起纯BFS/DFS方法，随机游走有许多好处。随机游走在时间和空间需求上的计算很高效。在图中为每个节点存储它的立即邻节点的空间复杂度为\(O(\|E\|)\)。对于二阶随机游走，会存储在每个节点的邻节点间的交叉连接，这会引发一个空间复杂度为\(O(a^2 \|V\|)\)，其中\(a\)是该graph的平均度，它通常对于现实网络来说很小。比起经典的基于搜索的抽样策略，随机游走的其它核心优点是它的时间复杂度。特别是，通过引入在抽样生成过程中的图连通性，随机游走提供了一个很便利的机制，通过复用跨不同源节点间的样本，来增加有效抽样率。通过模拟一个长度l>k的随机游走，得益于随机游走的马尔可夫性，我们可以为l-k个节点一次生成k个样本。因而，每个样本的有效复杂度为\(O(\frac{1}{k(1-k)})\)。例如，在图1中，我们抽样一个长度为l=6的随机游走 {\(u, s_4, s_5, s_6, s_8, s_9\)}，它会产生\(N_S(u)=\left s_4, s_5, s_6 \right\)，\(N_S(s_4)=\left s_5, s_6, s_8 \right\)，以及\(N_S(s_5)=\left s_6, s_8, s_9 \right\)。注意，在整个过程中，样本复用可能引入一些bias。然而，我们观察到它可以极大提升效率。
3.2.3 node2vec算法
算法1
node2vec的伪代码，详见算法一。在任何随机游走中，由于起始节点u的选择，会有一个隐式偏差（implicit bias）。由于我们为所有节点学习表示，我们会为每个节点通过模拟r个固定长度为l的随机游走来对该bias进行补偿（offset）。在该walk的每一个step，会基于转移概率\(\pi_{vx}\)进行抽样。对于二阶马尔可夫链，转移概率\(\pi_{vx}\)可以被预计算好，因而，当模拟随机游走时，节点的抽样可以很有效地在O(1)时使用alias sampling完成。node2vec的三个阶段（phases），即：预处理计算转移概率、随机游走模拟、使用SGD进行优化，是按顺序进行的。每个phase可以并行化和异步执行，从而做到node2vec整体可扩展性。 node2vec的一个实现：http://snap.stanford.edu/node2
3.3 学习边特征
node2vec算法提供了一个半监督方法来学习网络中节点的丰富特征表示。然而，我们通常对涉及节点对（pairs of nodes）的预测任务感兴趣，而非单个节点。例如，在链接预测上，我们在网络中的两个节点间预测一个链接是否存在。由于我们的随机游走在底层网络上天然地基于节点间的连通结构，我们可以使用一个bootstrap方法来将它们扩展到节点对的特征表示，而非单个节点的特征表示。
给定两个节点u和v，我们定义了一个二元操作o，在相应的特征向量f(u)和f(v)，为了生成一个表示g(u,v)，比如：\(g: V \times V -> R^d^'\)，其中\(d'\)是pair(u,v)的表示的size。我们希望我们的操作对于任意节点对可以进行定义，即使一条边在pair间不存在，因为这样做可以使表示对于连接预测有用，我们的测试集包含了true edges和false edges（不存在）。我们对于操作符o的一些选择，以便\(d'=d\)，由表1归纳的。
实验
略