pith. sign in

arxiv: 2605.17339 · v1 · pith:QSZMITHInew · submitted 2026-05-17 · 💻 cs.LG

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

Ziwei Li , Tao Yuan , Shuzi Niu , Huiyuan Li This is my paper

Pith reviewed 2026-05-20 14:43 UTC · model grok-4.3

classification 💻 cs.LG
keywords sparse matrix reorderingfill-in reductiongraph neural networksspectral embeddingmatrix factorizationdeep learning frameworkmulti-grid GNN
0
0 comments X

The pith

A graph neural network learns to reorder sparse matrices by approximating Laplacian eigenvectors and minimizing a fill-in surrogate based on rank distribution.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out to close the separation between choosing a matrix reordering and seeing the fill-in that actually appears during factorization. It trains two multi-grid-style graph neural networks: the first approximates the smallest eigenvectors of the graph Laplacian to embed the matrix structure, and the second uses that embedding to shrink the region where fill-in can occur according to rank distribution. A sympathetic reader would care because better reorderings directly cut the extra nonzeros created in sparse factorization, which lowers both memory use and arithmetic cost in scientific computing. The framework therefore learns reorderings from matrix structure alone rather than requiring repeated factorization runs during training.

Core claim

The central claim is that a multi-grid-like GNN can first learn to approximate the smallest eigenvectors of the graph Laplacian of a sparse matrix, thereby producing a spectral embedding that captures global structure, and a second such GNN can then minimize a surrogate measure of fill-in potential derived from rank distribution, yielding permutation orderings that reduce fill-in during subsequent factorization.

What carries the argument

A pair of multi-grid-like GNN architectures that first approximate the smallest eigenvectors of the graph Laplacian for spectral embedding and then minimize a rank-distribution-based surrogate for the space where fill-in can occur.

If this is right

  • Reorderings can be generated without running the target factorization during the learning process itself.
  • The resulting permutations achieve performance comparable to classical graph-theoretic algorithms on benchmark matrices.
  • Computational and storage costs of sparse matrix factorization decrease when the learned orderings are used.
  • The approach generalizes to unseen matrices after training on a representative set.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same two-stage GNN pattern could be tested on related ordering problems such as bandwidth minimization or nested dissection.
  • If the surrogate correlates strongly with actual fill-in, hybrid schemes that warm-start classical heuristics with the network output become feasible.
  • Scalability to very large matrices would require checking whether the multi-grid GNN training cost remains practical as matrix size grows.

Load-bearing premise

Minimizing the proposed fill-in surrogate derived from spectral embedding and rank distribution will actually produce orderings that reduce fill-in when the reordered matrix is factored on matrices not seen during training.

What would settle it

Train the network on a collection of matrices, apply the resulting reorderings to a held-out set of standard sparse matrices, run sparse LU factorization on each, and count the fill-ins generated; if the count is not competitive with or better than established methods such as AMD or METIS on a majority of the test cases, the central claim does not hold.

Figures

Figures reproduced from arXiv: 2605.17339 by Huiyuan Li, Shuzi Niu, Tao Yuan, Ziwei Li.

