Message-Passing GNNs Fail to Approximate Sparse Triangular Factorizations

• URL: http://arxiv.org/abs/2502.01397v2
• Date: Wed, 28 May 2025 07:53:55 GMT
• Title: Message-Passing GNNs Fail to Approximate Sparse Triangular Factorizations
• Abstract summary: Graph Neural Networks (GNNs) have been proposed as a tool for learning sparse matrix preconditioners.<n>This paper argues that message-passing GNNs are incapable of approximating sparse triangular factorizations.
• Score: 3.868222899558346
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) have been proposed as a tool for learning sparse matrix preconditioners, which are key components in accelerating linear solvers. This position paper argues that message-passing GNNs are fundamentally incapable of approximating sparse triangular factorizations. We demonstrate that message-passing GNNs fundamentally fail to approximate 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 severe performance degradation compared to exact or K-optimal factorizations, with cosine similarity dropping below $0.6$ in key cases. 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. Experiments demonstrate that overcoming non-locality alone is insufficient. Tailored architectures are necessary to capture the required dependencies since even a completely non-local Graph Transformer fails to match the proposed baselines.

Related papers

• On the Potential of Graph Neural Networks as Metamodels for Supply Chain Optimization: Dataset, Architectures, and Directions [0.0]
  Graph Neural Networks (GNNs) have emerged as a powerful, differentiable class of learning models forstructured systems.<n>This paper lays the foundation, presents initial steps, and discusses key research directions.
  arXiv  Detail & Related papers  (2026-07-18T11:06:22Z)
• Plain Transformers are Surprisingly Powerful Link Predictors [57.01966734467712]
  Link prediction is a core challenge in graph machine learning, demanding models that capture rich and complex topological dependencies.<n>While Graph Neural Networks (GNNs) are the standard solution, state-of-the-art pipelines often rely on explicit structurals or memory-intensive node embeddings.<n>We present PENCIL, an encoder-only plain Transformer that replaces hand-crafted priors with attention over sampled local subgraphs.
  arXiv  Detail & Related papers  (2026-02-02T02:45:52Z)
• Learning Sparse Approximate Inverse Preconditioners for Conjugate Gradient Solvers on GPUs [25.22023084590467]
  Concomitant gradient solver (CG) is a prevalent method for solving symmetric and positive definite linear systems Ax=b.<n>Existing learning-based methods often utilize Graph Neural Networks (GNNs) to improve the performance and speed up the construction.<n>We propose a learning-based method to generate GPU-friendly preconditioners, particularly using GNNs to construct Sparse Approximate Inverse (SPAI) preconditioners.
  arXiv  Detail & Related papers  (2025-10-31T14:42:48Z)
• Non-Euclidean Hierarchical Representational Learning using Hyperbolic Graph Neural Networks for Environmental Claim Detection [1.3673890873313355]
  Transformer-based models dominate NLP tasks like sentiment analysis, machine translation, and claim verification.<n>In this work, we explore Graph Neural Networks (GNNs) and Hyperbolic Graph Neural Networks (HGNNs) as lightweight yet effective alternatives for Environmental Claim Detection.
  arXiv  Detail & Related papers  (2025-02-19T11:04:59Z)
• LASE: Learned Adjacency Spectral Embeddings [7.612218105739107]
  We learn nodal Adjacency Spectral Embeddings (ASE) from graph inputs.<n>LASE is interpretable, parameter efficient, robust to inputs with unobserved edges.<n>LASE layers combine Graph Convolutional Network (GCN) and fully-connected Graph Attention Network (GAT) modules.
  arXiv  Detail & Related papers  (2024-12-23T17:35:19Z)
• Learning incomplete factorization preconditioners for GMRES [1.1519724914285523]
  We train a graph neural network to approximate the matrix factorization directly. Applying a graph neural network architecture allows us to ensure that the output itself is sparse. We show their effectiveness in decreasing the number of GMRES iterations and improving the spectral properties on synthetic data.
  arXiv  Detail & Related papers  (2024-09-12T17:55:44Z)
