最近研究GNN的应用方面，遇到了很大的瓶颈，所以回归理论，潜心阅读图结构学习的理论知识，也希望给大家在学习时带来帮助，如有错误请私信指正！

Graph Neural Networks: Graph Structure Learning

摘要：

由于图神经网络（GNNs）在建模图结构数据方面具有出色的表达能力，GNNs在自然语言处理、计算机视觉、推荐系统、药物发现等各种应用中都取得了巨大成功，GNN的巨大成功依赖于图结构数据的质量和可用性，这些数据可能是有噪声的或不可用的。图结构学习问题旨在从数据中发现有用的图结构，这有助于解决上述问题。本章试图通过传统机器学习和GNN的视角，全面介绍图结构学习。阅读本章后，读者将了解如何从不同的角度、不同的目的、通过不同的技术来解决这个问题，以及它与GNN相结合时的巨大潜力。读者还将了解到这一研究领域未来的发展方向

14.1 介绍：

近年来，人们对图神经网络（GNN）的兴趣显著增加（Kipf和Welling，2017b；Bronstein等人，2017；Gilmer等人，2017年；Hamilton等人，2017b，Li等人，2016b），在自然语言处理中有着广泛的应用（Bastings等人，2017，Chen等人，2020p），计算机视觉（Norcliffe-Brown等人，2018），推荐系统（Ying等人，2018b）、药物发现（You等人，2018a）等。GNN在学习表达图表示方面的强大能力依赖于图结构数据的质量和可用性。然而，这给图表示学习提出了一些挑战。一方面，在图结构已经可用的一些场景中，大多数基于GNN的方法都假设给定的图拓扑是完美的，这并不一定成立，因为①.由于不可避免地容易出错的数据测量或收集，实字图拓扑往往是有噪的或不完整的；②.内在图拓扑可能只代表物理连接（例如分子中的化学键），而不能捕捉顶点之间的抽象或隐式关系，这可能有利于某些下游预测任务。另一方面，在许多现实世界的应用程序中，如自然语言处理或计算机视觉中的应用程序，数据的图形表示（例如，文本数据的文本图或图像的场景图）可能不可用。GNN的早期实践（Bastings等人，2017；Xu等人，2018d）在很大程度上依赖于手动图构建，这需要大量的人力和领域专业知识才能在数据预处理阶段获得性能合理的图拓扑。

为了应对上述挑战，图结构学习旨在从数据中去发现有用的图结构，以便使用GNN进行更好的图表示学习。最近的尝试（Chen等人，2020米，o；Liu等人，2021；Franceschi等人，2019年；Ma等人，2019b；Elinas等人，2020年；Velickovic等人，2020；Johnson等人，2020）侧重于图形结构和表示（representations）的联合学习，而无需对人类努力或领域专业知识进行重新排序。已经开发了不同的技术集来学习GNN的离散图结构和加权图结构。更广泛地说，在无监督学习和监督学习环境中，图结构学习在传统机器学习的文献中得到了广泛的研究（Kalofolias，2016；Kumar等人，2019a；Berger等人，2020；Bojchevski等人，2017；Zheng等人，2018b；Yu等人，2019a；Li等人，2020a）。此外，图结构学习还与重要问题密切相关，如图生成（You等人，2018a；Shi等人，2019a）、图对抗性防御（Zhang和Zitnik，2020；Entezari等人，2020；Jin等人，2020a，e）和变换器模型（Vaswani等人，2017）。

本章组织结构如下。我们将首先介绍在传统机器学习的文献中是如何研究图结构学习的，在最近GNN激增之前（第14.2节）。我们将介绍无监督图结构学习（第14.2.1节）和有监督图结构学习（第14.2.2节）的现有工作。读者稍后将看到一些最初为传统图结构学习开发的引入技术是如何被重新审视和改进GNN的图结构学习的。然后，我们将转到本章的主要重点，即第14.3节中GNN的图结构学习。本部分将涵盖各种主题，包括未加权图和加权图的联合图结构和表示学习（第14.3.1节），以及与其他问题的联系，如图生成、图对抗性防御和变换器（第14.3.2节）。我们将在第24.5节中强调一些未来方向，包括鲁棒图结构学习，可伸缩图结构学习、异构图的图结构学习和可转移图结构学习。我们将在第14.5节中对本章进行总结。

14.2 传统的图结构学习

在最近图神经网络的兴起之前，在传统机器学习的文献中，图结构学习已经从不同的角度进行了广泛的研究。在我们讨论图结构学习在图神经网络领域的最新成就（这是本章的主要重点）之前，在本节中，我们将首先从传统机器学习的角度来研究这个具有挑战性的问题。

