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

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

作者 | kaiyuan

整理 | NewBeeNLP公众号

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

顺手再安利几份资料吧

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

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

  • 论文:DeepWalk: Online Learning of Social Representations[1]
  • 代码:https://github.com/phanein/deepwalk

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可以说给网络学习方向打开了一个新思路,有很多优点:

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

但是仍然存在许多不足:

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

本文参考资料

[1]

DeepWalk: Online Learning of Social Representations: https://arxiv.org/abs/1403.6652

- END -

本文分享自微信公众号 - NewBeeNLP(NewBeeNLP),作者:kaiyuan

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 微软ALUM:当语言模型遇到对抗训练

    本文把对抗训练用到了预训练和微调两个阶段,对抗训练的方法是针对embedding space,通过最大化对抗损失、最小化模型损失的方式进行对抗,在下游任务上取得...

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

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

    kaiyuan
  • Transformers Assemble(PART III)

    第四篇也非常有趣提出将独立的词向量替换成自变量为位置的函数,引入了复数空间综合了词向量和位置向量」

    kaiyuan
  • 想去腾讯、阿里、字节跳动?先学会系统性成长

    从我身边听说的情况来看,只要技术扎实,很多人都能通过一、二面,却很容易死在三四面,原因就在于:

    GitHubDaily
  • 简单理解感受野

    最近在组会讲解框架时,在感受野这个小知识点,大家开始产生歧义,今天我就简单的给大家讲解下这个小知识点,也给初学者带来一个对Receptive Field崭新的认...

    计算机视觉研究院
  • 深度学习——感受野

    最近在组会讲解框架时,在感受野这个小知识点,大家开始产生歧义,今天我就简单的给大家讲解下这个小知识点,也给初学者带来一个对Receptive Field崭新的认...

    计算机视觉研究院
  • 数据结构与算法 - 树形结构目录一、树二、二叉树三、树、森林与二叉树的转换

    且行且珍惜_iOS
  • List以及其实现类(ArrayList、LinkList、Vector)简介

    洋仔聊编程
  • 开往视觉对话研究的列车——2018年第一届视觉对话挑战赛

    用户1737318
  • 5.2.2 邻接表法

    当一个图为稀疏图时,使用邻接矩阵表示法显然要浪费大量的存储空间。而图的邻接表示法结合了顺序存储和链式存储方法,大大减少了这种不必要的浪费。

    week

扫码关注云+社区

领取腾讯云代金券