今天我们来探讨图嵌入，我们要用一个指定维度的向量来表示我们的图节点，并且想要保持它作为图中一份子的特征，也就是，相邻的节点的节点嵌入也应该相似。

接下来我们来详细分析。

图的传统机器学习方法

给定一个输入图，提取节点、连接和图层面的特征，然后训练一个模型，比如支持向量机、神经网络等，来将图特征映射到标签。
而我们用到的这些图的特征通常都是人工提取设计的，方法可以参考我们的上一节。

革新-图表示学习

如图所示，我们的图表示学习可以正是消除每次都需要进行特征工程需求的方法。

图表示学习的核心目标

简单来说，图表示学习的核心目标就是实现高效的、与任务无关的特征学习。

把图节点嵌入到向量空间中，再利用我们熟悉的向量数据处理方法处理数据。

为什么要进行图嵌入(Node Embedding)

我们做的所有处理都是为了方便的机器学习，正由于图结构的特殊性，我们在寻找一个方便的途径可以把图进行表示，而图嵌入正是实现这个途径的方法。

我们希望用节点间嵌入的相似性来表示它们在网络中的相似程度。

例如：

• 两个节点是邻居（通过一条边连接）
• 编码网络信息
• 用于多种下游预测任务：
  • 节点分类
  • 边预测
  • 图分类
  • 异常节点检测
  • 聚类
  • And so on…
    

图嵌入实例

上图实现了对Zachary空手道俱乐部网络的2D节点嵌入。

编码器(Encoder)-解码器(Decoder)框架

接下来我们会探讨图嵌入的具体实现方法。
我们先来说说编码器-解码器框架。

假设我们有一个无向图G，V是节点集合，矩阵A是邻接矩阵。

我们的目标是对节点进行编码，使得嵌入空间中的相似度（例如点积）能够近似表示图中节点之间的相似性。

图示说明：
左侧：原始网络
展示了节点u,v及其在网络中的连接关系
右侧：嵌入空间
通过编码函数ENC将节点映射为向量zu,zv
映射过程：
ENC(u)将节点u映射到嵌入空间
ENC(v)将节点v映射到嵌入空间

节点嵌入的学习总过程

我们来总结一下节点嵌入的过程。

1. 编码器将节点映射为嵌入向量
2. 定义节点相似度函数(即在原始网络中衡量节点相似度的方法，如共同邻居、Jaccard相似性、余弦相似性等)
3. 解码器DEC将嵌入向量的相似度映射为相似性得分
4. 优化编码器参数，使得原始网络中的相似度similarity(u,v)近似于嵌入空间中的相似度（参见下图，这里是用点积来衡量相似度）。

两个关键组件

Encoder

Encoder作为编码器的功能是将每个图节点映射为d维向量。

Similarity Function

相似度函数定义向量空间与原始网络的关系映射。

浅层编码(Shallow Embedding)

最简单的编码方法：编码器就是一个嵌入查找表

数学表达如下：

在浅层编码器里，编码器就只是一个嵌入查找表。
如果你好奇嵌入矩阵的结构的话，我们可以看下图：

嵌入矩阵Z包含以下关键特征：

矩阵维度

• 矩阵的行数对应嵌入向量的维度(d维)
• 矩阵的列数等于图中节点的总数(|V|)

矩阵结构

• 每一列向量zi代表节点i的d维嵌入表示
• 所有列向量共同构成完整的节点嵌入空间

浅层编码的关键特点是，每个节点都有唯一的嵌入向量，我们可以直接优化每个节点的嵌入表示，不需要复杂的编码转换过程。
而浅层编码的实现方法也很多，如:

• DeepWalk
• Node2Vec
• GraphSAGE
• And so on…

框架总结

下面是编码器-解码器框架的主要组成：
编码器

• 采用浅层编码器：简单的嵌入查找
• 优化参数：矩阵Z，包含所有节点u∈V的嵌入向量Z_u
• 深度编码器我们将在GNN探讨

解码器

• 基于相似度函数计算节点相似度进行解码
• 优化目标：对于对于相似的节点对(u,v)，最大化它们的嵌入向量点积

这个框架通过编码器将节点映射到向量空间，然后通过解码器和优化目标来保证相似节点在嵌入空间中的距离更近。

而我们定义节点相似度的可能标准，有：

• 是否直接连接？
• 是否有共同邻居？
• 两个节点在网络中是否扮演相似的结构角色？

接下来我们会学习基于随机游走的节点相似度等于，学习如何针对这种相似度度量来优化这种节点嵌入。

节点嵌入注意事项

学习方式：无监督/自监督

• 不使用节点标签
• 不使用节点特征
• 目标：直接估计节点坐标（嵌入），以保证网络结构特征
• 网络结构通过解码器(DEC)来捕获

嵌入特点：与任务无关的特征学习

• 不为特点任务而训练
• 可以应用于任何下游任务
• 具有通用性

这种方法的优势很明显，我们不需要标注数据，只依赖于网络结构，学到的嵌入具有通用性。

随机游走的方法

符号说明

向量 z_u：

• 节点 u 的嵌入向量（我们的目标是找到它）。

概率 P(v|z_u)：➡️ 基于 z_u 的模型预测

• 从节点 u 开始的随机游走访问节点 v 的（预测）概率。

用于生成预测概率的非线性函数

Softmax 函数：

• 将 K 个实数值（模型预测）转换为和为 1 的 K 个概率：
  

Sigmoid 函数：

• S形函数，将实数值转换到(0, 1)范围内。表达式为:
  

随机游走的过程

随机游走的概念是什么？

基本概念
给定一个图和初始点，通过随机选择邻居节点进行移动，不断重复这个随机选择和移动的过程，就是随机游走。

而上图的随机游走过程如下：

• 从起始节点开始
• 第1步：移动到结点5
• 第2步：移动到结点8
• 第3步：移动到结点9
• 第4步：返回结点8
• 第5步：移动到结点11

我们可以发现随机游走的关键特点是，每一步选择都是随机的，只能移动到当前节点的邻居节点，并且形成的访问序列构成了图上的随机游走路径。

另外，节点嵌入向量的点积可以近似于节点在随机游走中的共线概率。
所以我们可以利用这个特性来学习节点嵌入。具体来说：

1. 首先，我们通过随机游走收集节点共现信息：

   • 在图上进行多次随机游走
   • 记录在游走序列中共同出现的节点对

2. 然后，优化节点嵌入使得：

   • 经常在随机游走中共现的节点对，其嵌入向量的点积较大
   • 很少或从不在随机游走中共现的节点对，其嵌入向量的点积较小

这样的优化目标确保了：

• 网络中结构相近的节点会被映射到相似的嵌入向量
• 通过随机游走捕获的局部网络结构可以被保存在嵌入空间中

随机游走嵌入的两个主要步骤

估计随机游走概率

• 从起始节点u开始
• 采用特定的随机游走策略R
• 计算到达目标节点的概率Pr(v|u)

优化嵌入向量
我们的目标是将随机游走产生的统计学习编码到嵌入中。

• 使用向量点积(cos(θ))表示相似度
• 向量间的角度θ与随机游走概率成比例
• 确保嵌入空间的相似度反映随机游走的相似度