1.1.3　图上的计算任务

目前有各种各样针对图的计算任务被提出。然而, 为了完成图上的各种任务, 我们首先需要基本的图表示, 即节点嵌入。它可以建模图中的有用信息, 获得节点嵌入的过程又称为图表示学习。

定义 1.13　图表示学习^[31]　图表示学习又称为网络嵌入,旨在学习一个将图中节点 嵌入低维欧几里得空间 (其中 ) 的函数 (见图 1.4)。

通过图表示学习, 复杂的非欧几里得空间网络被投影到低维欧几里得空间中, 从而很好地解决了高计算成本和低并行性的问题。

图1.4　图表示学习的一个例子(示例图来自Deep Walk^[150])

许多以节点为中心的任务已经得到广泛研究, 例如节点分类、节点排名、链接预测和社群检测。接下来, 我们主要讨论两个典型任务, 分别是节点分类和链接预测。由于在现实中往往很难为所有节点获取完整的标签集合, 我们也许只能获得一部分与标签相关联的图, 并旨在推断没有标签的节点的标签, 这启发了图上的节点分类问题。

定义 1.14　节点分类　在图 中,部分节点带有标签,这些节点集合表示为标签集 。没有标签信息的节点集合表示为无标签集 。具体而言, 且 。节点分类任务的目标是预测 中节点的标签,并通过从 和 中提取有用信息来学习一个映射函数 。

实际应用中的图并不完整, 往往存在缺失边, 一些边没有被观察或记录。推断或预测这些缺失的边, 可以为许多应用程序带来提升。

定义 1.15　链接预测　在图 中, 表示所有观察到的边。假设 表示所有可能的节点之间的边。未观察到的节点之间的潜在边集合表示为 ,其中 。链接预测任务的目标是预测最可能存在的边。在完成链接预测任务后,就可以为 中的每条边分配一个分数, 该分数表示边存在或将来出现的可能性。

除了节点级别任务, 还有许多图级别任务, 例如图分类、图匹配和图生成。接下来, 我们将讨论最具代表性的以图为中心的任务, 即图分类。

事实上, 节点分类将图中的每个节点视为一个数据样本, 并旨在为这些未标记的节点分配标签。在某些应用中, 每个样本可以表示为一个图。例如, 在化学信息学中, 化学分子可以表示为图, 其中原子是节点, 它们之间的化学键是边。不同化学分子具有不同的特性, 如溶解度和毒性, 这些特性可以视为它们的标签。现实中, 我们可能希望自动预测这些新发现化学分子的特性。这个目标可以通过图分类任务来实现, 图分类任务旨在为未标记的图预测标签。由于图结构的复杂性, 图分类通常不能简单地通过传统的分类方法来完成。图分类的定义如下。

定义 1.16　图分类　给定一组带标签的图 ,其中 表示图 的标签,图分类任务的目标是利用上述有标签的图 来学习一个映射函数,该映射函数可以为无标签的图预测标签。