OpenGSL | 开源图结构学习基准库, 含12个前沿GSL方法和10个数据集

为解决拓扑结构固有的次优性质，图结构学习（Graph Structure Learning，GSL）作为一种以数据为中心（data-centric）的学习方法被提出，得到了迅速的发展。尽管如此，GSL研究领域仍然缺少一个统一的基准库，这在多个方面阻碍了这个领域的进展，因此我们开发了一个全面的图结构学习基准库OpenGSL，来实现公平对比和深入探索。我们希望OpenGSL可以帮助研究者了解GSL的前沿方法，促进快速、公平的评估，并激发 GSL 领域进一步的创新性研究。

论文链接：https://arxiv.org/abs/2306.10280 代码链接：https://github.com/OpenGSL/OpenGSL

一、引言

图1：GSL研究时间线

最近图神经网络（Graph Neural Networks，GNNs）发展迅速，成为了深度学习的一个研究热点。由于能够同时利用拓扑结构信息和特征信息，GNN成为了处理图数据的主流方法。GNN领域的新工作层出不穷，它们大部分着重于如何改进模型架构。然而这些以模型为中心（model-centric)的工作忽略了数据中图结构的潜在缺陷，例如关键边的缺失或者不需要的边的冗余，进而会导致次优的结果。。

为了解决拓扑结构固有的次优性问题，研究者们提出了一种以数据为中心（data-centric）的学习方法，称为图结构学习（Graph Structure Learning，GSL），引起了广泛的关注。GSL通过联合优化图结构和GNN，能够改善原始图结构，学习到更加优秀的图表示。近期涌现了各种创新的GSL方法，并成功应用于实际场景中。

虽然该研究领域的发展快速，如图1所示，我们注意到这个领域缺少一个全面的基准测试，这在多个方面都显著阻碍了对GSL的理解和进展：

1. 现有的研究中使用了不同的数据集、数据划分和数据处理策略，使得许多结果无法相互比较。
2. 大多方法只关注GSL在下游任务上的表现，缺乏对所学结构本身的探索，特别是同质性以及对其他GNN主干的泛化能力。
3. 在准确性之外，理解每种方法的计算成本也十分重要，但在文献中往往被忽略。

为了解决这些问题，我们提出了第一个全面的图结构学习基准库OpenGSL。OpenGSL涵盖了广泛的GSL算法，并采用统一的数据处理和数据划分方式，以实现公平比较。通过在各种数据集上对现有的GSL方法进行基准测试，我们的研究具有以下主要贡献：

1. 全面的基准：OpenGSL具有统一的实验设置，我们在10个不同类型和规模的数据集上公平比较12种前沿GSL方法。实证结果表明，GSL方法并不总是优于基本的GNN方法。
2. 多维度的分析：我们对GSL方法进行了多维度的分析，包括学到结构的同质性和泛化能力，以及现有方法的效率。我们的主要发现有：不同于普遍观念，同质性和分类表现没有显著关联；GSL学到的结构有较强的泛化能力；大部分GSL方法在时间和空间上低效。
3. 开源的基准库和未来方向：我们列举了若干可能的未来研究方向，同时我们在Github上开源了基准库OpenGSL，以支持未来的研究工作。

二、实验结果与分析

OpenGSL在10个数据集上对12种方法进行了统一而全面的测试。论文提供了关于OpenGSL设计的详细信息，欢迎读者阅读。我们在这里将直接讨论实验结果和所得到的发现。我们的代码仓库提供了轻松复现这些实验结果的途径。

2.1 性能比较

由于先前的GSL工作使用的数据集、数据划分和数据处理的不同，我们难以公平地评估和比较它们的表现。在 OpenGSL 提供的公平比较环境下，第一个研究问题是重新审视现有 GSL 方法取得了多少进展。我们在表1和表2中分别展示了所有实现的方法在同质图和异质图上的表现。

