图机器学习（4）——图机器学习与嵌入算法

0. 前言

机器学习是人工智能的一个重要分支，它致力于让系统能够从数据中自主学习并持续优化。这项技术在诸多应用领域取得了显著成果，特别是在那些难以通过明确定义规则来解决具体任务的场景中表现尤为突出。例如，我们可以训练算法执行垃圾邮件识别、多语言文本翻译和图像目标识别等任务。
近年来，将机器学习应用于图数据的研究日益受到关注。相较于传统机器学习方法，图机器学习的主要优势在于能够自动学习更优的数据表征、提升预测准确度、发现潜在模式，以及更深入地理解复杂动态关系。本节首先回顾机器学习基本概念。然后重点介绍图机器学习 (Graph Machine Learning) 中的表示学习，最后通过实践案例理解这些理论概念。

1. 图机器学习

作为人工智能 (Artificial Intelligence, AI) 的重要分支，机器学习 (Machine Learning, ML) 近年来备受关注。这类计算机算法能够通过经验自主学习和提升能力，而无需显式编程。这种方法的灵感来源于自然界的学习过程——就像运动员学习新动作时，会通过模仿教练、不断试错来逐步掌握技能。
机器学习的本质是一个优化问题。目标是寻找在特定任务上表现最优的数学模型。性能可以通过特定的性能指标(或损失函数)来衡量。在常见的学习任务中，算法利用大量数据迭代做出预测，在每次迭代中，根据损失函数进行评估，由此产生的误差用来更新模型参数，逐步提升性能，这一过程通常称为训练。
更正式地讲，考虑一个特定的任务 T 和一个性能指标 P，P 能够量化算法在任务 T 上的表现。根据 Mitchell 的定义，当算法在任务 T 上的性能指标 P 随着经验 E 提升时，即称为学习。

1.1 机器学习基本原理

机器学习算法主要分为三类：监督学习、无监督学习和半监督学习。这些学习范式取决于数据的提供方式和评估方法。
监督学习 (supervised learning) 是在我们知道问题答案的情况下使用的学习范式。在这种情况下，数据集由样本对 $<x,y>$ 组成，其中 $x$ 是输入(例如图像或语音信号)，$y$ 是相应的期望输出(例如，图像类别或语音文本)。输入变量也称为特征，而输出通常被称为标签、目标。在监督学习中，性能通常通过距离函数来评估。这个函数衡量预测和期望输出之间的差异。根据标签的类型，监督学习可以进一步分为以下几类：

• 分类：标签是离散的，表示输入属于哪个“类别”，如图像识别、垃圾邮件检测
• 回归：目标是连续的，例如温度预测、商品价格预测

无监督学习与监督学习的不同之处在于问题的答案是未知的。在这种情况下，没有标签，数据集只有输入 $<x>$ ，核心目标是发现数据内在结构和模式，如聚类分析、高维数据降维。
在半监督学习中，算法使用有标签和无标签数据的组合进行训练。通常，为了引导发现无标签输入数据中存在的结构，会使用少量的有标签数据。
这里还需要特别介绍强化学习 (Reinforcement Learning)。这种学习方式通过"奖惩机制"来训练模型做出一系列决策：人工智能算法会面临游戏般的场景，根据采取的行动获得惩罚或奖励，其核心目标是通过学习找到最大化奖励、最小化惩罚的最优策略。
在机器学习中，仅仅最小化训练数据的误差是远远不够的。真正的关键在于"学习"能力——算法必须对未见过的数据保持同样的性能水平。评估算法泛化能力的常规做法是将数据集划分为两部分：训练集和测试集。模型在训练集上训练，计算损失函数并用于更新参数。训练后，模型在测试集上进行评估。此外，数据充足时，测试集可以进一步分为验证集和测试集，验证集通常用于评估模型在训练过程中的表现。
训练机器学习算法时，可能会出现以下三种典型情况：