14.2.1 无监督图结构学习

无监督图结构学习的任务旨在以无监督的方式从一组数据点直接学习图结构。所学习的图结构可以稍后被用于变量预测任务的后续机器学习方法所消耗。这种方法最重要的好处是，它们不需要标记的数据，例如用于超视觉的地面实况图结构，而获得这些数据可能很昂贵。然而，由于图结构学习过程不考虑数据上的任何特定下游预测任务，因此所学习的图结构对于下游任务可能是次优的。

14.2.1.1从平滑信号中学习图结构

图结构学习在图信号处理（GSP）的文献中得到了广泛的研究。它通常在文献中被称为图学习问题，其目标是以无监督的方式从图上定义的平滑信号中学习拓扑结构。这些图学习技术（Jebara等人，2009年；Lake和Tenenbaum，2010年；Kalofolias，2016年；Kumar等人，2019a；Kang等人，2019年；Kuma等人，2020年；Bai等人，2020a）通常通过解决具有图的属性（例如平滑度、稀疏度）的某些先验约束的优化问题来操作。在这里，我们介绍了一些在图上定义的具有代表性的先验约束，这些约束已被广泛用于解决图学习问题。

在介绍具体的图学习技术之前，我们首先提供了图和图信号的形式化定义。考虑一个图 $G=V,E$，其顶点集 $V$ 为基数 $n$，边集 $E$，其邻接矩阵 $A\in {\mathbb{R}}^{n\times n}$ 决定其拓扑结构，其中 $A_{i,j}>0$ 表示存在连接顶点 $i$ 和 $j$ 的边，$A_{i,j}$ 是边权重。给定一个邻接矩阵 $A$，我们可以进一步得到图拉普拉斯矩阵 $L=D-A$，其中 $D_{i,i}={\sum }_j{A}_{i,j}$，$D$ 是非对角项均为零的度矩阵。

一个图信号被定义为一个函数，它为图中的每个顶点分配一个标量值。我们可以进一步定义在图上分配一个 $d$ 维向量到每个顶点的多通道信号 $X\in R^{n\times d}$，其中特征矩阵 $X$ 的每一列可以被视为一个图信号。让 $X_i\in R^d$ 表示在第 $i$ 个顶点上定义的图信号。

适应度
早期关于图学习的工作（Wang和Zhang，2007；Daitch等人，2009）通过假设每个数据点可以使用其邻居的线性组合来优化重建，从而利用每个数据点的邻居信息来构建图。Wang和Zhang（2007）提出通过最小化以下目标来学习具有归一化度的图,
${\sum }_i||X_i-{\sum }_j{A}_{i,j}{X}_j|{|}_2^2$ （14.1）
其中 ${\sum }_j{A}_{i,j}=1,A_{i,j}\ge 0$。
这个公式简单来讲就是使信息聚合后的信号和之前的信号的距离尽可能小，保证平滑性。

类似地，Daitch等人（2009）提出了最小化适应度度量的方法，该度量计算每个顶点到其加权邻居的加权平均值的平方距离的加权和，表示为以下形式：

${\sum }_i||D_{i,i}{X}_i-{\sum }_j{A}_{i,j}{X}_j|{|}_2^2=||LX|{|}_F^2$ （14.2）

其中 $||M|{|}_F=(\sum i,j{M}_{i,j}^2{)}^{\frac{1}{2}}$ 是 Frobenius 范数。
公式 (14.2) 的推导如下：

假设 $X$ 是一个 $n\times d$ 的矩阵，其中第 $i$ 行代表图上第 $i$ 个顶点的图信号。令 $L=D-A$ 为拉普拉斯矩阵，其中 $D$ 是度矩阵，$A$ 是邻接矩阵。拉普拉斯矩阵是一个对称半正定的矩阵，因此它的特征值为非负实数。

我们的目标是最小化误差的平方和，即

${\sum }_{i=1}^n||D_{i,i}{X}_i-{\sum }_{j=1}^n{A}_{i,j}{X}_j|{|}_2^2$

我们将上式展开并进行变换：

$\begin{array}{rlrl}& \sum _{i=1}^n||D_{i,i}{X}_i-\sum _{j=1}^n{A}_{i,j}{X}_j|{|}_2^2=& \sum _{i=1}^n\left(D_{i,i}^2||X_i|{|}_2^2-2D_{i,i}\sum _{j=1}^n{A}_{i,j}{X}_i^T{X}_j+\sum _{j=1}^n\sum _{k=1}^n{A}_{i,j}{A}_{i,k}{X}_j^T{X}_k\right)=& ||DX|{|}_F^2-2\sum _{i=1}^n{X}_i^{T}L{X}_i+\sum _{j=1}^n\sum _{k=1}^n{A}_{i,j}{A}_{i,k}{X}_j^T{X}_k\end{array}$

