NeurIPS 2023 | 图数据蒸馏Partially=图像数据蒸馏：探究图结构对图数据蒸馏性能的影响…

?作者 | 杨贝宁

学校 | 北京航空航天大学

来源 | ACTBIGDATA

在大规模图数据集上进行 GNN 训练是一个艰巨的挑战。特别是在增量学习和图结构搜索这些经常需要重复训练的场景中，训练图模型不仅消耗大量时间，还对显存和计算能力提出了严峻要求。

最近，图数据集蒸馏/图压缩（Graph Dataset Distillation / Graph Condensation）方法引起了广泛关注，它旨在将庞大的原始图数据蒸馏至一个极小规模且信息丰富的生成图，使得在此生成图上的训练模型能够以极低的代价获得与原图相近的性能。

论文链接：

https://arxiv.org/abs/2310.09192

代码链接：

https://github.com/RingBDStack/SGDD

然而，尽管现有的图数据蒸馏方法取得了显著的进展，现有的图数据蒸馏(图压缩)方法往往是将面向图像数据的数据蒸馏方法简单扩展到图数据上，忽视了图结构在图数据蒸馏中的关键作用。

通过理论和实验分析，我们发现现有方法对图结构考量的不足会对生成图的跨框架能力有着较大的影响，即，现有方法生成的压缩图在多种不同的下游框架（如 GCN、GAT、APPNP 等框架）下有着并不一致的表现，这不仅限制了这些方法的适用范围，也削弱了它们的通用性。

因此，我们的研究聚焦于图结构对图数据蒸馏性能的影响。从谱域角度出发，我们定量分析了原始图与生成图间的“结构差异”，并实验性地验证了这种差异与生成图的跨框架泛化性能之间的关系。基于此，我们提出了一种名为 SGDD（Structure-broadcasting Graph Dataset Distillation）的方法，旨在减少生成图与原图在结构上的差异，进而显著提升生成图在不同框架间的泛化能力。

现有方法的问题

现有的图数据蒸馏（图压缩）方法往往是将面向图像数据的数据蒸馏方法简单扩展到图数据上，忽视了图结构信息在图数据压缩中的重要影响。

如下图（a）所示，现有的代表性图蒸馏方法（GCond [1]）采用了典型的梯度匹配（Gradient Matching）方法得到生成的特征，并利用 Pair-wise 的方法生成结构。如图（b）所示，这种方法压缩出来的图无法保留原始数据集的结构信息。进一步地，如图（c）所示，这种方法生成的图在不同的下游框架上有相对较大的性能差异。

我们的方法（SGDD）通过显式的传播（Broadcasting）原图的结构 信息 [图（c）] 到数据蒸馏过程中，能够更好的保留原图的结构信息，并且不仅使得生成图具有更好的结构特征 [图（e）]，而且在不同的下游框架上都有一致出色的性能表现 [图（f）]。

从谱域的角度衡量图结构信息对生成图性能的影响

为了可以定量的探究结构对方法的影响，我们选取了谱域角度进行分析。

具体来说，我们首先引入了拉普拉斯能量分布（Laplacian Energy Distribution, LED）的定义，用于在谱域中分析图结构的特性。

其次，原图和生成图的结构差异可以表示为两者的 LED 的差异：

进一步地，为了使得上式可以实际的计算，我们采用了直观的图匹配假设：“具有相似特征值分布比例的两个节点可以进行对齐比较。”进而引入 KDE 和 JS 散度来实际的衡量图 LED 分布的差异，并提出了衡量图 LED 分布差异的系数：

在引入了后，如图（a）所示，我们采用不同框架进行压缩，并展示了生成图 LED 分布可视化结果以及对应的系数（）和跨框架性能（Avg.）。进一步地，为了探究谱域滤波器响应范围和生成图之间的关系，我们引入可变频率响应的带通图滤波器 BWGNN [2]，通过调控滤波器的频率响应范围（p,q）来展示系数和跨框架性能的关系。

结果显示，更小的 系数（即原图和生成图的 LED 更佳接近）和跨框架性能提升之间有着较强的相关性。

SGDD 方法

基于上述分析，我们提出 SGDD（Structure-broadcasting Graph Dataset Distillation）方法，显式地利用原图结构指导图数据蒸馏过程中的图结构优化。

我们采用基于 Graphon 的图生成方法，在原有的梯度匹配基础上引入原图的结构信息指导的生成；并且为了缩小原图和生成图的 LED 分布差异，我们引入最优传输理论（Optimal transport, OT），将图匹配过程映射为自由变量，从而避免了特征值分解的时间开销，能够更高效的进行图结构优化。

具体来说，我们定义了一个图生成器使得，其中是随机噪声，我们的 Loss 函数可以表达为：

其次，为了降低优化系数的时间开销，我们从图匹配的假设出发，用最优传输矩阵代替复杂的特征值分解以及基于分布的节点对齐操作。最后我们将上述 Loss 函数近似转变为下述形式：

其中的为自由变量，为拉普拉斯伪逆操作，从而将时间复杂度从降低到。

整体算法流程如下：

实验结果

4.1 节点分类/异常检测/链接预测实验

我们在 9 个数据集，3 种不同任务上测试了 SGDD 的性能。除了常?的节点分类（node calssification, ND）和链接预测（link prediction, LP）任务上外，由于异常检测（anomaly detection, AD）任务往往依赖图数据中的?频信息 [2]（原图的?频信息可能被现有的?法过滤），我们也在常?的异常检测数据上做了实验：

1）我们提出的 SGDD ?法在多数情况下取得了最?的实验成果，特别是在较?规模的图（Ogbn-arxiv, reddit）和异常检测数据集上，展?了所提出?法的优越性。

2）在异常检测数据集上，我们的?法的改进更为明显。在 YelpChi 和 Amazon 数据集上，与 GCond ?，我们的?法分别提?了 9.6% 和 7.7%。证明了我们的?法更有效地捕捉了原始图数据集中的结构信息（?频信息）。