图嵌入模型

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会将其邻居的嵌入向量进行聚合，然后将聚合结果与该节点的嵌入向量进行拼接，从而得到该节点的嵌入向量。这个聚合过程可以用如下的公式来表示：

$h_{\mathcal{N}(v)}^{(l)} = \text{AGGREGATE}^{(l)}\left(\{h_u^{(l-1)} : u \in \mathcal{N}(v) \}\right)$

其中， $h_{\mathcal{N}(v)}^{(l)}$ 表示节点 $v$ 的邻居节点在第 $l$ 层的嵌入向量， $\text{AGGREGATE}^{(l)}$ 表示第 $l$ 层的聚合函数， $h_u^{(l-1)}$ 表示节点 $u$ 在第 $l-1$ 层的嵌入向量， $\mathcal{N}(v)$ 表示节点 $v$ 的邻居节点集合。

GraphSage可以使用不同的聚合函数来聚合节点的邻居信息，例如平均池化、最大池化和LSTM等。此外，GraphSage还可以使用多层神经网络来学习更复杂的嵌入表示。

训练方法

在训练过程中，GraphSage使用随机梯度下降（SGD）来优化嵌入向量。具体来说，它使用节点的嵌入向量和标签信息来计算损失函数，然后使用反向传播算法来更新嵌入向量。损失函数可以用如下的公式来表示：

$\mathcal{L} = \sum_{v \in \mathcal{V}} \text{loss}\left(f\left(h_v^{(L)}, \frac{1}{|\mathcal{N}(v)|}\sum_{u \in \mathcal{N}(v)}h_u^{(L)}\right), y_v\right)$

其中， $h_v^{(L)}$ 表示节点 $v$ 在最后一层的嵌入向量， $f$ 表示分类器函数，例如softmax函数， $\mathcal{N}(v)$ 表示节点 $v$ 的邻居节点集合， $|\mathcal{N}(v)|$ 表示节点 $v$ 的邻居节点数， $y_v$ 表示节点 $v$ 的标签信息， $\text{loss}$ 表示损失函数，例如交叉熵损失函数。

通过最小化所有节点的损失函数，GraphSage可以学习到图中所有节点的嵌入向量。

训练过程
初始化模型参数，例如嵌入向量的维度、每层的神经元数、聚合函数等。
对于每个训练样本，使用GraphSage模型计算出节点的嵌入向量。（采样邻居节点->聚合邻居节点嵌入->更新目标节点嵌入）
使用节点的嵌入向量和标签信息计算损失函数，并使用反向传播算法更新模型参数。
重复步骤2-3，直到达到预定的训练轮数或损失函数收敛。
对于测试样本，使用训练好的GraphSage模型计算出节点的嵌入向量，并使用分类器函数预测标签。

GAT

GAT（Graph Attention Network）是一种用于图形分类的神经网络模型。与传统的图形分类模型不同，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}$ 将其映射到一个新的维度，最后通过一个注意力机制计算它们之间的相似性。