第二章 图机器学习简介 Graph Machine Learning

---

前言

机器学习是人工智能的一个子集，旨在为系统提供从数据中学习和改进的能力。它在许多不同的应用中都取得了令人印象深刻的结果，特别是当显式地定义规则来解决特定任务是困难的或不可行的时候。例如，我们可以训练算法来识别垃圾邮件，将句子翻译成其他语言，识别图像中的物体，等等。

近年来，人们对将机器学习应用于图结构数据 的兴趣日益浓厚。在这里，主要目标是自动学习合适的表示，以做出预测，发现新的模式，并以一种比“传统”机器学习方法更好的方式理解复杂的动态。

本章将首先回顾一些基本的机器学习概念。然后，介绍图形机器学习，并特别关注表示学习（representation learning） 。然后，我们将分析一个实际的例子，以指导您通过理解理论概念。

本章将涉及以下主题:

• 机器学习回顾
• 什么是图上的机器学习，为什么它很重要?
• 一个通用的分类导航图机器学习算法

1. 环境要求Technical requirements

所有实验将在Python 3.8和Jupyter Notebook中完成。

实验所需的常用模块及建议版本如下：

• Jupyter==1.0.0
• networkx==2.5
• snap-stanford==5.0.0
• matplotlib==3.2.2
• pandas==1.1.3
• scipy==1.6.2

2. 理解图机器学习

在人工智能的各个分支中，机器学习是近年来最受关注的一个。它指的是一类通过经验自动学习和提高技能的计算机算法，而不需要显示设计（without being explicitly programmed）。这种方法需要从自然中获得灵感。想象一个运动员第一次面对一个新奇的动作:他们开始慢慢地、仔细地模仿教练的手势，尝试、犯错误、再尝试。最终，他们会进步，变得越来越自信。

那么，这个概念如何转化为机器呢?它本质上是一个优化问题。其目标是找到一种数学模型，能够在特定任务上实现最佳性能。可以使用特定的性能度量(也称为损失函数（loss function） 或成本函数（cost function） )来度量性能。在一个普通的学习任务中，算法会被提供数据，可能是大量的数据。该算法使用这些数据迭代地为特定的任务做出决策或预测。在每次迭代中，使用损失函数来评估决策。由此产生的误差被用来更新模型参数，以使模型能够更好地执行。这个过程通常被称为训练（training）。

更正式地说，考虑一个特定的任务$T$和一个性能指标$P$，它允许我们量化算法在$T$上的表现. (Mitchell et al.， 1997)指出如果一种算法在任务T上的性能随着经验E而提高(由P衡量)，则称该算法从经验E中学习。

2.1 机器学习的基本原理

机器学习算法分为三大类，即监督学习、无监督学习和半监督学习。这些学习模式取决于向算法提供数据的方式和性能的评估方式。

监督学习（Supervised learning） 是当我们知道问题的答案时所使用的学习范式。在此场景中，数据集由形式为$<x,y>$的成对样本组成，其中$x$是输入(例如，图像或语音信号)，$y$是相应的期望输出(例如，图像表示的内容或语音表示的内容)。输入变量也称为特征（features），而输出通常称为标签（labels）、目标（targets）和注释（annotations）。在监督设置中，通常使用距离函数来评估性能。根据标签的类型，监督学习可以进一步分为以下几类:

• 分类（Classification）:这里的标签是离散的，指的是输入所属于的“类”。分类的例子包括确定照片中的对象或预测电子邮件是否为垃圾邮件。
• 回归:目标是连续的。回归问题的例子是预测建筑物的温度或预测任何特定产品的销售价格。

无监督学习（Unsupervised learning） 不同于监督学习，因为问题的答案是未知的。在这里，我们没有任何标签，只有输入$<x>$被提供。因此，我们的目标是推断结构和模式，试图找到相似之处。

发现相似样本组(聚类 clustering)，高维空间中数据的表示都属于无监督学习。

半监督学习（semi-supervised learning） 算法使用标记和未标记数据的组合进行训练。通常，为了指导对无标记输入数据中存在的结构的研究，会使用数量有限的标记数据。

