图嵌入模型

作者: 不可能打工 | 来源:发表于2023-03-22 15:39 被阅读0次

DeepWalk

DeepWalk是一种用于学习节点嵌入的算法，它可以将节点表示为低维向量，并在这些向量之间保留节点之间的相似性关系。DeepWalk算法基于随机游走，通过在图中进行随机游走来捕捉节点之间的相似性关系。DeepWalk算法的核心思想是利用节点的邻居信息来定义节点的上下文，然后通过学习这些上下文来得到节点的嵌入表示。

DeepWalk模型的数学公式如下：

首先，我们假设有一个无向图G=(V, E)，其中V表示节点集合，E表示边集合。我们使用 $P_{u,v}$ 表示从节点u到节点v的转移概率。DeepWalk算法中的关键是如何定义转移概率 $P_{u,v}$ ，以便更好地捕捉节点之间的相似性关系。

DeepWalk算法中，转移概率 $P_{u,v}$ 定义如下：

$P_{u,v}=\frac{1}{Z_{u}}\times w_{u,v}$

其中， $w_{u,v}$ 是边权重， $Z_u$ 是归一化因子。 $w_{u,v}$ 可以根据边的出现次数来计算，例如：

$w_{u,v}=\frac{1}{\text{count}(u,v)}$

然后，我们使用随机游走来生成节点的上下文。具体来说，我们从图中的每个节点开始，根据转移概率 $P_{u,v}$ 进行随机游走，生成一些节点序列。这些节点序列可以看作是节点的上下文，用于学习节点的嵌入表示。

最后，我们使用skip-gram模型来学习节点的嵌入表示。具体来说，我们将节点序列作为输入，将每个节点表示为一个低维向量，然后通过最大化相邻节点的余弦相似度来训练模型。

总的来说，DeepWalk算法是一种基于随机游走的节点嵌入算法，它可以学习节点之间的相似性关系，并将节点表示为低维向量。这个算法可以应用于很多领域，例如社交网络分析、生物信息学等。

Node2Vec

node2vec是一种用于学习节点嵌入的算法，它可以将节点表示为低维向量，并在这些向量之间保留节点之间的相似性关系。node2vec算法基于随机游走，通过在图中进行随机游走来捕捉节点之间的相似性关系。node2vec算法的核心思想是利用节点的邻居信息来定义节点的上下文，然后通过学习这些上下文来得到节点的嵌入表示。

node2vec模型的数学公式如下：

首先，我们假设有一个无向图G=(V, E)，其中V表示节点集合，E表示边集合。我们使用 $P_{u,v}$ 表示从节点u到节点v的转移概率。node2vec算法中的关键是如何定义转移概率 $P_{u,v}$ ，以便更好地捕捉节点之间的相似性关系。

node2vec算法中，转移概率 $P_{u,v}$ 定义如下：

$P_{u,v}=\frac{1}{Z_{u}}\times \begin{cases} \frac{1}{p}, & \text{if } d_{u,v}=1 \\ 1, & \text{if } d_{u,v}=2 \\ \frac{1}{q}, & \text{if } d_{u,v}=0 \end{cases}$

其中， $d_{u,v}$ 表示节点u和节点v之间的距离， $p$ 和 $q$ 是两个超参数， $Z_u$ 是归一化因子。当 $d_{u,v}=1$ 时，表示节点v是节点u的一阶邻居；当 $d_{u,v}=2$ 时，表示节点v是节点u的二阶邻居；当 $d_{u,v}=0$ 时，表示节点v等于节点u。这个转移概率的定义可以让我们在随机游走时更好地探索节点之间的相似性关系。

总的来说，node2vec算法是一种基于随机游走的节点嵌入算法，它可以学习节点之间的相似性关系，并将节点表示为低维向量。这个算法可以应用于很多领域，例如社交网络分析、生物信息学等。

LINE

