1. 论文介绍
论文标题：OpenGSL: A Comprehensive Benchmark for Graph Structure Learning
论文领域：图神经网络，图结构学习
论文发表：Camera-ready version for NeurIPS Datasets and Benchmarks Track 2023
论文代码：https://github.com/OpenGSL/OpenGSL
论文背景：
2. 论文摘要
图神经网络（GNNs）能够有效地集成图的拓扑结构和节点属性，已成为图表示学习的事实标准。然而，由于图的复杂和偶然的形成过程，节点连接固有的次优性质给有效地建模带来了巨大的挑战。为了解决这一问题，图结构学习（Graph Structure Learning，GSL）作为一种以数据为中心的学习方法，近年来得到了广泛的关注。GSL背后的核心概念是联合优化图结构和相应的GNN模型。尽管提出了许多GSL方法，但由于实验协议不一致，包括数据集、数据处理技术和分割策略的变化，该领域的进展仍然不清楚。在本文中，我们介绍了OpenGSL，第一个全面的GSL基准，旨在解决这一差距。OpenGSL通过使用统一的数据处理和分割策略在各种流行的数据集中对最新的GSL方法进行评估，从而实现了对这些方法的公平比较。通过大量的实验，我们观察到，现有的GSL方法并不总是优于香草GNN的同行。我们还发现，学习结构的同质性与任务绩效之间没有显著的相关性，挑战了共同的信念。此外，我们观察到，尽管计算量和空间消耗都很高，但学习的图结构在不同的GNN模型中表现出很强的泛化能力。我们希望，我们的开源库将有助于快速和公平的评估，并鼓励在这一领域的进一步创新研究。
3. 相关介绍
3.1 相关背景
现实世界的图通常表现出非最优特征，例如缺少有价值的链接和节点之间存在虚假连接。
为了提高图质量，图结构学习（GSL）一系列以数据为中心的图学习方法，最近引起了相当大的研究兴趣。这些方法旨在共同优化图结构和相应的GNN表示。
目前研究领域有大量的GSL方法，但是并没有一个全面的基准，体现在
（1），在以往的工作中使用了不同的数据集、数据处理方法和数据拆分策略，使得许多结果无法对比和比较。
（2）， 缺乏对学习结构本身的理解，特别是关于其同质性和对 GCN 以外的 GNN 模型的通用性。
（3），除了准确性之外，了解每种方法的计算和内存成本也很重要。
3.2 本文贡献
本文第一个针对 GSL 的综合基准测试。OpenGSL 通过统一的 API 实现了广泛的 GSL 算法，同时还采用了一致的数据处理和数据拆分方法进行公平比较。
（1） 综合基准。OpenGSL 通过统一 10 个具有不同特征的流行数据集的实验设置，可以在 13 种最先进的 GSL 方法之间进行公平的比较。
（2） 多维度分析。我们从各个维度对 GSL 方法进行了系统分析，包括学习结构的同质性、学习结构在 GNN 模型之间的泛化性以及现有方法的时间和内存效率。主要发现有
- 与对同质性假设的普遍看法相反，增加结构的同质性并不一定意味着性能的提高。
- GSL 方法学习的结构具有很强的泛化性。
- 大多数 GSL 方法的时间和内存效率低下，其中一些方法需要比普通 GNN 多几个数量级的资源，这凸显了对更高效的 GSL 方法的迫切需求。
（3），开源基准库和未来方向：我们已在 GitHub 上公开了我们的基准库，旨在促进未来的研究工作。
3.3 同质性
同质性和异质性是基于连接节点对之间相似性的两种互斥测量，其中如果两个节点共享相同的节点标签，则认为它们相似。整个图G的同质性定义为：
相应的，图G的异质性定义为 1−homo(𝒢)
GSL研究的时间线表如下
将现有的 GSL 方法分为三类，如左下角所示：（a）预训练，（b）协同训练，以及（c）迭代训练。预训练涉及一个两阶段的学习过程，其中通过预训练学习结构，然后用于在下游任务中训练 GNN，在协同训练方法中，生成图结构的神经网络与 GNN 一起进行优化。迭代方法涉及迭代训练两个组件;他们从优化的 GNN 生成的预测或表示中学习结构，并使用它来训练新的 GNN 模型以供后续迭代。
4. 基准设计
4.1 数据集
本文收集了 10 个在 GSL 文献中被广泛使用的图节点分类数据集，分别是论文引用数据集 Cora、Citeseer、Pubmed， 社交网络数据集BlogCatalog 和 Flickr。
数据集分为同质图和异质图两类，详细介绍如表格所示。
4.2 GSL算法
考虑的GSL算法包括 LDS、ProGNN、IDGL、GRCN、GAug、SLAPS1、GEN、WSGNN、
Nodeformer、CoGSL、SUBLIME、STABLE 和 SEGSL 这十三个算法。
LDS算法：假设该结构是从具有总参数的 n2 相互独立的伯努利分布中采样的。该文提出了一个双水平优化问题，其中内部问题对训练集上的 GNN 参数进行优化，而外部问题对验证集上的结构参数进行优化。采用基于元学习的方法对结构参数进行优化。
ProGNN：直接优化邻接矩阵，将其设置为 n×n 参数矩阵。引入稀疏性、低秩性和平滑性三个属性来指导结构学习。
IDGL：将结构建模为节点表示的加权余弦函数。为了提高较大图的效率，本文提出了一种基于锚点的结构学习方法。
GRCN：包含两个 GNN，一个用于节点分类，另一个用于计算节点表示，用于通过度量函数推导结构。两个 GNN 同时优化，以最大限度地减少任务损失。
GAug：与 GRCN 具有相似的架构，不同之处在于 GAug 使用图自动编码器来学习结构，而结构学习除了任务损失外，还受到边缘预测损失的指导。
SLAPS：探讨了原始结构缺失的场景。它利用 MLP 获取节点表示，通过度量函数生成结构。SLAPS 的整体架构与 GRCN 类似，但增加了一个自动去噪损耗来指导结构学习。具体来说，损坏的特征和学习到的结构被输入到另一个 GNN 中，输出有望重建原始特征。
GEM：假设最优结构是由 SBM 模型生成的，并进一步假设不同级别的节点表示的相似矩阵是对最优结构的观测。采用 EM 算法来学习给定优化良好的 GNN 的预期最优结构。GEN 以迭代的方式进行结构学习和任务学习。
Nodeformer：一种模型，它允许利用内核化的 Gumbel-Softmax 算子对所有节点对进行层级边缘重新加权，该算子将节点数量的复杂性从二次降低到线性。为了指导结构学习，实现了额外的边缘级正则化。
CoGSL：从原始图中提取了两个基本视图，并使用视图估计器对其进行了细化。采用自适应融合策略来获得最终视图。CoGSL 保持了三个视图的性能，同时减少了每两个视图之间的相互信息，以实现“最小足够的结构”。
SUBLINE：一种无监督结构学习的方法。提出了一种结构引导对比学习框架，其中设置锚定结构为学习者结构提供监督信号。具体来说，SUBLIME 利用基于 GNN 的编码器从两个视图中获取节点表示，并通过节点级对比损失来优化 GNN 编码器。在训练过程中，锚点结构每隔几个 epoch 更新一次，作为锚点结构和学习器结构之间的插值。
WSGNN：一种概率生成模型，它利用变分推理来共同学习节点标签和图结构。它采用双分支模型架构来共同细化节点嵌入和潜在结构。复合损失函数是从底层数据分布中得出的，有效地捕获了观测数据和缺失数据之间的相互作用。
STABLE：利用对比学习获得可靠的节点表示。新结构被计算为节点表示的相似矩阵。此外，提出了一种先进的 GCN 来增强普通 GCN 的鲁棒性。
SEGSL：引入了图结构熵的概念。首先，增强一维结构熵最大化策略引导的结构。然后，构建编码树来捕获图结构的层次信息。最后，SEGSL 从编码树中重建图结构。该方法以迭代的方式进行结构学习和任务学习。
4.3 研究问题
q1：现有的GSL取得了多大的进展
由于大多数实现的 GSL 方法都以 GCN 为骨干，因此我们将 GSL 方法的性能与普通 GCN 进行了比较，以验证学习结构的增强。
q2： GSL 是否在具有更高同质性的图结构表现更好？
同质假设一直是现代 GNN 设计的基本动机，这也被带到了 GSL 场景中。 更具体地说，一些现有的 GSL 方法试图通过引入显式以同质为导向的目标。
通过检查同质性和节点分类性能之间的相关性来确定性能改进是否源于更同质的图结构。
q3：学习到的结构可以推广到其他 GNN 模型吗？
将每个 GSL 方法视为预处理步骤，并使用学习到的结构从头开始训练 GNN 模型，而不是使用与结构联合优化的 GNN。通过比较原始图和新图的性能，我们可以评估学习结构的泛化性。
q4：现有的 GSL 方法在时间和空间上是否有效率？
记录了每种方法训练过程中的具体运行时间和峰值 GPU 内存消耗。为了公平比较，这部分的所有实验都是在单个 NVIDIA A800 GPU 上进行的。
5. 实验结果分析
5.1 性能比较
（1），对于同质图，许多 GSL 方法在具有平衡类的数据集中效果很好，但它们不能处理高度不平衡的情况。
（2），GSL 方法对特定的异质图有效。
5.2 结构学习中的同质性
将学习结构的同质性和节点分类性能绘制在同一图中，为了很好的对比和比较。
（3），学习结构的同质性在同质和异质数据集上有所不同
（4），同质并不总是结构学习的正确指导
在大多数情况下，我们没有观察到性能与同性之间存在正相关关系，在某些情况下甚至呈负相关（在 Citeseer 和 Wiki-cooc 上）。
GNN 可以利用某些异质结构模式，从而在有限的监督下以同质性指导结构学习可能不会产生足够的同质结构，而是破坏这些模式并导致非最优结果。
5.3 通用性
（5），GSL 方法学习的结构具有较强的泛化性
与原始结构相比，许多 GNN 模型在学习的结构上表现出更好的性能，以绿色标记。实验结果为学习结构的泛化性提供了有力的证据，并呼吁进一步探索和应用 GSL 方法。
5.4 时间和内存效率
（6），大多数 GSL 方法耗时和空间大
大多数现有的 GSL 方法都存在严重的效率问题，许多方法的运行时间是 GCN 方法的十倍。
6. 未来方向
（1），重新思考 GSL 中同质性的必要性。
GSL 的性能改进并不一定源于同质性的增加。
（2），不同的数据集设计自适应 GSL 方法
当前的 GSL 方法在不同的数据集中并不普遍有效。因此，创建能够适应不同数据集的创新 GSL 方法存在明显的机会。关注两个关键问题：
- 学习的结构应该为不同的数据集表现出哪些特征？
- 如何将这些特征融入到结构学习中
（3），开发与任务无关的 GSL 方法
现有的 GSL 研究工作主要是任务驱动的。然而，现实世界的场景通常需要在不访问下游任务的情况下细化图结构。
（4），提高 GSL 方法的效率
7. 总结
GSL领域内的综述性问题，不仅仅有综述，而且基于领域内的13种方法重新进行实验和关于同质性的检验，虽然没有提出新算法，但是给出更好使用GSL算法的建议。
7. 个人感悟
浅层的综述只介绍算法和简单比较。高阶的综述进行XXX的实验比较，并给出相关的研究建议。
)
