Graph embedding详解

DeepWalk

原论文：DeepWalk: Online Learning of Social Representations

项目代码：https://github.com/phanein/deepwalk

简介

虽然DeepWalk是KDD 2014的工作，但却是我们了解Graph Embedding无法绕过的一个方法。

我们都知道在NLP任务中，word2vec是一种常用的word embedding方法，word2vec通过语料库中的句子序列来描述词与词的共现关系，进而学习到词语的向量表示。

DeepWalk的思想类似word2vec，使用图中节点与节点的共现关系来学习节点的向量表示。那么关键的问题就是如何来描述节点与节点的共现关系，DeepWalk给出的方法是使用随机游走(RandomWalk)的方式在图中进行节点采样。

RandomWalk是一种可重复访问已访问节点的深度优先遍历算法。给定当前访问起始节点，从其邻居中随机采样节点作为下一个访问节点，重复此过程，直到访问序列长度满足预设条件。

获取足够数量的节点访问序列后，使用skip-gram model 进行向量学习。

DeepWalk 核心代码

DeepWalk算法主要包括两个步骤，第一步为随机游走采样节点序列，第二步为使用skip-gram model（word2vec）学习表达向量。

①构建同构网络，从网络中的每个节点开始分别进行Random Walk 采样，得到局部相关联的训练数据； ②对采样数据进行SkipGram训练，将离散的网络节点表示成向量化，最大化节点共现，使用Hierarchical Softmax来做超大规模分类的分类器

DeepWalk 算法原理

语言模型的输入是语料库和词汇表，而 DeepWalk 的输入是一组short random walk 序列和图的顶点

算法

训练与优化

实验

数据集：

• BlogCatalog 数据集：由博客作者提供的社交关系网络。标签代表作者提供的主题类别。
• Flickr 数据集：Flickr网站用户之间的关系网络。标签代表用户的兴趣组，如“黑白照片”。
• YouTube 数据集：YouTube 网站用户之间的社交网络。标签代表用户的视频兴趣组，如“动漫、摔跤”。

Random Walk

我们可以通过并行的方式加速路径采样，在采用多进程进行加速时，相比于开一个进程池让每次外层循环启动一个进程，我们采用固定为每个进程分配指定数量的num_walks的方式，这样可以最大限度减少进程频繁创建与销毁的时间开销。

deepwalk_walk方法对应上一节伪代码中第6行，_simulate_walks对应伪代码中第3行开始的外层循环。最后的Parallel为多进程并行时的任务分配操作。

def deepwalk_walk(self, walk_length, start_node):

    walk = [start_node]

    while len(walk) < walk_length:
        cur = walk[-1]
        cur_nbrs = list(self.G.neighbors(cur))
        if len(cur_nbrs) > 0:
            walk.append(random.choice(cur_nbrs))
        else:
            break
    return walk

def _simulate_walks(self, nodes, num_walks, walk_length,):
    walks = []
    for _ in range(num_walks):
        random.shuffle(nodes)
        for v in nodes:           
            walks.append(self.deepwalk_walk(alk_length=walk_length, start_node=v))
    return walks

results = Parallel(n_jobs=workers, verbose=verbose, )(
    delayed(self._simulate_walks)(nodes, num, walk_length) for num in
    partition_num(num_walks, workers))

walks = list(itertools.chain(*results))

LINE

原论文：LINE: Large-scale Information Network Embedding

模型

一阶邻近度

二阶邻近度

融合

最优化问题

边采样

二阶邻居

新顶点

LINE核心代码

模型和损失函数定义

LINE使用梯度下降的方法进行优化，直接使用tensorflow进行实现，就可以不用人工写参数更新的逻辑了~

这里的 实现中把1阶和2阶的方法融合到一起了，可以通过超参数order控制是分开优化还是联合优化，论文推荐分开优化。

首先输入就是两个顶点的编号，然后分别拿到各自对应的embedding向量，最后输出内积的结果。 真实label定义为1或者-1，通过模型输出的内积和line_loss就可以优化使用了负采样技巧的目标函数了~

def line_loss(y_true, y_pred):
    return -K.mean(K.log(K.sigmoid(y_true*y_pred)))

def create_model(numNodes, embedding_size, order='second'):

    v_i = Input(shape=(1,))
    v_j = Input(shape=(1,))

    first_emb = Embedding(numNodes, embedding_size, name='first_emb')
    second_emb = Embedding(numNodes, embedding_size, name='second_emb')
    context_emb = Embedding(numNodes, embedding_size, name='context_emb')

    v_i_emb = first_emb(v_i)
    v_j_emb = first_emb(v_j)

    v_i_emb_second = second_emb(v_i)
    v_j_context_emb = context_emb(v_j)

    first = Lambda(lambda x: tf.reduce_sum(
        x[0]*x[1], axis=-1, keep_dims=False), name='first_order')([v_i_emb, v_j_emb])
    second = Lambda(lambda x: tf.reduce_sum(
        x[0]*x[1], axis=-1, keep_dims=False), name='second_order')([v_i_emb_second, v_j_context_emb])

    if order == 'first':
        output_list = [first]
    elif order == 'second':
        output_list = [second]
    else:
        output_list = [first, second]

    model = Model(inputs=[v_i, v_j], outputs=output_list)

顶点负采样和边采样

下面的函数功能是创建顶点负采样和边采样需要的采样表。中规中矩，主要就是做一些预处理，然后创建alias算法需要的两个表。

def _gen_sampling_table(self):

    # create sampling table for vertex
    power = 0.75
    numNodes = self.node_size
    node_degree = np.zeros(numNodes)  # out degree
    node2idx = self.node2idx

    for edge in self.graph.edges():
        node_degree[node2idx[edge[0]]
                    ] += self.graph[edge[0]][edge[1]].get('weight', 1.0)

    total_sum = sum([math.pow(node_degree[i], power)
                        for i in range(numNodes)])
    norm_prob = [float(math.pow(node_degree[j], power)) /
                    total_sum for j in range(numNodes)]

    self.node_accept, self.node_alias = create_alias_table(norm_prob)

    # create sampling table for edge
    numEdges = self.graph.number_of_edges()
    total_sum = sum([self.graph[edge[0]][edge[1]].get('weight', 1.0)
                        for edge in self.graph.edges()])
    norm_prob = [self.graph[edge[0]][edge[1]].get('weight', 1.0) *
                    numEdges / total_sum for edge in self.graph.edges()]

    self.edge_accept, self.edge_alias = create_alias_table(norm_prob)

