方法主要优点主要问题图粗化传播结果通常更接近原图节点表示更容易趋同，过平滑更严重图稀疏化更能保持节点表示的多样性传播结果会逐渐偏离原图为什么粗化更容易过平滑？粗化首先把多个节点的特征取平均，再在超级节点之间传播。 因此，它实际上进行了两次“混合”： 合并节点时先平均一次； 后续传播时继续聚合。 节点之间的差异因此更快消失，数值秩也更容易下降。不过，粗化保留了较完整的聚合关系，所以其长期传播轨迹通常更接近原图。为什么稀疏化能缓解过平滑？稀疏化删除了一部分边，节点每次传播时能接触到的邻居变少，因此特征混合速度下降，节点之间的差异能够保留更久。但删除边也改变了信息传播路径。因此，传播层数越深，这种结构差异反复累积，压缩图的结果就越偏离原图。需要注意：随机删边可能制造大量孤立节点。这些节点因为无法与邻居交换信息而保留原始特征，看起来“多样性很高”，但实际上可能只是图断连造成的假象。摘要图压缩能够降低图学习的计算成本，但它对信号传播的影响在很大程度上仍未得到充分探索。现有工作通过下游任务性能或结构保持性来评估压缩，而这两者都不能直接刻画压缩后传播动力学如何变化。我们研究两种基本的压缩范式——粗化与稀疏化，并探究它们是否能够保留原图的传播行为。我们在五个数据集、不同压缩率和不同传播深度下，通过三个互补指标衡量信号行为。结果揭示了两类压缩方法之间一种稳定存在的矛盾：稀疏化能够保留更高的信号多样性并缓解过平滑，但其传播轨迹会逐渐偏离原图；粗化能够更忠实地保留传播行为，却以更强的平滑和秩坍塌为代价。上述发现表明，在图压缩条件下，“保持信号多样性”与“保持传播保真度”这两个以传播为中心的目标彼此不同，并且在经验上相互冲突。因此，评估协议需要同时考虑这两个维度。代码与实验结果：https://github.com/KawshikBanerjee/Compression-Propagation-Duality关键词：图压缩，过平滑，图学习一、引言图压缩已经成为应对大规模图学习计算和内存需求的一种实用方案：它在缩小图规模的同时，力求保留有效学习所需的性质 [1]–[4]。图压缩研究已经形成两种主要范式：一是粗化，即把多个节点合并成超级节点，从而降低图的阶数 [5], [6]；二是稀疏化，即通过剪除边来减小图的规模 [7], [8]。尽管压缩方法已经取得显著进展，其评估却一直集中于少量下游代理指标。最常见的方法是通过下游任务表现来评价压缩质量，例如分类准确率或链路预测的曲线下面积（AUC）[9], [10]。另一类互补工作评估结构保持性，考察压缩后能否保留谱性质 [11] 或割保证 [5]。这两种视角都很有价值，但均未直接回答一个问题：反复应用图算子时，压缩是否保留了节点特征的演化方式 [12]。本文将这一过程称为信号传播。这种区别具有实际意义。传播是图结构影响节点表示的机制。如果压缩改变了传播动力学，那么一个节点在压缩后接收到的信号，就会从根本上不同于它在原图中接收到的信号——即使下游任务指标看起来没有受到影响也是如此 [13]。理解这一差距，直接关系到何时以及如何安全地应用图压缩。本文从以传播为中心的视角研究图压缩。我们在多个图数据集上，以不同的压缩率和传播深度评估具有代表性的粗化与稀疏化方法，并采用互补指标衡量信号行为；这些指标既刻画信号的内在平滑程度，也刻画其相对于原始传播轨迹的保真度。分析揭示出两种范式之间稳定且鲜明的矛盾：粗化方法能够紧密跟随原始传播轨迹，却会造成更强的信号平滑，即过平滑 [14]–[16]；稀疏化方法能够更好地保留信号多样性并抵抗过平滑，但随着深度增加，其传播轨迹会逐渐偏离原图。在这两种范式下，保持信号多样性与保持传播保真度这两个目标在经验上都是相互冲突的。本文的主要贡献如下：我们识别并通过实验刻画了图压缩中的两个不同且在经验上相互竞争的评估目标：信号多样性保持与传播保真度保持。我们对两种范式下的六种压缩方法进行了系统的实证分析，覆盖五个数据集、多个压缩率和传播深度，并使用三个以传播为中心的指标。我们表明，粗化与稀疏化之间的矛盾能够推广到各范式内的不同方法，同时各方法之间仍存在重要差异；在面向过平滑的指标上表现有利的方法，也可能同时大幅偏离原始传播轨迹。二、相关工作图压缩将大图缩减为小图，同时保留与下游任务相关的性质 [4], [17]。本文不根据压缩对任务性能的影响来评价它，而是研究压缩后传播算子本身如何表现，即压缩图上的传播信号能够在多大程度上复现原图上的信号。我们关注两种具有无训练传播算子的范式：减少节点集合的粗化，以及减少边集合的稀疏化。A. 图粗化图粗化通过把节点分组为超级节点，并聚合它们之间的连接来缩小图 [6]。重边匹配（Heavy Edge Matching，HE）[18] 反复按照最重的边匹配相邻节点对，再将其收缩为单个超级节点，从而优先保留较强的局部连接。变分邻域（Variation Neighborhoods，VN）[5] 采用更宽泛的视角：把每个节点及其全部邻居作为候选收缩集合，并以贪心方式收缩局部变分最小的组。局部变分是一种局部化指标，用于衡量所保留的信号在组内有多不平滑。这两种方法都以节点对或局部结构相似性作为合并准则。NOPE [19] 则通过优先考虑集体性的邻域干扰而区别于上述方法。它不是独立优化每次合并，而是惩罚邻域层面的偏差，从而避免这样的合并决策：它虽然保留了节点对相似性，却破坏了周围的语义结构。B. 图稀疏化图稀疏化通过删除部分边，用稀疏图近似稠密图 [20]。其理论依据是：每个图都存在规模近线性的谱稀疏器 [21]。在实践中，稀疏化方法依据某种结构目标为每条边打分，再进行全局过滤，以保留目标比例的边 [8]。随机边（Random Edge，RE）[8] 是最简单的方法，它不考虑图结构，均匀随机采样边。局部度（Local Degree，LE）[8] 在此基础上保留与每个节点的最高度邻居相连的边，从而保持局部连通性与枢纽结构；这一做法沿用了社区发现方法 [22]。TEDDY [23] 采取更有原则的方法：它根据节点度为边赋分，在一次处理中剪除高度节点之间的边，同时保留连接低度节点的边，因为后者往往是连接图中原本相距较远部分的关键结构链路。C. 压缩条件下的过平滑与传播过平滑是图学习中已有充分记录的现象：节点表示随深度增加而变得越来越相似，最终坍塌为几乎完全相同的向量 [15], [24]。Dirichlet 能量常被用于衡量这种效应，并且已经证明它会随深度呈指数衰减 [14], [15], [25]。近期工作质疑了能量型指标是否充分，因为性能下降可能早于明显的能量衰减，并提出了基于秩的替代指标 [26]。由于压缩会改变传播算子本身，过平滑与压缩并非相互独立。[14] 表明，删边和节点粗化会以相似方式改变图的特征值与 Dirichlet 能量。与本文设定更接近的是，[13] 表明，在粗化过程中，谱保持并不能保证粗化图上的消息传递与原图一致，并提出了一个具有显式消息传递保证的新传播矩阵。D. 本文的定位现有文献主要通过下游任务性能评价压缩，而过平滑文献则独立于压缩，研究传播如何使特征表示退化。本文把这两条研究线索连接起来，探究信号多样性保持与传播保真度是否是压缩条件下两个不同的目标，以及两类压缩方法是否处在这一权衡的互补两侧。三、问题设置与方法A. 概述我们研究不同图压缩范式如何改变信号传播动力学。具体而言，我们比较粗化与稀疏化这两种本质不同的压缩类别，并考察它们能否保留原图的传播行为。为此，我们使用三个互补指标，同时刻画信号的内在平滑程度以及相对于原始传播轨迹的保真度。B. 基线传播为了研究压缩如何改变信号传播，我们首先在未经压缩的原图上建立参照传播。该基线刻画节点特征如何在反复的邻域聚合下沿图结构扩散，并作为比较压缩图传播的真实参照。考虑图G=(V,E)G=(V,E)G=(V,E)，其中VVV表示包含NNN个节点的集合，EEE表示包含∣E∣|E|∣E∣条边的集合。按照 [12] 引入的带自环对称归一化邻接矩阵，定义基线传播算子：A~=D~−12(A+I)D~−12, \widetilde{A}=\widetilde{D}^{-\frac{1}{2}}(A+I)\widetilde{D}^{-\frac{1}{2}},A=D−21​(A+I)D−21​,其中，AAA是邻接矩阵，III是单位矩阵，D~\widetilde{D}D是A+IA+IA+I的度矩阵。给定初始节点特征矩阵X∈RN×dX\in\mathbb{R}^{N\times d}X∈RN×d，其中每个节点具有ddd维特征，则深度kkk处的传播信号为：Y(k)=A~kX.Y^{(k)}=\widetilde{A}^{k}X.Y(k)=AkX.请注意，我们不训练任何模型；这里使用A~\widetilde{A}A的唯一目的，是衡量信号在逐渐加深的图结构传播中如何演化。C. 图压缩图压缩试图在保留图G=(V,E)G=(V,E)G=(V,E)结构性质的同时减小其规模。我们比较两种根本不同的压缩范式：粗化与稀疏化。在两种情况下，我们都把压缩视为改变图拓扑的操作，并评估它对信号传播而非训练模型性能的影响。1. 图粗化图粗化把原始节点集合VVV划分成N′N'N′个互不相交的组，再将每组合并为一个超级节点，从而产生较小的图Gc=(Vc,Ec)G_c=(V_c,E_c)Gc​=(Vc​,Ec​)，其中∣Vc∣=N′N|V_c|=N'N∣Vc​∣=N′N。形式上，聚类分配矩阵C∈{ 0,1}N′×NC\in\{0,1\}^{N'\times N}