其中 $||M||F$ 表示矩阵 $M$ 的 Frobenius 范数，即 $\sqrt{\sum i,j{M}_{i,j}^2}$。第二个等式用到了邻接矩阵的性质：${\sum }_{j=1}^n{A}_{i,j}=1$，以及拉普拉斯矩阵的定义：$L=D-A$。

最小化上式等价于最小化

$||LX|{|}_F^2={\sum }_{i=1}^n{\sum }_{j=1}^n{L}_{i,j}{X}_i^T{X}_j={\sum }_{i=1}^n{X}_i^{T}L{X}_i$
公式 (14.1) 中，每个顶点的图信号 $X_i$ 与其邻居节点的加权平均值之间的距离的平方被加权求和。这个加权平均值由邻接矩阵 $A$ 权重加权求得。最小化误差的平方和可以通过对每个节点的图信号 $X_i$ 求导并令其为零来得到最优解。

公式 (14.2) 中，每个顶点的图信号 $X_i$ 与其邻居节点的加权平均值之间的距离的平方被加权求和，这个加权平均值由度矩阵 $D$ 权重加权求得。最小化误差的平方和同样可以通过对每个节点的图信号 $X_i$ 求导并令其为零来得到最优解。

这两个公式的形式类似，但权重矩阵的定义不同。它们都是用来优化图信号的表示，以便更好地描述图上的结构和模式。
平滑性:
平滑性是自然图信号中另一个广泛采用的假设。给定在带权无向图上定义的图信号 $X\in R^{n\times d}$，其中邻接矩阵为 $A\in R^{n\times n}$，图信号的平滑性通常用Dirichlet能量（Belkin和Niyogi，2002）来衡量：

$\Omega (A,X)=\frac{1}{2}{\sum }_{i,j}{A}_{i,j}||X_i-X_j|{|}_2^2=tr(X^{T}LX)$

其中 $L$ 是拉普拉斯矩阵，$tr(\cdot )$ 表示矩阵的迹。Lake和Tenenbaum（2010）；Kalofolias（2016）建议通过最小化 $\Omega (A,X)$ 来学习一个图，从而强制相邻的顶点具有相似的特征，从而在学习的图上平滑图信号。值得注意的是，仅最小化上述平滑性损失可以导致平凡解 $A=0$。
连通性和稀疏：
为了避免仅最小化平滑性损失所导致的平凡解，Kalofolias（2016）对学习的图施加了额外的约束：
$$-\alpha {\vec{1}}^{\top }\log (A\vec{1})+\beta ||A|{|}_F^2(14.4)$$
其中第一项通过对数障碍（logarithmic barrier）惩罚断开的图的形成，第二项通过惩罚第一项导致的大度数来控制稀疏性。注意，$\vec{1}$ 表示全 1 向量。因此，这可以改善图的总体连接性，而不影响稀疏性。

全1向量的作用是通过对数障碍（logarithmic barrier）来惩罚断开的图的形成。具体来说，对于矩阵 $A$，如果存在一个子集 $S\subseteq 1,2,...,n$，满足所有 $i,j\in S$ 的元素 $A_{i,j}=0$，即 $S$ 对应的子图是一个孤立的子图，则全1向量与 $A$ 的乘积 ${\vec{1}}^{\top }A\vec{1}$ 的值为0。因此，如果我们在目标函数中引入一个对数障碍 $-\alpha \log ({\vec{1}}^{\top }A\vec{1})$，其中 $\alpha$ 是正常数，则可以通过最小化这个惩罚项来防止出现孤立子图。当 ${\vec{1}}^{\top }A\vec{1}>0$ 时，对数障碍惩罚项的值是负的，并且趋近于0。当 ${\vec{1}}^{\top }A\vec{1}=0$ 时，对数障碍惩罚项的值趋近于正无穷，因此目标函数的值也趋近于正无穷。这样，我们就能保证学习到的图是连通的。

14.2.1.2 谱聚类通过图结构的学习

图结构学习也在聚类分析领域得到了研究。例如，为了提高谱聚类方法对噪声输入数据的鲁棒性，Bojchevski等人（2017）假设观察到的图 $A$ 可以分解为受损图 $A^c$ 和良好的（即清洁的）图 $A^g$，并且仅在清洁的图上执行谱聚类是有益的。因此，他们提出了在观察到的图的分解和谱聚类之间联合进行，并采用高效的块坐标下降（alternating）优化方案来逼近目标函数。Huang等人（2019b）提出了一种多视角学习模型，它同时进行多视角聚类，并在核空间中学习数据点之间的相似性关系。

