Simple yet Effective Graph Distillation via Clustering

📄 arXiv: 2505.20807v1 📥 PDF

作者: Yurui Lai, Taiyan Zhang, Renchi Yang

分类: cs.LG

发布日期: 2025-05-27

备注: This is the technical report of the paper "Simple yet Effective Graph Distillation via Clustering" accepted by KDD 2025

💡 一句话要点

提出ClustGDD，通过聚类实现高效图数据蒸馏，加速GNN训练。

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

关键词: 图数据蒸馏 图神经网络 聚类算法 节点分类 大规模图数据

📋 核心要点

  1. 现有图数据蒸馏方法依赖启发式对齐梯度或表示，导致质量下降或训练成本高昂。
  2. ClustGDD通过聚类合成压缩图和节点属性，最小化簇内方差，最大化图同质性。
  3. 实验表明，ClustGDD在节点分类任务上性能优越，且训练速度远超现有方法。

📝 摘要（中文）

图表示学习在各个领域取得了显著成功，但由于实际应用中大型图所需的巨大计算开销，图神经网络(GNN)的训练仍然面临挑战。图数据蒸馏(GDD)通过将大型图提炼成紧凑且信息丰富的图，成为一种有前景的技术，可以实现高效的GNN训练。然而，现有GDD方法大多依赖于启发式方法，对齐压缩图和原始图上的模型梯度或表示分布，导致结果质量下降，或蒸馏大型图的训练成本过高。为此，本文提出了一种高效且有效的GDD方法ClustGDD。ClustGDD通过快速且理论上有依据的聚类来合成压缩图和节点属性，该聚类旨在最小化簇内平方和并最大化原始图上的同质性。该方法的核心思想源于我们的经验和理论发现，揭示了聚类与使用Fréchet Inception Distance（一种合成图像的常用质量指标）衡量的经验压缩质量之间的联系。此外，为了减轻基于同质性的聚类带来的不利影响，ClustGDD通过类感知图采样和一致性损失学习的小型增强来细化压缩图的节点属性。大量实验表明，在五个基准数据集上，使用ClustGDD生成的压缩图训练的GNN在节点分类方面始终优于或可与最先进的GDD方法相媲美，同时速度提高了几个数量级。

🔬 方法详解

问题定义：现有图数据蒸馏方法在处理大规模图数据时，面临着计算开销大、训练效率低的问题。这些方法通常依赖于启发式算法，例如对齐原始图和压缩图之间的梯度或表示分布，但这些启发式方法往往会导致蒸馏后的图质量下降，或者需要大量的计算资源进行训练，尤其是在处理大型图时。因此，如何高效地将大型图蒸馏成一个紧凑且信息丰富的图，同时保证蒸馏后的图能够有效地用于GNN训练，是一个亟待解决的问题。

核心思路：ClustGDD的核心思路是利用聚类算法来合成压缩图和节点属性。具体来说，该方法通过最小化簇内平方和以及最大化原始图上的同质性来进行聚类，从而保证压缩后的图能够尽可能地保留原始图的结构信息和节点属性信息。这种基于聚类的图数据蒸馏方法不仅能够有效地降低计算复杂度，而且能够保证蒸馏后的图具有较高的质量，从而使得GNN能够在压缩图上进行高效且有效的训练。

技术框架：ClustGDD的整体框架主要包括两个阶段：聚类阶段和属性细化阶段。在聚类阶段，该方法首先利用聚类算法将原始图中的节点划分为若干个簇，然后将每个簇合并为一个节点，从而生成压缩图。在属性细化阶段，为了减轻基于同质性的聚类可能带来的不利影响，该方法利用类感知图采样和一致性损失学习的小型增强来细化压缩图的节点属性。

关键创新：ClustGDD的关键创新在于其利用聚类算法进行图数据蒸馏。与现有的基于启发式算法的图数据蒸馏方法相比，ClustGDD具有更高的效率和更好的性能。此外，ClustGDD还通过属性细化阶段来进一步提高压缩图的质量，从而使得GNN能够在压缩图上获得更好的训练效果。

关键设计：ClustGDD的关键设计包括：1) 使用K-means等聚类算法进行节点聚类；2) 基于聚类结果构建压缩图，其中每个簇对应压缩图中的一个节点；3) 使用类感知图采样和一致性损失学习的小型增强来细化压缩图的节点属性。损失函数的设计目标是使得压缩图的节点属性能够尽可能地保留原始图的节点属性信息，并且能够有效地用于GNN训练。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，ClustGDD在五个基准数据集上，使用压缩图训练的GNN在节点分类任务上始终优于或可与最先进的GDD方法相媲美，同时训练速度提高了几个数量级。例如，在某些数据集上，ClustGDD能够达到与现有方法相当的性能，但训练时间缩短了10倍以上。

🎯 应用场景

ClustGDD可应用于大规模图数据的快速分析和GNN模型的加速训练。例如，在社交网络分析、生物信息学、知识图谱推理等领域，可以先使用ClustGDD对原始图数据进行蒸馏，然后利用蒸馏后的图数据进行后续的分析和建模，从而显著降低计算成本，提高效率。该方法还有助于在资源受限的设备上部署GNN模型。

📄 摘要（原文）

Despite plentiful successes achieved by graph representation learning in various domains, the training of graph neural networks (GNNs) still remains tenaciously challenging due to the tremendous computational overhead needed for sizable graphs in practice. Recently, graph data distillation (GDD), which seeks to distill large graphs into compact and informative ones, has emerged as a promising technique to enable efficient GNN training. However, most existing GDD works rely on heuristics that align model gradients or representation distributions on condensed and original graphs, leading to compromised result quality, expensive training for distilling large graphs, or both. Motivated by this, this paper presents an efficient and effective GDD approach, ClustGDD. Under the hood, ClustGDD resorts to synthesizing the condensed graph and node attributes through fast and theoretically-grounded clustering that minimizes the within-cluster sum of squares and maximizes the homophily on the original graph. The fundamental idea is inspired by our empirical and theoretical findings unveiling the connection between clustering and empirical condensation quality using Fréchet Inception Distance, a well-known quality metric for synthetic images. Furthermore, to mitigate the adverse effects caused by the homophily-based clustering, ClustGDD refines the nodal attributes of the condensed graph with a small augmentation learned via class-aware graph sampling and consistency loss. Our extensive experiments exhibit that GNNs trained over condensed graphs output by ClustGDD consistently achieve superior or comparable performance to state-of-the-art GDD methods in terms of node classification on five benchmark datasets, while being orders of magnitude faster.