GNN 综述

一、Deep Learning On Graph[2018]

  1. 将传统深度学习框架应用于图数据存在一些挑战:

    • 图的不规则结构:和网格结构的图像、音频、文本数据不同,图数据具有不规则的结构,因此很难将一些基础的数学算子推广到图上。如,为图数据定义卷积、池化算法并不简单。这个问题通常被称作几何深度学习问题 geometric deep learning problem
    • 图的异质性heterogeneity 和多样性diversity:图本身可能很复杂,包含各种类型和属性。如,图可以是异质的或同质的、加权的或者不加权的、有向的或无向的。此外,图任务也有很大不同,包括 node-level 任务(如节点分类)、graph-level 任务(如图分类)。这些不同的类型、属性、任务需要不同的模型架构来解决特定的问题。
    • 大型图:大数据时代,真实的图很容易拥有数百万甚至数十亿个节点和边。一些著名的例子是社交网络和电商网络。因此如何设计可扩展 scalable 的模型非常关键。
    • 融合跨学科知识:图通常和其它学科联系在一起,如生物学、化学、社会科学。这种跨学科的性质带来了机遇和挑战:可以利用领域知识来解决特定问题,但是融合领域知识可以使得模型设计复杂化。如,当生成分子图时,目标函数和化学约束通常是不可微的,因此基于梯度的训练方法不容易应用。

    为了应对这些挑战,人们在这一领域做出了巨大努力,诞生了很多有关论文和方法。论文 《Deep Learning on Graphs: A Survey》 试图通过全面回顾图的深度学习方法来系统性总结不同方法之间的差异和联系。

    如下图所述,论文根据现有的模型架构和训练策略将这些方法分为五类:

    • 图递归神经网络 graph recurrent neural networks: Graph RNN
    • 图卷积网络 graph convolutional networks: GCN
    • 图自编码器 graph autoencoders: GAE
    • 图强化学习 graph reinforcement learning: Graph RL
    • 图对抗方法graph adversarial methods

    论文在下表中总结了这些方法之间的一些主要特点:

    • Graph RNN 通过在 node-level 或者 graph-level 对状态建模从而捕获图的递归模式 recursive pattern 或者序列模式 sequential pattern
    • GCN 在不规则图结构上定义卷积和 readout 操作,从而捕获常见的局部结构模式和全局结构模式。
    • GAE 假设 low-rank 图结构,并采用无监督方法进行节点 representation learning
    • Graph RL 定义了 graph-based 动作和奖励,从而在遵循约束的同时获得图任务的反馈。
    • 图对抗方法采用对抗训练技术来提升 graph-based 模型的泛化能力,并通过对抗攻击测试其鲁棒性。

  2. 相关工作:

    • 之前的一些调综述与我们的论文有关:

      • 《Geometric deep learning: going beyond euclidean data》 总结了一些早期的 GCN 方法以及流形上的CNN,并通过几何深度学习geometric deep learning对其进行了全面的研究。
      • 《Relational inductive biases, deep learning, and graph networks》 总结了如何使用 GNNGCN 进行关系推理,使用了一个统一的框架,即 graph network
      • 《Attention models in graphs: A survey 》 回顾了图的注意力模型。
      • 《Graph convolutional networks: Algorithms, applications and open challenges》 总结了一些 GCN 模型。
      • 《Adversarial attack and defense on graph data: A survey》 简要综述了图的对抗性攻击。

      我们的工作与之前的这些工作不同,我们系统地、全面地回顾了图上不同的深度学习架构,而不是专注于一个特定的分支。

      与我们的工作同时,《Graphneural networks: A review of methods and applications》《A comprehensive survey on graph neural networks》从不同的角度和分类对这个领域进行了综述。具体来说,他们的工作都没有考虑图强化学习或图对抗方法,而这些都是本文所涉及的。

    • 另一个密切相关的主题 graph embedding ,目的是将节点嵌入到低维向量空间中。 graph embedding 和本文之间的主要区别是:我们专注于不同的深度学习模型如何应用于图,而 graph embedding 可以被认作是使用其中一些模型的具体应用实例。另外,graph embedding 也可能使用非深度学习方法。

  3. 论文最后附录还给出了所有这些方法的源码地址、在公开数据集上的效果、时间复杂度。

1.1 基本概念

  1. 给定图 G=(V,E) ,其中 V={v1,,vN} 为节点集合, EV×VN=|V| 为节点数量, M=|E| 为边数量。

    • 每个节点 viV 关联一个特征向量 fiV,所有节点的特征向量构成节点特征矩阵 FV

    • 每条边 ei,jE 关联一个特征向量 fi,jE,所有边的特征向量构成边特征矩阵 FE

    • 定义 ARN×N 为邻接矩阵,其中第 i 行记作 A(i,:) ,第 j 列记作 A(:,j) ,第 ij 列元素为 A(i,j)

    • 图可以为有向的或者无向的,可以为带权图或者无权图。

      • 如果是有向图则 A 不是对称矩阵;如果是无向图则 A 是对称矩阵。
      • 如果是带权图则 A(i,j) 可以是任何数值;如果是不带权图则 A(i,j){0,1}
    • 无向图的拉普拉斯矩阵定义为 L=DA ,其中 D=diag(D1,,DN),Di=jA(i,j) 为节点的degree 矩阵。

      定义拉普拉斯矩阵的特征分解 eigen decomposition 为:

      L=QΛQ

      其中:

      • Λ=diag(λ1,,λN)L 的特征值eigenvalue组成的对角矩阵。
      • QRN×N 为对应特征向量eigenvector 组成的矩阵 。
    • 定义转移概率矩阵为 P=D1A,其中 P(i,j) 表示从节点 vi 经过一步随机游走到节点 vj 的概率。

    • 定义 vik-step 邻域为:

      Nk(i)={jdist(i,j)k}

      其中 dist(i,j) 表示节点 vi,vj 之间的最短距离。为了简化讨论,对于一阶邻域我们记作 N(i)=N1(i)

  2. 对于深度学习方法,我们使用上标来区分不同的层 layer,如 H(l) 。我们用 dl 来表示第 l 层的 representation 维度。

    通用的非线性激活函数记作 ρ(),其中 sigmoid 激活函数记作 σ(x)=1/(1+exp(x))relu 激活函数记作 ReLU(x)=max(0,x)

    除非另有说明,否则我们假设所有函数都是可微的,从而允许使用反向传播算法并使用常用的优化器和训练技术来学习模型参数。

    如果使用采样技术,则采样大小记作 s

  3. 图上的深度学习任务大致可以分为两类:

    • node-level 任务:这些任务和图中的各个节点有关,如节点分类、链接预测、节点推荐。
    • graph-level 任务:这些任务和整个图有关,如图分类、图属性预估、图生成。

1.2 Graph RNN

  1. 诸如 gated recurrent units: GRU 或者 long short-term memory: LSTM 之类的循环神经网络是建模序列数据的事实标准。这里我们总结了可捕获图的递归和序列模式的 Graph RNN

    Graph RNN 大致可以分为两类:node-level RNNgraph-level RNN 。主要区别是通过节点状态对 node-level 模式建模,还是通过公共的图状态对 graph-level 模型建模。下表给出了这些方法的主要特点。

1.2.1 node-level RNN

  1. 图的 node-level RNN,也称作图神经网络 graph neural networks: GNNs,其背后思想很简单:每个节点 vi 都由一个低维状态向量 si 来表示,从而编码图结构信息。

    受递归神经网络启发,GNN 采用了状态的递归定义:

    si=jN(i)F(si,sj,fiV,fjV,fi,jE)

    其中 F() 为待学习的函数。该公式也被称作状态方程。

    一旦得到 si ,则可以应用输出函数 O() 来得到最终输出:

    y^i=O(si,fiV)

    对于graph-level 任务,作者建议添加一个具有唯一属性的特殊节点来代表整个图。

    为学习模型参数,作者使用以下半监督方法:

    • 使用 Jacobi 方法将状态方程(即定义 si 的方程)递归求解到不动点 stable point
    • 使用 Almeida-Pineda 算法执行一个梯度下降 step
    • 最小化 task-specific 目标函数,如针对回归任务的平方损失。
    • 重复上述过程直到模型收敛。

    GNN 通过上述两个简单方程,发挥了两个重要作用:

    • GNN 统一了一些处理图数据的早期方法,如 RNN 和马尔科夫链。
    • GNN 的基本概念具有深远启发,许多最新的 GCN 实际上都有类似于状态方程的公式。

    尽管 GNN 在概念上很重要,但是它仍然存在一些缺陷:

    • 为确保状态方程具有唯一解, F() 必须是一个收缩映射 contraction map。即,μ,0μ<1 ,使得:

      ||F(x)F(y)||μ||xy||,x,y

      直观地看,收缩映射要求任意两个点之间的距离在经过 F() 映射之后必须减小,这严重地限制了模型的能力。

    • 在梯度下降的 step 之间,需要多轮迭代才能够收敛到不动点,因此 GNN 的计算量很大。

    由于存在这些缺陷,并且当时算力不高(GPU 在当时并未被广泛应用于深度学习),以及缺乏研究兴趣,当时 GNN 并未成为研究重点。

  2. GNN 的显著改进是 gated graph sequence neural networks:GGS-NNs 。在 GGS-NNs 中,作者使用 GRU 替代了状态方程中的递归定义,因此移除了收缩映射的约束,并支持了现代优化技术。

    具体而言,状态方程修改为:

    si(t)=(1zi(t))si(t1)+zi(t)s~i(t)

    其中 zi(t) 是通过更新门来计算,s~i(t) 为状态更新信息, t 为时间。

    然后作者提出依次使用若干个这种网络,从而产生序列输出,表明这种方法可以应用于序列任务。

  3. SSE 采用了类似于 GGS-NNs 的方法,但是并未使用 GRU ,而是采用随机固定点梯度下降 stochastic fixed-point gradient descent ,从而加快训练过程。

    这种方案基本上是在使用局部邻域计算不动点状态、优化模型参数之间交替进行。这两种计算都是在 mini-batch 中进行的。

1.2.2 graph-level RNN

  1. Graph-level RNN 中,不是将单个 RNN 应用于每个节点以学习节点状态,而是将单个 RNN 应用于整个图从而对图状态进行编码。

  2. 《GraphRnn:Generating realistic graphs with deep auto-regressive models》Graph RNN 用于图生成问题。具体而言,他们采用两种 RNN:一种用于生成新节点,另一种用于以自回归的方式为新添加的节点生成边。

    他们表明:这种层次 hierarchicalRNN 体系结构比传统的、基于规则的图生成模型更有效地从输入图中学习,同时具有合理的时间复杂度。

  3. 为捕获动态图的时间信息,DGNN 使用时间感知 time-awareLSTM 来学习node representation

    当建立新的边时,DGNN 使用 LSTM 更新这条边的两个交互节点以及它们直接邻居的 representation,即考虑一阶传播效果。作者表明:time-aware LSTM 可以很好地建模边生成的顺序 establishing order 和时间间隔time interval ,从而有助于一系列图的应用。

  4. Graph RNN 也可以和其它架构(如 GCN/GAE )组合。

    • 如,为解决稀疏性问题,RMGCNNLSTM 应用于 GCN 的结果,从而逐渐重建 reconstruct 图。通过使用 LSTM ,来自图不同部分的信息不需要很多 GCN 层就可以传递到很远的距离。
    • Dynamic GCN 使用 LSTM 来聚合动态网络中不同时间片的 GCN 结果,从而捕获时空图 spatial and temporal graph 的信息。

1.3 GCN

  1. 类似 CNN, 现代 GCN 通过精心设计的卷积函数和 readout 函数来学习图的常见局部结构模式和全局结构模式。

    由于大多数 GCN 可以使用 task-specific 损失函数(只有少数例外,如无监督学习方法),并通过反向传播进行训练。因此这里我们仅讨论体系结构。

    下表给出了我们总结的 GCN 的主要特征。

1.3.1 卷积操作

  1. 卷积操作可以分为两类:

    • 谱域卷积spectral convolution:卷积操作通过使用图傅里叶变换将node representation转换到谱域 spectral domain 中进行卷积。
    • 空域卷积 spatial convolution:卷积操作使用邻域节点进行卷积。

    注意,这两种卷积可以重叠 overlap,如使用多项式谱域卷积核 polynomial spectral kernel 时。

a. 谱域卷积
  1. 卷积是 CNN 中最基本的操作,但是用于图像或文本的标准卷积算子无法直接应用于图,因为图没有网格结构。

  2. 《Spectral networks and locally connected networks on graph》 首先使用图拉普拉斯矩阵 L 引入了谱域的图卷积,这种图卷积在信号处理中起着和傅里叶基 basis 相似的作用。

    定义图卷积算子 G 为:

    u1Gu2=Q((Qu1)(Qu2))

    其中 u1,u2RN 为定义在图 G 所有节点上的两个信号, Q 为图拉普拉斯矩阵 L 的特征向量 eigenvector 组成的矩阵 , 为逐元素乘法。

    简而言之:

    • 通过左乘 Q ,信号 u1,u2 被转换到谱域 spectral domain ,即图傅里叶变换 Graph Fourier Transform
    • 通过左乘 Q ,谱域信号又被转换到空域 spatial domain,即傅里叶逆变换。

    该定义的有效性基于卷积定理,即卷积运算的傅里叶变换是其傅里叶变换的逐元素乘积。

    定义谱域卷积核为 K=diag(g(λ1),,g(λN))RN×N 为一个对角矩阵,其对角线元素为拉普拉斯矩阵 L 的特征值 eigenvalue λi 的函数 g(λi)。其中 g(λi) 包含可学习的参数。

    因此作用在输入信号 uRN 的卷积运算为:

    u=QKQu

    其中 u 为输出信号。这里每个信号 u 表示所有节点某个维度的标量值拼接而成。

    通过将不同的卷积核应用于不同的 input-output 信号来定义卷积层,即:

    uj(l+1)=ρ(i=1dlQKi,j(l)Qui(l)),j=1,2,,dl+1

    其中:

    • l 表示第 l 层卷积层, dl 为第 l 层的 hidden representation 的维度。
    • ui(l) 为第 l 层所有节点的 hidden representation 向量在第 i 维的取值拼接而成的 RN 向量,也可以视为第 i 个输入通道。
    • Ki,j(l) 为第 l 层针对第 i 个输入通道、第 j 个输出通道的可训练的卷积核。

    上式背后的思想和传统的卷积类似:它使输入信号通过一组可学习的滤波器,从而聚合信息,然后进行一些非线性变换。通过使用节点特征矩阵 FV 作为输入层,并堆叠多个卷积层,模型整体架构类似于 CNN。理论分析表明:图卷积运算的这种定义可以模拟 CNN 的某些几何特性。

    但是,直接使用上式需要学习 O(N) 的参数,这在实践中不可行。此外,谱域中的滤波器可能不是空间局部性的 localized in the spatial domain,即在谱域卷积中,每个节点都会受到全局所有节点的影响(而不是仅受到局部邻域节点的影响)。为缓解这些问题 《Spectral networks and locally connected networks on graphs》 建议使用以下平滑滤波器 smoothing filters

    Ki,j(l)=αi,j(l)K

    其中 K 为一个固定的插值核 fixed interpolation kernelαi,j(l) 为可学习的插值系数。

    但是还有两个基本问题尚未解决:

    • 首先,每次计算都需要拉普拉斯矩阵的完整特征向量 eigenvectors ,因此每次前向传播、反向传播的时间复杂度至少为 O(N2) ,更不必说计算特征分解所需的 O(N3) 的复杂度。这意味着这种方法无法扩展到大型图。
    • 其次,由于滤波器取决于图的傅里叶基 basis Q ,因此无法在不同图之间共享参数。
  3. 有一些GCN 模型用于解决上述的第一个问题,即计算效率方向。

    • 为解决计算效率问题,ChebNet 提出使用多项式滤波器,即:

      K=diag(g(λ1),,g(λN))=k=0KθkΛk

      其中:

      • θ0,,θK 为可学习的参数,表示多项式系数。K 为多项式最高阶数。
      • Λ=diag(λ1,,λN) 为拉普拉斯矩阵特征值组成的对角矩阵。

      然后作者使用切比雪夫多项式展开来代替矩阵的特征分解:

      K=k=0KθkTk(Λ~)

      其中:

      • Λ~=2Λ/λmaxI 为重新缩放的特征值矩阵, λmax 为最大的特征值, IRN×N 为单位矩阵。
      • Tk(x)k 阶切比雪夫多项式。

      由于切比雪夫多项式的正交基的要求,这里重新缩放是有必要的。

      根据 Lk=QΛkQ ,则有:

      u=QKQu=k=0KθkQTk(Λ~)Qu=k=0KθkTk(L~)u=k=0Kθku~k

      其中 u~k=Tk(L~)uL~=2L/λmaxI

      根据切比雪夫多项式的递归定义,有:

      Tk(x)=2xTk1(x)Tk2(x)T0(x)=1,T1(x)=x

      因此有:

      u~k=2L~u~k1u~k2u~0=u,u~1=L~u

      现在仅需要计算稀疏矩阵 L~ 和某些向量的乘积,因此当使用稀疏矩阵的乘法时,时间复杂度为 O(KM) ,其中 M 为边的数量, K 为多项式的阶数。因此时间复杂度为边数量的线性函数。

      另外,也很容易看到这种多项式滤波器是严格地 K 阶局部化的:每次卷积时,节点 virepresentation 仅受到它 K 阶邻域 NK(i) 的影响(因为切比雪夫多项式的最高阶次为 K 次)。

    • 《Semi-supervised classification with graph convolutional networks》 进一步仅使用一阶邻域来简化滤波器:

      hi(l+1)=ρ(jN~(i)hj(l)W(l)d~i×d~j)

      其中:

      • N~(i)=N(i){i} 为添加自连接的一阶邻域, A~=A+I 为添加自连接的邻接矩阵,d~i 为添加自连接之后节点 videgree
      • hi(l)Rdl 为节点 vi 在第 l 层的 representationdlrepresentation 向量的维度。

      将其写作矩阵形式为:

      H(l+1)=ρ(D~1/2A~D~1/2H(l)W(l))

      其中 D~ 为添加自连接的 degree 矩阵。

      作者表明:通过设置 K=1 以及一个微小的修改,ChebNet 滤波器等价于上式。作者认为,如下图所述堆叠足够多的卷积层具有类似于 ChebNet 的建模能力,并且会带来更好的效果。下图中,每个节点仅被它们的直接邻居所影响。

    • ChebNet 及其扩展方法的重要洞察 insight 是:它们将谱域图卷积和空间结构联系在一起。具体而言,它们表明:当谱域卷积为多项式时(一阶多项式也是一种多项式),谱域卷积等价于空间卷积。

      另外,卷积公式 hi(l+1)=ρ(jN~(i)hj(l)W(l)d~i×d~j)GNN 中的状态定义 si=jN(i)F(si,sj,fiV,fjV,fi,jE) 高度相似,不同之处在于用卷积定义代替了递归定义。从这个方面来看,GNN 可以被视为具有大量 identical layer (即层与层之间都相同的)以达到稳定状态的 GCN。例如, GNN 使用固定参数的固定函数来迭代更新节点的 hidden state,直到达到状态平衡为止。而 GCN 具有预设的层数,并且每层使用不同的参数。

    • 还有一些谱域方法解决效率问题。如 CayleyNet 并未使用切比雪夫多项式展开,而是采用 Cayley 多项式来定义图卷积:

      K=θ0+2Re{k=1Kθk(θhΛiI)k(θhΛ+iI)k}

      其中 i=1 为单位虚数, θh 为另一个谱域缩放参数。

      除了证明 CayLeyNet 的效率和 ChebNet 一样,作者还证明了 Caylay 多项式可以检测 narrow frequency bands of importance 从而获得更好的效果。

    • Graph wavelet neural network:GWNN 通过重写公式 u1Gu2=Q((Qu1)(Qu2)),用图小波变换代替谱域滤波器中的傅里叶变换:

      u1Gu2=ψ((ψ1u1)(ψ1u2))

      其中 ψ 为图小波 graph wavelet 的基 bases

      通过使用快速近似算法来计算 ψ,ψ1GWNN 的计算复杂度也是 O(KM) ,和边的数量成线性关系。

  4. 有一些GCN 模型用于解决上述的第二个问题,即跨图的泛化。

    • Neural FPs 也提出一种使用一阶邻域的空间卷积方法:

      hi(l+1)=σ(jN~(i)hj(l)Wdegree(j)(l))

      由于参数 Wdegree(j)(l) 可以在不同的图之间共享,并且和图大小无关,因此 Neural FP 可以处理任意大小的多个图。注意这里 Wdegree(j)(l) 根据节点的 degree 不同而不同。

      上式和 《Semi-supervised classification with graph convolutional networks》 提出的滤波器非常相似,区别在于:Neural FP 不是通过添加归一化项来考虑节点 degree 的影响,而是为不同 degree 的节点学习不同的参数。该策略对于较小的图(如分子图)效果很好,但是无法扩展到更大的图。

    • PATCHY-SAN 使用诸如 Weisfeiler-Lehman kernel 之类的图 labeling 过程为节点分配了唯一的节点顺序,然后使用这个预分配的顺序将节点邻居排列。

      然后 PATCHY-SAN 通过从节点的 k 阶邻域 Nk(i) 中选择固定数量的节点,从而为每个节点 vi 定义了一个感受野 receptive field

      最后,PATCHY-SAN 采用一个标准的、带适当 normalization 的一维 CNN 到这个感受野上。

      通过这种方式,不同的图中的节点都具有固定大小和顺序的感受野,因此 PATCHY-SAN 可以从多个图中学习,就像正常的 CNN 从多个图像中学习一样。

      这种方式的缺点是卷积在很大程度上依赖于图 labeling 过程,而图 labeling 过程是一个预处理步骤,它并不是学习的一部分(即没有可学习的参数)。

      • LGCN 进一步提出通过按字典顺序简化排序过程。即根据邻居在最后一层 hidden representation H(L) 来排序。作者并没有使用一个单一的排序,而是分别对 H(L) 的不同维度(即通道)进行排序。
      • SortPooling 采用了类似的方法,但是它并不是对每个节点的邻居进行排序,而是对所有节点进行排序。即所有节点的所有邻域的排序都相同。

      尽管这些方法之间存在差异,但是对于图来说,强制采用一维节点顺序可能不是很自然的选择。

    • GCNN 采用 diffusion-basis 来代替图卷积中的 eigen-basis ,即节点的邻域由节点之间的扩散转移概率 diffusion transition probability 来决定。

      具体而言,卷积定义为:

      H(l+1)=ρ(PKH(l)W(l))

      其中 P=D1A 为节点之间的一阶转移概率, PK=PPK 为节点之间的 K 阶转移概率。K 为预设的扩散长度。W(l) 为可学习的参数矩阵,可以在任意大小的图之间共享。

      但是,计算 PK 的时间复杂度为 O(N2K) ,因此该方法无法扩展到大图。

    • DGCN 通过一个对偶图卷积 dual graph convolutional 框架来同时使用 diffusion baseadjacent base 。具体而言,DGCN 使用两个卷积:

      • 一个是邻接矩阵的形式:H(l+1)=ρ(D~1/2A~D~1/2H(l)W(l))

      • 另一个是将转移概率中的邻接矩阵转换为 pointwise mutual information:PPMI

        Z(l+1)=ρ(DP1/2MPDP1/2Z(l)W(l))

        其中 MPPPMI 矩阵:

        MP(i,j)=max(log(P(i,j)i,jP(i,j)iP(i,j)jP(i,j)),0)

        P(i,j) 为节点 vi,vj 之间的转移概率, DP(i,i)=jMP(i,j) 为基于 MP 的对角 degree 矩阵。

      然后 DGCN 通过最小化 HZ 之间的均方差来 ensemble 这两个卷积。

      DGCN 通过随机游走采样技术来加速转移概率的计算。实验表明:这种对偶卷积甚至对于单图问题single-graph problem也是有效的。

