Graph Neural Preconditioners for Iterative Solutions of Sparse Linear Systems

Authors: Jie Chen
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: General-purpose preconditioner, linear systems, graph neural networks

Abstract:
Preconditioning is at the heart of iterative solutions of large, sparse linear systems of equations in scientific disciplines. Several algebraic approaches, which access no information beyond the matrix itself, are widely studied and used, but ill-conditioned matrices remain very challenging. We take a machine learning approach and propose using graph neural networks as a general-purpose preconditioner. They show attractive performance for many problems and can be used when the mainstream preconditioners perform poorly. Empirical evaluation on over 800 matrices suggests that the construction time of these graph neural preconditioners (GNPs) is more predictable and can be much shorter than that of other widely used ones, such as ILU and AMG, while the execution time is faster than using a Krylov method as the preconditioner, such as in inner-outer GMRES. GNPs have a strong potential for solving large-scale, challenging algebraic problems arising from not only partial differential equations, but also economics, statistics, graph, and optimization, to name a few.

Decision: accept (poster)
Reviewer scores: 6, 3, 6, 6

Reviews and discussion:
<thread>
creation date:
1730010884557

thread_type:
official_review

<thread_object>
creator: reviewer_4sht

<content>
summary:
The authors focus on the task of preconditioning linear systems which remains one of the most important problems in scientific computing and applied maths. The authors use a machine learning approach and propose using graph neural networks as a general-purpose preconditioner.

strengths:
- Preconditioning is a relevant problem and discovering new preconditioners for novel applications is resource-demanding
- The paper tackles a large number of test matrices and compares with SOTA black box preconditioners

weaknesses:
- The authors state their result as probably novel. Have they not found anything similar in the literature? I would like them to discuss the difference to the work USING FGMRES TO OBTAIN BACKWARD STABILITY IN MIXED PRECISION by Arioli and Duff, which they have done in the revised version.
- I am not a fan of presenting the results as best performer but it could be that the other methods are really close and this method only outperforms slightly and is terrible for the other problems. I would like to see actual  numbers or convergence plots.

questions:
- For the training data generation at the beginning of 2.2, is this really meaningful? You cannot sample the whole of $\mathbb{R}^n$ to run the problem forwards as also given possible ill-conditioning of $A$ approximating the inverse is difficult. Is this the reason the authors then switch to Arnoldi? This is the basis for many Krylov solvers and it is not clear what the advantage of the machine learning approach his if we have to do Arnoldi anyways?
- How about the sharpness of the Gershgorin estimates? These are not necessarily sharp.
- Do the authors really observe convergence of GMRES in 10 iterations to $10^{-6}$?
- AMG works better for symmetric problems, for nonsymmetric matrices PyAMG comes with better approaches for nonsymmetric problems such as the AIR approach.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730294002907

thread_type:
official_review

<thread_object>
creator: reviewer_hjdk

<content>
summary:
This paper proposes a GNN-based approach to preconditioning Krylov solvers, offering a novel alternative to traditional algebraic preconditioners. Unlike conventional methods, the GNN-based preconditioner (GNP) approximates the matrix inverse without relying on additional information, making it adaptable and robust across a wide range of matrices. GNP demonstrates predictable training costs, good robustness, and, in some cases, faster convergence than traditional preconditioners like ILU and AMG, which are often hampered by unpredictable construction times and structural limitations.
The contributions:
1. Convergence analysis for FGMRES, a widely used but theoretically underexplored method.  
2. New approach to training the neural preconditioner, focusing on effective training data generation by sampling from the bottom eigensubspace of  A to enhance training performance. 
3. Scale-equivariant GNN to serve as the preconditioner, addressing the challenge of varying input scales in the training data by enforcing an inductive bias that maintains scale-equivariance. 
4. Novel evaluation protocol to test the preconditioner broadly, evaluating across over 800 matrices from 50 diverse application areas in the SuiteSparse collection.

strengths:
1. Introduces a GNN-based preconditioner (GNP) as a novel, general-purpose alternative to traditional methods, approximating the matrix inverse without additional problem-specific information.
2. Offers stable and consistent training times, unlike traditional preconditioners with unpredictable construction times due to matrix irregularities.
3. Contributes a convergence analysis for FGMRES.
4. Tests GNP on over 800 matrices from 50 application areas.

weaknesses:
Sometimes both Iter-AUC and Time-AUC do not give good "weight" for the final residual accuracy. A method that reaches a lower final residual can be underrepresented if it converges more gradually, while a method with fast early convergence but a higher final residual might appear more favorable.

questions:
1. Since neither Iter-AUC nor Time-AUC specifically prioritizes the final residual accuracy, have you considered including a metric that directly measures the final residual? For applications where achieving a specific residual threshold is crucial, this could provide a more balanced evaluation. If not, what are your thoughts on this?
2. Iter-AUC and Time-AUC capture different aspects of convergence (iteration efficiency and time efficiency, respectively). In cases where these metrics might conflict (e.g., one method scores well on Iter-AUC but poorly on Time-AUC), how would you recommend interpreting the results?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730647830382