同样值得一提的是，强化学习（reinforcement learning） 被用来训练机器学习模型来做出一系列的决策。人工智能算法面临类似游戏的情况，根据执行的行动获得惩罚或奖励。算法的作用是理解如何行动，以最大化奖励和最小化惩罚。

将训练数据的误差最小化是不够的。机器学习的关键词是学习。这意味着即使是在看不见的数据上，算法必须能够达到同样的性能水平。评估机器学习算法泛化能力最常用的方法是将数据集分为两部分:训练集（training set） 和测试集（test set） 。模型在训练集上进行训练，在训练集上计算损失函数并用于更新参数。 此外，当有更多的数据可用时，测试集可以进一步分为验证集（validation set） 和测试集（test set） 。验证集通常用于评估模型在训练中的性能。

在训练机器学习算法时，可以观察到三种情况:

• 第一种情况中，模型在训练集上达到较低的性能水平。这种情况通常被称为欠拟合(underfitting) ，这意味着模型不够强大，无法处理该任务。
• 第二种情况中，模型在训练集上实现了高水平的性能，但在泛化测试数据上却遇到了困难。这种情况被称为过拟合(overfitting) 。在这种情况下，模型只是简单地记忆训练数据，而没有真正理解它们之间的真正关系。
• 理想的情况是当模型能够(可能)在训练和测试数据上都能实现最高水平的性能。

如图2.1 所示的风险曲线给出了过拟合和欠拟合的一个例子。从图中可以看出，训练集和测试集的性能随模型复杂度(拟合参数个数)的变化情况:

过拟合是影响机器学习实践的主要问题之一。发生的可能原因如下:

• 数据集可能定义不清或不能充分代表任务。在这种情况下，增加更多的数据可以帮助缓解问题。
• 用来解决这个问题的数学模型对于这个任务来说太强大了。在这种情况下，可以向损失函数添加适当的约束，以减少模型的“权利”。这样的约束称为正则项（regularization） 。

机器学习在许多领域都取得了令人印象深刻的成果，成为计算机视觉、模式识别和自然语言处理等领域最广泛、最有效的方法之一。

2.2 图机器学习的优点

目前常用的机器学习算法包络：回归算法(如线性回归和逻辑回归)、基于实例的算法(如KNN、SVM)、决策树算法(decision tree algorithm)、贝叶斯算法(如naïve Bayes)、聚类算法(如k-means)、人工神经网络(artificial neural networks)。

但这些算法成功的关键是什么呢?

从本质上都可以归结为同一件事，机器学习可以自动处理人类容易完成的任务。这些任务可能过于复杂，无法用传统的计算机算法来描述，在某些情况下，它们甚至显示出比人类更好的能力。在处理图时尤其如此——由于其复杂的结构，图在很多方面都和图像或音频信号不同。通过使用图机器学习，我们可以创建自动检测和解释重复出现的潜在模式的算法。

由于这些原因，人们对学习图结构数据的表示方式越来越感兴趣，许多机器学习算法已被开发用于处理图。例如,在生物交互图上可以确定蛋白质的作用,利用进化协作网络进行预测,利用社交网络推荐新产品给用户,等等。

由于图的性质，图可以在不同的粒度层级上进行分析:节点、边和图层次(整个图)，如图2.2所示。对于每一层，可能会面临不同的问题，因此，应该使用特定的算法:

在下面的要点中，我们将针对每个层级给出一些机器学习问题的例子:

• 节点层级:给定一个(可能很大)图 $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$是图所属的类。

在本节中，我们讨论了机器学习的一些基本概念。此外，通过引入一些处理图时常见的机器学习问题，丰富了我们的描述。有了这些理论原理作为基础，我们现在将介绍一些与图机器学习相关的更复杂的概念.

3. 广义图嵌入问题 The generalized graph embedding problem

在经典的机器学习应用程序中，处理输入数据的一种常见方法是从一组特征开始构建，这一过程称为特征工程，它能够为数据集中出现的每个实例提供紧凑而有意义的表示。

从特征工程步骤中获得的数据集将作为机器学习算法的输入。如果这个过程通常适用于大量的问题，那么当我们处理图时，它可能不是最优的解决方案。
实际上，由于其定义良好的结构，找到一个能够融合所有有用信息的合适表示可能不是一件容易的任务。

