Bridging the Gap between Sparse Matrix Reordering and Factorization: A Deep Learning Framework for Fill-in Reduction

• URL: http://arxiv.org/abs/2605.17339v1
• Date: Sun, 17 May 2026 09:15:42 GMT
• Title: Bridging the Gap between Sparse Matrix Reordering and Factorization: A Deep Learning Framework for Fill-in Reduction
• Abstract summary: Sparse matrix reordering can significantly reduce the fill-in during matrix factorization.<n>Finding a minimal fill-in ordering is known to be an NP-hard problem.<n>We propose a deep learning framework to minimize a fill-in surrogate function based on spectral embedding.
• Score: 8.282571271774573
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sparse matrix reordering can significantly reduce the fill-in during matrix factorization, thereby decreasing the computational and storage requirements in sparse matrix computations. Finding a minimal fill-in ordering is known to be an NP-hard problem. Moreover, there is a paradox: matrix reordering is applied before matrix factorization, but fill-ins that matrix reordering methods aim at are generated from matrix factorization. To bridge the gap between reordering and factorization, we propose a deep learning framework to minimize a fill-in surrogate function based on spectral embedding. First, we employ a multi-grid-like GNN architecture to learn to approximate the smallest eigenvectors of its graph Laplacian matrix, i.e. spectral embedding, and capture the global structural information of the matrix. Then, another multi-grid-like GNN architecture is used to minimize the potential space where fill-in can occur based on the rank distribution. Experimental results indicate that our approach achieves competitive performance compared with traditional graph-theoretic algorithms and deep learning methods.

Related papers

• Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure [4.961696679306355]
  We investigate when a nonnegative matrix can be recovered from a real-valued matrix of much lower rank by zeroing out its negative elements.<n>The potential for such decompositions suggests a mathematical connection between sparsity and rank.<n>We analyze a number of sparse matrices with this latent low-rank structure and use them to illustrate the origins of this connection.
  arXiv  Detail & Related papers  (2026-08-21T20:19:29Z)
• Self-Supervised Learning for Sparse Matrix Reordering [11.432320020523894]
  Rearranging rows or columns of a sparse matrix using an appropriate ordering can significantly reduce fill-ins.<n>Existing approaches, including graph-theoretic and deep learning methods, rely on surrogate objectives without theoretical guarantees.
  arXiv  Detail & Related papers  (2026-05-17T11:54:12Z)
• Factorization-in-Loop: Proximal Fill-in Minimization for Sparse Matrix Reordering [9.46982964997944]
  We learn a reordering network by minimizing triangular factors of the reordered matrix to approximate the exact number of fill-ins.<n>For gradient based optimization, there is a large gap between the predicted node scores and resultant triangular factors in the optimization objective.<n> Experimental results on benchmark sparse matrix collection SuiteSparse show the fill-in number and LU factorization time reduction of our proposed method is 20% and 17.8% compared with state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-11-12T08:06:33Z)
• Understanding Incremental Learning with Closed-form Solution to Gradient Flow on Overparamerterized Matrix Factorization [44.278609916888065]
  gradient flow learns a target matrix by sequentially learning its singular values in decreasing order of magnitude over time.<n>We show that incremental learning emerges from some time-scale separation among dynamics corresponding to learning different components in the target matrix.
  arXiv  Detail & Related papers  (2025-08-28T01:36:42Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Learning a Compressive Sensing Matrix with Structural Constraints via Maximum Mean Discrepancy Optimization [17.104994036477308]
  We introduce a learning-based algorithm to obtain a measurement matrix for compressive sensing related recovery problems. Recent success of such metrics in neural network related topics motivate a solution of the problem based on machine learning.
  arXiv  Detail & Related papers  (2021-10-14T08:35:54Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  Multi-view spectral clustering can effectively reveal the intrinsic cluster structure among data. This paper proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix. Our proposed algorithm generates the optimal Laplacian matrix by searching the neighborhood of the linear combination of both the first-order and high-order base.
  arXiv  Detail & Related papers  (2020-08-31T12:28:40Z)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  Robust low-rank matrix completion (RMC) has been studied extensively for computer vision, signal processing and machine learning applications. This problem aims to decompose a partially observed matrix into the superposition of a low-rank matrix and a sparse matrix, where the sparse matrix captures the grossly corrupted entries of the matrix. A widely used approach to tackle RMC is to consider a convex formulation, which minimizes the nuclear norm of the low-rank matrix (to promote low-rankness) and the l1 norm of the sparse matrix (to promote sparsity). In this paper, motivated by some recent works on low-
  arXiv  Detail & Related papers  (2020-08-18T04:46:22Z)
• Fast Rank Reduction for Non-negative Matrices via Mean Field Theory [5.634825161148483]
  We formulate rank reduction as a mean-field approximation by modeling matrices via a log-linear model on structured sample space. We empirically show that our rank reduction method is faster than NMF and its popular variant, lraNMF, while achieving competitive low rank approximation error on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2020-06-09T14:55:47Z)

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.