Self-Supervised Learning for Sparse Matrix Reordering

• URL: http://arxiv.org/abs/2605.17403v1
• Date: Sun, 17 May 2026 11:54:12 GMT
• Title: Self-Supervised Learning for Sparse Matrix Reordering
• Abstract summary: 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.
• Score: 11.432320020523894
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Rearranging the rows or columns of a sparse matrix using an appropriate ordering can significantly reduce fill-ins, i.e., new nonzeros introduced during matrix factorization, decreasing memory usage and runtime. However, finding an ordering that minimizes fill-ins is NP-complete. Existing approaches, including graph-theoretic and deep learning methods, rely on surrogate objectives without theoretical guarantees. The Fill-Path Theorem reveals a direct and intrinsic relationship between fill-in generation and the sparse structure of the matrix as path triplet inequalities. Here we first employ a multigrid graph network to capture structural information for each vertex. We then derive a triplet sampling strategy based on inequalities. Finally, we introduce an end-max chain loss function to reduce the number of triplets whose predicted scores satisfy these inequalities. Experimental evaluations on the publicly available SuiteSparse matrix collection demonstrate the superiority of the proposed method in terms of both fill-in reduction and speedup in LU factorization time.

Related papers

• Bridging the Gap between Sparse Matrix Reordering and Factorization: A Deep Learning Framework for Fill-in Reduction [8.282571271774573]
  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.
  arXiv  Detail & Related papers  (2026-05-17T09:15:42Z)
• 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)
• Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares [0.8702432681310401]
  We propose a new algorithm for recovering data that adheres to multiple, heterogeneous low-dimensional structures from linear observations. We show that the IRLS method favorable in identifying low/comckuele state measurements.
  arXiv  Detail & Related papers  (2023-06-08T06:35:47Z)
• Disjunctive Branch-And-Bound for Certifiably Optimal Low-Rank Matrix Completion [6.537257913467247]
  We present a novel and often near-exact class of convex relaxations by decomposing a low-rank matrix as a sum of two minors.<n>In numerical experiments, our new convex relaxations decrease the optimality or near optimality in for $max m, n q$ and $r leq$.
  arXiv  Detail & Related papers  (2023-05-20T22:04:34Z)
• 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)
• Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences [52.6022911513076]
  Transformer-based models are not efficient in processing long sequences due to the quadratic space and time complexity of the self-attention modules. We propose Linformer and Informer to reduce the quadratic complexity to linear (modulo logarithmic factors) via low-dimensional projection and row selection. Based on the theoretical analysis, we propose Skeinformer to accelerate self-attention and further improve the accuracy of matrix approximation to self-attention.
  arXiv  Detail & Related papers  (2021-12-10T06:58:05Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• 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)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  We propose a new non scalable low-rank regularizer called "nuclear Frobenius norm" regularizer, which is adaptive and sound. It bypasses the computation of singular values and allows fast optimization by algorithms. It obtains state-of-the-art recovery performance while being the fastest in existing matrix learning methods.
  arXiv  Detail & Related papers  (2020-08-14T18:47:58Z)
• 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.