GraphEmbedding实战系列：Node2vec原理与代码实战

GraphEmbedding实战系列：Node2vec原理与代码实战

论文：《node2vec: Scalable Feature Learning for Networks》

基本介绍

node2vec是一种半监督算法，用于在网络中的可扩展特征学习。node2vec使用SGD对一个定制的基于图的（graph-based）目标函数进行优化。这种方法会返回特征表示，对于在d维空间内的节点，会对它们的网络邻节点的似然进行最大化。

node2vec关键贡献是，为一个顶点的网络邻节点定义了一个灵活的概念。通过选择一个合适的概念，node2vec可以学到网络表示，它们可以基于现在的网络角色，或者属于的社群来进行组织。论文通过开发一个有偏的随机游走（biased random walks）的族谱，它可以有效探索一个给定顶点的邻居分布。结果算法很灵活，提供可调参数给我们以对搜索空间进行控制，而不是进行严格搜索（rigid search）。相应的，论文的方法可以建模网络等价物。参数管理着搜索策略，具有一个直观解释，会让walk朝着不同的网络搜索策略进行偏移。这些参数在一个半监督学习中，只使用很小比例的带标注数据（labeled data）就可以直接学到。

我们也展示了单独节点的特征表示如何被扩展成节点对（pairs of nodes。比如：边）。为了生成边的特征表示，我们将将学到的特征表示与简单的二元操作相组合。这种组合（compositionality）将node2vec引入到关于节点（或者是边）的预测任务上。

该paper主要贡献是：

• 1.提出了nod2vec，一种用于网络特征学习的高效的扩展算法，可以通过一种显著的network-aware，neighborhood preserving objectives，使用SGD方法进行高效优化。
• 2.展示了node2vec如何适应在网络科学中已确立的准则，提供了在发现表示上的灵活性，并有不同的等价物。
• 3.基于neighborhood preserving objectives，扩展了node2vec以及其它特征学习方法，将节点扩展到节点对，来基于边的预测任务。
• 4.在多个真实数据集上，在多标签分类和链接预测上评估node2vec。

特征学习框架

为了让最优化变得可处理，做出了两个标准假设：

• 条件独立性。我们通过假设：给定源节点的特征表示，观察到一个邻节点的似然，与观察到其它邻节点是独立的：

Pr(N_s(u) | f(u)) = \prod_{n_i \in N_S(u)} Pr( n_i | f(u)) \\

• 特征空间的对称性。一个源节点和它的邻节点在特征空间中具有对称性的相互影响。因而，我们建模每个（源节点-邻节点）pair的条件似然建模成一个softmax unit，它由它们的特征点积进行参数化：

Pr(n_i | f(u)) = \frac{exp(f(n_i)\cdot f(u))} {\sum_{v \in V} exp(f(v) \cdot f(u))} \\

有了以上假设，等式一的目标可以简化为：

max_{f} \sum_{u \in V} [ -log Z_u + \sum_{n_i \in N_S(u)} f(n_i) \cdot f(u) ] \\

每个节点的分区函数：

Z_u = \sum_{v \in V} exp(f(u) \cdot f(v))\\

，对于大网络来说计算开销很大，可以使用负采样来对它做近似。

基于skip-gram的特征学习方法，最早源自于NLP上下文学习。文本本身是线性的，一个邻词可以很自然地使用一个在连续词汇上的滑动窗口进行定义。而对于网络，是非线性的，因而需要更丰富。为了解决这一点，论文提出了一个随机过程，它会对给定源节点u抽样许多不同的邻节点。

N_S(u)

不局限于它的立即邻节点（immediate neighbors），具体取决于抽样策略S，有不同的结构。

经典搜索策略

BFS和DFS表示了根据搜索空间进行探索的两种极限情况。

特别的，在网络上的节点的预测任务通常会是两种类型相似度的混合（shuffle）：同质（homophily）等价 和结构（structural）等价。在同质假设下，节点高度交错连接，并且属于同网络聚类或社群，在embedding上更紧密（例如：图中的节点

s_1

和u属于相同的网络社群）。相反的，结构等价假设下，在网络上具有相似结构角色的节点，应该在embedding上更紧密（例如：节点u和

s_6

在图上分演扮演着相应社群中心的角色）。更重要的是，不同于同质等价，结构等价不强调连通性；在网络中的节点可以离得很远，但它们仍具有相近的网络结构角色。在真实世界中，这些等价概念并是排斥的；网络通常具有两者的行为。

