一文详解图表示学习

作者: 晓柒NLP与药物设计 | 来源:发表于2022-06-30 22:27 被阅读0次

Graph Embedding与Word Embedding一样，目的是用低维、稠密、实值的向量表示网络中的节点。目前Graph Embedding在推荐系统、搜索排序、广告等领域非常流行，并且也取得了非常不错的实践效果。图Graph表示一种==二维==的关系，而序列Sequence表示一种==一维==的关系。因此，要将图转换为Graph Embedding，一般需要先通过一些算法把图变为序列；然后通过一些模型或算法把这些序列转换为Embedding。

一. 图表示学习意义

需要使用图形嵌入有以下几个原因:

机器学习图形是有限的，图由边和节点组成。这些网络关系只能使用数学、统计和机器学习的特定子集，而向量空间有更丰富的方法工具集
嵌入是压缩的表示。邻接矩阵描述图中节点之间的连接，它是一个 $|V|×|V|$ 维度的矩阵，其中 $|V|$ 是图中节点的个数，使用邻接矩阵作为大型图的特征空间几乎是不可能的
向量运算比图形上的可比运算更简单、更快

二. 图表示学习常用方法

2.1 DeepWalk

DeepWalk方法是首先以随机游走(Random Walk)的方式在网络中进行节点采样，生成序列，然后使用Skip-Gram模型将序列转换为Embedding的过程(仿照Word2vec)

算法步骤如下：

首先使用Random Walk的方式进行节点采样，其是一种可重复访问已访问节点的深度优先遍历算法。然后给定当前访问起始节点，从其邻居中随机选择一个节点作为下一个访问节点
重复此过程，直到访问序列长度满足预设条件
获取足够数量的节点访问序列后，使用Skip-Gram模型进行向量学习，最终获得每个节点的Embedding

2.1.1 随机游走（random walk）

对于无向图 $G=(V,E)$ ， $e_{i,j}$ 表示顶点 $v_i$ 和顶点 $v_j$ 之间边的权值（如果不存在边则为0）。使用随机游走构建长度为 $T$ 的序列 $\mathcal{S}=\{s^{(1)},s^{(2)},\cdots, s^{(T)}\}$ ，从顶点 $v_i$ 游走到顶点 $v_j$ 的概率为
$\begin{equation}p(s^{(t+1)}=v_j|s^{(t)}=v_i) = \begin{cases} \frac{e_{i,j}}{Z_i}, if \quad e_{i,j} \neq 0 \\ 0, if \quad e_{i,j} = 0 \end{cases}\end{equation} \tag{1}$
其中， $Z$ 为所有以 $v_i$ 为顶点的边的权值之和，即：
$Z_i=\sum_{j=1}^{|V|}e_{i,j}\tag{2}$

显然，顶点 $v_i$ 和顶点 $v_j$ 之间边的权值越大，越有可能从顶点 $v_i$ 游走到顶点 $v_j$ 。random walk可以看作是一个可回头的深度优先搜索。有向图理论上可以进行随机游走，但是容易游走到出度为0的顶点，一般情况下，deep walk用于无向图比较多

2.1.2 word2vec(skip-gram)

使用随机游走得到句子序列后，根据word2vec算法(skip-gram模型)得到目标函数：
$argmax \frac{1}{T}\sum_{t=1}^{T}\sum_{-c \leq j \leq c, j \neq 0}\log p(w_{s^{(t+j)}}|w_{s^{(t)}})\tag{3}$
其中， $w$ 为顶点的向量表示，最开始为随机初始化，随着目标函数的不断优化，逐渐收敛，可以使用hierarchical softmax和negative sampling实现 $p(w_{O}|w_I)$

2.2 Line

LINE算法适用于任意类型的图，包括有向图、无向图、有权图和无权图。使用LINE算法学习到的embeddings可以保留顶点的局部结构和全局结构（local and global network structures）。其核心思想是使用一阶相似度first-order proximity表征==local structure==，使用二阶相似度second-order proximity表征==global structure==

2.2.1 相关定义