GraRep

原论文：GraRep: Learning Graph Representations with Global Structural Information

模型

GraRep vs SGNS

TADW

原论文：Network Representation Learning with Rich Text Information

大多数网络表示学习方法仅仅研究网络结构。事实上，网络顶点包含了丰富的信息（如文本内容和其它元数据），而这些方法都无法利用到这些信息。

利用顶点的文本信息的一个直接方法是：分别独立学习文本特征representation 和网络顶点representation，然后将二者拼接在一起。这种方法没有考虑网络结构和文本信息之间的复杂交互，因此通常效果一般。

论文《Network Representation Learning with Rich Text Information》 提出了 text-associated DeepWalk:TADW 模型，该模型在矩阵分解的框架下将顶点的文本信息纳入网络表示学习中。

模型

DNGR

原论文：Deep Neural Networks for Learning Graph Representations

虽然 DeepWalk 可以有效的学习无权图的顶点representation ，但是它存在两个缺点：

• 获得vertex-context 的采样过程效率太低，且无法对带权图进行采样。

• SGNS 等价于对 PPMI 矩阵进行矩阵分解，目前广泛使用的 SVD 本质是一种降维工具。

  事实上 SVD 是一种线性降维，无法捕获原始高维空间和representation 低维空间之间的非线性关系。Levy 也证明了：从 SVD 方法中学到的representation 不一定优于 PPMI 矩阵本身作为 representation（参考 word representation 章节）。

针对这两个问题，论文 《Deep Neural Networks for Learning Graph Representations》 提出了 DNGR 模型，该模型主要做了两点改进：

• 采用基于随机游走模型 random surfing model 来直接构建Graph 的结构信息，抛弃了基于随机游走random walk策略生成线性序列的方式。
• 引入stacked denoising autoencoder:SDAE 堆叠式降噪自编码器来分解 PPMI 矩阵，从而进行非线性降维，从而捕获顶点之间的潜在复杂的非线性关系。

模型

Node2Vec

原论文：node2vec: Scalable Feature Learning for Networks

1. feature learning 的挑战是如何定义恰当的目标函数，这涉及计算效率和预测准确率之间的平衡。

   • 一方面可以直接优化下游监督任务的目标函数。
     • 优点：预测准确率高。
     • 缺点：需要估计的参数数量激增，训练时间复杂度较高；且学到的feature representation 是任务相关的，无法广泛应用于其它类型的任务。
   • 另一方面可以精心设计独立于下游监督任务的目标函数。
     • 优点：计算效率较高；且feature representation 是任务无关的，可以广泛应用于下游各种类型的任务。
     • 缺点：应用于下游监督学习任务时预测准确率稍低。

2. 当前的模型和方法无法为无监督学习 graph feature learning 定义一个合理目标函数。

   • 基于线性和非线性的经典无监督学习算法，如 PCA,MDS,IsoMap 及其扩展算法，它们最大化的目标函数为：原始数据在低维空间representation 的方差。

     这些算法具有两个主要缺点：

     • 算法涉及矩阵的特征分解，这对于大型Graph 代价太大，因此可扩展性很差。

     • 这些算法的目标函数隐含着对 Graph 结构的各种假设，如同质性 homophily 或者结构对等性 structural equivalence ，这些假设不一定适合各种类型的 Graph 。

       例如谱聚类的目标函数就有很强的同质假设：图的割cut 有助于分类。该假设在很多场景下是合理的，但是无法推广到所有的 Graph 。

   • 基于邻域关系的无监督学习算法，如 DeepWalk, LINE 及其扩展算法，它们最大化的目标函数为：尽可能在低维空间中保留原始空间中的顶点邻域关系 neighborhood ，即在低维空间中尽可能相似。

     不同的采样策略将导致不同的邻域关系，因此学到不同的顶点表达。实际上并没有一个明确的、更好的采样策略使得采样到的领域关系适合所有网络以及所有任务。这也是 DeepWalk,LINE 等工作的主要缺点：无法为采样过程提供任何的灵活性。

论文 《node2vec: Scalable Feature Learning for Networks》 提出了 node2vec 模型，该模型的目标函数也是：尽可能在低维空间中保留原始空间中的顶点邻域关系 neighborhood 。但是 node2vec 重新定义了邻居这一概念，认为灵活地探索顶点领居是学习更加丰富的顶点表达的关键。

node2vec 通过一个有偏随机游走过程biased random walk procedure 来探索各种类型的邻居，从而能够灵活的根据顶点所属的社区或者顶点在网络中的角色来学习顶点表达。

node2vec 是 DeepWalk,LINE 等算法的进一步扩展。与 DeepWalk,LINE 等死板的搜索方法相比，node2vec 可以通过调节超参数来控制搜索空间，从而产生更加灵活的算法。该超参数具有直观的解释，并决定了不同不同的搜索策略。

• 在多标签分类任务中node2vec 优于最新的方法最高达 26.7%；在链接预测任务中 node2vec 优于最新的方法最高达 12.6% 。
• 在计算效率上 node2vec 主要计算阶段很容易并行化，可以在几个小时内计算扩展到数百万个结点的大型网络。

node2vec 还将单个顶点的表达扩展到成对顶点的表达，即边的表达，使得node2vec 能够同时进行基于顶点的预测任务、基于边的预测任务。

模型

边的representation

算法

node2vec核心代码

node2vecWalk

通过上面的伪代码可以看到，node2vec和deepwalk非常类似，主要区别在于顶点序列的采样策略不同，所以这里我们主要关注node2vecWalk的实现。

由于采样时需要考虑前面2步访问过的顶点，所以当访问序列中只有1个顶点时，直接使用当前顶点和邻居顶点之间的边权作为采样依据。 当序列多余2个顶点时，使用文章提到的有偏采样。

def node2vec_walk(self, walk_length, start_node):
    G = self.G    
    alias_nodes = self.alias_nodes    
    alias_edges = self.alias_edges
    walk = [start_node]
    while len(walk) < walk_length:        
        cur = walk[-1]        
        cur_nbrs = list(G.neighbors(cur))        
        if len(cur_nbrs) > 0:            
            if len(walk) == 1:                
                walk.append(cur_nbrs[alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])])            
            else:                
                prev = walk[-2]                
                edge = (prev, cur)                
                next_node = cur_nbrs[alias_sample(alias_edges[edge][0],alias_edges[edge][1])]                
                walk.append(next_node)        
        else:            
            break
    return walk

