图结构学习 Graph Structure Learning

本文翻译自该章节¹。

简介

GNN 目前强大的表达能力是基于图结构数据的可用性以及质量，但这一依赖反而给图的表征学习带来了挑战。在现实场景中，

• 对于已经有结构信息的图数据：由于数据测量或收集不可避免地存在误差，真实的图拓扑结构往往是有噪声或不完整的；内在的图拓扑结构可能仅仅代表物理连接（如分子中的化学键），而不能捕捉顶点之间的抽象或隐含关系，而这种关系对某些下游预测任务是有益的。
• 现实中的数据现成的图结构可能不存在：如自然语言处理或计算机视觉中的应用，数据的图表示（例如，文本数据的文本图或图像的场景图）可能不存在。

但是早期的 GNN 方法严重依赖于图的结构，以便获得更好的表征性能。

因此，有许多工作开始关注于图结构学习（Graph Structure Learning）。图结构学习旨在从数据中发现有用的图结构，以便用GNN进行更好的图表示学习。

实际上，在 GNN 之前，有很多工作已经在传统机器学习领域对图结构的学习进行了广泛探索，而且也有许多最初为传统图结构学习而开发的技术被重新审视并引入用于改善GNN的图结构学习。因此我们首先来关注传统机器学习领域里图结构学习的方法。

传统的图结构学习

无监督方法

图结构学习在图信号处理（GSP）的文献中得到了广泛的研究。它在文献中通常被称为图学习问题，其目标是以无监督的方式从定义在图上的平滑信号中学习拓扑结构。

图形信号被定义为给图形的每个顶点分配一个标量值的函数，定义为$X \in \mathbb{R}^{n \times d}$，每个顶点的信号$X_i \in \mathbb{R}^d$就是一个$d$纬的向量，目标就是学习一个邻接矩阵$A \in \mathbb{R}^{n \times n}$。

这些方法典型的操作是通过解决一个优化问题，并对图的属性（如平滑性、稀疏性）进行某些先验约束。在此，我们介绍一些定义在图上的代表性先验约束，这些约束已被广泛用于解决图学习问题。

• 适应度 Fitness。利用每个数据点的邻域信息进行图的构建。例如最小化以下目标：

  \[\sum_i\left\|X_i-\sum_j A_{i, j} X_j\right\|^2\]

  其中$\sum_j A_{i, j}=1, A_{i, j} \geq 0$。就是目标节点信号更接近于适应（接近）其邻居的信号。

• 平滑度 Smoothness。图信号的平稳性通常由 Dirichlet 能量衡量：

  \[\Omega(A, X)=\frac{1}{2} \sum_{i, j} A_{i, j}\left\|X_i-X_j\right\|^2=\operatorname{tr}\left(X^{\top} L X\right)\]

  这迫使相邻的顶点具有相似的信号，从而迫使图形信号在学习的图形上平稳地变化。

• 连接性和稀疏性 Connectivity and Sparsity。最小化上面平滑度的式子，可能会导致一个解就是 $A=0$。通过限制连通性和稀疏性可以解决这个问题。

有监督方法

• 交互系统的关系推理旨在研究复杂系统中的对象如何相互作用。早期的工作考虑了一个固定的或全连接的交互图，同时对对象之间的交互动态进行建模。Sukhbaatar等人提出了一个神经模型来学习动态变化的代理集之间的连续通信，其中通信图随着代理的移动、进入和退出环境而变化。

  最近的工作是为了同时推断潜在的交互图和建立交互动态模型。Kipf等人提出了一种基于变异自动编码器（VAE）的方法，该方法以无监督的方式从物理对象的观察轨迹中同时学习推断交互图结构和建立交互动力学模型。VAE的离散潜伏代码代表潜伏交互图的边缘连接，编码器和解码器都采取GNN的形式来模拟物体间的交互动态。

• 贝叶斯网络（BN）是一种概率图解模型（PGM），它通过有向无环图（DAG）对随机变量之间的条件依赖进行编码，每个随机变量在DAG中被表示为一个节点。在贝叶斯网络研究中，学习BN结构的问题很重要，但也很有挑战性。大多数现有的关于BN学习的工作集中在基于分数的DAG学习上，目的是找到一个具有最大分数的DAG，分数表示任何候选DAG被观察到的数据（和任何先验知识）支持的程度。早期的工作将BN学习视为一个组合优化问题，由于DAG的搜索空间随着节点数量的超指数增长而难以解决，因此是NP-hard。一些有效的方法已经被提出，通过动态编程（Koivisto和Sood，2004；Silander和Myllym¨aki，2006）或整数编程（Jaakkola等人，2010；Cussens，2011）进行精确的BN学习。最近，Zheng等人（2018b）提出将传统的组合优化问题表述为实数矩阵上的纯连续优化问题，该问题具有平滑的平等约束，确保了图的非周期性。因此，所产生的问题可以通过标准的数字算法有效解决。