表1：在Cora，Citeseer，Pubmed，Questions和Minesweeper上的节点分类结果。表中数据是使用不同随机种子运行10次的均值±标准差。绿、黄、蓝分别标识排名第一，第二和第三的结果。--表示内存不足或超时。

表2：在BlogCatalog，Flickr，Amazon-ratings，Roman-empire和Wiki-cooc上的节点分类结果。表中数据是使用不同随机种子运行10次的均值±标准差。绿、黄、蓝分别标识排名第一，第二和第三的结果。--表示内存不足或超时。

以下是我们的主要发现：

大部分GSL方法可以在同质图上起作用，但无法处理类别不均衡的情况。

从表2中我们可以看出，在Cora、Citeseer和Pubmed这三个典型的同质图数据集上，大多数方法超过了GCN。然而，在Questions和Minesweeper这两个类别不均衡的数据集上，大多数GSL方法相对于GCN没有明显的优势。这一结果表明，在这种类型的数据上，GSL的效果受到限制。考虑到许多现实世界的图数据都存在类别不均衡的情况，未来的GSL研究需要更多地关注这一方面。

GSL方法可以在部分异质图上起作用。

表3显示，包括IDGL，GAug，GEN和SUBLIME在内的一些GSL方法在BlogCatalog，Flickr和Amazon-ratings上可以超越普通GCN。然而在Roman-empire和Wiki-cooc数据集上，结果则截然相反，只有少数方法表现出相对GCN更好的性能。这种观察表明，异质数据集可能包含信息丰富的结构模式，而当前以同质性为导向的GSL方法则会削弱这些模式的作用。

2.2 探索同质性

同质性假设一直是GNN设计的基本动机之一，一些现有的GSL方法也尝试通过引入显式的同质性导向目标来学习更具同质性的结构。而这些说法的有效性尚未得到充分验证。近期一些研究者开始质疑GNN上的同质性假设，因此我们有必要重新评估GSL方法在学习更同质性的图结构方面的表现。我们将学习到的结构的同质性和节点分类性能绘制在图2和图3中。

图2：在同质图数据集上学习到的结构的同质性和节点分类性能。方法按学到结构的同质性排序。黄色标明原始结构。

图3：在异质图数据集上学习到的结构的同质性和节点分类性能。方法按学到结构的同质性排序。黄色标明原始结构。

我们有以下观察：

在同质图和异质图上，GSL学到结构的同质性有不同表现。

图2的结果显示，在同质性数据集上学习结构的同质性与原始结构几乎没有区别，在某些情况下甚至会更低。然而，在图3的异质性数据集上，学习结构的同质性在大多数情况下显著提高。这种差异的原因可能是图的同质性初始水平不同。大多数GSL方法在有限的监督信号下进行训练，其能够恢复或删除的边数量是有限的。因此，在大多数边不符合同质性的异质性数据集上，这些有限的边很可能被调整。另一方面，在同质性数据集上，这些边已经满足同质性要求，因此同质性更难进一步提升。

对于GSL，同质性不是一个通用的目标。

正如图2和图3展示的，同质性只在部分数据集上（BlogCatalog和Flickr）和分类表现有显著正相关。在大多数情况下，我们并没有观察到性能和同质性之间的正相关性。这些观察结果表明，对于GSL方法而言，同质性并非一个通用的目标。这一发现挑战了先前一些GSL方法所基于的假设，也需要我们未来进行深入的研究和探索。最近的一些研究对此有一定解释，即GNN可以利用一些特殊的异质结构模式，在结构学习过程中以同质性为目标可能破坏这些模式，导致次优的结果产生。

2.3 图结构的泛化能力

之前的研究大多使用节点分类任务的性能来评估GSL方法，而对于学习到的图结构的质量评估则较少。我们希望在实验中评估各种GSL方法学习到的结构是否具有对其他更多GNN模型的泛化能力。我们使用学习到的图结构和原始特征创建一个新的图数据，并从头训练一个新的GNN模型。在表3和表4中，我们展示了使用GSL方法学习的结构作为输入的几种GNN模型和简单的非GNN模型的性能结果。