构造采样表

def get_alias_edge(self, t, v):
    G = self.G    
    p = self.p    
    q = self.q
    unnormalized_probs = []    
    for x in G.neighbors(v):        
        weight = G[v][x].get('weight', 1.0)# w_vx        
        if x == t:# d_tx == 0            
            unnormalized_probs.append(weight/p)        
        elif G.has_edge(x, t):# d_tx == 1            
            unnormalized_probs.append(weight)        
        else:# d_tx == 2            
            unnormalized_probs.append(weight/q)    
    norm_const = sum(unnormalized_probs)    
    normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs]
    return create_alias_table(normalized_probs)

def preprocess_transition_probs(self):
    G = self.G
    alias_nodes = {}    
    for node in G.nodes():        
        unnormalized_probs = [G[node][nbr].get('weight', 1.0) for nbr in G.neighbors(node)]        
        norm_const = sum(unnormalized_probs)        
        normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs]                 
        alias_nodes[node] = create_alias_table(normalized_probs)
    alias_edges = {}
    for edge in G.edges():        
        alias_edges[edge] = self.get_alias_edge(edge[0], edge[1])
    self.alias_nodes = alias_nodes    
    self.alias_edges = alias_edges
    return

WALKLETS

原论文：Don’t Walk, Skip! Online Learning of Multi-scale Network Embeddings

1. 社交网络本质都是分层的，每个人（顶点）都属于多个社区，这些社区范围从小型社区（如家庭、朋友）、中型社区（如学校、企业）到大型社区（如民族、国家），代表了不同尺度 scale 的关系。

   随着关系尺度的变化，网络的拓扑结构也发生变化。如下图所示：

   • 当考虑家庭、朋友关系这一尺度时只有黄色部分构成一个社区。
   • 当考虑学校、企业关系这一尺度时只有蓝色部分（包括黄色部分）构成一个社区。
   • 当考虑民族、国家关系这一尺度时所有顶点都构成一个社区。

   在这个过程中尺度扮演者关键的角色，它决定了社区的规模以及顶点归属到哪些社区。

   

2. 在网络representation 学习的任务中，大多数方法都是一刀切：每个顶点得到一个融合了所有尺度的representation ，无法明确的捕获网络内结点之间的多尺度关系，因此无法区分网络在各个尺度上的差异。

   GraRep 方法显式的建模多尺度关系，但是计算复杂度太高从而无法扩展到真实世界的大型网络。

   论文 《Don’t Walk, Skip! Online Learning of Multi-scale Network Embeddings》 提出了 WALKLETS 模型，该模型是一种在线的图reprensentation 学习方法，可以捕获网络顶点之间的多尺度关系，并且可扩展性强，支持扩展到百万顶点的大型网络。

   WALKLETS 将每个顶点映射到低维reprensentation 向量，该向量捕获了顶点所属社区的潜在层次结构。在预测时可以用单个尺度 representationi 或者组合多个尺度 representation 来提供顶点更全面的社区关系。

   下图来自于 Cora 引用网络的一个子网络的二维可视化，中心的红色顶点表示源点，顶点颜色代表该顶点和源点的距离：距离越近颜色越红，距离越远颜色越蓝。

   • 左图给出了细粒度 representation 相似度的结果。在这一尺度下，只有源点的直系邻居才是相似的。
   • 右图给出了粗粒度 representation 相似度的结果。在这一尺度下，源点附近的很多顶点都是相似的。

   

3. 我们受到一个事实的启发：通过一个结点可能同时隶属于不同层次的圈子，如家庭、学校、公司等等。针对这些不同的社区进行建模和预测不仅对于了解网络结构至关重要，而且还具有重要的商业价值，如更有效的广告定向。

模型

SDNE

原论文：Structural Deep Network Embedding

1. 网络 representation 学习有以下几个主要挑战：

   • 高度非线性 non-linear：网络的底层结构是高度非线性的，如何设计模型来捕获这种高度非线性相当困难。
   • 保留结构 structure-preserving：如何在低维空间种保留原始网络的全局结构和局部结构也是一个难点。
   • 网络稀疏性 sparsity ：大多数现实世界的网络非常稀疏，仅利用已观察到的有限链接不足以获得效果较好的 representation

2. 高度非线性：过去的几十年提出了很多基于浅层模型的网络embedding 方法，如 IsoMap, Laplacian Eigenmaps(LE), LINE 。由于浅层模型的表达能力有限，所以这些方法很难捕获高度非线性的网络结构，因此得到的是次优（非最优）的网络representation 。

   尽管可以采用核技巧来捕获非线性，但是核技巧本身也是浅层的。

3. 保留结构：有一些方法，如 LINE, GraRep,WALKLETS 尝试分别使用一阶邻近度和高阶邻近度来保留局部结构和全局结构。其做法是分别学习一阶representation 和高阶 representation，然后简单的将二者拼接在一起。

   与在一个统一模型中同时建模局部网络结构和全局网络结构相比，这种方法不是最优的。

4. 论文 《Structural Deep Network Embedding》 提出了 SDNE 模型。

   • 模型利用多个非线性层来捕获非线性的网络结构。这些非线性层的组合将原始数据映射到高度非线性的潜在低维空间中，从而能够捕获到网络结构的高度非线性。

   • 一阶邻近度是直接相连的两个顶点之间的局部的、成对的相似性，它刻画了网络的局部结构。但是由于网络的稀疏性，很多真实存在的链接由于未被观察到所以缺失，这导致仅依赖一阶邻近度不足以描述整个网络。二阶邻近度表示顶点邻域结构的相似性，它刻画了网络的全局结构。

     通过一阶邻近度和二阶邻近度，我们可以很好的刻画网络本地结构和网络全局结构。而 SDNE 模型就利用一阶邻近度和二阶邻近度来保留网络结构。其中使用无监督学习来利用二阶邻近度从而捕获全局网络结构，使用监督学习来利用一阶邻近度从而捕获局部网络结构。

     通过在一个优化目标中同时优化这两者，SDNE 既可以保留局部网络结构，又可以保留全局网络结构。

     同时，由于网络二阶邻近度非零的顶点对比一阶邻近度数量多得多，因此采用二阶邻近度可以提供更多的网络结构信息，这有助于解决网络稀疏性问题。

     如下图所示，二阶邻近度顶点对的数量与一阶邻近度顶点对数量对比：

     