14.2.2 监督图结构学习

监督图结构学习的任务旨在以监督的方式从数据中学习图结构。在模型训练阶段，它们可以考虑也可以不考虑特定的下游预测任务。

14.2.2.1 交互系统的关系推理

关于相互作用系统的关系推断旨在研究复杂系统中的对象如何相互作用。早期的研究考虑了一个固定或完全连接的交互图（Battaglia等人，2016；van Steenkiste等人，2018），同时对对象之间的交互动态进行建模。Sukhbaatar等人（2016）提出了一种神经模型，学习动态变化的代理集之间的连续通信，其中通信图随着代理移动、进入和退出环境而改变。最近的研究（Kipf等人，2018；Li等人，2020a）致力于同时推断潜在的交互图并建模交互动态。Kipf等人（2018）提出了一种基于变分自编码器（VAE）（Kingma和Welling，2014）的方法，该方法通过观察对象的运动轨迹以无监督的方式学习推断交互图结构和建模物理对象之间的交互动态。VAE的离散潜在编码表示潜在交互图的边连接，编码器和解码器均采用GNN的形式来建模对象之间的交互动态。由于VAE的潜在分布是离散的，作者采用了连续松弛方法以使用重新参数化技巧（Kingma等人，2014）。虽然Kipf等人（2018）专注于推断静态交互图，但Li等人（2020a）设计了一种动态机制，以适应性地随时间演化潜在交互图。采用门控循环单元（GRU）（Cho等人，2014a）来捕捉历史信息并调整先验交互图。

14.2.2.2 在贝叶斯网络中的结构学习

贝叶斯网络（BN）是一种概率图模型（PGM），通过有向无环图（DAG）对随机变量之间的条件依赖关系进行编码，其中DAG中的每个随机变量都表示为一个节点。学习BN结构的问题在贝叶斯网络研究中是重要而具有挑战性的。大多数现有的BN学习工作侧重于基于评分的DAG学习，并旨在找到具有最大得分的DAG，其中得分表示观察数据（和任何先前知识）如何支持任何候选DAG的好坏。早期的工作将BN学习视为组合优化问题，由于DAG的不可计算的搜索空间与节点数量的超指数级缩放而是NP难的。一些高效的方法已经被提出，通过动态规划（Koivisto和Sood，2004；Silander和Myllym ̈aki，2006）或整数规划（Jaakkola等，2010；Cussens，2011）进行准确的BN学习。最近，Zheng等人（2018b）提出了将传统组合优化问题转化为一个纯连续优化问题，其中平滑等式约束确保图的无环性。因此，通过标准的数值算法可以高效地解决这个问题。随后的研究（Yu等，2019a）利用GNN的表达能力，提出了一种基于变分自编码器（VAE）的深度生成模型，其中包含一种结构约束的变体来学习DAG。VAE由一个GNN参数化，可以自然地处理离散和矢量值随机变量。

14.3 图神经网络的图结构学习

最近，在GNN领域重新审视了图结构学习，以处理图结构数据有噪声或不可用的情况。最近在这一研究领域的尝试主要集中在图结构和表示的联合学习上，而不需要人力或领域专业知识。图14.1显示了GNN的图结构学习的概述。此外，我们看到近年来正在积极研究的几个重要问题（包括图生成、图通用防御和变换器模型），这些问题与GNN的图结构学习密切相关。我们将在本节中讨论它们之间的联系和差异。
Fig. 14.1: The overview of graph structure learning for GNNs

14.3.1 联合图结构与表示学习

在GNN的最近实践中，联合图结构和表示学习引起了越来越多的关注。这一研究方向旨在以端到端的方式联合优化图结构和GNN参数，以实现下游预测任务，并可以大致分为两类：学习离散图结构和学习加权邻接矩阵。第一类方法（Chen等，2018e; Ma等，2019b; Zhang等，2019d; Elinas等，2020; Pal等，2020; Stanic等，2021; Franceschi等，2019; Kazi等，2020）通过从学习到的概率邻接矩阵中采样离散图结构（即对应于二进制邻接矩阵），然后将图输入到后续的GNN中以获得任务预测。由于采样操作破坏了整个学习系统的可微性，因此应用变分推断（Hoffman等，2013）或强化学习（Williams，1992）等技术来优化学习系统。考虑到离散图结构学习通常由不可微的采样操作引入了优化困难，因此很难学习边权重，另一类方法（Chen等，2020m; Li等，2018c; Chen等，2020o; Huang等，2020a; Liu等，2019b, 2021; Norcliffe-Brown等，2018）专注于学习加权（通常是稀疏的）邻接矩阵，该矩阵与加权图相关联，后续的GNN将使用该矩阵进行预测任务。我们将在接下来详细讨论这两种方法。

