1.2　图神经网络的发展

1.2.1　图表示学习的历史

图表示学习旨在学习节点嵌入, 并在过去的几十年里得到了很大的发展, 可分为传统图嵌入、现代图嵌入和图深度学习。

作为图表示学习的第一代方法, 传统图嵌入已经在谱聚类、基于图的降维和矩阵分解等背景下得到广泛研究。现代图嵌入将 word2vec 成功扩展到图领域, 开启了第二代图表示学习。word2vec 是一种生成词嵌入的技术, 它将大量的文本语料库作为输入, 并为文本语料库中的每个唯一单词生成一个向量表示。word2vec 在各种自然语言处理任务中取得了巨大成功, 这激发了人们越来越多地尝试将 word 2vec (尤其是 skip-gram 模型) 应用于学习节点表示。DeepWalk ^[150] 迈出了实现这一目标的第一步。具体而言,给定一个图,其中的节点将被视为一种人工语言的单词, 随机游走会生成这种人工语言的句子。然后使用 skip-gram 模型学习节点表示, 这样就可以保留这些随机游走中节点的共现信息。随后, 一些经典的图嵌入方法被提出^{[19,69,106,155,194]}。

由于深度神经网络在表示学习方面的强大和成功, 越来越多的工作致力于将其推广到图中。图神经网络 (Graph Neural Network, GNN) 是其中最具代表性的工作, 它设计了一个基于卷积的算子, 目的是在空域中通过网络结构过滤节点属性。这些方法被称为图神经网络, 它们可以大致分为空域方法和谱域方法两种。谱域方法利用图的谱域视图, 通过图傅里叶变换和图傅里叶逆变换来设计可以用于过滤输入信号的某些频率的图谱滤波算子。 Bruna 等人在参考文献 [13] 中尝试设计图傅里叶系数, 而切比雪夫多项式滤波器算子被提出用于减少计算成本并使算子在空间上局部化^[35]。随后,Kipf 和 Welling 在参考文献 [101] 中简化了切比雪夫滤波器。Xu 等人在参考文献 [209] 中利用小波图滤波器来设计 GNN。另外, 基于空域的图神经网络已经发展起来, 这些方法明确地利用图结构 (例如利用空域中的相邻节点) 来设计空域滤波器。Kipf 和 Welling 提出了最经典的基于空域的 GNN, 随后 Hamilton 等人在参考文献 [73] 中提出了 GraphSAGE。GraphSAGE 首先采样邻居,然后引入了具有平均值、LSTM (Long Short-Term Memory, 长短期记忆) 或池化聚合器的邻居聚合策略。紧接着, 参考文献 [185] 引入了自注意力机制来学习图注意力网络中的邻居边权。

此外, 图神经网络不仅在节点级别的图分析任务上表现良好, 而且在以图为中心的任务 (如图分类) 上也表现出色。在这些任务中, 由于需要整个图的表示, 因此引入了许多池化方法^[59,125,221]。