arXiv:2506.11743cs.LGstat.ML2025-06NeurIPS被引 4

提出更通用的图粗化缩减矩阵分类,可降低信息损失并提升图神经网络性能。

Taxonomy of reduction matrices for Graph Coarsening

  • 打破缩减与提升矩阵互为伪逆的限制,构建更灵活的缩减矩阵分类体系。
  • 相同粗化下,调整缩减矩阵可进一步降低谱近似误差(RSA)。
  • 适用于图神经网络节点分类任务,尤其在保持精度前提下压缩图规模。

图粗化旨在减小图的规模以降低内存开销,在图信号处理和机器学习中应用广泛。通常通过缩减矩阵与提升矩阵定义,分别实现信号从原图到粗化图的投影及逆过程,由此产生的信息损失由受限谱近似(RSA)度量。现有框架通常强制缩减矩阵与提升矩阵互为伪逆,目标是最小化RSA。本文指出二者角色并不对称:仅对提升矩阵施加约束即可保证粗化图邻接矩阵或拉普拉斯矩阵的存在性。因此,我们引入更一般的缩减矩阵概念,不再要求其为提升矩阵的伪逆。建立了一套“可接受”缩减矩阵家族的分类体系,讨论其需满足的性质,以及是否具有闭式表达。我们证明,对于固定提升矩阵所对应的粗化,仅通过调整缩减矩阵即可进一步降低RSA。通过多种示例验证,包括基于RSA约束优化的构造方法。由于该指标与图神经网络性能相关,我们还在多个节点分类任务上展示了不同选择对粗化图性能的影响。

原文摘要 · Abstract (English)

Graph coarsening aims to diminish the size of a graph to lighten its memory footprint, and has numerous applications in graph signal processing and machine learning. It is usually defined using a reduction matrix and a lifting matrix, which, respectively, allows to project a graph signal from the original graph to the coarsened one and back. This results in a loss of information measured by the so-called Restricted Spectral Approximation (RSA). Most coarsening frameworks impose a fixed relationship between the reduction and lifting matrices, generally as pseudo-inverses of each other, and seek to define a coarsening that minimizes the RSA. In this paper, we remark that the roles of these two matrices are not entirely symmetric: indeed, putting constraints on the lifting matrix alone ensures the existence of important objects such as the coarsened graph's adjacency matrix or Laplacian. In light of this, in this paper, we introduce a more general notion of reduction matrix, that is not necessarily the pseudo-inverse of the lifting matrix. We establish a taxonomy of ``admissible'' families of reduction matrices, discuss the different properties that they must satisfy and whether they admit a closed-form description or not. We show that, for a fixed coarsening represented by a fixed lifting matrix, the RSA can be further reduced simply by modifying the reduction matrix. We explore different examples, including some based on a constrained optimization process of the RSA. Since this criterion has also been linked to the performance of Graph Neural Networks, we also illustrate the impact of this choices on different node classification tasks on coarsened graphs.

图粗化谱近似图神经网络

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。