Graph Distillation
with Eigenbasis Matching
「作者」
Yang Liu, Deyu Bo, Chuan Shi
「单位」
北京邮电大学
「摘要」
随着图数据量的不断增加，高效训练图神经网络（graph neural networks, GNNs）的需求也在不断提升。新兴的图蒸馏（graph distillation, GD）技术为这一挑战提供了解决思路，图蒸馏通过生成一个小的合成图来代替真实的大规模图，并确保在合成图上训练的GNNs表现出与在真实图上训练相当的性能。然而，现有的方法依赖与GNNs相关的信息进行监督，例如梯度、表征和轨迹，这样做有两个局限性。首先，GNNs可能会影响真实图的谱（spectrum，即特征值），造成在合成图上产生谱偏差。其次，使用不同架构的GNNs蒸馏会生成不同的合成图，为了训练不同的GNNs都能获得最优性能，需要遍历各种架构的GNNs蒸馏出相应的合成图。为了解决这些问题，我们提出了基于特征基匹配的图蒸馏方法（Graph Distillation with Eigenbasis Matching, GDEM），该方法在蒸馏过程中对齐了真实图和合成图的特征基和节点特征，并直接复制真实图的谱来构建合成图，以避免GNNs带来的影响。除此之外，我们还设计了一个判别约束项，并通过调整各损失项的权重来平衡GDEM的有效性和泛化性。理论分析表明，GDEM蒸馏出的合成图保留了真实图的谱相似性。大量实验表明，GDEM的跨架构泛化能力和蒸馏效率远远超越了现有最先进的图蒸馏方法。
1. 背景与动机
图神经网络（Graph neural networks, GNNs）在各种图相关任务中已被证明是有效的。然而，图的非欧几里得性质为GNNs的训练效率和可扩展性带来了挑战。为了加速训练，一种以数据为中心的方法是将大规模图简化为一个更小的图。传统方法包括图稀疏化和图粗化，然而，这些方法通常旨在优化一些启发式指标，例如谱相似性和成对距离，这些指标可能与下游任务无关，从而导致次优的性能。
近年来，图蒸馏（GD），也称作图压缩，凭借其显著压缩比和无损性能在图简化领域引起了广泛的关注。GD的目标是合成一个小图，使得在该小图上训练的GNNs能够表现出与在真实大图上训练的GNNs相当的性能。为实现这一目标，现有方法通过匹配一些与GNNs相关的信息（如梯度、表征和训练轨迹）来优化合成图。合成图借此将分布对齐到了真实图，同时还结合了来自下游任务的信息。
尽管取得了相当大的进展，现有图蒸馏（GD）方法需要预先选择一个特定的GNN作为蒸馏模型，这造成了两方面限制：
「(1) 用于蒸馏的GNNs会影响真实谱，导致合成图产生谱偏差，即少数特征值主导了数据分布。」
Figure 1展示了真实图和合成图的总变差（Total Variation, TV），TV通常用于反映信号在图上的平滑度，小的TV值表示低频分布，反之亦然。我们可以观察到，由低通滤波器蒸馏的合成图中的TV值始终低于真实图的TV值，而高通滤波器的情况则相反，从而验证了谱偏差的存在。
「(2) 为获得最优性能，需要遍历各种GNNs架构，这导致了不可忽视的计算成本。」
Table 1展示了GCOND在六个常用GNNs（包括GCN，SGC，PPNP，ChebyNet，BernNet和GPRGNN）的跨架构结果。可以看到，每行中不同GNNs的性能差异很大。因此，现有GD方法需要遍历多种GNNs架构来进行蒸馏，以获得最优性能，这显著增加了时间开销。
根据现有方法的不足，一个自然的问题由此产生：
「如何在不受GNNs影响的情况下进行图蒸馏？」
因此，我们提出了基于特征基匹配的图蒸馏方法（GDEM）。具体来说，GDEM将图结构分解为特征值和特征基，在蒸馏过程中，GDEM只匹配真实图和合成图的特征基和节点特征，从而均衡地保留不同频率的信息，解决了谱偏差问题。此外，我们优化时还引入了一个判别损失项以提高GDEM的性能，并通过调整损失项之间的权重来平衡其有效性和泛化性。在完成优化后，GDEM利用真实图的谱和合成特征基构建完整的合成图，从而防止谱受到GNNs的影响，并确保了合成图的唯一性，从而避免了遍历需求，提高了蒸馏效率。
本文的主要贡献如下：(1) 我们系统分析了现有蒸馏方法的局限性，包括谱偏差和遍历需求。(2) 我们提出了GDEM，一个新的图蒸馏框架，通过匹配特征基而不是整个图结构来减轻对特定GNNs的依赖。此外，理论分析证明了GDEM在蒸馏过程中保留了谱的相似性。(3) 我们在七个图数据集上进行了大量的实验，验证了GDEM在有效性、泛化性和效率等方面超越了现有最先进的GD方法。
2. 符号定义
本文主要以节点分类的任务场景为例，给定图
，其中
是节点集合且
，
表示边集合，
是节点特征矩阵。图
的邻接矩阵为
，如果节点
和
之间存在边，则
，否则
。对应的归一化拉普拉斯矩阵为
，其中
是单位矩阵，
是度矩阵，其中对于每个节点
，
，当
时，
。
「特征基和特征值」
归一化图拉普拉斯矩阵可以分解为
，其中
是特征值，且
，
是特征基，由一组特征向量组成。每个特征向量
有一个对应的特征值
，且
。
「图蒸馏」
图蒸馏（GD）旨在从真实的大图
中蒸馏出一个小的合成图
，其中
且
，使得在
和
上训练的GNNs将具有相似的性能，从而加速GNNs的训练。现有框架可以分为三类：梯度匹配、分布匹配和轨迹匹配。
3. 梯度匹配中的谱偏差
我们系统分析了梯度匹配的目标函数，并为GDEM的设计提供了灵感与指导。我们从一个简单的例子开始：当蒸馏模型为单层GCN，GNNs的目标函数为MSE Loss时：
其中，
是模型参数。真实图和合成图上的梯度分别为：
假设梯度匹配的目标是两个梯度之间的MSE Loss，即
，
的上界可表示为：
其中，
和
是用于监督合成图更新的两个目标分布，根据以下分析，它们都会被少数特征值主导，导致谱偏差。
「引理 3.1」
当蒸馏模型GCN经过多层堆叠后，目标分布会由最小的特征值主导。
「证明」
此时目标分布可以表示为：
其中，
是层数。当
趋于无穷大时，只有最小的特征值
保留其系数，即
，其他系数趋近于0，因此，目标分布
被
主导。
同理可得。
「引理 3.2」
假设蒸馏GNNs的滤波函数为
，目标分布将由滤波值大于1（即
）的特征值主导。
「证明」
此时蒸馏GNNs的目标函数为
，目标分布变为
和
。因此，只有滤波值
的特征值保留了系数，并主导目标分布。
引理3.1和3.2表明，在蒸馏过程中使用GNNs相关的信息会在目标分布中引入谱偏差，导致合成图只能匹配真实图数据分布的一部分，导致其结构信息不完整。
4. 方法：GDEM
与先前方法（例如，梯度匹配Figure 2(a)和分布匹配Figure 2(b)）相比，GDEM（见Figure 2(c)）不依赖于特定的GNNs，其蒸馏过程分为两个步骤：(1) 匹配真实图和合成图之间的特征基和节点特征。(2) 使用合成的特征基和真实图的谱构建合成图。
4.1. 特征基匹配
图的特征基代表了其关键的结构信息，例如，较小特征值的特征向量反映了全局社区结构，而较大特征值的特征向量编码了局部细节。由于特征向量的数量与图中的节点数相同，我们无法在合成图中保留所有真实的特征基，因此，GDEM匹配了
个最小特征值和
个最大特征值的特征向量，其中
和
是超参数，且
。这种方法在图粗化和谱图神经网络中被普遍证明是有效的。我们通过优化矩阵
以匹配真实图的主要特征基
。为消除GNNs的影响，GDEM在蒸馏过程中不使用谱信息，因此，公式3中的第一个项变为：
其中，
和
是由真实图和合成图中的第
个特征向量构成的子空间。
此外，作为图傅里叶变换的基，特征向量具有正交归一化的性质，然而，通过梯度下降直接优化
不能保留这种性质，因此，我们使用了一个额外的正则化来约束表示空间：
