【KD】2023 NeurIPS Does Graph Distillation See Like Vision Dataset Counterpart?

简介

在大规模图数据集上进行图神经网络（GNN）训练是一项繁重的任务。特别是在增量学习和图结构搜索等频繁需要重复训练的场景中，训练图模型不仅会带来显著的时间开销，还对内存和计算资源提出了严苛的限制。 最近，图数据集蒸馏/图压缩(Graph Dataset Distillation / Graph Condensation)方法受到了广泛关注，其目标是将海量原始图数据浓缩为一个规模极小但信息含量丰富的生成图，使得在该生成图上训练出的模型能够在极低的资源消耗下实现与原图相近的性能水平。

Paper:

https://arxiv.org/abs/2310.09192

Code:

https://github.com/RingBDStack/SGDD

然而，尽管现有的图数据蒸馏方法已取得显著进展，现有的图数据蒸馏（图压缩）方法却通常会简单地将图像数据上的蒸馏方法扩展至图数据上，却忽视了图结构在图数据蒸馏中至关重要的作用。通过理论分析与实验验证，我们发现现有方法对图结构的考量不足将直接影响生成图在多种下游框架（如GCN、GAT、APPNP等）上的表现，即，现有方法生成的压缩图在多种不同的下游框架下表现出明显差异，这不仅限制了这些方法的适用范围，也降低了它们的通用性。

本研究关注图结构对图数据蒸馏性能的影响。我们从谱域视角出发，定量评估了原始图与生成图间的结构差异，并通过实验验证了这种差异与生成图跨框架泛化能力之间的关系。在此基础上，我们提出了一种名为SGDD(Structure-broadcasting Graph Dataset Distillation)的方法，旨在减少生成图与原图在结构上的差异，从而显著提升生成图在不同框架间的泛化能力。

1. 现有方法的问题

现有的图数据蒸馏（图压缩）方法往往只是简单地将针对图像数据的蒸馏方法直接应用到图数据上，未能充分考虑图结构信息在图数据压缩过程中的重要性。这些方法在实际应用中可能面临性能和效率上的瓶颈，特别是在需要严格压缩率的场景下。

如下图(a)所示，现有的代表性图蒸馏方法(GCond[1])主要采用典型的梯度匹配(Gradient Matching)方式生成特征x'，并基于Pair-wise方式 f(x')构建结构特征。如图(b)所示，该方法压缩出的图谱未能有效保持原始数据集的结构信息。此外，如图(c)所示，该方法生成的图谱在不同下游任务框架下表现出相对较大的性能差异。

我们的方法(SGDD)通过有意识的传播结构A****信息[图(c)]到数据蒸馏过程中，更有效地保留了原图的结构信息。不仅生成图具有更好的结构特征[图(e)]，在多个下游框架中表现出一致的优秀性能[图(f)]。

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

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

具体而言，我们首先提出了拉普拉斯能量分布(Laplacian Energy Distribution, LED)的概念，用于分析图的谱特性。

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

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

在引入SC后，参考图(a)，我们采用不同框架进行压缩，展示了生成图LED分布的可视化结果，同时呈现了SC系数（SC）和跨框架性能（Avg.）的数值。进一步地，为了探究谱域滤波器的响应范围与生成图之间的关系，我们引入了可变频率响应的带通图滤波器BWGNN[2]。通过调节滤波器的频率响应范围(p, q)，我们揭示了SC系数与跨框架性能之间的关系。

结果显示，通过分析更小的SC系数（即原图与生成图的LED组件更接近）与跨框架性能提升之间的关系，发现两者之间具有显著的相关性。

**3.**SGDD 方法

在深入分析的基础上，我们提出了一种名为SGDD的方法，通过显式地利用原图结构，指导图数据蒸馏过程中的图结构优化。

本研究中，我们基于Graphon理论构建了一个图生成框架。在此基础上，我们融合了原图的结构信息，指导生成过程。为了缩小原图与生成图的LED分布差异，在此过程中，我们融合了最优传输理论（OT）。通过定义一个图生成器GEN，使得该生成器不仅能够实现图的结构优化，还能够有效降低生成过程中的计算开销。具体而言，GEN通过...

，其中 Z是随机噪声，我们的Loss函数可以表达为:

其次，我们旨在降低优化SC系数所需的时间开销，基于图匹配的理论假设，采用最优传输矩阵来替代传统的特征值分解和基于分布的节点对齐方法。随后，我们将上述Loss函数近似转换为以下形式：

在其中，P 作为自由变量，L+ 代表拉普拉斯伪逆操作，从而使得时间复杂度得以从 O(N^3) 转化为

。

整体算法流程如下：

4. 实验结果

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

在9个数据集和3种不同任务的环境下，我们对SGDD的性能进行了评估。其中，在常规的节点分类任务（node classification, ND）和链接预测任务（link prediction, LP）上，该方法表现突出。然而，由于异常检测任务（anomaly detection, AD）通常依赖于图数据中的关键信息[2]（现有方法可能无法有效提取这些关键信息），因此我们选择了若干具有代表性的数据集进行了实验。

我们提出的SGDD⽅法通常情况下展现出卓越的实验效果，尤其在规模较大的图数据集（如OGB-ND-Arxiv和Reddit）以及异常检测相关数据集上，充分验证了该方法的显著优势。

(2). 在异常检测相关数据集上，我们的改进更为显著。在YelpChi和Amazon数据集上，与GCond相比，我们的方法分别提升了9.6%和7.7%。这表明，我们的方法更有效地捕捉了原始图数据集中的关键信息（高频信息）。

4.2 跨框架泛化性实验

我们进一步在APPNP、Cheby、GCN、GraphSAGE以及SGC等框架中展开了跨框架泛化性实验（参考表2和表3），相较于现有方法，我们的方法在性能上实现了11.3%的显著提升，这一结果验证了将原始结构信息传播至生成图的有效性。

4.3 神经⽹络架构搜索实验

此外，在神经网络架构搜索（NAS）这一数据压缩典型应用场景中，SGDD在该场景中表现得优于GCond，并且其与表4中的皮尔逊相关系数进行对比。

4.4 生****成图可视化实验

我们对生成图进行了比较可视化实验，其中上半部分采用了Ogbn-arxiv数据集，下半部分则采用了SBM生成图的形式。观察到生成图在结构特征上与SGDD生成图(c, f)最为接近，与GCond生成图(b, e)和原图(a, d)的差异较小。其SC系数显著低于GCond生成图。

5. 总结

目前，图数据蒸馏领域仍是一个新兴的研究方向。本研究特别关注图结构保持在图数据蒸馏中的重要性，我们希望该研究能够激发领域内对这一方向的进一步探索和深入研究。

参考

NeurIPS'23 | 图数据提取与视觉数据蒸馏对比研究，

[1] Jin, Wei, et al. Graph Condensation for Graph Neural Networks. ICLR 2022.

Jianheng Tang and colleagues re-examined Graph Neural Networks in Anomaly Detection at the ICML 2022 conference.