GNN 中的图结构学习

目前这一研究方向的最新尝试主要集中在图结构和表征的联合学习上，而不需要借助于人的努力或领域的专业知识。图14.1显示了GNN的图结构学习的概况。此外，我们看到近年来正在积极研究的几个重要问题（包括图生成、图对抗性防御和变换器模型）与GNN的图结构学习密切相关。我们将在本节中讨论它们的联系和区别。

主要分成两大类：学习离散图结构和学习加权邻接矩阵。

考虑到离散图结构学习往往有非微分采样操作带来的优化困难，因此很难学习边上的权重，另一种方法是着重于学习与加权图相关的加权（通常是稀疏的）邻接矩阵，该矩阵将被随后的GNN用于预测任务。

问题描述

图 $\mathscr{G}=(\mathscr{V}, \mathscr{E})$ 有节点 $v_i \in \mathscr{V}$ 以及节点的原始表征 $X \in \mathbb{R}^{n \times d}$。可能有边 $\left(v_i, v_j\right) \in \mathscr{E}$ ，有一个带噪声的邻接矩阵$A^{(0)} \in \mathbb{R}^{n \times n}$。

输入：是原始的噪声图 $\mathscr{G}:={A^{(0)}, X}$ 或者仅有节点表征 $X \in \mathbb{R}^{n \times d}$ 。

输出：优化后的图 \(\mathscr{G}^*:=\{A^{(*)}, X\}\) ，以及对应新的节点表征 $Z=f(\mathscr{G}^*, \theta) \in \mathbb{R}^{h \times n}$ 。

其中 $f$ 是 GNN，$\theta$ 是模型。

学习离散的图结构

为了处理图的不确定性问题，许多现有的关于学习离散图结构的工作将图结构视为一个随机变量，其中离散图结构可以从某些概率性的邻接矩阵中取样。

学习加权图结构

首先，优化加权邻接矩阵比优化二元邻接矩阵要容易得多，因为前者可以通过SGD技术（甚至凸优化技术轻松实现，而后者由于其非差异性，往往要借助于更具挑战性的技术，如变分推理、强化学习和组合优化技术。

其次，与二元邻接矩阵相比，加权邻接矩阵能够编码更丰富的边的信息，这可能有利于后续的图表示学习。

在本小节中，我们将首先介绍一些常见的图相似性度量学习技术以及现有工作中广泛使用的图稀疏化技术，通过考虑嵌入空间中成对的节点相似性来学习稀疏加权图。稍后将介绍一些有代表性的图正则化技术，以控制所学图结构的质量。然后，我们将讨论结合内在的图结构和学习到的隐含图结构对提高学习性能的重要性。最后，我们将介绍一些重要的学习范式，用于联合学习图结构和图表示，这些范式已经被现有的工作成功地采用。