• 欠拟合 (Underfitting)：模型在训练集上的表现较差，意味着模型没有足够的能力来处理任务。
• 过拟合 (Overfitting)：模型在训练集上的表现很好，但在测试数据上表现欠佳，在这种情况下，模型仅仅记住了训练数据，而没有真正理解它们之间的关系
• 理想状态：模型能够在训练和测试数据上都达到最优的性能水平。

过拟合和欠拟合可以通过下图中的风险曲线理解，从图中可以看到，随着模型复杂性的变化(即拟合的参数数量)，训练集和测试集上的性能变化情况：

过拟合问题是机器学习实践中的主要挑战之一，其产生原因主要包括：

• 数据层面：数据集定义不当或样本代表性不足。在这种情况下，增加更多的数据有助于减轻问题
• 模型层面：模型复杂度超出任务需求。在这种情况下，可以在损失函数中添加正则化项以约束模型复杂度

机器学习已在许多领域取得显著成果，成为计算机视觉、模式识别、自然语言处理等领域中最广泛应用和有效的方法之一。

1.2 图机器学习的独特优势

传统机器学习算法包括：回归算法(线性/逻辑回归)、基于实例的算法( K 近邻/支持向量机)、决策树算法、贝叶斯算法(朴素贝叶斯)、聚类算法( K 均值)和人工神经网络等。
本质上，这些算法成功的核心是，机器学习可以自动处理那些人类容易完成，但传统计算机算法难以描述的任务，并且在某些情况下，它们已经展示了比人类更好的能力。这在处理图数据时尤为突出，与图像或音频信号相比，图结构更加复杂。通过使用图机器学习，可以创建算法来自动检测和解释重复出现的潜在模式。
因此，图结构数据的表示学习已引发广泛关注，典型应用包括：生物交互图中蛋白质功能判定、合作网络演化预测和社交网络用户产品推荐等。
由于图结构的特性，图可以在不同的粒度级别上进行分析：节点级、边级和图级(整个图)，如下所示。每个层级对应不同的问题类型，需采用特定算法解决：

以下是不同粒度层面的图机器学习问题示例及解决方案：

• 节点级别：给定图 $G=(V,E)$，将每个顶点 $v\in V$ 分类到正确的类别。在这种设置下，数据集包括图 $G$ 和节点-标签对 $<v_i,y_i>$ 集合，其中 $v_i$ 是图 $G$ 的一个节点，$y_i$ 是该节点所属的类别。典型任务包括社交网络用户分类、蛋白质功能预测等
• 边级别：给定图 $G=(V,E)$，将每条边 $e\in E$ 分类到正确的类别。在这种设置下，数据集包括图 $G$ 和边-标签对 $<e_i,y_i>$ 集合，其中 $e_i$ 是图 $G$ 的一条边，$y_i$ 是该边所属的类别。典型任务为链接预测，即预测图中两个现有节点之间是否存在链接
• 图级别：给定一个包含 $m$ 个不同图的数据集，将每个图分类到正确类别。在这种设置下，数据集包括图-标签对 $<G_i,y_i>$ 集合，其中 $G_i$ 是一个图，$y_i$ 是该图所属的类别。典型应用包括分子属性预测、社交网络类型识别等

本节我们系统阐述了机器学习的基础概念，并着重介绍了图数据处理中常见的机器学习问题类型。基于这些理论基础，接下来将深入探讨图机器学习中更为复杂的核心概念。

2. 广义图嵌入问题

在传统机器学习应用中，处理输入数据的常见方法是通过特征工程从一组特征中构建出一个紧凑且有意义的表示，为数据集中每个实例提供一个合适的表示。
经过特征工程处理后的数据集将作为机器学习算法的输入。虽然这种方法在多数情况下表现良好，但在处理图数据时可能并非最优解。由于图数据具有明确的结构特性，要找到能够整合所有有用信息的合适表示并非易事。
创建能够表示图结构信息的特征的最直接的方法是提取某些统计数据。例如，可以通过图的度分布、效率来表示图。更复杂的过程包括应用特定的核函数或设计专用特征以整合所需特性。然而，这些方法通常耗时且可能无法完整保留图的关键信息。
过去十年间，研究者们提出了多种新方法来创建紧凑而有意义的图表示。这些方法的核心理念是：通过学习算法将原始图数据映射到一个新的空间，使得新空间中的几何关系能够反映原始图的结构特性。我们通常称这个过程为表示学习或网络嵌入。
表示学习 (representation learning，也称网络嵌入)是指学习一个从离散图到连续域的映射函数 $f:G\to R^d$ 的任务。函数 $f$ 能够生成低维向量表示，同时保留图 $G$ 的局部和全局特性。
学习得到映射函数 $f$ 后，可以将其应用于图中，生成的映射结果可作为机器学习算法的特征集，这一过程的如下所示。

