专栏首页NewBeeNLPDeepWalk:图网络与NLP的巧妙融合
原创

DeepWalk:图网络与NLP的巧妙融合

最近这段时间一直在做图网络相关,也差不多收尾了,有空整体复盘了下,大致以下几个主题,不过没整理完全哈哈

顺手再安利几份资料吧,

  • 斯坦福的CS224W课程
  • 清华大学唐杰老师的很多分享,在之前文章中
  • 清华大学 thunlp/GNNPapers
  • 一些大佬们的新书:《Graph Representation Learning》、《Deep Learning on Graphs》
  • 等等

ok,回到正题,今天要介绍的这篇是『Graph Embedding』系列第一篇,十分经典

enjoy~

TL;DR

DeepWalk是首次将深度学习技术(无监督学习)引入到网络分析(network analysis)中的工作,它的输入是一个图,最终目标就是获得网络图中每个结点的向量表示 \mathbf{X}_{e} \in \mathbb{R}^{|V| \times d} 。毕竟万物皆可向量,得到向量之后能做的事情就非常多了。如下所示是论文中给出的Karate network例子。

先验知识

说到生成向量表示,最有名的莫过于Word2Vec了,那么是不是可以将network embedding的问题转化为熟悉的word embedding形式呢?这样我们就可以借用word2vec的思想来解决了。

转化的方式就是Random Walk ,通过这种方式将图结构表示为一个个序列,然后我们就可以把这些序列当成一个个句子,每个序列中的结点就是句子中的单词。

在这里插入图片描述

简单的说,DeepWalk = RandomWalk + SikpGram, 下面我们来具体介绍下两种技术。

Random Walk

随机游走,顾名思义,就是从输入图中的任意一个结点 v_{i} 开始,随机选取与其邻接的下一个结点,直至达到给定长度 t, 生成的序列 \tilde{\mathcal{W}}_{v_{i}}=\left(\mathcal{W}_{v_{i}}^{1},\cdots, \mathcal{W}_{v_{i}}^{k}, \cdots, \mathcal{W}_{v_{i}}^{t}\right)

在论文中,对于每一个顶点 v_{i}, 都会随机游走出 \gamma 条序列。

采用随机游走有两个好处:

  • 利于并行化:随机游走可以同时从不同的顶点开始采样,加快整个大图的处理速度;
  • 较强适应性:可以适应网络局部的变化;

Skip Gram

word2vec的skip-gram相信大家都非常熟悉了,这里就不再赘述,放一张图。

DeepWalk

结合上面两点, deepwalk其实就是首先利用random walk来表示图结构,然后利用skip-gram模型来更新学习节点表示。算法流程如下所示:

算法有两层循环,第一层循环采样 \gamma 条路径,第二层循环遍历图中的所有结点随机采样一条路径并利用skip-gram模型进行参数更新。

其中第2步构建二叉树的目的是为了方便后续 SkipGram模型的层次softmax算法。

参数更新的流程如下:

一个小结

deepwalk可以说给网络学习方向打开了一个新思路,有很多优点:

  • 支持数据稀疏场景
  • 支持大规模场景(并行化)

但是仍然存在许多不足:

  • 游走是完全随机的,但其实是不符合真实的社交网络的;
  • 未考虑有向图、带权图

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • DeepWalk:图网络与NLP的巧妙融合

    最近这段时间一直在做图网络相关,也差不多收尾了,有空整体复盘了下,大致以下几个主题,不过没整理完全哈哈(下次一定

    kaiyuan
  • 【NLP保姆级教程】手把手带你RCNN文本分类(附代码)

    之前介绍的都是属于深度神经网络框架的,那么在Deep Learning出现或者风靡之前,文本分类是怎么做的呢?

    kaiyuan
  • Python中那些低调有趣的模块

    python语言上位成功的其中一个原因是其丰富的社区支持,不管你有什么奇奇怪怪的需求,大概率能在网上搜到一个库来便捷实现。这篇文章就列举了几个低调的python...

    kaiyuan
  • 3行代码实现小程序直播,带美颜优惠券抽奖功能

    注意我们上图红色框里的一些要求。必须要满足这些条件,才可以开通直播功能。更详细些的如下:

    编程小石头
  • Power Query 系列 (04) - 从 Web 导入数据

    因为网络页面具有很大不确定性,比如数据变化,或者页面过几天就不见了,所以无法保证我所选取的页面在您查看的时候一定还在。但基本方法类似,您也可以找到一个类似的页面...

    StoneWM
  • 搭建自己的技术博客系列(一)使用 hexo 搭建一个精美的静态博客

    https://github.com/ppoffice/hexo-theme-icarus

    黄小斜
  • 测点大数据洪小林:工业大数据蓝海已现,电力产业能效提升需求正快速增长 | 镁客请讲

    对于一家成立仅7个月,且经历了年初这场突如其来的疫情的初创公司而言,当下最需要做的是什么?

    镁客网
  • TIOBE 11月编程语言排行榜:前十为什么又变了!

    首先,C 现在非常接近 Java,排在 Java 后指数仅差 0.2%,预计年底之前 C 会再次冲上第一位;

    老九君
  • Idea 常用快捷键

    ———–自动代码——– 常用的有fori/sout/psvm+Tab即可生成循环、System.out、main方法等boilerplate样板代码 例...

    用户1212940
  • python基本数据类型

    在python中变量不需要声明数据类型,但是每个变量使用前都必须先赋值,只有赋值后变量才会被创建。所以在python中变量就是变量没有类型,我们所说的类型是变量...

    端碗吹水

扫码关注云+社区

领取腾讯云代金券