图嵌入模型LINE是一种基于矩阵分解的图嵌入算法，旨在将图中的每个节点映射到低维向量空间中，从而捕捉节点之间的相似性和关系。它基于两个假设：1）同类节点在向量空间中应该更加接近，不同类节点在向量空间中应该更加远离；2）同类节点与其邻居节点的相似度应该更高。
LINE模型中，每个节点都被映射成两个向量，一个是表示节点的上下文信息，另一个是表示节点的目标信息。上下文信息表示节点周围的邻居节点，而目标信息表示节点自身。模型的目标是最小化每个节点上下文信息向量和目标信息向量之间的距离和。
LINE模型使用了两种不同的损失函数，分别用于建模节点与节点之间的一阶关系和二阶关系。一阶关系即节点与其邻居节点之间的关系，二阶关系则是节点与邻居节点的邻居节点之间的关系。每个节点的向量表示通过最小化这两种损失函数而得到。
具体来说，模型的优化目标是最小化以下两个损失函数之和：
1）一阶损失函数：
$L_{1st}=-sum_{(u,v)in E}logsigma(u^Tv)+sum_{uin V}d_u(-sum_{vin V}logsigma(-u^Tv))$
其中，E表示图中的边集， $sigma(x)$ 表示sigmoid函数， $u$ 和 $v$ 表示图中的节点， $d_u$ 表示节点 $u$ 的度数。
2）二阶损失函数：
$L_{2nd}=-sum_{uin V}sum_{vin N(u)}logsigma(u^Tv)+sum_{uin V}sum_{tin N(v)}logsigma(-u^Tv)$
其中， $N(u)$ 表示节点 $u$ 的邻居节点集合， $N(v)$ 表示节点 $v$ 的邻居节点集合。
模型的优化采用随机梯度下降算法，每次迭代从图中随机选择一个节点对，计算其一阶和二阶损失函数的梯度，更新节点向量表示。迭代次数越多，模型的表现越好。
总之，LINE模型是一种基于矩阵分解的图嵌入算法，通过最小化一阶和二阶损失函数来学习节点向量表示，从而捕捉节点之间的相似性和关系。

GCN

GCN（Graph Convolutional Network）模型是一种基于图结构的神经网络模型，主要用于图数据的建模和预测。它是在卷积神经网络（CNN）和递归神经网络（RNN）的基础上发展而来，具有卷积神经网络的特点，可以处理图数据中的局部信息，同时也具有递归神经网络的特点，可以考虑图数据中的全局信息。
GCN模型的基本思想是将图数据转化为矩阵形式，然后通过卷积操作对矩阵进行相应的处理，最后将处理后的矩阵作为输入，进行分类、预测等任务。在GCN模型中，卷积操作是在图结构上进行的，通过邻居节点之间的信息传递，实现对节点特征的更新和预测。
下面是GCN模型的数学公式：

首先，假设我们有一个图G=(V, E)，其中V表示节点集合，E表示边集合。每个节点i都有一个特征向量 $h_i$ ，表示节点i的特征。邻接矩阵A表示节点之间的连接关系，其中 $A_{ij}$ 表示节点i和节点j之间是否有边连接。

然后，我们定义一个卷积操作 $*$ ，用于将邻接矩阵A和节点特征向量 $h$ 进行卷积，得到新的特征表示 $H_{new}$ 。具体的卷积操作如下：

$H_{new}=\sigma(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H W)$

其中， $\tilde{A}=A+I$ 表示邻接矩阵A加上自环， $\tilde{D}$ 表示度矩阵， $I$ 表示单位矩阵， $\sigma$ 表示激活函数， $W$ 表示权重矩阵。

这个卷积操作可以分解成两个部分。首先，我们将节点特征向量 $h$ 与权重矩阵 $W$ 相乘，得到一个中间表示 $X=W H$ 。然后，我们将中间表示 $X$ 与邻接矩阵 $\tilde{A}$ 相乘，得到新的特征表示 $H_{new}$ 。这个过程中，我们还使用了度矩阵 $\tilde{D}$ 来对邻接矩阵进行归一化，以便更好地捕捉节点之间的关系。

最后，我们再使用激活函数 $\sigma$ 来对新的特征表示 $H_{new}$ 进行非线性变换，得到最终的特征表示。

GCN模型的训练过程通常使用反向传播算法进行优化，从而使得预测结果与实际标签之间的误差最小化。在训练过程中，我们通常会使用dropout等正则化技术来防止过拟合。

总的来说，GCN模型是一种基于卷积操作的神经网络模型，可以用于图数据的建模和预测。它的核心思想是利用邻接矩阵来描述节点之间的连接关系，通过信息传递来更新每个节点的特征向量，最终实现对节点特征的预测。GCN模型在社交网络、推荐系统、生物信息学等领域具有广泛的应用前景。
GCN模型是基于图卷积的深度学习模型，它可以用于节点分类、图分类等任务。在GCN模型中，每个节点都有一个特征向量表示，而节点之间的连接关系可以用邻接矩阵来表示。GCN模型的核心思想是利用邻接矩阵来对节点的特征进行卷积操作，从而得到新的特征表示。

GraphSage