映射函数 $f$ 不仅可以用于学习整个图的向量表示，还能专门针对节点和边进行表示学习。正如前文所述，图机器学习问题可以在不同粒度层级上进行分析，因此研究人员开发了不同的嵌入算法来学习特定的映射函数：

• 节点嵌入 (Node Embedding)：映射函数 $f:V\to R^d$，生成的向量空间能反映原始图中节点的结构关系
• 边嵌入 (Edge Embedding)：映射函数 $f:E\to R^d$，生成的向量空间能反映原始图中边的结构关系

这些映射函数构建的向量空间具有以下关键特性：

• 原始空间中相似的图结构/节点/边，在新空间中也保持相似性
• 相似结构的欧氏距离较小，不相似结构的欧氏距离较大

下面我们通过一个实际案例来直观理解嵌入空间的特性，以及如何在新空间中体现相似性关系。以下代码展示了 Node2Vec (将图 G 中的每个节点映射为一个向量)算法的应用示例：

from node2vec import Node2Vec

G = nx.barbell_graph(m1=7, m2=4)
draw_graph(G, nx.spring_layout(G))

node2vec = Node2Vec(G, dimensions=2)
model = node2vec.fit(window=10)
import matplotlib.pyplot as plt

fig, ax = plt.subplots(figsize=(10,10))

for x in G.nodes():
    
    v = model.wv.get_vector(str(x))
    ax.scatter(v[0],v[1], s=1000)
    ax.annotate(str(x), (v[0],v[1]), fontsize=12)

在前述代码中，完成了以下操作：

1. 生成了一个杠铃图 (barbell graph)
2. 然后使用 Node2Vec 嵌入算法，将图中的每个节点映射为一个二维向量
3. 最后，绘制生成的二维向量表示，每个向量表示原始图中的一个节点，向量空间中的位置反映节点间的结构关系

结果如下所示：

从图中可以看出，具有相似结构的节点在嵌入空间中彼此靠近，而与具有不相似结构的节点距离较远。还可以观察到 Node2Vec 在区分能有效区分组1和组3的节点。由于该算法使用每个节点的邻域信息来生成表示，因此能清晰区分不同群组。
我们再以 Edge2Vec 算法为例，对同一个图 G 的边进行向量化表示：

from node2vec.edges import HadamardEmbedder
edges_embs = HadamardEmbedder(keyed_vectors=model.wv)
import matplotlib.pyplot as plt

fig, ax = plt.subplots(figsize=(10,10))

for x in G.edges():
    
    v = edges_embs[(str(x[0]), str(x[1]))]
    ax.scatter(v[0],v[1], s=1000)
    ax.annotate(str(x), (v[0],v[1]), fontsize=16)

在前述代码中，完成了以下操作：

1. 生成了一个杠铃图 (barbell graph)
2. 将 HadamardEmbedder 嵌入算法应用于 Node2Vec 算法的结果 (keyed_vectors=model.wv)，将图中的每条边映射为二维向量
3. 最后，绘制由嵌入算法生成的二维向量，每个向量对应原始图中的一条边

结果如下所示：

在上图中展示了边嵌入算法的处理结果。从图中可以看到，算法能准确识别结构相似的边，属于组 1、组 2 和组 3 的边分别聚集在三个明确区域，特殊边 (6,7) 和 (10,11) (分别属于组 5 和组 4 )也形成了独立的聚类群组。
接下来，展示图向量 (Graph2Vec) 算法的应用，该算法可将整个图结构映射为单个向量，使用 Graph2Vec 算法生成一组图的嵌入表示：

