消息传递GNN无法学习需要非局部依赖的稀疏三角分解。
Message-Passing GNNs Fail to Approximate Sparse Triangular Factorizations
- 用合成与真实矩阵验证，消息传递GNN难以捕捉非局部依赖关系。
- 预测因子与参考因子的余弦相似度≤0.7，效果差。
- 需定制化架构，仅放宽局部性不够，适合科学计算场景研究者。
图神经网络（GNN）被提出用于学习稀疏矩阵预条件器，这是加速线性求解器的关键组件。本文通过理论和实证证据表明，消息传递型GNN在某些矩阵类上根本无法近似稀疏三角分解，尽管这些矩阵存在高质量预条件器且依赖非局部结构。我们使用合成矩阵和SuiteSparse中的真实案例构建基线。在多种GNN架构（包括图注意力网络和图变换器）中，预测因子与参考因子的余弦相似度在关键情况下≤0.7。结果表明，将GNN应用于科学计算中的矩阵分解任务，必须突破消息传递架构。此外，实验显示，仅解决非局部性仍不足：即使完全非局部的全局图变压器也未能达到基准性能，说明需设计专用架构以捕获必要依赖关系。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) have been proposed as a tool for learning sparse matrix preconditioners, which are key components in accelerating linear solvers. We present theoretical and empirical evidence that message-passing GNNs are fundamentally incapable of approximating sparse triangular factorizations for classes of matrices for which high-quality preconditioners exist but require non-local dependencies. To illustrate this, we construct a set of baselines using both synthetic matrices and real-world examples from the SuiteSparse collection. Across a range of GNN architectures, including Graph Attention Networks and Graph Transformers, we observe low cosine similarity ($\leq0.7$ in key cases) between predicted and reference factors. Our theoretical and empirical results suggest that architectural innovations beyond message-passing are necessary for applying GNNs to scientific computing tasks such as matrix factorization. Moreover, experiments demonstrate that overcoming non-locality alone is insufficient. Tailored architectures are necessary to capture the required dependencies since even a completely non-local Global Graph Transformer fails to match the proposed baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。