ICDE 2025 | PKU-DAIR实验室论文被ICDE 2025

录用两篇

ICDE（International Conference on Data Engineering ）是数据库领域影响力最高的国际学术会议之一，也是CCF推荐的A类国际学术会议之一。第41届IEEE国际数据工程大会（ICDE）将于2025年5月19日-23日在中国香港举行。

PKU-DAIR实验室论文《 Towards Scalable and Efficient Graph Structure Learning 》和《Training-free Heterogeneous Graph Condensation via Data Selection》被数据库领域顶级会议ICDE 2025录用论文两篇。

一、面向可扩展且高效的图结构学习

作者：Siqi Shen, Wentao Zhang, Chengshuo Du ,  Chong Chen, Fangcheng  Fu, Yingxia  Shao,  Bin Cui

1. 引言

图结构学习（Graph Structure Learning，GSL）是一类提升图结构质量和图神经网络（GNN）下游任务表现的方法。然而，在实际应用中，GSL通常面临以下两大挑战：

（1）可扩展性不足

GSL方法的扩展性受限于高计算复杂度和架构耦合。许多方法的运算复杂度高达O(N^2)（N为节点数），导致执行时间长、内存消耗大，尤其在大规模图上表现明显。此外，结构优化模块与特定GNN架构紧密耦合，难以与如SGC、SIGN等可扩展GNN兼容，进一步限制了其适用性。

（2）效率低下

现有的GSL方法效率偏低，实验结果充分证明了这一点。我们选用三个常用数据集（Cora、Citeseer和Pubmed），并选取了NodeFormer、CoGSL和SLAPS三个代表性GSL基线模型，记录了它们在上述数据集上的端到端训练时间。实验结果（下图）显示，即便在小规模图数据上，这些GSL方法的处理时间也显著高于普通GNN的训练时间，并且随着图规模的增大，执行时间呈现快速增长趋势。同时，图结构优化与图学习模块的强耦合性要求每次更换GNN架构时都需重新训练，进一步增加计算开销，降低灵活性。

                                            图1. 在三个数据集上的不同执行时间

这些挑战凸显了在大规模图学习任务中，提升GSL方法可扩展性和效率的紧迫性。

2. 方法

针对现有GSL方法在可扩展性和效率上的不足，我们提出了一种新方法，称为基于随机游走的图结构学习（简称RWGSL）。

为了解决可扩展性问题，我们引入了邻域采样和随机游走策略，避免了对图中所有节点对进行大规模计算的需求，从根本上降低了计算复杂度，显著缓解了高复杂度带来的计算资源消耗。

为了解决效率问题，我们将图结构优化模块与图学习模块解耦，并将优化过程前置到数据预处理阶段。此设计具有两方面优势：一方面，可以利用多进程并行技术加速图结构优化过程；另一方面，优化后的图结构与具体的GNN架构无关，从而具备更高的通用性和灵活性。

在图结构优化模块中，我们综合考虑图拓扑结构和监督信号等多方面因素，计算节点间的多维度相似性，以进一步提升方法的有效性，确保优化后的图结构能够更好地支持下游任务的性能表现。下图是我们的方法框架。

图2. RWGSL框架

3. 实验结果

下表展示了RWGSL在三个中等规模数据集上的节点分类结果。为清晰起见，我们标注了每种基础GNN模型在使用优化后的图结构作为输入时所带来的准确率提升。此外，我们将每个数据集上的最佳结果用加粗表示，次优结果用下划线标注。

表1. 中等规模数据集上的节点分类结果

实验结果表明，与原始图相比，使用RWGSL处理后的图能够显著提升分类准确率。具体而言，RWGSL将基础GCN的分类准确率在Cora数据集上提升了3.0%，在Citeseer数据集上提升了2.6%，在Pubmed数据集上提升了2.1%。值得注意的是，当RWGSL与GCN结合时，其表现可与其他先进的图结构学习方法相媲美。此外，这些结果进一步验证了RWGSL的强泛化能力：优化后的单一图结构能够在所有基线模型中一致提升性能。

我们还在一个大规模数据集Ogbn-Products上进行了实验，其结果展示在下表的左两列中。

表2. 大规模数据集上的实验结果

该表清楚地表明，大多数图结构学习方法在处理大规模图时面临显著挑战。虽然NodeFormer在一定程度上展现了处理大规模图的能力，但其表现仍未达到最优。相比之下，当与可扩展的GNN结合时，我们的方法RWGSL能够有效优化大规模图的拓扑结构，展现出令人期待的结果。具体而言，RWGSL将SGC的分类准确率提升了4.0%，SIGN提升了1.7%，GraphSAGE提升了1.3%，GraphSAINT提升了1.6%。这些结果表明，RWGSL在处理大规模图结构优化方面具有显著优势，能够有效提升可扩展GNN的性能。

4. 总结

通过对图结构学习方法的调研和实践，我们发现现有工作普遍面临两个关键挑战：可扩展性有限和效率低下。具体而言，这些方法在处理大规模图数据集时常常遭遇运行时间过长和内存消耗过大的问题。为了解决这些局限性，我们提出了一种无参数、非参数学习型的图结构学习方法——RWGSL。

