Bilibili-DeepWalk【图神经网络论文精读】

图机器学习大纲

• 新论文精读专题

• 图机器学习、图数据挖掘、图神经网络GNN、图卷积神经网络GCN

• 知识图谱、知识计算、对话问答

• 推荐系统、社会计算、媒体计算、网络智能

• 搜索引擎、社交网络、情感计算

• 学习路径与必读论文清单

• Stanford CS224W、知识图谱实战

• DeepWalk、Node2vec

• PageRank

• GNN、GCN、Graph-SAGE、GIN、GAT

• Trans-E、Trans-R

• 扩展学习：图计算

• 图论与数据结构：

• 中心性、连通性、最短路径、关键路径、拓扑排序、聚集系数、标签传播

• 概率图模型：

• Koller的公开课

• 图机器学习：

• 图神经网络

• 图嵌入 Graph Embedding

• 节点、边、子图、全图

• 基于

• 手工构造特征、矩阵分解、随机游走、图神经网络

介绍

DeepWalk 将 graph 的每一个节点编码为一个D维向量（Embedding）（无监督学习）

Embedding 中隐式包含了 graph 中的社群、连接、结构信息，可用于后续节点分类等下游任务。

• Word2Vec：

• 用周围词预测中心词，CBOW

• 用中心词预测周围词

• DeepWalk 用大量的随机游走序列去训练

自然语言处理中每一个单词在 DeepWalk 中是每一个节点，word2vec 是把每一个单词变成一个向量，在 DeepWalk 中是把每个节点变成一个向量。

Embedding 嵌入的艺术

计算机认识向量，表示学习/representation learning，把任何一个东西变成向量，然后进行处理；

Word2Vec 词嵌入

把每个词变成一个向量，并反应词和词之间的关系；NLP开山之作；

《Efficient Estimation of Word Representations in Vector Space》[论文链接] 2013年，被引：33279

《Distributed Representations of Words and Phrases and their Compositionality》[论文链接] 2013年，被引：37451，

巧妙之处：自监督

两个任务：

• 用周围词预测中心词，CBOW

• 用中心词预测周围词

随机游走

假设：相邻节点应该具有相似的Embedding

可以利用 Word2Vec 的 Skip-gram，把每一个节点编码成向量；

DeepWalk

https://dl.acm.org/doi/10.1145/2623330.2623732

PPT 链接

We can also create features by transforming the graph into a lower dimensional latent representation.

DeepWalk learns a latent representation of adjacency matrices using deep learning techniques developed for language modeling.

• Advantages of DeepWalk

• Scalable - An online algorithm that does not use entire graph at once

• Walks as sentences metaphor

• The cool idea

• Short random walks = sentences（图和语言是互通的）

DeepWalk步骤

• 1、输入 图

• 2、采样随机游走序列

• 3、随机游走序列训练word2vec

• 4、为了解决分类数过多的问题，可以加一个分层softmax（霍夫曼编码树）

• 5、得到每个节点的图嵌入（向量表示）

任务：

• 输入中心词的向量，然后预测周围词（输入2号节点，输出1号、5号节点）

优化：

• Use Stochastic Gradient Descent to update both the classifier weights and the vertex representation simultaneously.（同时优化分类器交叉熵和词嵌入网络）

讨论：

• 优点：

• 缺点：