如何把节点映射成D维向量：（先对节点进行分析是非常必要的）

• 人工特征工程：节点重要度、集群系数、Graphlet

• 图表示学习：通过随机游走构造自监督学习任务，DeepWalk、Node2Vec

• 矩阵分解

• 深度学习：图神经网络

• 图表示学习：

• 不需要特征工程，将各个模态输入转为向量，自动学习特征

• 将节点映射为d维向量，向量具有低维（向量维度远小于节点数）、连续（每个元素都是实数）、稠密（每个元素都不为0），与下游任务无关

• 嵌入d维空间：

• 向量相似度反映节点相似度

• 嵌入向量包含网络连接信息

1 基本框架（编码器+解码器）

• 编码器：输入一个节点，输出这个节点的D维向量，

• 解码器：输入这个节点的dd维向量，输出节点相似度，向量点乘数值反映节点的相似度（需要人为定义）

• 优化目标：迭代优化每个节点的dd维向量，使得图中相似节点向量数量积大，不相似节点向量数量积小 ==> 对于每一个相似的节点对(u, v)最大化

1.1 编码器

• 最简单的编码器：查表（浅编码器），采用独热编码，

• Z表示一个矩阵，每一列表示一个节点，行数表示向量的维度

• 优化Z矩阵的方法：DeepWalk、Node2Vec

1.2 解码器

• 基于节点相似度（key：定义相似度的计算方法）

• 目标：对

• 进行优化迭代每个节点的D维向量，使得使得图中相似节点向量数量积大，不相似节点向量数量积小

• 直接优化嵌入向量，使用随机游走方式，如果两个节点出现在同一个随机游走序列中，就反映了这两个节点是相似的，并与下游任务无关

2 基于随机游走的方法

2.1 随机游走的概念

• 随机游走：可以定义具体的策略，在图中进行游走

• 图机器学习可以和NLP对应：

• 图：文章

• 随机游走序列：句子

• 节点：单词

• DeepWalk：Skip-Gram

• Node Embedding：Word Embedding

2.2 随机游走的方法步骤

• P(v|z_u)P(v∣zu)：从uu节点触发的随机游走序列经过vv节点的概率

• 使用softmax方法计算P(v|z_u)P(v∣zu)：

• 具体步骤：

1. 采样得到若干随机游走序列，计算条件概率

1. 迭代优化每个节点的D维，使得序列中共现节点向量数量积大，不共现节点向量数量积小

• 优点：表示能力、计算便捷、无监督/自监督学习问题

• 使用极大似然估计，优化目标函数

• 其中

• 表示从uu节点出发的随机游走序列的所有邻域节点

• 整个优化的目标函数：

• 其中

• 遍历所有节点，并遍历从uu节点出发的随机游走序列的所有邻域节点，计算节点uu和节点vv在该随机游走序列中共现。

2.3 计算优化

• 负采样：

• 其中

• （非均匀分布采样），

• 梯度下降：

• 全局梯度下降（Gradient Descent）：求所有节点uu总梯度

• ，并迭代更新

• 随机梯度下降（Stochastic Gradient Descent）：每次随机游走优化一次

• ，并迭代更新

3 Node2Vec

• 有偏二阶随机游走

• 通过两个超参数pp和qq控制随机游走的方向，其中概率\displaystyle \frac{1}{p}p1表示退回上一个节点，概率\displaystyle \frac{1}{q}q1表示走向更远的节点，1表示走向上一个节点距离相等的节点

• 设置不同的超参数：

• pp大qq小：DFS深度优先（探索远方），应用于同质社群（homophily community）

• pp小qq大：BFS广度优先（探索近邻），应用于节点功能角色（中枢、桥接、边缘）（structural equivalence）

• Node2Vec算法：

1. 计算每条边的随机游走概率

2. 以uu节点为出发点，长度为ll，生成rr个随机游走序列

3. 用随机梯度下降优化目标函数

4 随机游走的图嵌入的讨论与总结

• 基于随机游走的图嵌入的缺点：

• 随机游走的图嵌入方法都是对图中已有的节点计算特征，无法立刻泛化到新加入的节点，其实是某种程度的过拟合

• 只是探索相邻局部信息，只能采样出地理上相近的节点

• 仅利用图本身的连接信息，并没有使用属性信息

• DeepWalk：

• 首个将深度学习和自然语言处理的思想用于图机器学习

• 在稀疏标注节点分类场景下，嵌入性能卓越

• 均匀随机游走，没有偏向的游走方向

• 需要大量随机游走序列训练

• 基于随机游走，管中窥豹，距离较远的两个节点无法相互影响。看不到全图信息。

• 无监督，仅编码图的连接信息，没有利用节点的属性特征。

• 没有真正用到神经网络和深度学习

• Node2Vec：

• 解决图嵌入问题，将图中的每个节点映射为一个向量（嵌入）

• 向量（嵌入）包含了节点的语义信息（相邻社群和功能角色）

• 语义相似的节点，向量（嵌入）的距离也近

• 向量（嵌入）用于后续的分类、聚类、Link Prediction、推荐等任务

• 在DeepWalk完全随机游走的基础上，Node2Vec增加参数p和q，实现有偏随机游走。不同的p、q组合，对应了不同的探索范围和节点语义

• DFS深度优先探索，相邻的节点，向量（嵌入）距离相近

• BFS广度优先探索，相同功能角色的节点，向量（嵌入）距离相近

• DeepWalk是Node2Vec在p=1，q=1的特例

• 结

5 全图嵌入

• 所有节点的D维向量求和：

• 引入虚拟节点，并求出虚拟节点嵌入，作为整个子图的嵌入

• 匿名随机游走