精华内容
下载资源
问答
  • DeepWalk算法

    千次阅读 2019-04-03 22:04:00
    DeepWalk算法

    随机游走

    随机游走

    幂律分布

    前提: 如果一个网络的节点服从幂律分布,那么节点在随机游走序列中的出现次数也服从幂律分布,并且实证发现NLP中单词的出现频率也服从幂律分布。
    幂率分布

    DeepWalk算法

    DeepWalk算法

    DEEPWALK(G,w,d,γ,t);G代表网络,w代表窗口大小,d达标维度,γ代表每个顶点随机游走的次数,t代表随机游走的步长
    Input:G(V,E);G代表网络,V代表网络中的节点,E代表网络中的边
    output:|V|*d的矩阵,每一个顶点都有一个d维的连续向量
    1.初始化每个顶点的向量空间
    2.建立Huffman树(根据随机游走顶点出现的次数构建)
    3.0- γ(表示随机游走 γ次)(进入循环)
    4.将V打乱顺序得到O
    5.遍历O中的每一个顶点,do(进入循环)
    6.得到从vi节点开始的步长为t的随机游走序列
    7.使用SkipGram进行参数更新
    8.退出里层循环
    9.退出外层循环

    SkipGram算法

    Skip-gram算法

    SkipGram(Φ, Wvi , w);Φ代表当前的顶点向量,Wvi代表随机游走生成的序列,w代表窗口大小
    1.遍历序列中的每一个节点vi(进入循环)
    2.uk ∈ Wvi [j − w : j + w],遍历vi顶点前后w的每一个顶点(进入循环)
    3.更新参数(为什么用梯度下降???)
    4.退出里层循环
    5.退出外层循环

    总体过程总体过程

    node2vec基本思想

    node2vec通过改变随机游走序列生成的方式进一步扩展了DeepWalk算法。DeepWalk选取随机游走序列中下一个节点的方式是均匀随机分布的,而node2vec通过引入两个参数p和q,将宽度优先搜索和深度优先搜索引入随机游走序列的生成过程。宽度优先搜索(BFS)注重临近的节点,并刻画了相对局部的一种网络表示,宽度优先中的节点一般会出现很多次,从而降低刻画中心节点的邻居节点的方差;深度优先搜索(BFS)反应了更高层面上的节点间的同质性。(即BFS能够探究图中的结构性质,而DFS则能够探究出内容上的相似性(相邻节点之间的相似性)。其中结构相似性不一定要相连接,甚至可能相距很远。)如下图所示:
    node2vec
    NBFS={s1,s2,s3} 局部微观结构
    NDFS={s4,s5,s6} 全局宏观结构

    展开全文
  • deepwalk算法

    2018-04-08 16:05:17
    用于deepwalk的python算法代码,很好用的,对于想要理解deepwalk的同学可以看看。
  • Graph-Embedding和DeepWalk算法     在之前的图算法介绍里,我们探讨了部分比较简单和经典的图算法,比如PageRank、最短路径、深度优先搜索等方法。在某些场景,之前介绍的一些算法虽然很经典,...

    图论-图论算法之DeepWalk

    Graph-Embedding和DeepWalk算法
        在之前的图算法介绍里,我们探讨了部分比较简单和经典的图算法,比如PageRank、最短路径、深度优先搜索等方法。在某些场景,之前介绍的一些算法虽然很经典,逻辑很清晰,但是由于实际情况里数据量非常大,所以经常会用到Graph-Embedding类型的算法,在基于图的推荐等经常被使用,因此本文将会介绍这种类型的算法,并且拿一个最基础的Graph-Embedding类型的算法做进一步介绍。
        首先介绍的是Graph-Embedding,也就是所谓的图嵌入,这种方法是把实际场景里的高维度稀疏图数据,转化为低维度稠密的向量,然后再进行后续深度学习或者机器学习算法进行构建模型。这种思路是比较常见的,比如某线上商城有100万种商品、3亿用户,这个时候如果直接在原始图上进行推荐、聚类等操作,会非常耗时和耗资源,所以这种嵌入的思路应运而生。
        那么基于上述的图嵌入思路,在2014年提出了比较经典的DeepWalk方法,它的思路就是多次在图上进行随机游走,然后得到海量的节点序列,并且把这些序列作为训练样本输入到模型进行训练,并且得到最终的Embedding结果向量。下面我们来说明DeepWalk算法的步骤。
        1)初始化相关的参数,比如设置Embedding结果的向量长度,设置每次随机游走总共的步数,设置走多少轮次等参数。
        2)对于图里的每一个节点,都进行K次游走,而且每一次在游走的时候,每次都走N步,将走过的节点进行记录,对于得到的结果进行打乱处理,然后再把这些结果输入到树里面,再次进行随机游走,并记录结果,然后使用skip-gram模型对参数进行更新。
        3)反复走过K轮次后,结束该算法,并且得到最终的Embedding结果。
    在这里插入图片描述
        从广义来说,我们可以认为DeepWalk其实是一种可以回溯的深度优先算法,其本身使用了两次随机游走,一次是在图里针对节点进行随机游走,第二次是针对游走的结果和当前节点构成的树再一次进行随机游走,因此只要数据量够大就可以使得这种方法比较好地刻画出图里面节点的关联性和结构信息。当然这种方法由于提出的时间比较早,还可以在进行优化,比如可以考虑点之间的路径存在权重,从而引入跳转概率,尽可能地游走到权值更高、关系更强的节点之中,这样可以更好地刻画图的结构信息,因为当前的DeepWalk算法其实是完全等概率的一种跳转形式,现实应用显然可以考虑边的权重等信息,这个在后续的模型里会再进行介绍。
        总的来说,图嵌入的方法是想把数据的表现形式进行转化,把高维度稀疏图数据转为低维度稠密的向量,从而使得可以展开并行化的计算,在大数据场景下非常实用;并且由于这种嵌入的技术可以看作特征工程,在转换后的数据可以继续无缝对接机器学习算法、神经网络等,所以可用性和灵活性较好。而DeepWalk算法是基于随机游走提出的,虽然思路比较简单,但在某些实际问题中,可以使用它进行求解,所以初学者需要熟练掌握这种嵌入的思路和算法。

    展开全文
  • 最近项目需要用到 Graph Embedding 模型,所以简单把这个系列学习一下做个记录。 ...二、DeepWalk 算法 参考文献: 论文题目:DeepWalk: Online Learning of Social Representations 论文来源:K.

    最近项目需要用到 Graph Embedding 模型,所以简单把这个系列学习一下做个记录。

    一、Graph Embedding

    Graph Embedding 的中心思想是找到一种映射函数,将图中的每个节点转换为低维稠密的嵌入表示,要求在图中相似的节点在低维空间距离相近

    得到的表示向量可用于下游任务,如节点分类、链接预测、可视化等。

    二、DeepWalk 算法

    参考文献:
    论文题目:DeepWalk: Online Learning of Social Representations
    论文来源:KDD 2014
    论文原文:https://arxiv.org/pdf/1403.6652.pdf

    概述

    本文首次将无监督特征学习引入图网络分析中。 DeepWalk 算法通过截断式随机游走(truncated random walk)来学习图网络节点的社区表示(Social Representations)。

    问题定义

    以节点分类问题为例。

    给定图 G=(V,E)G=(V,E),其中,VV 是节点数,EE 是边数,E(V×V)E \subseteq (V \times V)

    给定部分标记的图 GL=(V,E,X,Y)G_L=(V,E,X,Y),其中,XX 是节点的属性,YY 是节点的标签。

    本文的目标是学习节点的表示 XERV×dX_E \in \mathbb R^{|V| \times d},其中,dd 是较小的嵌入维数。

    与传统的关系分类问题不同,本文提出的方法可捕获与标签分布无关的图网络结构的特征,因此学得的表示具有通用性,可应用于多种下游任务。

    可行性及性质分析

    DeepWalk 算法学得的社区表示具有以下特征:

    • 适应性:随着图网络的不断发展,可只学习新的节点信息,不需重复学习过程;
    • 社区性:同社区的节点具有相似的表示,即相似的节点在低维嵌入空间距离相近;
    • 低维:低维模型可以更好地泛化,降低过拟合风险,并加快收敛和推理速度;
    • 连续:连续的嵌入向量使节点表示在社区之间具有平滑的决策边界,从而可以进行更加可靠的分类。

    DeepWalk 算法的思路是使用 Random Walk 算法在图网络中进行节点采样,获得了足够的节点访问序列后,使用 Word2Vec 的 Skim-Gram 算法进行表示学习。

    如上图所示,图 (a) 来自无标度图网络上的一系列截断性随机游走,图 (b) 来自英语维基百科的100万条语料。其分布规律满足类似的幂律分布,因此可以将 NLP 的词向量模型(如 Skim-Gram 算法)应用在图网络的截断性随机游走中。

    Deepwalk 算法

    该算法包含两个主要的步骤:第一步利用 Random Walk 算法采样节点序列,第二步使用 skip-gram 算法学习表达向量。

    Random Walk 算法

    Random Walk 算法思路:

    在图网络上,从某个特定的节点开始,从与该节点相连的边中随机选择一条移动直下个节点,重复该过程直到达到窗口大小。是一种可重复访问已访问节点的深度优先遍历算法。

    Random Walk 算法具有两个主要特征:可扩展可并行。可扩展是指在后续添加新的信息时,可只学习新的节点信息,无需从头学习。可并行是指,可以同时从不同的节点处开始游走。

    Skip-Gram 算法

    内容比较多,单独记录在了另外一篇文章。

    【Word2Vec】Skip-Gram 算法

    效果展示

    本文中,通过 DeepWalk 算法获取图网络表示后,使用 K-Means 算法进行聚类,得到如下图所示的实验结果。

    实验数据选取了成熟的空手道图网络,设置低维嵌入维度 d=2d=2,不同颜色代表节点的聚类。

    可见,将嵌入表示维数压缩至 d=2d=2 的情况下,也取得了较好的聚类效果。

    展开全文
  • 目录图神经网络DeepWalk 算法原理DeepWalk算法 图网络现在非常的流行,应用场景也十分的广泛,在推荐领域应用也十分广泛,在召回阶段graph-embedding是很有效的一种方式。以下内容参考浅梦大神的笔记。 图神经网络 ...

    图网络现在非常的流行,应用场景也十分的广泛,在推荐领域应用也十分广泛,在召回阶段graph-embedding是很有效的一种方式。以下内容参考浅梦大神的笔记

    图神经网络

    主要包括Graph Embedding(基于随机游走)和Graph CNN(基于邻居汇聚)两部分。这里先看下Graph Embedding的相关内容。Graph Embedding技术将图中的节点以低维稠密向量的形式进行表达,要求在原始图中相似(不同的方法对相似的定义不同)的节点其在低维表达空间也接近。得到的表达向量可以用来进行下游任务,如节点分类,链接预测,可视化或重构原始图等。

    DeepWalk 算法原理

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

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

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

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

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

    在这里插入图片描述

    DeepWalk算法

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

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

    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))
    

    Word2vec
    可以直接用gensim里的Word2Vec了。

    from gensim.models import Word2Vec
    w2v_model = Word2Vec(walks,sg=1,hs=1)
    
    展开全文
  • | Deepwalk算法介绍Deepwalk 介绍Deepwalk 流程总结参考资料 Hi~这里是Linzhuo,是口袋AI算法小队的成员,研究方向主要为计算机视觉和推荐系统。Linzhuo最近要入职啦,为了能更好的适应工作的节奏,最近开始复 (xian...
  • 参考文献 Perozzi B, Alrfou R, ... DeepWalk: online learning of social representations[J]. 2014:701-710. DeepWalk源码 《DeepWalk: Online Learning of Social Representations》笔记 C实现的DeepWalk ...
  • DeepWalk 什么是网络嵌入 将网络中的点用一个低维的向量表示,并且这些向量要能反应原先网络的某些特性。 一种网络嵌入的方法叫DeepWalk,它的输入是一张图或者网络,输出为网络中顶点的向量表示。DeepWalk通过截断...
  • 【Graph Embedding】: DeepWalk算法

    千次阅读 2019-03-21 23:35:23
    论文“DeepWalk: Online Learning of Social Representations” 发表在kdd2014, 下载地址:https://arxiv.org/pdf/1403.6652.pdf 作者开源的代码:https://github.com/phanein/deepwalk 文章提出的deepwalk用于...
  • | DeepWalk算法 文章转载自微信公众号“硬科技课堂”,经作者同意转载,若需转载请联系原作者。 01 社交网络数据是一种图,自然语言,是一种序列数据,那社交网络数据和自然语言是一回事吗? 表面看,确实是风马牛...
  • 本文首先从整体介绍一下图表示学习,然后分别从原理,核心代码,应用三个部分介绍 DeepWalk 。 图表示学习 我们都知道在数据结构中,图是一种基础且常用的结构。现实世界中许多场景可以抽象为一种图结构,如社交...
  • 该算法首先基于矩阵分解的DeepWalk算法分解得到网络的表示向量;然后通过余弦相似度计算每对节点之间的相似度,构建目标网络的相似度矩阵;最后利用相似度矩阵,在三个真实的引文网络中进行链路预测实验。实验结果...
  • Deepwalk(深度游走)算法简介

    万次阅读 多人点赞 2019-09-11 12:51:18
    深度游走:一种社交表示的在线学习算法主要思想Deepwalk算法参考文献 主要思想 Deepwalk是一种将随机游走(random walk)和word2vec两种算法相结合的图结构数据挖掘算法。该算法能够学习网络的隐藏信息,能够将图中的...
  • 渣渣的deepwalk之旅——win10下deepwalk配置和运行

    千次阅读 热门讨论 2017-08-02 12:24:36
    渣渣的deepwalk之旅刚开始学习网络表示学习,看完《Deepwalk Online learning of social representations》后,打算去github上下载源码并自己测试,实现deepwalk算法,结果就开始漫长的修正bug之路: 对deepwalk论文...
  • deepwalk论文及算法阅读笔记

    千次阅读 2018-03-11 15:35:30
    论文题目:《DeepWalk: Online Learning of Social Representations》出版时间2014年6月 这篇文章是网络表示学习的经典文章,下面将简单介绍这篇文章的算法思想,如有不对的地方,欢迎指正!!!! 这篇论文提出的...
  • 万物皆可Embedding系列会结合论文和实践经验进行介绍,前期主要集中在论文中,后期会加入实践经验和案例,目前已更新: 万物皆可Vector之语言模型:从N-Gram...DeepWalk算法原理、代码实现和应用说明 后续会持续更
  • 基于deepwalk图嵌入的match解读

    千次阅读 2019-01-08 21:07:49
    目录 一、deepwalk解读 1. deepwalk介绍 ...3. deepwalk算法和流程实现 二、deepwalk在推荐应用 1. 目标 2. 代码说明 2.1 数据格式 2.2 代码说明 3. 实验输出 目前推荐系统常用的召回方法有ite...
  • 本文主要涉及图游走算法DeepWalk的代码实现。1. DeepWalk采样算法对于给定的节点,DeepWalk会等概率的选取下一个相邻节点加入路径,直至达到最大路径长度,或者没有下一个节...
  • deepwalk 主要描述的是Deep Learning的方法学图结构, 学出每个节点的隐含表示(比较像LSA、LDA、word2vec) 主要是基于随机游走 实验步骤及代码 1.http://www.perozzi.net/projects/deepwalk/论文地址 2....
  • DeepWalk是一种利用的截断随机游走获得网络的结构信息,来进行网络嵌入的算法。将网络中的节点嵌入到一个潜在的连续空间中。 一.随机游走 DeepWalk是利用截断随机游走来获取节点的上下文信息(可以认为是网络的局部...
  • 1、Deepwalk 和 Node2vec 这些图算法的本质就是特征提取器,对graph进行采样(Sampling),对采样出来的序列构造模型(embedding),最终把节点转化为特征向量,即为embedding。 2、图算法的优势 graph是对复杂的...
  • 目录图游走类算法目标基本思路Word2vec算法思想整体架构Skip Gram——根据中心词预测上下文Negative Sampling——负采样应用到图嵌入领域DeepWalk整体架构Random Walk具体过程 图游走类算法 图游走算法可以理解为一...
  • DeepWalk

    2020-09-18 17:59:21
    DeepWalk ...DeepWalk作为一种在线学习算法,可建立有效的增量结果,并且可以并行化。事实上DeepWalk已经可以称作是上古的图表示学习的方法了,这篇文章主要是考古用。 DeepWalk 图的点特征表示学习定
  • deepwalk+word2vec 比较简单,效果也还可以。这种方法再此不再介绍。 接下里记下我对line算法的一些理解。 先说line算法要解决的问题。 1、需要能够表示有向图。 2、能够体现节点的权重,边的权重。节点的权重论文中...
  • 经典数据结构与算法层面的:最小生成树(Prim,Kruskal,…),最短路(Dijkstra,Floyed,…),拓扑排序,关键路径等 概率图模型,涉及图的表示,推断和学习,详细可以参考Koller的书或者公开课 图...
  • DeepWalk的加权随机游走实现(Python) 带有加权边缘图的deepwalk [1]在这里实现。 安装: 安装原始的deepwalk软件包: pip install deepwalk 将'main.py'和'weighted_random_walk.py'移至python lib目录以进行...
  • 推荐系统(二)Graph Embedding之DeepWalk

    千次阅读 2020-01-28 16:13:25
    本篇博客概述了DeepWalk的由来以及算法的基本过程,其基本内容包括:1. Graph Embedding的由来,2. Graph Embedding中Graph的构建,3. RandomWalk+Word2Vec算法介绍,3. 代码实现,4. DeepWalk算法的缺点

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,572
精华内容 1,028
关键字:

deepwalk算法