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

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 ⽣成图的 SC 系数更低。

总结

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

参考文献

[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.

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：[e-mail] 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·

·

·