在讨论联合图结构和表示学习的不同技术之前，让我们首先明确联合图结构和表示学习问题的定义。

14.3.1.1 问题阐述

假设图 $G=(V,E)$ 可以表示为由 $n$ 个节点 $v_i\in V$、一个初始节点特征矩阵 $X\in {\mathbb{R}}^{d\times n}$ 和一组 $m$ 条边 $(v_i,v_j)\in E$（二进制或加权）组成的集合。给定一个带噪图输入 $G:=A(0),X$ 或仅有一个节点特征矩阵 $X\in {\mathbb{R}}^{d\times n}$，我们考虑的联合图结构和表示学习问题旨在针对某些下游预测任务生成经过优化的图 $G^{\ast }:=A^{,}X$ 及其对应的节点嵌入 $Z=f(G^{,}\theta )\in {\mathbb{R}}^{h\times n}$。这里，我们将 $f$ 表示为一个 GNN，$\theta$ 表示它的模型参数。

14.3.1.2 学习离散图结构

为了处理图上的不确定性问题，现有的许多离散图结构学习方法将图结构视为一个随机变量，其中可以从某种概率邻接矩阵中采样出一个离散图结构。它们通常利用各种技术，如变分推断（Chen等人，2018e; Ma等人，2019b; Zhang等人，2019d; Elinas等人，2020; Pal等人，2020; Stanic等人，2021）、双层优化（Franceschi等人，2019）和强化学习（Kazi等人，2020）来联合优化图结构和GNN参数。值得注意的是，它们通常只适用于转导学习设置，即在训练和推断阶段都完全观察到节点特征和图结构。在本节中，我们介绍了一些代表性的作品，并展示了它们如何从不同的角度来解决这个问题。

Franceschi等人（2019）提出了通过将任务视为双层优化问题Colson等人（2007）来联合学习图的边缘的离散概率分布和GNN参数的方法，其公式为：

$mi{n}_{\vec{\theta }\in H_N}{\mathbb{E}}_{A\sim Ber(\vec{\theta })}[F(w_{\theta },A)]s.t.w_{\theta }=argmi{n}_w{\mathbb{E}}_{A\sim Ber(\vec{\theta })}[L(w,A)]$

其中，$H_N$表示N个节点的所有邻接矩阵集合的凸包，$L(w,A)$和$F(w_{\vec{\theta }},A)$都是衡量GNN预测和基于训练集和验证集计算的真实标签之间差异的任务特定损失函数。图的每个边缘（即节点对）都被独立地建模为一个伯努利随机变量，因此可以从由$\vec{\theta }$参数化的图结构分布中采样得到邻接矩阵$A\sim Ber(\vec{\theta })$。外部目标（即第一个目标）旨在给定GCN找到最优的离散图结构，内部目标（即第二个目标）旨在给定图找到GCN的最优参数$w_{\vec{\theta }}$。作者使用超梯度下降算法近似地解决了上述具有挑战性的双层问题。

Ma等人（2019b）认为，由于真实世界的图通常存在噪声，因此将节点特征、图结构和节点标签视为随机变量，并使用灵活的生成模型对它们进行了建模，以解决基于图的半监督学习问题。他们受到网络科学领域随机图模型的启发（Newman，2010），假设图是基于节点特征和标签生成的，因此将联合分布因子化为以下形式：
$p(X,Y,G)=p_{\theta }(G|X,Y)p_{\theta }(Y|X)p(X)$，
其中$X,Y$和$G$是随机变量，分别对应于节点特征、标签和图结构，$\theta$是可学习的模型参数。注意到条件概率$p_{\theta }(G|X,Y)$和$p_{\theta }(Y|X)$可以是任何灵活的参数分布族，只要它们对$\theta$几乎处处可微分即可。在论文中，$p_{\theta }(G|X,Y)$使用潜空间模型（LSM）(Hoff et al，2002)或随机块模型（SBM）(Holland et al，1983)来实现。在推断阶段，为了推断出缺失的节点标签 $Y_{miss}$，作者利用了可扩展的变分推断技术 (Kingma and Welling, 2014; Kingma et al, 2014) 来逼近由识别模型 $q_{\varphi }(Y_{miss}|X,Y_{obs},G)$ 所参数化的后验分布 $p_{\theta }(Y_{miss}|X,Y_{obs},G)$。其中，$Y_{obs}$ 表示已观测的节点标签，而在该论文中，$q_{\varphi }(Y_{miss}|X,Y_{obs},G)$ 被实例化为一个 GNN。模型参数 $\theta$ 和 $\varphi$ 被共同优化，以最大化给定 X 下，观测数据 $(Y_{obs},G)$ 的证据下界 (Bishop, 2006)。
Elinas等人（2020）旨在最大化给定观察数据（即，节点特征X和观测节点标签Yo）的二元邻接矩阵的后验概率，其公式为：