1. 图形相似性度量学习技术

   正如前面所介绍的，先前关于从平滑信号中学习无监督图结构的工作也旨在从数据中学习加权邻接矩阵。然而，它们无法处理在推理阶段存在未见过的图或节点的归纳学习环境。这是因为它们通常是通过直接优化基于图形属性的某些先验约束的邻接矩阵进行学习。由于类似的原因，许多关于离散图结构学习（第14.3.1.2节）的工作也难以进行归纳学习。

   最近的许多文献工作假设节点属性或多或少包含推断图的隐性拓扑结构的有用信息，因此将图结构学习作为定义在节点嵌入空间上的相似度量学习。这种策略的一个最大优点是，学到的相似性度量函数以后可以应用于未见过的节点嵌入集来推断图结构，从而实现归纳图结构学习。

   也分为两种方法：基于节点嵌入的相似度量学习和结构感知的相似度量学习。

   • 基于节点嵌入的相似度量学习

     基于节点嵌入的相似性度量学习函数被设计用来学习基于节点嵌入的成对节点相似性矩阵，这些节点嵌入理想地编码了节点的重要语义，用于图结构学习。

     • Attention-based

       例如以下每一个式子。方法非常多，核心思想就是利用 pair-wise 节点来学习节点相似性矩阵$S_{i,j}$：

       \[\begin{gathered}S_{i, j}=\vec{v}_i^{\top} \vec{v}_j \\S_{i, j}=\left(\vec{v}_i \odot \vec{u}\right)^{\top} \vec{v}_j \\S_{i, j}=\operatorname{ReLU}\left(W \vec{v}_i\right)^{\top} \operatorname{ReLU}\left(W \vec{v}_j\right) \\S_{i, j}=\operatorname{ReLU}\left(f\left(\vec{v}_i\right)^{\top} f\left(\vec{v}_j\right)\right) \\S_{i, j}=\frac{\left(\operatorname{ReLU}\left(\left(W_1 \vec{v}_i\right)^{\top} W_2 \vec{v}_j+b\right)^2\right.}{\sum_k\left(\operatorname{ReLU}\left(\left(W_1 \vec{v}_k\right)^{\top} W_2 \vec{v}_j+b\right)^2\right.} \\S_{i, j}=\operatorname{softmax}\left(\left(W_1 \vec{v}_i\right)^{\top} W_2 \vec{v}_j\right)\end{gathered}\]

     • Cosine-based 余弦

       例如：

       \[\begin{aligned}S_{i, j}^p & =\cos \left(\vec{w}_p \odot \vec{v}_i, \vec{w}_p \odot \vec{v}_j\right) \\S_{i, j} & =\frac{1}{m} \sum_{p=1}^m S_{i j}^p\end{aligned}\]

       $p$和节点表征纬度相同，计算第$p$个视角的对等余弦相似度，其中每个视角考虑嵌入中捕获的语义的一部分。相当于多头的学习器。

     • Kernel-based

       例如高斯核：

       \[\begin{aligned}& d\left(\vec{v}_i, \vec{v}_j\right)=\sqrt{\left(\vec{v}_i-\vec{v}_j\right)^{\top} M\left(\vec{v}_i-\vec{v}_j\right)} \\& S\left(\vec{v}_i, \vec{v}_j\right)=\frac{-d\left(\vec{v}_i, \vec{v}_j\right)}{2 \sigma^2}\end{aligned}\]

       $M$是可学习的权重。

   • 结构感知的相似度量学习

     当从数据中学习隐含的图结构时，如果有内在的图结构，也可以利用它们，这可能是有益的。

     • 使用现成的边嵌入

       例如一种结构感知的注意力机制，就是把边考虑进去：

       \[S_{i, j}^l=\operatorname{softmax}\left(\vec{u}^{\top} \tanh \left(W\left[\vec{h}_i^l, \vec{h}_j^l, \vec{v}_i, \vec{v}_j, \vec{e}_{i, j}\right]\right)\right)\]

       还有提出了一种结构感知的全局注意力机制，用于学习成对的节点相似性：

       \[S_{i, j}=\frac{\operatorname{ReLU}\left(W^Q \vec{v}_i\right)^{\top}\left(\operatorname{ReLU}\left(W^K \vec{v}_i\right)+\operatorname{ReLU}\left(W^R \vec{e}_{i, j}\right)\right)}{\sqrt{d}}\]

     • 利用节点的相邻信息

       在现有的图中只有边连接信息的情况下，提出了一种用于图结构学习的掩蔽式注意力机制：

       \[S_{i, j}=\frac{A_{i, j} \exp \left(\operatorname{ReLU}\left(\vec{u}^{\top}\left|\vec{v}_i-\vec{v}_j\right|\right)\right)}{\sum_k A_{i, k} \exp \left(\operatorname{ReLU}\left(\vec{u}^{\top}\left|\vec{v}_i-\vec{v}_k\right|\right)\right)}\]

       $u$是可学习的。这种使用掩蔽注意力来纳入初始图拓扑结构的想法与GAT模型有着相同的思想。

2. 图稀疏技术

   上述的相似性度量学习函数都会返回一个与全连接图相关的加权邻接矩阵。一个完全连接的图不仅计算成本高，而且还可能引入噪音，如不重要的边缘。

   一般都是对上一节中相似性学习后，进行一些额外的处理，使得图变得稀疏，例如：

   \[A_{i,:}=\operatorname{topk}\left(S_{i,:}\right)\]

   每个节点，只选择邻居节点中topk的连接，作为最终学习到的图结构。或者采用阈值的方式：

   \[A_{i, j}= \begin{cases}S_{i, j} & S_{i, j}>\varepsilon \\ 0 & \text { otherwise }\end{cases}\]

3. 图正则化技术

   许多关于GNN的图结构学习的工作旨在向下游预测任务优化相似度量学习函数（用于学习图结构）。然而，他们并没有明确地强制要求所学的图结构具有真实词汇图中的一些共同属性。这些属性在传统的图形信号处理领域比较常见，一般是对图的一些属性进行约束。

   这里感觉是从直接的图出发的一些约束，来希望对图的结构学习有所帮助。

   Chen等人（2020m）提出通过最小化混合损失函数来优化图形结构，该函数结合了任务预测损失和图形正则化损失。他们探索了三种类型的图形正则化损失，这些损失对所学图形的平滑性、连通性和稀疏性构成了限制条件。

   • 平滑性：平滑性属性假定相邻的节点具有相似的特征。

     \[\Omega(A, X)=\frac{1}{2 n^2} \sum_{i, j} A_{i, j}\left\|X_i-X_j\right\|^2=\frac{1}{n^2} \operatorname{tr}\left(X^{\top} L X\right)\]

     可以看出，最小化该式子迫使相邻的节点具有相似的特征，因此在与$A$相关的图形上强制执行图形信号的平稳性。然而，仅仅最小化平滑度损失将导致琐碎的解决方案$A = 0$。我们可能还想对图形提出其他约束。

   • 连通性：下面的方程通过对数障碍来惩罚不连通的图形的形成。

     \[\frac{-1}{n} \overrightarrow{1}^{\top} \log (A \overrightarrow{1})\]

   • 稀疏性：下面的方程通过惩罚大度数来控制稀疏性。

     \[\frac{1}{n^2}\|A\|_F^2\]

   在实践中，仅仅最小化一种类型的图形正则化损失可能是不可取的。因此，通过计算各种图形正则化损失的线性组合来平衡不同类型的所需图形属性之间的权衡可能是有益的。

   除了上述图的正则化技术，文献中还采用了其他先验假设，如相邻节点倾向于共享相同的标签，学习到的隐性邻接矩阵应接近内在的邻接矩阵。

4. 结合内在图结构和隐式图结构

   回顾一下，图结构学习的一个最重要的动机是，内在图结构（如果它是可用的）可能是容易出错的（例如，有噪音或不完整），并且对下游预测任务来说是次优的。然而，内在图通常仍带有关于下游任务的最佳图结构的丰富和有用的信息。因此，完全摒弃内在图结构可能是有害的。

   有必要用内在图结构的理由

   • 首先，他们假设优化后的图结构有可能是内在图结构的 “转变”（如子结构），而相似性度量函数的目的是学习这样的 “转变”，它是对内在图结构的补充。
   • 其次，考虑到没有关于相似度量的先验知识，可训练的参数是随机初始化的，因此可能需要很长时间才能收敛，纳入内在的图结构有助于加速训练过程并提高训练稳定性。

   那么综合考虑的方法也有不少，例如计算内在图结构的归一化图拉普拉斯和隐含图结构的归一化邻接矩阵的线性组合：

   \[\widetilde{A}=\lambda L^{(0)}+(1-\lambda) f(A)\]

   Liu等人（2021年）提出了一种用于GNN的混合信息传递机制，该机制融合了分别来自本征图和学习的隐含图的两个聚合节点向量，然后将融合后的向量反馈给GRU，以更新节点嵌入。

5. 图结构学习范式

   大多数现有的GNN的图结构学习方法包括两个关键的学习组件：

   • 图结构学习（即相似度量学习）
   • 图表示学习（即GNN模块）

   最终目标是学习与某些下游预测任务相关的优化的图结构和表示。如何优化这两个独立的学习组件，使之朝着同一个最终目标前进？

   • 图形结构和表征的联合学习

     最直接的策略是以端到端的方式联合优化整个学习系统。下游预测任务提供某种形式的监督。

     

     例如设计一个混合损失函数，结合了任务预测损失和图形正则化损失。引入图形正则化损失的目的是为图形属性带来一些先验知识（如平滑性、稀疏性），正如我们上面所讨论的，以便强制学习更有意义的图形结构并缓解潜在的过拟合问题。

   • 图形结构和表征的自适应学习

     通常的做法是依次堆叠多个GNN层，以捕捉图中的长程依赖关系。因此，由一个GNN层更新的图表示将被下一个GNN层作为初始图表示来使用。

     由于每个GNN层的输入图表示是由前一个GNN层转换的，自然会想到每个GNN层的输入图结构是否应该自适应调整以反映图表示的变化，如图所示。

     

     其中一个例子是GAT模型，该模型在每个GAT层进行邻域聚合时，通过对先前更新的节点嵌入应用自我关注机制，对相邻节点嵌入的重要性进行了临时性的重新加权。然而，GAT模型并不更新内在图的连接信息。

     在GNN的图结构学习的文献中，一些方法也是通过基于前一个GNN层产生的更新的图表示，为每个GNN层自适应学习图结构来操作。而整个学习系统通常是以端到端的方式，朝着下游的预测任务共同优化。

   • 图形结构和表征的迭代式学习

     前面提到的联合学习和自适应学习范式都是为了通过对图形表征应用相似度量函数来一次性地学习图形结构。尽管自适应学习范式的目的是在每个GNN层基于更新的图形表示学习图形结构，但每个GNN层的图形结构学习过程仍然是一次性的。

     这种一次性的图结构学习范式的一个很大的局限性是，学到的图结构的质量在很大程度上依赖于图表示的质量。大多数现有的方法都假定原始节点特征能够捕捉到大量关于图拓扑的信息，但不幸的是，情况并非总是如此。因此，从不包含足够的图拓扑信息的原始节点特征中学习良好的隐含图结构是很有挑战性的。

     Chen等人提出了一个新颖的端到端图形学习框架，被称为IDGL，用于联合和迭代学习图形结构和表示。如图下所示。

     

     IDGL框架的运作方式是在更好的图表示的基础上学习更好的图结构，同时，以迭代的方式在更好的图结构基础上学习更好的图表示。

     更具体地说，IDGL框架迭代地寻找一种隐含的图结构，以增强内在的图结构（如果没有，则使用KNN图），这种图结构对下游的预测任务是最优化的。当学习到的图结构根据一定的停止标准（即连续迭代中学习到的邻接矩阵之间的差异小于一定的阈值）足够接近于优化的图时，这个迭代学习程序就会动态停止。在每个迭代中，结合任务预测损失和图形正则化损失的混合损失被添加到总体损失中。在所有迭代之后，整体损失通过所有先前的迭代进行反向传播以更新模型参数。

     这种反复完善图结构和图表示的迭代学习范式有几个优点。

     • 一方面，即使原始节点特征不包含足够的信息来学习节点之间的隐含关系，由图形表示学习组件学习的节点嵌入也能理想地提供有用的信息来学习更好的图形结构，因为这些节点嵌入是针对下游任务优化的。
     • 另一方面，新学的图结构可以成为图表示学习组件学习更好的节点嵌入的更好的图输入。

未来发展方向

Robust Graph Structure Learning

尽管为GNN开发图结构学习技术的主要动机之一是处理噪声或不完整的输入图，但鲁棒性并不在大多数现有图结构学习技术的核心。大多数现有的工作并没有评估他们的方法对嘈杂的初始图的鲁棒性。最近的工作表明，随机边缘添加或删除攻击大大降低了下游任务的性能。此外，大多数现有的工作承认初始图结构（如果提供的话）可能是嘈杂的，因此对图表示学习来说是不可靠的，但他们仍然假设节点特征对图结构学习来说是可靠的，这在现实世界的场景中往往是不真实的。因此，对于具有噪声初始图结构和噪声节点属性的数据，探索稳健的图结构学习技术是具有挑战性的，但也是有益的。

Scalable Graph Structure Learning

大多数现有的图结构学习技术需要对所有节点之间的成对关系进行建模，以发现隐藏的图结构。因此，它们的时间复杂度至少是$O(n^2 )$，其中$n$是图的节点数。这对于大规模的图（如社交网络）来说，在实际词中可能是非常昂贵的，甚至是难以解决的。最近，Chen等人（2020m）提出了一种可扩展的图结构学习方法，通过利用基于锚的近似技术来避免显式计算成对节点的相似性，并在计算时间和内存消耗方面实现了与图节点数量有关的线性复杂。为了提高变换器模型的可扩展性，最近的工作中也开发了不同种类的近似技术。考虑到GNN的图结构学习和变压器之间的密切联系，我们认为在为GNN建立可扩展的图结构学习技术方面有很多机会。

Graph Structure Learning for Heterogeneous Graphs

大多数现有的图结构学习工作集中在从数据中学习同质图结构。与同质图相比，异质图能够携带更丰富的节点类型和边缘类型的信息，并且经常出现在现实世界的图相关应用中。由于需要从数据中学习更多类型的信息（如节点类型、边缘类型），所以异质图的图结构学习应该更具挑战性。最近的一些尝试（Yun等人，2019；Zhao等人，2021）是为了从异质图中学习图结构。

1. Y. Chen and L. Wu, “Graph neural networks: Graph structure learning,” in Graph Neural Networks: Foundations, Frontiers, and Applications, L. Wu, P. Cui, J. Pei, and L. Zhao, Eds. Singapore: Springer Singapore, 2022, pp. 297–321. ↩︎