通过高斯过程实现的高效图简化

《IEEE Transactions on Knowledge and Data Engineering》：Efficient Graph Condensation via Gaussian Process

针对大规模图数据训练效率低下的问题，本文提出基于高斯过程的图凝聚方法GCGP，通过结构信息协方差函数扩展节点感受野，并利用混凝土随机变量实现二进制邻接矩阵的连续化，消除迭代训练需求，显著提升计算效率与模型性能。

　　

摘要：

图压缩技术在保持性能的同时减小了大型图的规模，解决了图神经网络（GNN）在处理大规模数据集时遇到的可扩展性问题，这些问题通常由计算效率低下引起。现有方法往往依赖于双层优化，需要大量的GNN训练，从而限制了其可扩展性。为了解决这些问题，我们提出了基于高斯过程（Gaussian Process, GCGP）的图压缩技术，这是一种新颖且高效的框架，能够优化出紧凑、高保真的压缩图，以较低的计算成本实现对各种GNN的有效训练。GCGP利用高斯过程（GP），以压缩图作为观测值来估计预测的后验分布。这种方法消除了GNN通常所需的迭代和资源密集型训练过程。为了增强GCGP捕捉函数值之间依赖关系的能力，我们推导出一个专门的协方差函数，该函数结合了结构信息。这种协方差函数通过局部邻域聚合扩大了输入节点的感受野，从而有助于表示节点内部的复杂依赖关系。为了解决在压缩图中优化二进制结构信息的挑战，我们使用具体随机变量（Concrete random variables）来近似二进制邻接矩阵的连续形式。这种放松处理使得邻接矩阵可以以可微分的形式表示，从而可以将基于梯度的优化技术应用于离散图结构。实验结果表明，所提出的GCGP方法能够高效地压缩大规模图数据，同时保持预测性能，有效解决了可扩展性和效率方面的问题。

引言

图结构数据由节点和边组成，是一种多用途的表示方法，用于建模各种现实世界系统，包括社交网络[1]、交通基础设施[3]、[4]以及分子结构[5]、[6]。图结构数据能够捕捉关系和交互，使其成为描述复杂系统的强大工具。为了从图结构数据中有效提取有意义的见解，人们开发了图神经网络（GNNs）[7]、[8]、[9]，这是一种专门的深度神经网络类别。GNN通过利用消息传递机制[10]来处理图数据。通过从相邻节点迭代聚合信息，GNN扩展了节点的感受野，使它们能够表示局部和全局图结构[11]。这一能力使得GNN在许多图挖掘任务中表现出色[12]、[13]、[14]。尽管取得了成功，但由于图数据规模庞大[15]、[16]、[17]，GNN的应用仍面临重大挑战。训练和部署GNN通常需要大量的计算资源，包括大量内存和长时间的GPU使用。此外，训练迭代、超参数调整和神经架构搜索的需求也严重限制了它们的实际应用。