创建能够从图中表示结构信息的特征的第一种、也是最直接的方法是提取某些统计信息 。例如，一个图可以用度分布、效率和我们在前一章中描述的所有度量来表示。

更复杂的过程包括应用特定的内核函数，或者在其他情况下，应用能够将所需属性纳入最终机器学习模型的工程特定特征。但是，可以想象，这个过程可能非常耗时，在某些情况下，模型中使用的特性可能只是最终模型获得最佳性能所需的信息的一个子集。

在过去的十年中，为了定义新的方法来创建有意义和紧凑的图形表示，已经做了大量的工作。所有这些方法背后的基本思想是创建能够学习原始数据集的良好表示的算法，以便新空间中的几何关系反映原始图的结构。我们通常把学习给定图的良好表示的过程称为表示学习（representation learning） 或网络嵌入（network embedding） 。正式的定义如下所示。

表示学习(网络嵌入) 的任务是学习从离散图到连续域的映射函数，$f:G\to {\mathbb{R}}^n$。函数$f$将能够将图的节点进行低维向量表示，同时又能使图的属性(局部和全局)能得以保持。

一旦映射$f$通过学习得到，它就可以应用到图上，得到的映射可以用作机器学习算法的特征集。图2.3展示了这个过程的一个图形例子:

正如我们已经提到的，图上的机器学习问题可能发生在不同的粒度层级。因此还可以应用映射函数$f$来学习节点和边的向量表示。因此，学习函数来生成节点$f:V\to {\mathbb{R}}^n$的矢量表示称为节点嵌入（node embedding）， 学习函数来生成边$f:E\to {\mathbb{R}}^n$的矢量表示称为边嵌入（edge embedding）。这些映射函数试图构建一个向量空间，使新空间中的几何关系反映原始图、节点或边的结构。因此，我们将看到在原始空间中相似的图、节点或边在新空间中也会相似。

也就是说，在嵌入函数生成的空间中，相似结构的欧几里得距离较小，而不同结构的欧几里得距离较大。需要强调的是，虽然大多数嵌入算法在欧几里德向量空间中生成映射，但最近人们对非欧几里德映射函数产生了兴趣。

现在让我们看一个实际的例子，看看嵌入空间是什么样子的，以及在新的空间中可以看到怎样的相似性。在下面的代码块中，我们展示了一个使用称为Node to Vector (Node2Vec) 的特定嵌入算法的示例。我们将在下一章描述它是如何工作的。目前，我们仅需了解算法将图G的每个节点映射到一个向量中:

import matplotlib.pyplot as plt
def draw_graph(G, pos_nodes, node_names={}, node_size=50, plot_weight=False):
    nx.draw(G, pos_nodes, with_labels=False, node_size=node_size, edge_color='gray', arrowsize=30)
    
    pos_attrs = {}
    for node, coords in pos_nodes.items():
        pos_attrs[node] = (coords[0], coords[1] + 0.08)
        
    nx.draw_networkx_labels(G, pos_attrs, font_family='serif', font_size=20)
    
    
    if plot_weight:
        pos_attrs = {}
        for node, coords in pos_nodes.items():
            pos_attrs[node] = (coords[0], coords[1] + 0.08)
        
        nx.draw_networkx_labels(G, pos_attrs, font_family='serif', font_size=20)
        edge_labels=dict([((a,b,),d["weight"]) for a,b,d in G.edges(data=True)])
        nx.draw_networkx_edge_labels(G, pos_nodes, edge_labels=edge_labels)
    
    plt.axis('off')
    axis = plt.gca()
    axis.set_xlim([1.2*x for x in axis.get_xlim()])
    axis.set_ylim([1.2*y for y in axis.get_ylim()])

3.1 Node2Vec example

import networkx as nx
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. 我们生成了一个杠铃图；
2. 然后使用Node2Vec嵌入算法将图的每个节点映射到一个二维向量中；
3. 最后，绘制由嵌入算法生成的表示原始图节点的二维向量。