first-order proximity:表征顶点与顶点之间的局部相似度，如果顶点 $v_i$ 和 $v_j$ 之间存在边，则一阶相似度为边的权值，否则一阶相似度为0；
second-order proximity:表征顶点 $v_i$ 的邻域和 $v_j$ 的邻域的相似程度（即两个顶点有多少共同的邻居节点）。定义 $S_i=(w_{i,1},\cdots,w_{i,|V|})$ 表示顶点 $v_i$ 与其它顶点的一阶相似度，则顶点 $v_i$ 和 $v_j$ 的二阶相似度可以用 $S_i$ 和 $S_j$ 的相似度衡量

2.2.2 LINE with First-order Proximity

LINE with first-order proximity只适用于无向图，公式(4)用来衡量顶点 $v_i$ 和 $v_j$ 的向量表示之间的一阶相似度。
$p_1(v_i,v_j)=\frac{1}{1+exp(-u_i^{T}u_j)}\tag{4}$
其中， $u_i$ 和 $u_j$ 分别对应顶点 $v_i$ 和 $v_j$ 的向量表示，顶点 $v_i$ 和 $v_j$ 在原始图中的一阶相似度使用empirical probability定义，如公式(5)所示：
$\hat{p}_1(i,j)=\frac{w_{i,j}}{W},W=\sum_{(i,j)\in E} w_{i,j}\tag{5}$
为了使得学习到的embeddings能够保留顶点在原始图中的一阶相似度，最直接的做法是，最小化 $\hat{p}_1(\cdot,\cdot)$ 和 $p_1(\cdot,\cdot)$ 两个分布之间的差异
$O_1=d(\hat{p}_1(\cdot,\cdot),p_1(\cdot,\cdot))\tag{6}$
使用KL-divergence来衡量分布间的差异（ $D_{KL}(P,Q)=\sum_i P(i)\log \frac{P(i)}{Q(i)}$ ），LINE with first-order proximity的目标函数如式：
$O_1=-\sum_{(i,j)\in E}w_{i,j}\log p_1(v_i, v_j)\tag{7}$

2.2.3 LINE with Second-order Proximity

LINE with second-order proximity既可以使用于无向图，也可以适用于有向图。以有向图为例，每个顶点都有2个向量表示：