表3：在Cora上的结构泛化性能。绿色表明相对原始结构有提升。

表4：在BlogCatalog上的结构泛化性能。绿色表明相对原始结构有提升。

GSL学到的结构具有较强的泛化能力。

表3和表4的结果表明，与原始结构相比，许多GNN模型在GSL方法学到的结构上有性能提升。这个观察结果强调了学到结构增强许多GNN方法的潜力。此外，我们还观察到，使用GSL方法学习的结构也有助于提高两种简单的非GNN方法（即LPA和LINK）的性能，在某些情况下，它们甚至超过了GNN。这些实验结果为学习结构的泛化能力提供了有力证据。

2.4 效率

GSL方法同时优化GNN和图结构，因此它们在时间和空间上的消耗通常比单纯的GNN方法更多。然而，现有方法往往忽视了GSL方法的效率问题。在性能和效率之间找到平衡是一个重要的考虑因素。理解这种平衡对于在实际应用中使用GSL方法非常关键。图4展示了所有方法在Cora数据集上的效率。关于其他数据集的完整统计信息，请参阅我们的论文。

图4：Cora上各方法的时间和空间消耗

大部分GSL方法有较大的时间和空间消耗。

图4清楚地表明，当前前沿的GSL方法在性能和效率之间很难实现一个令人满意的平衡。大多数现有的GSL方法存在明显的效率问题，很多方法的运行时间比GCN方法长10倍。其中ProGNN速度最慢，需要190倍的时间。同样，大多数GSL方法消耗过多的内存，CoGSL需要的内存量高达GCN的66倍。GSL方法的效率问题在更大的数据集上尤为明显，详见我们的论文。考虑到这些发现，解决效率问题对于确保GSL方法能够成功应用于各种实际场景至关重要。

三、未来研究

基于以上的实验结果和分析，我们列举了一些可能的研究方向。

重新思考GSL中的同质性。当前的GSL方法通常致力于增强图结构的同质性，但根据我们的实验观察，性能的提升并不一定源于增加的同质性。因此，我们需要重新考虑同质性在GSL中的重要性，并探索其他对GSL有效性有贡献的因素。

设计能够适用于不同数据集的GSL方法。我们的实验显示目前的GSL方法无法在所有数据集上起作用，因此我们需要设计能够适用于不同数据集的GSL方法。为了实现这一目标，有两个关键问题需要解决：1）学习到的结构应该具备哪些特性？2）如何将这些特性融入到结构学习过程中？有些结构特性可能很难进行评估或优化，因此需要进一步的研究。

提高GSL的效率。我们的实验揭示了GSL中的效率问题。当前GSL方法的实际效用受到这些效率问题的限制。虽然已经有工作尝试解决这个问题，但它们通常会牺牲GSL的表达能力。借鉴图神经网络(GNNs)中采样策略的成功应用，我们需要专门设计针对GSL的采样方法。

发展无监督的GSL。现有的GSL研究主要以任务为动机。然而，实际场景有时需要在不访问下游任务的情况下进行图结构的精细化。这一方面的核心挑战是如何从图数据中提取语义信息，并在没有标签的情况下定义结构的最优性。

四、总结

我们搭建了第一个针对图结构学习的基准库OpenGSL。其中我们囊括了12个前沿GSL方法和10个数据集，实现了公平的比较和系统的评估，同时我们通过实验得到了若干关键发现，并指出了可能的研究方向。我们希望OpenGSL能够对GSL这一新兴研究领域产生广泛的积极影响。我们期待大家使用OpenGSL进行GSL的开发和测试，也欢迎各种讨论和进一步贡献。

标题：OpenGSL: A Comprehensive Benchmark for Graph Structure Learning 论文链接：https://arxiv.org/abs/2306.10280 代码链接：https://github.com/OpenGSL/OpenGSL