无标签

发布日期: 2023-04-20

作者: 熊水斌

文章字数: 4.9k

阅读时长: 16 分

阅读次数:

图深度学习

第1章绪论

1.1 图深度学习的动机

为什么要将现实数据表示为图？

为什么要将深度学习与图联系起来？

图深度学习面临哪些挑战？

为什么要将现实数据表示为图？

现实世界应用产生的数据可以有多种表示形式：矩阵、张量、序列等。将数据表示为图有两个原因：

图提供了数据的通用表示形式，来自各个领域的系统的数据可以直接表示为图，例如，社交网络、交通运输网络、知识图谱等，许多其它类型的数据可以转换为图的表示
许多现实问题可以通过图上的计算任务解决，例如，推断节点的属性、检测异常节点、识别与疾病相关的基因、向患者推荐药物，都可以归结为节点分类问题。对于朋友推荐、多药副作用预测、知识图谱补全，在本质上都是图上的链接预测问题。

为什么要将深度学习与图联系起来？

图上的节点是自然相连的，这表明节点不是独立的，但是传统的机器学习方法通常假设数据是独立同分布的，因此它们不适合直接用来解决图上的计算任务，解决思路主要有两种：

一种思路是建立一种特定于图的新机制，这种针对图设计的分类问题称为集体分类问题（collective classification），与传统分类不同，对于结点来说，集体分类不仅考虑其特征与其标签之间的映射，而且还要考虑其邻域相应的映射
另一种思路是通过构建一组特征来表示其节点，在该表示上可以应用传统的分类技术，这种思路变得越来越流行且主流。该思路的关键是如何为节点构造一组特征，或者说如何构造节点表示。而深度学习在表示学习方面具有强大的功能。

图深度学习面临哪些挑战？

传统的深度学习只是针对常规数据（例如图像和序列）进行设计的，而图可以具有不同的大小，图中的节点是无序的，并且可以具有不同的邻域
规则数据的结构信息很简单，而图的结构信息很复杂，并且节点和边可以包含丰富的额外信息。为传统数据设计的深度学习技术不足以捕获如此丰富的信息

1.2 图特征学习

为了利用传统的机器学习执行图上的计算任务，人们期望找到节点的表示形式，主要有两种方法可以实现此目标：特征工程和特征学习。

特征工程依赖手工设计的特征，例如节点度的统计信息；而特征学习是自动学习节点特征：

一方面，人们通常没有办法事先知道哪些特征是重要的，特别是对于给定的下游任务而言，因此来自特诊工程的特征对于下游任务而言可能不是最理想的，并且该过程需要大量的人力；
另一方面，特征学习是自动学习特征，该过程可以由下游任务直接知道，因此学习到的特征可能适合于下游任务，且通常比通过特诊工程获得的特征能够取得更好的性能，同时该过程需要最少的人工干预，并且可以轻松地适应新任务。

图的特征学习技术可以粗略地划分为：

图特征选择，用于移除节点上的无关和冗余的特征
图表示学习，目的是生成一组新的节点特征

图特征选择

现实世界中的数据通常是高维度的，并且存在着嘈杂的、不相关的和多余的特征。特征选择的目的是自动地选择一小部分特征，这些子集具有最小的冗余度，但与学习目标有最大的相关性。在许多应用中，原始特征对于知识提取和模型解释至关重要，例如，在用于研究癌症的遗传分析中，除了区分癌组织，鉴定诱导癌症发生的基因（即原始特征）更重要。在这种应用场景下，特征选择是优先考虑的，因为它可以保留原始特征，并且他们的语义通常为学习问题提供关键见解和解释。传统的特征选择假定数据样本是独立同分布的，然而，许多应用中的数据样本都嵌入在图上，因此，它们本质上不是独立同分布的，这就是图特征选择研究的领域。

首先，在有监督的情况下，对该问题进行研究，这些方法使用线性分类器将所选特征映射到类别标签，并引入图正则化项，以捕获结构信息来选择特征，该正则化项的目的是确保具有所选特征的连接的节点可以映射到相似的标签中。
然后，在无监督的情况下，对问题进一步研究，首先从结构信息中提取伪标签，然后用伪标签充当监督信息知道特征选择过程。（假定节点内容和结构信息都是从一组高质量的特征中生成的，而这些特征可以通过最大化生成过程获得）
在后续的工作中，问题从简单图扩展到复杂图，例如，动态图、多维图、有符号图、属性图等等

图表示学习

图表示学习是学习一组新的节点特征，这个问题被研究了数十年，通过深度学习得到了极大的加速。

在早期阶段，图表示学习在谱聚类、基于图的降维和矩阵分解的背景下进行了研究。

