REVIEW 3 major objections 9 minor 15 references
Message-Passing GNNs Fail to Approximate Sparse Triangular Factorizations
T0 review · 3 major / 9 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read Message-passing GNNs cannot learn sparse triangular factorizations when the ideal factor depends non-locally on the matrix.
desk verdict A clean counterexample and a useful benchmark, but the experiments train on mismatched labels and the 'fundamental' claim outruns the proof. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the inverse of a bidiagonal matrix: when $L$ is bidiagonal, $L^{-1}$ has the rank-1 semiseparable form $L^{-1}_{i,j} = u_i v_j$ on the relevant triangle. The synthetic benchmark exploits this property in reverse: sample vectors $u$ and $v$, form the dense inverse with that structure, invert it to get a sparse bidiagonal $L$, and set $A = LL^{\top}$. This guarantees that the exact sparse factor encodes global information. For the real-world part, the paper computes K-optimal preconditioners by minimizing $K(L^{\top}A^{-1}L)$, which reduces to solving one small linear system per column of $L$; those factors, together with incomplete Cholesky factors, are the ground-truth targets.
What would settle it
Train a message-passing network with depth equal to the graph diameter on the tridiagonal counterexample from Theorem 2.1; if it reaches cosine similarity above 0.9 with the true Cholesky factor, the claimed fundamental barrier is overturned.
Extended reading notes
Core claim
The central claim is that sparse triangular factorization is non-local in a way message-passing GNNs cannot represent. Theorem 2.1 constructs a tridiagonal positive definite $A$ with a bidiagonal Cholesky factor $L$, and shows that adding a perturbation to a single entry of $A$ changes many entries of $L$ according to a recurrence; the change does not stay in a local neighborhood. A message-passing network with $k$ layers can only see information within $k$ hops of each edge, and the graphs considered here have diameter $O(N)$, so matching the map would require depth proportional to the matrix size, which the paper treats as infeasible. In experiments across GAT, generalized aggregation, message-passing layers, and graph transformers, cosine similarity between predicted and reference factors stays low, below 0.6 in key cases, and a global all-pair-attention transformer does not fix the problem. The paper concludes that the locality bias of message passing is fundamentally incompatible with non-local sparse preconditioners.
Load-bearing premise
The conclusion depends on treating networks deep enough to span the whole matrix as impractical; the paper does not prove an approximation lower bound, so a message-passing network with depth proportional to matrix size could in principle learn the map.
Editorial extensions
If this is right
- Claims that off-the-shelf message-passing GNNs can learn sparse factorized preconditioners must be restricted to problems with local dependence; the paper's experiments show systematic failure on the non-local benchmark.
- The new benchmark of synthetic tridiagonal and real-world matrix pairs gives future preconditioner-learning systems a concrete target: match K-optimal or incomplete-Cholesky factors with high cosine similarity.
- Architectures for ML-driven linear algebra need mechanisms for routing global information, but the graph-transformer results show that global attention by itself is insufficient.
- If the position holds, progress on learned preconditioners depends on designing non-local, structure-aware architectures rather than scaling existing message-passing models.
Reading between the lines
- The paper does not prove a formal approximation lower bound for message-passing networks; it assumes depth of order $N$ is not viable. Proving a concrete gap-based lower bound would make the 'fundamentally incapable' claim airtight.
- The Cholesky recurrence in the counterexample is sequential, so recurrent or unrolled architectures that iterate column-by-column could escape the barrier even though feed-forward message passing cannot.
- Non-local Green's-function-like dependencies should appear in other learned numerical tasks, such as domain-decomposition interface conditions or multigrid components, so the benchmark's lesson likely extends beyond factorizations.
- The K-optimal construction is limited to symmetric positive definite matrices and moderate sizes; broadening it to nonsymmetric or large sparse systems would let the benchmark test a wider range of architectures.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper argues that message-passing graph neural networks (GNNs) are fundamentally incapable of learning sparse triangular factorizations (Cholesky-type preconditioners) for matrix classes whose high-quality factors require non-local dependencies. The theoretical part proves Theorem 2.1, a sensitivity statement for bidiagonal Cholesky factors of tridiagonal symmetric positive definite matrices: perturbing a single entry of A changes the entire factor L by O(1) amounts at all diagonal positions. The paper then constructs 'K-optimal' preconditioners by explicitly minimizing the K-condition number functional K(L^T A^{-1} L) (Section 4, Algorithm 1), builds a benchmark from synthetic tridiagonal matrices with non-local factors and 150 SuiteSparse matrices (Section 5), and trains five types of models (MLP baseline, GAT, GEN, MessagePassingMLP, and two graph transformers) with at most 7 message-passing layers, reporting cosine similarity between predicted and reference factors (Section 6). The authors conclude that non-locality alone is not the bottleneck and that dedicated architectures are necessary, positioning the benchmark as a test for future architecture design.
Significance. If the central claim were established, the paper would be an important cautionary contribution to the growing literature on learned preconditioners, and its benchmark would be a useful community resource. The paper has genuine strengths: Theorem 2.1 is correct and self-contained, and it cleanly demonstrates that sparse Cholesky factors can have dense, non-decaying sensitivity to single input entries; the K-optimal construction in Section 4 is explicit, principled, and reusable beyond benchmarking; and the experimental section covers a reasonable spread of architectures. That said, the paper does not prove the headline claim. The gap between the sensitivity example and 'fundamental incapability' is filled by an informal infeasibility assertion about O(n) depth rather than an approximation lower bound, and the main synthetic experiment (Eq. (8)) supervises the network with chol(A_i) on inputs A_i + e1e1^T, a task that is not the factorization of the input. The mismatch between the strength of the claims and the evidence provided, together with the absence of error bars and released benchmark, currently limits the paper's impact.
major comments (3)
- [Section 2.1, Theorem 2.1] Theorem 2.1 proves a sensitivity property: the constructed matrices A and A' differ in one entry, yet their bidiagonal Cholesky factors differ at every diagonal position by O(1) for large n. Sensitivity of the target map does not by itself imply inapproximability by message-passing networks, and no approximation lower bound is stated or proved in the paper. The receptive-field argument in Section 2.1 is informal: it asserts that O(n) depth is infeasible and concludes 'fundamental incompatibility' (Section 7). Note also that the tridiagonal Cholesky recurrence l_{i,i-1} = a_{i,i-1}/l_{i-1,i-1} is sequential along the path graph, so a depth-O(n) message-passing network can represent the exact factor; the literal reading of 'fundamentally incapable' is therefore only valid for bounded depth. I recommend stating a formal lower bound, e.g., the two-point argument that any network whose receptive field at the far node does not include entry (1,1) must have error at least half the output distance on at least one of A or A', and relating that bound to the reported cosine-similarity metric, or alternatively reframing the central claim as a bounded-depth/practical limitation.
- [Section 6.3, Eq. (8)] The synthetic benchmark supervises the network with mismatched targets. Eq. (8) defines A^m_i = A_i + e1e1^T and L^m_i = chol(A_i); the target is the factor of the unperturbed matrix, not of the input. A model that perfectly implemented input factorization would output chol(A^m_i), which by Theorem 2.1 differs densely from chol(A_i), and would be scored poorly. The learned task is therefore 'recover the factor of a hidden matrix from a rank-1 perturbed observation', not 'approximate the sparse triangular factorization of the input'. Consequently, the low cosine similarities in Figure 2 do not support the statement in Section 7 that GNNs cannot recover Cholesky factors for tridiagonal matrices. The experiment should be rerun with targets chol(A^m_i), or the benchmark should be explicitly recast as a de-perturbation task with a justification of why that task tests the paper's claim.
- [Section 6.3, Figures 2-3] The empirical evidence does not support the blanket claim that message-passing GNNs fail. The paper reports that the MessagePassingMLP architecture (a message-passing model) 'produces satisfactory results with a number of rounds greater than one' on the synthetic benchmark, which contradicts the title and abstract's unqualified failure claim. In addition, no error bars, standard deviations, or multiple-seed results are reported, and the benchmark (generation details and the SuiteSparse matrix list) is not released, so the quantitative statements ('low cosine similarity (≤ 0.7 in key cases)', 'dropping below 0.6') are not reproducible. Please report mean and standard deviation over several seeds per architecture, release the benchmark and code, and report results per architecture rather than summarizing them as a single 'GNNs fail' conclusion.
minor comments (9)
- [Section 5.1] The construction of the synthetic benchmark samples vectors u and v to build L^{-1} as a rank-1 semiseparable matrix, but the sampling distributions, matrix sizes, and how non-locality is quantified are not specified; without these details the synthetic benchmark cannot be reproduced.
- [Section 5.2] The 150 SuiteSparse matrices are not identified, no train/test split is given, and no data or code repository link is provided; please release the list of matrix names and the prepared (A_i, L_i) pairs.
- [Section 6.1] The phrase 'medium-sized linear problems are of the size N = 108' is ambiguous (10^8 versus 108); please state the matrix sizes actually used, since the ratio of the 7-layer receptive field to the graph diameter is central to the depth-infeasibility argument.
- [Section 6.1] The conclusion that 'overcoming non-locality alone is insufficient' is based on the FastGraphTransformer, whose global attention uses node features only; without a controlled comparison against an edge-aware global model (e.g., the GraphTransformer with sufficient depth or edge-aware attention) the transformer failure may reflect feature misalignment or optimization difficulty rather than the absence of locality.
- [Section 6.2] The cosine-similarity loss was adopted because L2 training 'could not achieve convergence'; please report which L2 variants were tried and provide the cosine-similarity values with variance, and note explicitly that cosine similarity to a reference factor measures factor approximation, not preconditioner quality, so that the paper does not implicitly claim spectral quality from it.
- [Theorem 2.1 proof] There are small notation slips (e.g., 'Li,i−1 = 1, i = 2' should read 'i = 2, . . . , n', and the indexing A_{i+1,i} = 1/i versus L_{ii} = 1/i should be checked), and the claim that d_i converges to 1 as i → ∞ is asserted without proof; a short induction or fixed-point argument would make the proof self-contained.
- [Section 4, Algorithm 1] Algorithm 1 assumes the principal submatrices B_i of A^{-1} are nonsingular; please state how singular or ill-conditioned cases are handled and specify precisely the sparsity pattern used for the SuiteSparse experiments (e.g., zero fill-in pattern matching the lower triangle).
- [Section 7] The sentence 'This claim is supported by the fact that current GNN-based preconditioners often do not outperform their classical analogues in terms of their effect on the spectrum of A' makes an empirical assertion without any citation; please add supporting references or soften the statement.
- [Section 1 and elsewhere] There are several typos and grammatical slips, including 'precondtioner' (Section 1), 'biadiagonal' (Section 2, twice), 'a an example' (Section 2.1), and 'we randomly sampling' (Section 5.1); these should be corrected during revision.
Circularity Check
Synthetic benchmark's ground truth is defined as chol(A_i) for input A_i+e1e1^T, so low cosine similarity is forced by label definition rather than by any failure of factorization; K-optimal experiments remain independent.
-
self definitional
[Sections 5.1/6.3, Eq. (8); conclusion in Section 7]
"The modified training pairs (Am i , Lm i ) are obtained as follows: Am i = Ai + e1e⊤ 1 , Lm i = chol(Ai) . (8) where chol is a Cholesky factorization. ... We have demonstrated that GNNs cannot recover the Cholesky factors for tridiagonal matrices, for which perfect sparse preconditioners exist."
Eq. (8) labels the perturbed input A_i+e1e1^T with the Cholesky factor of the unperturbed A_i, not of the input itself. A model that correctly implements the factorization mapping A↦chol(A) would output chol(A_i+e1e1^T), which Theorem 2.1 shows is densely different from chol(A_i). The benchmark therefore guarantees low cosine similarity for any correct factorization learner, by construction. The Section 7 conclusion that GNNs cannot recover Cholesky factors for tridiagonal matrices follows from this label definition rather than from a test of factorization, which would require target chol(A^m_i).
full rationale
The K-optimal SuiteSparse benchmark is self-contained: each target L is the explicit minimizer of Kaporin's K-condition functional (Eq. 4/Algorithm 1) for the same A that is fed to the GNN, so those experiments are not circular and provide independent (if weaker) evidence that generic GNNs underperform classical preconditioner constructions. There is no load-bearing self-citation: references to Trifonov et al. 2024 and Li et al. 2023 are contextual and do not supply the paper's main premise. The one genuine circular step is the synthetic benchmark's label definition in Eq. (8), which makes the target chol(A_i) rather than chol(A_i+e1e1^T); failures on that task are artifacts of the definition. Separately, the leap from Theorem 2.1's sensitivity example to 'fundamentally incapable' is an unsupported generalization (no approximation lower bound is proved, and Section 2.1 only assumes depth O(N) is infeasible), but that is a logical gap, not circularity. Score 6 reflects partial circularity: the tridiagonal claim is forced by the benchmark definition, while the K-optimal experiments retain independent content.
Assumptions & free parameters
free parameters (1)
- maximum message-passing depth =
7 layers (GPU memory limited)
assumptions (5)
- domain assumption GNN receptive field equals the number of message-passing layers and grows only along graph edges.
- standard math The Cholesky factor of a tridiagonal symmetric positive definite matrix is bidiagonal.
- standard math The K-condition number functional can be minimized exactly as described in Algorithm 1, using the inverse matrix and the prescribed sparsity pattern.
- ad hoc to paper Cosine similarity between predicted and reference factors is a valid measure of preconditioner quality.
- domain assumption Message-passing depth proportional to graph diameter is computationally infeasible for large n.
Cite this review
Pith. "Pith review of Message-Passing GNNs Fail to Approximate Sparse Triangular Factorizations." pith.science (2026). https://pith.science/paper/2NMK5GGI
@misc{pith2026250201397,
author = {Pith},
title = {Pith review of: Message-Passing GNNs Fail to Approximate Sparse Triangular Factorizations},
year = {2026},
howpublished = {\url{https://pith.science/paper/2NMK5GGI}},
note = {Machine review of arXiv:2502.01397}
}
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.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[2]
P. Häusner, O. Öktem, and J. Sjölund. Neural incomplete factorization: Learning preconditioners for the conjugate gradient method. arXiv preprint arXiv:2305.16368,
-
[5]
J. D. Booth, H. Sun, and T. Garnett. Neural acceleration of incomplete Cholesky preconditioners. arXiv preprint arXiv:2403.00743,
-
[6]
J. Chen. Graph neural preconditioners for iterative solutions of sparse linear systems. arXiv preprint arXiv:2406.00809,
-
[7]
J. Luo, J. Wang, H. Wang, Z. Geng, H. Chen, Y . Kuang, et al. Neural Krylov iteration for accelerating linear system solving. In The Thirty-eighth Annual Conference on Neural Information Processing Systems. T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993,
-
[8]
Understanding over-squashing and bottlenecks on graphs via curvature
10 Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.14522,
-
[11]
P. W. Battaglia, J. B. Hamrick, V . Bapst, A. Sanchez-Gonzalez, V . Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261,
-
[13]
G. Li, C. Xiong, A. Thabet, and B. Ghanem. DeeperGCN: All you need to train deeper GCNs. arXiv preprint arXiv:2006.07739,
arXiv 2006
-
[14]
Y . Shi, Z. Huang, S. Feng, H. Zhong, W. Wang, and Y . Sun. Masked label prediction: Unified message passing model for semi-supervised classification. arXiv preprint arXiv:2009.03509,
arXiv 2009
Show all 15 references
-
[15]
K-optimal only: IC(0) preconditioner failed
11 A Appendix A.1 Algorithm for K-optimal preconditioners Algorithm 1 Construction of K-optimal preconditioner Require: Symmetric positive definite matrix A, sparsity pattern for L Ensure: Lower triangular matrix L Compute B = A−1 for i = 1 to n do Find indices si of non-zero ...
2019
-
[2017]
Veliˇckovi´c, G
P. Veliˇckovi´c, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y . Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903,
-
[2018]
Brody, U
S. Brody, U. Alon, and E. Yahav. How attentive are graph attention networks? arXiv preprint arXiv:2105.14491,
-
[2019]
Machine-learned precon- ditioners for linear solvers in geophysical fluid flows
Jan Ackmann, Peter D Düben, Tim N Palmer, and Piotr K Smolarkiewicz. Machine-learned precon- ditioners for linear solvers in geophysical fluid flows. arXiv preprint arXiv:2010.02866,
2010
-
[2021]
K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826,
-
[2023]
Deep learning of pre- conditioners for conjugate gradient solvers in urban water related problems
Johannes Sappl, Laurent Seiler, Matthias Harders, and Wolfgang Rauch. Deep learning of pre- conditioners for conjugate gradient solvers in urban water related problems. arXiv preprint arXiv:1906.06925,
1906 arXiv
-
[2024]
Trifonov, A
V . Trifonov, A. Rudikov, O. Iliev, I. Oseledets, and E. Muravleva. Learning from linear algebra: A graph neural network approach to preconditioner design for conjugate gradient solvers. arXiv preprint arXiv:2405.15557,
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.