# Message-Passing GNNs Fail to Approximate Sparse Triangular Factorizations

arXiv: https://arxiv.org/abs/2502.01397 · HTML: https://mlsanity.com/paper/2502.01397/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 38 references that are in the map.
- First posted on arXiv 3 Feb 2025.

## Builds on (most cited first, 26 of 26)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [E(n) Equivariant Graph Neural Networks](https://mlsanity.com/paper/2102.09844/) (2021)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [DeeperGCN: All You Need to Train Deeper GCNs](https://mlsanity.com/paper/2006.07739/) (2020)
- [A Survey on Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2303.10993/) (2023)
- [SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations](https://mlsanity.com/paper/2306.10759/) (2023)
- [Learning Algebraic Multigrid Using Graph Neural Networks](https://mlsanity.com/paper/2003.05744/) (2020)
- [Deep Learning of Preconditioners for Conjugate Gradient Solvers in Urban Water Related Problems](https://mlsanity.com/paper/1906.06925/) (2019)
- [Neural incomplete factorization: learning preconditioners for the conjugate gradient method](https://mlsanity.com/paper/2305.16368/) (2023)
- [Learning from Linear Algebra: A Graph Neural Network Approach to Preconditioner Design for Conjugate Gradient Solvers](https://mlsanity.com/paper/2405.15557/) (2024)
- [Graph Neural Preconditioners for Iterative Solutions of Sparse Linear Systems](https://mlsanity.com/paper/2406.00809/) (2024)
- [MG-GNN: Multigrid Graph Neural Networks for Learning Multilevel Domain Decomposition Methods](https://mlsanity.com/paper/2301.11378/) (2023)
- [Machine-Learned Preconditioners for Linear Solvers in Geophysical Fluid Flows](https://mlsanity.com/paper/2010.02866/) (2020)
- [Learning Interface Conditions in Domain Decomposition Solvers](https://mlsanity.com/paper/2205.09833/) (2022)
- [Learning incomplete factorization preconditioners for GMRES](https://mlsanity.com/paper/2409.08262/) (2024)
- [Neural-network preconditioners for solving the Dirac equation in lattice gauge theory](https://mlsanity.com/paper/2208.02728/) (2022)
- [Graph Neural Networks and Applied Linear Algebra](https://mlsanity.com/paper/2310.14084/) (2023)
- [Generative modeling of Sparse Approximate Inverse Preconditioners](https://mlsanity.com/paper/2405.11007/) (2024)
- [Neural Acceleration of Incomplete Cholesky Preconditioners](https://mlsanity.com/paper/2403.00743/) (2024)

## Built on by (most cited first, 2 of 2)

- [Spectral Analysis of the Weighted Frobenius Objective](https://mlsanity.com/paper/2509.16783/) (2025)
- [RAPNet: Accelerating Algebraic Multigrid with Learned Sparse Corrections](https://mlsanity.com/paper/2605.26854/) (2026)

## Abstract (arXiv)

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 (≤0.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.