在谱聚类中，数据点被视为图的节点，然后聚类问题变成了将图划分为节点社区。谱聚类的关键一步是谱嵌入，它的目的是将节点嵌入到低维空间中，然后在该空间中可以将传统的聚类算法应用于识别聚类。
基于图的降维技术可以直接应用于学习节点表示，这些方法通常基于数据样本的原始特征，使用预定义的距离或相似度函数构建亲和度图，然后通过保留该亲和度图的结构信息学习节点表示。例如，IsoMap 通过测地线保留全局几何，而 LLE 和 eigenmap 保留亲和图中的局部邻域信息。因为前述方法经常需要在亲和矩阵（邻接矩阵或拉普拉斯矩阵）上进行特征分解，所以它们通常具有很高的计算复杂度。
矩阵分解可以自然地用于学习节点表示，矩阵分解的目的是将节点嵌入低维空间，在该低维空间中可以利用新的节点表示重建邻接矩阵
DeepWalk首先把Word2vec应用于图的节点表示学习，它首先把给定图中的节点视为人类语言的单词，并通过在图中随机游走生成该语言的句子。然后使用Skip-gram模型学习节点表示，从而保留了这些随机游走中的节点共现。（什么是节点共现？为什么在图中随机游走就是一个句子，该句子什么时候结束？）
- 开发先进的方法保存节点共现
- 保留其他类型的信息，例如，节点的结构角色、社区信息和结点状态
- 设计复杂图的嵌入框架，例如，有向图、异构图、二分图、多维图、有符号图、超图、动态图
因为深度学习在表示学习中的强大功能和成功经验，将深度学习扩展到图中的方法称为图神经网络（GNN），大致可以分为两类：空间方法和谱方法

空间方法显式地利用了图结构，例如空间上接近的邻居；谱方法通过图的傅里叶变换和逆变换得到图的谱视图。GNN在一下几个方面得到迅速发展：
- 提出了大量新的GNN模型，包括谱方法和空间方法
- 侧重于图的任务，例如，图分类（需要得到整个图的表示）。因此，许多池化方法被提出来，目的是为了从节点表示中获得图表示。

1.3 章节依赖关系

第2章图论基础

2.1 简介

首先讨论图的邻接矩阵和拉普拉斯矩阵及其重要性质，接着介绍节点带有属性的图（属性图），并通过将属性定义为函数或者信号来对这类图进行新的理解。然后讨论为图深度学习奠定了重要基础的图傅里叶分析和图信号处理的基本概念。

2.2 性质（特征工程）

中心性

节点的中心性（centrality）用于衡量节点在图中的重要性，中心性有多种类型的定义

度中心性（degree centrality）

如果有许多节点连接到某个节点 X，那么该结点 X 可以被认为是重要的。因此，可以基于一个结点的度来衡量它的中心性，即直接以节点的度作为其度中心性的定义。
特征向量中心性（eigenvector centrality）

度中心性认为度越大的节点越重要，且认为所有邻居节点的贡献度是一样的。然而，这些相邻节点本身的重要性是不同的，因此，它们对于中心节点的影响也不相同。

对邻居节点的中心性的平均值，是一种递归定义。

其中 $\lambda$ 是矩阵 A 的最大的特征值，将最大特征值对应的特征向量作为中心性向量。

在上图的案例中，$v_2,v_3,v_4$ 的度都是 2，但是根据 A 得到的中心性向量 $[1,0.675,0.675,0.806,1]$，其中 $v_4$ 的中心性值为 0.806，高于另外两个度为 2 的节点，这是因为 $v_4$ 和 $v_1,v_5$ 这两个高中心性（度为3）的节点直接相连。
Katz 中心性

不仅考虑邻居的中心性，而且包含了一个常数来考虑中心节点本身。

$\beta$ 表示一个包含所有节点的常数项的向量。类比特征向量中心性，应该满足 $\alpha = \frac{1}{\lambda_{max}}$，但实际往往是 $\alpha < \frac{1}{\lambda_{max}}$，目的是保证矩阵 $I-\alpha \cdot A$的可逆性
介数中心性（Betweenness Centrality）

前面提到的中心性都是基于和相邻节点的连接，另一种度量节点重要性的方法是检查该结点是否位于图中的重要位置，例如，许多路通过同一个结点，那么该节点处于图中的一个重要位置。

2.3 谱图论

图的拉普拉斯矩阵
$$
L = D-A
$$
归一化拉普拉斯矩阵
$$
L = D^{-\frac{1}{2}} (D-A) D^{\frac{1}{2}}
$$
拉普拉斯矩阵是半正定的，即对于任意一个实向量 $x$，满足 $x ^T L x \ge 0$。因此拉普拉斯矩阵的特征值是非负的。