从图中可以很容易地看出，具有相似结构的节点非常接近，而与不同的结构的节点则保持一定距离。 Node2Vec在区分组1和组3方面做得如何也很有趣。由于该算法利用每个节点的相邻信息来生成表示，因此可以对两组进行明显的区分。

3.2 Edge2Vec example

在同一图形上的另一个例子可以使用Edge to Vector(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. 我们生成了一个杠铃图；
2. 将HadamardEmbedder嵌入算法应用于 Node2Vec算法(keyed_vectors=model.wv)的实验结果，用于将图的每条边映射到一个二维向量中；
3. 最后，绘制由嵌入算法生成的表示原始图节点的二维向量。

从结果图中可以地看出边缘嵌入算法很清楚识别类似的边缘。 正如预期的那样，属于组1、组2和组3的边聚类在定义良好和分组良好的区域中。 并且(6,7)和(10,11)边（属于组4和组5），也分别很好地聚类在特定的组中。

3.3 Graph2Vec Example

最后，我们将提供一个图到向量(Grap2Vec)嵌入算法的例子。该算法将一个图映射到一个向量中。在下面的代码块中，我们提供了一个Python示例，展示了如何使用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)] #随机生成20个Watts-Strogatz图

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)

Gs #列出所有的图

[(<networkx.classes.graph.Graph at 0x1f35d2b4250>, [10, 6, 0.128767775815537]),
 (<networkx.classes.graph.Graph at 0x1f35d2b4df0>,
  [12, 9, 0.7372534077172181]),
 (<networkx.classes.graph.Graph at 0x1f35d1135e0>,
  [8, 7, 0.43198883389880194]),
 (<networkx.classes.graph.Graph at 0x1f35d288a60>,
  [17, 15, 0.767661068133147]),
 (<networkx.classes.graph.Graph at 0x1f358c67dc0>,
  [15, 9, 0.7609303303616198]),
 (<networkx.classes.graph.Graph at 0x1f35d2ec2e0>,
  [13, 5, 0.0554433360654879]),
 (<networkx.classes.graph.Graph at 0x1f35d2ec160>,
  [13, 5, 0.9876661719190771]),
 (<networkx.classes.graph.Graph at 0x1f35d2ec100>,
  [17, 8, 0.4263302748463037]),
 (<networkx.classes.graph.Graph at 0x1f35d2ec0d0>,
  [6, 6, 0.42884423271020256]),
 (<networkx.classes.graph.Graph at 0x1f35d9ef0d0>,
  [9, 6, 0.40267094267082526]),
 (<networkx.classes.graph.Graph at 0x1f35d2ec310>,
  [12, 7, 0.09070518718983422]),
 (<networkx.classes.graph.Graph at 0x1f35d2ec130>, [6, 5, 0.3089875170608076]),
 (<networkx.classes.graph.Graph at 0x1f358c75a30>,
  [6, 6, 0.40565467622141915]),
 (<networkx.classes.graph.Graph at 0x1f35db9bd30>,
  [14, 8, 0.2726158698759191]),
 (<networkx.classes.graph.Graph at 0x1f35db56a00>,
  [18, 17, 0.452926553893246]),
 (<networkx.classes.graph.Graph at 0x1f35db56a90>,
  [18, 17, 0.5807880792448519]),
 (<networkx.classes.graph.Graph at 0x1f35db56ca0>, [8, 6, 0.9368555071579051]),
 (<networkx.classes.graph.Graph at 0x1f35db56eb0>,
  [19, 11, 0.7809691735267761]),
 (<networkx.classes.graph.Graph at 0x1f35db56ee0>,
  [10, 8, 0.026694905038849748]),
 (<networkx.classes.graph.Graph at 0x1f35db56f70>,
  [9, 6, 0.11043046664880829])]

#画出特定参数的图
G5 = nx.watts_strogatz_graph(13, 5, 0.0554433360654879)
G1 = nx.watts_strogatz_graph(12, 9, 0.7372534077172181)
G15 = nx.watts_strogatz_graph(18, 17, 0.452926553893246)
G4 = nx.watts_strogatz_graph(15, 9, 0.7609303303616198)

plt.figure(figsize=(15,10))