模型

C为误差权值

代码实现

损失函数定义

l_2nd是2阶相似度对应的损失函数，参数beta控制着非零元素的惩罚项系数。y_true和y_pred分别是输入的邻接矩阵和网络重构出的邻接矩阵。

l_1st是1阶相似度对应的损失函数，参数alpha控制着其在整体损失函数中的占比。

def l_2nd(beta):    
    def loss_2nd(y_true, y_pred):        
        b_ = np.ones_like(y_true)        
        b_[y_true != 0] = beta        
        x = K.square((y_true - y_pred) * b_)        
        t = K.sum(x, axis=-1, )        
        return K.mean(t)
    return loss_2nd

def l_1st(alpha):    
    def loss_1st(y_true, y_pred):        
        L = y_true        
        Y = y_pred        
        batch_size = tf.to_float(K.shape(L)[0])        
        return alpha * 2 * tf.linalg.trace(tf.matmul(tf.matmul(Y, L, transpose_a=True), Y)) / batch_size    
    return loss_1st

模型定义

create_model函数创建SDNE模型，l1和l2分别为模型的正则化项系数，模型的输入A为邻接矩阵，L为拉普拉斯矩阵。输出A_为重构后的邻接矩阵，Y为顶点的embedding向量。

函数中两个for循环分别对应encoder和decoder结构。

def create_model(node_size, hidden_size=[256, 128], l1=1e-5, l2=1e-4):    
    A = Input(shape=(node_size,))    
    L = Input(shape=(None,))    
    fc = A    
    for i in range(len(hidden_size)):        
        if i == len(hidden_size) - 1:            
            fc = Dense(hidden_size[i], activation='relu',kernel_regularizer=l1_l2(l1, l2),name='1st')(fc)
        else:            
            fc = Dense(hidden_size[i], activation='relu',kernel_regularizer=l1_l2(l1, l2))(fc)    
    Y = fc    
    for i in reversed(range(len(hidden_size) - 1)):        
        fc = Dense(hidden_size[i], activation='relu',kernel_regularizer=l1_l2(l1, l2))(fc)
    A_ = Dense(node_size, 'relu', name='2nd')(fc)    
    model = Model(inputs=[A, L], outputs=[A_, Y])    
    return model

EOE

原论文：Embedding of Embedding (EOE) : Joint Embedding for Coupled Heterogeneous Networks

1. 大数据时代有大量的相关信息可用，这些信息可以融合成一个耦合的异构网络，其中每种类型的信息可以表示为单个同构子网络。

   这里我们定义耦合异构网络为：两个不同类型但是相互关联的子网络组成的网络。这些子网络通过子网络之间的链接来相互连接。

   例如：

   • 论文引用网络中的author 和 word ：作者可以通过作者之间的交互来链接，单词可以通过单词共现来链接，作者可以通过他们文章的单词来链接。
   • 社交网络中的 user 和 word：类似于论文引用网络中的 author 和 word 。
   • 观影网络中的 customer 和 movie：观众可以通过观众之间的关系来链接，电影可以通过共同的演员或者导演来链接，观众可以通过他们观看的电影来链接。
   • 基因和化合物：基因可以通过基因之间的相互作用来链接，化合物可以通过具有相同的基团关系来链接，基因可以通过 binding 关系和化合物链接。

   为直观说明这个概念，下图实现了author 和 word 网络的例子。其中作者通过 co-authorship 关系来链接，单词通过标题中的共现关系来链接。我们从 DBLP 数据集进行采样，采样的 author 包含 2000 ~2003 年在两个数据挖掘会议 KDD,IDCM 以及两个数据库会议 SIGMOD,VLDB 上发表论文的作者。author 和 word 之间链接用黑线表示。为了更清晰的展示，我们忽略了author 网络内部的边以及 word 网络内部的边，并且绘制的顶点大小和它的 degree 成正比。

   可以看到：

   • author 形成了两个聚类，word 也形成了两个聚类。这些聚类可以通过社团检测算法来生成。

   • 数据挖掘专家到数据挖掘领域单词之间的边，要比数据挖掘专家到数据库领域单词的边更多。

     数据库专家到数据库领域单词之间的边，要比数据库专家到数据挖掘领域单词之变的边更多。

   这说明：作者和单词之间的链接可以在存在作者之间链接的基础上，额外提供补充信息。这是因为相同领域的作者更有可能在其领域内的单词上存在链接，这使得仅仅从作者之间的链接学到的embedding 更加全面和准确。

   当作者之间缺乏链接时（如冷启动时），这种补充信息尤为重要。

   学习单词的embedding 的情况也是类似的。

   

2. 目前存在一些分别作用于author 网络或者word 网络的 embedding 方法，但是从单个网络的 embedding 方法扩展到用于耦合异构网络的 embedding 并不容易。主要挑战在于两个不同网络的异构性，这将导致两个异构的潜在空间latent space，而这两个空间的特征不能直接匹配。

   为解决该问题，论文 《Embedding of Embedding (EOE) : Joint Embedding for Coupled Heterogeneous Networks》 提出了Embedding of Embedding : EOE 方法，该方法通过引入一个调和嵌入矩阵 harmonious embedding matrix 从而将embedding 从一个潜在空间进一步嵌入到另一个潜在空间。

   作为一种 embedding 方法，EOE 使得存在链接的顶点在潜在空间中尽可能接近。但是和现有 embedding 方法相比，EOE 的关键区别在于：在 EOE 方法中存在两个子网络、三种类型的链接、两个潜在空间。此外 EOE 必须同时学习两个子网络的潜在特征，因为任一侧特征都可以通过网络间的链接向另一侧子网络提供补充信息。

3. EOE 模型存在三种类型的参数：两个子网络的 embedding 参数以及调和嵌入矩阵。为了优化目标函数，EOE 提出了一种交替优化算法，其中每次仅针对其中某一种类型的参数进行优化。

   通过这种交替优化的方式，EOE 可以用一系列简单的优化代替对三种参数的比较困难的联合优化。

