Does Graph Distillation See Like Vision Dataset Counterpart?

📄 arXiv: 2310.09192v1 📥 PDF

作者: Beining Yang, Kai Wang, Qingyun Sun, Cheng Ji, Xingcheng Fu, Hao Tang, Yang You, Jianxin Li

分类: cs.LG, cs.AI

发布日期: 2023-10-13

备注: Accepted by NeurIPS 2023

🔗 代码/项目: GITHUB

💡 一句话要点

提出结构广播图数据蒸馏方法以提升图表示学习性能

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 图表示学习 图数据蒸馏 结构信息 拉普拉斯能量分布 异常检测 链接预测 深度学习

📋 核心要点

  1. 现有图凝聚方法忽视了原始图结构信息的影响，导致性能下降。
  2. 提出的SGDD方法通过结构广播机制，确保合成图保留原始结构信息。
  3. 在9个数据集上验证SGDD的有效性，取得了显著的性能提升和LED变化减少。

📝 摘要（中文）

在大规模图的训练中，图表示学习取得了显著成果，但其成本和存储问题日益受到关注。现有的图凝聚方法主要集中在优化凝聚图的特征矩阵，而忽视了原始图的结构信息对性能的影响。本文通过谱域分析，识别出以往方法中拉普拉斯能量分布（LED）的显著变化，导致跨架构泛化和特定任务（如异常检测和链接预测）表现不佳。为此，提出了一种新颖的结构广播图数据蒸馏（SGDD）方案，旨在将原始结构信息传递到合成图的生成中，从而显著减少LED的变化。实验结果表明，SGDD在9个数据集上均取得了最先进的结果，例如在YelpChi数据集上，测试准确率达到98.6%，且图规模节省达1000倍。

🔬 方法详解

问题定义：本文旨在解决现有图凝聚方法在优化特征矩阵时忽视原始图结构信息的问题，导致跨架构泛化能力和特定任务性能下降。

核心思路：SGDD方法通过结构广播机制，将原始图的结构信息有效传递到合成图中，确保合成图在特征和结构上都能更好地反映原始图的特性。

技术框架：SGDD的整体架构包括数据预处理、结构信息提取、合成图生成和性能评估四个主要模块。首先提取原始图的结构信息，然后生成合成图，最后通过多种任务评估合成图的有效性。

关键创新：SGDD的主要创新在于其结构广播机制，显著减少了合成图与原始图之间的LED变化，这与以往方法的特征矩阵优化策略本质上不同。

关键设计：在SGDD中，设计了特定的损失函数以平衡特征保留与结构信息的传递，同时采用了多层图神经网络架构来增强合成图的表达能力。具体参数设置和网络结构细节在实验部分进行了详细描述。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

SGDD在9个数据集上均取得了最先进的结果，特别是在YelpChi数据集上，测试准确率达到98.6%，并且在多个数据集上LED变化减少了17.6%至31.4%。这些结果表明SGDD在跨架构设置和特定任务中均表现优越。

🎯 应用场景

该研究的潜在应用领域包括社交网络分析、推荐系统、异常检测等。通过提升图表示学习的性能，SGDD能够帮助研究人员和工程师在处理大规模图数据时，获得更高的准确性和效率，具有重要的实际价值和未来影响。

📄 摘要（原文）

Training on large-scale graphs has achieved remarkable results in graph representation learning, but its cost and storage have attracted increasing concerns. Existing graph condensation methods primarily focus on optimizing the feature matrices of condensed graphs while overlooking the impact of the structure information from the original graphs. To investigate the impact of the structure information, we conduct analysis from the spectral domain and empirically identify substantial Laplacian Energy Distribution (LED) shifts in previous works. Such shifts lead to poor performance in cross-architecture generalization and specific tasks, including anomaly detection and link prediction. In this paper, we propose a novel Structure-broadcasting Graph Dataset Distillation (SGDD) scheme for broadcasting the original structure information to the generation of the synthetic one, which explicitly prevents overlooking the original structure information. Theoretically, the synthetic graphs by SGDD are expected to have smaller LED shifts than previous works, leading to superior performance in both cross-architecture settings and specific tasks. We validate the proposed SGDD across 9 datasets and achieve state-of-the-art results on all of them: for example, on the YelpChi dataset, our approach maintains 98.6% test accuracy of training on the original graph dataset with 1,000 times saving on the scale of the graph. Moreover, we empirically evaluate there exist 17.6% ~ 31.4% reductions in LED shift crossing 9 datasets. Extensive experiments and analysis verify the effectiveness and necessity of the proposed designs. The code is available in the GitHub repository: https://github.com/RingBDStack/SGDD.