我们观察到，BFS和DFS的策略在处理表示时扮演着重要角色，它影响着上述两种等价。特别的，BFS抽样的邻节点会导致embedding与结构等价更紧密。直觉上，我们注意到，为了探明结构等价，通常会对局部邻节点进行精准的描述。例如，基于网络角色（桥接：bridges、中心：hubs）的结构等价可以通过观察每个节点的立即节点(immediate neighborhoods)观察到。通过将搜索限制到邻近节点，BFS达到了这种characterization， 并且获得了关于每个节点的邻近点的微观视角。另外，在BFS中，在抽样邻节点上的节点趋向于重复多次。这很重要，对于。

node2vec

基于上述观察，论文设计了一种灵活的邻节点抽样策略，它允许我们在BFS和DFS间进行平衡。论文通过开发一种灵活的有偏随机游走（biased random wolk）过程，它可以以BFS和DFS的方式来探索邻节点。

随机游走

直觉上，参数p和q控制着该walk从起始节点u进行探索和离开邻节点的快慢。特别的，该参数允许我们的搜索过程（近似）在BFS和DFS间进行插值，从而影响不同节点等价的紧密关系。

返回（Return）参数：p。参数p控制着在walk中立即访问一个节点的似然。将它设置成一个高值(> max(q,1))，可以确保在接下来的两步内对一个已经访问节点进行抽样的可能性变得很小。（除非在walk内的下一个节点没有其它邻居）。这种策略鼓励适度探索，避免在抽样时存在二跳内重复（2-hop redundancy）。另一方面，如果p很小（<min(q,1)），它将导致该walk会回溯(backtrack)一个step，并且这会让该walk“局部”上保持与起始节点u的接近。

入出（In-out）参数：q。参数q允许搜索在“inward”和"outward"节点间区分。如果q>1, 随机游走会偏向于更接近节点t的节点。这样的walk会根据在walk中各自的起始节点获得一个关于底层graph的局部视图，近似的BFS行为感觉上我们的抽样在一个小的局部内的节点组成。

作为对比，如果 q < 1, 该walk更趋向于访问那些离节点t更远的节点。这样的行为受DFS影响，它会鼓励outward探索。然而，这里的一个基本不同是，在随机游走框架内完成DFS-like的探索。因而，被抽中的节点不需要对到给定节点u的距离进行增加才行，反过来，将会受益于对随机游走的回溯预处理和优秀的采样效率。注意，通过将

\pi_{v,x}

设置成关于一个在walk t内前继节点的函数，随机游走是2-order markovian。

node2vec实战

node2vec算法

node2vec代码

from gensim.models import Word2Vec
from gensim import __version__ as gensim_version
import numpy as np
from numba import njit

from tqdm import tqdm


@njit
def set_seed(seed):
    np.random.seed(seed)


class Node2Vec(Word2Vec):
    def __init__(
        self,
        graph,
        dim,
        walk_length,
        context,
        p=1.0,
        q=1.0,
        workers=1,
        batch_walks=None,
        seed=None,
        **args,
    ):
        assert walk_length < 10000
        if batch_walks is None:
            batch_words = 10000
        else:
            batch_words = min(walk_length * batch_walks, 10000)

        if gensim_version < "4.0.0":
            args["iter"] = 1
        else:
            args["epochs"] = 1

        super().__init__(
            sg=1,
            vector_size=dim,
            window=context,
            min_count=1,
            workers=workers,
            batch_words=batch_words,
            **args,
        )
        self.build_vocab(([w] for w in graph.node_names))
        self.graph = graph
        self.walk_length = walk_length
        self.p = p
        self.q = q
        self.seed = seed

    def train(self, epochs, *, progress_bar=True, **kwargs):
        def gen_nodes(epochs):
            if self.seed is not None:
                np.random.seed(self.seed)
            for _ in range(epochs):
                for i in np.random.permutation(len(self.graph.node_names)):
                    # dummy walk with same length
                    yield [i] * self.walk_length

        if progress_bar:

            def pbar(it):
                return tqdm(
                    it, desc="Training", total=epochs * len(self.graph.node_names)
                )

        else:

            def pbar(it):
                return it

        super().train(
            pbar(gen_nodes(epochs)),
            total_examples=epochs * len(self.graph.node_names),
            epochs=1,
            **kwargs,
        )

    def generate_random_walk(self, t):
        return self.graph.generate_random_walk(self.walk_length, self.p, self.q, t)

    def _do_train_job(self, sentences, alpha, inits):
        if self.seed is not None:
            set_seed(self.seed)
        sentences = [self.generate_random_walk(w[0]) for w in sentences]
        return super()._do_train_job(sentences, alpha, inits)

调用方式

import networkx as nx

# 生成图，df为数据集
G = Graph(df[["user_id", "item_id"]].values.tolist(),directed=False, weighted=False)

# 调用Node2Vec
model = Node2Vec(G, dim=16, walk_length=100, context=5, p=2.0, q=0.5, workers=20)
model.train(epochs=5)