thread_type:
official_review

<thread_object>
creator: reviewer_7hsm

<content>
summary:
The paper proposes a novel approach using Graph Neural Networks (GNNs) as general-purpose preconditioners for solving large, sparse linear systems. The authors present an empirical evaluation of their method, showing that it outperforms traditional preconditioning techniques like ILU and AMG in terms of construction time and execution efficiency, especially for ill-conditioned matrices. The method is tested on a diverse set of over 800 matrices, suggesting significant advantages in robustness and performance compared to existing methods.

strengths:
- **Innovative Approach:** The use of GNNs as preconditioners is a fresh perspective that leverages recent advancements in machine learning.

- **Empirical Validation:** The extensive evaluation on a wide range of matrices provides strong evidence of the proposed method's effectiveness across various problem domains.

- **Robustness:** The proposed method demonstrates high robustness with a low failure rate compared to traditional preconditioners, particularly in handling ill-conditioned problems.

- **Theoretical Contributions:** The paper includes a convergence analysis for the flexible GMRES method, which adds valuable theoretical insights to the practical implementation.

weaknesses:
- **Scalability Concerns:** While the paper mentions robustness, it lacks detailed discussions on scalability, particularly regarding the performance of GNNs with significantly larger matrices.

- **Dependence on Training Data:** The effectiveness of the GNN-based preconditioner seems to heavily rely on the quality and diversity of the training data. The paper does not explore the implications of this dependence thoroughly.

- **Limited Theoretical Foundation:** Although the empirical results are compelling, the theoretical grounding could be strengthened, especially concerning the convergence properties of the proposed methods under varied conditions.

questions:
1. How does the proposed preconditioner handle matrices outside the tested conditions, particularly in real-world applications?

2. Could you elaborate on the training data generation process? How might biases in the training set affect the performance of the GNN?

3. What are the implications of your findings for future research in preconditioning techniques, especially concerning adapting the GNN for a wider array of problems?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730685018611

thread_type:
official_review

<thread_object>
creator: reviewer_vmvp

<content>
summary:
Authors propose use Graph Neural Network (GNN) as a general-purpose preconditioner. They offer a convergence analysis for flexible GMRES. A new effective training data generation is proposed to training GNN. They develop a scale-equivariant GNN as the preconditioner. A novel evaluation protocol proposed by authors is being for general-purpose preconditioners.

strengths:
* Authors pay their attention to the problem which is linked to using neural networks (in particular, GNN) as the preconditioner. In this sense, the preconditioner is a nonlinear operator and, using a standard preconditioned solver with this preconditioner is not correct. In this case, the convergence theory is broken. They concentrate on flexible GMRES and present an original convergence analysis. 
* Authors propose original scheme of data generation. Suggested sampling is linked with eigen-subspace of the $\mathbf{A}$.
* Of course, the idea of using GNN as the preconditioner is not novel. Authors offer a fresh approach to normalize $\mathbf{A}$. This prevents the potential division-by-zero issue that can arise in the standard normalization of GCN. The major innovation of the architecture is its scale-equivariance, i.e. the input space of the neural network is restricted.
* Proposed architecture is checked on the SuiteSparse matrix collection https://sparse.tamu.edu (square, real-valued 867 matrices (not spd-matrices) from 50 application areas, whose count of non-zero elements is less than 2M. To compare with classical methods such as ILU, AMG, and GMRES author propose two novel metrics.

weaknesses:
* Authors use $\ell_1$ residual norm as the training loss. Is it possible to use $\ell_2$ norm or others as the training loss?
* Authors compare their architecture with classical methods(GNP, ILU, AMG, Jacobi, and GMREs). It will be good to compare their approach and metrics with the existing general-purpose preconditioners which are used GNN as the preconditioner. See for example, https://proceedings.mlr.press/v202/li23e/li23e.pdf, https://arxiv.org/pdf/2405.15557.
* Are there exist some constraints to use this approach for SPD-matrices?
* Why is not the full GitHub repository made available for review?
* Why do the authors only assume the ground truth solution $\mathbf{x} = 1$?

questions:
See weaknesses.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This work proposes using graph neural networks (GNNs) as general-purpose preconditioners for solving large, sparse linear systems, particularly for challenging ill-conditioned matrices. Empirical evaluation on 800+ matrices shows that GNN-based preconditioners offer faster and more predictable construction times compared to traditional methods like ILU and AMG, with faster execution times than Krylov-based preconditioners. The approach has strong potential for large-scale problems in various fields, including PDEs, economics, and optimization.

Three reviewers recommended acceptance, emphasizing the substantial contributions of the paper. They highlighted the soundness and novelty of the proposed preconditioning technique, noting its fresh perspective. Another reviewer praised the thoroughness of the experiments, which evaluate performance across 800 matrices from 50 application areas, effectively showcasing the method's capabilities.
However, one reviewer recommended rejection, citing concerns about scalability, reliance on training data, and a limited theoretical foundation.

The AC sides with the majority vote, acknowledging that the paper's strengths significantly outweigh its weaknesses.