Node Embedding

图表征学习(Graph Representation Learning)

将图中的节点，边等要素映射到低维的向量空间（即embedding），学习一个函数$f(u)$,将图中的节点$u$都映射到一个$d$维的向量空间：

$f:u\rightarrow\R^d$

输入节点，输出$d$维向量，这个向量称为节点的嵌入表示（embedding）

Embedding的作用

能保留节点的相似性，连接较近的两个节点会有相似的嵌入表示
编码网络信息，嵌入向量不仅包含结点的特征，还包含图的拓扑信息
嵌入向量可以作为输入，用于””节点分类，链路预测，图分类的等任务

Embedding Node

嵌入的目标是将节点进行编码，使得得到的向量的相似性近似于图中的相似性

Encoder：将每一个节点编码成一个低维向量

Similarity function：区分如何将向量空间的关系映射到原始的网络上的关系

Decoder：接受节点的嵌入向量作为输入，输出相似性分数

要做的就是优化Decoder的参数使得计算的相似性分数和嵌入向量的点积相近

$similarity(u,v)\approx z_{u}^Tz_{v}$

“Shallow” Encoding

浅层编码，直接通过为每一个节点分配一个嵌入向量来表示节点。

编码器仅是一个嵌入查找表（Embedding lookup table）,每个节点被分配一个唯一的嵌入向量

define node similarity

解码器的选择主要看相似性是如何定义的，比如连接的节点有相似性还是有公共邻居的节点有相似性等等。

随机游走在节点嵌入上的应用

给定一个起始点，然后在这个起始点的邻居内随机选择一个，移动到这个邻居，然后在邻居内随机选择一个，以此类推，得到的点的随机序列就叫这个图上的随机游走。

$z_{u}^Tz_{v}\approx u,v\in random \ walk$

如何用随机游走估计相似性

估计从节点u开始进行随机游走时，访问节点v的概率$P_{R(v|u)}$,$R$是随机游走的策略，决定了随机游走的规则（比如如何选择邻居节点）。

过程：从节点u开始按照随机游走策略，遍历图中的路径，记录v在游走路径中的频率，作为$P_{R(u|v)}$的估计值

随机游走的作用：捕获结点的局部和全局图结构信息，节点u和v在随机游走中共同出现的频率可以翻译他们在图中的相似性

如何优化嵌入

如果两个节点的嵌入向量距离较近（点积较大），则表示他们在图中的随机游走出现的概率高，相似性强

我们要学习的是结点的嵌入向量，使得嵌入向量的相似性能够反映随机游走中的共现概率（嵌入向量的相似性通过点积来衡量），优化嵌入向量，使得节点嵌入向量之间的点击能近似等于$P_{R(u|v)}$

最大化随机游走中邻居节点集合的预测概率

$arg\ max_{z}\sum_{u\in V}log\ P(N_{R(U)}|z_{u})$

邻居集合$N_{R(u)}$是从节点u开始的随机游走中访问的节点集合（多重集合，可重复），随机游走策略$R$决定这些节点的选择规则

最大化目标的等价形式：

最大化

$log\ P(N_{R(u)}|z_{u})$

等价于最小化负对数似然：

$\mathcal{L} = -\sum_{u\in V}\sum_{v\in N_{R(u)}}\log{P(v|z_u)}$

使用softmax函数建模$P(v|z_u)$

$P(v|z_u)=\frac{exp(z_u^\top z_u)}{\sum_{n\in V}exp(z_u^\top z_n)}$

损失函数的定义

$\mathcal{L}= -\sum_{u\in V}\sum_{v\in N_{R(u)}}\frac{exp(z_u^\top z_u)}{\sum_{n\in V}exp(z_u^\top z_n)}$

优化过程就是寻找$z_n$使得$\mathcal{L}$最小，我们定义好损失函数后，优化过程可以采用随机梯度下降

随机游走总结

在固定长度上进行随机游走
对每一个节点$u$，收集其为起始点进行随机游走得到的$N_R(u)$
使用随机梯度下降对损失函数进行优化

node2vec

node2vec是一种基于随机游走的嵌入方法，开发了一种带偏置的二阶随机游走策略R，用于生成结点的邻域$N_{R(u)}$,从而学习更丰富的嵌入

带偏置的随机游走

在图的局部视图和全局试图进行权衡。

随机游走有两个参数：

返回参数p，决定是否要返回到上一个顶点
进出参数q，决定是向外（DFS）还是向内（BFS）走

带偏置的随机游走的一步

随机游走通过(t,w)这条边到达了w
为节点w的邻居节点设置边的转移概率

节点w的邻居节点有三类
- 和t距离为0的节点（t本身）
  
  转移概率为$\frac{1}{p}$
- 和t距离为1的节点（t的邻居节点）
  
  转移概率为1
- 和t距离为2的节点（t的非直接邻居）
  
  转移概率为$\frac{1}{q}$

转移概率是没有归一化的，需要标准化为总合为1的分布

node2vec算法

计算边的转移概率

对每条边计算转移概率
模拟随机游走
优化嵌入

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

最大化随机游走中邻居节点的共现概率

Embedding Entire Graphs

将图或子图映射为一个嵌入向量，用于识别有毒分子和无毒分子或识别异常图等任务

approach 1

用节点的嵌入方式对一个图的所有节点进行嵌入向量映射，然后将所有的嵌入向量映射相加得到图的嵌入向量。

approach 2

引入一个虚拟节点来代表图，然后对这个虚拟节点计算嵌入向量

矩阵分解于嵌入向量

每个节点的嵌入向量为列组成的矩阵称为嵌入矩阵，记作$Z$，列数为节点数，行数为嵌入维度，优化目标是列向量的点积。

如果我们定义相似性为两个节点是否相连，那么两个节点的嵌入向量的点积就应该近似与图的邻接矩阵的对于项，也就是

$z_v^\top z_u=A_{u,v}$

进一步我们得到

$Z^\top Z=A$

由于嵌入维度一般远小于节点数，将$A$精确分解比较困难，但是我们可以将$Z$近似化。优化目标为

$\min||A-Z^\top Z||_2$

优化$Z$使得弗罗贝尼乌斯范数（矩阵元素平方和的平方根）最小

得到结论：点积作为decoder，相似性为边的连接性等价于对邻接矩阵的矩阵分解

PageRank

将一个页面的链接数作为衡量标准

每一个页面的重要程度和连接到这个页面的源页面的重要程度相关，每一个链接的重要程度等于这个链接的发出页面的重要程度除以这个页面发出的总链接数，每一个页面的重要程度等于这个链接进入这个页面的所有链接的重要程度之和

所有页面的链接方式可以表示为一个矩阵：

矩阵的每一列表示一个节点链接到所有节点的情况,$d_j$是节点$j$指向其他页面的链接数

$M_{ij}=\frac{1}{d_j}$

pagerank满足

$r=Mr$

$r$是随机矩阵$M$特征值为1的特征向量

GNN

终于来到图神经网络的正式部分。

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。