# Self-Supervised Learning for Sparse Matrix Reordering

arXiv: https://arxiv.org/abs/2605.17403 · HTML: https://mlsanity.com/paper/2605.17403/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 28 references that are in the map.
- First posted on arXiv 17 May 2026.

## Builds on (most cited first, 5 of 5)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2104.03546/) (2021)
- [Deep Learning and Spectral Embedding for Graph Partitioning](https://mlsanity.com/paper/2110.08614/) (2021)
- [Alpha Elimination: Using Deep Reinforcement Learning to Reduce Fill-In during Sparse Matrix Decomposition](https://mlsanity.com/paper/2310.09852/) (2023)
- [Towards Neural Sparse Linear Solvers](https://mlsanity.com/paper/2203.06944/) (2022)

## Abstract (arXiv)

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.