b. 空域卷积
  1. 基于谱域卷积的工作,《Neural message passing for quantum chemistry 》提出了MPNNs 为图的空域卷积提出了一个统一的框架,它使用消息传递函数 message-passing function

    mi(l+1)=jN(i)F(l)(hi(l),hj(l),fi,jE)hil+1=G(l)(hi(l),mi(l+1))

    其中:

    • F(l)() 为第 l 层待学习的消息函数。
    • G(l)() 为第 l 层待学习的节点更新函数。
    • mi(l) 为第 l 层节点 vi 的邻域和该节点之间传递的消息。

    从概念上讲MPNN 是一个框架,在该框架中,每个节点都根据其状态发送消息,并根据从直接邻居中收到的消息来更新节点状态。作者表明:上述框架已经包含了很多现代方法,如 GGSNNsNeural FPs 等都是特例。

    另外,作者建议添加一个 master 节点,该节点连接图中所有其它节点从而加速长程消息传递。并且作者拆分 hidden representation 到不同的 tower 来提高泛化能力。作者表明:MPNNs 的特定变体可以在预测分子特性方面达到 state-of-the-art 性能。

  2. GraphSAGE 采用类似 message-passing function 的思想,它使用聚合函数:

    mi(l+1)=AGG(l)({hj(l),jN(i)})hi(l+1)=ρ(Wl[hi(l),mi(l+1)])

    其中 [,] 是向量拼接操作, AGG(.) 表示聚合函数。

    作者提出三个聚合函数:均值池化、LSTM 、最大池化。例如对于最大池化有:

    AGG(l)=max{ρ(Wpoolhj(l)+bpool),jN(i)}

    其中 Wpool,bpool 是待学习的参数,max{} 为逐元素最大值函数。

    对于 LSTM 聚合函数,由于需要确定邻域顺序,因此作者采用了最简单的随机顺序。

  3. Mixture model network:MoNet 也尝试使用 “模板匹配“template matching ” 将现有的 GCN 模型以及用于流形 manifoldCNN 模型统一到一个通用框架中:

    hi,kl+1=jN(i)Fk(l)(u(i,j))hj(l),k=1,,dl+1

    其中:

    • u(i,j) 为节点 pair(vi,vj) 的伪坐标 pseudo-coordinates ,定义为:

      u(i,j)=(1D(i,i),1D(j,j))

      其中 D(i,i) 为节点 videgree

    • Fk(l)(u) 为待学习的函数,它返回一个向量。

    • hi,k(l)hi(l) 的第 k 维。

    换句话讲, Fk(l)(u) 作为组合邻域的加权 kernel 。然后 MoNet 采用以下高斯核:

    Fk(l)(u)=exp(12(uμk(l))(Σk(l))1(uμk(l)))

    其中 μk(l)Σk(l) 为待学习的均值向量和对角方差矩阵。

  4. Graph Network:GNs 提出了一个比 GCNs、GNNs 更通用的框架,它学习三组 representation

    {hi(l)},{ei,j(l)},{z(l)}

    分别代表节点 embedding、边 embedding、整个图的 embedding

    这些 representation 通过三个聚合函数、三个更新函数来学习:

    mi(l)=GEV({ei,j(l),jN(i)})mV(l)=GVG({hi(l),viV})mE(l)=GEG({ei,j(l),(vi,vj)E})hi(l+1)=FV(mi(l),hi(l),z(l))ei,j(l+1)=FE(ei,j(l),hi(l),hj(l),z(l))z(l+1)=FG(mE(l),mV(l),z(l))

    其中:

    • FV(),FE(),FG() 对应于节点更函数、边更新函数、全图更新函数。
    • G() 对应于消息传递函数,上标表示消息传递的方向。

    注意:消息传递函数都是以集合作为输入,因此它们的参数是可变数量的。因此这些消息传递函数对于输入的不同排列应该是不变的。一些排列不变的函数包括逐元素求和、均值池化、最大池化。

    MPNN 相比,GNs 引入了边的 representation 和全图 representation,从而使得框架更加通用。

  5. 总而言之,卷积运算已经从谱域发展到频域,并从 k-hop 邻域发展到直接邻域。目前,从直接邻域收集消息,如 H(l+1)=ρ(D~1/2A~D~1/2H(l)W(l)) , 并遵循 message-passing functionGraphSAGE aggregating functionsGNet aggretation/ update functions 是图卷积运算最常见的选择。

1.3.2 Readout 操作

  1. 使用图卷积操作可以学到有效的节点 representation 从而解决 node-level 任务。但是,为处理 graph-level 任务,需要聚合节点信息来构成 graph-level representation 。在文献中,这种聚合过程被称作 readout 操作。

    基于规则的局部邻域,标准的 CNN 可以执行步长大于 1 的卷积或池化操作来逐渐降低分辨率,从而得到 graph-level representation 。而图缺乏网格结构,因此无法直接应用现有的这些方法。

  2. 顺序不变性 order invariance:图的 readout 操作的关键要求是该操作不应依赖于节点顺序。即,如果我们改变节点编号和边的编号(编号改变意味着顺序改变),则整个图的 representation 不应改变。

    例如,一种药物是否可以治疗某些疾病取决于其固有结构,和我们对节点的编号顺序无关。如果我们采用不同的编号顺序,则应该得到相同的结果。

    注意:

    • 这个问题和图同构 isomorphism 问题有关,其中最著名的算法是拟多项式的 quasipolynomial ,所以我们只能找到多项式时间内 order-invariant 的函数。
    • 同构的两个图得到相同的 representation,反之不一定成立。即相同 representation 的两个图不一定是同构的 。
  3. 统计量:最常见的顺序无关算子包括简单的统计量 statistics ,如求和、均值池化、最大池化:

    hG=i=1Nhi(L)hG=1Ni=1Nhi(L)hG=max{hi(L),viV}

    其中: hG 为图 Grepresentationhi(L) 为节点 vi 在最后一层(第 L 层)的 representation

    这种一阶统计量虽然简单,但是不足以刻画不同的图结构。

    • 论文 《Molecular graph convolutions: moving beyond fingerprints》 建议通过使用模糊直方图 fuzzy histograms 来考虑节点 representation 的分布。

      模糊直方图背后的基本思想是:构建几个直方图分桶 histogram bins,然后计算 hi(L) 归属于哪个分桶。即,通过将节点 representation 作为样本,将它们和一些预定义的模板(每个模板代表一个分桶)进行匹配,最后返回最终直方图的拼接 concatenation 。通过这种方式,可以区分具有相同的 sum/average/maximum、但是具有不同节点分布的图。

    • 在论文 《Spectral networks and locally connected networks on graphs 》 中,作者采用了常用的一种方法:添加一个全连接层 FC 作为final layer

      hG=ρ([h1(L),,hN(L)]WFC)

      其中 [] 表示向量拼接, WFCR(NdL)×doutdout 为输出向量维度。

      上式可以视为 node-level representation 的加权和。优点之一是该模型可以为不同节点学习不同的加权权重。但是,这种能力是以无法保证顺序不变性为代价的。

  4. 层次聚类:实际上图具有丰富的层次结构,而不仅仅是 node-level、graph-level 这两层结构。可以通过层次聚类 hierarchical clustering 的方式来探索图的层次结构,如下图所示。

    • 《Spectral networks and locally connected networks on graphs》 使用了基于密度的 agglomerative 聚类,《Deep convolutional networks on graph-structured data》 使用了多分辨率谱聚类。ChebNetMoNet 使用了另一种贪婪的层次聚类算法 Graclus 来一次合并两个节点,并采用了一种快速池化的方法将节点重新排列为平衡二叉树。ECC 通过执行特征分解来使用另一种层次聚类方法。

      但是,这些层次聚类方法都和图卷积无关,而是作为预处理步骤进行的,并且无法以端到端的方式进行训练。

    • 为解决这个问题,DiffPool 提出了一种与图卷积联合训练的、可微的层次聚类算法。具体而言,作者提出使用 hidden representation 来学习每个层次中的 soft cluster assignment 矩阵。

      S(l)=F(A(l),H(l))

      其中:

      • S(l)RNl×Nl+1cluster assignment 矩阵,Nl 是层次中第 l 层的聚类簇的数量。
      • A(l) 是层次中第 l 层的邻接矩阵。
      • H(l) 是层次中第 l 层的 hidden representation
      • F() 是待学习的函数。

      然后根据 S(l) 取均值,可以得到粗化coarsened 图的node representation和新的邻接矩阵:

      H(l+1)=(S(l))H^(l+1),A(l+1)=(S(l))A(l)S(l)

      其中 H^(l+1) 为对 H(l) 应用一个图卷积层得到。

      因此,在 DiffPool 中每一层的卷积操作之后,图从 Nl 个节点被粗化到 Nl+1 个节点。初始图的节点数量为 N0=N , 最终图的节点数量为 NL=1 (即整个图只有单个节点)。因为 cluster assignment 操作是 soft 的,因此簇之间的连接并不是稀疏的,因此该方法的时间复杂度原则上为 O(N2)

  5. 强加顺序:如前所述,PATCHY-SANSortPooling 采用强加节点顺序impose order的思想 ,然后像 CNN 一样采用标准的一维池化。这些方法是否可以保留顺序不变性,取决于强加顺序的方式,这是另一个研究领域。

    除了强加节点顺序之外,还有一些启发式方法。在 GNN 中,作者建议添加一个连接到所有节点的特殊节点从而代表整个图。同样地,GNs 提出通过从所有节点和所有边接收消息来直接学习整个图的 representation

  6. MPNNs 采用 set2set,这是对 seq2seq 模型的修改。具体而言,set2set 使用 Read-Process-Write 模型,该模型同时接收所有输入,使用 attention 机制和 LSTM 计算内部状态,然后写入输出。

    seq2seq 的顺序敏感性不同,set2set 对于输入是顺序不变的。

  7. 简而言之,诸如均值、求和之类的统计量是最简单的 Readout 操作,而通过图卷积联合训练的层次聚类算法更加先进、也更复杂。还有一些其它的方法,如添加虚拟节点来代表图、或强加节点顺序。