Figure 1
Figure 1. Figure 1: LU factorization of the matrix Trefethen_500 with different reorder [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Architecture of UDNO. 3.1 Spectral Embedding The first stage of our method adopts the setup of the initial phase of the graph partitioning work by Alice Gatti et al. [12]. This approach utilizes a multi￾grid-like GNN architecture to approximate the d − 1 eigenvectors associated with the smallest non-zero eigenvalues, thereby serving as node-level feature representations of the graph [PITH_FULL_IMAGE:figur… view at source ↗
Figure 3
Figure 3. Figure 3: Nnz Ratio and Ordering time changes along with the increase of matrix [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes a deep learning framework for sparse matrix reordering to reduce fill-in during factorization. It employs a multi-grid-like GNN to approximate the smallest eigenvectors of the graph Laplacian for spectral embedding, followed by a second multi-grid-like GNN that minimizes a fill-in surrogate derived from rank distribution. The central claim is that this approach bridges reordering and factorization and achieves competitive performance with traditional graph-theoretic algorithms on experimental benchmarks.

Significance. If the surrogate minimization is shown to reliably predict and reduce actual fill-in on held-out matrices, the work would offer a data-driven alternative to NP-hard combinatorial reordering problems, with potential impact on efficiency in large-scale sparse linear algebra applications such as scientific computing and machine learning.

major comments (2)
  1. [Abstract and Experimental Results] The central claim that minimizing the rank-distribution surrogate produces reorderings with reduced fill-in relies on an unverified correlation; the manuscript provides no ablation studies, correlation coefficients, or statistical tests demonstrating that lower surrogate values predict lower nonzero counts during actual factorization on unseen test matrices (see abstract and experimental results description).
  2. [Method Description] The surrogate is constructed directly from the rank distribution of the spectral embedding produced by the first GNN; this introduces a risk of circularity in which the second GNN learns a mapping within the same feature space rather than an independent predictor of factorization fill-in (see method overview).
minor comments (2)
  1. [Method Description] The term 'multi-grid-like GNN architecture' is used without a precise definition of the coarsening, prolongation, or smoothing operators relative to classical algebraic multigrid or standard GNN message-passing layers.
  2. [Experimental Results] No mention of reproducibility measures such as code release, random seed reporting, or data splits for the training and test matrices.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback. We address each major comment below, agreeing where revisions are needed to strengthen the validation and clarity of the work.

read point-by-point responses

  1. Referee: [Abstract and Experimental Results] The central claim that minimizing the rank-distribution surrogate produces reorderings with reduced fill-in relies on an unverified correlation; the manuscript provides no ablation studies, correlation coefficients, or statistical tests demonstrating that lower surrogate values predict lower nonzero counts during actual factorization on unseen test matrices (see abstract and experimental results description).

    Authors: We agree that the manuscript would benefit from explicit verification of the surrogate's predictive power. The current experimental results focus on end-to-end reordering quality relative to baselines, but do not include direct correlation analysis or statistical tests linking surrogate values to actual fill-in on held-out matrices. We will add ablation studies, correlation coefficients, and statistical tests on unseen test matrices in the revised version to address this. revision: yes

  2. Referee: [Method Description] The surrogate is constructed directly from the rank distribution of the spectral embedding produced by the first GNN; this introduces a risk of circularity in which the second GNN learns a mapping within the same feature space rather than an independent predictor of factorization fill-in (see method overview).

    Authors: The first GNN approximates the spectral embedding independently, while the second GNN is trained to minimize a surrogate objective defined as a deterministic function of the rank distribution of that embedding. The surrogate approximates potential fill-in locations and is not recomputed from the second network's outputs in a looped manner. We will revise the method overview to explicitly separate the embedding step from the surrogate minimization and clarify that the second GNN learns permutations reducing this fixed objective. revision: yes

Circularity Check

1 steps flagged

Fill-in surrogate minimization reduces to rank distribution derived from the model's own spectral embedding

specific steps
  1. self definitional [Abstract]
    "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."

    The surrogate function is explicitly constructed from the rank distribution of the spectral embedding produced by the first GNN; the second GNN's minimization step therefore optimizes a quantity defined directly from the model's own outputs. The resulting permutation is presented as a prediction of reduced fill-in, yet it is the direct result of minimizing the internally defined surrogate rather than an independent quantity.

full rationale

The derivation chain first learns spectral embedding via GNN approximation of Laplacian eigenvectors, then defines a fill-in surrogate from the rank distribution of that embedding and minimizes it with a second GNN. This makes the claimed reordering (and its fill-in reduction) equivalent by construction to optimizing an internally generated quantity rather than an independently validated predictor of actual factorization fill-in. The central bridging claim therefore rests on a self-contained surrogate whose correlation to real nonzero growth is not separately demonstrated.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The framework rests on the assumption that graph-Laplacian eigenvectors capture ordering-relevant structure and that a learned rank-distribution surrogate correlates with actual fill-in. No new physical entities are postulated; the main free parameters are the GNN weights and any scaling factors inside the surrogate.

free parameters (1)
  • GNN weights and surrogate scaling factors
    Learned parameters of the two multi-grid GNNs and any coefficients inside the rank-distribution surrogate that are fitted to training matrices.
axioms (2)
  • domain assumption The graph Laplacian of the sparse matrix encodes the structural information relevant to fill-in during factorization.
    Invoked when the first GNN is trained to approximate its smallest eigenvectors.
  • ad hoc to paper Minimizing the rank-distribution surrogate will reduce actual fill-in on unseen matrices.
    Central modeling choice that bridges the reordering and factorization stages.

pith-pipeline@v0.9.0 · 5703 in / 1495 out tokens · 35088 ms · 2026-05-20T14:43:08.243203+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    R., Davis, T

    Amestoy, P. R., Davis, T. A., Duff, I. S.: An approximate minimum degree order- ing algorithm. SIAM Journal on Matrix Analysis and Applications17(4), 886–905 (1996)

    work page 1996

  2. [2]

    T., Pothen, A., Simon, H

    Barnard, S. T., Pothen, A., Simon, H. D.: A spectral algorithm for envelope reduction of sparse matrices. In: Proceedings of the 1993 ACM/IEEE Con- ference on Supercomputing, pp. 493–502. ACM, New York, NY, USA (1993). https://doi.org/10.1145/169627.169790

    work page doi:10.1145/169627.169790 1993

  3. [3]

    T., Simon, H

    Barnard, S. T., Simon, H. D.: A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. In: Proceedings of the 6th SIAM Conference on Parallel Processing for Scientific Computing, pp. 711–718. SIAM, Philadelphia, PA, USA (1993)

    work page 1993

  4. [4]

    D., Bolet, G

    Booth, J. D., Bolet, G. S.: Neural Acceleration of Graph Based Util- ity Functions for Sparse Matrices. IEEE Access11, 31619–31635 (2023). https://doi.org/10.1109/ACCESS.2023.3262453

    work page doi:10.1109/access.2023.3262453 2023

  5. [5]

    N., Jones, C.: A heuristic for reducing fill-in in sparse matrix factorization

    Bui, T. N., Jones, C.: A heuristic for reducing fill-in in sparse matrix factorization. In: Proceedings of the 6th SIAM Conference on Parallel Processing for Scientific Computing, pp. 445–452. SIAM, Philadelphia, PA, USA (1993)

    work page 1993

  6. [6]

    In: Proceedings of the 24th National Conference, pp

    Cuthill, E., McKee, J.: Reducing the bandwidth of sparse symmetric matrices. In: Proceedings of the 24th National Conference, pp. 157–172. ACM, New York, NY, USA (1969). https://doi.org/10.1145/800195.805928

    work page doi:10.1145/800195.805928 1969

  7. [7]

    B., Zhang, Y., Dilkina, B., Song, L.: Learning combinatorial op- timization algorithms over graphs

    Dai, H., Khalil, E. B., Zhang, Y., Dilkina, B., Song, L.: Learning combinatorial op- timization algorithms over graphs. In: Proceedings of the 31st International Confer- ence on Neural Information Processing Systems, pp. 6351–6361. Curran Associates Inc., Red Hook, NY, USA (2017)

    work page 2017

  8. [8]

    In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases

    Dasgupta,A.,Kumar,P.:AlphaElimination:UsingDeepReinforcementLearningto Reduce Fill-In During Sparse Matrix Decomposition. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer (2023)

    work page 2023

  9. [9]

    A., Hu, Y.: The University of Florida Sparse Matrix Collec- tion

    Davis, T. A., Hu, Y.: The University of Florida Sparse Matrix Collec- tion. ACM Transactions on Mathematical Software38(1), Article 1 (2011). https://doi.org/10.1145/2049662.2049663

    work page doi:10.1145/2049662.2049663 2011

  10. [10]

    S., Erisman, A

    Duff, I. S., Erisman, A. M., Reid, J. K.: Direct Methods for Sparse Matrices. Clarendon Press, Oxford (1986) Ziwei Li, Tao Yuan, Shuzi Niu() , and Huiyuan Li

    work page 1986

  11. [11]

    Journal of Machine LearningResearch23(303),1–28(2022).https://jmlr.org/papers/v23/21-0644.html

    Gatti, A., Hu, Z., Smidt, T., Ghysels, P.: Graph partitioning and sparse matrix or- dering using reinforcement learning and graph neural networks. Journal of Machine LearningResearch23(303),1–28(2022).https://jmlr.org/papers/v23/21-0644.html

    work page 2022

  12. [12]

    G., Ghysels, P.: Deep Learning and Spectral Embedding for Graph Partitioning

    Gatti, A., Hu, Z., Smidt, T., Ng, E. G., Ghysels, P.: Deep Learning and Spectral Embedding for Graph Partitioning. In: Proceedings of the 2021 SIAM Conference on Computational Science and Engineering (CSE21), pp. 1–12. SIAM, Philadelphia, PA, USA (2021). https://doi.org/10.1137/1.9781611977141.3

    work page doi:10.1137/1.9781611977141.3 2021

  13. [13]

    SIAM Journal on Matrix Analysis and Applications18(3), 706–732 (1997)

    George, A., Pothen, A.: An analysis of spectral envelope reduction via quadratic assignment problems. SIAM Journal on Matrix Analysis and Applications18(3), 706–732 (1997). https://doi.org/10.1137/S0895479894262865

    work page doi:10.1137/s0895479894262865 1997

  14. [14]

    A.: Nested dissection of a regular finite element mesh

    George, J. A.: Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis10(2), 345–363 (1973)

    work page 1973

  15. [15]

    SIAM Journal on Scientific Computing20(1), 359–392 (1998)

    Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing20(1), 359–392 (1998). https://doi.org/10.1137/S1064827595287997

    work page doi:10.1137/s1064827595287997 1998

  16. [16]

    Technical Report, University of Minnesota, Minneapolis, MN, USA (1998)

    Karypis,G.,Kumar,V.:METIS:ASoftwarePackageforPartitioningUnstructured Graphs, Partitioning Meshes, and Computing Fill-Reduced Orderings of Sparse Ma- trices. Technical Report, University of Minnesota, Minneapolis, MN, USA (1998)

    work page 1998

  17. [17]

    Liu, J. W. H.: Modification of the Minimum-Degree Algorithm by Multiple Elim- ination. ACM Transactions on Mathematical Software (TOMS)11(2), 141–153 (1985). https://doi.org/10.1145/214393.214403

    work page doi:10.1145/214393.214403 1985

  18. [18]

    In: Proceedings of the 37th International Conference on Machine Learning, vol

    Luz, I., Galun, M., Maron, H., Basri, R., Yavneh, I.: Learning Algebraic Multigrid Using Graph Neural Networks. In: Proceedings of the 37th International Conference on Machine Learning, vol. 119, pp. 6489–6499. PMLR, Vienna, Austria (2020). https://proceedings.mlr.press/v119/luz20a.html

    work page 2020

  19. [19]

    Technical Report, LaBRI, Université Bordeaux, Bordeaux, France (2020)

    Pellegrini, F., Chevalier, C.: SCOTCH: Static Mapping, Graph, Mesh and Hyper- graph Partitioning, and Parallel and Sequential Sparse Matrix Ordering Package. Technical Report, LaBRI, Université Bordeaux, Bordeaux, France (2020)

    work page 2020

  20. [20]

    D., Liou, K

    Pothen, A., Simon, H. D., Liou, K. P.: Partitioning sparse matrices with eigenvec- tors of graphs. SIAM Journal on Matrix Analysis and Applications11(3), 430–452 (1990). https://doi.org/10.1137/0611030

    work page doi:10.1137/0611030 1990

  21. [21]

    D., Wang, L.: Spectral nested dissection

    Pothen, A., Simon, H. D., Wang, L.: Spectral nested dissection. Technical Report CS-92-01, Department of Computer Science, Pennsylvania State University, Uni- versity Park, PA (1992). Also available as NASA Ames Research Center Report RNR-92-003

    work page 1992

  22. [22]

    J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations

    Rose, D. J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Graph Theory and Computing, pp. 183–217. Elsevier (1972)

    work page 1972

  23. [23]

    D.: Partitioning of unstructured problems for parallel pro- cessing

    Simon, H. D.: Partitioning of unstructured problems for parallel pro- cessing. Computing Systems in Engineering2(2–3), 135–148 (1991). https://doi.org/10.1016/0956-0521(91)90014-3

    work page doi:10.1016/0956-0521(91)90014-3 1991

  24. [24]

    In: Proceedings of the 1st International Conference on Web Search and Data Mining (WSDM), pp

    Taylor, M., Guiver, J., Robertson, S., Minka, T.: SoftRank: Optimising Non- Smooth Rank Metrics. In: Proceedings of the 1st International Conference on Web Search and Data Mining (WSDM), pp. 77–86. ACM, New York, NY, USA (2008). https://doi.org/10.1145/1341531.1341544

    work page doi:10.1145/1341531.1341544 2008

  25. [25]

    SIAM Journal on Algebraic Discrete Methods2(1), 77–79 (1981)

    Yannakakis, M.: Computing the Minimum Fill-In is NP-Complete. SIAM Journal on Algebraic Discrete Methods2(1), 77–79 (1981). https://doi.org/10.1137/0602010

    work page doi:10.1137/0602010 1981

  26. [26]

    M.: Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem

    Zheng, J., He, K., Zhou, J., Jin, Y., Li, C. M.: Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem. In: Proceedings of the AAAI Conference on Artificial Intelligence35, 12445–12452. AAAI Press, New York, NY, USA (2021). https://doi.org/10.1145/569147.569149

    work page doi:10.1145/569147.569149 2021