顶点 $v_i$ 自身的embedding $u_i$
顶点 $v_i$ 作为其它顶点的context时的embedding ${u^{'}}_i$ 。

对于有向边(i,j)，给定顶点 $v_i$ ，顶点 $v_j$ 作为 $v_i$ 的上下文(context)，顶点 $v_j$ 相对于顶点 $v_i$ 的一阶相似度为 $p_2(v_j|v_i)$
$p_2(v_j|v_i) = \frac{exp({u^{'}}_j^\top u_i)}{\sum_{k=1}^{|V|}{u^{'}}_k^\top u_i}\tag{8}$
在原始图中，empirical probability为：
$\hat{p}_2(v_j|v_i)=\frac{w_{i,j}}{d_i},d_i=\sum_{k\in N(i)}w_{i,k}\tag{9}$
其中， $N(i)$ 表示顶点 $v_i$ 的out neighbor(与 $v_i$ 出边相连的顶点)。为了使得学习到的embeddings能够保留顶点在原始图中的二阶相似度，最小化 $\hat{p}_2(\cdot|v_i)$ 和 $p_2(\cdot|v_i)$ 两个分布之间的差异：
$O_2=\sum_{i\in V}d(\hat{p}_2(\cdot|v_i),p_2(\cdot|v_i))\tag{10}$

$O_2=-\sum_{(i,j)\in E}w_{i,j}\log p_2(v_j|v_i)\tag{11}$

如果想要学习到的embedding既保留一阶相似度，也保留二阶相似度，最简单的做法是，分别使用LINE with first-order proximity和LINE with second-order proximity训练模型，将得到的embedding拼接

2.2.4 Optimization via Edge Sampling

在使用梯度下降算法优化目标函数(9)时，存在一个问题，如果边 $(i, j)$ 被采样， $Embedding_{i→j}$ 如下：
$\frac{\partial O_2}{\partial u_i}=w_{i,j}\frac{\partial\log p_2(v_j|v_i)}{\partial u_i}\tag{12}$
显然边的权值影响梯度的计算，这会导致模型的learning rate难以确定，如果根据权重大的边确定学习率，那么权重小的边对应的梯度就很小，反之，如果根据权重小的边确定学习率，那么权重大的边对应的梯度就很大。为了解决这一问题，可以对原始图中的边进行采样，每条边被采样的概率正比于该边的权值。令 $W =(w_1,\cdots,w_{|E|}),w_{sum}=\sum_{i=1}^{|E|}w_i$ ，在范围 $[0,w_{sum}]$ 内生成一个随机数，选择随机数所在区间对应的边，作为采样边，可以使用alias table method将采样的复杂度从 $O(|E|)$ 降至 $O(1)$

2.3 Node2vec

Node2ve算法通过表征2种顶点间的关系，得到顶点的低维向量表示

Homophily equivalence

Structural equivalence

homophily equivalence表明直接相连的顶点或是在同一community中的顶点，其embeddings应该比较靠近，如图所示，顶点 $u$ 、 $s_1$ 、 $s_2$ 、 $s_3$ 和 $s_4$ 之间直接相连且属于同一community，因此，这些顶点的embedding在特征空间中比较靠近；structural equivalence表面在图中具有相似结构特征的顶点（顶点间不必直接相连，可以离得很远)，其embeddings应该比较靠近，例如，顶点 $u$ 和 $s_6$ 都是各自所在community的中心，具有形似的结构特征，因此，顶点 $u$ 和 $s_6$ 的embedding在特征空间中比较靠近。Node2vec算法设计了一种灵活的邻域采样策略，允许在BFS和DFS之间平滑插值

2.3.1 特征学习框架

Node2vec算法希望，在给定顶点的条件下，其领域内的顶点出现的概率最大。即优化目标函数公式(13)：
$\max_f\sum_{u \in V}\log Pr(N_S(u)|f(u)) \tag{13}$
对于每一个源顶点 $u\in V$ ， $N_S(u)$ 为根据采样策略 $S$ 得到的邻域，为了简化目标函数，论文提出了2个假设:

条件独立性
特征空间对称性

假设1表示当源顶点 $u$ 的特征表示 $f(u)$ 给定时， $Pr(n_i|f(u))$ 和 $Pr(n_j|f(u))$ 无关（ $n_i\in N_S(u),n_j \in N_S(u),i\neq j$ ）。因此， $Pr(N_S(u)|f(u))$ 可写为公式(14)：
$Pr(N_S(u)|f(u))=\Pi_{n_i \in N_S(u)}Pr(n_i|f(u))\tag{14}$
假设2说明源顶点和其邻域内任一顶点，相互之间的影响是相同的。最自然的想法就是将 $Pr(n_i|f(u))$ 写为公式(15)：
$Pr(n_i|f(u))=\frac{exp(f(n_i)^\top f(u))}{\sum_{v \in V}exp(f(v)^\top f(u))}\tag{15}$
因此，Node2vec算法就需要解决两个问题：

给定一个源顶点 $u$ ，使用什么样的采样策略 $S$ 得到其邻域 $N_S(u)$ ；
如何优化目标函数。

对于第二个问题，可以参考基于negative sampling的skip-gram模型进行求解，关键是确定采样策略 $S$

2.3.2 邻域采样策略

Node2vec算法提出了有偏的随机游走，通过引入2个超参数 $p$ 和 $q$ 来平衡BFS和DFS，从顶点 $v$ 有做到顶点 $x$ 的转移概率为公式(16)：
$p(c_i=x|c_{i-1}=v) = \begin{cases} \frac{\pi_{vx}}{Z}, if \quad (v,x)\in E \\ 0, otherwise \end{cases}\tag{16}$

其中， $x$ 表示游走过程中的当前顶点， $t$ 和 $v$ 分别为 $x$ 前一时刻的顶点和下一时刻将要游走到的顶点， $\pi_{vx}=\alpha_{pq}(t,x)\cdot w_{vx}$ ， $w_{vx}$ 为边(v,x)的权值， $\alpha_{pq}(t,x)$ 定义如下:
$\alpha_{pq}(t,x)=\begin{cases}\frac{1}{p}, if \quad d_{tx}=0\\1,if \quad d_{tx}=1\\ \frac{1}{q},if \quad d_{tx}=2\end{cases}\tag{17}$
其中， $d_{tx}=0$ 表示顶点 $t$ 和 $x$ 相同， $d_{tx}=1$ 表示顶点 $t$ 和 $x$ 之间存在之间相连的边， $d_{tx}=0$ 表示顶点 $t$ 和 $x$ 不存在直接相连的边，如图所示，在一个无权图中（可以看作是所有边的权值为1），在一次游走过程中，刚从顶点 $t$ 游走到 $v$ ，在下一时刻，可以游走到4个不同的顶点， $t$ 、 $x_1$ 、 $x_2$ 和 $x_3$ ，转移概率分别为 $\frac{1}{p}$ 、 $1$ 、 $\frac{1}{q}$ 和 $\frac{1}{q}$

参数 $p$ 和控制游走探索和离开起始节点附近的速度 $u$ ， $p$ 越小，随机游走采样的顶点越可能靠近起始顶点；而 $q$ 越小，随机游走采样的顶点越可能远离起始顶点

2.4 SDNE

2.4.1 SDNE模型架构

SDNE模型(Structural Deep Network Embedding)的结构图如下：

模型主要包括两个部分：无监督和有监督部分

无监督部分是一个深度自编码器用来学习二阶相似度
监督部分是一个拉普拉斯特征映射捕获一阶相似度

2.4.2 二阶相似度(无监督)

如上图所示，这是一个自编码器，没有标签数据，是一种无监督学习

模型的输入 $x_i$ ，是节点 $i$ 的邻接矩阵，因此结构相似的顶点可以学习到相似的embedding向量，不断优化代价函数来捕捉全局结构特征，即二阶相似度

输出是 $\hat x_i$ ，是重构后的邻接矩阵。其目标是：
$f(x) \approx x\tag{18}$
所以，二阶相似度损失函数定义为:
$\mathcal{L}=\sum_{i=1}^n{||\hat{x_i}-x_i||^2_2}\tag{19}$
由于网络的稀疏性，邻接矩阵中的0元素远多于非0元素，使用邻接矩阵作为输入的话要处理很多0，这样就做了太多无用功了。为了解决这个问题，对损失函数做了改进如下：
$\mathcal{L_{2nd}}=\sum_{i=1}^n||(\hat{x_i}-x_i)\odot{b_i}||^2_2=||\hat{X}-X\odot{B}||^2_F\tag{20}$
其中 $\odot$ 是哈马达积，表示对应元素相乘。邻接矩阵中的0对应 $b=1$ , 非0元素的 $b>1$ ,这样的目的是对于有边连接的节点增加惩罚，可以理解为对有边连接的节点赋予更高权重

在模型中，从 $x_i$ 到 $y_i^{(K)}$ 是编码器，从 $y_i^{(K)}$ 到 $\hat x_i$ 是解码器， $y_i^{(K)}$ 是节点 $i$ 的Embedding向量，编码器的公式为：
$y_i^{(1)}=\sigma{(W^{(1)}x_i+b^{(1)})}\\ y_i^{(k)}=\sigma{(W^{(k)}y_i^{(k-1)}+b^{(k)})}, k=2,...,K\tag{21}$
其中， $\mathbf W^{(k)}$ 为第 $k$ 层的参数矩阵， $b^k$ 为第 $k$ 层的偏置项

2.4.3 一阶相似度(有监督)

前导知识——拉普拉斯映射(Laplacian Eigenmap)，其目的是降维，目标函数如下：
$\sum_{i,j}\mathbf W_{ij}||y_i - y_j||^2\tag{22}$
$y_i^{(K)}$ 是节点 $i$ 的Embedding向量，若顶点 $v_i$ 和 $v_j$ 之间存在边，那他们的Embedding的结果 $y^{(K)}$ 应该也很接近，所以，借助拉普拉斯的思想，其一阶相似度为：
$\mathcal{L_{1st}}=\sum_{i,j=1}^n{s_{i,j}||y_i^{(K)}-y_j^{(K)}||^2_2}=\sum_{i.j=1}^n{s_{i,j}||y_i-y_j||^2_2}\tag{23}$
最小化 $\mathcal{L_{1st}}$ ，可以使得一条边的两个节点在嵌入空间中的表示相对接近，为了防止过拟合，加入正则化，SDNE的loss为：
$\mathcal{L_{mix}}=\mathcal{L_{2nd}+\alpha{\mathcal{L_{1st}}}}+\nu{\mathcal{L_{reg}}} =||(\hat{X}-X)\odot{B}||^2_F+\alpha{\sum_{i.j=1}^n{s_{i,j}||y_i-y_j||^2_2}}+\nu{\mathcal{L_{reg}}}\tag{24}$
其中，正则化 $\mathcal{L_{reg}}$ 的计算公式如下：
$mathcal{L_{reg}}=\frac{1}{2}\sum_{k=1}^k({||W^{(k)}||^2_F+||\hat{W}^{k}||_F^2})\tag{25}$
$\alpha$ 为控制1阶损失的参数， $\nu$ 为控制正则化项的参数

2.5 Graph2vec

Graph2Vec原理上和DeepWalk差不多，也是尝试借用word2vec来训练，只是这次为了嵌入整张图，所以尝试利用子图来训练。类似文档嵌入doc2vec，通过最大化作为输入的文档，来预测随机单词的可能性，Graph2vec预测图中子图的概率

采样子图。为了提高效率，采样只选当前节点周围的邻接节点，构成子图 $sg$
skip-gram，最大化输入图子图的概率 $J(\Phi)=-log P(sg_n^{(d)}|\Phi(G))$ ， $d$ 为度， $sg$ 为子图

2.5.1 算法详解

算法由两个主要组件组成：

对给定图中每个节点周围生成根子图
学习给定图嵌入

第 $e$ 轮次学习数据集 $G$ 中所有图的 $δ$ 维嵌入
首先随机初始化数据集中所有图的嵌入
随后继续提取每个图中的每个节点周围的根子图
并迭代地学习(即细化)相应图在一些轮次的嵌入

提取根子图：

输入根节点 $n$ ，原图 $G$ ，以及预期子图的度 $d$ ，输出预期子图 $sg_n^{(d)}$ ，递归出口 $d=0$ ，不要子图，只输出节点 $n$ 的标签 $λ$
对于 $d>0$ ，根据宽度优先得到 $n$ 的邻居，对每个邻居再得到其对应的 $d-1$ 子图，记录进 $M_n^{(d)}$ 得到 $n$ 的 $d-1$ 子图后与排序后的 $M_n^{(d)}$ 拼接得到最终结果

负采样Skip-gram：

考虑词库SGvocab巨大，通过负采样计算 $P r(sg^{(d)}_n |Φ(G))$ 这个后验概率
在每个训练周期，给定一个图 $Gi∈G$ 与其上下文的一组根子图， $c(Gi)=c={sg_1，sg_2，…}$ ，选择一组固定数量的随机选择的子图作为负样本 $c’={sgn_1，sgn_2，…sgn_k}$ 这样保证 $c’$ 是词库的子集，保证 $k<<|SGvocab|$ 和 $c∩c’=\{\}$
负样本是一组k个子图，每个子图都不存在于需要学习嵌入的图 $Gi$ 中，而是存在于子图的词库中，负样本的数量k是一个可以通过经验进行调整的超参数
为了有效的训练，对于每个图 $Gi∈G$ ，首先训练目标—上下文对 $(Gi，c)$ ，并更新相应的子图的嵌入。随后，我们只更新负样本 $c’$ 的嵌入，而不是整个词库