Graph Sparsification via Mixture of Graphs

图神经网络（GNN）在各种图学习任务中表现出卓越的性能，但在应用于大规模图时面临着重大的计算挑战。缓解这些挑战的一种有效方法是图稀疏化，即通过去除非必要的边来减少计算开销。然而，以往的图稀疏化方法通常依赖于单一的全局稀疏设置和统一的修剪标准，未能为每个节点的复杂局部上下文提供定制的稀疏化方案。在本文中，我们介绍了Mixture-of-Graphs（MoG），利用Mixture-of-Experts（MoE）的概念，为每个节点动态选择量身定制的修剪方案。具体而言，MoG包含多个稀疏化专家，每个专家都具有独特的稀疏水平和修剪标准，并为每个节点选择适当的专家。随后，MoG在Grassmann流形上对不同专家产生的稀疏图进行混合，以得出最优稀疏图。MoG的一个显著特点是其完全本地化，因为它取决于每个单独节点的特定情况。在四个大规模OGB数据集和两个超像素数据集上进行的大量实验，配备五个GNN骨干网络，证明了MoG（I）以高于$8.67\%\sim 50.85\%$的稀疏水平识别子图，性能等同于或优于密集图，（II）实现了$1.47-2.62\times$的GNN推理加速，性能下降可忽略不计，（III）提升了“顶尖学生”GNN的性能（在RevGNN+\textsc{ogbn-proteins}上$1.02\%\uparrow$，在DeeperGCN+\textsc{ogbg-ppa}上$1.74\%\uparrow$）。

本论文尝试解决在大规模图数据上应用GNN时所面临的计算挑战，提出图稀疏化的方法以减少计算开销。同时，该论文还试图为每个节点提供定制化的稀疏化方案，以更好地适应局部复杂环境。

论文提出了一种名为Mixture-of-Graphs（MoG）的方法，借鉴了Mixture-of-Experts（MoE）的概念，为每个节点动态选择定制化的稀疏化方案。MoG包括多个稀疏化专家，每个专家都具有独特的稀疏度和修剪标准，并为每个节点选择适当的专家。随后，MoG在Grassmann流形上混合不同专家产生的稀疏图，以得出最优稀疏图。

本论文的亮点包括：（1）MoG能够识别高稀疏度（8.67%~50.85%）的子图，且性能等同于或优于密集图；（2）MoG在GNN推理中实现了1.47-2.62倍的加速，性能下降可以忽略不计；（3）MoG提高了“顶尖学生”GNN的性能，如在RevGNN+ extsc{ogbn-proteins}上提高了1.02%、在DeeperGCN+ extsc{ogbg-ppa}上提高了1.74%。

最近在这个领域中，还有一些相关研究，如《GraphSAINT: Graph Sampling Based Inductive Learning Method》和《Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks》。