4. DeepWalk 的随机游走可能会更跨多个社区，这违背了保持网络结构的目标。

CANE

原论文：CANE: Context-Aware Network Embedding for Relation Modeling

1. 一个顶点在和不同的邻居顶点交互时，通常表现出不同的形象aspect 。例如：

   • 一个学者可以和不同的合作者partner 就不同的研究方向进行合作。

     如下图所示：红色、蓝色、绿色字体分别表述左侧学者、右侧学者以及所有学者都关注的研究方向。

   • 一个自媒体作者可以和不同的朋友就不同的兴趣进行分享。

   • 一个网页可以可以因为不同的目的而链接到不同的其它网页。

   

2. 目前的大多数 GraphEmbedding 方法忽略了顶点交互过程中每个顶点的各种角色，仅为每个顶点分配一个统一的向量，这带来两个问题：

   • 它们无法处理顶点针对不同的邻居交互呈现不同aspect 的问题。

   • 它们往往强迫顶点的不同邻居之间的 embedding 也是彼此靠近的，然而事实并非总是如此。

     如上图所示：左侧学者和中间学者的距离较近，右侧学者和中间学者的距离也较近。但是，事实上左侧学者和右侧学者的距离是较远的，因为二者之间共同关注的主题很少。而传统的模型认为它们是彼此接近的，仅仅因为它们都和中间顶点相连。

   这使得顶点的 embedding 没有区分度，无法区分顶点的链接是刻画哪个 aspect 。

   为解决该问题，论文 《CANE: Context-Aware Network Embedding for Relation Modeling》 提出了 Context-Aware Network Embedding:CANE 框架来精确建模顶点之间的关系。

   CANE 假设一个顶点在和不同的邻居顶点交互时表现出不同的角色从而产生不同的 embedding。

   具体而言，CANE 考虑每个顶点包含的丰富的外部信息，如：文本、标签以及其它元数据。传统的Graph embedding 模型忽略了这些上下文信息，因此每个顶点都是静态的embedding 向量。CANE 根据和顶点交互的不同邻居为顶点动态分配一个embedding 向量，这被称作 context-aware embedding 上下文感知向量。CANE 通过attentioin 机制学习顶点的上下文感知向量，从而精确的建模顶点之间的语义关系。

3. 本文仅考虑外部信息为文本的文本信息网络，但是 CANE 可以轻松扩展到其它类型的信息网络。

metapath2vec

原论文：metapath2vec: Scalable Representation Learning for Heterogeneous Networks

1. 目前为止绝大多数embedding 方法都集中在异质网络的表示学习representation learning 上，即网络的顶点类型是单一的，边的类型也是单一的。但是大量的社交网络以及其它信息网络本质上是异质heterogeneous的，网络包含多种顶点类型，也包含多种边的类型。因此异质网络表示学习的挑战在于：网络中存在多种类型的顶点和边。

   传统的 embedding 模型将不同类型的顶点和边采用相同的处理方式，这将导致为异质顶点生成没有类型区分的表示。因此这些异质网络是专门为同质homogeneous网络设计的 embedding 模型无法解决的。

   论文 《metapath2vec: Scalable Representation Learning for Heterogeneous Networks》 首先形式化异质网络的表示学习问题，然后提出了 metapath2vec 框架，及其扩展的 metapath2vec ++ 框架来解决异质网络的表示学习问题。

2. 异质网络表示学习的目的是同时学习多种类型顶点的低维 embedding 。metapath2vec 框架基于meta-path 的随机游走从而构造顶点的异质邻域，然后利用异质 skip-gram 模型来执行顶点 embedding 。metapath2vec 的目标是最大化的保留给定异质网络的结构关系和语义关系。

   而 metapath2vec ++ 在 metapath2vec 的基础上使用了一种基于异质负采样的方法，称作 metapath2vec ++ ，该方法可以有效并且准确的预测顶点的异质邻域。

   大量实验表明，metapath2vec 和 metapath2vec ++ 不仅能够超越各种异质网络挖掘任务的 SOA 的 embedding 模型，还能够识别不同顶点之间的结构相关性和语义相关性。

3. metapath2vec 和 metapath2vec ++ 不同于传统的网络 embedding 模型，后者专注于同质网络。

   metapath2vec 和 metapath2vec++ 在某些方面也不同于 Predictive Text Embedding:PTE 模型。

   • 首先 PTE 是一种半监督学习模型，其中包含文本数据的标签信息。
   • 其次，PTE 中的异质性来自于文本网络，网络中存在了单词到单词的链接、单词到它所属文档的链接、单词及其 label 的链接。 因此本质上 PTE 的原始输入为单词，输出是每个单词的 embedding ，而不是多种类型的输入。

GraphGAN

原论文：GraphGAN: Graph Representation Learning with Generative Adversarial Nets

Struc2Vec

原论文：struc2vec: Learning Node Representations from Structural Identity

1.几乎所有网络中的顶点都具有一个或者多个角色，这些角色很大程度上决定了顶点在网络中的功能。如：社交网络中的成员具有社交角色或者社会地位，而蛋白质网络中的蛋白质具有特定的功能。直觉上看，这些网络中的不同顶点可能具有相同的角色从而发挥相似的作用。如：公司社交网络中的实习生intern 角色，蛋白质网络中的催化剂catalyst 角色。因此，可以根据顶点在网络中的角色来将顶点划分为等效的类别equivalent classe 。

通常识别顶点的角色需要利用顶点的特征或者边的特征，但是仅仅依靠网络结构来识别顶点角色，这更有挑战性。此时，顶点的角色仅仅取决于顶点之间的链接。

确定顶点结构角色的常用方法是基于距离的方法或者基于递归的方法：

• 基于距离的方法：根据每个顶点的邻域信息（如邻域大小，邻域形状）来计算每对顶点之间的距离（邻域越相似则距离越小），然后通过聚类、规则匹配等方式来确定顶点的等效类别。
• 基于递归的方法：构造基于邻域的递归，然后不停迭代直到收敛，并采用最终迭代的结果来确定顶点的等效类别。如 Weisfeiler-Lehman 算法。