ax = plt.subplot(2,2,1)
draw_graph(G5, nx.circular_layout(G5))
ax.set_title('Graph5')
ax = plt.subplot(2,2,2)
draw_graph(G1, nx.circular_layout(G1))
ax.set_title('Graph1')
ax = plt.subplot(2,2,3)
draw_graph(G15, nx.circular_layout(G15))
ax.set_title('Graph15')
ax = plt.subplot(2,2,4)
draw_graph(G4, nx.circular_layout(G4))
ax.set_title('Graph4')

在这个例子中，已经做了以下工作:

1. 用随机参数生成了20个Watts-Strogatz图；
2. 然后，我们执行了图嵌入算法，以生成每个图的二维向量表示。
3. 最后，将生成的向量绘制在欧几里德空间中。

从以上两图可以看出，具有较大的欧氏距离的图，如图5和图1，具有较大差异的图结构。而具有较小欧氏距离的图，如图15和图4，则具有相似的图结构。

目前已有的文献已经开发了大量的嵌入方法。我们将在本书的下一部分详细描述并使用其中的一些方法。根据添加新样本时函数的更新过程，这些方法通常分为两种主要类型:直推（transductive） 和归纳（inductive） 。如果提供了新的节点，直推方法会更新模型(例如，重新训练)以推断出关于节点的信息，而在归纳方法中，模型有望推广到新的节点、边或在训练过程中没有观察到的图。

3. 图嵌入机器学习算法的分类

为图表示生成紧凑空间的各种方法已经被开发出来。近年来，研究人员和机器学习从业者都趋向于统一的符号来提供一个共同的定义来描述这些算法。在本节中，我们将介绍在《Machine Learning on Graphs: A Model and Comprehensive Taxonomy》https://arxiv.org/abs/2005.03675中定义的分类法的简化版本。

在这种形式表示中，每个图、节点或边缘嵌入方法都可以由两个基本组件来描述，即编码器和解码器。编码器(encoder，ENC) 将输入映射到嵌入空间，而解码器(decoder，DEC) 从学习的嵌入中解码关于图的结构信息(图2.7)。

本文中描述的框架遵循一个直观的想法:如果我们能够编码图,解码器能够获取所有必要的信息,然后嵌入必须包含所有这些信息的压缩版本,可用于下游机器学习任务:

在许多用于表示学习的基于图的机器学习算法中，解码器通常被设计成将节点嵌入对映射为一个实值，通常表示原始图中节点的接近(距离)。例如，可以实现这样的解码器:给定两个节点的嵌入表示，$z_i=ENC(V_i)$和$z_j=ENC(V_j)$，如果在输入图中存在连接两个节点$z_i，z_j$的边，则$DEC(z_i,z_j)=1$。在实际应用中，可以使用更有效的*邻近函数(proximity functions)*来度量节点之间的相似性。

3.1 嵌入算法的分类

受图2.7中描述的一般框架的启发，我们现在将嵌入算法分为四大类。此外，为了帮助您更好地理解这种分类，我们将提供伪代码中的简单代码快照。在伪代码形式中，我们将$G$表示为一个通用 networkx 图，graphs_list表示 networkx 图列表，model表示为通用的嵌入算法:

• 浅嵌入方法（Shallow embedding methods） :这些方法能够学习并只返回学习到的输入数据的嵌入值。我们前面讨论过的Node2Vec、Edge2Vec和Graph2Vec都是浅嵌入方法的例子。实际上，他们只能返回在适合过程中学习到的数据的矢量表示。要得到不可见数据的嵌入矢量是不可能的。使用这些方法的典型方法如下:

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

在代码中，一个通用的浅嵌入方法是在一个图列表上训练的(line 1)。一旦模型被拟合，我们只能得到属于graphs_list的第i个图的嵌入向量(line 2)。
无监督和有监督的浅嵌入方法将分别在第三章和第四章介绍。

• 图自动编码方法（Graph autoencoding methods） :这些方法不是简单地学习如何将输入的图映射成向量;他们学习了一个更通用的映射函数$f(G)$，它也能够为不可见的实例生成嵌入向量。使用它们的典型方法如下:

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

模型在graphs_list上进行训练(line 1)。一旦模型被拟合到输入训练集上，就可以使用它来生成一个新的看不见的图$G$的嵌入向量.图的自动编码方法将在第三章中介绍。

