图嵌入表示学习

---

---

---

一、图嵌入简介

传统机器学习（特征工程）：抽取D个特征编码成D维向量，再使用机器学习算法进行训练和预测

图表示学习：

1. 不需要特征工程，将各个模态输入转为向量，自动学习特征
2. 将节点映射为d维向量，向量具有低维（向量维度远小于节点数）、连续（每个元素都是实数）、稠密（每个元素都不为0），与下游任务无关

嵌入d维空间：

1. 向量相似度反映节点相似度
2. 嵌入向量包含网络连接信息

二、基本框架（编码器+解码器）

编码器：输入一个节点，输出这个节点的D维向量
解码器：输入这个节点的d维向量，输出节点相似度，向量点乘数值反映节点的相似度（需要人为定义）
优化目标：迭代优化每个节点的d维向量，使得图中相似节点向量数量积大，不相似节点向量数量积小

2.1编码器

最简单的编码器：查表（浅编码器），采用独热编码，Z表示一个矩阵，每一列表示一个节点，行数表示向量的维度
优化Z矩阵的方法：DeepWalk、Node2Vec

2.2解码器

基于节点相似度
目标：对进行优化迭代每个节点的D维向量，使得使得图中相似节点向量数量积大，不相似节点向量数量积小
直接优化嵌入向量，使用随机游走方式，如果两个节点出现在同一个随机游走序列中，就反映了这两个节点是相似的，并与下游任务无关

三、基于随机游走的方法

3.1随机游走的概念

随机游走：可以定义具体的策略，在图中进行游走
图机器学习可以和NLP对应：

1. 图：文章
2. 随机游走序列：句子
3. 节点：单词
4. DeepWalk：Skip-Gram
5. Node Embedding：Word Embedding

3.2随机游走的步骤

$P(v|z_u)$从u节点触发的随机游走序列经过v节点的概率
具体步骤:

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

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

四、Node2Vec

有偏二阶随机游走

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

设置不同的超参数：

• p大q小：DFS深度优先（探索远方），应用于同质社群（homophily community）
• p小q大：BFS广度优先（探索近邻），应用于节点功能角色（中枢、桥接、边缘）（structural equivalence）

Node2Vec算法：

1. 计算每条边的随机游走概率
2. 以u节点为出发点，长度为l，生成r个随机游走序列
3. 用随机梯度下降优化目标函数

五、矩阵分解

通过邻接矩阵分解，可得：

1. 两个节点之间相连：节点向量的数量积是1，两个节点是相似的
2. 两个节点之间不相连：节点向量的数量积是0，两个节点是不相似的