RWGSL通过在数据预处理阶段优化图结构并利用采样策略缩小搜索空间，显著降低了计算复杂度。其优化后的图结构为图学习模型提供了更高质量的输入，在多种图类型上均实现了性能的持续提升。

我们在多个数据集上进行了广泛实验，验证了RWGSL的有效性和可扩展性，为高效图学习技术的进一步探索与发展提供了新的方向和动力。

二、通过数据选择实现无需训练的异构图压缩

作者：Yuxuan Liang, Wentao Zhang, Xinyi Gao, Ling Yang, Chong Chen, Hongzhi Yin, Yunhai Tong, Bin Cui

论文链接：https://arxiv.org/abs/2412.16250

1. 引言

最近，图压缩（GC）已被提出作为密集计算问题的一种有前途的解决方案。图压缩旨在通过学习合成图结构和节点属性来压缩大型原始图。作为关键设计，GC 利用中继模型连接原始图和合成图，方便两个图的比较和压缩优化。遵循 GCond 的梯度匹配范式，HGCond是第一个提出的用于压缩异构图的工作。与 GC 不同，它使用聚类信息进行超节点初始化，并采用正交参数序列（OPS）策略来探索参数。虽然这种方法可以压缩异构图，但它仍然存在两个局限性：

（1）低性能： 考虑到模型复杂性导致的过拟合问题，HGCond 被迫仅使用最简单的异构图模型作为图压缩的中继模型，其压缩精度与最先进的 (SOTA) HGNN之间存在很大差距。即使使用先进的 HGNN 作为中继模型，性能也会变差。此外，复杂的优化问题使得 HGCond 的性能随着压缩图的大小增加而下降或变平。同时，HGCond还存在泛化性差的问题。

（2）效率低： 遵循同构图压缩方法 GCond 的范式，HGCond 需要双层优化和嵌套循环来压缩异构图。这种复杂的压缩过程计算量大且耗时。举例来说，在128 个 epoch下大约需要 1 小时（在单个 TITAN RTX GPU 上运行）才能将大规模数据集 AMiner压缩到 1%。

为了解决上述两个挑战，本文提出了一种新的无需训练的异构图压缩方法，称为 FreeHGC，用于从原始图结构中选择和合成高质量图，而无需模型训练过程。与传统的异构图压缩不同，传统的异构图压缩通过迭代训练中继模型来优化合成图和参数，如图 1 所示，我们提出的 FreeHGC 与模型无关，仅在预处理阶段压缩图。图 1 还从四个关键标准突出了 FreeHGC 与 HGCond 相比的优势：有效性、效率、灵活的压缩率和泛化。

图1. 现有异构图压缩方法与FreeHGC 的对比

2. 方法

FreeHGC执行流程。我们提出第一种无需训练的异构图压缩方法——FreeHGC。如图2所示，我们的方法分为两个部分：压缩目标类型节点和压缩其他类型节点。第一个部分使用感受野最大化函数和元路径相似度最小化函数，基于图结构的直接影响和元路径之间的间接影响来计算节点的重要性。然后，FreeHGC将这两个函数结合起来作为统一的数据选择标准来选择高质量数据，在确保每个节点沿着不同的元路径捕获更丰富的图结构信息的同时，最大化节点的影响力。第二个部分使用邻居重要性最大化函数来选择重要的父类型节点，并使用信息损失最小化函数来合成叶类型节点。重复上述过程，直到获得压缩图。

图2. FreeHGC架构

3. 实验结果

实验主要包含以下五个方面：（1）有效性；(2) 可扩展性；(3) 泛化性；(4) 压缩数据分析；(5)消融实验。这里选取具有代表性的有效性实验和可扩展性实验，其余实验可参考论文。

（1）与最先进的图压缩方法进行端到端比较：如表1所示，在大多数压缩率设置下，FreeHGC 的表现均优于所有基线方法。

表2. 节点分类预测任务的实验结果

（2）可扩展性：如表2所示，FreeHGC在不同的压缩率下表现最佳，且准确度逐渐提高。

表3. 大规模数据集上的实验结果

4. 总结

本文提出了一种新的无需训练的异构图压缩方法——FreeHGC。其目标是从原始大图中选取并合成高质量节点，然后将其压缩为无需训练的小图。节点分类任务上的实验结果表明，FreeHGC 可以在保持令人满意的性能的同时显著减小图的大小，并且具有灵活压缩率的优势。此外，实验结果还表明我们的方法具有良好的泛化性和可扩展性。

实验室简介

北京大学数据与智能实验室（Data And Intelligence Research Lab at Peking Univeristy，PKU-DAIR实验室）由北京大学计算机学院崔斌教授领导，长期从事数据库系统、大数据管理与分析、人工智能等领域的前沿研究，在理论和技术创新以及系统研发上取得多项成果，已在国际顶级学术会议和期刊发表学术论文100余篇，发布多个开源项目。课题组同学曾数十次获得包括CCF优博、ACM中国优博、北大优博、微软学者、苹果奖学金、谷歌奖学金等荣誉。PKU-DAIR实验室持续与工业界展开卓有成效的合作，与腾讯、阿里巴巴、苹果、微软、百度、快手、中兴通讯等多家知名企业开展项目合作和前沿探索，解决实际问题，进行科研成果的转化落地。