1.3.3 改进

  1. 已有很多技术用于进一步改善 GCN。注意,其中一些方法是通用的,也可以应用于图上的其它深度学习模型。

  2. attention 机制:上述 GCN 中,邻域节点以相等或预定义的权重进行聚合。但是邻域节点的影响力可能差异很大,因此应该在训练过程中学习它们,而不是预先确定。

    受注意力机制的启发,图注意力网络 graph attention network:GAT 通过修改 hi(l+1)=ρ(jN~(i)hj(l)W(l)d~i×d~j) ,从而将注意力机制引入 GCN

    hi(l+1)=ρ(jN~(i)αi,j(l)hj(l)W(l))

    其中 αi,j(l) 为第 l 层中,节点 vj 对于节点 vi 的注意力:

    αi,j(l)=exp(LeakyReLU(F(hi(l)W(l),hj(l)W(l))))kN^(i)exp(LeakyReLU(F(hi(l)W(l),hk(l)W(l))))

    其中 F(,) 为待学习的函数,如多层感知机 MLP

    可以看到 αi,j(l) 满足:jαi,j(l)=1.0,0.0<αi,j(l)<1.0

    为提高模型的容量和稳定性,作者还提出使用多个独立的注意力,并将其结果进行合并。即下图所述的多头注意力机制 multi-head attention mechanism 。每种颜色代表不同的、独立的注意力向量。

    GaAN 进一步提出针对不同的 head 学习不同的权重,并将这种方法应用于交通预测问题。

    HAN 提出针对异质图的 two-level 注意力机制,即 node-level 注意力和 semantic-level 注意力。具体而言:

    • node-level 注意力机制类似于 GAT,但是也考虑了节点类型。因此它可以分配不同的权重来聚合 metapath-based 邻域。
    • 然后,semantic-level 注意力机制学习不同 metapath 的重要性,并输出最终结果。
  3. 残差和跳跃连接:很多研究观察到,现有 GCN 最合适的深度通常非常有限,如 2 层或 3 层。这个问题可能是由于训练深层 GCN 时比较困难,或者过度平滑 over-smoothing 问题导致。过度平滑问题是指:深层GCN 中,所有节点都具有相同的 representation

    为解决这些问题,可以考虑将类似 ResNet 的残差连接添加到 GCN 中。

    • 《Semi-supervised classification with graph convolutional networks》 在公式 H(l+1)=ρ(D~1/2A~D~1/2H(l)W(l)) 中添加了残差连接 residual connection

      H(l+1)=ρ(D~1/2A~D~1/2H(l)W(l))+H(l)

      他们通过实验表明:通过添加此类残差连接可以使得网络深度更深,这和 ResNet 结果类似。

    • Column network:CLN 采取了类似的思想,它使用以下具有可学习权重的残差连接:

      h~i(l+1)=ρ(jN~(i)hj(l)W(l)d~i×d~j)hi(l+1)=αi(l)h~i(l+1)+(1αi(l))hi(l)

      其中 αi(l) 为一组权重:

      αi(l)=ρ(bα(l)+Wα,1(l)hi(l)+Wα,2(l)jN(i)hj(l))

      其中 bα(l),Wα,1(l),Wα,2(l) 为模型参数。

      注意:hi(l+1)=αi(l)h~i(l+1)+(1αi(l))hi(l) 非常类似于 GGS-NNs 中的 GRU 。区别在于:这里的上标表示层数,不同的层包含不同的参数;在 GRU 中上标表示时间,并且跨不同时间步共享同一组参数。

    • 受到 personalized PageRank 启发,PPNP 定义如下的卷积层:

      H(l+1)=(1α)D~1/2A~D~1/2H(l)+αH(0)

      其中 H(0)=Fθ(FV)α 为超参数。

      注意:PPNP 的所有参数都在 Fθ() 中,而不是在卷积层中。

    • JK-Net 提出另一种体系结构,它将网络的最后一层和所有较低的 hidden layer 相连,即通过将所有 representation 跳跃到最终输出,如下图所述。这样,模型可以自适应地学习利用来自不同层的信息。

      正式地,JK-Net 定义为:

      hi(final)=AGG(hi(0),hi(1),,hi(L))

      其中:

      • hi(final) 为节点 vi 的最终 representation
      • AGG() 为聚合函数。JK-Net 使用三个类似于 GraphSAGE 的聚合函数:拼接 concatenation、最大池化 max-poolingLSTM attention
      • L 为网络层数。

      实验结果表明:添加跳跃连接可以提高 GCN 的性能。

  4. edge 特征:前面提到的 GCN 大多数聚焦于利用节点特征和图结构,这里我们讨论如何利用另一个重要的信息源:边特征。

    对于具有离散值(如边类型)的简单边特征,一种直接的方法是为不同的边类型训练不同的参数,然后对结果进行聚合。

    • Neural FPs 为不同 degree 的节点训练了不同的参数,这对应于分子图中不同化学键类型的隐式边特征,然后对结果进行求和。
    • CLN 在异质图中为不同的边类型训练不同的参数,然后对结果取均值。
    • Edge-conditioned convolution:ECC 也基于边类型训练了不同的参数,并将其应用于图分类。
    • Relational GCNs: R-GCNs 通过为不同的关系类型训练不同的权重,对知识图谱采用了类似的方法。

    但是这些方法仅适用于有限数量的、离散的边特征discrete edge feature

    • DCNN 将每条边转换为一个节点,该节点和该边的 head node, tail node 相连。进行转换之后,可以将边特征视为节点特征。

    • LGCN 构建一个线性图 line graph BR2M×2M 来融合边特征。线性图的 ”节点“ 是原始图中的边,如果信息流经原始图中的两条边,则它们在线性图中的 ”节点“ 是相连的。

      Bij,ij={1 if j=i and ji0 else

      (ij)(ij) 均为线性图中的节点。

      然后 LGCN 采用两个 GCN:一个位于原始图上、另一个位于线性图上。

    • 《Molecular graph convolutions: moving beyond fingerprints》 提出了一个使用 weave module 的架构。具体而言,他们学习了节点和边的representation,并使用四个不同的函数在每个 weave module 中交换它们之间的信息:节点到节点 node-to-node:NN、节点到边 node-to-edge:NE、边到边 edge-to-edge:EE、边到节点 edge-to-node:EN

      hi(l)=FNN(hi(0),hi(1),,hi(l))hi(l)=FEN({ei,j(l)jN(i)})ei,j(l)=FEE(ei,j(0),ei,j(1),,ei,j(l))ei,j(l)=FNE(hi(l),hj(l))hi(l+1)=FNN(hi(l),hi(l))ei,j(l+1)=FEE(ei,j(l),ei,j(l))

      其中:

      • ei,j(l) 为边 (vi,vj) 在第 l 层的 representation
      • F() 为可学习的函数,其下标表示消息传递的方向。

      通过堆叠多个这样的 module ,信息可以在节点 representation 和边representation 之间交替传递。

      注意:在节点到节点的函数、边到边的函数中,隐式添加了 JK-Nets 相似的跳跃连接。

    • GNs 还提出了学习边的 representation,并通过消息传递函数来同时更新 node representationedge representation 。这这一方面,weave moduleGNs 的特例,这个特例并不学习整个图的representation

  5. 采样:在大型图上训练 GCN 时,关键的瓶颈之一是计算效率。如前所述,许多 GCN 采用邻域聚合方案。但是,由于很多真实场景的图遵循幂律分布 power-low distribution,其中少量节点的 degree 非常大、大量节点的 degree 非常小,因此不同节点的邻域规模差异很大。

    为解决这个问题,已经提出两种类型的采用方法:邻域采样 neighborhood samplings 、逐层采样 layer-wise samplings 。如下图所示,其中蓝色节点表示一个 batch 的样本,箭头表示采样方向,B 中的红色节点表示历史采样样本。

    • 在邻域采样中,GCN 在计算期间对每个节点执行采样。

      • GraphSAGE 在训练期间为每个节点统一采样固定数量的邻居。
      • PinSage 提出在图上使用随机游走对邻域进行采样,同时还有一些实现方面的改进,包括 CPUGPU 之间的协同、一个 map-reduce inference pipeline 等。PinSage 被证明能够处理真实的、十亿级的图。
      • StochasticGCN 进一步提出通过使用上一个 batch 的历史激活作为控制变量来降低采样方差,从而理论上保证可以使用任意小的采样数量。
    • FastGCN 并没有对节点的邻域进行采样,而是在每个卷积层中对所有节点进行采样,即 layer-wise 采样。FastGCN 将节点解释为独立同分布的样本,并将图卷积解释为概率测度下的积分变换。FastGCN 还显示:通过归一化 degree 来采样节点可以降低方差并提高模型性能。

      《Adaptive sampling towards fast graph representation learning》 进一步提出基于更高一层layer 为条件来采样更第一层 layer 的节点,从而更加自适应,并显著降低方差。

  6. inductive learningGCN 模型的一个重要特点是,它是否可以应用于 inductive learning 。即在一组节点或图上进行训练,并在另一组未见过的节点或图上进行测试。

    原则上,这个目标是通过学习给定特征上的映射函数来实现的,其中给定的特征不依赖于图结构,使得这个映射函数可以迁移到未见过的节点或图上。

    inductive learning 已经在 GraphSAGE、GAT、GaAN、FastGCN 中得到了验证。但是,现有的 inductive GCN 仅适用于具有显式特征的图,如何对没有显式特征的图(通常称作样本外问题 out-of-sample problem )进行 inductive learning 仍然是悬而未决的。

1.3.4 理论分析

  1. 为理解 GCN 的有效性,人们提出了一些理论分析,可以分为三类:node-level 任务、graph-level 任务、一般性分析。

  2. node-level 任务:

    • 《Deeper insights into graph convolutional networks for semi-supervised learning》 首先通过使用特殊形式的拉普拉斯平滑分析了 GCN 的性能:拉普拉斯平滑使得同一个簇内的节点的 representation 相似。

      原始拉普拉斯平滑操作如下:

      hi=(1γ)hi+γjN(i)1dihj

      其中 hi 为节点 vi 的原始representationhi 为节点 vi 的拉普拉斯平滑后的representation

      可以看到拉普拉斯平滑非常类似于卷积公式 hi(l+1)=ρ(jN~(i)hj(l)W(l)d~i×d~j) 。基于这种洞察,论文提出了 GCNCo-TrainingSelf-Training 方法。

    • 最近 《Simplifying graph convolutional networks》 从信号处理的角度分析了 GCN。通过将节点特征视为图信号,他们表明公式 hi(l+1)=ρ(jN~(i)hj(l)W(l)d~i×d~j) 基本上是一个固定的低通滤波器。

      利用这一洞察,他们提出了 simplified graph convolution:SGC 方法,该方法消除所有非线性并将所有待学习的参数收缩 collapsing 到一个矩阵:

      H(L)=(D~1/2A~D~1/2)LFVW

      作者表明:这种 non-deeplearningGCN 变体可以在很多任务上达到与现有 GCN 匹配的性能。

    • 《Revisiting graph neural networks: All we have is low-pass filters》 通过证明低通滤波操作并没有为 GCN 配备非线性流形学习能力来强化这一结果,并进一步提出 GFNN 模型来解决这个额外的难题,方法是在图卷积层之后添加一个 MLP 层。

  3. graph-level 任务:

    • 《Semi-supervised classification with graph convolutional networks》SortPooling 都考虑 GCNgraph kernel (如 Weisfeiler-Lehman:WLkernel )之间的联系,其中 graph kernel 广泛用于图同构测试 graph isomorphism tests

      他们表明:从概念上讲 GCNWL kernel 的泛化,因为这两种方法都会迭代地聚合来自节点领域的信息。

    • 《How powerful are graph neural networks?》 通过证明 WL kernel 在区分图结构方面为 GCN 提供了上限,从而形式化了这一思想。

      基于该分析,他们提出了 graph isomorphism network:GIN ,并表明使用一个基于求和的 Readout 操作、一个 MLP 就可以实现最大判别能力,即在 graph classification 任务中具有最高的训练 accuracy

  4. 一般性分析:

    • 《The vapnik–chervonenkis dimension of graph and recursive neural networks》 表明:具有不同激活函数的 GCNVC-dim 具有与 RNN 相同的规模。

    • 《Supervised community detection with line graph neural networks》 分析了线性 GCN 的优化情况,并表明在某些简化下,任何局部极小值都接近于全局最小值。

    • 《Stability and generalization of graph convolutional neural networks》 分析了 GCN 的算法稳定性和泛化界。

      他们表明:如果图卷积滤波器的最大绝对特征值和图大小无关,则单层 GCN 会满足均匀稳定性 uniform stability 的强概念。

1.4 Graph AutoEncoder

  1. 自编码器 autoencoder:AE 及其变体已经被广泛应用到无监督学习任务中,它适用于学习图的节点 representation。其背后隐含的假设是:图具有固有 inherent 的、潜在potentially 的非线性低秩结构。

    这里我们首先介绍图自编码器graph autoencoder:GAE ,然后介绍图变分自编码器graph variational autoencoder 以及其它改进。下表总结了 GAE 的主要特点,其中 TC 表示时间复杂度。

1.4.1 图自编码器

  1. 图自编码器起源于稀疏自编码器 sparse autoencoder:SAE,其基本思想是:将邻接矩阵或其变体视为节点的原始特征,然后利用自编码器作为降维技术来学习节点 representation

    具体而言,SAE 使用了如下的 L2 重构损失函数:

    minΘL2=i=1NP(i,:)P^(i,:)2P^(i,:)=G(hi),hi=F(P(i,:))

    其中:

    • P 是转移矩阵, P^ 为重构的转移矩阵。
    • hiRd 为节点 vi 的低维 representation 向量, dN 为节点 representation 向量维度。
    • F() 为编码器, G() 为解码器,Θ 为模型参数。通常编码器和解码器都是具有多个隐层的 MLP

    换句话讲,SAE 通过编码器将 P(i,:) 的信息压缩为低维向量 hi ,然后利用解码器从该向量重构原始特征。

    另外,还可以在损失函数中添加一个正则化项。

    在获得低维 representation hi 之后,可以使用 k-means 算法来用于节点聚类。

    实验表明:SAE 优于非深度学习 baseline。但是,SAE 是基于不正确incorrect 的理论分析,其有效性的底层机制仍然无法解释。

  2. Structure deep network embedding:SDNE 解决了这个问题。SDNE 表明:L2=i=1NP(i,:)P^(i,:)2 重构损失实际上对应于节点之间的二阶邻近度second-order proximity 。即,如果两个节点共享相似的邻域,则它们应该具有相似的潜在表示。这是 network science 中被深入研究的概念,被称作协同过滤或三角闭合 triangle closure

    由于 network embedding 方法表明一阶邻近度也很重要,因此 SDNE 通过添加另一个拉普拉斯特征图 Laplacian Eigenmap 项来调整目标函数:

    minΘL2+αi,j=1NA(i,j)hihj2

    即:如果两个节点直连,则它们也共享相似的潜在表示。

    作者还通过使用邻接矩阵来修改 L2 重构损失,其中零元素和非零原始赋予不同的权重:

    L2=i=1N(A(i,:)G(hi))bi2

    其中:

    • hi=F(A(i,:))
    • A(i,j)=0bi,j=1,否则 bi,j=β>1 。其中 β 是另外一个超参数。

    SDNE 整体架构如下图所示,它通过 deep autoencoder 来保持节点之间的一阶邻近度和二阶邻近度。

  3. DNGR 使用 positive pointwise mutual information: PPMI 代替转移概率矩阵 P ,这样原始特征就可以和图的某些随机游走概率相联系。但是,构造输入矩阵的时间复杂度为 O(N2) ,无法扩展到大型图。

  4. GC-MC 采用了不同的方法,它使用 GCN 来作为编码器:

    H=GCN(FV,A)

    然后使用一个简单的 bilinear 函数作为解码器:

    A^(i,j)=hiΘdehj

    其中 Θde 为解码器参数。

    通过这种方式,可以很自然地融合节点特征。对于没有节点特征的图,可以使用节点 IDone-hot 向量。作者证明了 GC-MC 在二部图推荐问题上的有效性。

  5. DRNE 并没有重构邻接矩阵或其变体,而是提出了另一种思路:通过LSTM 聚合邻域信息来直接重构低维节点 embedding 向量。具体而言,DRNE 采用以下目标函数:

    L=i=1NhiLSTM({hjjN(i)})

    由于 LSTM 要求输入为序列,因此作者建议根据邻域内每个邻居节点的 degree 对邻居节点进行排序。作者还对具有较大degree 的节点采用邻域采样技术,从而防止序列太长。

    作者证明:DRNE 可以保留 regular equivalence,以及节点的很多 centrality measure,如 PangeRank

  6. 与上述将节点映射为低维向量的工作不同,Graph2Gauss:G2G 提出将每个节点编码为高斯分布 hi=N(M(i,:),diag(Σ(i,:))) 来捕获节点的不确定性。

    具体而言,作者使用从节点属性到高斯分布的均值、方差的深度映射作为编码器:

    M(i,:)=FM(fiV)Σ(i,:)=FΣ(fiV)

    其中 FM(),FΣ() 都是待学习的函数。

    然后,它们使用 pairwise 约束来学习模型,而不是使用显式的解码器函数:

    KL(hj||hi)<KL(hj||hi),i,j,js.t.d(i,j)<d(i,j)

    其中:

    • d(i,j) 为节点 vivj 之间的最短距离。
    • KL(q()||p())q()p() 之间的 Kullback-Leibler: KL 距离。

    换句话讲,约束条件确保node representation之间的 KL 距离和图中节点之间距离保持相同的相对顺序。

    但是,由于上式难以优化,因此作者采用基于能量的损失函数作为松弛:

    L=(i,j,j)D(Ei,j2+expEi,j)

    其中:

    • D={(i,j,j)d(i,j)<d(i,j)} 为训练三元组,它保持 d(i,j)<d(i,j) 的关系。
    • Ei,j=KL(hj||hi)KL 距离。

    作者进一步提出了无偏的采样策略,从而加快训练过程。

1.4.2 变分自编码器

  1. 与上述自编码器不同,变分自编码器 variational autoencoders:VAE 是将降维技术和生成模型结合在一起的另一种深度学习方法。它的潜在优点包括对噪声容忍、以及能够学习平滑的 representation

  2. VAE 首次被引入图数据是在 VAGE,其中解码器是简单的线性内积:

    p(AH)=i,j=1Nσ(hihj)

    其中节点 representation 假设服从高斯分布:

    q(hiM,Σ)=N(hiM(i,:),diag(Σ(i,:)))

    作者使用 GCN 作为均值和方差的编码器:

    M=GCNM(FV,A)logΣ=GCNΣ(FV,A)

    然后通过最小化变分下界 variational lower bound 来学习模型参数:

    L=Eq(HFV,A)[logp(AH)]KL(q(HFV,A)||p(H))

    但是该方法需要重构完整的图,因此时间复杂度为 O(N2)

  3. 受到 SDNEG2G 启发,DVNE 为图数据提出了另一种 VAE,它也将每个节点表示为高斯分布。和现有的采用 KL 散度作为距离度量不同,DVNE 使用 Wasserstein 距离来保留节点相似度的传递性 transitivity

    SDNEG2G 相似,SVNE 在目标函数中保留了一阶邻近度和二阶邻近度:

    minΘ(i,j,j)D(Ei,j2+exp(Ei,j))+αL2

    其中:

    • Ei,j=W2(hj||hi) 为两个高斯分布 hjhi 之间的二阶 Wasserstein 距离。
    • D={(i,j,j)jN(i),jN(i)} 为三元组的集合,用于计算一阶邻近性的 ranking loss

    重构损失定义为:

    L2=infq(ZP)Ep(P)Eq(ZP)P(PG(Z))22

    其中 P 为转移矩阵, Z 为从 H 中采样得到。整体架构如下图所示。

    通过这种方法,目标函数可以像传统VAE 中使用 reparameterization 技巧一样被最小化。

1.4.3 改进

  1. 对抗训练:

    • ARGA 通过在 GAE 中添加一个额外的正则化项,从而引入了对抗训练 adversarial training。其总体架构如下图所示。

      具体而言,GAE 编码器用作生成器generator,而判别器discriminator 目标是区分潜在representation是来自生成器还是来自先验分布。通过这种方式,自编码器被迫匹配先验分布,这相当于是一个正则化。

      ARGA 的目标函数是:

      minΘL2+αLGAN

      其中 L2 对应于GAE 中的重构损失,而 LGAN 为:

      LGAN=minGmaxDEhPh[logD(h)]+EzG(FV,A)[log(1D(z))]

      其中:

      • F(FV,A) 为生成器,它使用VAGE 中的图卷积编码器。
      • D() 为基于交叉熵损失的判别器。
      • Ph 为先验分布,论文采用简单的高斯先验。

      实验结果证明了对抗训练方案的有效性。

    • 同一时期,NetRA 也提出了一个生成对抗网络 generative adversarial network:GAN 来提升图自编码器的泛化能力。作者使用如下的目标函数:

      minΘL2+α1LLE+α2LGAN

      其中:

      • L2 对应于GAE 中的重构损失。
      • LLE 对应于拉普拉斯特征图损失。
      • LGAN 对应于生成对抗损失。

      此外,作者使用 LSTM 作为编码器,从而聚合邻域信息。NetRA 并没有像 DRNE 中那样仅对直接邻居进行采样并使用 degree 对直接邻居进行排序,而是使用了随机游走来生成输入序列。

      ARGA 相比,NetRA 认为 GAErepresentationground-truth,并使用随机高斯噪声然后接一个 MLP 作为生成器。

  2. inductive learning:和 GCN 相似,如果将节点属性融合到编码器中,则 GAE 可以应用于 inductive learning。 这可以通过使用 GCN 作为编码器来实现,如在 GC-MC, VGAE 中。

    也可以通过直接学习一个从节点特征到 embedding 的映射函数来实现,如 G2G 。由于仅在学习参数时才用到边信息,所以该模型也可以应用于训练期间未曾见过的节点。

    这些工作还表明,尽管 GCNGAE 基于不同的架构,但是它们可以组合使用。我们认为这是未来一个有希望的方向。

  3. 相似性度量:在 GAE 中已经采用了很多相似性度量,如:

    • 图自编码器:L2 重构损失、拉普拉斯特征图损失、ranking loss
    • 图变分自编码器:KL 距离、Wasserstein 距离。

    尽管这些相似性度量基于不同的动机,但是如何为特定的任务和模型体系结构选择合适的相似性度量仍然未被研究。需要更多的研究来了解这些度量指标之间的根本差异。

1.5 Graph RL

  1. 众所周知,强化学习 reinforcement learning:RL 善于从反馈中学习,尤其是在处理不可微的目标和约束时。这里我们回顾了 Graph RL 方法,如下表所示。

  2. GCPN 利用 RL 生成目标导向的 goal-directed 分子图,同时考虑了不可微的目标函数和约束。

    具体而言,它将图生成过程建模为添加节点和边的马尔可夫决策过程,并将生成模型视为在图生成环境中运行的 RL agent 。通过将 agent action 视为链接预测、使用 domain-specific 以及对抗性奖励、使用 GCN 来学习节点 representation,该方法可以使用策略梯度以端到端的方式训练 GCPN

  3. 同一时期的 MolGAN 采用了类似的思想,即使用 RL 生成分子图。但是, MolGAN 提出不要通过一系列 action 来生成图,而是直接生成完整的图。这种方法对于小分子特别有效。

  4. GTPN 采用 RL 预测化学反应产物。具体而言,该 agentaction 是选择分子图中的节点 pair 对,然后预测它们新的化学键的类型。根据预测是否正确,从而对 agent 进行实时奖励以及最终奖励。

    GTPN 使用 GCN 来学习节点 representation,以及一个 RNN 来记住 memorize 预测序列。

  5. GAM 通过使用随机游走将 RL 应用于图分类。作者将随机游走建模为部分可观测的马尔可夫决策过程 partially observable Markov decision process:POMDP

    agent 执行了两项操作:

    • 首先,它预测了图的标签。
    • 然后,它选择随机游走中的下一个节点。

    奖励的确定仅取决于 agent 是否对图进行了正确的分类:

    J(θ)=EP(S1:T;θ)t=1Trt

    其中:St 为环境;T 为总的时间步 time steprt=1 表示正确的预测,否则 rt=1

  6. DeepPathMINERVA 都是采用 RL 对知识图谱 knowledge graph: KG 进行推理。

    具体而言,DeepPath 的目标是寻找路径,即在两个目标节点之间找到信息量最大的路径;而 MINERVA 则处理问答任务,即在给定问题节点和关系的情况下找到正确的答案节点。

    这两种方法中,RL agent 都需要在每个 step 中预测路径中的下一个节点,并在 KG 中输出推理路径。如果路径正确地到达了目的地,则 agent 获得奖励。

    DeepPath 还添加了正则化项来鼓励路径多样性。

1.6 Graph Adversarial

  1. 这里我们介绍如何将对抗方法 adversarial method 应用到图,下表给出了图对抗方法的主要特点:

1.6.1 对抗训练

  1. GAN 的基本思想是建立两个相关联的模型:判别器 discriminator 和生成器 generator

    • 生成器的目标是通过生成假数据来 ”欺骗“ 判别器。
    • 判别器的目标是区分样本是来自于真实数据还是由生成器生成的。

    然后,两个模型通过使用 minmax game 进行联合训练而彼此受益。

    对抗训练已被证明在生成模型中有效,并提高了判别模型的泛化能力。在前文中,我们分别回顾了如何在 GAEGraph RL 中使用对抗训练方案,这里我们详细回顾了图上的其它几种对抗训练Adversarial Training方法。

  2. GraphGAN 提出使用 GAN 来提升具有以下目标函数的graph embedding 方法:

    minGmaxDi=1N(EvPgraph(vi)[logD(v,vi)]+EvG(vi)[log(1D(v,vi)))

    其中:

    • 判别器 D() 定义为:

      D(v,vi)=σ(dvdvi)

      dv 为节点 v 在判别器中的低维 embedding 向量。

    • 生成器 G() 定义:

      G(vvi)=exp(gvgvi)vviexp(gvgvi)

      gv 为节点 v 在生成器中的低维 embedding 向量。

    结合以上等式,判别器实际上有两个目标:原始图中的节点 pair 对应该具有较大的相似性,生成器生成的节点 pair 对应该具有较小的相似性。

    该架构和 graph embedding 方法(如 LINE)相似,除了negative node pair 是由生成器 G() 生成的而不是随机采样的之外。

    作者表明,该方法提升了节点 embedding 向量的 inference 能力。

  3. Adversarial network embedding:ANE 也采用对抗训练方案来改进网络 embedding 方法。

    类似 ARGAANEGAN 作为现有网络 embedding 方法(如 DeepWalk)的额外正则化项,通过将先验分布作为真实数据 real data 并将 embedding 向量视为生成样本。

  4. GraphSGAN 使用 GAN 来提升图的半监督学习。具体而言,作者观察到:应该在子图之间的稠密间隙density gap 中生成伪节点,从而削弱现有模型在不同 cluster 之间的传播效果。

    为实现该模型,作者设计了一个新的优化目标,该目标具有精心设计的损失项,从而确保生成器在稠密间隙中生成样本。

  5. NetGAN 为图生成任务采用了 GAN 。具体而言,作者将图生成视为一个学习有偏随机游走分布的任务,并采用 GAN 框架使用 LSTM 来生成和区分这些随机游走序列。

    实验表明,使用随机游走也可以学习全局网络模式。

1.6.2 对抗攻击

  1. 对抗攻击Adversarial attack是另一类对抗方法,旨在通过向数据添加较小的扰动来故意 “欺骗“ 目标方法。

    研究对抗攻击可以加深我们对现有模型的理解,并启发更强大的体系结构。

  2. Nettack 是首次提出通过修改图结构和节点属性来攻击节点分类模型(如 GCN)的方法。

    假设目标节点为 v0,其真实类别为 ctrue ,目标模型为 F(A,FV) ,损失函数为 LF(A,F(V)) , 则该模型使用以下目标函数:

    argmax(A,FV)PmaxcctruelogZv0,clogZv0,ctrues.t.Z=Fθ(A,FV),θ=argminθLF(A,FV)

    其中:

    • A,FV 为修改的邻接矩阵和节点特征矩阵。
    • Z 表示通过 F() 预测的节点类别概率矩阵。
    • Pattack 约束定义的空间。

    简而言之,优化的目标是在图结构和节点属性中找到最佳的合法修改,使得 v0 被错误地分类。

    θ 表示攻击是有因果关系的 causative ,即攻击是在训练目标模型之前发生的。

    作者还提出一些针对攻击的约束条件,最重要的约束条件是:攻击应该是 ”微小的“, 即应该仅仅进行很小的修改。具体而言,作者提出保留诸如节点 degree 分布和特征共现之类的数据特点。

    作者还提出了两种攻击方式:直接攻击direct attack (直接攻击 v0 )、影响力攻击 influence attack (仅攻击其它节点),并提出了几种放宽措施以便优化过程易于处理。

  3. 同一时期,《Adversarial attack on graph structured data》 研究了类似于 Nettack 的目标函数。但是,他们关注仅更改图结构的情况。他们并没有假设攻击者拥有所有信息,而是考虑了几种情况,每种情况提供了不同数量的信息。

    最有效的策略 RL-S2V 采用 structure2vec 来学习节点和图的 representation,并使用强化学习来解决优化问题。实验结果表明,这些攻击对于节点和图分类任务均有效。

  4. 前面提到的两种攻击都是针对性的,即它们旨在引起某些目标节点 v0 的错误分类。《Adversarial attacks on graph neural networks via meta learning》 率先研究了非目标攻击,这些攻击旨在降低整体模型的性能。

    他们将图结构视为要优化的超参数,并在优化过程中采用了元梯度meta-gradient ,同时还采用了几种逼近元梯度的技术。

1.7 讨论和总结

  1. 应用:除了诸如节点分类、图分类之类的标准的图 inference 任务之外,基于图的深度学习方法也应用于多种学科,包括建模社会影响力、推荐、化学和生物学等等。由于这些应用多种多样,对其进行彻底的回顾超出了本文的范围,但是我们列出了一些关键的灵感:

    • 首先,在构建图或者选择架构时,将领域知识纳入模型非常重要。

      例如,基于 relative distance 构建的图可能适用于交通预测问题,但可能不适用于地理位置也很重要的天气预报问题。

    • 其次,基于图的模型通常可以在其它体系结构之上构建,而不是作为独立模型构建。如

      例如,计算机视觉社区通常采用 CNN 来检测对象,然后将基于图的深度学习用作推理模块。

    这些应用还表明:基于图的深度学习不仅可以挖掘现有图数据背后的丰富价值,还有助于将关系型数据自然地建模为图,从而极大地扩展了基于图的深度学习模型的适用性。

  2. 未来方向:

    • 新模型用于未研究过的图结构:由于图数据的结构各种各样,因此现有方法不适合所有图结构。

      例如,大多数方法集中于同质图,很少研究异质图。

    • 现有模型的组合:可以集成很多现有架构,如将GCN 用作GAEGraph RL 中的一层。

      除了设计新的构建 block 之外,如何系统性地组合这些体系结构也是未来一个有趣的方向。

    • 动态图:现有大多数方法都关注于静态图,而实际上很多图本质上是动态的,图的节点、边、特征都可以随时间变化。

      例如社交网络中,人们可能建立新的社交关系、删除旧的社交关系,并且他们的特征(如兴趣爱好职业)会随着时间改变。新用户可以加入社交网络、现有用户也可以离开。

      如何对动态图的不断变化的特点进行建模,以及如何支持对模型参数的增量更新仍是悬而未决的。

    • 可解释性和鲁棒性:由于图通常和其它风险敏感 risk-sensitive 的场景相关,因此深度学习模型结果的可解释能力对于决策问题至关重要。

      例如,在医学或与疾病相关的问题中,可解释性对于将计算机实验转化为临床应用至关重要。

      但是,基于图的深度学习的可解释性甚至比其它黑盒模型更具挑战性,因为图的节点和边通常紧密相连。

      此外,正如对抗攻击所示,许多现有的图深度学习模型对于对抗攻击都很敏感,因此提升现有方法的鲁棒性是另一个重要问题。

二、GNN : A Review of Methods and Applications[2018]

  1. 摘要:很多学习任务需要处理包含元素之间丰富的关系信息的图数据。图神经网络 Graph Neural Networks:GNNs 是连接主义的模型connectionist model ,它通过图上节点之间的消息传递来捕获图的依赖关系。与标准的神经网络不同,图神经网络保留了一个状态,该状态能够代表来自任意深度的邻域的信息。尽管发现原始 GNN 难以训练得到一个不动点 fixed point ,但是网络体系结构、优化技术、并行计算的很多最新进展使得图神经网络能够成功地学习。

    近年来基于图神经网络的变体,如图卷积神经网络 Graph Convolutional Network: GCN、图注意力网络Graph Attention Network: GAT、图门控神经网络gated graph neural network: GGNN 已经在很多任务上展现了突破性的性能。

  2. 引言:图 Graph 是一种数据结构,可用于一组对象(节点)及其关系(边)进行建模。近年来,由于图的强大表示能力,图的分析和研究受到越来越多的关注。作为机器学习中唯一的非欧几何数据结构,图分析重点关注于节点分类、链接预测、聚类。图神经网络 Graph Neural Networks: GNN 是在图上执行的、基于深度学习的方法。由于 GNN 令人信服的性能和高解释性,GNN 最近已经成为一种广泛应用的图分析方法。

    采用 GNN 有以下的动机 motivation

    • GNN 第一个动机源于卷积神经网络 CNNCNN 可以提取多尺度局部空间特征,并将其组合以构建高度表达能力的 representation。这导致了几乎所有机器学习领域的突破,并开启了深度学习的新时代。

      随着我们对 CNN 和图的深入研究,我们发现 CNN 的关键特性:局部链接、权重共享、使用 multi-layer 。这些对于解决图领域的问题也非常重要,因为:

      • 图是最典型的局部连接结构。
      • 和传统的谱图理论 spectral graph theory 相比,共享权重降低了计算成本。
      • multi-layer 结构是处理层级模式 hierarchical pattern 的关键,它捕获了各种尺度的特征。

      但是,CNN 只能处理诸如图像(2D 网格)、文本(1D 序列)之类的常规欧氏空间的数据。一种直觉的想法是将 CNN 推广到图数据上。然而,很难在图上定义局部卷积操作和池化操作,这阻碍了 CNN 应用到非欧空间的图上。

    • GNN 第二个动机来自于 graph embeddinggraph embedding 学习图的节点、边或者子图subgraphrepresentatation 低维向量。

      在图分析领域,传统机器学习方法通常依赖于人工设计的特征,这种方式灵活性较差、成本很高。 结合表示学习 representation learning 思想以及 word embedding 的做法,DeepWalk 是第一种基于表示学习的 graph embedding 方法,它将 SkipGram 模型应用于图上生成的随机游走序列。类似的方法,如 node2vec,LINE, TADW 也取得了突破。

      但是,这些方法有两个严重不足:

      • 首先,编码器中的节点之间没有共享参数,这导致计算效率较低。因为这意味着参数数量随着节点数量线性增加。
      • 其次,直接 embedding 的方法缺少泛化能力,这意味着它们无法处理动态图,也无法泛化到新的图上。

    基于 CNNgraph embedding,人们提出了 GNN 来聚合图结构中的信息,从而可以对节点及其关联进行建模。

    论文 《Graph Neural Networks: A Review of Methods and Applications》 对现有的图神经网络模型进行详细的综述,并解释了 GNN 值得研究的根本原因:

    • 首先,像 CNN/RNN 这样的标准神经网络无法正确处理图输入,因为它们按照特定顺序堆叠了节点特征。但是,图的节点没有自然顺序 natural order。为了解决这个问题,GNN 分别在每个节点上传播,从而忽略了节点的输入顺序。即:GNN 的输出对于节点的输入顺序是不变的。

    • 其次,图的边表示两个节点的依赖关系。在标准神经网络中,依赖关系仅被视为节点的特征。但是,GNN 可以通过图结构进行传播,而不必将其用作特征的一部分。

    • 第三,推理reasoning 是高级人工智能的一个非常重要的研究课题,人脑的推理过程几乎是基于从日常经验中提取的图。标准的神经网络已经显示出通过学习数据的分布来生成合成的synthetic 图像和文档的能力,但是它们仍然无法从大型数据中学习 reasoning graph

      GNN 试图从诸如场景图片、故事文档之类的非结构化数据生成graph ,这可以作为进一步的高级人工智能的强大神经网络模型。

      最近,已经证明具有简单架构的、未经训练的 GNN 也可以很好地发挥作用。

    论文贡献:

    • 论文对现有的图神经网络模型进行了详细的回顾。作者介绍了原始模型、变体、以及若干个通用框架。作者研究了这一领域的各种模型,并提供了一个 unified representation 来展示不同模型中的不同 propagation 步骤。通过识别相应的 aggregatorupdater ,人们可以很容易地区分不同的模型。
    • 论文对应用进行了系统的分类,将应用分为结构性场景、非结构性场景和其他场景。在每个场景下,论文提出了几个主要的应用和相应方法。
    • 论文提出了未来研究的四个开放性问题。图神经网络存在 over-smoothingscaling 问题。目前还没有有效的方法来处理动态图以及非结构化的感官数据 non-structural sensory data 的建模。作者对每个问题进行了深入分析,并提出了未来的研究方向。

2.1 模型

2.1.1 GNN

  1. GNN 的概念第一次是在论文 《The graph neural network model》 中被提出,它用于处理图数据并扩展了现有的神经网络。

    GNN 的目标是:对于每个节点 vV ,学习一个状态嵌入 state embedding 向量 hvRs ,其中包含节点的输入特征以及邻域信息。 状态 embedding 进一步地可以用于产生节点 v 的输出向量 ovRdo ,如节点的 label 。其中 sembedding 维度,do 为输出向量维度。

  2. GNN 定义了两个函数:

    • 定义 f() 为一个可学习的函数,称作局部转移函数 local transition function 。它在所有节点之间共享,并根据每个节点的输入特征和邻域来更新节点状态向量。
    • 定义 g() 为一个可学习的函数,称作局部输出函数 local output function 。它也在所有节点之间共享,并根据每个节点的状态向量来计算节点输出。

    其中函数 f()g() 可以解释为前馈神经网络。

    根据这两个函数,则GNN 的更新方程为:

    hv=f(xvV,{xu,vE,(u,v)E},{xuV,uNv},{hu,uNv})ov=g(hv,xvV)

    其中:

    • xvV 为节点 v 的输入特征, xu,vE 为边 (u,v) 的输入特征。
    • {xu,vE,(u,v)E} 为节点 v 所有边的输入特征。
    • {xuV,uNv} 为节点 v 所有邻域节点的特征,Nv 为节点邻域集合。
    • {hu,uNv} 为节点 v 所有邻域节点的状态向量。
  3. HRN×s 为所有节点的状态向量组成的矩阵,称作状态矩阵;令 ORN×do 为所有节点的输出向量组成的矩阵,称作输出矩阵;令 XRN×da 为所有特征向量(包含边的特征、邻域特征)组成的矩阵,称作特征矩阵;令 XV 为所有节点的特征向量组成的矩阵,称作节点特征矩阵。其中 N 为节点数量。则上式转化为:

    H=F(H,X),O=G(H,XN)

    其中:

    • F(,) 被称作全局转移函数 global transition function,它是考虑图上所有节点的 f() 函数而来。
    • G(,) 被称作全局输出函数 global output function ,它是考虑图上所有节点的 g() 函数而来。
  4. 实际上 H 是公式 H=F(H,X) 中的不动点,并且仅当 F(,) 是一个收缩映射contraction map 才有定义。

    基于 Banach 不动点理论,GNN 使用以下经典的迭代方案来计算状态矩阵:

    H(t+1)=F(H(t),X)

    其中 H(t) 表示 H 的第 t 次迭代。对于任何初始化值 H(0),该迭代方程以指数形式快速收敛。

  5. 当得到 GNN 框架时,下一个问题是如何学习 f(),g() 的参数。

    基于监督信息,损失函数可以为:

    L=i=1Nll(ti,oi)

    其中:

    • Nl 为带标签的节点数量。
    • ti 为节点 vi 的标签经过one-hot之后的向量。
    • oi 为节点 vi 的输出向量。
    • l(,) 为单个样本的损失。

    然后我们基于梯度下降法按照以下步骤来进行学习:

    • 通过公式 hv=f() 迭代更新 T 轮从而得到近似的不动点: H(T)H

    • 然后从损失函数中计算权重 W 的梯度 WL

      Wf()g() 的参数。

    • 根据梯度来更新权重 WWWηWL

  6. 尽管实验结果表明 GNN 是用于对图结构数据建模的强大工具,但是原始GNN 仍然存在一些局限性:

    • 首先,迭代不动点从而更新节点状态的效率太低。如果放松不动点的假设,则我们可以设计一个多层 GNN 来获得节点及其邻域的 stable representation
    • 其次,GNN 在迭代 不动点过程中使用相同的参数。但是,流行的神经网络在不同的 layer 使用不同的参数,这是一种层次 hierarchical 特征提取方法。
    • 第三,边上存在一些信息特征,这些特征无法在原始 GNN 中有效建模。例如,异质图中包含不同类型的边,那么不同类型边的消息传播应该有所不同。
    • 最后,如果我们专注于节点的representation而不是图的representation,则不动点并不合适。因为不动点的representation 分布过于平滑,使得难以很好地区分不同的节点。

2.1.2 GNN 变体

  1. GNN 的变体有三类:基于图类型的变体 Graph Types、基于传播步骤的变体 Propagation Step、基于训练方法的变体 Training Methods。下图概括了这三类变体。

a. Graph Types
  1. 原始 GNN 中,输入图由带标签信息的节点以及无向边组成,这是最简单的图。下面我们介绍针对不同类型的图进行建模的方法。

  2. 有向图:有向边相比无向边可以带来更多的信息。在知识图谱中,边从 head entity 指向 tail entity ,表示 head entitytail entity 的父节点。这表明我们应该区别对待 head entity (父节点)和 tail entity (子结点)。

    DGP《Rethinking knowledge graph propagation for zero-shot learning》)使用两种权重矩阵 Wp,Wc 来获得更精确的结构信息,其传播规则为:

    H(l)=σ(Dp1Apσ(Dc1AcH(l1)Wc)Wp)

    其中:

    • H(t) 为第 l 层的representation 矩阵。

    • σ()sigmoid 函数。

    • Dp1Ap 为父节点的归一化邻接矩阵, Dc1Ac 为子结点的归一化邻接矩阵。

      其中 Ap 表示节点和其父节点的邻接矩阵,Ac 为节点和其子结点的邻接矩阵,且满足 Ap=Ac

    • Wp 为父节点的参数矩阵, Wc 为子结点的参数矩阵。

  3. 异质图:异质图存在多种类型的节点。

    • 处理异质图最简单的方法是将节点类型转换为 one-hot 向量,然后拼接这个 one-hot 向量到节点原始特征向量之后作为节点新的特征向量。
    • 此外,GraphInceptionmetapath 的概念引入到异质图传播过程中。通过 metapath,我们可以根据邻居节点的类型、邻居节点距当前节点的距离来对邻居节点进行分组。对于每个分组,GraphInception 将其视为同质图中的子图进行传播,并将不同分组的传播结果拼接起来作为邻域节点集合的 representation
    • 最近,heterogeneous graph attention network: HAT 提出利用node-level 注意力和 semantic-level 注意力来同时考虑节点重要性和 meta-path 重要性。
  4. 边信息:在图的另一类变体中,每条边都带有边信息,如边的权重或类型。对于带边信息的图,有两种处理方式:

    • 首先,可以将图转换为二部图,其中原始边变成节点(称作 edge node),并且一条原始边被拆分为两条新边。这意味着 edge node 分别和原始边的开始节点、结束节点都存在连接。

    • 其次,我们可以对不同类型的边上的传播使用不同的权重矩阵。在 G2S《Graph-to-sequence learning using gated graph neural networks》) 中,encoder 使用如下的聚合函数:

      hv(l)=ρ(1|Nv|uNvWr(rv(l)hu(l1))+br)

      其中:

      • hv(l) 为节点 v 在第 l 层的representation 向量。
      • ρ() 为非线性激活函数。
      • Nv 为节点 v 的邻域。
      • Wr,br 为不同边类型的权重(从而考虑边的类型信息)。
      • rv(l)reset gate

      当边的类型非常多时,R-GCN 引入了两种正则化来减少关系建模的参数数量:基分解 basis-decomposition、块对角分解 block-diagonal-decomposition

      • 对于基分解,每个 Wr 定义为:Wr=i=1Bar,bVb

        其中每个 Wr 是基转换权重 basis transformation Vb 的线性组合,组合的系数为 ar,b

      • 对于块对角分解,R-GCN 通过一组低维矩阵直接求和来定义每个 Wr 。和基分解相比,块对角分解需要更多的参数。

  5. 动态图:动态图具有静态图结构和动态输入信号。

    • 为捕获这两种信息,DCRNNSTGCN 首先通过 GNN 收集空间信息spatial information,然后将输出馈送到序列模型(如 sequence-to-sequence 或者 CNN ) 从而捕获时序信息 temporal information
    • 不同的是,Structure-RNNST-GCN 同时收集空间信息和时序信息。它们通过时序连接 temporal connnection 扩展了静态图结构,因此可以在扩展图上应用传统的 GNN
