一文详解图表示学习

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

一文详解图表示学习
一文详解 NSObject 对象的内存布局
Logstash 篇之插件详解
消息轨迹全景图详解-独门秘籍
自定义View的各个重要的类和属性
Java 虚拟机系列一：一文搞懂 JVM 架构和运行时数据区
Java 虚拟机系列二：垃圾收集机制详解，动图帮你理解
2020-01-21【并发编程】一文详解Java中的各种锁
2019-05-21
轮播图详解

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’$ 的嵌入，而不是整个词库

一文详解图表示学习
Graph Embedding与Word Embedding一样，目的是用低维、稠密、实值的向量表示网络中的节点。...
一文详解 NSObject 对象的内存布局
一文详解 NSObject 对象的内存布局一文详解 NSObject 对象的内存布局
Logstash 篇之插件详解
input插件详解及glob讲解 codec插件详解默认是false，表示匹配规则，设置为true反而表示不匹配...
消息轨迹全景图详解-独门秘籍
简介：消息轨迹全景图详解-独门秘籍消息轨迹全景图详解-独门秘籍消息轨迹全景图详解-独门秘籍阿里云 IoT ...
自定义View的各个重要的类和属性
1 、Path类详解 2、Paint详解 3、Canvas详解 4 、绘制雷达图
Java 虚拟机系列一：一文搞懂 JVM 架构和运行时数据区
Java 虚拟机系列一：一文搞懂 JVM 架构和运行时数据区 Java 虚拟机系列二：垃圾收集机制详解，动图帮你理...
Java 虚拟机系列二：垃圾收集机制详解，动图帮你理解
Java 虚拟机系列一：一文搞懂 JVM 架构和运行时数据区 Java 虚拟机系列二：垃圾收集机制详解，动图帮你理...
2020-01-21【并发编程】一文详解Java中的各种锁
转载自：【并发编程】一文详解Java中的各种锁
2019-05-21
超分:深度学习超分辨率最新综述：一文道尽技术分类与效果评测详解爱奇艺ZoomAI视频增强技术的应用使用深度学习的单...
轮播图详解
轮播图详解

一文详解图表示学习

一. 图表示学习意义

二. 图表示学习常用方法

2.1 DeepWalk

2.1.1 随机游走（random walk）

2.1.2 word2vec(skip-gram)

2.2 Line

2.2.1 相关定义

2.2.2 LINE with First-order Proximity

2.2.3 LINE with Second-order Proximity

2.2.4 Optimization via Edge Sampling

2.3 Node2vec

2.3.1 特征学习框架

2.3.2 邻域采样策略

2.4 SDNE

2.4.1 SDNE模型架构

2.4.2 二阶相似度(无监督)

2.4.3 一阶相似度(有监督)

2.5 Graph2vec

2.5.1 算法详解

相关文章

一文详解图表示学习

一文详解 NSObject 对象的内存布局

Logstash 篇之插件详解

消息轨迹全景图详解-独门秘籍

自定义View的各个重要的类和属性

Java 虚拟机系列一：一文搞懂 JVM 架构和运行时数据区

Java 虚拟机系列二：垃圾收集机制详解，动图帮你理解

2020-01-21【并发编程】一文详解Java中的各种锁

2019-05-21

轮播图详解

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

自然语言处理

知识图谱