拉普拉斯矩阵的零特征值的数量是图中连通分量的数目。

2.4 图信号处理

图中的节点常常关联一些特征或属性，这种图结构数据可以看做图信号，它捕获结构信息（即节点之间的连接）和数据（即节点上的属性）。

图信号由图 G={V,E} 和映射函数 f 构造，其中映射函数 f 将节点域上节点映射为实数值。

如果图中相邻的节点的值是相似的，那么认为这个图是平滑的（smooth）。一个平滑的图信号是低频率的，因为这些值通过图中的边在缓慢地变化。拉普拉斯矩阵的二次型可以用来测量一个图信号 f 的平滑度（频率），因为 $f^T L f$ 是所有相邻节点对的平方差之和。一个图信号 f 越平滑，则 $f^T L f$ 的值越小，即 $f^T L f$ 的值被称为信号的平滑度（频率）。

在传统的信号处理，信号可以表示在两个域：时域和频域。同样，图信号也可以表示在两个域，即空间域和谱域（频域）。图信号的谱域基础是图傅里叶变换（GFT），GFT 建立在谱图论之上。

2.5 复杂图

异质图

同质图中，每个节点都认为是同一个类型的节点，或者说每个节点具有的属性都相同；而异质图中，图中存在多种类型的节点，例如，知识图谱中存在作者节点、论文节点、会议节点等不同类型的节点。

二分图

多维图

节点和节点之间可以同时存在多种关系，例如，用户可以对视频进行点赞、分享、投币等

符号图

包含正边和负边的符号图（signed graphs），例如，用户关注用户为正，用户屏蔽用户为负

动态图

每个节点或每条边都与时间戳相关联，例如，下图中每条边都与一个时间戳相关联，而节点的时间戳是该节点产生第一条边的时间。

在实际情况中，无法记录每个节点和每条边的时间戳，通常在每隔一段时间记录图的快照，这种动态图称为离散动态图，它由一系列快照图组成。离散动态图可以认为是一个时间序列。

2.6 图的计算任务

图上的各种计算任务可以分为两大类：

一类侧重于节点的任务（node-level tasks），其中整个数据通常表示为一个图，每个数据样本是图中的一个节点
- 节点分类
  
  在现实世界的图中，节点常常与有用的信息相关联，这些信息可以被视为节点的标签。在社交网络中，这类信息可以是用户的人口统计属性，例如，年龄、性别、职业、兴趣、爱好等。这些标签有助于描述该节点的特征。但是通常很难为所有节点获得完整的标签集，只有不到1%的用户提供了完整的个人属性，因此很多时候得到的是一个只有一部分节点有标签的图，而哪些无标签的节点就需要通过模型预测标签。这就是节点分类问题。
- 节点排序
- 链接预测
  
  在许多实际应用中，图并不是完整的，会缺失一些节点之间的连接。一方面，这些连接是真实存在的，但是它们没有被观察到或者被记录下来，这就导致在图中丢失一些边。另外，许多图是自然演变的，例如，用户可以不断地与其它用户成为朋友。推断或预测这些缺失的连接可以用于许多场景，例如，好友推荐（friend recommendation）、知识图谱补全（knowledge graph completion）和犯罪情报分析（criminal intelligence analysis）。简单来说，连接预测就是预测在邻接矩阵中，哪些0值的位置最有可能变成1。
- 社区检测
另一类侧重于图的任务（graph-level tasks），其中数据往往包括一组图，每个数据样本是一个图
- 图分类
  
  图分类任务的本质是预测未标记图的标签。
- 图匹配
- 图生成

第4章图嵌入（表示学习）

通过无监督学习，将节点学习为向量表示，不需要考虑下游任务。

将节点特征和图结构作为输入，以一组新的节点特征作为输出的过程称为图滤波操作（graph filtering）。图深度学习目的是学习每个节点的代表性特征，这些节点特征有助于该类任务的后续处理。

对于侧重于节点的任务来说，仅仅使用图滤波操作就足够了，通常通过连续堆叠多个图滤波操作来生成最终的节点特征。但是对于侧重于图的任务来说，最终目标是学习整个图的代表性特征，而学习节点特征通常只是一个中间步骤，还需要其他的操作从节点特征生成整个图的特征，例如，池化操作（pooling）被用来汇总节点特征以生成图特征。由于图结构是不规则的，这就要求图的池化操作和传统的池化操作有所不同，图的池化操作应该利用图结构信息来指导池化过程。实际上，池化操作通常将图作为输入，然后生成节点更少的粗化图。