为什么这些embedding 方法（如 DeepWalk/node2vec 在分类任务中大获成功，但是在结构等效structural equivalence 任务中难以奏效？原因是大多数真实网络结构中，很多顶点的特征都表现出很强的同质性。如：两个具有相同政治偏好的博客更有可能被连接，而不是随机性的连接。网络中相邻的顶点更可能具有相同的特征，因此在 embedding 空间中趋于靠近；网络中相距较远的顶点可能具有迥异的特征，因此在embedding 空间中趋于分离。这

种性质和顶点的局部结构无关，因此这些 embedding 方法无法捕获结构等效性。因此如果任务更依赖于结构等效性而不是同质性，则这些 embedding 方法容易失败。

论文 《struc2vec: Learning Node Representations from Structural Identity》 提出了一个学习顶点结构等效性的无监督学习框架 struc2vec，它可以根据顶点的局部网络结构来识别structural identity 结构角色。

struc2vec 的关键思想是：

• 不依赖于顶点特征、边的特征、顶点的位置，仅仅依赖于顶点的局部结构来衡量顶点之间的结构相似性。我们也不需要网络是连通的，我们可以识别不同连通分量connected componet 中结构相似的顶点。
• 对结构相似性进行分层 hierarchy ，随着层次的提高结构相似越严格。在层次的底部，degree 相近的顶点之间是结构相似的；在层次的顶部，需要整个网络相似的顶点之间才是结构相似的。
• 采用加权随机遍历一个 multi-layer 图来生成每个顶点的随机上下文。这个 multi-layer 是根据原始网络生成的，multi-layer 图中的边是根据原始图中顶点结构相似性得到。因此有相似上下文的两个顶点很可能具有相似的结构。

2.DeepWalk 使用随机游走从网络中生成顶点序列，并基于 SkipGram 学习顶点 embedding 。网络中接近的顶点将具有相似的上下文，因此具有相似的 embedding 。

node2vec 通过一个有偏的二阶随机游走模型来扩展了这个想法，从而在生成顶点上下文时提供了更大的灵活性。特别的，可以通过设计边的权重从而尝试捕获顶点的同质性和结构等效性。

但是 DeepWalk 和 node2vec 等方法的一个基本缺陷是：结构上相似的顶点如何其距离大于 SkipGram 窗口的大小，则它们永远不会共享相同的上下文。

RolX 是一种仅利用网络结构来明确标识顶点角色的方法。这种无监督方法基于枚举顶点的各种结构特征，然后找到联合特征空间的基向量basis vector，并为每个顶点赋予一个角色分布，这允许顶点具有多个混合的角色。在没有明确考虑顶点结构相似性的情况下，RolX 可能会遗漏结构相似的顶点pair 对。

模型

考虑捕获网络中结构相似性的顶点representation 学习方法，它应该具有预期的特点：

• 顶点之间结构越相似，则顶点的embedding 距离越近。因此如果两个顶点的局部网络结构相同，则它们应该具有相同的 embedding 。
• embedding 的学习不依赖于任何顶点的特征、边的特征、顶点的 label、顶点的位置，仅仅依赖于顶点的局部网络结构。

考虑这两个特点，我们提出了 struc2vec框架，该框架由四个部分组成：

• 结构相似性度量：确定图中每对顶点之间不同大小邻域的结构相似性。这在结构相似性度量中引入了层次 hierarchy ，从而在不同层次水平上衡量结构相似性。
• 加权 multi-layer 图：该图的每一层都包含原始图的所有顶点，每一层对应于hierarchy 结构相似性中的某个层级。层内顶点之间边的权重与结构相似度成反比。
• 上下文生成：基于 multi-layer 图上的有偏随机游走来生成顶点序列，然后为每个顶点生成上下文。这些随机游走序列更可能包含结构相似的顶点。
• 学习embedding：采用一种技术（如 SkipGram ）从顶点序列中学到顶点的 embedding 。

struc2vec 非常灵活，它不要求任何特定的结构相似性度量或者表示学习方法。

相似度定义

顶点对距离定义

构建层次带权图

采样获取顶点序列

三个时空复杂度优化技巧

OPT1 有序度序列长度优化

OPT2 相似度计算优化

OPT3 限制层次带权图层数

核心代码

Struc2Vec的实现相比于前面的几个算法稍微复杂一些，这里我主要说下大体思路，对一些细节有疑问的同学可以邮件或者私信我~

根据前面的算法原理介绍，首先确定一下我们要做哪些事情 1. 获取每一层的顶点对距离 2. 根据顶点对距离构建带权层次图 3. 在带权层次图中随机游走采样顶点序列

顶点对距离计算

def _get_order_degreelist_node(self, root, max_num_layers=None):
    if max_num_layers is None:
        max_num_layers = float('inf')

    ordered_degree_sequence_dict = {}
    visited = [False] * len(self.graph.nodes())
    queue = deque()
    level = 0
    queue.append(root)
    visited[root] = True

    while (len(queue) > 0 and level <= max_num_layers):

        count = len(queue)
        if self.opt1_reduce_len:
            degree_list = {}
        else:
            degree_list = []
        while (count > 0):

            top = queue.popleft()
            node = self.idx2node[top]
            degree = len(self.graph[node])

            if self.opt1_reduce_len:
                degree_list[degree] = degree_list.get(degree, 0) + 1
            else:
                degree_list.append(degree)

            for nei in self.graph[node]:
                nei_idx = self.node2idx[nei]
                if not visited[nei_idx]:
                    visited[nei_idx] = True
                    queue.append(nei_idx)
            count -= 1
        if self.opt1_reduce_len:
            orderd_degree_list = [(degree, freq)
                                  for degree, freq in degree_list.items()]
            orderd_degree_list.sort(key=lambda x: x[0])
        else:
            orderd_degree_list = sorted(degree_list)
        ordered_degree_sequence_dict[level] = orderd_degree_list
        level += 1

    return ordered_degree_sequence_dict

def _compute_ordered_degreelist(self, max_num_layers):

    degreeList = {}
    vertices = self.idx  # self.g.nodes()
    for v in vertices:
        degreeList[v] = self._get_order_degreelist_node(v, max_num_layers)
    return degreeList