$p(A|X,Y_o)\propto p_{\theta }(Y_o|X,A)p(A)$

其中$p_{\theta }(Y_o|X,A)$是条件似然，可以根据条件独立性假设进一步分解为：

$p_{\theta }(Y_o|X,A)={\prod }_{y_i\in Y_o}{p}_{\theta }(y_i|X,A)$

$p_{\theta }(y_i|X,A)=Cat(y_i|{\pi }_i)$

其中$Cat(y_i|{\pi }_i)$表示分类分布，是由GCN模型建模的概率矩阵Π∈RN×C的第i行，即$\Pi =GCN(X,A,\theta )$。对于邻接矩阵的先验分布$p(A)$，该方法考虑了以下形式：

$p(A)={\prod }_{i,j}p(A_{i,j})$

$p(A_{i,j})=Bern(A_{i,j}|{\rho }_{o_{i,j}})$

其中$Bern(A_{i,j}|{\rho }_{o_{i,j}})$是带参数${\rho }_{o_{i,j}}$的伯努利分布，用于建模具有参数${\rho }_{o_{i,j}}$的邻接矩阵$A_{i,j}$。在本文中，${\rho }_{o_{i,j}}={\rho }_1{A}_{i,j}+{\rho }_2(1-A_{i,j})$被构造来编码对于观测链接存在和不存在的信念度，其中超参数$0<{\rho }_1,{\rho }_2<0$。需要注意的是，$A_{i,j}$是可能被扰动的观测图结构。如果没有可用的输入图，则可以使用KNN图。基于上述公式，该方法采用重参数化技巧（Kingma等人，2014年）和Concrete分布技巧（Maddison等人，2017年；Jang等人，2017年）开发了一种随机变分推断算法，共同优化了图后验概率$p(A|X,Y_o)$和GCN参数$\theta$。

Kazi等人（2020年）设计了一种概率图生成器，其基础概率分布是基于成对节点相似性计算的，公式为：

$p_{i,j}=e^{-t||X_i-X_j||}$

其中t是温度参数，$X_i$是节点$v_i$的节点嵌入。在给定上述边缘概率分布的情况下，他们采用了Gumbel-Top-k技巧（Kool等人，2019年）来采样一个无权重的KNN图，该图将被馈送到基于GNN的预测网络中。需要注意的是，采样操作会破坏模型的可微性，因此该方法利用强化学习来实现。

14.3.1.3学习加权图结构

与专注于为GNN学习离散图结构（即二元邻接矩阵）的方法不同，有一类方法则专注于学习加权图结构（即加权邻接矩阵）。与学习离散图结构相比，学习加权图结构有几个优势。首先，优化加权邻接矩阵比优化二元邻接矩阵更可行，因为前者可以通过SGD技术（Bottou，1998）甚至凸优化技术（Boyd et al，2004）轻松实现，而后者通常需要更具挑战性的技术，如变分推断（Hoffman et al，2013）、强化学习（Williams，1992）和组合优化技术（Korte et al，2011），因为其不可微性。其次，加权邻接矩阵能够相对于二元邻接矩阵更好地编码边缘的信息，这有利于后续的图表示学习。例如，广泛使用的Graph Attention Network（GAT）（Veliˇckovi ́c et al，2018）本质上旨在学习输入二元邻接矩阵的边缘权重，以利于后续的消息传递操作。在本子节中，我们首先介绍一些常见的图相似度度量学习技术以及在嵌入空间中考虑节点对相似性而广泛使用的图稀疏化技术，以学习稀疏加权图。接下来，将介绍一些代表性的图正则化技术，用于控制所学习图结构的质量。然后，我们将讨论将内在图结构和学习到的隐式图结构相结合以获得更好的学习性能的重要性。最后，我们将涵盖一些重要的学习范式，用于联合学习图结构和图表示，这些范式已经被现有的研究成功采用。

