【Datawhale图机器学习】图嵌入表示学习

图嵌入表示学习

学习视频：https://www.bilibili.com/video/BV1AP4y1r7Pz/

如何把节点映射成D维向量？

• 人工特征工程：节点重要度、集群系数、Graphlet
• 图表示学习：通过随机游走构造自监督学习任务。DeepWalk、Node2Vec
• 矩阵分解
• 深度学习：图神经网络

图嵌入-概述

表示学习：自动学习特征将各个模态输入转为向量
嵌入向量包含网络连接信息

图嵌入-基本框架 编码器-解码器

V：节点集
A：连接矩阵
仅利用连接信息，没有利用节点属性信息
向量点乘数值（余弦相似度）反映节点的相似度

最简单的编码器：查表

没有使用节点类别标签
没有使用节点属性特征
直接优化嵌入向量
与下游任务无关

图嵌入：基于随机游走的方法

图机器学习 NLP
图：文章
随机游序列：句子
节点：单词
DeepWalk：Skip-Gram
Node Embedding：Word Embedding

随机游走序列

1.采样得到若干随机游走序列计算条件概率
2.迭代优化每个节点的D维向量，使得序列中共现节点向量数量积大不共现节点向量数量积小

为什么随机游走序列
1.表示能力
2.计算便捷

随机梯度下降

缺点

• 无法理科泛化到新加入的节点，某种程度的过拟合，重新采样随机游走序列优化更新所有节点嵌入向量
• 结构上相似，地理上远隔
• 仅使用图本身的连接信息，没利用属性信息

DeepWalk 讨论

• 首个将深度学习和自然语言处理的思想用于图机器学习。
• 在稀疏标注节点分类场景下，嵌入性能卓越。
• 均匀随机游走，没有偏向的游走方向。(Node2Vec)
• 需要大量随机游走序列训练。
• 基于随机游走，管中窥豹。距离较远的两个节点无法相互影响。看
不到全图信息。（图神经网络）
• 无监督，仅编码图的连接信息，没有利用节点的属性特征。
• 没有真正用到神经网络和深度学习。

Node2Vec 图嵌入算法

• Node2Vec解决 图嵌入 问题，将图中的每个节点映射为一个向量（嵌入）。
• 向量（嵌入）包含了节点的语义信息（相邻社群和功能角色）。
• 语义相似的节点，向量（嵌入）的距离也近。
• 向量（嵌入）用于后续的分类、聚类、Link Prediction、推荐等任务。
• 在DeepWalk完全随机游走的基础上，Node2Vec增加p、q参数，实现有偏
随机游走。不同的p、q组合，对应了不同的探索范围和节点语义。
• DFS深度优先探索，相邻的节点，向量（嵌入）距离相近。
• BFS广度优先探索，相同功能角色的节点，向量（嵌入）距离相近。
• DeepWalk是Node2Vec在p=1，q=1的特例。

嵌入整张图

匿名随机游走嵌入：每次见到不同节点，就发一个新编号

Anonymous Walk Embeddings, ICML 2018 https://arxiv.org/pdf/1805.11921.pdf

扩展阅读

• DeepWalk-算法讲解：https://www.bilibili.com/video/BV1o94y197vf
• DeepWalk-论文逐句精读：https://www.bilibili.com/video/BV1pW4y1z7pb
• DeepWalk代码实战-维基百科词条图嵌入可视化：https://www.bilibili.com/video/BV1et4y187Gd
• Node2Vec-算法讲解：https://www.bilibili.com/video/BV1BS4y1E7tf
• Node2Vec-论文逐句精读：https://www.bilibili.com/video/BV1vU4y1i77T
• Node2Vec代码实战-《悲惨世界》小说人物图嵌入、Alias Sampling复现：
https://www.bilibili.com/video/BV1VS4y1E7Me
• Anonymous Walk Embeddings：https://arxiv.org/pdf/1805.11921.pdf
• Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec：
https://arxiv.org/abs/1710.02971
• 随机梯度下降讲解：https://www.bilibili.com/video/BV1K7411W7So