LLM2D
Bonsai:无梯度图凝练节点分类
Bonsai: Gradient-free Graph Condensation for Node Classification
作者: Mridul Gupta, Samyak Jain, Vansh Ramani, Hariprasad Kodamana, Sayan Ranu
发布日期: 3/27/2025
arXiv ID: oai:arXiv.org:2410.17579v5

摘要

arXiv:2410.17579v5 宣告类型: replace-cross 摘要:图凝聚已成为一种有希望的方法,通过压缩训练数据集以保留关键的图特性,从而实现大规模训练GNNs。我们的研究揭示了当前图凝聚技术中的重大不足。首先,大多数算法出乎意料地需要在完整数据集上进行训练才能执行凝聚。其次,由于它们采用梯度模拟方法,这些方法要求对任何超参数或GNN架构的改变都进行新的凝聚,这限制了其灵活性和再利用性。最后,由于生成完全连接、带有边权重的图,它们未能实现显著的规模缩减。为了解决这些挑战,我们提出了一种名为Bonsai的新颖图凝聚方法,该方法基于观察到的计算树是消息传递GNN的基本处理单元。Bonsai通过编码训练集中所有计算树的精心选择的示例树来压缩数据集,从而最大化表示所有计算树。这一独特方法使Bonsai成为首个在节点分类任务上优于现有基线的线性时间、模型无关的图凝聚算法,可在7个真实数据集上实现更高的准确率,并且平均快22倍。Bonsai基于采用的近似策略的严格数学保证,使其在GNN架构、数据集和参数方面具有鲁棒性。