图的相似性度量学习技巧

正如在14.2.1.1节中介绍的那样，关于平滑信号的无监督图结构学习的先前工作也旨在从数据中学习一个加权邻接矩阵。然而，它们无法处理归纳学习设置，其中推断阶段存在未见过的图形或节点。这是因为它们通常通过在图形属性上施加一定的先验约束条件来直接优化邻接矩阵进行学习。许多离散图形结构学习的工作（第14.3.1.2节）也因为类似的原因而难以进行归纳学习。
受基于注意力技术（Vaswani等，2017; Veliˇckovi ́c等，2018）用于建模对象之间关系的成功启发，最近文献中的许多工作将图结构学习视为在节点嵌入空间中定义的相似性度量学习，假设节点属性多少包含用于推断图的隐式拓扑结构的有用信息。这种策略的最大优势之一是，学习的相似性度量函数可以稍后应用于一组未见过的节点嵌入，以推断图形结构，从而实现归纳图结构学习。
对于在非欧几里得域中部署的数据（如图形数据），欧几里得距离不一定是衡量节点相似性的最佳度量。常见的度量学习选项包括余弦相似度（Nguyen和Bai，2010），径向基函数（RBF）核（Yeung和Chang，2007）和注意机制（Bahdanau等，2015; Vaswani等，2017）。通常，根据所需的原始信息来源的类型，我们将相似度度量函数分为两类：基于节点嵌入的相似度度量学习和结构感知相似度度量学习。接下来，我们将介绍一些在先前用于GNN的图结构学习中成功采用的来自这两个类别的代表性度量学习函数。

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

基于节点嵌入的相似性度量学习函数被设计为基于节点嵌入来学习成对的节点相似性矩阵，该矩阵理想地对节点的重要语义进行编码，用于图结构学习。
基于注意力的相似度量函数：迄今为止，大多数提出的相似度度量函数都基于注意力机制Bahdanau等人（2015）和Vaswani等人（2017）。Norcliffe-Brown等人（2018）采用了一个简单的度量函数，它计算任意一对节点嵌入的点积（eq.（14.12））。由于其学习能力有限，它可能难以学习到最优的图结构。
$S_{i,j}={\overrightarrow{v_i}}^{\top }\overrightarrow{v_j}(14.12)$

其中 $S\in R^{n\times n}$ 是节点相似性矩阵，而 $\overrightarrow{v_i}$ 是节点 $v_i$ 的向量表示。

为了丰富点积的学习能力，Chen等人（2020n）提出了一种修改后的点积，引入了可学习参数，如下所示：
$S_{i,j}=(\overrightarrow{v_i}\odot \vec{u}{)}^{\top }\overrightarrow{v_j}(14.13)$

其中 $\odot$ 表示逐元素乘法，$\vec{u}$ 是一个非负可训练的权重向量，它学习突出节点嵌入的不同维度。请注意，输出的相似度矩阵 $S$ 是不对称的。

Chen等人（2020o）通过引入一个权重矩阵，提出了更具表现力的点积版本，如下所示：
$S_{i,j}=\text{ReLU}(W\overrightarrow{v_i}{)}^{\top }\text{ReLU}(W\overrightarrow{v_j})(14.14)$
其中 $W$ 是一个 $d\times d$ 的权重矩阵，$\text{ReLU}(x)=\max (0,x)$ 是一个修正线性单元（ReLU）（Nair和Hinton，2010），在这里用于强制输出相似度矩阵的稀疏性。

类似于Chen等人（2020o），On等人（2020）在计算点积之前，引入了一个可学习的映射函数到节点嵌入中，并应用ReLU函数来强制稀疏性，如下所示：
$S_{i,j}=\text{ReLU}(f(\overrightarrow{v_i}{)}^{\top }f(\overrightarrow{v_j}))(14.15)$
其中 $f:\mathbb{R}\to \mathbb{R}$ 是一个单层前馈神经网络，没有非线性激活函数。
除了使用ReLU来强制稀疏性之外，Yang等人（2018c）还应用了平方运算来稳定训练，并应用行归一化操作来获得归一化的相似度矩阵，如下所示：
$$S_{i,j}=\frac{\text{ReLU}((W_1\overrightarrow{v_i}{)}^{\top }{W}_2\overrightarrow{v_j}+b{)}^2}{{\sum }_k\text{ReLU}((W_1\overrightarrow{v_k}{)}^{\top }{W}_2\overrightarrow{v_j}+b{)}^2}(14.16)$$
其中 $W_1$ 和 $W_2$ 是 $d\times d$ 的权重矩阵，$b$ 是一个标量参数。
与Chen等人（2020o）应用相同的线性变换到节点嵌入不同，Huang等人（2020a）在计算点对节点相似性时，将不同的线性变换应用于两个节点嵌入，如下所示：
$$S_{i,j}=\text{softmax}((W_1\overrightarrow{v_i}{)}^{\top }{W}_2\overrightarrow{v_j})(14.17)$$其中 $W_1$ 和 $W_2$ 是 $d\times d$ 的权重矩阵，$\text{softmax}(\vec{z}{)}_i=\frac{e^{z_i}}{{\sum }_j{e}^{z_j}}$ 用于获得行归一化的相似度矩阵。