GraphSage是一种用于节点嵌入的图神经网络模型，旨在解决图上节点分类、节点聚类等问题。
GraphSage的核心思想是利用节点的本地邻域信息来生成节点的表示。具体来说，GraphSage通过迭代地聚合节点的邻居特征来生成节点的嵌入，这些邻居特征可以是节点本身的特征，也可以是邻居节点的特征。
GraphSage的聚合过程可以分为两个阶段：采样邻居节点和聚合邻居特征。在采样邻居节点阶段，GraphSage通过随机游走或者固定大小的邻居采样策略来获取每个节点的邻居节点。在聚合邻居特征阶段，GraphSage使用一个多层感知器（MLP）来聚合邻居节点的特征，并将聚合后的特征作为输入，再次进行采样和聚合，直到达到预定的深度。
具体来说，GraphSage模型可以表示为以下公式：
$h_v^{(k)} = sigma(W^{(k)} cdot AGG({h_u^{(k-1)} | u in N(v)}))$
其中， $h_v^{(k)}$ 表示第 $k$ 层节点 $v$ 的表示， $AGG$ 表示聚合函数， $sigma$ 表示非线性激活函数， $W^{(k)}$ 表示第 $k$ 层的权重矩阵， $N(v)$ 表示节点 $v$ 的邻居节点集合， $h_u^{(k-1)}$ 表示第 $k-1$ 层节点 $u$ 的表示。在第 $0$ 层， $h_v^{(0)}$ 为节点 $v$ 的原始特征。
GraphSage的优点在于它能够有效地利用节点的本地邻域信息来生成节点的表示，同时具有较强的可扩展性和泛化性能。另外，GraphSage还可以通过在聚合函数中增加注意力机制等方法来进一步提高模型的性能。

GraphSAGE是一种用于图嵌入学习的模型，它可以对整个图进行端到端的学习。GraphSAGE的训练过程可以分为以下几个步骤：

初始化节点嵌入向量
在训练开始之前，需要对每个节点进行初始化，通常是使用随机向量进行初始化。
采样邻居节点
对于每个节点，从它的邻居节点中随机采样一定数量的节点作为邻居，并将它们作为输入传递给神经网络。
聚合邻居节点的信息
对于每个节点，将其邻居节点的嵌入向量进行聚合操作，通常是将它们进行加权平均。这个聚合操作可以在每个节点的邻居节点上进行并行计算。
更新节点嵌入向量
使用聚合得到的邻居节点的信息来更新每个节点的嵌入向量。更新的方式通常是将邻居节点的信息与当前节点的嵌入向量拼接起来，然后通过神经网络进行一次前向传播得到一个新的嵌入向量。
计算损失函数
使用更新后的嵌入向量来计算节点分类的损失函数，通常是使用交叉熵损失函数。
反向传播更新参数
使用反向传播算法来更新神经网络的参数，以最小化损失函数。
重复以上步骤
重复以上步骤直到模型收敛，或者达到预设的训练轮数。在每一轮训练中，可以随机采样不同的邻居节点来增加模型的泛化性能。

GAT

GAT（Graph Attention Network）是一种用于图形分类的神经网络模型。与传统的图形分类模型不同，GAT使用注意力机制来学习每个节点与其邻居节点之间的关系。这使得模型能够更好地捕捉节点之间的复杂关系。
GAT的核心思想是使用注意力机制来计算每个节点与其邻居节点之间的权重。这些权重可以表示节点之间的重要性，从而帮助模型更好地理解图形。

GAT模型的数学公式如下：

首先，我们假设有一个无向图G=(V, E)，其中V表示节点集合，E表示边集合。我们使用 $A$ 表示图的邻接矩阵，其中 $A_{i,j}$ 表示节点i和节点j之间是否存在边。我们还使用 $H^{(l)}$ 表示第l层节点的嵌入表示，其中 $H^{(0)}$ 表示初始节点嵌入表示。

然后，我们使用注意力机制来计算节点之间的相似性。具体来说，我们定义注意力系数 $e_{i,j}$ 如下：

$e_{i,j}=\text{LeakyReLU}\left(\vec{a}^{T}\cdot[\vec{W}h_i||\vec{W}h_j]\right)$

其中， $\vec{W}$ 和 $\vec{a}$ 是可学习的参数矩阵， $||$ 表示向量的拼接操作，LeakyReLU是一个激活函数。这个公式的意思是，我们将节点i和节点j的嵌入表示拼接起来，然后通过一个可学习的参数矩阵 $\vec{W}$ 将其映射到一个新的维度，最后通过一个注意力机制计算它们之间的相似性。