复杂系统导航：通过扩展窗口匹配实现无损图图缩减
内容提要
图压缩将大图压缩为小型合成图，以提升图神经网络训练效率。研究采用梯度匹配、分布匹配、特征基匹配等方法，在Reddit、Flickr等数据集上大幅缩小图规模并保持性能。最新提出的映射感知图压缩MCond支持归纳推理，在Reddit上实现121.5倍推理加速和55.9倍存储降低。
延伸解读
图压缩的动机与核心挑战
图神经网络处理大规模图时面临计算和存储瓶颈，图压缩通过生成小型合成图来提升训练效率。但传统方法受限于节点间拓扑结构，只能压缩观测到的训练节点及其结构，无法处理未见数据，导致推理阶段仍需原始大图进行信息传递，计算需求依然庞大。
MCond的归纳推理突破
针对上述局限，MCond提出映射感知的图压缩，学习原始节点到合成节点的一对多映射，使新节点能无缝整合到合成图中进行归纳表示学习。这样直接在合成图上传播信息比在原始大图上更高效。在Reddit数据集上，MCond实现了高达121.5倍的推理加速和55.9倍的存储降低。
不同压缩方法的性能对比
文章提及多种图压缩方法：梯度匹配在Reddit上达到95.3%的性能，Flickr上99.8%，Citeseer上99.0%，同时将图尺寸缩小99.9%以上；特征基匹配（GCEM）通过匹配特征基消除谱偏差，缩小不同GNN间的性能差距；CONVMATCH在摘要大小为原图1%时达到GNN节点分类性能的95%，链接预测任务上最多有2倍改进。
Q&A
图压缩是什么？它主要解决什么问题？
图压缩是将原始大图压缩成小型合成图的技术，旨在提高图神经网络训练的时间性能，同时保持模型性能。它通过优化梯度匹配损失和设计策略同时压缩节点特征和结构信息，将不同图数据集压缩成信息丰富的较小图，用于训练各种GNN体系结构。
图压缩在Reddit和Flickr数据集上的效果如何？
在Reddit上可达到95.3%的性能，在Flickr上可达到99.8%，在Citeseer上可达到99.0%，同时将图的尺寸缩小了99.9%以上。
MCond是什么？它有什么创新点？
MCond是映射感知的图压缩方法，它明确学习原始节点到合成节点的一对多映射，以无缝地将新节点整合到合成图中进行归纳表示学习。它采用交替优化方案，具有来自传统的和归纳的角度的创新损失项，促进了图压缩和节点映射学习之间的相互促进。
MCond在推理速度和存储需求上有什么优势？
在Reddit数据集上，与基于原始图的对照方法相比，MCond在推理速度上实现了高达121.5倍的加速和55.9倍的存储需求降低。
CONVMATCH算法是什么？它在节点分类和链接预测上的表现如何？
CONVMATCH是一种用于创建保持图卷积输出的图摘要的算法，具有高度可扩展的变种A-CONVMATCH。在节点分类上，当图的摘要大小为原图的1%时，CONVMATCH达到了GNN节点分类性能的95%；在链接预测任务上，CONVMATCH始终优于所有基准，达到了最多2倍的改进。
结构自由图压缩（SFGC）是什么？
SFGC是一种结构自由图压缩范式，将大规模图形压缩为小规模无图结构的节点集，并介绍了一种训练轨迹元匹配方案和图神经特征评分指标，检验了该方法的优越性。