• Weight Conditioning for Smooth Optimization of Neural Networks [28.243353447978837]
  We introduce a novel normalization technique for neural network weight matrices, which we term weight conditioning. This approach aims to narrow the gap between the smallest and largest singular values of the weight matrices, resulting in better-conditioned matrices. Our findings indicate that our normalization method is not only competitive but also outperforms existing weight normalization techniques from the literature.
  arXiv  Detail & Related papers  (2024-09-05T11:10:34Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• Learning from Linear Algebra: A Graph Neural Network Approach to Preconditioner Design for Conjugate Gradient Solvers [40.6591136324878]
  We train GNNs to obtain preconditioners that reduce the condition number of the system more significantly than classical preconditioners.<n>Our approach outperforms both classical and neural network-based methods for an important class of parametric partial differential equations.
  arXiv  Detail & Related papers  (2024-05-24T13:44:30Z)
• Matrix Completion via Nonsmooth Regularization of Fully Connected Neural Networks [7.349727826230864]
  It has been shown that enhanced performance could be attained by using nonlinear estimators such as deep neural networks. In this paper, we control over-fitting by regularizing FCNN model in terms of norm intermediate representations. Our simulations indicate the superiority of the proposed algorithm in comparison with existing linear and nonlinear algorithms.
  arXiv  Detail & Related papers  (2024-03-15T12:00:37Z)
• Interpretable A-posteriori Error Indication for Graph Neural Network Surrogate Models [0.0]
  This work introduces an interpretability enhancement procedure for graph neural networks (GNNs) The end result is an interpretable GNN model that isolates regions in physical space, corresponding to sub-graphs, that are intrinsically linked to the forecasting task. The interpretable GNNs can also be used to identify, during inference, graph nodes that correspond to a majority of the anticipated forecasting error.
  arXiv  Detail & Related papers  (2023-11-13T18:37:07Z)
• Probabilistically Rewired Message-Passing Neural Networks [41.554499944141654]
  Message-passing graph neural networks (MPNNs) emerged as powerful tools for processing graph-structured input. MPNNs operate on a fixed input graph structure, ignoring potential noise and missing information. We devise probabilistically rewired MPNNs (PR-MPNNs) which learn to add relevant edges while omitting less beneficial ones.
  arXiv  Detail & Related papers  (2023-10-03T15:43:59Z)
• Implicit Graph Neural Diffusion Networks: Convergence, Generalization, and Over-Smoothing [7.984586585987328]
  Implicit Graph Neural Networks (GNNs) have achieved significant success in addressing graph learning problems. We introduce a geometric framework for designing implicit graph diffusion layers based on a parameterized graph Laplacian operator. We show how implicit GNN layers can be viewed as the fixed-point equation of a Dirichlet energy minimization problem.
  arXiv  Detail & Related papers  (2023-08-07T05:22:33Z)
• Contextualizing MLP-Mixers Spatiotemporally for Urban Data Forecast at Scale [54.15522908057831]
  We propose an adapted version of the computationally-Mixer for STTD forecast at scale. Our results surprisingly show that this simple-yeteffective solution can rival SOTA baselines when tested on several traffic benchmarks. Our findings contribute to the exploration of simple-yet-effective models for real-world STTD forecasting.
  arXiv  Detail & Related papers  (2023-07-04T05:19:19Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Connectivity Optimized Nested Graph Networks for Crystal Structures [1.1470070927586016]
  Graph neural networks (GNNs) have been applied to a large variety of applications in materials science and chemistry. We show that our suggested models systematically improve state-of-the-art results across all tasks within the MatBench benchmark.
  arXiv  Detail & Related papers  (2023-02-27T19:26:48Z)
• GNN at the Edge: Cost-Efficient Graph Neural Network Processing over Distributed Edge Servers [24.109721494781592]
  Graph Neural Networks (GNNs) are still under exploration, presenting a stark disparity to its broad edge adoptions. This paper studies the cost optimization for distributed GNN processing over a multi-tier heterogeneous edge network. We show that our approach achieves superior performance over de facto baselines with more than 95.8% cost eduction in a fast convergence speed.
  arXiv  Detail & Related papers  (2022-10-31T13:03:16Z)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  We propose a simple yet efficient framework to make the homogeneous GNNs have adequate ability to handle heterogeneous graphs. Specifically, we propose Relation Embedding based Graph Neural Networks (RE-GNNs), which employ only one parameter per relation to embed the importance of edge type relations and self-loop connections.
  arXiv  Detail & Related papers  (2022-09-23T05:24:18Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• Orthogonal Graph Neural Networks [53.466187667936026]
  Graph neural networks (GNNs) have received tremendous attention due to their superiority in learning node representations. stacking more convolutional layers significantly decreases the performance of GNNs. We propose a novel Ortho-GConv, which could generally augment the existing GNN backbones to stabilize the model training and improve the model's generalization performance.
  arXiv  Detail & Related papers  (2021-09-23T12:39:01Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  We study tradeoffs of computational cost and expressive power of Graph Neural Networks (GNNs) We show that a new model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. In several cases, the proposed algorithm can greatly reduce computational complexity compared to the existing higher-order $k$-GNNs.
  arXiv  Detail & Related papers  (2020-12-06T03:42:54Z)
• Nonlinear State-Space Generalizations of Graph Convolutional Neural Networks [172.18295279061607]
  Graph convolutional neural networks (GCNNs) learn compositional representations from network data by nesting linear graph convolutions into nonlinearities. In this work, we approach GCNNs from a state-space perspective revealing that the graph convolutional module is a minimalistic linear state-space model. We show that this state update may be problematic because it is nonparametric, and depending on the graph spectrum it may explode or vanish. We propose a novel family of nodal aggregation rules that aggregate node features within a layer in a nonlinear state-space parametric fashion allowing for a better trade-off.
  arXiv  Detail & Related papers  (2020-10-27T19:48:56Z)
• Improving predictions of Bayesian neural nets via local linearization [79.21517734364093]
  We argue that the Gauss-Newton approximation should be understood as a local linearization of the underlying Bayesian neural network (BNN) Because we use this linearized model for posterior inference, we should also predict using this modified model instead of the original one. We refer to this modified predictive as "GLM predictive" and show that it effectively resolves common underfitting problems of the Laplace approximation.
  arXiv  Detail & Related papers  (2020-08-19T12:35:55Z)
• Learning Reasoning Strategies in End-to-End Differentiable Proving [50.9791149533921]
  Conditional Theorem Provers learn optimal rule selection strategy via gradient-based optimisation. We show that Conditional Theorem Provers are scalable and yield state-of-the-art results on the CLUTRR dataset.
  arXiv  Detail & Related papers  (2020-07-13T16:22:14Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  Graph neural networks (GNNs) have made great progress recently on learning from graph-structured data in practice. We provide a theoretically-grounded generalizability analysis of GNNs with one hidden layer for both regression and binary classification problems.
  arXiv  Detail & Related papers  (2020-06-25T00:45:52Z)
• Binarized Graph Neural Network [65.20589262811677]
  We develop a binarized graph neural network to learn the binary representations of the nodes with binary network parameters. Our proposed method can be seamlessly integrated into the existing GNN-based embedding approaches. Experiments indicate that the proposed binarized graph neural network, namely BGN, is orders of magnitude more efficient in terms of both time and space.
  arXiv  Detail & Related papers  (2020-04-19T09:43:14Z)
• Node Masking: Making Graph Neural Networks Generalize and Scale Better [71.51292866945471]
  Graph Neural Networks (GNNs) have received a lot of interest in the recent times. In this paper, we utilize some theoretical tools to better visualize the operations performed by state of the art spatial GNNs. We introduce a simple concept, Node Masking, that allows them to generalize and scale better.
  arXiv  Detail & Related papers  (2020-01-17T06:26:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.