在大规模图数据集上进行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)的方法，旨在减少生成图与原图在结构上的差异，进而显著提升生成图在不同框架间的泛化能力。

1. 现有方法的问题

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

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

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

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

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

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

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

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

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

3. SGDD 方法

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

我们采用基于Graphon的图生成方法，在原有的梯度匹配基础上引入原图的结构信息 指导 的生成；并且为了缩小原图和生成图的LED分布差异，我们引入最优传输理论(Optimal transport, OT)，将图匹配过程映射为自由变量，从而避免了特征值分解的时间开销，能够更高效的进行图结构优化。具体来说，我们定义了一个图生成器 使得 ，其中 是随机噪声，我们的Loss函数可以表达为:

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

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

整体算法流程如下：

4. 实验结果

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%。证明了我们的方法更有效地捕捉了原始图数据集中的结构信息（高频信息）。

4.2. 跨框架泛化性实验

我们进一步在APPNP，Cheby，GCN，GraphSAGE以及SGC框架上进行了跨框架泛化性实验（见表2和表3），与现有方法相比，我们的方法的改进高达11.3%，这证明了将原始结构信息传播到生成图中的有效性。

4.3. 神经网络架构搜索实验

此外，在数据压缩典型的应用场景—神经网络架构搜索(NAS)中，SGDD也取得了相较于GCond更高的性能表现以及皮尔逊相关系数指数（见表4）。

4.4. 生成图可视化实验

我们对生成图进行了可视化实验，其中上半部分是采用Ogbn-arxiv数据集，下半部分采用SBM生成图的形式。可以看到相较于GCond生成图(b, e), SGDD生成图(c, f)和原图(a, d)更为接近。并且SGDD生成图的 系数更低。

5.总结

面向图数据的蒸馏目前仍为一个较新的方向，我们的研究着眼于图结构对图数据蒸馏的重要性，期望此工作能够引起领域对该方向更多的研究和探讨。

参考文献

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

2.Jianheng Tang,et al. Rethinking Graph Neural Networks for Anomaly Detection. ICML 2022.

公众号后台回复“数据集”获取100+深度学习各方向资源整理