def compute_dtw_dist(part_list, degreeList, dist_func):
    dtw_dist = {}
    for v1, nbs in part_list:
        lists_v1 = degreeList[v1]  # lists_v1 :orderd degree list of v1
        for v2 in nbs:
            lists_v2 = degreeList[v2]  # lists_v1 :orderd degree list of v2
            max_layer = min(len(lists_v1), len(lists_v2))  # valid layer
            dtw_dist[v1, v2] = {}
            for layer in range(0, max_layer):
                dist, path = fastdtw(
                    lists_v1[layer], lists_v2[layer], radius=1, dist=dist_func)
                dtw_dist[v1, v2][layer] = dist
    return dtw_dist

def _compute_structural_distance(self, max_num_layers, workers=1, verbose=0,):

    if os.path.exists(self.temp_path+'structural_dist.pkl'):
        structural_dist = pd.read_pickle(
            self.temp_path+'structural_dist.pkl')
    else:
        if self.opt1_reduce_len:
            dist_func = cost_max
        else:
            dist_func = cost

        if os.path.exists(self.temp_path + 'degreelist.pkl'):
            degreeList = pd.read_pickle(self.temp_path + 'degreelist.pkl')
        else:
            degreeList = self._compute_ordered_degreelist(max_num_layers)
            pd.to_pickle(degreeList, self.temp_path + 'degreelist.pkl')

        if self.opt2_reduce_sim_calc:
            degrees = self._create_vectors()
            degreeListsSelected = {}
            vertices = {}
            n_nodes = len(self.idx)
            for v in self.idx:  # c:list of vertex
                nbs = get_vertices(
                    v, len(self.graph[self.idx2node[v]]), degrees, n_nodes)
                vertices[v] = nbs  # store nbs
                degreeListsSelected[v] = degreeList[v]  # store dist
                for n in nbs:
                    # store dist of nbs
                    degreeListsSelected[n] = degreeList[n]
        else:
            vertices = {}
            for v in degreeList:
                vertices[v] = [vd for vd in degreeList.keys() if vd > v]


        results = Parallel(n_jobs=workers, verbose=verbose,)(
            delayed(compute_dtw_dist)(part_list, degreeList, dist_func) for part_list in partition_dict(vertices, workers))
        dtw_dist = dict(ChainMap(*results))

        structural_dist = convert_dtw_struc_dist(dtw_dist)
        pd.to_pickle(structural_dist, self.temp_path +
                     'structural_dist.pkl')

    return structural_dist

构建带权层次图

def _get_transition_probs(self, layers_adj, layers_distances):
    layers_alias = {}
    layers_accept = {}

    for layer in layers_adj:

        neighbors = layers_adj[layer]
        layer_distances = layers_distances[layer]
        node_alias_dict = {}
        node_accept_dict = {}
        norm_weights = {}

        for v, neighbors in neighbors.items():
            e_list = []
            sum_w = 0.0

            for n in neighbors:
                if (v, n) in layer_distances:
                    wd = layer_distances[v, n]
                else:
                    wd = layer_distances[n, v]
                w = np.exp(-float(wd))
                e_list.append(w)
                sum_w += w

            e_list = [x / sum_w for x in e_list]
            norm_weights[v] = e_list
            accept, alias = create_alias_table(e_list)
            node_alias_dict[v] = alias
            node_accept_dict[v] = accept

        pd.to_pickle(
            norm_weights, self.temp_path + 'norm_weights_distance-layer-' + str(layer)+'.pkl')

        layers_alias[layer] = node_alias_dict
        layers_accept[layer] = node_accept_dict

    return layers_accept, layers_alias

def prepare_biased_walk(self,):

    sum_weights = {}
    sum_edges = {}
    average_weight = {}
    gamma = {}
    layer = 0
    while (os.path.exists(self.temp_path+'norm_weights_distance-layer-' + str(layer))):
        probs = pd.read_pickle(
            self.temp_path+'norm_weights_distance-layer-' + str(layer))
        for v, list_weights in probs.items():
            sum_weights.setdefault(layer, 0)
            sum_edges.setdefault(layer, 0)
            sum_weights[layer] += sum(list_weights)
            sum_edges[layer] += len(list_weights)

        average_weight[layer] = sum_weights[layer] / sum_edges[layer]

        gamma.setdefault(layer, {})

        for v, list_weights in probs.items():
            num_neighbours = 0
            for w in list_weights:
                if (w > average_weight[layer]):
                    num_neighbours += 1
            gamma[layer][v] = num_neighbours

        layer += 1

    pd.to_pickle(average_weight, self.temp_path + 'average_weight')
    pd.to_pickle(gamma, self.temp_path + 'gamma.pkl')

随机游走采样

def _exec_random_walk(self, graphs, layers_accept,layers_alias, v, walk_length, gamma, stay_prob=0.3):
    initialLayer = 0
    layer = initialLayer

    path = []
    path.append(self.idx2node[v])

    while len(path) < walk_length:
        r = random.random()
        if(r < stay_prob):  # same layer
            v = chooseNeighbor(v, graphs, layers_alias,
                               layers_accept, layer)
            path.append(self.idx2node[v])
        else:  # different layer
            r = random.random()
            try:
                x = math.log(gamma[layer][v] + math.e)
                p_moveup = (x / (x + 1))
            except:
                print(layer, v)
                raise ValueError()

            if(r > p_moveup):
                if(layer > initialLayer):
                    layer = layer - 1
            else:
                if((layer + 1) in graphs and v in graphs[layer + 1]):
                    layer = layer + 1

    return path

GraphWave

原论文：Learning Structural Node Embeddings via DiffusionWavelets

NetMF

原论文：Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec

NetSMF

原论文：NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization

PTE

原论文：PTE:Predictive Text Embedding through Large-scale Heterogeneous Text Networks

1. 传统的词袋模型bag-of-word:BOW 忽略了不同单词之间的语义相关性，因此存在诸如数据稀疏性sparsity 、一词多义polysemy、同义词synonymy 之类的问题。单词的分布式 representation 通过在低维空间中嵌入单词来有效缓解该问题。

   单词的embedding 有两种方式：

   • 基于无监督学习的文本 embedding 通用性更强，可应用于各种类型的任务中。典型的无监督文本 embedding 方法包括 SkipGram、Paragraph Vector 等。
   • 基于监督学习的文本 embedding 效果更好，因为它可以充分利用task-specific 的标记信息。典型的监督学习方法有 CNN 神经网络。

   无监督文本 embedding 方法具有很多优点：

   • 首先，深度神经网络，尤其是 CNN，在训练中需要大量的计算。
   • 其次，CNN 网络通常需要大量的标记数据，而这在很多任务中是不现实的。
   • 最后，CNN 的训练需要对很多超参数进行调优，这对专家而言非常耗时、对非专家而言甚至不可行。

   但是和监督学习相比，无监督文本 embedding 方法在 task-specific 上的预测效果较差。原因是这些文本 embedding 在学习文本embedding 过程中没有利用任务中的任何标记信息。