b. Propagation Step
  1. 在模型中,propagation stepoutput step 对于获取节点(或边)的 representation 至关重要。对于output step 而言,通常都采用和原始 GNN 相同的、简单的前馈神经网络。但是对于 propagation step,已经有很多种不同于原始 GNN 的修改,如下表所示。

    这些变体利用不同的聚合器 aggregator 从每个节点的邻域聚合消息,并使用不同的更新器 updater 来更新节点的 hidden state

  2. Convolution:近期卷积被应用到图领域,其中主要分为谱域卷积 spectral convolution 和空间卷积 spatial convolution

    谱域卷积使用图的谱域表示:

    • Spectral Network

      论文 《Spectral networks and locally connected networks on graphs》 提出了谱域网络 spectral network 。它通过对图的拉普拉斯算子执行特征分解eigendecomposition ,从而在傅里叶域 Fourier domain 定义卷积运算。

      定义图卷积算子 G 为:

      x1Gx2=U((Ux1)(Ux2))

      其中:

      • x1,x2RN 为定义在图 G 所有节点上的两个信号。每个信号在每个节点上都是一个标量(如,特征向量的某个维度)。
      • U 为图拉普拉斯矩阵 L 的特征向量 eigenvector 组成的矩阵 。
      • 图拉普拉斯矩阵 L=ID1/2AD1/2A 为邻接矩阵, D 为度矩阵。

      定义谱域卷积核为 K=diag(g(λ1),,g(λN))RN×N 为一个对角矩阵,其对角线元素为拉普拉斯矩阵 L 的特征值 eigenvalue λi 的函数 g(λi)。其中 g(λi) 包含可学习的参数。

      因此作用在输入信号 xRN 的卷积运算为:

      x=UKUx

      其中 x 为输出信号。

      这种卷积操作的计算复杂度太高,并且得到的滤波器是非空间局部化的 non-spatially localized 。因此,《Deep convolutional networks on graph-structured data》 试图通过引入具有平滑系数的参数来使得谱域滤波器在空域是局部化的。

    • ChebNet

      《Wavelets on graphs via spectral graph theory》 提出 g(λi) 可以通过一个截断的 K 阶切比雪夫多项式来近似。则有:

      x=UKUxk=0KθkTk(L~)x=k=0Kθkx~k

      其中:

      • L~=2λmaxLIλmaxL 的最大特征值。
      • θkk 阶切比雪夫多项式的系数。
      • Tk(x)k 阶切比雪夫多项式,x~k=Tk(L~)x

      根据切比雪夫多项式的递归定义,有:

      Tk(x)=2xTk1(x)Tk2(x)T0(x)=1,T1(x)=x

      因此有:

      x~k=2L~x~k1x~k2x~0=x,x~1=L~x

      可以看出该卷积操作是拉普拉斯矩阵的 K 阶多项式,因此它是 K 阶局部化的K-localized

      《Convolutional neural networks on graphs with fast localized spectral filtering》 提出了 ChebNet,它利用这种 K-localized 卷积运算来定义卷积神经网络,从而避免计算拉普拉斯矩阵的特征向量 eigenvector

    • GCN

      《Semi-supervised classification with graph convolutional networks》 通过限制 K=1,从而缓解在节点 degree 分布范围非常广的图中局部邻域结构上的过拟合问题。进一步地它假设 λmax=2,因此卷积操作简化为:

      x=UKUxk=01θkx~k=θ0x+θ1(LI)x=θ0xθ1D1/2AD1/2x

      其中包含两个参数 θ0,θ1

      为减少参数数量并令 θ=θ0=θ1 ,则有:

      x=UKUxθ(I+D1/2AD1/2)x

      注意,堆叠该卷积算子可能会导致数值不稳定性以及梯度消失、梯度爆炸。因此,GCN 引入 renormalization 技巧:

      I+D1/2AD1/2D~1/2A~D~1/2

      其中 A~=A+ID~=diag(D~1,,D~N),D~i=jA~i,j

      最终,GCN 将上述卷积算子推广到信号 XRN×C,其中包含 C 的输入通道(即 C 个输入信号),以及 F 个滤波器(即 F 个输出信号):

      Z=D~1/2A~D~1/2XΘ

      其中: ZRN×F 为卷积输出矩阵, ΘRC×F 为滤波器参数矩阵。

      这里的输入通道数量 C 就是节点的特征向量的维度。

    • 上述所有方法均使用原始图结构来表明节点之间的关系,然而不同节点之间可能存在隐式关系。为此, 《Adaptive graph convolutional neural networks》 提出了 Adaptive Graph Convolution Network:AGCN 来学习潜在关系。

      AGCN 学习一个残差 residual 图的拉普拉斯算子,并将该残差图的拉普拉斯算子添加到原始的图拉普拉斯算子中。结果在多个图数据集中证明了 AGCN的有效性。

    • 另外 《Bayesian semi-supervised learning with graph gaussian processes》 提出了一种基于高斯过程的贝叶斯方法 Gaussian process-based Bayesian approach:GGP 来解决半监督学习问题。它展示了 GGP 和谱域卷积方法之间的相似之处,这可能会从另一个角度为我们提供一些洞察。

    但是,上述所有谱域方法中,学习的滤波器都取决于拉普拉斯矩阵的特征根 eigenbasis ,而拉普拉斯特征根取决于图结构。即,在特定结构的图上训练的模型无法直接应用于具有不同结构的其它图上。

    空域卷积直接在图上定义卷积,并在空间上相邻的邻域上进行计算。空域方法的主要挑战是:为具有不同大小邻域的节点定义卷积运算,并保持CNN 的局部不变性。

    • Neural FPs

      《Convolutional networks on graphs for learning molecular fingerprints》 对不同 degree 的节点使用不同的权重矩阵:

      xv=hv(l1)+uNvhu(l1)hv(l)=σ(xvW(l,|Nv|))

      其中 W(l,|Nv|) 为第 l 层对应于degree|Nv| 的节点的权重矩阵。

      该方法的主要缺点是无法应用于节点 degree 范围很广的大型图。

    • DCNN

      《Diffusion-convolutional neural networks》 提出 diffusion-convolutional neural networks: DCNN ,它利用转移矩阵来定义节点邻域。对于节点分类问题,有:

      H=f(W(c)(P()X))

      其中:

      • XRN×F 为输入特征矩阵,F 为节点特征向量的维度。
      • P()RN×K×N 包含了转移矩阵 P 的一组幂次: {P,,PK}P=D1A 是归一化的转移概率矩阵, Pi,j 表示从节点 vi 经过一步转移到节点 vj 的概率。因此 Pk 中的 (Pk)i,j 表示节点 vi 经过 k 步转移到节点 vj 的概率。
      • W(c)RK×F 为权重矩阵。
      • HRN×K×F 为图上每个节点的 diffusion representation
      • σ() 为非线性激活函数, 为逐元素乘积。

      对于图分类任务,DCNN 简单地将节点的 representation 取平均:

      H=f(W(c)(1PX/N))

      其中 1=(1,1,,1N) 为全 1 的向量。

      DCNN 也可以用于边分类任务,只需要将边转换为节点并调整邻接矩阵即可。

    • DGCN

      《Dual graph convolutional networks for graph-based semi-supervised classification》 提出了 dual graph convolutional network:DGCN 来同时考虑图的局部一致性和全局一致性。它使用两个卷积网络来捕获局部一致性和全局一致性,并采用无监督损失来集成 ensemble 它们。

      • 第一个卷积网络和 GCN 相同: Z=D~1/2A~D~1/2XΘ

      • 第二个卷积网络使用 positive pointwise mutual information:PPMI 矩阵代替邻接矩阵:

        H=ρ(DP1/2XPDP1/2HΘ)

        其中:XPPPMI 矩阵, DPXPdegree 矩阵。

    • PATCHY-SAN

      PATCHY-SAN 模型为每个节点提取并归一化邻域,其中邻域刚好包含 k 个邻居节点。然后,归一化的邻域作为常规卷积运算的感受野 receptive field

    • LGCN

      LGCN 利用 CNN 作为聚合器。它对节点的邻域矩阵进行最大池化,并获取 top-k 个特征,然后应用一维卷积来计算 hidden representation

    • MoNet

      MoNet 推广了前面的几种技术。在流形 manifold 上的Geodesic CNN:GCNNAnisotropic CNN:ACNN 、在图上的 GCN,DCNN 都可以视为 MoNet 的特例。

    • GraphSAGE

      GraphSAGE 提出了一个通用的 inductive 框架,它通过对节点的局部邻域特征进行采样和聚合来生成节点 embedding

      hNv(l)=AGG(l)({hu(l1),uNv})hv(l)=σ(W(l)[hv(l1)||hNv(l)])

      其中 || 表示向量拼接。

      但是,GraphSAGE 并没有使用节点邻域中的所有节点来计算 hNv(l) ,而是通过均匀随机采样来获取固定大小的采样邻域。另外,GraphSAGE 采用了三种聚合函数:

      • 均值聚合:

        hv(l)=σ(W(l)MEAN({hv(l1)} {hu(l1),uNv}))

        均值聚合和其它两种聚合不同,因为它并没有将 hv(l1)hNv(l) 进行拼接的操作。它可以视为 skip connection 的一种形式,并可以实现更好的性能。

      • LSTM 聚合:AGG 使用表达能力很强的 LSTM 网络。但是,LSTM 处理序列数据,因此并不是排列不变的 permutation invariantLSTM 通过对节点邻域随机排序从而应用于无序的邻域集合。

      • 池化聚合:AGG 使用最大池化:

        hNv(l)=max({σ(Wpool(l)hu(l1)+bpool(l)),uNv}) 

        .

  3. Gate:有一些工作试图在传播step 中引入门控机制(类似于 GRU/LSTM),从而减少之前 GNN 模型中的缺陷,并改善信息在整个图结构中的 long-term 传播。

    • GGNN

      《Gated graph sequence neural networks》 提出了 gated graph neural network:GGNN ,它在传播阶段使用 Gate Recurrent Units:GRU ,展开 unroll 固定的 T 个递归步并通过 backpropagation through time:BPTT 计算梯度。

      具体而言,传播模型的基本递归 basic recurrence 公式为:

      av(t)=Av[h1(t1),,hN(t1)]+bzv(t)=σ(W(z)av(t)+U(z)hv(t1))rv(t)=σ(W(r)av(t)+U(r)hv(t1))hv(t)~=tanh(Wav(t)+U(rv(t)hv(t1)))hv(t)=(1zv(t))hv(t1)+zv(t)hv(t)~

      其中:av(t) 收集了节点 v 的邻域信息, zv(t) 为更新门update gaterv(t) 为恢复门 reset gate

      节点 v 首先聚合来自其邻域的消息,其中 Av 表示邻接矩阵 A 的子矩阵,表示节点 v 和它邻居的连接。类似于 GRU 的更新函数结合了来自其它节点的信息和上一个时间步的信息,从而更新每个节点的 hidden state

    • Tree-LSTM

      在基于树或图的传播过程中,LSTM 也以 GRU 相似的方式使用。《Improved semantic representations from tree-structured long short-term memory networks》 提出基于 LSTM 的两个扩展:Child-Sum Tree-LSTMN-ary Tree-LSTM

      类似于标准的 LSTM 单元,每个 Tree-LSTM 单元(由 v 索引)都包含输入门 input gate iv 、输出门 output gate ovmemmory cell cv 以及 hidden state hv 。但是,Tree-LSTM 单元对于每个 child k 包含一个遗忘门 forget gate fv,k ,而不是单个遗忘门,这使得单元可以有选择地融合每个 child 的信息。

      • Child-Sum Tree-LSTM 递归方程如下:

        hv(t1)~=kNvhk(t1)iv(t)=σ(W(i)xv(t)+U(i)hv(t1)~+b(i))fv,k(i)=σ(W(f)xv(t)+U(f)hk(t1)+b(f))ov(t)=σ(W(o)xv(t)+U(o)hv(t1)~+b(o))uv(t)=tanh(W(u)xv(t)+U(u)hv(t1)~+b(u))cv(t)=iv(t)uv(t)+kNvfv,k(t)ck(t1)hv(t)=ov(t)tanh(cv(t))

        其中 xv(t) 为标准 LSTM 中时刻 t 的输入向量。

        这里的 LSTM 作用的是节点的状态序列,而 GraphSAGE 中的 LSTM 作用的是节点的邻域。

      • 如果树的分支因子最多为 K ,并且节点的所有子节点均已排序,即它们可以从 1,...,K 进行索引,则可以使用 N-ary Tree-LSTM

        对于节点 vhv,k(t),cv,k(t) 表示它的第 kchid 在时刻 thidden statememory cellN-ary Tree-LSTM 的递归方程如下:

        iv(t)=σ(W(i)xv(t)+l=1KUl(i)hv,l(t1)+b(i))fv,k(t)=σ(W(f)xv(t)+l=1KUk,l(f)hv,l(t1)+b(f))ov(t)=σ(W(o)xv(t)+l=1KUl(o)hv,l(t1)+b(o))uv(t)=tanh(W(u)xv(t)+l=1KUl(u)hv,l(t1)+b(u))cv(t)=iv(t)uv(t)+l=1Kfv,l(t)cv,l(t1)hv(t)=ov(t)tanh(cv(t))

        Child-Sum Tree-LSTM 相比, N-ary Tree-LSTM 为每个 child k 引入单独的参数矩阵,使得模型可以学习更多关于每个单元的 child 的细粒度表示。

        这两种类型的 Tree-LSTM 可以轻松地应用于图。

    • Graph LSTM

      • 《Conversation modeling on reddit using a graph-structured lstm》 中的 graph-structured LSTMN-ary Tree-LSTM 应用于图上的例子。

        但是它是简化版本,因为图中的每个节点最多具有 2 个入边 incoming edge (从它的父亲parent 以及同辈的前驱 sibling predecessor )。

      • 《Cross-sentence n-ary relation extraction with graph lstms》 基于关系抽取任务提出了 Graph LSTM 的另一种变体。

        图和树之间的主要区别在于图的边具有标签 label ,因此该论文使用不同的权重矩阵来表示不同label 的边:

        iv(t)=σ(W(i)xv(t)+kNvUm(v,k)(i)hk(t1)+b(i))fv,k(t)=σ(W(f)xv(t)+Um(v,k)(f)hk(t1)+b(f))ov(t)=σ(W(o)xv(t)+kNvUm(v,k)(o)hk(t1)+b(o))uv(t)=tanh(W(u)xv(t)+kNvUm(v,k)(u)hk(t1)+b(u))cv(t)=iv(t)uv(t)+kNvfv,k(t)ck(t1)hv(t)=ov(t)tanh(cv(t))

        其中 m(v,k) 表示节点 v 和节点 k 之间的边标签 edge label

      • 《Sentence-state lstm for text representation》 提出了用于改进text encodingSentence LSTM:S-LSTM 。它将文本转换为图,并利用 Graph LSTM 来学习 representationS-LSTM 在很多 NLP 问题中展现出强大的表示能力。

      • 《Semantic object parsing with graph lstm》 提出了一种 Graph LSTM 网络来解决语义对象解析任务 semantic object parsing task 。它使用置信度驱动方案 confidence-driven scheme 来自适应地选择开始节点并决定节点更新顺序。它遵循相同的思想来推广 LSTM 到图结构数据上,但是具有特定的更新顺序。而我们上述提到的方法和节点的顺序无关。

  4. Attention:注意力机制已经成功地应用于很多 sequence-based 任务,例如机器翻译、机器阅读等。

    • 《Graph attention networks》 提出了 graph attention network: GAT 从而将注意力机制融合到传播步骤。它采用 self-attention 机制,通过关注节点的邻域来计算节点的 hidden state

      GAT 定义一个 graph attention layer,并通过堆叠多个 graph attention layer 来构建 graph attention network 。该层通过以下方式计算节点 pair(i,j) 在注意力机制中的注意力系数:

      αi,j=exp(LeakyReLU(a[Whi||Whj]))kNiexp(LeakyReLU(a[Whi||Whk]))

      其中:

      • graph attention layer 的输入为节点的特征集合 {h1,,hN} ,其中 hiRFF 为特征维度, N 为节点数量。

      • graph attention layer 的输出为节点的新的特征集合 {h1,,hN} ,其中 hiRFF 为新的特征维度。其中:

        hi=σ(jNiαi,jWhj)

        σ() 非非线性激活函数。

      • WRF×F 为权重矩阵,它在所有节点之间共享。

      • aR2F 为单层 feedforward neural network 的权重。

      • || 为向量拼接。

      • αi,j 为节点 j 对于节点 iattention 系数。它满足:jNiαi,j=1.0,0<αi,j<1.0

      此外,GAT 利用 multi-head attention 来稳定学习过程。它使用 K 个独立的注意力机制来计算 hidden state,然后将这 Khidden state 拼接起来(或均值聚合),从而得到以下两种形式的 representation

      hi=||k=1Kσ(jNiαi,j(k)W(k)hj(k))hi=σ(1Kk=1KjNiαi,j(k)W(k)hj(k))

      其中 αi,j(k) 为第 kattention计算到的注意力系数。

      GAT 的注意力架构具有几个特点:

      • 节点-邻居 pair 对的计算是可并行的,因此计算效率很高。
      • 通过为邻域指定不同的权重,因此可以应用于不同 degree 的节点。
      • 可以轻松地应用于 inductive learning
    • GANN:除了 GAT 之外,Gated Attention Network:GAAN 也是用 multi-head 注意力机制。但是,它使用 self-attention 机制从不同的 head 收集信息,而不是像 GAT 那样拼接或者取平均。即每个 head 的重要性不同。

  5. Skip connection:很多应用application 会堆叠多层神经网络从而预期获得更好的结果。因为更多的层,比如 K 层,可以使得每个节点从其 K 阶邻域中收集到更多的信息。但是,很多实验发现更深层的模型无法提高性能甚至表现更差。这主要是因为更深的层也可以指数级地传播噪音信息。

    可以从计算机视觉社区找到一种直接的解决方案,即残差网络 residual network 。但是,即便使用残差连接,在很多数据集上具有多层的 GCN 的性能也不如 2GCN 更好。

    • Highway GCN

      《Semi-supervised user geolocation via graph convolutional networks》 提出 Highway GCN ,它使用类似于 highway networkslayer-wise gatelayer 的输出和layer 的输入加权累加,权重由门控给出:

      T(h(t))=σ(W(t)h(t)+b(t))h(t+1)h(t+1)T(h(t))+h(t)(1T(h(t)))

      通过增加 higthway gate4层的 Higthway GCN 在某些特定问题上性能最佳。

      论文 《Column networks for collective classification》 提出的 Column Network:CLN 也使用 highway network,但是它使用不同的函数来计算门控权重。

    • JK-Net

      《Representation learning on graphs with jumping knowledge networks》 研究了邻域聚合方案的特点以及邻域聚合导致的缺陷。该论文提出了 Jump Knowledge Network:JK-Net,它可以学习自适应adaptive 的 、结构感知structure-awarerepresentation`。

      JK-Net 将节点的每一层中间 representation 跳跃到最后一层,并在最后一层对这些中间 representation 进行自适应地选择,从而使得模型可以根据需要自适应地调整每个节点的有效邻域大小。

      JK-Net 在实验中使用了三种聚合方式来聚合信息:拼接、最大池化、LSTM-attention 。它也可以和 Graph Convolutional Network, GraphSAGE, Graph Attention Network 等模型结合,从而提升后者的性能。

  6. Hierarchical Pooling:在计算机视觉领域,卷积层之后通常跟着池化层从而获得更加泛化的特征。和视觉领域的池化层相似,有很多工作集中在图上的层次池化层 hierarchical pooling layer 。复杂的大型图通常带有丰富的层次结构,这对于 node-levelgraph-level任务非常重要。

    • 为了探索这种内部特征 inner featuresEdge-Conditioned Convolution:ECC 设计了具有递归下采样操作的池化模块。下采样方法通过拉普拉斯矩阵的最大特征向量的符号将图划分为两个分量。

    • DIFFPOOL 通过对每一层训练一个 assignment 矩阵,从而提出了一个可学习的层次聚类模块:

      S(l)=softmax(GNNl,pool(A(l),X(l)))

      其中: X(l) 为节点在 lfeature 矩阵, A(l) 为第 l 层的粗化邻接矩阵 coarsened adjacency matrix

c. Training Methods
  1. 原始的图卷积神经网络在训练和优化方法上存在缺陷:

    • 首先,GCN 需要完整的图拉普拉斯算子,这对于大型图来讲计算量太大。
    • 其次,在第 L 层单个节点计算 embedding 时需要该节点邻域所有节点在第 L1 层的 embedding 。因此,单个节点的感受野相对于层数呈指数型增长,因此计算单个节点的梯度的代价很大。
    • 最后,GCN 针对给定的图训练,这缺乏 inductive learning 能力。
  2. Sampling

    • GraphSAGEGraphSAGE 是原始 GCN 的全面改进。为解决上述问题,GraphSAGE 用可学习的聚合函数替换了完整的图拉普拉斯算子,这是执行消息传递和泛化到未见过节点的关键:

      hNv(l)=AGG(l)({hu(l1),uNv})hv(l)=σ(W(l)[hv(l1)||hNv(l)])

      GraphSAGE 首先聚合邻域 embedding,然后和目标节点的 embedding 拼接,最后传播到下一层。

      通过可学习的邻域聚合函数和消息传播函数,GraphSAGE 可以泛化到未见过的节点。

      此外,GraphSAGE 使用邻域采样来缓解感受野的扩张 expansion

    • PinSagePinSage 提出了基于重要性的采样方法。通过模拟从目标节点开始的随机游走,该方法选择了归一化访问次数 top T 个节点。

    • FastGCNFastGCN 进一步改善了采样算法。FastGCN 不会为每个节点采样邻居,而是直接为每层采样整个感受野。

      FastGCN 也使用重要性采样,但是其重要性因子为:

      q(v)1|Nv|uNv1|Nu|
    • 和上面固定的采样方法相反,论文 《Adaptive sampling towards fast graph representation learning》 引入了一个参数化、且可训练的采样器来执行以前一层为条件的逐层采样。此外,该自适应采样器可以找到最佳采样重要性并同时减少采样方差。

    • SSE:遵循强化学习,论文 《Learning steady-states of iterative algorithms over graphs》 提出SSE,它采用 Stochastic Fixed-Point Gradient Descent 用于 GNN 的训练。

      该方法将 embedding 更新视为值函数 value function。在训练期间,该算法将对节点进行采样以更新 embedding, 对标记节点采样以更新参数,二者交替进行。

  3. Receptive Field Control《Stochastic training of graph convolutional networks with variance reduction》 通过利用节点的历史激活作为控制变量control variate ,提出了一种基于控制变量的 GCN 随机近似算法。该方法限制了一阶邻域中的感受野,但使用历史 hidden state 从而作为一个可接受的近似值。

  4. Data Augmentation《Deeper insights into graph convolutional networks for semi-supervised learning》 聚焦于 GCN 的局限性,其中包括 GCN 需要许多额外的标记数据用于验证集,并且还遭受卷积滤波器的局部性。为解决这些限制,作者提出了 Co-Training GCN 以及 Self-Training GCN 来扩大训练集。前者寻找训练标记样本的最近邻居,后者遵循类似 boosting 的方法。

  5. Unsupervised trainingGNN 通常用于监督学习或半监督学习,最近有一种趋势是将自编码器 auto-encoder:AE 扩展到图领域。图自编码器旨在通过无监督学习获取节点的低维 representation

    • GAE

      论文 《Variational graph auto-encoders》 提出了Graph Auto-Encoder: GAEGAE 是首次使用 GCN 对图中的节点进行编码,然后它使用简单的解码器重构邻接矩阵,并根据原始邻接矩阵和重构邻接矩阵之间的相似度来评估损失:

      Z=GCN(X,A)A~=ρ(ZZ)

      论文也以变分的方式训练 GAE 模型,称作变分图自编码器variational graph autoencoder:VGAE

      此外,graph convolutional matrix completion:GC-MC 也使用 GAE 并应用于推荐系统中。在 MovieLens 数据集上,GC-MC 性能优于其它 baseline 模型。

    • ARGA

      Adversarially Regularized Graph Auto-encoder:ARGA 使用生成对抗网络 generative adversarial network:GAN 来正则化 GCN-basedGAE 从而遵循先验分布。

    • 也有几种图自编码器,例如 NetRA, DNGR, SDNE, DRNE,但是它们的架构中未使用 GNN

2.2 通用框架

  1. 除了图神经网络的不同变体之外,人们还提出了一些通用框架,旨在将不同的模型整合到一个框架中。

    • 《Neural message passing for quantum chemistry》 提出了消息传递神经网络 message passing neural network: MPNN ,它统一了各种图神经网络和图卷积网络方法。
    • 《Non-local neural networks》 提出了非局部神经网络 non-local neural network: NLNN ,它统一了集中 self-attention 风格的方法。
    • 《Relational inductive biases, deep learning, and graph networks》 提出了一种图网络 graph network: GN,它统一了 MPNNNLNN 以及许多其它变体,例如 Interaction NetworkNeural Physics EngineCommNetstructure2veGGNNRelation NetworkDeep SetsPoint Net

2.2.1 MPNN

  1. MPNN 框架总结了几种最流行的图模型之间的共性,如graph convolution network, gated graph neural network, interaction network, molecular graph convolution, deep tensor neural network 等等。

  2. MPNN 包含两个阶段:消息传递阶段、readout 阶段 。

    • 消息传递阶段(也称作传播阶段)执行 T 个时间步,并根据消息函数 Mt 和节点更新函数 Ut 来定义。

      令节点 v 在时刻 t 收到的消息为 mv(t) ,在时刻 thidden statehv(t) ,则有:

      mv(t+1)=wNvMt(hv(t),hw(t),ev,w)hv(t+1)=Ut(hv(t),mv(t+1))

      其中 ev,w 为节点 v,w 之间边的特征。

    • readout 阶段使用 Readout 函数 R() 来计算整个图的特征向量:

      y^=R({hv(T)vV})

      其中 T 表示总的时间步。

  3. 消息函数 Mt 、节点更新函数 Utreadout 函数 R 可以有不同的设置,因此 MPNN 框架可以通过不同的配置来概括几种不同的模型。

    这里我们以 GGNN 为例,其它模型的示例参考原始论文。针对 GGNN 模型的函数配置为:

    Mt(hv(t),hw(t),ev,w)=Aev,whw(t)Ut(hv(t),mv(t+1))=GRU(hv(t),mv(t+1))R({hv(T)vV})=vVσ(Fi(hv(T),hv(0)))(Fj(hv(T)))

    其中:

    • Aev,w 为邻接矩阵,对于每一个edge label 采用不同的邻接矩阵。
    • GRUGated Recurrent Unit
    • Fi(,),Fj()R 中的神经网络, 为逐元素乘法。

2.2.2 NLNN

  1. NLNN 用户捕获深度神经网络的长程依赖。

    non-local 操作是计算机视觉中经典的 non-local 均值操作的推广。non-local 操作将某个位置的 response 计算为所有位置的特征的加权和,位置可以为空间位置、时间位置、或者时空位置。因此,NLNN可以视为不同的 self-attention 方式的统一。

  2. 我们首先介绍 non-local 操作的一般定义。遵从 non-local 均值操作,推广的 non-local 操作定义为:

    hi=1Ci(H)jf(hi,hj)×g(hj)

    其中:

    • i 为输出位置索引, j 遍历所有可能的输入位置索引。
    • f(hi,hj)R 是位置 i 和位置 j 之间的一个标量函数,表示它们之间的关系。
    • g(hj) 表示输入 hj 的变换,并使用因子 1Ci(H) 来归一化结果。
    • H 为所有 hj 拼接而成的向量,Ci(H) 表示针对输出 i 的归一化分母。

    有几种不同的 f(,)g() 的配置,为简单起见 NLNN 使用线性变换作为 g() 函数。这意味着 g(hj)=Wghj ,其中 Wg 为可学习的权重矩阵。接下来我们讨论 f(,) 函数的选择。

  3. 高斯Gaussian 函数:高斯函数是根据非局部均值 non-local mean (论文 《A non-local algorithm for image denoising》)和双边滤波器 bilateral filter (论文 《Bilateral filtering for gray and color images》)的自然选择:

    f(hi,hj)=exp(hihj)

    其中, hihj 是点积相似性 dot-product similarity 。并且:

    Ci(H)=jf(hi,hj)
  4. Embedded Gaussian 函数:很自然地通过计算 embedding 空间中的相似性来扩展高斯函数。即:

    f(hi,hj)=exp(θ(hi)ϕ(hj))

    其中:

    θ(hi)=Wθhi,ϕ(hj)=Wϕhj,Ci(H)=jf(hi,hj)

    可以发现 《Attention is all you need》 提出的 self-attentionEmbedded Gaussian 函数的特例。对于给定的 i1Ci(H)jf(hi,hj) 成为沿着维度 jsoftmax。因此有:

    h=softmax(HWθWϕH)g(H)

    这就是 self-attention 的形式。

  5. 点积函数: f(,) 可以是简单的点积相似性 dot-product similarity,即:

    f(hi,hj)=θ(hi)ϕ(hj)

    其中:

    θ(hi)=Wθhi,ϕ(hj)=Wϕhj,Ci(H)=N

    其中 N 为节点数量。

  6. 拼接函数: f(,) 可以为简单的向量拼接:

    f(hi,hj)=ReLU(wf[θ(hi)||ϕ(hj)])

    其中: wf 是一个权重向量, Ci(H)=NN 为节点数量。

  7. NLNN 将上述 non-local 操作包装到一个 non-local block 中:

    zi=Wzhi+hihi=1Ci(H)jf(hi,hj)g(hj)

    其中 +hi 为残差连接。因此,non-local block 可以插入任何预训练模型 pre-trained model 中,这使得该 block 适用性更好。

2.2.3 GN

  1. Graph Network:GN 框架概括并扩展了各种图神经网络、MPNN 、以及 NLNN 方法。我们首先介绍图的定义,然后描述 GN 块、GN 核心计算单元、计算步骤。

  2. GN 框架内,图被定义为三元组 G=(u,V,E) ,其中:

    • u 为全局属性,比如它代表全局的万有引力场。
    • V={vi}i=1Nv 代表节点属性的集合, Nv 为节点数量, vi 为节点 i 的属性向量。
    • E={(ek,rk,sk)}k=1Ne 为边的集合, Ne 为边数量, ek 为边的属性, rkreceiver 节点, sksender 节点。
  3. 一个 GN 块包含三个更新函数 ϕ,以及三个聚合函数 ρ

    ek=ϕ(e)(ek,vrk,vsk,u)e¯i=ρ(ev)(Ei)vi=ϕ(v)(e¯i,vi,u)e¯=ρ(eu)(E)u=ϕ(u)(e¯,v¯,u)v¯=ρ(vu)(V)

    其中:

    Ei={(ek,rk,sk)}rk=i,k=1,,Ne,E={(ek,rk,sk)}k=1,,Ne,V={vi}i=1,,Nv

    其物理意义为:

    • ϕ(e) 根据每条边的属性 ek、全局属性 u、以及 sender 节点属性 vskreceiver节点属性 vrk来更新对应边的属性 ek
    • ϕ(v) 根据每个节点的属性 vi、全局属性 u、以及 receiver为当前节点的所有边的属性(更新后的边属性)的聚合值 e¯i 来更新对应节点的属性 vi
    • ϕ(u) 根据全局属性 u、所有节点的属性(更新后)的聚合值 v¯ 、全局属性、所有边的属性(更新后)的聚合值 e¯ 来更新全局属性 u 。它仅更新一次。
    • 每个 ρ 函数使用一个集合作为输入,然后聚合为单个结果代表聚合后的信息。最重要的是:ρ 函数必须是排列无关的 permutation invariant,并且应该采用可变数量的自变量。一些典型的例子包括:逐元素求和、均值池化、最大值池化等。

    ϕ()ρ() 函数不一定是神经网络,但是本文中我们仅关注神经网络的实现。

  4. GN 块的计算步骤:

    • 通过执行 ϕ(e)(ek,vrk,vsk,u) 得到每条边更新后的属性 ek

      • 更新后,边的集合为 E={(ek,rk,sk)}k=1,,Ne
      • 更新后,节点 i 相关的边的集合为 Ei={(ek,rk,sk)}rk=i,k=1,,Ne 。这里节点 ireceiver
    • 执行 e¯i=ρ(ev)(Ei) 从而得到每个节点对应边的聚合信息。

    • 通过执行 vi=ϕ(v)(e¯i,vi,u) 得到每个节点更新后的属性。

      更新后,所有节点的属性集合为 V={vi}i=1,,Nv

    • 通过执行 e¯=ρ(eu)(E) 对所有边进行聚合得到 e¯

    • 通过执行 v¯=ρ(vu)(V) 对所有节点进行聚合得到 v¯

    • 通过执行 u=ϕ(u)(e¯,v¯,u) 来更新图的全局属性。

    尽管这里我们给出了计算步骤的顺序,但是并不是严格地根据这个顺序来执行。例如,可以先更新全局属性、再更新节点属性、最后更新边属性。

  5. 设计原则:Graph Network 的设计基于三个基本原则:灵活的representation、可配置的块内结构 within-block structure 、可组合的多块架构 multi-block architecture

    • 灵活的representationGN 框架支持属性的灵活representation,以及不同的 graph 结构。

      • 全局属性、节点属性和边属性可以使用任意的表示格式,但实值向量和张量是最常见的。
      • graph 结构而言,GN 框架既可以应用于图结构明确的结构性场景,也可以应用于需要推断关系结构 relational structure 的非结构性场景。
    • 可配置的块内结构:一个 GN 块内的函数及其输入可以有不同的设置,因此 GN 框架在块内结构配置方面提供了灵活性。基于不同的结构和函数设置,各种模型(如 MPNNNLNN和其他变体)都可以由GN 框架表达。

    • 可组合的多块架构:GN 块可以被组合从而构建复杂的架构。任意数量的GN 块可以用共享参数或不共享参数的方式来堆叠式地组合。也可以采用一些其他技术来构建 GN-based 架构,如 skip connectionLSTM-style 门控机制、GRU-style 门控机制,等等。

2.3 应用

  1. 图神经网络已经在监督学习、半监督学习、无监督学习、强化学习等领域广泛应用。这里我们将应用分为三类:

    • 数据具有明确关系结构的结构性场景,如物理系统 physical system 、分子结构molecular structure 、知识图谱knowledge graph
    • 关系结构不明确的非结构性场景,包括图像image 、文本text 等。
    • 其它应用场景,如生成模型generative model、组合优化问题combinatorial optimization problem

    下表给出这些场景的一个总结:

2.3.1 结构化的场景

  1. 物理学:对现实世界的物理系统进行建模是理解人类智能的最基本方面之一。通过将物体表示为节点,将关系表示为边,我们可以用一种简化但有效的方式对物体、关系和物理学进行 GNN-based 的推理。

  2. 分子学和生物学:

    • 分子指纹 molecular fingerprint 计算:分子指纹是一个代表分子的特征向量,主要用于计算机辅助药物设计。传统的分子指纹是手工制作和固定的,通过将 GNN 应用于分子图,我们可以获得更好的分子指纹。
    • 蛋白质交互预测:蛋白质交互预测任务是一个具有挑战性的问题,在药物发现和设计中有着重要的应用。
  3. 知识图谱:《Knowledge transfer for out-of-knowledge-base entities : A graph neural network approach》 使用 GNN ,从而在 knowledge base completion: KBC 中解决 out-of-knowledge-base: OOKB 实体问题。

    《Cross-lingual knowledge graph alignment via graph convolutional networks》 使用 GCN 解决跨语言的知识图谱 knowledge graph 的对齐问题。

2.3.2 非结构化的场景

  1. 图像:

    • 分类任务:几项工作利用图神经网络在图像分类中纳入结构的信息。

      • 首先,知识图谱可以作为额外的信息来指导 zero-shot 分类。
      • 其次, 除了知识图谱之外,数据集中的图像之间的相似性也有助于few-shot learning
    • 视觉推理任务:计算机视觉系统通常需要通过纳入空间信息和语义信息来进行推理。因此,为推理任务生成 graph 是很自然的。一个典型的视觉推理任务是视觉问题回答 visual question answering: VQA 。视觉推理的其他应用包括目标检测、交互检测和区域分类。

    • 语义分割:语义分割任务是为图像中的每一个像素分配一个标签(或类别)。然而,分割区域 region 往往不是 grid-like 并且需要 non-local 信息,这导致了传统 CNN的失败。一些工作利用了图结构数据来处理该任务。

  2. 文本:

    • 文本分类: 有一些工作把文档或句子看作是一个由 word 节点组成的图,还有一些工作依靠文档引用关系来构建图,还有一些工作将文档和词视为构建语料库 graph 的节点(因此是异质图)。
    • 序列标注:由于 GNN中的每个节点都有其隐状态 hidden state ,如果我们把句子中的每个词都看作是一个节点,我们就可以利用隐状态来解决序列标注问题。
    • 神经机器翻译neural machine translation: NMTGNN 的一个流行应用是将句法信息或语义信息纳入神经机器翻译任务中。

2.3.3 其它场景

  1. 生成式模型:现实世界的图的生成模型因其重要的应用而引起了极大的关注,包括建模社交互动、发现新的化学结构、以及构建知识图谱。由于深度学习方法具有学习图的隐含分布的强大能力,最近神经图生成模型neural graph generative model 出现了一个高潮。
  2. 组合优化 combinatorial optimization:图上的组合优化问题是一组 NP-hard 问题,吸引了所有领域的科学家的关注。一些具体的问题,如旅行推销员问题(traveling salesman problem: TSP )和最小生成树(minimum spanning tree: MST),已经得到了各种启发式的解决方案。最近,使用深度神经网络来解决这类问题成为一个热点,其中一些解决方案由于其图结构而进一步利用了图神经网络。

2.4 悬而未决的问题

  1. 尽管 GNN 在不同领域取得了重大成功,但是 GNN 仍然还有一些尚未解决的问题:

    • 浅层结构Shallow Structure:传统的深度神经网络可以堆叠数百层从而获得更好的性能,因为更深的结构具有更多的参数从而显著提高表达能力。但是图神经网络总是很浅,大多数不超过三层。

      实验表明,堆叠多个 GCN层将导致过度平滑,即所有节点都收敛到相同的值。尽管一些研究人员设法解决了该问题,但是它仍然是GNN 的最大局限。

    • 动态图 Dymaic Graph:另一个挑战是如何处理具有动态结构的图。

      静态图是稳定的,因此可以对其进行建模。而动态图引入了变化的结构,当边或节点出现或消失时,GNN无法自适应地调整。

    • 非结构化场景Non-Structural Scenario:没有很好的方法从原始的、非结构的数据生成图结构。如果找到最佳的图构建方法,则可以使得 GNN 应用范围更广。

    • 可扩展性ScalabilityGNN 的扩展很困难,因为许多关键步骤在大规模数据下消耗大量的计算资源。例如:

      • 图数据不是规则的欧几里得结构,每个节点都有自己的邻域结构,因此无法进行 batch 处理。
      • 当有数百万个节点、边时,计算图拉普拉斯算子是不可行的。

      此外,我们必须指出:可扩展性决定了算法能否应用于实际工作中。

三、A Comprehensive Survey On GNN[2019]

  1. 最近神经网络的成功推动了模式识别和数据挖掘的发展。很多机器学习任务,如目标检测、机器翻译、语音识别任务,它们曾经高度依赖于手工特征工程 handcrafted feature engineering 来抽取特征,但是这些任务最近被各种端到端的深度学习范式所变革,如卷积神经网络CNN、递归神经网络 RNN、自编码器 autoencoder

    深度学习在许多领域的成功部分归因于快速发展的计算资源(如 GPU)、大量可用的训练数据、以及深度学习从欧几里得数据(如图像、文本、视频)中抽取潜在 representation 的有效性。以图像数据为例,我们可以将图像表示为欧几里得空间中的规则网格,而卷积神经网络CNN 能够利用图像数据的平移不变性shift-invariance 、局部连通性local connectivity 、以及组合性 compositionality 。结果,CNN 可以抽取在整个数据集上共享的、局部的、有意义的特征,从而进行各种图像分析。

    虽然深度学习有效地捕获了欧几里得数据的隐藏模式,但是越来越多的应用application 以图graph 的形式表示数据。例如:电商领域中基于图的学习系统可以利用用户和商品之间的交互来提高推荐准确性;化学领域中分子被建模为图,并需要确定其生物活性以进行药物发现。图数据的复杂性对现有的机器学习算法提出了重大挑战:

    • 由于图可能是不规则的,因此图可能包含可变数量的无序节点。而且,图中的节点可能具有不同数量的邻居,从而导致一些在图像领域很容易实施的重要的操作(如卷积)很难应用于图领域。
    • 此外,现有机器学习算法的核心假设是样本彼此独立。该假设在图数据上不再成立,因为图数据中每个节点通过各种类型的链接(如引用、好友、交互)和其它节点相关联。

    最近越来越多的人关注将深度学习方法扩展到图数据上。受深度学习的 CNN、RNN、autoencoder 等技术的推动,过去几年中一些关键算子的新的推广、新的定义快速发展,从而能够处理图数据的复杂性。例如,可以从 2D 卷积中推广出图卷积。如下图所述,可以将图像视为特殊的、相邻像素连接的图。和 2D 卷积类似,可以通过获取节点邻域信息的加权均值来执行图卷积。

    • (a):一个 2D 卷积。图像中每个像素视为一个节点,其中邻域由卷积核确定。2D 卷积采用红色节点及其邻域像素的像素值的加权平均,节点的邻域是有序的、固定大小的。

      加权平均的权重由卷积核来指定。

    • (b):一个图卷积。为获得红色节点的 hidden representation,一种简单的图卷积运算是获取红色节点及其相邻节点的 representation 均值。和图像数据不同,节点的邻域是无序的、大小可变的。

    目前有关图神经网络 GNNreview 的数量有限,论文 《A Comprehensive Survey on Graph Neural Networks》 给出了一份 GNN 的全面综述。具体而言:

    • 作者提出了新的分类方法,将图神经网络划分为四类:递归图神经网络recurrent graph neural network:RecGNN、卷积图神经网络convolutional graph neural network:ConvGNN、图自编码器 graph autoencoder:GAE、时空图神经网络spatial-temporal graph neural network:STGNN

      对于每种类型的图神经网络,作者提供有关代表性模型的详细说明、必要的比较、并总结相应的算法。

    • 作者收集了大量资源,包括 SOTA模型、benchmark 数据集、开源代码、实际应用。作者指出:该综述可以用于了解、使用、开发各种现实应用的不同的图深度学习方法的指南 hands-on guide

    • 最后作者探讨了图神经网络的理论方面,分析了现有方法的局限性,并就模型深度model depth 、可扩展性scalability 、异构性heterogeneity 、动态性dynamicity 提出了四个未来可能的研究方向。

3.1 背景

  1. GNN 的历史:《Supervised neural networks for the classification of structures》 首次将神经网络应用于有向无环图,这激励了早期对 GNN 的研究。《A new model for learning in graph domains》 最初概述了图神经网络的概念,《The graph neural network model》 进一步阐述了这个概念。这些早期的研究属于递归图神经网络(recurrent graph neural network: RecGNN)的范畴。它们通过以迭代的方式传播邻居信息来学习目标节点的 representation,直到达到一个稳定的不动点。这个过程的计算成本很高,最近有越来越多的人在努力克服这些挑战。

    在计算机视觉领域 CNN 成功的鼓舞下,大量为图数据重新定义卷积概念的方法被提出。这些方法都属于卷积图神经网络(convolutional graph neural network: ConvGNN)的范畴。卷积图神经网络分为两个主要方向,即基于谱域的方法和基于空间域的方法。

    • 第一个关于基于谱域的卷积图神经网络的突出研究是由 《Spectral networks and locally connected networks on graphs》 提出的,他们开发了一个基于谱图理论的图卷积。此后,对基于谱域的卷积图神经网络的改进、扩展越来越多。
    • 基于空间域的卷积图神经网络的研究比基于谱域开始得更早。《Neural network for graphs: A contextual constructive approach》 首次通过架构上来组合非递归层来解决图的相互依赖性,同时继承了递归图神经网络的消息传递思想。然而,这项工作的重要性被忽略了。

    除了递归图神经网络和卷积图神经网络,过去几年中还开发了许多其他的 GNN,包括图自编码器和 "空间-时间"图神经网络。这些学习框架可以建立在递归图神经网络、卷积图神经网络或其他用于图建模的神经架构上。

  2. GNN vs graph embeddingGNNgraph embedding 密切相关。

    • graph embedding 目的是将网络节点表示为低维embedding 向量,同时保持网络拓扑结构和节点内容信息,以便可以使用简单的、已有的机器学习方法(如支持向量机)轻松执行任何后续的图分析任务(如节点分类、节点聚类、推荐)。

    • GNN 是深度学习模型,旨在以端到端的方式解决图相关的任务。很多 GNN 显式地提取 high-level representation

    • GNNgraph embedding 主要区别在于:

      • GNN 是一组为各种任务而设计的神经网络模型,而 graph embedding 覆盖了同一个任务的各种不同方法。因此,GNN 可以通过图自编码器框架解决 graph embedding 问题。
      • 另一方面,graph embedding 也包含其它非深度学习方法,如矩阵分解 MF、随机游走。
  3. GNN vs graph kernelGraph Kernel 曾经是历史上解决图分类问题的主流技术。这些方法设计核函数 kernel function 来度量graph pair-wise 之间的相似度,使得 kernel-based 算法(如支持向量机)可用于图上的监督学习。

    • GNN 相似,Graph Kernel 可以通过映射函数将图或节点嵌入到向量空间。不同之处在于:Graph Kernel 的这个映射函数是确定性的,而不是通过学习得到。
    • 由于 pair-wise 相似性的计算,Graph Kernel 方法遇到了计算瓶颈。
    • GNN 基于抽取的 graph representation 直接执行图分类,因此比 Graph Kernel 方法更有效。

3.2 GNN 分类

  1. 定义图 G=(V,E) ,其中 V={v1,,vn} 为节点集合, E={ei,j} 为边集合。

    • ei,j=(vi,vj)E 表示一条从 vj 指向 vi 的边。
    • 节点 v 的邻域定义为 Nv={uV(v,u)E}
    • 邻接矩阵 ARn×n 定义为:如果 ei,jEAi,j=1,否则 Ai,j=0
    • 每个节点 vV 关联一个节点属性 xvRd ,其中 d 为属性维度。所有节点的属性构成节点属性矩阵 XRn×d ,其中第 v 行对应于节点 v 的属性 xv
    • 每条边 e=(v,u)E 关联一个边属性 xv,ueRc,其中 c 为属性维度。所有边的属性构成边属性矩阵 XeRm×c,其中 m 为边的数量,第 e 行对应于边 e=(v,u) 的属性 xv,ue
  2. 定义有向图是所有边都是有向边的图,其中有向边指的是每条边都从一个节点指向另一个节点。

    • 无向图是有向图的特殊情况,其中每条有向边都存在与之相反方向的另一条边。
    • 当且仅当邻接矩阵是对称矩阵时,图才是无向图。
  3. 定义时空图spatial-temporal graph 为一个属性图,其中节点属性随时间动态变化,记作 G(t)=(V,E,X(t)) ,其中 X(t)Rn×d

  4. 我们将图神经网络 GNN 分类为:循环图神经网络 RecGNN、卷积图神经网络ConvGNN、图自编码器 GAE、时空图神经网络STGNN,如下表所述。

    下表给出了各种模型架构的一些示例。

    • 具有多个图卷积层graph convolutional layerConvGNN。图卷积层通过聚合来自邻域的特征信息,从而得到每个节点的 hidden representation,并在特征聚合之后再应用非线性变换。通过堆叠多个图卷积层,每个节点的最终 hidden representation 将接收来自更远邻域的消息。

    • 具有池化层和 readout 层的、用于图分类的 ConvGNN 。图卷积层之后是池化层,从而将图粗化 coarsen 为子图,以便粗化图上的节点representation 能够表达更高的 graph-level representationreadout 层通过获取粗化图所有节点的 hidden representation 均值或sum 结果,从而得到最终的 graph representation

    • 用于graph embeddingGAE。编码器使用图卷积层获取每个节点的 graph embedding,解码器根据graph embedding 计算节点的 pairwise 距离。在应用非线性激活函数之后,解码器重构图邻接矩阵。通过最小化实际的图邻接矩阵、重构的图邻接矩阵之间的差异来训练网络。

    • 用于时空图预测的 STGNN。图卷积层后面是1D-CNN 层:图卷积层在 AX(t) 上操作从而捕获空间相关性;而 1D-CNN 沿时间轴在 X 上滑动以捕获时间相关性。输出是一个线性变换,可以为每个节点生成预测,如下一个time step 的、未来的取值。

  5. 循环图神经网络 RecGNN:大多数是图神经网络的早期作品。RecGNN 目的是通过递归神经网络体系架构学习节点的 representation。他们假设图中的节点不断与其邻居交换消息,直到到达稳定的平衡。

    RecGNN 在概念上很重要,并激发了后续对卷积图神经网络的研究。具体而言,RecGNN 消息传递的思想被基于空间的卷积图神经网络所继承。

  6. 卷积图神经网络ConvGNN:推广了从网格数据到图数据的卷积运算。主要思想是通过聚合节点自身的特征 xv 和邻居特征 xu,uNv 来生成节点 vrepresentation 。和 RecGNN 不同,ConvGNN 堆叠多个图卷积层从而获得high-level 节点 representation

    ConvGNN 在搭建很多其它更复杂的 GNN 模型中起着核心作用。

  7. 图自编码器 GAE:是一种无监督的学习框架,可以将节点/图编码到潜在的 embedding 空间,并根据编码后的信息重建图数据。

    GAE 用于学习 graph embedding 以及图生成分布 graph generative distribution

    • 对于 graph embedding任务,GAE 通过重构图结构信息(如图的邻接矩阵)来学习潜在的节点 representation
    • 对于图生成任务,一些方法逐步生成图的节点和边,而另一些方法则一次性生成整个图。
  8. 时空图神经网络STGNN:旨在从时空图学习隐藏的模式 hidden pattern ,这在各种应用中变得越来越重要,例如:交通速度预测 traffic speed forecasting 、驾驶员操纵预测、人类动作识别等。

    STGNN 的关键思想是同时考虑空间依赖性spatial dependency和时间依赖性temporal dependency 。当前的许多方法将图卷积和 RNN/CNN 集称在一起,其中图卷积捕获空间依赖性,RNN/CNN 捕获时间依赖性。

  9. GNN 的输入为图结构和节点内容信息,但是 GNN 的输出依赖于具体的图分析任务:

    • node-level 输出:和节点回归、节点分类任务有关。

      RecGNNConvGNN 可以通过消息传播/图卷积抽取high-level 节点representation,然后使用多层感知机 multi-perceptron:MLP 或者 softmax 层作为输出层。最终 GNN 能够以端到端的方式执行 node-level 任务。

    • edge-level 输出:和edge 分类、链接预测任务有关。

      使用来自 GNN 的两个节点的 hidden representation 作为输入,然后利用相似度函数或神经网络来预测边的标签或链接强度。

    • graph-level 输出:和图分类任务有关。

      为获得 graph-level 的紧凑表示compact representationGNN 通常与池化操作、readout 操作配合使用。

  10. 训练框架:可以在端到端学习框架内以监督学习、半监督学习甚至完全无监督学习的方式训练一些 GNN 模型(如 ConvGNN),具体取决于学习任务和可用的标签信息。

    • 用于 node-level分类的半监督学习:给定一个graph 其中部分节点带类别标记、剩余节点没有类别标记,ConvGNN 可以学习一个 robust 模型,该模型可以有效地识别未标记节点的类别信息 。为此,可以堆叠几个图卷积层,然后跟一个 softmax layer 从而构建端到端的多类别分类框架。

    • 用于 graph-level 分类的监督学习:目的是预测整个图的类标签。可以通过图卷积层、图池化层、和/或 readout layer 的组合来完成端到端的图分类任务。

      • 图卷积层负责获取准确的 high-level 节点 representation
      • 图池化层充当降采样的角色,从而每次都将图粗化 coarsen 为子结构 sub-structure
      • readout layer 将图的所有节点压缩为一个 graph representation

      通过将一个多层感知机 MLP 以及一个 softmax layer 应用于 graph representation,我们可以构建用于图分类的端到端框架。

    • 用于 graph embedding 的无监督学习:当图没有可用的类标签时,我们可以在端到端框架中以纯无监督的方式学习 graph embedding

      这些算法以两种方式利用 edge-level 信息:

      • 一种简单的方法是采用自编码器框架,其中编码器使用图卷积层将 graph 嵌入到潜在 representation 空间中,然后对潜在 representation 应用解码器来重构图结构。
      • 另一种流行的方法是利用负采样方法,该方法采样一部分节点 pair 对为负边 negative edge,而图中具有链接的节点 pair 对为正边 postive edge。然后应用逻辑回归层 regression layer 来区分正边和负边。
  11. 我们在下表中总结了一些典型 RecGNNConvGNN 的主要特点,并在各种模型之间比较了输入源、池化层、readout layer、以及时间复杂度。更具体而言,我们仅比较每个模型中消息传递/图卷积操作的时间复杂度。

    • 由于 《Spectral networks and locally connected networks on graphs》《Deep convolutional networks on graph-structured data》 中的方法需要特征值分解 eigenvalue decomposition,因此其时间复杂度为 O(n3)

    • 由于需要计算节点 pair 对的最短路径,因此 《On filter size in graph convolutional networks》 的时间复杂度也是 O(n3)

    • 其它方法的时间复杂度几乎差不多:如果图的邻接矩阵是稀疏的,则时间复杂度为 O(m) ;否则时间复杂度为 O(n2)

      这是因为这些方法中,计算每个节点 virepresentation 都涉及其 di 个邻居(di 为节点 videgree ),并且所有节点上 di 的总和刚好等于边的数量。

    • 表中缺少几种方法的时间复杂度,这是因为:这些方法在原始论文中缺乏时间复杂度分析,或者仅报告其总体模型或算法的时间复杂度。

    • 池化层和 readout layer 中的缺失值 - 表示该方法仅在 node-level/edge-level 任务上进行实验。

3.3 RecGNN

  1. RecGNN 大多数是 GNN 的早期研究,它在图上的节点反复应用相同的函数,从而抽取high-level 节点 representation。受算力的限制,早期研究主要集中于有向无环图上。

  2. 论文 《The graph neural network model》首次提出了图神经网络 GNN,它扩展了已有的递归模型recurrent model 从而处理图数据,如带环图、无环图、有向图、无向图等。为区分通用的术语图神经网络,这里我们将论文中的模型记作 GNN*

    GNN* 基于消息传播机制,通过反复交换邻域信息来更新节点的状态,直到达到稳定的平衡状态为止。节点的 hidden state 反复被更新,更新方程为:

    hv(t)=uNvf(xv,ev,u,xu,hu(t1))

    其中 f() 是一个可学习的函数,hv(0) 为随机初始化的hidden state

    • 求和运算使得 GNN* 适用于所有类型的节点,即使邻居的数量不同并且不知道邻居节点的顺序。
    • 为了确保收敛,递归函数 f() 必须是收缩映射,即两个节点经过 f() 之后它们在潜在空间中的距离缩小(相比于原始空间中特征向量之间的距离)。如果 f() 是神经网络,则必须对参数的雅可比矩阵施加惩罚。
    • GNN* 交替执行节点状态传播、参数梯度计算,从而最小化训练目标。这种策略使得 GNN* 可以处理有环图。
  3. 在后续的工作中,Graph Echo State Network:GraphESN 扩展了 echo state network 来提升 GNN* 的训练效率。

    GraphESN 由编码器和输出层组成。其中, f() 作为编码器是随机初始化且无需训练,它实现了收缩映射从而递归更新节点状态直到收敛。然后通过将 fixed node state 作为输入来训练输出层。

  4. Gated Graph Neural Network:GGNN 采用GRU 作为递归函数 f() ,并且将递归次数降低到固定的step 数量。其优点是:它不再需要约束参数从而确保 f() 收敛。节点 hidden state 根据它之前的 hidden state 以及邻居的 hidden state 来更新:

    hv(t)=GRU(hv(t1),uNvWhu(t1))

    其中 hv(0)=xv

    GNN*、GraphESN 不同,GGNN 使用时间反向传播 back-propagation through time:BPTT 算法来学习模型参数。这对于大型图可能会出现问题,因为 GGNN 需要在所有节点上多次运行递归函数,并要求将所有节点的中间状态存储在内存中。

  5. Stochastic Steady-state Embedding:SSE 提出了一种学习算法,该算法对大型图更具有可扩展性 scalable

    SSE 以随机的、异步的方式递归地更新节点 hidden state。它交替采样一个 batch 的节点用于状态更新、采样一个 batch 的节点用于梯度计算。为了保持稳定性,SSE 递归函数定义为历史状态和最新状态的加权平均,更新方程为:

    hv(t)=(1α)hv(t1)+αW1σ(W2[xv,uNv[hu(t1),xu]])

    其中:

    • α 为超参数。
    • hv(0) 为节点 v 的初始状态,它随机初始化。
    • σ() 为非线性激活函数,[,] 为向量拼接。
    • W1,W2 为模型参数。

    尽管从概念上讲很重要,但是 SSE 并未在理论上证明:通过反复应用上述公式节点状态会逐渐收敛到不动点fixed point

3.4 ConvGNN

  1. 图卷积神经网络 ConvGNN 和递归图神经网络密切相关。ConvGNN 不是使用收缩约束的映射来迭代节点状态,而是使用固定数量的layer ,其中每层具有不同的权重。下图说明了这一主要区别:

    • (a)RecGNN 使用相同的 graph recurrent layer:Grec 来更新节点 representation
    • (b)ConvGNN 使用不同的 graph convolutional layer:GConv 来更新节点 representation

  2. 由于图卷积更有效、更方便与其它神经网络进行组合,因此近年来 ConvGNN 的普及非常迅速。ConvGNN 可以分为两类:基于谱域spectral-based、基于空域 spatial-based

    • 基于谱域的方法通过从图信号处理的角度引入滤波器来定义图卷积,其中图卷积运算被解释为从图信号中去除噪声。
    • 基于空域的方法继承了 RecGNN 的思想,它通过消息传播来定义图卷积。

    自从 GCN 弥合了基于谱域方法和基于空域方法之间的 gap ,基于空域的方法由于其卓越的效率efficiency 、灵活性flexibility 、通用性generality 而得到迅速发展。

3.4.1 基于谱域的 ConvGNN

  1. 基于谱域的ConvGNN 在图信号处理中具有扎实的数学基础。他们认为图是无向的,归一化的图拉普拉斯矩阵是无向图的数学表述,定义为 L=ID1/2AD1/2 ,其中 :

    • A 为图的邻接矩阵。
    • D=diag(D1,,Dn),Di=jAi,j 为节点的degree 矩阵(一个对角矩阵)。

    归一化的图拉普拉斯矩阵是实对称的、半正定的矩阵,因此可以对其进行特征值分解:

    L=UΛU

    其中:

    • Λ=diag(λ1,,λn)n 个特征值,其中 λ1λ2λn

    • U=[u1,,un]Rn×n 为特征向量eigenvector 组成的矩阵,其中 ui 为特征值 λi 对应的特征向量。

      {u1,,un} 构成了一个线性空间的正交基,数学语言描述为 UU=I

    在图信号处理领域,一个图信号 x=(x1,,xn)Rn 是关于所有节点的特征向量 feature vector ,其中 xiR 表示在节点 vi 上的取值(一个标量)。针对图信号 x 的图傅里叶变换定义为:

    x^=F(x)=Ux

    对应的图傅里叶逆变换为:

    x=F1(x^)=Ux^

    图傅里叶变换将输入的图信号投影到正交空间,正交基是由归一化的图拉普拉斯矩阵的特征向量构成。图傅里叶变换后的信号 x^ 的元素是新空间中图信号的坐标,因此输入图信号可以表示为:

    x=ix^iui

    这刚好就是图傅里叶逆变换。

    因此对输入信号 x 使用滤波器 gθRn 的图卷积定义为:

    xGgθ=F1(F(x)F(gθ))=U(UxUgθ)

    其中 表示逐元素的乘积,θ 为卷积核参数。

    如果我们定义一个滤波器为:Kθ=diag(Ugθ)Rn×n (即向量 Ugθ 的元素组成对角矩阵),则谱域图卷积定义为:

    xGgθ=UKθUx

    所有的谱域卷积都遵从这个公式,但是不同的方法选择不同的滤波器 Kθ

  2. Spectral Convolutional Neural Network:Spectral CNN 假设图信号是多通道的,通道 i 的输入记作 H:iRn

    假设网络有多层,其中第 l 层的输入记作 H(l1)Rn×dl (即 dl 个通道)。Spectral CNN 对于每个通道采用多个卷积层来生成多通道输出。对于第 l 层第 j 个输出通道定义为:

    H:,j(l)=σ(i=1dl1UΘi,j(l)UH:,i(l1)),j=1,2,,dl

    其中:

    • Θi,j(l)Rn×n 为第 l 层对应于输入通道 i 、输出通道 j 的卷积核,它是一个对角矩阵因此只有 n 个参数。(它就是前述的滤波器 Kθ )。
    • H(l1) 为第 l 层的输入信号(也是第 l1 层的输出信号)。H(0)=X
    • dl1 为第 l 层输入信号的通道数,dl 为第 l 层输出信号的通道数。

    由于图拉普拉斯矩阵的特征分解 eigendecompositionSpectral CNN 面临三个限制:

    • 首先,对图的任何扰动都会导致特征根 eigenbasis 的变化。
    • 其次,学习的滤波器是transductive 的,它无法应用于具有不同结构的图。
    • 最后,特征分解计算复杂度为 O(n3) 。在后续工作中,ChebNetGCN 通过进行一些近似和简化将计算复杂度降低到 O(m)
  3. Chebyshev Spectral CNN:ChebNet 通过切比雪夫多项式来逼近滤波器 Kθ (注:它是一个对角矩阵)。即:

    Kθ=i=0KθiTi(Λ~)

    其中 Λ~=2ΛλmaxIλmax 为最大特征值。因此 Λ~ 是一个对角线元素取值在 [-1,1] 之间的对角矩阵。

    切比雪夫多项式定义为:

    Ti(x)=2x×Ti1(x)Ti2(x)T0(x)=1,T1=x

    因此图信号 xRn 的卷积定义为:

    xGgθ=UKθUx=U(i=0KθiTi(Λ~))Ux

    定义 L~=2LλmaxI ,则有 Ti(L~)=UTi(Λ~)U 。因此得到 ChebNet 卷积公式:

    xGgθ=i=0KθiTi(L~)x

    作为对 Spectral CNN 的改进,ChebNet 定义的滤波器是空间局部性的,这意味着滤波器可以独立于图的大小而抽取局部特征。

    另外,ChebNet 将频谱 spectrum 线性映射到 [-1,1] 之间(即线性映射: 2λi/λmax1)。

  4. CayleyNet 进一步使用参数为有理复函数rational complex functionCayley 多项式来捕获窄带信号narrow frequency bandCayleyNet 的谱图卷积定义为:

    xGgθ=c0x+2×Re{j=1rcj(hLiI)j(hL+iI)jx}

    其中:

    • Re(.) 返回复数的实部。
    • c0 为实数系数, cj 为复数系数,i 为单位虚数,h 为卷积核参数用于控制 Cayley 滤波器的谱spectrum

    CayleyNet 不仅可以保持空间局部性 spatial locality,而且 ChebNet 可以视为 CayleyNet 的特例。

  5. Graph Convolutional Network:GCNChebNet 采用一阶近似。假设 K=1 以及 λmax=2,则ChebNet 卷积公式近似为:

    xGgθ=i=0KθiTi(L~)xθ0xθ1D1/2AD1/2x

    为限制参数数量从而缓解过拟合,GCN 进一步假定 θ=θ0=θ1 ,因此上式进一步简化为:

    xGgθθ(I+D1/2AD1/2)x

    为支持多通道输入和多通道输出,GCN 进一步将上式转换为:

    H=XGgΘ=f(A¯XΘ)

    其中:

    • A¯=I+D1/2AD1/2
    • f() 为非线性激活函数。
    • XRn×dindin 个通道的输入信号。
    • HRn×doutdout 个通道的输出信号。
    • ΘRdin×dout 为卷积核参数。

    由于使用 I+D1/2AD1/2 实际应用中会导致 GCN 数值不稳定。为解决该问题,GCN 应用了归一化技巧,将A¯=I+D1/2AD1/2 代替为:

    A¯=D~1/2A~D~1/2A~=A+I,D~=diag(D~1,,D~n),D~i=jA~i,j

    GCN 虽然是基于谱域的方法,也可以解释为基于空域的方法。从基于空域的角度来看,GCN 可以视为聚合节点邻域中的特征信息。即 H=XGgΘ=f(A¯XΘ) 视作:

    hv=f(Θ(uNv{v}A¯v,uxu)),vV
  6. 最近的一些工作通过探索某些对称矩阵来代替邻接矩阵从而对 GCN 进行增量改进 incremental improvement

    • Adaptive Graph Convolutional Network:AGCN 学习隐藏的结构关系,这种关系未被图的邻接矩阵所给出。

      AGCN 通过一个可学习的距离函数来构造一个所谓的残差图邻接矩阵 residual graph adjacency matrix 。这个距离函数将两个节点的特征作为输入。

    • Dual Graph Convolutional Network:DGCN 引入双图卷积体系架构,它有两个并行的图卷积层。这两个图卷积层共享参数,但是分别使用归一化的邻接矩阵 A¯ 、以及positive pointwise mutual information:PPMI 矩阵。

      PPMI 矩阵通过从图上采样的随机游走来捕获节点的共现信息,定义为:

      PPMIi,j=max(log(ci,j×|D|ci×cj),0)

      其中:

      • PPMIi,j 表示节点 vi,vj 的共现 PPMI 值。
      • D 为随机游走统计到的所有节点 pair 对的集合, |D| 表示集合的大小。
      • ci 表示 D 中节点 vi 出现的频次,cj 表示 D 中节点 vj 出现的频次,ci,j 表示 D 中节点 vi,vj 共现的频次。

      通过集成 ensembling 来自双图卷积层的输出,DGCN 可以对局部结构信息和全局结构信息进行编码,无需堆叠多个图卷积层。

3.4.2 基于空域的 ConvGNN

  1. 和在图像上进行卷积操作的传统 CNN 类似,基于空域的方法基于节点的空间关系定义图卷积。

    图像可以被视为图的一种特殊形式,其中:图像上每个像素代表一个节点,每个像素直接与其附近的像素相连。在图像上应用一个 3x3 的卷积可以获得每个通道上中心节点及其邻居(共9 个节点)像素值的加权均值。

    类似地,基于空域的图卷积将中心节点的representation 和邻居的 representation 进行卷积,从而得到中心节点的更新 representation

    从另一个角度来看,基于空域的 ConvGNNRecGNN 共享相同的消息传递思想。空域图卷积运算本质上是沿着edge 传播节点信息。

  2. Neural Network for Graphs:NN4GGNN* 同一时期被提出,它是针对基于空域的 ConvGNN 的第一项工作。

    RecGNN 截然不同的是,NN4G 通过每层具有独立参数的组合神经网络体系架构来学习节点的相互依赖关系。节点的邻域可以通过体系结构的增量构建来扩张。

    NN4G 通过直接聚合节点的邻域信息来执行图卷积,它还使用残差链接 residual connection 以及跳跃连接 skip connection 来记住每一层的信息。最终NN4G 的节点状态更新方程为:

    hv(l)=f(W(l)xv+i=1l1uNvΘ(l)hu(i))

    其中: f() 为非线性激活函数,hv(0)=0

    上式也可以写作矩阵形式:

    H(l)=f(XW(l)+i=1l1AH(i)Θ(l))

    这类似于 GCN 的形式。一个区别是 NN4G 使用未归一化的邻接矩阵,这可能潜在地导致节点的 hidden state 具有极为不同的量级。

  3. Contextual Graph Markov Model:CGMM 受到NN4G 启发,从而提出了一种概率模型。CGMM 在保持空间局部性的同时,还具有可解释性的优势。

  4. Diffusion Convolutional Neural Network:DCNN 将图卷积视为扩散过程。它假定信息以一定的转移概率从一个节点转移到相邻节点之一,从而使得信息分布可以在几轮之后达到平衡。DCNN 将扩散图卷积diffusion graph convolution 定义为:

    H(l)=f(W(l)(PlX))

    其中:

    • f() 为非线性激活函数, 为逐元素相乘。
    • P=D1ARn×n 为转移概率矩阵,Pl=PPllP 相乘。
    • W(l)Rn×d 为第 l 层的参数。

    注意在 DCNN 中,hidden representation 矩阵 H(l) 的维度和输入特征矩阵 XRn×d 相同,并且不是前一层 hidden representation 矩阵 H(l1) 的函数。

    最终 DCNN 拼接 H(1),,H(L) 为模型最终输出。

  5. 由于扩散过程的平稳分布是概率转移矩阵的幂级数的总和,因此 Diffusion Graph Convolution:DGC 将每个扩散step 中的结果相加,而不是进行拼接。它定义扩散图卷积diffusion graph convolution 为:

    H=l=0Lf(PlXW(l))

    其中:

    • f() 为非线性激活函数。
    • W(l)Rd×dout ,其中 d 为输入特征维度,dout 为输出representation 维度。这使得hidden representation 矩阵 H(l)Rn×dout 的维度和输入特征矩阵 XRn×d 维度可以不同。
  6. 使用转移概率矩阵的幂意味着距离遥远的邻居向中心节点贡献的信息很少。PGC-DGCNN 根据最短路径增加遥远邻居的贡献,它定义最短路径邻接矩阵 S(j) :如果从节点 v 到节点 u 的最短路径为 jSv,u(j)=1 ,否则 Sv,u(j)=0

    转移概率矩阵的幂次意味着邻居节点的重要性随着距离的增加呈指数型衰减,而这里的权重设定为 1

    通过使用超参数 r 控制感受野大小receptive field sizePGC-DGCNN 引入了图卷积运算如下:

    H(l)=||j=0rf((D~(j))1S(j)H(l1)W(j,l))

    其中:

    • f() 为非线性激活函数,|| 表示向量拼接。
    • D~(j) 为根据 S(j) 计算得到的度矩阵:D~(j)=diag(D~1(j),,D~n(j)),D~i(j)=kSi,k(j)
    • W(j,l)Rdl1×dl 为最短路径 j 在第 l 层的参数,dl 为第 lrepresentation 的维度。

    由于最短路径邻接矩阵 S(j) 的计算复杂度为 O(n3) ,因此该方法计算代价太高。

  7. Partition Graph Convolution:PGC 根据某些原则(不限于最短路径)将节点的邻居划分为 Q 个分组,并根据每个组定义的邻域来构造 Q 个邻接矩阵。然后PGC 将具有不同参数的 GCN 应用于每个邻居分组,并对结果求和:

    H(l)=q=1QA¯(q)H(l1)W(q,l)

    其中:

    • H(0)=XH(l)Rn×dl 为第 l 层的 representationdl 为第 l 层的 representation的维度。
    • A¯(q)=(D~(q))1/2A~(q)(D~(q))1/2A~(q)=A(q)+ID~(q)A~(q) 的度矩阵。
    • W(q,l)Rdl1×dl 为分组 q 的参数矩阵。

    类似于注意力机制中的 multi-head

  8. Message Passing Neural Network:MPNN 总结了基于空域的 ConvGNN 的通用框架。MPNN 将图卷积视为一个消息传递过程,其中信息可以直接从一个节点沿着边传递到另一个节点。MPNN 执行 L 步消息传递从而使得信息传递得更远。

    消息传递函数(即空间图卷积)定义为:

    hv(l)=Ul(hv(l1),uNvMl(hv(l1),hu(l1),ev,u))

    其中:

    • Ul(),Ml() 都是可学习的函数。
    • hv(l)Rdl 为节点 v 在第 l 层的 representationhv(0)=xv

    在得到每个节点的hidden representation 之后,可以将 hv(L) 传递到输出层从而执行 node-level 预测任务,或者传递给 readout 函数从而执行 graph-level 预测任务。readout 函数基于节点hidden representation 从而生成整个图的 representation

    hG=R(hv(L)vV)

    其中 R() 表示可学习的 readout 函数。

  9. 虽然 MPNN 可以通过选择不同形式的 Ul(),Ml(),R() 从而覆盖cover 很多现有的 GNN 模型,但是 Graph Isomorphism Network:GIN 发现:基于 MPNN 的方法无法根据它们生成的 graph embedding 来区分不同的图结构。

    为弥补这一缺陷,GIN 通过可学习的参数 ϵ(l) 来调整中心节点的权重。它定义图卷积为:

    hv(l)=MLP((1+ϵ(l))hv(l1)+uNvhu(l1))

    其中MLP() 表示多层感知机。

  10. 由于节点的邻居数量可能从11000 甚至更多,因此获取节点的全部邻居效率太低。GraphSAGE 采用采样技术为每个节点获取固定数量的邻居,并定义图卷积为:

    hv(l)=σ(W(l)Aggl(hv(l1),{hu,(l1),uSNv}))

    其中:

    • σ() 为非线性激活函数,Aggl() 为第 l 层的聚合函数, SNv 为节点 v 随机采样的邻域。
    • hv(l)Rdl 为节点 v 在第 l 层的 representationhv(0)=xv

    聚合函数需要满足排列不变性 permutation invariant ,如均值函数、求和函数、最大值函数等。

  11. Graph Attention Network:GAT 假设邻居节点对于中心节点的贡献既不像GraphSAGE 一样都是 1 (即所有邻居节点对于中心节点的贡献都相同)、也不像 GCN 一样预先定义(权重为 1degi×degj),如下图所示。

    GAT 采用注意力机制来学习两个相连节点之间的相对权重,它定义图卷积运算为:

    hv(l)=σ(uNv{v}αv,u(l)W(l)hu(l1))

    其中 hv(0)=xvαv,u(l) 刻画了节点 v 及其邻居节点 u 的注意力强度:

    αv,u(k)=softmax(g(a[W(l)hv(l1)||W(l)hu(l1)]))

    其中:

    • g()LeakyReLU 激活函数。
    • a 为可学习的注意力向量。
    • || 表示向量拼接。
    • softmax 函数可以确保节点 v 的所有邻居(包括节点 v 自身)的注意力权重之和为 1.0

    GAT 进一步执行multi-head attention 从而提高模型的表达能力。在节点分类任务上,GAT 相对于 GraphSAGE 有着显著的提升。

  12. GAT 假设attention head 的贡献是相等的,而Gated Attention Network:GAAN 认为不同的 attention head 的贡献是不同的。GAAN 引入了一种 self-attention 机制,该机制为每个 attention head 计算一个额外的注意力得分。

  13. 除了在空间上 spatially 应用图注意力之外,GeniePath 进一步提出了一种类似于 LSTM 的门控机制,从而控制跨图卷积层的信息流。

    还有其它有趣的图注意力模型,但是它们不属于 ConvGNN 框架。

  14. Mixture Model Network:MoNet 采用不同的方法为节点的邻居分配不同的权重,它引入节点伪坐标 pseudo-coordinates 以确定节点及其邻居之间的相对位置。一旦知道两个节点之间的相对位置,则权重函数会根据相对位置计算这两个节点之间的相对权重。这样,图滤波器的参数可以在不同位置 location 之间共享。

    MoNet 框架下,通过构造非参数的 nonparametric 权重函数,几种流形manifold 方法如 Geodesic CNN: GCNNAnisotropic CNN : ACNNSpline CNN,某些图卷积方法如 GCN、DCNN ,都可以视作 MoNet 的特例。

    MoNet 还提出了一个具有可学习参数的高斯核,从而自适应地学习权重函数。

  15. 另一类独特的方法是:根据某些标准对节点的邻居进行排名ranking,并将每个排名与可学习的权重相关联,从而在不同位置实现权重共享。

    • PATCHY-SAN 根据它们的图标签graph label对每个节点的邻居进行排序,并选择 top q 个邻居。图标签本质上是节点得分,可以通过节点 degree、节点中心度centrality、节点 Weisfeiler-Lehman color 得到。

      由于每个节点现在都有固定数量的有序邻居,因此可以将图结构数据转换为网格结构的数据。PATCHY-SAN 采用标准的 1D 卷积滤波器来聚合邻域特征信息,其中滤波器权重的顺序和节点邻居的顺序相对应。

    • PATCHY-SAN 的排名准则仅考虑图结构,这需要大量计算才能进行数据处理。Large-scale Learnable Graph Convolutional Network:LGCN 根据节点特征信息对节点的邻居进行排名。对于每个节点,LGCN 都会拼装assemble 一个由其邻域组成的特征矩阵,并沿着每一列(行代表节点、列代表特征)对该矩阵进行排序。排序后的特征矩阵的前 k 行被用于中心节点的输入数据从而执行标准的卷积运算。

      下图中,矩阵第一行是中心节点的特征向量,它不参与排序。后面 4 行是排序之后的。排序时,不同列之间相互独立排序。

3.4.3 空域 ConvGNN 训练效率

  1. 通常训练诸如 GCN 之类的 ConvGNN 需要将整个图数据和所有节点的中间状态保存到内存中,因此 ConvGNNfull-batch 训练算法遭受内存溢出的困扰,尤其是当一个图包含数百万节点时。

  2. 为降低内存需求,GraphSAGE 提出了一种针对 ConvGNNbatch 训练算法。对于batch 中的每个节点,它以固定大小递归采样节点邻域从而构成一棵以该节点为根节点的采样树。对于每棵采样树,GraphSAGE 通过从下到上分层聚合节点的 hidden representation 来计算根节点的 hidden representation

  3. Fast Learning with Graph Convolutional Network:FastGCN 为每个图卷积层采样固定数量的节点,而不是像 GraphSAGE 那样为每个节点采样固定数量的邻居。它将图卷积解释为概率测度下节点 embedding 函数的积分变换,然后采用蒙特卡洛近似Monte Carlo approximation 以及方差缩减技术 variance reduction technique 来加速训练过程。

  4. 由于 FastGCN 针对每一层独立采样节点,因此层间连接可能很稀疏。《Adaptive sampling towards fast graph representation learning》 提出一种自适应的逐层采样方法,其中较低层的节点采样以上一层已经采样到的节点为条件。和 FastGCN 相比,该方法以更复杂的采样方案为代价实现了更高的准确率。

  5. Stochastic Training of Graph Convolutional Networks:StoGCN 使用历史的节点representation 作为控制变量从而将图卷积的感受野尺寸receptive field size 缩减到任意小的尺度scale。即使每个节点仅有两个邻居(其中一个是它自己),StoGCN 仍然可以达到可比的comparable 性能。但是,StoGCN 仍然必须保存所有节点的中间状态,这对于大型图来讲是非常消耗内存的。

  6. Cluster-GCN 使用图聚类算法对子图进行采样,并对所采样的子图中的节点执行图卷积。由于邻域搜索被限制在采样的子图中,因此 Cluster-GCN 能够处理更大的图,并同时使用更少的时间、更少的内存来训练更深的体系架构。

    对于现有的 ConvGNN 训练算法,Cluster-GCN 特别提供了时间复杂度和内存复杂度的直接比较,如下表所示。其中 n 为节点数量、m 为边数量、K 为层数、sbatch sizer 为每个节点采样的邻居数量。为简化讨论,我们假设所有层的 hidden representation 维度都是 d

    • GCNfull-batch 训练方法,它作为 baseline
    • GraphSAGE 以牺牲时间效率来节省内存。同时随着 Kr 的增加,GraphSAGE 的时间和内存复杂度呈指数级增长。
    • StoGCN 的时间复杂度最高,并且内存瓶颈仍未解决。但是,StoGCN 可以通过很小的 r 获得令人满意的性能。
    • Cluster-GCN 的时间复杂度和 baseline 相同,因为它没有引入冗余计算。
    • 所有方法中,ClusterGCN 实现了最低的内存复杂度。

3.4 .4 spectral vs spatial

  1. 谱域模型 spectral model 具有图信号处理的理论基础,可以通过设计新的图信号滤波器来构建新的 ConvGNN。但是,由于效率efficiency、通用性generality、灵活性flexibility 等问题,空域模型spatial model 要优于谱域模型。

    • 首先,谱域模型的效率不如空域模型。谱域模型要么需要执行特征向量 eigenvector 计算,要么需要同时处理整个图。

      空域模型对于大型图更具有可扩展性scalable,因为它通过信息传播直接在图域graph domain 中执行卷积。计算可以在一个 batch 的节点上进行,而不是整个图。

    • 其次,依赖于图傅里叶基graph Fourier basis 的谱域模型无法泛化到新的图。因为谱域模型假设图是固定的,对图的任何扰动都将导致本征基eigenbasis 的变化。

      另一方面,空域模型在每个节点的局部执行图卷积,其中模型权重可以在不同位置、不同结构之间轻松共享。

    • 最后,谱域模型仅限于在无向图上运行,而空域模型可以更灵活地处理多种数据源multi-source的图输入graph input,如edge input、有向图、有符号图、异质图等。因为这些图输入可以轻松地集成到空域模型的聚合函数中。

3.4.5 Graph Pooling 模型

  1. GNN 生成节点特征后,我们可以将其用于最终任务。但是,直接使用所有节点的特征可能在计算上具有挑战性,因此需要一种降采样策略down-sampling strategy 。根据不同的任务目标、以及降采样在网络中扮演的角色,该策略有不同的称呼:

    • pooling 操作:旨在通过对所有节点representation 进行降采样从而生成规模更小的 representation 从而减少参数大小,进而缓解过拟合、实现置换不变性 permutation invariance、以及解决计算复杂度问题。
    • readout 操作:旨在基于节点 representation 生成 graph-level representation

    它们的机制都非常相似,因此这里我们用池化pooling 来指代用于GNN 中的各种降采样策略。

  2. 在一些早期的工作中,图粗化算法graph coarsening algorithm 使用特征分解 eigen-decomposition 来基于图的拓扑结构来粗化图。但是这些方法存在时间复杂度问题。

    • Graclus 算法是特征分解的替代方法,用于计算原始图的聚类版本clustering version 。有一些近期的工作将它作为池化操作来粗化图。

    • 如今,mean/max/sum 池化是实现降采样的最原始、最有效的方法,因为在池化窗口中计算 mean/max/sum 值非常快:

      hG=mean/max/sum(h1(K),,hn(K))

      其中 K 为最后一层图卷积层的编号(即一共 K 层图卷积层)。

      《Deep convolutional networks on graph-structured data》 表明:在网络开始时执行简单的max/mean 池化对于降低图域的维度、缓解昂贵的图傅里叶变换的成本尤为重要。

      另外,《Graph echo state networks》《Neural message passing for quantum chemistry》《On filter size in graph convolutional networks》 也是用注意力机制来改进 mean/sum 池化。

  3. 即使使用注意力机制,reduction 操作(如sum pooling )效果也不理想,因为它使得 embedding 低效 inefficient :无论图的尺寸 size 如何,都生成固定尺寸 fixed-sizeembedding

    《Order matters: Sequence to sequence for sets》 提出了 Set2Set 方法来生成一个随着输入尺寸而增加的 memory embedding 。然后它实现了一个 LSTM ,该 LSTM 试图在reduction 操作之前将order-dependent 信息集成到 memory embedding 中;否则销毁destroy 该信息。

  4. 《Convolutional neural networks on graphs with fast localized spectral filtering》 以另一种方式通过以有意义的方式重排图的节点来解决这个问题。他们在自己的方法 ChebNet 中设计了一种有效的池化策略:

    • 首先通过 Graclus 算法将输入图粗化为多个level
    • 粗化之后,输入图的节点及其粗化版本重排为为平衡二叉树。
    • 然后对平衡二叉树从底部到顶部任意聚合,这将使得相似的节点排列在一起。

    池化这种重排的信号要比池化原始信号有效得多。

  5. 《An end-to-end deep learning architecture for graph classification》 提出了 DGCNN,它具有类似的叫做 SortPooling 的池化策略,该策略通过将节点重排为有意义的顺序来执行池化。

    ChebNet 不同,DGCNN 根据节点在图中的结构角色对节点进行排序。来自空间图卷积的、图的无序的节点特征被视为连续的 WL colors ,然后将它们用于对节点进行排序。除了对节点特征进行排序外,它还通过截断/扩展truncating/extending 节点特征矩阵,从而将图的大小归一化为 q

    • 如果 n>q ,则原始特征矩阵最后 nq 行被截断。
    • 如果 n<q ,则原始特征矩阵添加 qn 行全零。
  6. 上述池化方法主要考虑图的特征而忽略图的结构信息。最近提出了一个可微的池化方法DiffPool,它可以生成图的层次 representation。和所有之前的粗化方法相比,DiffPool 不仅简单地将图上的节点聚类,而且还学习了第 k 层的聚类分配矩阵cluster assignment metrix S,记作 S(k)Rnk×nk+1 ,其中 nk 为第 k 层的节点数量。

    矩阵 S(k) 中的概率值是根据节点特征和拓扑结构来生成:

    S(k)=softmax(ConvGNNk(A(k),H(k)))

    其中:

    • A(k) 为第 k 层的邻接矩阵(粗化后的节点)。
    • H(k) 为第 k 层的节点 representation (粗化后的节点)。
    • ConvGNNk 为第 k 层采用的 ConvGNN

    该方法的核心思想是学习同时考虑图的拓扑结构和特征信息的节点分配 node assignment ,因此上式可以使用任何标准的 ConvGNN 实现(因为 ConvGNN 同时使用图的拓扑结构和特征信息)。但是 DiffPool 的缺点是在池化后会生成稠密图 dense graph,此后的计算复杂度变成 O(n2) (之前是 O(m) ) 。

  7. 最近提出了 SAGPool 方法,该方法同时考虑节点的特征信息和图拓扑结构信息,并以一种self-attention 的方式学习了池化。

  8. 总体而言,池化是减小图尺寸的基本操作。如何提高池化的有效性、降低计算复杂度是一个尚待研究的问题。

3.4.6 理论分析

  1. 我们从不同角度讨论图神经网络的理论基础。

  2. 感受野形状shape of receptive field:节点的感受野是有助于确定其final node representation 的一组节点。当组合多个空间图卷积层时,每新增一层,节点的感受野就会向更远的邻居前进一步。

    《Neural network for graphs: A contextual constructive approach》 证明:存在有限数量的空间图卷积层,使得对于任意节点 vV,节点 v 的感受野覆盖了图中所有的节点。结果 ConvGNN 能够通过堆叠局部的图卷积层来抽取全局信息。

  3. VC 维:VC 维是模型复杂度的度量,定义为模型能够打散 shattere 的最大样本数。

    分析 GNNVC 维的工作很少。 《The vapnik–chervonenkis dimension of graph and recursive neural networks》指出,给定模型参数数量 p 、图节点数量 n

    • 如果使用 sigmoid 或者tanh 激活函数,则GNN*VC 维为 O(p4n2)
    • 如果使用分段多项式激活函数,则GNN*VC 维为 O(p2n)

    该结果表明:如果使用 sigmoid 或者 tanh 激活函数,则 GNN* 的模型复杂度会随着 pn 的增加而迅速增加。

  4. 图同构 graph isomorphism :如果两个图在拓扑上相同,则它们是同构的。

    给定两个非同构non-isomorphicG1,G2《How powerful are graph neural networks 》 证明:如果GNNG1,G2 映射到不同的 embedding ,则可以通过 Weisfeiler-Lehman:WL 同构测试将这两个图识别为非同构的。他们表示:常见的 GNN(如 GCN,GraphSAGE) 无法区分不同的图结构。

    论文进一步证明:如果 GNN 的聚合函数和 readout 函数是单射 injective 的,则 GNN 在区分同构图的能力上最多和 WL test 一样。

    单射函数 f:若 abf(a)f(b)

  5. 等变性和不变性equivariance and invariance:执行 node-level 任务时,GNN 必须是等变函数 equivariant function ;而执行 graph-level 任务时,GNN 必须是不变函数 invariant function

    • 对于node-level 任务,令 f(A,X)Rn×d 为一个 GNNQ 为任意改变节点顺序的排列矩阵 permutation matrix (即单位矩阵 I 经过任意行变换、或列变换得到的矩阵)。如果满足 f(QAQ,QX)=Qf(A,X) ,则这个 GNN 是等变的 equivariant
    • 对于 graph-level 任务,令 f(A,X)Rd 为一个 GNN,如果满足 f(QAQ,QX)=f(A,X) ,则这个 GNN 是不变的 invariant

    为了实现等变性 equivariance 或不变性invarianceGNN 的组件components 必须满足对节点顺序是不变的invariant 。论文 《Invariant and equivariant graph networks》 从理论上研究了图数据的排列不变性permutation invariant 、排列等变性permutation equivariant 的线性层的特点。

  6. 通用逼近 universal approximation:众所周知,具有单层 hidden layerMLP 前馈神经网络可以逼近任何 Borel 可测函数。但是很少有人研究 GNN 的通用逼近能力。

    • 《Universal approximation capability of cascade correlation for structures》 证明级联相关cascade correlation 可以逼近结构化输出的函数。
    • 《Computational capabilities of graph neural networks》 证明RecGNN 可以逼近任何函数到任意精度,该函数保持展开等价性unfolding equivalence。如果两个节点的展开树 unfolding trees 相同,则这两个节点的展开等价。其中节点的展开树是通过以一定深度迭代扩展节点的邻域来构造的。
    • 《How powerful are graph neural networks》 表明:在消息传递框架下 ConvGNN 不是在多集合multisets上定义的连续函数的通用逼近器。
    • 《Invariant and equivariant graph networks》 证明了不变图网络 invariant graph network 可以逼近图上定义的任意不变函数invariant function

3.5 GAE

  1. 图自编码器Graph Autoencoder: GAE 是一种深度神经网络架构,可以将节点映射到潜在表示latent representation ,然后从潜在表示中解码图信息。

    GAE 可用于学习graph embedding 或者生成新图,下表总结了部分 GAE 的主要特点。下文中,我们从 graph embeddinggraph generation 角度简要概述了 GAE

3.5.1 Graph Embedding

  1. graph embedding 是节点的低维向量表示,可以保留节点的拓扑信息。GAE 使用编码器抽取graph embedding 、并使用解码器来强迫graph embedding 保留图拓扑信息(如PPMI 矩阵和邻接矩阵)从而学习 graph embedding

  2. 早期的方法主要采用多层感知机MLP 来构建用于学习 graph embeddingGAE

    • Deep Neural Network for Graph Representations:DNGR 使用堆叠的降噪自编码器 denoising autoencoder 通过MLP 来编码和解码 PPMI 矩阵。

    • 同时,Structural Deep Network Embedding:SDNE 使用堆叠自编码器来同时保存节点的一阶邻近度 first-order proximity 和二阶邻近度second-order proximitySDNE 在编码器输出和解码器输出上分别提出了损失函数。

      • 第一个损失函数针对编码器输出,通过最小化节点的 graph embedding 及其邻居的 graph embedding 之间的距离,来迫使学到的 graph embedding 保持节点的一阶邻近度。这个损失函数定义为:

        L1st=(v,u)EAv,uenc(xv)enc(xu)2

        其中:

        • xv=(Av,1,,Av,n) 为邻接矩阵 A 的第 v 行。
        • enc() 为多层感知机multi-layer perceptron:MLP 组成的编码器。
      • 第二个损失函数针对解码器输出,通过最小化自编码器输入及其重构的输出之间的距离,来迫使学到的 graph embedding 保留节点的二阶邻近度。这个损失函数定义为:

        L2nd=vV(dec(enc(xv))xv)bv2

        其中:

        • dec() 为多层感知机MLP 组成的解码器。

        • 为逐元素乘积,bv 定义为:

          bv,u={1, if Av,u=0β>1, if Av,u=1

          这迫使模型更关注相连节点的损失。

        这里自编码器的输入为节点的邻接向量,因此重构节点的邻接向量意味着保持节点的邻域,即二阶邻近度。

  3. DNGRSDNE 仅考虑和节点pair 对之间的连通性有关的节点结构信息,他们忽略节点可能包含描述节点本身属性的特征信息。《Variational graph auto-encoders》 提出了Graph Autoencoder (记作 GAE* 以示区分)来利用 GCN 同时编码节点结构信息和节点特征信息。

    GAE* 的编码器由两个图卷积层组成,其形式为:

    Z=enc(X,A)=Gconv(f(Gconv(A,X;Θ1));Θ2)

    其中:

    • Z 表示图的 graph embedding 矩阵。
    • f() 为非线性激活函数,如 ReLU
    • Gconv()H=XGgΘ=f(A¯XΘ) 定义的图卷积层。

    GAE* 的解码器旨在通过重构图邻接矩阵,从而从节点的 embedding 中解码节点之间的关系信息。解码器定义为:

    A^v,u=dec(zv,zu)=σ(zvzu)

    其中 zv 为节点 vembedding

    GAE* 通过最小化给定真实邻接矩阵 A 和重构的邻接矩阵 A^ 之间的负交叉熵negative cross entropy 来训练。

  4. 由于自编码器的容量capacity ,简单地重构图邻接矩阵可能会导致过拟合。《Variational graph auto-encoders》 同时提出了变分图自编码器Variational Graph Autoencoder:VGAE ,它是GAE 的变分版本,用于学习数据分布。

    VGAE 优化变分下限 L

    L=Eq(ZX,A)[logp(AZ)]KL[q(ZX,A)||p(Z)]

    其中:

    • KL(.)KL 散度函数,用于衡量两个分布之间的距离。

    • p(Z) 为一个高斯先验分布,其中:

      p(Z)=i=1np(zi)=i=1nN(zi0,I)
    • p(Ai,j=1zi,zj)=dec(zi,zj)=σ(zizj)

    • q(ZX,A)=i=1nq(ziX,A)q(ziX,A)=N(ziμi,diag(σi2)) 。其中:高斯分布均值向量 μi 为一个编码器输出的第 i 行;logσi 类似于 μi ,它是另一个编码器的输出。

    根据上述公式,VGAE 假设经验分布 q(ZX,A) 应该和先验分布 p(Z) 尽可能接近。

    损失函数的第一项要求最大后验分布,第二项要求经验分布 q(ZX,A) 应该和先验分布 p(Z) 尽可能一致。

  5. 为进一步强制经验分布 q(ZX,A) 逼近于先验分布 p(Z) ,对抗正则变分图自编码器Adversarially Regularized Variational Graph Autoencoder:ARVGA 采用了生成对抗网络generative adversarial network:GAN 的方案。

    GAN 在训练生成模型时会在生成器 generator 和判别器 discriminator 之间进行竞争比赛:生成器试图生成尽可能真实的 fake 样本,而判别器试图将fake 样本和真实样本区分开。

    GAN 的启发,ARVGA 努力学习一种编码器,该编码器产生的经验分布 q(ZX,A) 和先验分布 p(Z) 难以区分。

  6. 类似于 GAE*GraphSAGE 用两个图卷积层编码节点特征。GraphSAGE 并没有优化重建损失,而是表明两个节点之间的关系信息可以通过负采样来保留,其损失函数为:

    L(zv)=log(dec(zv,zu))QEvnPn(v)[log(dec(zv,zvn))]

    其中:

    • 节点 u 是节点 v 的邻居节点,节点 vn 是远离节点 v 的节点并且从负采样分布negative sampling distribution Pn(v) 中采样得到。
    • Q 为节点 v 负采样的 “负节点” 数量。

    该损失函数本质上是迫使相邻的节点具有相似的representation、距离遥远的节点具有不同的 representation

  7. DGIGraphSAGE 不同,它通过最大化局部互信息local mutual information 来驱动局部网络 embeddinglocal network embedding )来捕获全局结构信息。从实验上看,它比 GraphSAGE 有明显改进。

  8. 上述方法本质上是通过解决链接预测问题来学习 graph embedding。但是,图的稀疏性导致 postive 节点 pair 对的数量远远少于 negative 节点 pair 对的数量。

    为缓解学习graph embedding 中的数据稀疏性问题,另一个方向的工作通过随机排列或随机游走将图转换为序列。通过这种方式,一些适用于序列的深度学习方法可以直接用于处理graph

    Deep Recursive Network Embedding:DRNE 假设节点的 graph embedding 应该近似于它邻域节点 embedding 的聚合。它采用 LSTM 来聚合节点的邻域 embeddingDRNE 的重构误差定义为:

    L=vVzvLSTM({zuuNv})2

    其中:

    • zv 为节点vembedding,它直接通过一个字典 look-up 得到。
    • 节点 v 邻居的随机序列并经过 degree 排序后作为 LSTM 网络的输入。

    如公式所示,DRNE 通过 LSTM 来隐式学到 graph embedding ,而不是直接使用 LSTM 来生成 graph embedding 。它避免了 LSTM 对于节点序列的排列不是不变 invariant 的问题。

  9. 对抗正则化自编码器Adversarially Regularized Autoencoder:NetRA 提出一个带通用损失函数的graph encoder-decoder 框架。其损失函数定义为:

    L=EzPdata(z)(dist(z,dec(enc(z))))

    其中:

    • dist(.) 为节点 embedding z 和重构的embedding dec(enc(z)) 之间的距离。
    • enc(.)dec(.) 分别为编码器和解码器。它们都是 LSTM 网络,使用以节点 vV 为根节点的随机游走序列作为输入。

    类似于 ARVGANetRA 通过对抗训练将学到的 graph embedding 正则化到先验分布中。尽管 NetRA 忽略了 LSTM 网络中节点的排列不变性的问题,但实验结果验证了 NetARA 的有效性。

3.5.2 Graph Generation

  1. 给定多个图,GAE 通过将图编码为hidden representation 并根据这个representation 解码图结构,从而可以学到图的生成分布generative distribution。大多数图生成的 GAE 旨在解决分子图molecular graph 生成问题,这在药物发现中具有很高的实用价值。这些方法要么以顺序方式sequential manner 、要么以全局方式 global manner生成一个新的图。

  2. 顺序方式通过逐步生成节点和边来生成图。

    • 《Automatic chemical design using a data-driven continuous representation of molecules》《Grammar variational autoencoder》《Syntax-directed variational autoencoder for molecule generation》 用深度 CNN 作为编码器、深度 RNN 作为解码器,对名为 SMILES 的分子图字符串的生成过程建模。

      尽管这些方法是domain-specific,但是它们通过将节点、边迭代地添加到图上直到满足特定条件为止,从而可以适用于一般的图生成。

    • Deep Generative Model of Graphs:DeepGMG 假设图的概率是所有可能的节点排列之和:

      p(G)=πp(G,π)

      其中 π 表示一种节点排列顺序。

      DeepGMG 捕获图中所有节点和边的、复杂的联合概率。

      DeepGMG通过做出一系列决策来生成图,即:是否添加节点、添加哪个节点、是否对这个新节点添加边、这个新节点连接到哪个节点。生成节点和边的决策过程取决于这个不断增长growing 图的节点状态和图状态,其中节点状态和图状态通过 RecGNN 来更新。

    • 在另一项工作中,GraphRNN 提出一个 graph-levelRNN 以及一个 edge-levelRNN 来建模节点和边的生成过程。每次 graph-level RNN 都会向节点序列中添加一个新的节点,而 edge-level RNN 生成一个binary sequence ,它指示新节点和节点序列中之前生成的节点之间的连接。

  3. 全局方式可以一次性生成整个图。

    • 图变分自编码器Graph Variational Autoencoder:GraphVAE 将节点和边的存在建模为独立随机变量。通过假设后验分布posterior distribution qϕ(zG) (它由编码器定义)、生成分布generative distribution pθ(Gz) (它由解码器定义),GraphVAE 优化变分下界:

      L(ϕ,θ;G)=Eqϕ(zG)[logpθ(Gz)]+KL[qϕ(zG)||p(z)]

      其中:

      • p(z) 为服从高斯分布的先验分布。
      • ϕ,θ 为待学习的参数。

      使用 ConvGNN 作为编码器、使用简单的MLP 作为解码器,GraphVAE 输出生成的图及其邻接矩阵、节点属性、边属性。

    • 控制生成图的全局属性(如图的连接性connectivity、有效性 validity,以及节点兼容性 compatibility)具有挑战性。正则化图变分自编码器Regularized Graph Variational Autoencoder:RGVAE 进一步在图变分自编码器上施加了有效性约束 validity constraint ,从而正则化解码器的输出分布。

    • 分子生成对抗网络 Molecular Generative Adversarial Network:MolGAN 整合了 ConvGNNGAN 、以及强化学习技术从而生成具有所需特性的图。

      MolGAN 由生成器和判别器组成,它们相互竞争从而提高生成器的真实性 authenticity 。在 MolGAN 中,生成器试图提出一个 fake 图及其特征矩阵,而判别器目标是将 fake 数据和真实数据中区分开。

      另外,引入了和判别器并行的奖励网络,从而鼓励生成的图具有某些特性。

    • NetGANLSTMWasserstein GAN 结合起来,通过基于随机游走的方法生成图。NetGAN 训练生成器通过 LSTM 网络生成合理的随机游走,并强迫判别器从真实的随机游走中识别 fake 随机游走。

      训练好之后,通过归一化基于生成器产生的随机游走而计算得到的节点共现矩阵,从而得到新的图。

  4. 总之:

    • 顺序方式将图线性化为序列。由于存在环结构,因此它们可能会丢失结构信息。
    • 全局方式可以一次性生成一个图。由于 GAE 的输出空间可达 O(n2),因此它不是可扩展的 scalable

3.6 SPATIAL-TEMPORAL GNN

  1. 在很多实际应用中,图在结构和输入方面都是动态的。时空图神经网络patial-temporal graph neural network: STGNN 在捕获图的动态性中占据重要位置。该类别下的方法旨在建模动态的节点输入,同时假设已连接节点之间的相互依赖性。

    STGNN 假设图的结构不变,需要建模的是节点的动态属性。

    例如,交通网络由放置在道路上的速度传感器组成,其中传感器之间的边的权重由传感器之间距离决定。由于一条道路的交通状况可能取决于其相邻道路的交通状况,因此执行交通速度预测时,必须考虑空间依赖性。作为解决方案,STGNN 可以同时捕获图的空间依赖性和时间依赖性。

    STGNN 的任务可以是预测节点未来的值或标签,或者预测时空图的 graph label

  2. STGNN 有两个方向,即:基于 RNN 的方法RNN-based method、基于 CNN 的方法CNN-based method

3.6.1 Rnn-based

  1. 大多数基于 RNN 的方法通过使用图卷积来过滤传递给 RNN 单元的 inputhidden state 来捕获时空依赖性。为了说明这一点,假设一个简单的 RNN 采用以下形式:

    H(t)=σ(WX(t)+UH(t1)+b)

    其中:

    • X(t)Rn×d 为节点在时刻 t 的特征矩阵。
    • H(t)Rn×dh 为节点在时刻 trepresentation 矩阵。
    • σ() 为非线性激活函数。

    在插入图卷积之后,上式变为:

    H(t)=σ(GConv(X(t),A;W)+GConv(H(t1),A;U)+b)

    其中 GConv(.) 为一个图卷积层。

  2. 图卷积递归网络 Graph Convolutional Recurrent Network:GCRN 结合了 LSTM 网络和 ChebNet

  3. 扩散卷积递归神经网络Diffusion Convolutional Recurrent Neural Network:DCRNN 将扩散图卷积层(H=k=0Kf(PkXW(k)))整合到 GRU 网络中。此外,DCRNN 采用 encoder-decoder 框架来预测未来 K 步的节点值。

  4. 另一项同时进行的工作使用 node-level RNNedge-level RNN 来处理时间信息的不同方面aspect

    Structural-RNN 提出了一个循环框架来预测每个time step 的节点标签。它包含两种 RNN,即:

    • node-RNN :用于传递每个节点的时间信息。
    • edge-RNN :用于传递每条边的时间信息。

    为整合空间信息,node-RNNedge-RNN 的输出作为输入。

    由于为不同的节点和边采用不同的 RNN 会大大增加模型的复杂度,因此 Structural-RNN 将节点和边进行语义分组semantic group。相同语义组中的节点或边共享相同的 RNN 模型,从而降低计算成本。

3.6.2 CNN-based

  1. 基于 RNN 的方法存在耗时的迭代传播、以及梯度爆炸/消失问题。作为替代方案,基于 CNN 的方法以非递归的方式处理时空图,具有计算并行、梯度稳定、内存需求低等优点。

  2. 基于 CNN 的方法将 1D-CNN 层和图卷积层交织从而分别学习时间依赖性和空间依赖性。

    假设时空图神经网络的输入为张量 XRT×n×d

    • 1D-CNN 层在 X[:,i,:] 上沿着时间轴滑动,从而聚合每个节点的时间信息。

      给定空间,聚合时间。

    • 而图卷积层在 X[t,:,:] 上运行从而聚合每个时间步的空间信息。

      给定时间,聚合空间。

  3. CGCN 将一维卷积层与 ChebNetGCN 层整合在一起。它通过按顺序堆叠一个门控 1D 卷积层、一个图卷积层、另一个门控 1D 卷积层,从而构成时空块 spatial-temporal block

  4. ST-GCN 使用 1D 卷积层和 PGC 层(H(l)=q=1QA¯(q)H(l1)W(q,l))构成时空块。

  5. 之前的方法都使用预定义的图结构,他们假设预定义的图结构反映了节点之间的真正依赖关系。

    但是,利用 spatial-temporal setting 中的很多图数据快照,可以从数据中自动学习潜在的静态图结构。为了实现这一点,Graph WaveNet 提出了一种自适应邻接矩阵来执行图卷积。自适应的邻接矩阵定义为:

    Aadp=Softmax(ReLU(E1E2))

    其中:

    • Softmax(.) 函数沿着行维度进行。
    • E1 表示source 节点 embedding
    • E2 表示 target 节点 embedding

    通过将 E1 乘以 E2 ,可以得到 source 节点和 target 节点之间的依赖关系权重。借助基于 CNN 的复杂时空网络,Graph WaveNet 无需提供邻接矩阵即可表现良好。

  6. 学习潜在的静态空间依赖性可以帮助研究人员发现网络中不同实体之间可解释的、稳定的相关性。但是,某些情况下,学习潜在的动态空间依赖性可以进一步提高模型的精度。例如,在交通网络中,两条道路之间的通行时间travel time 可能取决于它们当前的交通状况。

    • GaAN 利用注意力机制通过基于 RNN 的方法学习动态空间依赖性。注意力函数用于在给定这个边的两个节点的节点输入的情况下,更新边的权重。
    • ASTGCN 进一步包括空间注意力函数和时间注意力函数,从而通过基于 CNN 的方法学习潜在的动态空间相关性和动态时间相关性。

    学习潜在空间相关性的共同缺点是,它需要计算每对节点 pair 对之间的空间相关性权重,计算复杂度为 O(n2)

3.7 应用 & 方向

  1. 由于图结构数据无处不在,因此 GNN 有广泛的应用。这里我们分别总结了 benchmark 图数据集、评估方法、开源实现。我们还详细介绍了 GNN 在各个领域的实际应用。

  2. 数据集:我们将主要的图benchmark 数据集分为四类,即引文网络citation network、生化图biochemical graph、社交网络social network 以及其它。我们在下表给出了这些数据集的统计信息。

    • 引文网络:由论文、作者、以及它们之间的关系(如引用citation、作者、合著等关系)组成。尽管引文网络是有向图,但是评估节点分类、链接预测、节点聚类等任务的模型性能时,引文网络通常被视为无向图。

      流行的引文网络数据集有:

      • Cora数据集:包含 2708 篇机器学习论文组成,分为七个类别。每篇论文都由一个文章单词的 one-hot 向量表示,表示对应的单词是否出在论文中。
      • Citeseer数据集:包含 3327 篇科学论文,分为六个类别。每篇论文都由一个文章单词的 one-hot 向量表示,表示对应的单词是否出在论文中。
      • Pubmed数据集:包含 19717 篇与糖尿病有关的论文。每篇论文都由单词的 TF-IDF 向量来表示。
      • DBLP 数据集:包含数百万计算机科学论文及其作者,是一个大型的引文网络数据集。
    • 生化图:化学分子和化合物可以用化学图chemical graph 表示,原子为节点、化学键为边。

      • NCI-1NCI-9 数据集:分别包含 41104127 个化学化合物,标记它们是否具有活性以阻止人类癌细胞系的生长。
      • MUTAG数据集:包含188 种硝基化合物,分别标记它们是芳香族还是杂芳香族。
      • D&DPROTEIN数据集:将蛋白质表示为图,标记它们是酶还是非酶。
      • PTC 数据集:包含 344 种化合物,标记它们对雄性和雌性大鼠是否具有致癌性。
      • QM9数据集:记录最多含 9 个重原子的 133885 个分子的 13 个物理特性。
      • Alchemy 数据集:记录最多含 14 个重原子的 119487 个分子的 12 个量子力学特性。

      另一个重要的数据集是 ProteinProtein Interaction network:PPI数据集:包含 24个生物学图biological graph ,其中节点表示蛋白质,边表示蛋白质之间的相互作用。在 PPI 中,每个图都与一个人体组织相关联。每个节点的标签都是其生物学状态。

    • 社交网络:由在线服务(如 BlogCatalogReddit)的用户交互形成。

      • BlogCatalog数据集:一个由博客作者及其社交关系组成的社交网络。博客作者的类别代表他们的个人兴趣。
      • Reddit数据集:从 Reddit 论坛收集的帖子形成的无向图。如果两个帖子包含同一个用户的讨论,则帖子之间存在链接。每个帖子都有一个标签,标记其所属社区community
    • 其它:还有几个其它数据集值得一提:

      • MNIST数据集:包含 7000028 x 28 的图像,标记为 0~9 之间的十个数字。它是经典的手写数字识别数据集。

        我们可以基于像素位置构造一个 8-nearest-neighbor 图,从而将图片转换为 graph

      • METR-LA数据集:一个时空图数据集。它包含洛杉矶高速公路上的 207 个传感器收集的四个月的交通数据。通过具有高斯阈值的sensor network distance 来计算图的邻接矩阵。

      • NELL数据集:从 Never-Ending Language Learning 项目获得的知识图谱。它由三元组表示的fact 组成,其中涉及两个实体及其关系。

  3. 节点分类和图分类是评估 RecGNNConvGNN 性能的常用任务。

    • 节点分类:在节点分类中,大多数方法采用对 benchmark 数据集(包括 Cora,Citeseer,Pubmed,PPI,Reddit)进行标准的train/valid/test 划分。它们报告了多次运行测试数据集的平均准确率或 F1 得分,我们在下表给出了这些方法的实验结果的摘要。

      注意,这些结果不一定表示严格的比较。《Pitfalls of graph neural network evaluation》 指出,GNN 在节点分类任务的性能评估有两个陷阱:

      • 首先,在所有实验中使用相同的train/valid/test 划分会低估泛化误差。
      • 其次,不同的方法采用了不同的训练技术,如超参数调优、参数初始化、学习率衰减、早停技术。

      为了进行公平的比较,我们建议读者阅读论文 《Pitfalls of graph neural network evaluation》

    • 图分类:在图分类任务中,研究人员通常采用 10-fold 交叉验证进行模型评估。

      然而,正如 《A fair comparison of graph neural networks for graph classification》 所指出的,实验设置是模棱两可的ambiguous,并且在不同论文之间没有统一。具体而言,该论文抛出了在模型选择、模型评估方面对于数据集正确拆分的关注。一个经常遇到的问题是:每个 fold 的外部测试集都用于模型选择和风险评估。该论文在标准的、统一的评估框架中比较 GNN。他们使用一个external10-fold 交叉来评估模型的泛化性能,并使用一个内部holdout 技术(具有 90%/10%train/valid 拆分)来选择模型。

      另一种方法是双交叉方法,该方法使用外部的 k-fold 交叉验证进行模型评估,使用内部的 k-fold 交叉验证进行模型选择。可以阅读该论文从而详细比较 GNN 方法的图分类任务性能。

  4. 开源实现:我们在下表中给出了本文涉及到的 GNN 模型的开源实现的超链接。另外,PyTorch 有一个 PyTorch Geometirc 的库,它实现了很多 GNN;而 Deep Graph Library:DGL 也提供了很多 GNN 的快速实现。

  5. GNN 在不同的任务、不同领域中都具有很多应用,这些任务包括节点分类、图分类、graph embedding、图生成、时空图预测、节点聚类、链接预测、图聚类。我们基于以下研究领域详细介绍了一些应用。

    • 计算机视觉Computer visionGNN 在计算机视觉中的应用包括场景图生成scene graph generation、点云分类point clouds classification、动作识别action recognition

      • 识别对象之间的语义关系有助于理解视觉场景背后的含义。场景图生成模型旨在将图像解析为由对象及其语义关系组成的语义图semantic graph

        另一类应用通过给定场景图生成逼真的图像来执行场景图生成的逆向过程。由于自然语言可以解析为语义图,其中每个单词代表一个对象,因此对于给定文字说明的图像合成方法是一种很有前途的解决方案。

      • 通过对点云进行分类classifying 和分段segmentingLiDAR 设备可以 “看到” 周围的环境。点云是通过 LiDAR 扫描记录的一组 3D 点。

        《Dynamic graph cnn for learning on point clouds》《Large-scale point cloud semantic segmentation with superpoint graphs》《Rgcnn: Regularized graph cnn for point cloud segmentation》 将点云转换为 k 近邻图或者超点图 superpoint graph ,并使用 ConvGNN 探索拓扑结构。

      • 识别视频中包含的人的行为可以有助于机器更好地理解视频内容。一些解决方案可以检测视频中人体关节的位置,由骨骼链接的人体关节自然会形成图。给定人体关节位置的时间序列,《Structural-rnn:Deep learning on spatio-temporal graphs》《Spatial temporal graph convolutional networks for skeleton-based action recognition》STGNN 用于学习人类行为模式。

        此外,计算机视觉中 GNN 的适用方向数量仍在增长,它包括:human-object 交互、few-shot 图片分类、语义分割semantic segmentation 、视觉推理visual reasoning 、知识问答。

    • 自然语言处理 NLPGNNNLP 中常见的应用是文本分类。GNN 利用文档或单词的内部关系来推断文档标签。尽管自然语言数据表现出序列结构,但是它们也可能包含图结构,如语法树。语法树定义了句子中单词之间的句法关系。

      《Encoding sentences with graph convolutional networks for semantic role labeling》 提出了运行在 CNN/RNN 句子编码器之上的Syntactic GCN。它根据句子的语法依存关系树syntactic dependency tree 聚合隐藏的单词representation

      《Graph convolutional encoders for syntax-aware neural machine translation》Syntactic GCN 应用于neural machine translation 任务。

      《Exploiting semantics in neural machine translation with graph convolutional networks》 进一步采用Syntactic GCN 相同的模型来处理句子的语义依赖图 semantic dependency graph

      graph-to-sequence learning 学习在给定摘要单词语义图a semantic graph of abstract words 条件下生成具有相同含义的句子,称作 Abstract Meaning Representation

      《A graph-to-sequence model for amr-to-text generation》 提出了一种 graph-LSTM 来编码 graph-level 语义信息。

      《Graph-to-sequence learning using gated graph neural networks》GGNN 应用到 graph-to-sequence learning 以及 neural machine translation

      逆任务是sequence-to-graph learning。给定一个句子生成语义图或知识图在知识发现knowledge discovery 中非常有用。

    • 交通:在智能交通系统中,准确预测交通网络中的交通速度、交通流量、道路密度至关重要。

      《Gaan: Gated attention networks for learning on large and spatiotemporal graphs》《Diffusion convolutional recurrent neural network: Data-driven traffic forecasting》《Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting》 使用 STGNN 解决了交通预测问题。他们将交通网络视为时空图,其中节点是安装在道路上的传感器,边的权重是成对节点之间的距离。每个节点具有窗口内的平均交通速度作为动态输入特征。

      另一个工业级应用是出租车需求预测。给定历史的出租车需求、位置信息、天气数据、事件event 特征,《Deep multi-view spatial-temporal network for taxi demand prediction》 结合了LSTM,CNN 以及 LINE 训练的 graph embedding 从而形成每个位置的联合representation,以预测某个时间间隔内、某个位置所需的出租车数量。

    • 推荐系统:基于图的推荐系统将 itemuser 作为节点。通过利用 item-itemuser-useruser-item 以及内容信息之间的关系,基于图的推荐系统可以生成高质量的推荐。

      推荐系统的关键是评估 user 对于 item 的重要性得分,这可以转换为链接预测问题。为了预测 useritem 之间缺失的链接,《Graph convolutional matrix completion》《Graph convolutional neural networks for web-scale recommender systems》 提出了一种使用 ConvGNN 作为编码器的 GAE《Geometric matrix completion with recurrent multi-graph neural networks》RNN 和图卷积相结合,以学习生成已知评级rating 的底层过程 underlying process

    • 化学:在化学领域,研究人员应用 GNN 来研究分子/化合物的图结构。在分子/化合物图中,节点为原子、边为化学键。

      节点分类、图分类、图生成是针对分子/化合物图的三个主要任务,目的是学习分子指纹、预测分子特性、推断蛋白质interface、合成化合物。

    • 其它:GNN 的应用不限于上述领域和任务。已有研究者使用 GNN 对各种问题进行探索探索,如程序验证program verification、程序推理program reasoning、社交影响力预测social influence prediction、对抗攻击和预防adversarial attacks prevention、电器健康记录建模electrical health records modeling 、大脑网络brain network 、事件检测event detection 、组合优化combinatorial optimization 等。

  6. 尽管 GNN 已经证明它在学习图数据方面的能力,但是由于图的复杂性,仍然存在挑战。我们这里提出 GNN 四个未来的发展方向:

    • 模型深度:深度学习的成功在于较深的神经网络体系架构,但是 《Deeper insights into graph convolutional networks for semi-supervised learning》 表明:ConvGNN 的性能随着图卷积层数量的增加而急剧下降。由于图卷积将相邻节点的 representation 推向彼此靠近,理论上如果卷积层数量无穷,则所有节点的 representation 都将收敛到一个点。这就提出了一个问题:即更深的模型是否仍然是学习图数据的好策略?

    • 扩展性trade-offGNN 的可扩展性scalability 是以破坏图完整性completeness 为代价的。无论是采样还是聚类,模型都会丢失部分图信息。

      • 通过采样,节点可能会错过它的有影响力的邻居。
      • 通过聚类,可能丢失图的独有的结构模式。

      如何权衡算法的可扩展性和图的完整性可能是未来的研究方向。

    • 异质性 Heterogenity:当前的大多数GNN 假设图为同质图homogeneous 。难以将当前的 GNN 直接应用于异质图,因为异质图可能包含不同类型的节点和边,或者不同形式的节点输入、边输入(如图像和文本)。因此,应该设计新的方法来处理异质图。

    • 动态性Dynamicity:图在本质上是动态的,因为节点或边可能出现或消失,并且节点/边的输入可能会随着时间变化。需要新的图卷积从而适应图的动态性。虽然 STGNN 可以部分解决图的动态问题,但是很少有人考虑在动态空间关系的情况下如何执行图卷积。