精华内容
下载资源
问答
  • SDNE(Structural Deep Network Embedding )的原理,实现与应用
    千次阅读
    2020-10-18 17:22:26

    SDNE基本思想

    SDNE(Structural Deep Network Embedding )主要目标是保持网络的一阶相似性和二阶相似性。(相似性定义参考 【Graph Embedding】LINE的原理、核心代码及其应用

    一阶相似度指:具有边相连的节点的Embedding向量具有相似性。主要反映了 Graph 的局部特征

    二阶相似性指:拥有共同邻居但不是直接相连的两个顶点之间应该具有相似性。反映了 Graph 的全局特征。

    SDNE模型的结构图如下:

    在这里插入图片描述

    模型主要包括两个部分:无监督和有监督部分。其中,无监督部分是一个深度自编码器用来学习二阶相似度,监督部分是一个拉普拉斯特征映射捕获一阶相似度。

    二阶相似度(无监督)

    在这里插入图片描述

    如上图所示,这是一个自编码器,没有标签数据,是一种无监督学习。

    模型的输入 x i , x_i, xi本质是节点 i i i 的邻接矩阵,则输入每一个 x i x_i xi都包含了顶点 i i i的邻居结构信息。因此结构相似的顶点可以学习到相似的 embedding 向量,不断优化代价函数来捕捉全局结构特征,即二阶相似度

    输出是 x ^ i \hat x_i x^i,是重构后的邻接矩阵。其目标是:
    f ( x ) ≈ x f(x) \approx x f(x)x
    所以,二阶相似度损失函数定义为:
    L = ∑ i = 1 n ∣ ∣ x i ^ − x i ∣ ∣ 2 2 \mathcal{L}=\sum_{i=1}^n{||\hat{x_i}-x_i||^2_2} L=i=1nxi^xi22
    由于网络的稀疏性,邻接矩阵中的0元素远多于非0元素,使用邻接矩阵作为输入的话要处理很多0,这样就做了太多无用功了。为了解决这个问题,对损失函数做了改进如下:
    L 2 n d = ∑ i = 1 n ∣ ∣ ( x i ^ − x i ) ⊙ b i ∣ ∣ 2 2 = ∣ ∣ X ^ − X ⊙ B ∣ ∣ F 2 \mathcal{L_{2nd}}=\sum_{i=1}^n||(\hat{x_i}-x_i)\odot{b_i}||^2_2=||\hat{X}-X\odot{B}||^2_F L2nd=i=1n(xi^xi)bi22=X^XBF2
    其中 ⊙ \odot 是哈马达乘积,表示对应元素相乘。 邻接矩阵中的0对应 b = 1 b=1 b=1, 非0元素的 b > 1 b>1 b>1,这样的目的是对于有边连接的节点增加惩罚。可以理解为对有边连接的节点赋予更高权重。

    在模型中,从 x i x_i xi y i ( K ) y_i^{(K)} yi(K)是编码器,从 y i ( K ) y_i^{(K)} yi(K) x ^ i \hat x_i x^i是解码器, y i ( K ) y_i^{(K)} yi(K)是节点 i i i的Embedding向量,编码器的公式为:
    y i ( 1 ) = σ ( W ( 1 ) x i + b ( 1 ) ) , y i ( k ) = σ ( W ( k ) y i ( k − 1 ) + b ( k ) ) , k = 2 , . . . , K y_i^{(1)}=\sigma{(W^{(1)}x_i+b^{(1)})}, \\ y_i^{(k)}=\sigma{(W^{(k)}y_i^{(k-1)}+b^{(k)})}, k=2,...,K yi(1)=σ(W(1)xi+b(1)),yi(k)=σ(W(k)yi(k1)+b(k)),k=2,...,K
    其中, W ( k ) \mathbf W^{(k)} W(k)为第 k k k层的参数矩阵, b k b^k bk为第 k k k层的偏置项。

    一阶相似度(有监督)

    在介绍一阶相似度之前先来了解一下拉普拉斯映射(Laplacian Eigenmap),其目的是降维,目标函数如下:
    ∑ i , j W i j ∣ ∣ y i − y j ∣ ∣ 2 \sum_{i,j}\mathbf W_{ij}||y_i - y_j||^2 i,jWijyiyj2
    再看结构图,一阶相似度下图的(1)所示:

    在这里插入图片描述

    前面提到过 y i ( K ) y_i^{(K)} yi(K)是节点 i i i的Embedding向量,若顶点 v i v_i vi v j v_j vj之间存在边,那他们的Embedding的结果 y ( K ) y^{(K)} y(K)应该也很接近,所以,借助拉普拉斯的思想,其一阶相似度为:
    L 1 s t = ∑ i , j = 1 n s i , j ∣ ∣ y i ( K ) − y j ( K ) ∣ ∣ 2 2 = ∑ i . j = 1 n s i , j ∣ ∣ y i − y j ∣ ∣ 2 2 \mathcal{L_{1st}}=\sum_{i,j=1}^n{s_{i,j}||y_i^{(K)}-y_j^{(K)}||^2_2}=\sum_{i.j=1}^n{s_{i,j}||y_i-y_j||^2_2} L1st=i,j=1nsi,jyi(K)yj(K)22=i.j=1nsi,jyiyj22
    最小化 L 1 s t \mathcal{L_{1st}} L1st,可以使得一条边的两个节点在嵌入空间中的表示相对接近。

    为了防止过拟合,加入正则化,所以,SDNE的loss为:
    L m i x = L 2 n d + α L 1 s t + ν L r e g = ∣ ∣ ( X ^ − X ) ⊙ B ∣ ∣ F 2 + α ∑ i . j = 1 n s i , j ∣ ∣ y i − y j ∣ ∣ 2 2 + ν L r e g \mathcal{L_{mix}}=\mathcal{L_{2nd}+\alpha{\mathcal{L_{1st}}}}+\nu{\mathcal{L_{reg}}} =||(\hat{X}-X)\odot{B}||^2_F+\alpha{\sum_{i.j=1}^n{s_{i,j}||y_i-y_j||^2_2}}+\nu{\mathcal{L_{reg}}} Lmix=L2nd+αL1st+νLreg=(X^X)BF2+αi.j=1nsi,jyiyj22+νLreg
    其中,正则化 L r e g \mathcal{L_{reg}} Lreg的计算公式如下:
    L r e g = 1 2 ∑ k = 1 k ( ∣ ∣ W ( k ) ∣ ∣ F 2 + ∣ ∣ W ^ k ∣ ∣ F 2 ) \mathcal{L_{reg}}=\frac{1}{2}\sum_{k=1}^k({||W^{(k)}||^2_F+||\hat{W}^{k}||_F^2}) Lreg=21k=1k(W(k)F2+W^kF2)
    α \alpha α为控制1阶损失的参数, ν \nu ν为控制正则化项的参数。

    核心代码

    代码来源 代码来源 GraphEmbeddingsdne-keras
    损失函数

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

    def l_2nd(beta):    
        def loss_2nd(y_true, y_pred):
            # 生成 b_,y_true中为0的部分对应的b_i = 0,y_true中不为0的部分对应的b_i = beta,
            b_ = np.ones_like(y_true)        
            b_[y_true != 0] = beta 
            
            # 计算loss
            x = K.square((y_true - y_pred) * b_)        
            t = K.sum(x, axis=-1, )        
            return K.mean(t)
        return loss_2nd
    
    

    l_1st是1阶相似度对应的损失函数。

    def edge_wise_loss(true_y, embedding_diff):
        return K.mean(K.sum(K.square(embedding_diff), axis=1))  # mean sqaure error
    
    

    模型定义

    核心代码如下:

    # INPUT
    # 边的一个顶点 a 
    input_a = Input(shape=(1,), name='input-a', dtype='int32')
    # 边的另一个顶点 b
    input_b = Input(shape=(1,), name='input-b', dtype='int32')
    edge_weight = Input(shape=(1,), name='edge_weight', dtype='float32')
    
    # 定义编码器、解码器的层数组
    encoding_layers = []
    decoding_layers = []
    
    # 用 embedding_layer 保持邻接矩阵
    embedding_layer = Embedding(output_dim=self.N, input_dim=self.N,
                                trainable=False, input_length=1, name='nbr-table')
    # if you don't do this, the next step won't work
    embedding_layer.build((None,))
    embedding_layer.set_weights([self.adj_mat])
    
    encoding_layers.append(embedding_layer)
    encoding_layers.append(Reshape((self.N,)))
    
    # 构造编码器
    encoding_layer_dims = [encode_dim]
    
    for i, dim in enumerate(encoding_layer_dims):
        layer = Dense(dim, activation='sigmoid',
                        kernel_regularizer=regularizers.l2(l2_param),
                        name='encoding-layer-{}'.format(i))
        encoding_layers.append(layer)
    
    # 构造解码器
    decoding_layer_dims = encoding_layer_dims[::-1][1:] + [self.N]
    for i, dim in enumerate(decoding_layer_dims):
        activation = 'sigmoid'
        layer = Dense(
            dim, activation=activation,
            kernel_regularizer=regularizers.l2(l2_param),
            name='decoding-layer-{}'.format(i))
        decoding_layers.append(layer)
    
    # 构造整个网络
    all_layers = encoding_layers + decoding_layers
    
    # 取出节点 a 与节点 b 的 embedding 向量
    # reduce 函数将 input_a 作为数组 encoding_layers 中每一个 Layer 的输入
    # 然后将每个 layer 的输出值作为下一个 layer 的输入,直到编码器层结束
    encoded_a = reduce(lambda arg, f: f(arg), encoding_layers, input_a)
    encoded_b = reduce(lambda arg, f: f(arg), encoding_layers, input_b)
    
    # 得到节点的重构矩阵
    decoded_a = reduce(lambda arg, f: f(arg), all_layers, input_a)
    decoded_b = reduce(lambda arg, f: f(arg), all_layers, input_b)
    
    # 将两个节点的 embedding 向量做减法
    embedding_diff = Subtract()([encoded_a, encoded_b])
    
    # 为差值添加权重
    embedding_diff = Lambda(lambda x: x * edge_weight)(embedding_diff)
    
    # 构建模型
    self.model = Model([input_a, input_b, edge_weight],
                        [decoded_a, decoded_b, embedding_diff])
    
    # 构建损失函数
    reconstruction_loss = build_reconstruction_loss(beta)
    
    # 构建模型
    self.model.compile(optimizer='adadelta',
                        loss=[reconstruction_loss, reconstruction_loss, edge_wise_loss],
                        loss_weights=[1, 1, alpha]) # 损失函数权重
    # 构建模型
    self.encoder = Model(input_a, encoded_a)
    
    # 构建模型
    self.decoder = Model(input_a, decoded_a)
    self.decoder.compile(optimizer='adadelta',
                            loss=reconstruction_loss)
    
    

    库实现

    github仓库: GraphEmbedding

    使用教程:

    将项目clone到本地,依次执行:

    python setup.py install
    cd examples
    python deepwalk_wiki.py
    123
    

    接口:

    G = nx.read_edgelist('../data/wiki/Wiki_edgelist.txt',create_using=nx.DiGraph(),nodetype=None,data=[('weight',int)])#read graph
    
    model = SDNE(G,hidden_size=[256,128]) #init model
    model.train(batch_size=3000,epochs=40,verbose=2)# train model
    embeddings = model.get_embeddings()# get embedding vectors
    

    应用—阿里凑单算法

    SDNE的一个重要应用是阿里凑单算法,例如满400减50,当购物车商品金额不足400时,就需要进行凑单。

    算法框架图如下:

    在这里插入图片描述

    主要步骤如下:

    (1)如何构建了带权重的概率图

    构建的graph是带权重的商品网络,节点:商品,边:商品间共同购买的关系,权重:共同购买次数、购买时间。

    模型的输入是一个带权图,Graph定义:G = (V,E,W),V = vertex (顶点或者节点,在bundle的问题中,特指商品),E = edge(边,在bundle的问题中,特指共同购买) ,W = weight(边的权重,共同购买的次数、时间)。

    (2)基于带权重的采样

    传统的方法,比如deep walk,它的Sampling本质上是有两部分,首先,通过random walk的方式进行游走截断,其次,在仍给word2vec中Skip-Gram模型进行embedding之前,用negative sampling的方式去构造样本;这种随机采样的方法会大概率的将热门节点采集为负样本,这种方式适用于语言模型,因为在自然语言中,热门的单词均为无用单词(比如he、she、it、is、the)。对于我们的商品网络,刚好相反,热门商品往往是最重要的样本,如果采用negative sampling的方式去构造样本,模型肯定是学不出来。因此,我们基于边的权重去采样(weighted walk),使采样尽量往热门节点方向游走,以下图为例:

    在这里插入图片描述

    举个例子来说,假设游走2步,从节点A出发,随机取下一个邻居节点时,如果是random walk算法,它会等概率的游走到B或C节点,但是我们的算法会以7/8的概率取节点C,再会以8/12的概率游走到节点D,最终很大概率上会采出来一条序walk=(A,C,D),对于原始graph,A和D是没有关联的,但是通过weighted walk,能够有效的挖掘出A和D的关系。

    基于带权重的采样(weighted walk)作为正样本的候选,负样本从用户非购买行为中随机抽样;

    (3)Embedding

    将基于weighted walk采出来的序,构造成item-item的pair对,送给embedding模型,我们构造了一个有监督embedding模型(DNN),规避无监督模型无法离线评估模型效果的问题。模型结构如下图。

    在这里插入图片描述

    每一对商品都输出一个 score,上线之后,取出 topN 个 score 较高的关联商品进行推荐。

    参考:

    Structural Deep Network Embedding

    SDNE:《Structral Deep Network Embedding》阅读笔记

    大话深度信念网络(DBN)

    阿里凑单算法首次公开!基于Graph Embedding的打包购商品挖掘系统解析

    更多相关内容
  • KDD 2016 | SDNE:结构化深层网络嵌入

    千次阅读 2022-01-22 09:52:39
    KDD 2016 | SDNE:结构化深层网络嵌入

    前言

    在这里插入图片描述
    题目: Structural Deep Network Embedding
    会议: KDD 2016
    论文地址:Structural Deep Network Embedding

    这是继node2vecDeepWalkLINE后解读的第四篇图嵌入论文。

    SDNE和node2vec属于并行研究,二者同时发表在了KDD 2016上。在此之前,除了一些经典的图嵌入或降维算法,如多维标度(MDS)、IsoMap、局部线性嵌入(LLE)和拉普拉斯特征映射,业界主要使用的方法有DeepWalk和LINE。DeepWalk更倾向于具有更高二阶邻近度的节点产生类似的低维表示,LINE则是同时保留了一阶和二阶邻近度。

    然而,无论是DeepWalk还是LINE,它们都是浅层模型,很难捕捉高度非线性的网路结构。众所周知,深度神经网络在挖掘非线性特征这一块有着很好的效果,本文也是受此启发,利用自编码器开发了一个结构化的深层网络嵌入模型SDNE。

    为了保持局部和全局网络结构,同时也为了让模型对稀疏网络具有鲁棒性,与LINE一样,SDNE也同时考虑了一阶和二阶邻近。本文的很多实验结论与LINE中的完全一致(一个字没变),这也证明了同时考虑一阶和二阶邻近的必要性。

    除了LINE采用浅层模型,SDNE采用深层神经网络结构外,SDNE与LINE最大的不同在于如何结合一阶和二阶邻近。在LINE中,为了得到一个既保持了一阶邻近度也保持了二阶邻近度的LINE模型,作者提出了一个办法:分别训练保持一阶邻近度和二阶邻近度的LINE模型,然后将这两种方法训练的嵌入结果连接到每个顶点上。 而在SDNE中,作者直接利用一个损失函数将二者结合起来,然后联合优化。

    值得一提的是,LINE的作者(北大)也提到过想要将一阶和二阶邻近联合起来进行优化,但作者只是说希望将其作为未来的研究方向。然后过了一年,也就是2016年,清华大学的研究团队便发表了这篇论文。

    除此之外,本文还介绍了precision@k、Mean Average Precision (MAP) 、Micro-F1以及Macro-F1这四个图领域常用的评价指标,这点需要掌握。

    理解SDNE需要用到自编码器的知识,因此阅读本文前建议先阅读自编码器(AutoEncoder)

    摘要

    现有的网络嵌入方法几乎都采用浅层模型。然而,由于底层网络结构复杂,浅层模型无法捕捉高度非线性的网络结构。因此,如何找到一种能够有效捕获高度非线性网络结构并保持全局和局部结构的方法是一个开放而重要的问题。为了解决这一问题,本文提出了一种结构化深度网络嵌入方法,即SDNE。

    具体来说,本文首先提出了一个半监督深度模型,该模型具有多层非线性函数,因此能够捕获高度非线性的网络结构。然后,联合利用一阶和二阶邻近度来保持网络结构:无监督组件使用二阶邻近来捕获全局网络结构,一阶邻近度作为监督分量中的监督信息。通过在半监督深度模型中对它们进行联合优化,SDNE可以保持局部和全局网络结构,并且对稀疏网络具有鲁棒性。

    1. 引言

    网络嵌入主要面临以下挑战:

    1. 高度非线性:网络的底层结构是高度非线性的,如何设计一个模型来捕捉高度非线性的结构是相当困难的。
    2. 结构保持:网络的底层结构非常复杂,顶点的相似性取决于局部和全局网络结构。因此,如何同时保持局部和全局结构是一个难题。
    3. 稀疏性:许多现实世界的网络通常非常稀疏,仅利用非常有限的观测链路不足以达到令人满意的性能。

    现有的许多网络嵌入方法均采用了浅层模型,如IsoMAP、拉普拉斯特征映射(LE)和LINE,但浅层模型的表示能力有限,它们很难捕捉高度非线性的网络结构。尽管有些方法采用了核技术,但核方法也是浅层模型。

    在本文提出的模型中,设计了一个由多个非线性函数组成的多层体系结构。多层非线性函数的组合可以将数据映射到高度非线性的表示空间,从而能够捕获高度非线性的网络结构。

    同时,为了解决深度模型中的结构保持和稀疏性问题,进一步提出将一阶和二阶邻近度结合到学习过程中。实际上,在LINE中,也提出了将一阶和二阶邻近度结合来保持局部和全局网络结构,同时保持对稀疏网络的鲁棒性。

    本文贡献:

    1. 提出了SDNE,该方法能够将数据映射到高度非线性的潜在空间以保持网络结构,并且对稀疏网络具有鲁棒性。
    2. 提出了一个新的具有半监督结构的深度模型,该模型同时优化了一阶和二阶邻近。因此,学习到的表示保留了局部和全局网络结构,并且对稀疏网络具有鲁棒性。
    3. 实验结果证明,SDNE在多标签分类、重建、链接预测和可视化方面具有良好的实用性。

    2. 相关工作

    2.1 深度神经网络

    深度神经网络的最新进展表明,它们具有强大的表示能力,可以为许多类型的数据生成非常有用的表示。但目前的研究工作很少有利用深度模型来学习网络的潜在表示。

    2.2 网络嵌入

    现有的模型都是浅层模型,无法捕获高度非线性的网络结构。

    3. SDNE

    3.1 问题定义

    G = ( V , E ) G=(V, E) G=(V,E) V = { v 1 , . . . , v n } V=\left \{ v_1,...,v_n \right \} V={v1,...,vn} E = { e i j } i , j = 1 n E=\left \{ e_{ij} \right \}_{i,j=1}^{n} E={eij}i,j=1n v i v_i vi v j v_j vj间如果没有边存在,则 s i j = 0 s_{ij}=0 sij=0,否则:如果为无权图, s i j = 1 s_{ij}=1 sij=1,如果为有权图, s i j > 0 s_{ij}>0 sij>0

    一阶邻近度:如果 s i j > 0 s_{ij}>0 sij>0 v i v_i vi v j v_j vj间存在正的一阶邻近度,否则 v i v_i vi v j v_j vj间一阶邻近度为0。

    二阶邻近度:一对节点之间的二阶邻近度描述了这对顶点的邻域结构的接近度。 令 N u = { s u , 1 , . . . , s u , ∣ V ∣ } N_u=\left \{s_{u,1},...,s_{u,|V|} \right \} Nu={su,1,...,su,V}表示 v u v_u vu与其他节点间的一阶邻近度,那么两个节点间的二阶邻近度就是它们一阶邻近度的相似度量。

    本文研究问题定义:给定图 G = ( V , E ) G=(V,E) G=(V,E),目标是找到每一个节点 v i v_i vi d d d维向量表示 y i ∈ R d y_i \in R^d yiRd,这里 d < < ∣ V ∣ d<<|V| d<<V y i y_i yi同时保留了节点间的一阶邻近度和二阶邻近度。

    3.2 模型

    3.2.1 框架

    本文提出了一个半监督深度模型来执行网络嵌入,结果如下所示:
    在这里插入图片描述
    后面再详细解释这个框架。

    3.2.2 损失函数

    一些术语定义:
    在这里插入图片描述
    下面介绍上述框架怎么来保持二阶邻近度:给定一个图 G = ( V , E ) G=(V,E) G=(V,E),我们很容易获得它的邻接矩阵 S = { s i j } i , j = 1 n = { s 1 , . . . , s ∣ V ∣ } S=\left \{s_{ij} \right \}_{i,j=1}^n=\left \{s_{1},...,s_{|V|} \right \} S={sij}i,j=1n={s1,...,sV},其中每一个 s i s_i si都是一个向量。

    为了来保证二阶邻近度,作者扩展了自编码器。关于自编码器,自编码器(AutoEncoder)中比较详细地介绍,这里简单回顾一下。

    自编码器包含两个部分:编码器和解码器,编码器由多个非线性函数组成,这些函数将输入数据映射到表示空间,解码器同样包括多个非线性函数,将表示空间中的表示映射到重构空间

    这时候再来看看上面的框架:
    在这里插入图片描述
    对于一个顶点 v i v_i vi,首先需要初始化一个 x i x_i xi向量,经过一个中间隐层(非线性函数)后,变为 y i ( 1 ) y_i^{(1)} yi(1),然后一直变换,直到通过K个隐层后, x i x_i xi将被映射到表示空间,即变为 y i ( K ) y_i^{(K)} yi(K),然后经过一层层解码, x i x_i xi将被映射到重构空间,即变为 x ^ i \hat{x}_i x^i

    变化过程如下:
    y i ( 1 ) = σ ( W ( 1 ) x i + b ( 1 ) ) y i ( k ) = σ ( W ( k ) x k − 1 + b ( k ) ) y_i^{(1)}=\sigma(W^{(1)}x_i+b^{(1)})\\ y_i^{(k)}=\sigma(W^{(k)}x_{k-1}+b^{(k)}) yi(1)=σ(W(1)xi+b(1))yi(k)=σ(W(k)xk1+b(k))
    经过 K K K次变换,我们得到了 y i ( K ) y_i^{(K)} yi(K)。然后我们反转编码器的运算过程,就能得到一个与 x i x_i xi大小一致的向量 x ^ i \hat{x}_i x^i

    自编码器的目标是最小化重建损失,即最小化 x i x_i xi x ^ i \hat{x}_i x^i间的不同:
    L = ∑ i = 1 n ∣ ∣ x ^ i − x i ∣ ∣ 2 2 L=\sum_{i=1}^n||\hat{x}_i-x_i||_2^2 L=i=1nx^ixi22
    尽管最小化重建损失并不能明确地保持样本之间的相似性,但重建准则可以顺利捕获数据流形,从而保持样本之间的相似性。

    回到本文,如果使用 s i s_i si作为输入,也就是 x i = s i x_i=s_i xi=si因为每个 s i s_i si表征了顶点 v i v_i vi的邻域结构,因此,重构过程将使得具有相似邻域结构的顶点具有相似的潜在表示。 这句话算是SDNE的核心了。

    由于网络的稀疏性,邻接矩阵 S S S中非零元素的数量远小于零元素的数量,如果直接使用 S S S作为自动编码器的输入,它更容易在 S S S中重建零元素,但这不是我们想要的。为了解决这个问题,作者对非零元素的重构误差施加了比零元素更大的惩罚,修订后的目标函数如下所示:
    在这里插入图片描述
    其中 ⊙ \odot 表示对应元素相乘, b i = { b i , j } j = 1 n b_i=\left \{b_{i,j} \right \}_{j=1}^n bi={bi,j}j=1n,如果 s i , j = 0 , 则 b i , j = 1 s_{i,j}=0,则b_{i,j}=1 si,j=0bi,j=1,否则 b i , j = β > 1 b_{i,j}=\beta>1 bi,j=β>1

    也就是说,如果两个顶点间存在链接,会在原有损失的基础上乘上一个大于1的数,这样在最小化损失的时候,就加大了对非零元素的惩罚,这样将不会更容易重建零元素。

    (3)式只保证了全局网络结构,还需要通过顶点间的连接情况来保证局部网络结构:
    在这里插入图片描述
    (4)式借鉴了拉普拉斯特征映射的思想:当相似顶点在嵌入空间中映射到很远的地方时,会产生惩罚。

    很容易理解,如果两个顶点间存在链接,也就是 s i , j ≠ 0 s_{i,j}\neq0 si,j=0,那么在损失函数中两个节点(存在链接)的向量表示间的差异将变大,这样我们在最小化差异时会更多地考虑它们间的差异。

    因此,(4)式保持了一阶邻近度,即如果两个顶点间存在链接,那么它们会被映射到比较近的位置。

    为了同时保持一阶和二阶邻近,将(3)式和(4)式结合起来,损失函数设计如下:
    在这里插入图片描述
    其中 L r e g L_{reg} Lreg是L2正则化项,用来防止过拟合,定义如下:
    在这里插入图片描述
    从这里我们就可以看出SDNE和LINE的不同了:LINE是将保持一阶邻近的LINE的嵌入结果和保持二阶邻近的LINE的嵌入结果连接起来,SDNE则是联合优化。

    3.2.3 优化

    我们的目标是最小化 L m i n L_{min} Lmin,然后找出自编码器的参数 θ \theta θ,即:
    在这里插入图片描述
    再来看这张图:
    在这里插入图片描述
    W ( k ) W^{(k)} W(k) b ( k ) b^{(k)} b(k)是编码器的参数, W ^ ( k ) \hat{W}^{(k)} W^(k) b ^ ( k ) \hat{b}^{(k)} b^(k)是解码器的参数。因此,我们需要求得 L m i n L_{min} Lmin对上述参数的偏导数,其中的关键是对 W ^ ( k ) \hat{W}^{(k)} W^(k) W ( k ) W^{(k)} W(k)求偏导:
    在这里插入图片描述
    L 1 s t L_{1st} L1st是为了保持一阶邻近,只是需要计算到表示空间,并不需要参与解码运算,因此与 W ^ ( k ) \hat{W}^{(k)} W^(k)无关。

    首先来看 ∂ L 2 n d ∂ W ^ ( k ) \frac{\partial L_{2nd}}{\partial \hat{W}^{(k)}} W^(k)L2nd

    因为有:
    在这里插入图片描述
    所以有:
    在这里插入图片描述

    在这里插入图片描述
    对于(7)中的第二项 ∂ X ^ ∂ W ^ ( K ) \frac{\partial \hat{X}}{\partial \hat{W}^{(K)}} W^(K)X^,因为有:
    X ^ = σ ( Y ^ ( k − 1 ) W ^ ( k ) + b ^ ( k ) ) \hat{X}=\sigma(\hat{Y}^{(k-1)}\hat{W}^{(k)}+\hat{b}^{(k)}) X^=σ(Y^(k1)W^(k)+b^(k))
    所以很很容易计算出 ∂ X ^ ∂ W ^ ( K ) \frac{\partial \hat{X}}{\partial \hat{W}^{(K)}} W^(K)X^

    同理,对于 W ( k ) W^{(k)} W(k),我们可以采用类似的方法来得到 L 2 n d L_{2nd} L2nd对其的偏导数。

    关于 L 1 s t L_{1st} L1st
    在这里插入图片描述
    可以重新表述为:
    在这里插入图片描述
    这里 L = D − S L=D-S L=DS D n × n D_{n\times n} Dn×n为度矩阵(对角阵,数值表示节点的度)。

    因此,对 ∂ L 1 s t ∂ W ( k ) \frac{\partial L_{1st}}{\partial {W}^{(k)}} W(k)L1st有:
    在这里插入图片描述
    因为有:
    Y = σ ( Y ( k − 1 ) W ( k ) + b ( k ) ) Y=\sigma(Y^{(k-1)}W^{(k)}+b^{(k)}) Y=σ(Y(k1)W(k)+b(k))
    因此(10)式中第2项很容易计算。对于第一项,由(9)式我们有:
    在这里插入图片描述

    至此,所有偏导数都已经算出,然后再使用SGD进行优化。

    值得注意的是,由于模型的高度非线性,因此它在参数空间中存在许多局部最优。为了找到一个好的参数空间区域,作者首先使用深度信念网络(DBN) 对参数进行预训练。

    完整的算法可以描述如下:
    在这里插入图片描述
    算法输入: G = ( V , E ) G=(V,E) G=(V,E) G G G的邻接矩阵 S S S,损失函数中的参数 α \alpha α υ \upsilon υ;输出:每个节点的嵌入向量表示 Y Y Y和自编码器参数 θ \theta θ

    具体步骤:

    1. 使用深度信念网络得到初始参数 θ \theta θ
    2. 自编码器输入 X = S X=S X=S
    3. 根据 X X X θ \theta θ,得到重构输出 X ^ \hat{X} X^和表示空间 Y Y Y,然后损失函数对参数 θ \theta θ求偏导,然后反向传播更新参数。
    4. 重复3直到收敛。
    5. 得到表示空间 Y Y Y,也就是每个节点的低维向量表示。

    3.3 分析和讨论

    1. 新节点:如何学习新到达节点的表示?如果我们已知新节点 v k v_k vk与其他所有节点的连接情况,那么我们就能得到 x = { s 1 , k , . . . , s n , k } x=\left \{s_{1, k},...,s_{n,k} \right \} x={s1,k,...,sn,k},然后我们将 x x x输入到SDNE中,就能得到其低维向量表示 y k ( K ) y_k^{(K)} yk(K),这个过程的时间复杂度为 O ( 1 ) O(1) O(1)。如果我们不了解连接情况,我们就必须依靠其他信息,比如节点的文本信息,作者表示这一点将作为未来的研究方向。
    2. 训练复杂度:SDNE的时间复杂度为 O ( n c d I ) O(ncdI) O(ncdI),其中 n n n为顶点数, c c c为网络中节点的平均度, d d d为隐藏层最大维数, I I I为迭代次数。参数 d d d通常与嵌入向量的维数有关,与顶点数无关。 I I I n n n无关。而对于 c c c,在实际情况中可将其视为常数,比如在社交网络中,一个人的最大好友数总是有界的。因此, c d I cdI cdI n n n无关,那么总体训练复杂度与网络中的顶点数成线性关系。

    4. 实验

    4.1 数据集

    五个网络数据集,包括三个社交网络、一个引文网络和一个语言网络。数据集用于三个实际应用:多标签分类、链接预测和可视化。

    数据集介绍如下:
    在这里插入图片描述

    4.2 Baseline

    DeepWalk、LINE、GraRep、拉普拉斯特征映射(LE)、Common Neighbor(使用公共邻居的个数来度量顶点间的相似性)。

    4.3 评价指标

    以前的论文中没有介绍过评价指标,因此这里重点看一下。

    本文完成了重建、链接预测、多标签分类和可视化的任务。

    (1)对于重建和链路预测,使用precision@k和Mean Average Precision (MAP) 作为评价指标:
    在这里插入图片描述precision@k是一个搜索推荐评价指标,index(j)是第j个顶点的排名索引, Δ i ( j ) = 1 \Delta_i(j)=1 Δi(j)=1表示 v i v_i vi v j v_j vj间存在链接。假设查询得到的前K个结果中有n个相关结果,返回n/K。如果结果数不够K,补齐到K(补的都是不相关结果)。

    那么对于链接预测,到底怎么计算呢?我们知道在链接预测中,比如我们随机去掉30%的边,那么剩下的70%就是训练集,那30%为测试集。经过图嵌入算法我们可以得到每个节点的低维向量表示,然后我们就可以计算出所有节点间的两两相似度,然后进行排序。 然后需要剔除掉这些节点对中原本存在于训练集中的边,剔除后参与排序的边有两种可能:一是测试集中存在的边,二是原本不存在的边。计算precision@k时,取前k对节点,然后观察里面有几条边属于测试集,然后计算比例即可。

    另一个评价指标为MAP:
    在这里插入图片描述

    (2)对于多标签分类任务,使用micro-F1和macro-F1作为评价指标。对于二分类问题,可将测试样例根据其真实类别和分类器预测类别划分为:
    在这里插入图片描述

    • True Positive :预测为正,实际也为正
    • False Positive :预测为正,实际为负
    • False Negative :预测与负、实际为正
    • True Negative:预测为负、实际也为负

    多分类问题中,对于每一类,我们都可以算出它的F1分数:
    在这里插入图片描述

    F 1 = 2 ⋅ P ⋅ R P + R F1=2\cdot\frac{P\cdot R}{P+R} F1=2P+RPR
    其中P为查准率(精确率),R为查全率(召回率)。

    而Macro-F1就为所有类别F1分数平均值:
    在这里插入图片描述
    Micro-F1:
    在这里插入图片描述

    4.4 参数设置

    在各个数据上,每层的神经元个数如表3所示:
    在这里插入图片描述

    • 对于SDNE,在验证集上使网格搜索法找到初始的 α , β , υ \alpha,\beta,\upsilon α,β,υ
    • 对于LINE,随机梯度下降的mini-batch的size为1,初始学习率为0.025,负例样本个数为5,样本总数100亿。
    • 对于DeepWalk,窗口长度 w = 10 w=10 w=10,路径长度40,每个节点40条路径。
    • 对于GraRep,最大矩阵转换步长设置为5。

    4.5 实验结果

    4.5.1 网络重建

    给定一个网络,使用不同的网络嵌入方法来学习网络表示,然后预测原始网络的链接。由于原始网络中的现有链路是已知的,并且可以作为基本事实,因此可以评估不同方法的重建性能,即训练集误差。

    各个模型的precision@k和MAP如图3和表4所示:
    在这里插入图片描述
    在这里插入图片描述
    可以看出:

    1. 图3显示了precision@k当k增加时,SDNE的平均值始终是最高的,这表明SDNE能够很好地保持网络结构。
    2. 对于ARXIV GR-QC网络,SDNE的precision@k可以达到100%,并保持在100%左右,直到k增加到10000。这表明SDNE几乎可以完美地重建该数据集中的原始网络,特别是考虑到该数据集中的链路总数为28980。
    3. 虽然SDNE和LINE都利用一阶和二阶邻近性来保持网络结构,但SDNE实现了更好的性能。原因可能有两方面:(1)LINE采用浅层结构,难以捕捉底层网络中的高度非线性的结构。(2)SDNE中是联合优化一阶和二阶邻近,LINE中则是将结果相连,效果可能会差一些。

    4.5.2 多标签分类

    顶点的表示由网络嵌入方法生成,然后将其用作顶点分类的特征。实验结果如图4和图5所示:
    在这里插入图片描述
    在这里插入图片描述
    分析如下:

    1. 无论是在图4还是图5,SDNE的效果都是最好的。这说明SDNE可以很好地被推广到分类任务。
    2. 在图4(BLOGCATALOG)中,当训练集百分比从60%降低到10%时,SDNE相对于基线的改进幅度更为明显。结果表明,在标记数据有限的情况下,SDNE可以实现比基线更显著的改进。这种优势对于实际应用程序尤其重要,因为标记的数据通常很少。
    3. 在大多数情况下,DeepWalk的性能都是最差的。原因有两方面:(1)DeepWalk没有明确的目标函数来捕获网络结构。(2)DeepWalk使用随机游走来丰富顶点的邻域,由于其随机性,引入了大量的噪声,特别是对于高度复杂的顶点。

    4.5.3 链接预测

    与网络重建任务不同,此任务预测未来链接,而不是重建现有链接。因此,该任务可以显示不同网络嵌入方法的可预测性性能。

    第一个试验中,随机隐藏15个已有链接(一共约4000个链接)并使用precision@k作为预测隐藏链接的评价指标,结果如表5所示:
    在这里插入图片描述
    分析如下:

    1. 当k增加时,SDNE的性能始终优于其他网络嵌入方法。
    2. 当k=1000时,SDNE精度仍然高于0.9,但其他方法的精度很快下降到0.8以下。这表明,SDNE可以保持高精度的链接排名领先。这种优势对于一些实际应用(如推荐和信息检索)非常重要,因为用户更关心在此类应用中排名靠前的结果。

    在第二个实验中,随机移除原始网络中的一部分链路来改变网络的稀疏性,然后重新实验,结果如图6所示:
    在这里插入图片描述
    结果表明,SDNE的效果一直都是最好的。当网络较稀疏时,LE与SDNE之间或LE与LINE之间的差距在变大,这说明引入二阶邻近性能够使学习到的表示对稀疏网络更具鲁棒性。

    4.5.4 可视化

    与LINE中类似,实验结果如下所示:
    在这里插入图片描述
    相同颜色的点应该彼此靠近,因此SDNE的效果无疑是最好的。LE和DeepWalk的结果很差,LINE虽然形成了不同的簇,但在中心部分不同类别间还是有重叠。GraRep结果看起来很好,但每个类别的界限并不十分清楚。

    同样,也可以使用KL散度作为衡量指标:
    在这里插入图片描述
    同样可以看出,SDNE的效果是最佳的。

    4.6 参数灵敏度

    图8(a)展示了嵌入维度对模型性能的影响:
    在这里插入图片描述
    可以看到,最初性能随着嵌入维度增加而提高,因为更多的维度可以编码更多有用的信息。但是,当维度继续增加时,性能开始缓慢下降,原因是尺寸过大可能会产生噪音,从而降低性能。总的来说,确定潜在嵌入空间的维数总是很重要的,但SDNE对这个参数不是很敏感。

    参数 α \alpha α用于表征一阶邻近和二阶邻近的考虑程度:
    在这里插入图片描述实验结果如图8(b)所示:
    ,
    α = 0 \alpha=0 α=0时,模型表现完全由二阶邻近来决定,当 α = 0.1 \alpha=0.1 α=0.1 α = 0.2 \alpha=0.2 α=0.2时,性能开始提升。实验结果表明,一阶和二阶邻近性对于网络嵌入方法表征网络结构是必不可少的。

    参数 β \beta β用于惩罚零元素, β \beta β越大,模型越容易重构非零元素。实验结果如图8©所示:
    在这里插入图片描述
    β = 1 \beta=1 β=1时,结果并不好,因为在这种情况下,模型将平等地重构训练网络中的非零元素和零元素。当 β \beta β太大时,性能也会降低,原因是在这种情况下,模型在执行重建时几乎忽略零元素,并且易于保持任何一对节点之间的相似性。然而,许多零元素仍然表示顶点之间的差异,因此性能下降。该实验表明,在进行网络嵌入时,我们应该更多地关注训练网络中非零元素的重构误差,但不能完全忽略零元素的重构误差。

    5. 结论

    本文提出了一种新的网络嵌入方法SDNE:为了捕获高度非线性的网络结构,设计了一个具有多层非线性函数的半监督深度模型,然后,为了进一步解决结构保持和稀疏性问题,联合利用一阶邻近和二阶邻近来描述局部和全局网络结构。通过在半监督深度模型中对一阶和二阶邻近进行联合优化,学习到的表示保持了局部-全局结构,并且对稀疏网络具有鲁棒性。

    展开全文
  • 本文介绍 Structural Deep Network Embedding ,以下简称 SDNE,以半监督的方式用深度神经网络来做图嵌入。 模型解读 论文指出学习网络表示具有三大难点: 高度非线性:网络结构是高度非线性的,使用浅层网络无法...

    本文介绍 Structural Deep Network Embedding ,以下简称 SDNE,以半监督的方式用深度神经网络来做图嵌入。

    模型解读

    论文指出学习网络表示具有三大难点:

    1. 高度非线性:网络结构是高度非线性的,使用浅层网络无法捕捉高度非线性的网络结构。
    2. 结构捕捉:同时捕捉到局部结构与全局结构。
    3. 稀疏性:大部分真实的网络都是稀疏的,仅仅利用网络中的部分连接关系建模效果还不够好。

    SDNE 的目标是设计一个可以学习到一阶相似度与二阶相似度的模型。一阶相似度与二阶相似度的概念与之前博客【图嵌入】Graph Embedding 方法之 LINE 原理解读中描述的相同:

    • 一阶相似度:描述边相连的节点对之间具有的相似性。
    • 二阶相似度:拥有共同邻居但是不直接向相连的两个节点具有的相似性。

    也就是说一阶相似度主要反映了 Graph 的局部特征, 二阶相似度反映了 Graph 的全局特征。

    为此,作者设计的模型如下图所示:

    在这里插入图片描述

    二阶相似度学习(无监督学习部分)

    先看图中的左半部分:

    在这里插入图片描述

    其输入是 x i x_i xi 输出是 x ^ i \hat x_i x^i ,这实际上是一种自编码器,其目标是学习一种函数映射:
    f ( x ) ≈ x f(x) \approx x f(x)x
    自编码器没有标签数据,所以是一种非监督学习,前半部分为编码器,后半部分为解码器。在实际应用中通常会使用自编码器的前半部分,即输入 x i x_i xi 到得到 y i ( K ) y_i^{(K)} yi(K) 的部分,此部分的公式为:
    y i ( 1 ) = σ ( W ( 1 ) x i + b ( 1 ) ) y i ( k ) = σ ( W ( k ) y i ( k − 1 ) + b ( k ) ) , k = 2 , . . . , K y_i^{(1)}=\sigma{(W^{(1)}x_i+b^{(1)})} \\ y_i^{(k)}=\sigma{(W^{(k)}y_i^{(k-1)}+b^{(k)})}, k=2,...,K yi(1)=σ(W(1)xi+b(1))yi(k)=σ(W(k)yi(k1)+b(k)),k=2,...,K
    其中, x i x_i xi 为输入值,本质是节点 i i i 的邻接矩阵(后面会解释)。上面公式中的 y i ( k ) y_i^{(k)} yi(k) 为第 k k k 层的第 i i i 个节点的输出值,而 W ( k ) W^{(k)} W(k) 为第 k 层的参数矩阵, b k b^{k} bk 为第 k 层的偏置项。最终经过编码得到节点的 Embedding 向量 y i ( K ) y_i^{(K)} yi(K)之后,再经过与编码器对称的网络结构得到输出值 x ^ i \hat x_i x^i

    自编码器的目标是最小化输入与输出的重构误差,所以损失函数为:
    L = ∑ i = 1 n ∣ ∣ x i ^ − x i ∣ ∣ 2 2 \mathcal{L}=\sum_{i=1}^n{||\hat{x_i}-x_i||^2_2} L=i=1nxi^xi22
    这里存在的一个问题是由于图的稀疏性,邻接矩阵S中的非零元素是远远少于零元素的,那么对于神经网络来说只要全部输出0也能取得一个不错的效果,这不是我们想要的。文章给出的一个方法是使用带权损失函数,对于非零元素具有更高的惩罚系数:
    L 2 n d = ∑ i = 1 n ∣ ∣ ( x i ^ − x i ) ⊙ b i ∣ ∣ 2 2 \mathcal{L_{2nd}}=\sum_{i=1}^n||(\hat{x_i}-x_i)\odot{b_i}||^2_2 L2nd=i=1n(xi^xi)bi22
    公式中 ⊙ \odot 为哈马达乘积,表示对应位置元素相乘。 b i = { b i , j } j = 1 n b_i=\{b_{i,j}\}^n_{j=1} bi={bi,j}j=1n,邻接矩阵中的 0 元素对应 b = 1 b=1 b=1,非 0 元素的 b > 1 b>1 b>1,这意味着如果将非 0 元素预测错了,将面临更大的惩罚。

    讲到这还有个问题,输入的数据 x i x_i xi 到底是什么?假设用 S 表示邻接矩阵集合:
    S = { s 1 , s 2 , . . . , s n } s i = { s i j } j = 1 n , s i j > 0 S = \{ s_1, s_2,...,s_n \} \\ s_i = \{ s_{ij}\}^n_{j=1}, s_{ij}>0 S={s1,s2,...,sn}si={sij}j=1n,sij>0
    其中,n 表示节点的个数, s i s_i si 表示 { s i 1 , s i 2 , . . . , s i n } \{s_{i1},s_{i2},...,s_{in} \} {si1,si2,...,sin} 中与节点 i i i 相邻的节点的边的集合。令最终输入的 x i = s i x_i = s_i xi=si,则输入每一个 x i x_i xi 都包含了顶点 i i i 的邻居结构信息。因此结构相似的顶点可以学习到相似的 embedding 向量,不断优化代价函数来捕捉全局结构特征,即二阶相似度。

    一阶相似度学习(有监督部分)

    一开始文章提到 SDNE 是半监督学习模型,那么监督学习的部分体现在何处?再来观察整个网络的结构:

    在这里插入图片描述

    模型的两侧的输入了有边相连的节点 i , j i, j i,j 的信息可以学习全局特征,但是这还不够,相连的两个节点具有一阶相似性,即节点 i , j i, j i,j 应该有相似的向量表示。于是借用拉普拉斯特征映射的思想(在图中相连的点,在降维后的空间中尽可能的靠近。 ),定义如下损失函数:
    L 1 s t = ∑ i , j = 1 n s i , j ∣ ∣ y i ( K ) − y j ( K ) ∣ ∣ 2 2 = ∑ i . j = 1 n s i , j ∣ ∣ y i − y j ∣ ∣ 2 2 \begin{aligned} \mathcal{L_{1st}}&=\sum_{i,j=1}^n{s_{i,j}||y_i^{(K)}-y_j^{(K)}||^2_2}\\ &=\sum_{i.j=1}^n{s_{i,j}||y_i-y_j||^2_2} \end{aligned} L1st=i,j=1nsi,jyi(K)yj(K)22=i.j=1nsi,jyiyj22

    该损失函数可以利用边的约束作用使得相邻顶点保持一阶相似度,当相似的顶点在嵌入空间中映射得很远时,就会产生惩罚。

    补充:

    论文对这个损失函数进行了进一步的变换,根据拉普拉斯矩阵的性质有(参考:拉普拉斯矩阵谱聚类方法推导和对拉普拉斯矩阵的理解):
    L 1 s t = ∑ i . j = 1 n s i , j ∣ ∣ y i − y j ∣ ∣ 2 2 = 2 t r ( Y T L Y ) \begin{aligned} \mathcal{L_{1st}}&=\sum_{i.j=1}^n{s_{i,j}||y_i-y_j||^2_2} \\ &=2tr(Y^TLY) \end{aligned} L1st=i.j=1nsi,jyiyj22=2tr(YTLY)

    L = D − S L = D - S L=DS

    其中,Y 表示节点的 embedding 向量,L为拉普拉斯矩阵,D是节点的度,S是邻接矩阵。

    最终整个模型的的损失函数定义如下:
    L m i x = L 2 n d + α L 1 s t + ν L r e g = ∑ i = 1 n ∣ ∣ ( x i ^ − x i ) ⊙ b i ∣ ∣ 2 2 + α ∑ i . j = 1 n s i , j ∣ ∣ y i − y j ∣ ∣ 2 2 + ν L r e g \begin{aligned} \mathcal{L_{mix}}&=\mathcal{L_{2nd}+\alpha{\mathcal{L_{1st}}}}+\nu{\mathcal{L_{reg}}} \\ &=\sum_{i=1}^n||(\hat{x_i}-x_i)\odot{b_i}||^2_2+\alpha{\sum_{i.j=1}^n{s_{i,j}||y_i-y_j||^2_2}}+\nu{\mathcal{L_{reg}}} \end{aligned} Lmix=L2nd+αL1st+νLreg=i=1n(xi^xi)bi22+αi.j=1nsi,jyiyj22+νLreg

    其中 α , ν \alpha, \nu α,ν 为超参数, L r e g L_{reg} Lreg L 2 L_2 L2 正则项用于防止过拟合:

    L r e g = 1 2 ∑ k = 1 k ( ∣ ∣ W ( k ) ∣ ∣ F 2 + ∣ ∣ W ^ k ∣ ∣ F 2 ) \mathcal{L_{reg}}=\frac{1}{2}\sum_{k=1}^k({||W^{(k)}||^2_F+||\hat{W}^{k}||_F^2}) Lreg=21k=1k(W(k)F2+W^kF2)

    在模型优化方面,SDNE 使用反向传播来更新网络参数,但由于模型高度非线性,参数空间中可能存在许多局部最优。因此,为了得到全局最优,作者使用深度信念网络(Deep Belief Network,以下简称 DBN)对参数进行预训练。

    关键源码解读

    这部分主要参考了https://github.com/xiaohan2012/sdne-keras

    损失函数定义

    定义函数 build_reconstruction_loss 作为二阶相似度对应的损失函数,参数 beta 控制非零元素的惩罚力度。

    def build_reconstruction_loss(beta):
        def reconstruction_loss(true_y, pred_y):
            diff = K.square(true_y - pred_y)
            weight = true_y * (beta - 1) + 1
            weighted_diff = diff * weight
            return K.mean(K.sum(weighted_diff, axis=1))  # mean sqaure error
        return reconstruction_loss
    

    定义函数 edge_wise_loss 作为一阶相似度对应的损失函数,参数 true_y 并未使用,embedding_diff 表示相邻的节点 i i i 与节点 j j j 的 embedding 向量的差值,此函数就是利用差值求均方误差。

    def edge_wise_loss(true_y, embedding_diff):
        return K.mean(K.sum(K.square(embedding_diff), axis=1))  # mean sqaure error
    

    模型定义

    关键代码如下:

    # INPUT
    # 边的一个顶点 a 
    input_a = Input(shape=(1,), name='input-a', dtype='int32')
    # 边的另一个顶点 b
    input_b = Input(shape=(1,), name='input-b', dtype='int32')
    edge_weight = Input(shape=(1,), name='edge_weight', dtype='float32')
    
    # 定义编码器、解码器的层数组
    encoding_layers = []
    decoding_layers = []
    
    # 用 embedding_layer 保持邻接矩阵
    embedding_layer = Embedding(output_dim=self.N, input_dim=self.N,
                                trainable=False, input_length=1, name='nbr-table')
    # if you don't do this, the next step won't work
    embedding_layer.build((None,))
    embedding_layer.set_weights([self.adj_mat])
    
    encoding_layers.append(embedding_layer)
    encoding_layers.append(Reshape((self.N,)))
    
    # 构造编码器
    encoding_layer_dims = [encode_dim]
    
    for i, dim in enumerate(encoding_layer_dims):
        layer = Dense(dim, activation='sigmoid',
                        kernel_regularizer=regularizers.l2(l2_param),
                        name='encoding-layer-{}'.format(i))
        encoding_layers.append(layer)
    
    # 构造解码器
    decoding_layer_dims = encoding_layer_dims[::-1][1:] + [self.N]
    for i, dim in enumerate(decoding_layer_dims):
        activation = 'sigmoid'
        layer = Dense(
            dim, activation=activation,
            kernel_regularizer=regularizers.l2(l2_param),
            name='decoding-layer-{}'.format(i))
        decoding_layers.append(layer)
    
    # 构造整个网络
    all_layers = encoding_layers + decoding_layers
    
    # 取出节点 a 与节点 b 的 embedding 向量
    # reduce 函数将 input_a 作为数组 encoding_layers 中每一个 Layer 的输入
    # 然后将每个 layer 的输出值作为下一个 layer 的输入,直到编码器层结束
    encoded_a = reduce(lambda arg, f: f(arg), encoding_layers, input_a)
    encoded_b = reduce(lambda arg, f: f(arg), encoding_layers, input_b)
    
    # 得到节点的重构矩阵
    decoded_a = reduce(lambda arg, f: f(arg), all_layers, input_a)
    decoded_b = reduce(lambda arg, f: f(arg), all_layers, input_b)
    
    # 将两个节点的 embedding 向量做减法
    embedding_diff = Subtract()([encoded_a, encoded_b])
    
    # 为差值添加权重
    embedding_diff = Lambda(lambda x: x * edge_weight)(embedding_diff)
    
    # 构建模型
    self.model = Model([input_a, input_b, edge_weight],
                        [decoded_a, decoded_b, embedding_diff])
    
    # 构建损失函数
    reconstruction_loss = build_reconstruction_loss(beta)
    
    # 构建模型
    self.model.compile(optimizer='adadelta',
                        loss=[reconstruction_loss, reconstruction_loss, edge_wise_loss],
                        loss_weights=[1, 1, alpha]) # 损失函数权重
    # 构建模型
    self.encoder = Model(input_a, encoded_a)
    
    # 构建模型
    self.decoder = Model(input_a, decoded_a)
    self.decoder.compile(optimizer='adadelta',
                            loss=reconstruction_loss)
    

    关于 reduce 的更多说明如下:

    reduce(function, sequence[, initial]) -> value

    Apply a function of two arguments cumulatively to the items of a sequence,
    from left to right, so as to reduce the sequence to a single value.
    For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
    ((((1+2)+3)+4)+5). If initial is present, it is placed before the items
    of the sequence in the calculation, and serves as a default when the
    sequence is empty.

    行业应用

    在购物的过程中,经常遇到满减活动,例如满400减50,当购物车商品金额不足400时,就需要进行凑单。在2018年的时候,阿里公开了他们的凑单算法:

    在这里插入图片描述

    阿里的凑单算法框架图如上图所示,其中一部分就用到了 SDNE 模型。比较传统的协同过滤算法也能发掘共同购买关系,为什么还需要构造 graph?

    由于 graph 具有传播能力,它不仅能有效的提取出来节点之间的直接关联,而且可以通过游走策略,挖掘出来二度、三度的关系。朋友的朋友,也是朋友,也存在一定的弱关联,有效的利用这种传播能力,能解决购买数据的稀疏性,达到提升覆盖的效果。

    整个算法流程的步骤大致如下:

    (1)构建 Graph

    基于用户购买行为构建 graph,节点是商品,边是商品间同时购买的行为,权重是可以是两个商品同时购买的次数、时间、金额等。

    为什么需要带权重的Graph?商品的数量繁多,绝大多数是冷门商品。在对图进行采样的过程中,如果使用 random walk 策略,那么采样出来的序列就包含很多冷门商品。但是在引入权重后,可以基于边的权重进行游走(weighted walk),这样采样出来的序列就能包含更受用户欢迎的热门商品。

    (2)采样

    假如有了下图所示的带权商品图:

    在这里插入图片描述

    假设游走2步,从节点A出发,随机取下一个邻居节点时,如果是random walk算法,它会等概率的游走到B或C节点,但是weighted walk算法会以7/8的概率取节点C,再会以8/12的概率游走到节点D,最终很大概率上会采出来一条序walk=(A,C,D),对于原始graph,A和D是没有关联的,但是通过weighted walk,能够有效的挖掘出A和D的关系。

    (3)嵌入

    将基于weighted walk采出来的序,构造成item-item的pair对,送给embedding模型:

    在这里插入图片描述

    每一对商品都输出一个 score,上线之后,取出 topN 个 score 较高的关联商品进行推荐。

    参考文章:

    【论文笔记】Structural Deep Network Embedding

    SDNE:《Structral Deep Network Embedding》阅读笔记

    【Embedding】SDNE:深度学习在图嵌入领域的应用

    大话深度信念网络(DBN)

    阿里凑单算法首次公开!基于Graph Embedding的打包购商品挖掘系统解析

    展开全文
  • 1、概述SDNE(Structural Deep Network Embedding)算法是发表在KDD-2016上的一篇文章,论文的下载地址为:https://www.kdd.org/k...

    1、概述

    SDNE(Structural Deep Network Embedding)算法是发表在KDD-2016上的一篇文章,论文的下载地址为:

    https://www.kdd.org/kdd2016/papers/files/rfp0191-wangAemb.pdf

    SDNE主要也是用来构建node embedding的,和之前介绍的node2vec发表在同年,但不过node2vec可以看作是deepwalk的扩展,而SDNE可以看作是LINE的扩展。

    2、算法原理

    SDNE和LINE中相似度的定义是一致的,同样是定义了一阶相似度和二阶相似度,一阶相似度衡量的是相邻的两个顶点对之间相似性,二阶相似度衡量的是,两个顶点他们的邻居集合的相似程度。

    模型结构 如下:

    SDNE模型结构

    模型主要包括两个部分:无监督和有监督部分,其中:

    • 无监督部分是一个深度自编码器用来学习二阶相似度(上图中两侧部分)

    • 监督部分是一个拉普拉斯特征映射捕获一阶相似度(中间的橘黄色部分)

    对于一阶相似度,损失函数定义如下:

    该损失函数可以让图中的相邻的两个顶点对应的embedding vector在隐藏空间接近。

    论文中还提到一阶相似度的损失函数还可以表示为:

    其中:

    • 是图对应的拉普拉斯矩阵

    • 是图中顶点对应的度矩阵, 是邻接矩阵,

    拉普拉斯矩阵是「图论」中重要的知识点,可以参考:

    https://blog.csdn.net/qq_30159015/article/details/83271065

    对于二阶相似度,损失函数定义如下:

    这里使用图的邻接矩阵进行输入,对于第 个顶点,有 ,每一个 都包含了顶点 的邻居结构信息,所以这样的重构过程能够使得结构相似的顶点具有相似的embedding表示向量。

    但是现实中由于图都是稀疏的,邻接矩阵 中的非零元素是远远少于零元素的,那么对于神经网络来说只要全部输出0也能取得一个不错的效果,这不是我们想要的。为了解决这个问题,论文提出一种使用带权损失函数,对于非零元素具有更高的惩罚系数。修正后的损失函数为:

    其中:

    • 为逐元素积

    • ,若 ,则 ,否则

    模型整体的优化目标为:

    其中:

    • 为正则项, 为控制一阶损失的参数, 为控制正则化项的参数

    3、实验

    实验部分主要就是为了验证SDNE的效果要比其他的模型好,因此作者在5个数据集中进行了实验,分别为:

    • BLOGCATALOG

    • FLICKR

    • YOUTUBE

    • ARXIV GR-QC

    • 20-NEWSGROUP

    这里选取的对比模型包括:

    • Deepwalk

    • LINE

    • GraRep

    • Laplacian Eigenmaps (LE)

    • Common Neighbor

    实验评估的指标为:

    • precision@k:top k的精确度

    • Mean Average Precision (MAP):平均误差

    • Macro-F1:区分类别的F1-Score

    • Micro-F1 :不区分类别的F1-Score

    Macro-F1和Micro-F1区别参考:https://zhuanlan.zhihu.com/p/64315175

    4、代码实现

    代码实现部分可以参考:https://github.com/xiaohan2012/sdne-keras

    其中关于SDNE模型的定义部分为:

    class SDNE():
        def __init__(self,
                     graph,
                     encode_dim,
                     weight='weight',
                     encoding_layer_dims=[],
                     beta=2, alpha=2,
                     l2_param=0.01):
            """graph: nx.Graph
            encode_dim: int, length of inner most dim
            beta: beta parameter under Equation 3
            alpha: weight of loss function on self.edges
            """
            self.encode_dim = encode_dim
    
            ###################
            # GRAPH STUFF
            ###################
    
            self.graph = graph
            self.N = graph.number_of_nodes()
            self.adj_mat = nx.adjacency_matrix(self.graph).toarray()
            self.edges = np.array(list(self.graph.edges_iter()))
    
            # weights
            # default to 1
            weights = [graph[u][v].get(weight, 1.0)
                       for u, v in self.graph.edges_iter()]
            self.weights = np.array(weights, dtype=np.float32)[:, None]
    
            if len(self.weights) == self.weights.sum():
                print('the graph is unweighted')
            
            ####################
            # INPUT
            ####################
    
            # one end of an edge
            input_a = Input(shape=(1,), name='input-a', dtype='int32')
            # the other end of an edge
            input_b = Input(shape=(1,), name='input-b', dtype='int32')
            edge_weight = Input(shape=(1,), name='edge_weight', dtype='float32')
    
            ####################
            # network architecture
            ####################
            encoding_layers = []
            decoding_layers = []
            
            embedding_layer = Embedding(output_dim=self.N, input_dim=self.N,
                                        trainable=False, input_length=1, name='nbr-table')
            # if you don't do this, the next step won't work
            embedding_layer.build((None,))
            embedding_layer.set_weights([self.adj_mat])
            
            encoding_layers.append(embedding_layer)
            encoding_layers.append(Reshape((self.N,)))
            
            # encoding
            encoding_layer_dims = [encode_dim]
    
            for i, dim in enumerate(encoding_layer_dims):
                layer = Dense(dim, activation='sigmoid',
                              kernel_regularizer=regularizers.l2(l2_param),
                              name='encoding-layer-{}'.format(i))
                encoding_layers.append(layer)
    
            # decoding
            decoding_layer_dims = encoding_layer_dims[::-1][1:] + [self.N]
            for i, dim in enumerate(decoding_layer_dims):
                if i == len(decoding_layer_dims) - 1:
                    activation = 'sigmoid'
                else:
                    # activation = 'relu'
                    activation = 'sigmoid'
                layer = Dense(
                    dim, activation=activation,
                    kernel_regularizer=regularizers.l2(l2_param),
                    name='decoding-layer-{}'.format(i))
                decoding_layers.append(layer)
            
            all_layers = encoding_layers + decoding_layers
    
            ####################
            # VARIABLES
            ####################
            encoded_a = reduce(lambda arg, f: f(arg), encoding_layers, input_a)
            encoded_b = reduce(lambda arg, f: f(arg), encoding_layers, input_b)
    
            decoded_a = reduce(lambda arg, f: f(arg), all_layers, input_a)
            decoded_b = reduce(lambda arg, f: f(arg), all_layers, input_b)
            
            embedding_diff = Subtract()([encoded_a, encoded_b])
    
            # add weight to diff
            embedding_diff = Lambda(lambda x: x * edge_weight)(embedding_diff)
    
            ####################
            # MODEL
            ####################
            self.model = Model([input_a, input_b, edge_weight],
                               [decoded_a, decoded_b, embedding_diff])
            
            reconstruction_loss = build_reconstruction_loss(beta)
    
            self.model.compile(optimizer='adadelta',
                               loss=[reconstruction_loss, reconstruction_loss, edge_wise_loss],
                               loss_weights=[1, 1, alpha])
                               
            self.encoder = Model(input_a, encoded_a)
    
            # for pre-training
            self.decoder = Model(input_a, decoded_a)
            self.decoder.compile(optimizer='adadelta',
                                 loss=reconstruction_loss)
    
        def pretrain(self, **kwargs):
            """pre-train the autoencoder without edges"""
            nodes = np.arange(self.graph.number_of_nodes())
            node_neighbors = self.adj_mat[nodes]
                    
            self.decoder.fit(nodes[:, None],
                             node_neighbors,
                             shuffle=True,
                             **kwargs)
    
        def train_data_generator(self, batch_size=32):
            # this can become quadratic if using dense
            m = self.graph.number_of_edges()
            while True:
                for i in range(math.ceil(m / batch_size)):
                    sel = slice(i*batch_size, (i+1)*batch_size)
                    nodes_a = self.edges[sel, 0][:, None]
                    nodes_b = self.edges[sel, 1][:, None]
                    weights = self.weights[sel]
                    
                    neighbors_a = self.adj_mat[nodes_a.flatten()]
                    neighbors_b = self.adj_mat[nodes_b.flatten()]
    
                    # requires to have the same shape as embedding_diff
                    dummy_output = np.zeros((nodes_a.shape[0], self.encode_dim))
    
                    yield ([nodes_a, nodes_b, weights],
                           [neighbors_a, neighbors_b, dummy_output])
    
        def fit(self, log=False, **kwargs):
            """kwargs: keyword arguments passed to `model.fit`"""
            if log:
                callbacks = [keras.callbacks.TensorBoard(
                    log_dir='./log', histogram_freq=0,
                    write_graph=True, write_images=False)]
            else:
                callbacks = []
    
            callbacks += kwargs.get('callbacks', [])
            if 'callbacks' in kwargs:
                del kwargs['callbacks']
    
            if 'batch_size' in kwargs:
                batch_size = kwargs['batch_size']
                del kwargs['batch_size']
                gen = self.train_data_generator(batch_size=batch_size)
            else:
                gen = self.train_data_generator()
    
            self.model.fit_generator(
                gen,
                shuffle=True,
                callbacks=callbacks,
                pickle_safe=True,
                **kwargs)
            
        def get_node_embedding(self):
            """return the node embeddings as 2D array, #nodes x dimension"""
            nodes = np.array(self.graph.nodes())[:, None]
            return self.encoder.predict(nodes)
    
        def save(self, path):
            self.model.save(path)
    

    5、应用

    以下内容参考:

    https://developer.aliyun.com/article/419706

    SDNE算法主要应用是电商场景的「凑单」,比如在618、双十一这样的场景中会有满200-30这样的场景,当用户加购的商品不足200时,会进行提示凑单。

    其主要流程为:

    • 基于用户购买行为构建graph,节点:商品,边:商品间同时购买的行为,权重:同时购买的比重,可以是购买次数、购买时间、金额等feature

    • 基于权重Sampling(weighted walk)作为正样本的候选,负样本从用户非购买行为中随机抽样

    • embedding部分将无监督模型升级成有监督模型,将基于weighted walk采出来的序,构造成item-item的pair对,送给有监督模型(DNN)训练

    • 依据产出的embedding,计算item之间的相似度,生成item 的相似 item list

    5.1、算法流程

    整体算法的架构图为:

    算法流程

    5.1.1、构建Graph

    上文提到,我们要挖掘商品间共同购买的关系(bundle mining),类似买了又买的问题,所以,我们构建的graph是带权重的商品网络,节点:商品,边:商品间共同购买的关系,权重:共同购买次数、购买时间。

    构建Graph

    5.1.2、Sampling

    传统的方法,比如deep walk,它的Sampling本质上是有两部分,首先,通过random walk的方式进行游走截断,其次,在仍给word2vec中Skip-Gram模型进行embedding之前,用negative sampling的方式去构造样本;这种随机采样的方法会大概率的将热门节点采集为负样本,这种方式适用于语言模型,因为在自然语言中,热门的单词均为无用单词(比如he、she、it、is、the)。对于我们的商品网络,刚好相反,热门商品往往是最重要的样本,如果采用negative sampling的方式去构造样本,模型肯定是学不出来。因此,我们基于边的权重去采样(weighted walk),使采样尽量往热门节点方向游走,以下图为例:

    Sample

    举个例子来说,假设游走2步,从节点A出发,随机取下一个邻居节点时,如果是random walk算法,它会等概率的游走到B或C节点,但是我们的算法会以7/8的概率取节点C,再会以8/12的概率游走到节点D,最终很大概率上会采出来一条序walk=(A,C,D),对于原始graph,A和D是没有关联的,但是通过weighted walk,能够有效的挖掘出A和D的关系,算法详见:

    算法流程

    5.1.3、Embedding

    上一部分介绍了如何构建了带权重的概率图,基于带权重的采样(weighted walk)作为正样本的候选,负样本从用户非购买行为中随机抽样;这一部分主要介绍embedding的部分,将基于weighted walk采出来的序,构造成item-item的pair对,送给embedding模型,我们构造了一个有监督embedding模型(DNN),规避无监督模型无法离线评估模型效果的问题。模型结构如下图。

    Embedding产生

    5.2、实现

    5.2.1、离线

    a)训练:离线模型在PAI平台上用tensorflow框架实现,抽取了历史50天的全网成交数据,大概抽取3000万节点,构建的graph,在odps graph平台做完weighted walk,产出2亿条样本,也就是item-item的pair对,训练至收敛需要2小时的时间

    b)预测:从全网所有行为中,随机抽取几十亿条pair对,去做预测,给每对item pair预测一个score

    c)上线:对每个种子商品取topN的bundle商品,打到搜索引擎的倒排和正排字段,从qp中取出每个用户的种子商品,基于倒排字段召回bundle商品,基于正排字段做bundle排序

    5.2.2、实时

    用户购买行为,日常和大促差异很大,为了能够实时的捕获用户实时行为,我们在porsche上建了一套实时计算bundle mining的流程:

    a)数据预处理:在porsche上对用户实时日志进行收集,按离线的数据格式处理成实时的数据流

    b)Sampling:发送给odps graph实时计算平台,构建graph,做weighted walk,生成序,再通过swift消息发出

    c)Embedding:在porsche上做DNN模型训练和实时预测

    d)数据后处理:计算item的topN的bundle item list,实时写到dump和引擎

    更多干货请点击:

    如何利用NLP与知识图谱处理长句理解?【免费下载】2021年6月热门报告盘点&下载【干货】电商知识图谱构建及搜索推荐场景下的应用DTC模式如何引领消费品牌企业实现创新.pdf(附下载链接)【干货】营销拓客思维导图24式.pdf比电影刺激多了,警匪大战,记录仪真实镜头!某视频APP推荐策略详细拆解(万字长文)

    华为到底在研发怎样的核心技术?

    2020年轻人性和爱调查报告.pdf(附下载链接)

    【86年高清视频】西游记剧组春节晚会

    【视频】未来10年,普通人的赚钱机会在哪里?

    关注我们
    

    省时查报告

    专业、及时、全面的行研资料库

    长按并识别关注

    您的「在看」,我的动力 ????
    展开全文
  • 今天学的论文是清华大学崔鹏老师工作《Structural Deep Network Embedding》(后简称 SDNE),并发表于 2016 KDD,目前为止共有 880 多引用,是一个非常经典的将深度学习应用于 NetWork Embedding 的算法。...
  • -beta',default = 5.,type = float,help = 'beta is a hyperparameter in SDNE.') parser.add_argument('--mu1',default = 1e-5,type = float,help = 'mul is a hyperparameter in SDNE') parser.add_argument('--mu...
  • 文章目录 参考 Node2Vec SDNE 承接上文 graph embedding第一篇——deepwalk and line 本篇主要介绍Node2vec与SDNE,下一篇主要介绍各个大厂是怎么应用graph embedding的。 参考 graph embedding 深度学习中不得不学...
  • Graph Embeding—DeepWalk、Line、SDNE、Node2vec、Struc2vec概念什么是图嵌入(网络嵌入)?为什么用Graph Embeding?DeepWalk(2014)LINE(2015)SDNE(2016)Node2vec(2016)Struc2vec(KDD 2017)扩展 概念 ...
  • 1.概述 ...SDNE主要也是用来构建node embedding的,和之前介绍的node2vec发表在同年,但不过node2vec可以看作是deepwalk的扩展,而SDNE可以看作是LINE的扩展。 2.算法原理 SDNE和LINE中相似度的定义是一
  • SDNE 前一篇整理了3种常用的图嵌入方法,DeepWalk,LINE和Node2vec。Structural Deep Network Embeddings(结构深层网络嵌入,SDNE)的不同之处在于,它并不是基于随机游走的思想,在实践中比较稳定。 主要思路...
  • (本质上是这个世界很简单) SDNE 提出了一种半监督模型来做图嵌入,引入了deep auto encoder的模型架构,以邻接矩阵中第i个列向量表示节点i,输入编码器,得到低维的SDNE模型结构。 同时我们还需要训练解码器,使得...
  • SDNE 使用自动编码器(AutoEncoder)结合拉普拉斯特征映射(Laplacian Eigenmaps),针对网络结构非线性,构建多层非线性函数深度模型,同时针对全局和局部结构以及稀疏性问题,同时利用一阶相似性和二阶相似性学习...
  • Graph Embedding——(5)SDNE理论

    千次阅读 2022-01-28 23:48:34
    SDNE理论 1)理论 SDNE(Structural Deep Network Embedding )是和node2vec并列的工作,均发表在2016年的KDD会议中。可以看作是基于LINE的扩展,同时也是第一个将深度学习应用于网络表示学习中的方法。 之前的Deep...
  • 今天要聊的是SDNE(Structural Deep Network Embedding)。结合的论文为《Structural Deep Network Embedding》,这是2016年发表的一篇论文,与node2vec在同一年问世。总体上来,SDNE更像LINE,而不像Deepwalk。有了...
  • SDNE(Structural Deep Network Embedding Daixin)是和node2vec并列的工作,均发表在2016年的KDD会议中。可以看作是基于LINE的扩展,同时也是第一个将深度学习应用于网络表示学习中的方法。 SDNE使用了无监督...
  • 【网络表示学习】SDNE

    千次阅读 2019-05-25 21:08:39
    和之前使用浅层神经网络的方法(deepwalk)不同, SDNE使用深层神经网络对节点表示间的非线性进行建模。整个模型可以被分为两个部分: 一个是由 Laplace 矩阵监督的建模第一级相似度的模块, 另一 个是由无监督的深层自...
  • SDNE 图向量

    2021-02-25 01:25:51
    目录1 目的和思想2 模型原理2.1 节点编码公式2.2 损失函数2.3 算法3 SDNE 总结 1 目的和思想 SDNE 模型的目的:将图的顶点表示为向量 SDNE 的整体思想:为了保留网络的高度非线性关系 模型出自论文: Structural Deep...
  • 自然语言处理-GNN:SDNE【多层自编码器】
  • 文章目录前言论文结构学习目标论文研究背景、成果、意义研究背景 ...Abstract:提出之前多为浅层模型并提出SDNE模型,使用了一阶相似度和二阶相似度的概念。 Introduction:介绍学习图的表征的重要性、低维的分
  • 目录deepwalknode2vecstruct2vecLINE deepwalk 模型:随机截断游走+skipgram+层级softmax 整个过程: 输入:图的边集和点集 使用随机游走来获得结点序列 使用skip-gram算法来获得结点表示 使用层级softmax来优化...
  • SDNE----------多层自编码器
  • SDNE实战

    2022-05-14 00:34:05
    SDNE实战
  • 【Graph Embedding】: SDNE算法

    千次阅读 2019-04-09 23:17:01
    论文“Structural Deep Network Embedding”发表在kdd2016 ... 论文利用深度自编码器来学习图中节点的embedding向量,结合一阶和二阶相似度进行联合训练,将二阶相似度作为无监督信息,捕获全局网络结构信息,一阶...
  • 网络表示学习论文阅读之SDNE

    万次阅读 2018-04-08 18:10:27
    Structural Deep Network Embedding (SDNE) 方法。论文首次提出了一个半监督的深层模型,它具有多层非线性函数,从而能够捕获到高度非线性的网络结构。然后使用一阶和二阶邻近关系来保持网络结构。二阶邻近关系被无...
  • https://zhuanlan.zhihu.com/p/56637181
  • 网络表示学习(DeepWalk,LINE,node2vec,SDNE

    万次阅读 多人点赞 2017-07-24 12:49:01
    SDNE[4] : :   本文的一大贡献在于提出了一种新的半监督学习模型 , 结合一阶估计与二阶估计的优点 , 用于表示网络的全局结构属性和局部结构属性。 对节点的描述特征向量(比如点的「邻接向量」)使用 ...
  • paper: https://www.kdd.org/kdd2016/papers/files/rfp0191-wangAemb.pdf 2016 KDD | SDNE: Structural Deep Network Embedding

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 510
精华内容 204
关键字:

SDNE