2. 论文 《PTE:Predictive Text Embedding through Large-scale Heterogeneous Text Networks》 提出了 Predictive Text Embedding:PTE 方法，它同时具有无监督文本 embedding 计算量小、标记数据需求低、无需复杂调参的优点，同时也利用了task-specific 标记信息。

   PTE 是一种半监督学习方法，它可以从有限的标记数据和大量的未标记数据中共同学习单词的有效低维 representation。

3. PTE 首先通过 word-word、word-doc、word-label 不同level 级别的共现构建一个大规模的异质文本网络 Heterogeneous Text Network ，然后将该异质网络嵌入到低维向量空间。PTE 通过在低维向量空间中保持顶点之间的二阶邻近度来学习顶点的 embedding 。

   这种低维 embedding 不仅保留了单词和文档之间的语义关系，还对task-specific 具有很好的预测能力。

   一旦学到单词的 embedding，我们可以将句子/文档中单词 embedding 的均值作为句子/文档的 embedding 。

   我们在真实语料库上进行广泛实验，结果表明：

   • 在各种文本分类任务中，PTE 的文本 embedding 都远远优于最新的无监督 embedding 方法
   • 在和 CNN 的对比中，PTE 在长文本上效果更好、在短文本上效果和 CNN 相差无几。但是 PTE 计算效率更高、可以有效应用大规模未标记数据，并且对模型的超参数敏感性较低。

4. 监督学习方法和无监督学习方法的主要区别在于如何在学习阶段利用标记信息和未标记信息。在 representation learning 阶段：

   • 无监督学习不包含任何标记信息，仅在学到数据的representation 之后，才使用标记信息来训练下游的分类器。

   • 监督学习直接在学习过程中使用标记信息。

     另外，监督学习也可以间接地使用未标记数据：通过无监督方法来预训练单词的 embedding 。

   和这两种方式相比，PTE 通过半监督方法来学习文本 embedding ：在学习阶段直接利用少量的标记数据和大量的未标记数据。

5. DeepWalk 和 LINE 均为无监督学习方法，它们只能处理同质网络。PTE 扩展了 LINE 方法从而能够处理异质网络，并且能够融合监督信息。

模型

HNE

原论文：Heterogeneous Network Embedding via Deep Architecture

社交网络中包含Graph 以及相关的数据，如何学到数据的representation 具有挑战：

• 首先，社交网络上的数据规模呈指数型增长
• 其次，社交网络上的数据类型多种多样，不仅包含文本，还有图像、视频。
• 最后，社交网络上的数据并不是孤立的，而是相互产生关联。这些关联可以通过数据之间的链接来显式或隐式的构成：
  • 显式关联：如果文本和图像出现在同一个网页中，则该文本和图像之间构成显式关联；如果两个网页之间存在超链接，则这两个网页之间存在显式关联。
  • 隐式关联：用户的活动可以视为隐式反馈，它提供了数据之间的隐式关联。例如，如果用户使用相似的 tag 描述了多张图片，那么这些图片之间存在隐式的语义关联。

因此，如此大规模的数据导致异常复杂的异质网络heterogeneous network，这对学习数据的统一表达提出了巨大挑战。

为解决该问题，论文 《Heterogeneous Network Embedding via Deep Architectures》 提出了一种被称作异质网络嵌入 Heterogeneous Network Embedding:HNE 的新的方法来学习学习网络的representatioin 。

• HNE 方法同时考虑顶点的内容信息和顶点之间的链接信息。
• HNE 将不同的异质顶点映射到一个统一的潜在空间中，以便可以直接比较不同类型的顶点。

模型

线性 HNE

深度 HNE

1. 在前面的介绍中，我们将不同的异质顶点映射到统一的低维潜在空间。但是，这类 embedding 函数是线性的，缺乏对复杂网络进行建模的能力。这里我们引入深度学习框架。

   前面部分我们的解决方案可以分为两个步骤：

   • 手动构造顶点的特征表示：对于文本顶点，使用其 TF-IDF 向量；对于图像顶点，使用其原始 RGB 像素点拼接而成的向量。
   • 将不同的特征表示嵌入到公共的低维空间中。

   这里我们通过深度学习将特征表示的学习、公共空间的嵌入合并为一步。

AANE

原论文：Accelerated Attributed Network Embedding

在很多实际应用中，网络顶点通常会伴随着一组丰富的属性或特征，即属性网络 attributed network。因此，在对顶点embedding 建模的过程中考虑顶点属性会有所帮助，即 attributed network embedding:ANE 。但是，ANE 在以下三个方面具有挑战性：

• 算法复杂度：较高的算法复杂度限制了某些 ANE 算法在实际任务中的应用。已有一些算法基于网络的结构信息和属性信息来学习顶点embedding，但是这些算法要么在每个迭代step 中使用了 O(n^3) 复杂度的特征值分解， 要么使用了收敛速度很慢的梯度下降。

• heterogeneous 异质信息：由于同时引入了结构信息和属性信息，因此如何在网络的结构和属性的联合空间中评估顶点的邻近度（即距离）是一个挑战。

  另外，随着网络规模的扩大，顶点的属性邻近度矩阵通常非常庞大，难以存储到单台计算机上，更别提对它进行操作。

• 噪音：网络结构信息和顶点属性信息可能都是残缺的、带噪音的，这进一步加入了顶点 embedding 学习的难度。

因此，现有方法无法直接应用于 scalable 的 attributed network embedding 。为解决该问题，论文 《Accelerated Attributed Network Embedding》 提出了一种加速属性网络 embedding 算法 accelerated attributed network embedding:AANE 。

一方面， AANE 将顶点属性纳入到顶点 embedding 过程中；另一方面，AANE 提出了一种分布式优化算法，该算法将复杂的建模和优化过程分解为很多子问题，从而能够以分布式方式完成联合学习。

模型