• 邻域聚合方法（Neighborhood aggregation methods） :这些算法可以用于在图层级提取嵌入，其中节点被标记为一些属性。另外，对于图的自动编码方法，这类算法可以学习通用的映射函数$f(G)$，也可以生成不可见实例的嵌入向量。这些算法的一个很好的特性是能够构建一个嵌入空间，在这个空间中，不仅要考虑图的内部结构，而且还要考虑一些外部信息，这些信息定义为图节点的属性。例如，利用这种方法，我们可以得到一个嵌入空间，它能够同时识别节点上具有相似结构和不同属性的图。无监督和有监督的邻域聚集方法将在第三章和第四章中介绍。

• 图正则化方法（Graph regularization methods） :基于图正则化的方法与前几点所列方法略有不同。这里，我们没有一个图形作为输入。相反，我们的目标是通过开发一组特性来学习“互动”使过程规范化。更具体地说，通过考虑特征相似度，可以由特征构造出一个图。其主要思想是基于图中邻近节点可能具有相同标签的假设。因此，损失函数被设计用来约束标签，使之与图的结构一致。例如，正则化可能限制相邻节点（根据它们在L2范数中的距离）共享相似的嵌入。由于这个原因，编码器只使用$X$节点特性作为输入。这类的算法学习一个函数$f(X)$，它将一组特定的特征$(X)$映射到一个嵌入向量。相较于图的自编码和邻域聚合方法，该算法也能够将学习到的函数应用到新的、看不见的特征上。图的正则化方法将在第四章中介绍。

浅嵌入和邻域聚合算法可以用于无监督和监督形式。图自动编码算法适用于无监督任务，而图正则化方法的算法适用于半监督/监督学习。

对于无监督算法，特定数据集的嵌入仅使用包含在输入数据集中的信息来执行，例如节点、边或图。对于监督学习，使用外部信息来指导嵌入过程。这些信息通常被归类为一个标签，例如$<G_i,y_i>$对，它给每个图分配一个特定的类。这个过程比无监督的过程更复杂，因为模型试图找到最佳向量表示，以找到标签给实例的最佳分配。为了阐明这个概念，我们可以想想卷积神经网络用于图像分类的例子。在训练过程中，神经网络通过同时进行各种卷积滤波器的拟合，试图将每幅图像分类到正确的类中。这些卷积滤波器的目标是找到输入数据的紧凑表示，以最大限度地提高预测性能。同样的概念也适用于监督图嵌入，其中算法试图找到最佳的图表示，以最大限度地提高类分配任务的性能。

从更数学的角度来看，所有这些模型都是用适当的损失函数来训练的。损失函数可以概括为两个部分:

• 第一部分最小化预测值和标签值之间的差异，用于监督学习。
• 第二部分用来评估输入图与经过ENC + DEC步骤重构后的图之间的相似度(即结构重构误差)。

形式上，损失函数可以定义为:
$$Loss=\alpha L_{sup}(y,\hat{y})+L_{rec}(G,\hat{G})$$

其中，$ \alpha L_{sup}(y,\hat y)$ 是监督学习中的损失函数。$ L_{rec}(G,\hat G)$ 是表示输入图($G$)与ENC + DEC处理后得到的图 ($\hat{G}$)之间重构误差的损失函数。对于无监督学习，$\alpha =0$，因为我们没有标签可以使用。

当我们试图在图上解决机器学习问题时，突出这些算法的主要作用是很重要的。它们可以被动地用于将图转换为适合于经典机器学习算法或数据可视化任务的特征向量。但它们也可以在学习过程中被积极使用，机器学习算法会为特定问题找到一个紧凑而有意义的解决方案。

总结

在本章中，我们回顾了一些基本的机器学习概念，并发现了如何将它们应用到图上。我们定义了基本的图机器学习术语，特别是图表示学习。将主要的图机器学习算法进行了分类。最后，提供了实际的例子，以开始理解如何将理论应用于实际问题。

在下一章中，我们将学习基于图的机器学习算法。我们将分析他们的特点，并介绍他们如何在实践中使用。