Velickovic等人（2020）旨在在时间设置中进行图结构学习，其中要学习的隐式图结构随时间而变化。在每个时间步 $t$，他们首先使用与（Huang等人，2020a）中相同的注意力机制计算点对节点相似度 $a_{i,j}^{(t)}$，并基于此，进一步通过选择具有最大 ${\vec{a}}_{i,j}$ 的节点 $j$ 来为节点 $i$ 派生一个新边来获得“聚合”邻接矩阵 $S_{i,j}^{(t)}$。整个过程如下所示：
$$\begin{gathered} a_{i,j}^{(t)}=\text{softmax}((W_1{\vec{v}}_i^{(t)}{)}^{\top }{W}_2{\vec{v}}_j^{(t)}) \\ {\tilde{S}}_{i,j}^{(t)}={\mu }_i^{(t)}{\tilde{S}}_{i,j}^{(t-1)}+(1-{\mu }_i^{(t)}){\delta }_{j={\text{argmax}}_k(a_{i,k}^{(t)})} \\ {S}_{i,j}^{(t)}={\tilde{S}}_{i,j}^{(t)}\vee {\tilde{S}}_{j,i}^{(t)}(14.18) \end{gathered}$$其中 ${\mu }_i^{(t)}$ 是一个可学习的二进制门控蒙版，$\vee$ 表示两个操作数之间的逻辑析取以强制对称性，$W_1$ 和 $W_2$ 是 $d\times d$ 的权重矩阵。由于 $\text{argmax}$ 操作使整个学习系统不可微分，因此作者在每个时间步提供了真实图结构进行监督。
基于余弦的相似性度量函数:Chen等人（2020m）提出了一种多头加权余弦相似度函数，旨在从多个角度捕获点对节点相似性，如下所示：
$$S_{i,j}^p=cos({\vec{w}}_p\odot {\vec{v}}_i,{\vec{w}}_p\odot {\vec{v}}_j),S_{i,j}=\frac{1}{m}\sum _{p=1}^m{S}_{i,j}^p(14.19)$$其中，${\vec{w}}_p$ 是与第 $p$ 个视角相关联的可学习权重向量，具有与节点嵌入相同的维度。直观地说，$S_{i,j}^p$ 计算了第 $p$ 个视角下节点 $i$ 和节点 $j$ 的成对余弦相似度，其中每个视角考虑了嵌入中捕获的一部分语义。此外，正如（Vaswani et al，2017; Velickovic et al，2018）所观察到的那样，使用多头学习器能够稳定学习过程并增加学习容量。
基于内核的相似性度量函数:
除了基于注意力和余弦的相似度度量函数之外，研究人员还探索了将基于核的度量函数应用于图结构学习。Li等人（2018c）将高斯核应用于任意一对节点嵌入之间的距离，其公式如下所示：
$$d({\vec{v}}_i,{\vec{v}}_j)=\sqrt{({\vec{v}}_i-{\vec{v}}_j{)}^{\top }M({\vec{v}}_i-{\vec{v}}_j)},S({\vec{v}}_i,{\vec{v}}_j)=-\frac{d({\vec{v}}_i,{\vec{v}}_j)}{2{\sigma }^2}(14.20)$$其中，$\sigma$ 是一个标量超参数，决定高斯核的宽度，$d({\vec{v}}_i,{\vec{v}}_j)$ 计算两个节点嵌入之间的马氏距离。值得注意的是，如果我们假设图中所有节点的嵌入都来自同一分布，那么 $M$ 就是节点嵌入分布的协方差矩阵。如果我们将 $M$ 设置为单位矩阵 $I$，则马氏距离就会变成欧几里得距离。为了让 $M$ 成为对称且半正定的矩阵，作者让 $M=W{W}^{\top }$，其中 $W$ 是一个 $d\times d$ 的可学习权重矩阵。我们也可以将 $W$ 视为变换基，将两个向量之间的欧几里得距离度量到另一个空间中。