





















Abstract: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.
| Comments: | Camera-ready version published in Transactions on Machine Learning Research |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Numerical Analysis (math.NA) |
| Cite as: | arXiv:2502.01397 [cs.LG] |
| (or arXiv:2502.01397v3 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2502.01397 arXiv-issued DOI via DataCite |
|
| Journal reference: | Transactions on Machine Learning Research, 2026 |
From: Vladislav Trifonov [view email]
[v1]
Mon, 3 Feb 2025 14:28:20 UTC (1,582 KB)
[v2]
Wed, 28 May 2025 07:53:55 UTC (1,574 KB)
[v3]
Mon, 25 May 2026 13:10:35 UTC (1,972 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。