import random
import matplotlib.pyplot as plt
from karateclub import Graph2Vec

n_graphs = 20

def generate_radom():
    n = random.randint(6, 20)
    k = random.randint(5, n)
    p = random.uniform(0, 1)
    return nx.watts_strogatz_graph(n,k,p), [n,k,p]

Gs = [generate_radom() for x in range(n_graphs)]

model = Graph2Vec(dimensions=2, wl_iterations=10)
model.fit([x[0] for x in Gs])
embeddings = model.get_embedding()

fig, ax = plt.subplots(figsize=(10,10))

for i,vec in enumerate(embeddings):
    
    ax.scatter(vec[0],vec[1], s=1000)
    ax.annotate(str(i), (vec[0],vec[1]), fontsize=40)

在前述代码中，完成了以下操作：

1. 使用随机参数生成 20 个 Watts-Strogatz 图
2. 然后执行图嵌入算法，生成每个图的二维向量表示
3. 最后，将生成的向量绘制在二维空间中

结果如下所示：

从上图可以看出，欧几里得距离较大的图具有不同的结构，如图 12 和图 8，前者是使用 nx.watts_strogatz_graph(20,20,0.2857) 参数生成的，后者是使用 nx.watts_strogatz_graph(13,6,0.8621) 参数生成的。相比之下，欧几里得距离较小的图它们具有相似的结构，如图 15 和图 4，图 15 是使用 nx.watts_strogatz_graph(9,9,0.5091) 命令生成的，而图4是使用 nx.watts_strogatz_graph(10,5,0.5659) 生成的。
研究人员已经提出了大量的嵌入方法，这些方法通常分为两大类：转导性 (Transductive) 和归纳性 (Inductive)，根据函数在添加新样本时的更新过程进行分类。如果提供了新节点，转导性方法会更新模型(例如重新训练)以推断节点的信息，而在归纳性方法中，模型应能够推广到训练期间未观察到的新节点、边或图。

3. 图嵌入算法分类

为生成图表示的紧凑空间，研究人员提出了多种方法。近年来，研究人员和机器学习实践者趋向于采用统一术语来描述这类算法。
每个图、节点或边的嵌入方法都可以通过两个基本组件来描述，分别是编码器 (Encoder, ENC) 和解码器 (Decoder, DEC)。编码器将输入映射到嵌入空间，而解码器则从学习到的嵌入中解码图的结构信息，如下图所示。

该框架基于一个直观理念：若编码后的嵌入能使解码器还原全部必要信息，则说明该嵌入包含了原始图的压缩表示，可用于下游机器学习任务。
在基于图的表示学习机器学习算法中，解码器通常被设计为将节点嵌入对映射为一个实数值，该数值代表原始图中节点之间的邻近度(距离)。举例来说，可以这样实现解码器：给定两个节点的嵌入表示 $Z_i=ENC(V_i)$ 和 $Z_j=ENC(V_j)$，当且仅当输入图中存在连接这两个节点 $Z_i$ 和 $Z_j$ 的边时，$DEC(Z_i,Z_j)$ =1。实际应用中，我们可以采用更有效的邻近度函数来度量节点间的相似性。
基于上图所示框架，我们将现在把各种嵌入算法分为四大类。我们将嵌入算法划分为四大类别，并通过伪代码示例辅助理解。在伪代码形式中，约定 G 代表 networkx 图对象，graphs_list 表示图列表，model 为嵌入算法实例：

• 浅层嵌入方法：这类方法只能学习并返回对已学数据的嵌入值。Node2Vec、Edge2Vec 和 Graph2Vec 就是浅层嵌入方法的例子。它们只能返回在拟合过程中学习到的数据的向量表示，无法为未见过的数据获得嵌入向量。使用这类方法的典型方式如下：

  model.fit(graphs_list)
  embedding = model.get_embedding()[i]
  

  在代码中，一个通用的浅层嵌入方法对图列表进行训练。模型训练完成后，只能获取属于 graphs_list 的第 i 个图的嵌入向量。
• 图自编码方法：这类方法不仅学习如何将输入图映射为向量，学习得到一个更一般的映射函数，能够为未见过的实例生成嵌入向量。使用这类方法的典型方式如下：

  model.fit(graphs_list)
  embedding = model.get_embedding(G)
  

  模型在 graphs_list 上训练。模型在输入训练集上训练完成后，就可以用它生成一个新的、未见过的图 G 的嵌入向量。
• 邻域聚合方法：这类算法可用于提取图级的嵌入，其中节点用某些属性标记。此外，和图自编码方法一样，这类算法能够学习一个通用的映射函数 $f(G)$，也能为未见过的实例生成嵌入向量。这类算法的一个优点是，构建的嵌入空间同时考虑图的内部结构和节点的节点外部属性(如语义特征)。例如，使用此方法，我们可以构建一个嵌入空间，能够同时识别具有相似结构但节点属性不同的图。
• 图形正则化方法：这类方法与前述各类方法略有不同。其特点在于不需要以图结构作为输入数据，而是通过挖掘特征间的"交互关系"来实现正则化学习。具体而言，可通过计算特征相似度来构建关系图，其核心假设是图中相邻节点应具有相同标签。因此，损失函数的设计会强制标签预测结果与图结构保持一致，例如约束相邻节点在 L2 范数距离下的嵌入向量保持相似。正因如此，编码器仅需使用节点特征 $X$ 作为输入。这类算法通过学习映射函数 $f(X)$，将特定特征集 ($X$) 转化为嵌入向量。与图自编码和邻域聚合方法类似，该算法也能将习得的函数应用于未见过的特征数据。

对于浅层嵌入方法和邻域聚合方法类算法，均可定义无监督和有监督版本。图自编码类算法适用于无监督任务，而图正则化类算法则用于半监督/监督场景。无监督算法仅利用输入数据集本身的信息(如节点、边或图结构)进行嵌入学习；有监督算法则借助外部信息指导嵌入过程，这类信息通常以标签形式存在(例如为每个图结构 $G_i$ 分配类别标签 $y_i$ 的配对数据 $<G_i,y_i>$）。
有监督学习过程比无监督更为复杂，因为模型需要寻找最优的向量表示以实现最佳的标签分配。以图像分类的卷积神经网络为例：在训练过程中，神经网络通过适配多个卷积滤波器来将图像归类到正确类别，这些滤波器的目标是找到输入数据的紧凑表示以最大化预测性能。同样的原理适用于有监督图嵌入算法，其目标是寻找最优的图表示形式，从而在类别分配任务中实现最佳性能。
从数学角度而言，这些模型都通过特定的损失函数进行训练。该函数可统一表述为两个组成部分：

• 第一部分监督项：用于监督学习场景，最小化预测结果与真实标签之间的差异
• 第二部分重构项：评估原始输入图与"编码+解码"后重构图之间的相似度(即结构重构误差)

其数学形式可定义为：
$$L=\alpha L_{sup}(y,\hat{y})+L_{rec}(G,\hat{G})$$
其中 $\alpha L_{sup}(y,\hat{y})$ 表示监督学习中的损失函数，通过优化模型使每个样本的真实类别 $y$ 与预测类别 $\hat{y}$ 之间的误差最小化。$L_{rec}(G,\hat{G})$ 则表征输入图 $G$ 与编码解码后重构图 $\hat{G}$ 之间的结构误差。在无监督场景中，由于缺乏目标变量，系数 $\alpha$ 取值为 0。
需要特别强调的是，这类算法在图结构机器学习问题中扮演着双重角色：既可作为被动预处理工具，将图数据转换为适合传统机器学习算法或可视化任务的特征向量；也可作为主动学习组件，在模型训练过程中直接寻找特定问题的紧凑且具有语义的解决方案。

小结

在本节中，我们回顾了机器学习的基础概念，并探讨了其在图数据中的应用。我们系统梳理了图机器学习的基本术语，重点阐释了图表示学习的内涵。通过建立图嵌入学习算法的分类框架，厘清了各类技术方案的差异化特征。