mlsanityData to 14 Oct 2026

Learning Fill-in Reduction Ordering via Graph Policy Optimization for Sparse Matrices

arXiv 2605.17362 ↗First posted 17 May 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Matrix reordering in large sparse solvers seeks a permutation that minimizes factorization fill-in to reduce memory and computation. Because the minimum fill-in ordering problem is NP-complete and fill-in is implicit in the sparsity pattern, graph-theoretic heuristics are used. Existing reinforcement learning methods either ignore sparsity patterns--missing the global fill-in--or lack local exact fill-in feedback. We propose a graph policy optimization method, modeling fill-ins from global and local views: both the policy and value networks use a multi-hop graph neural backbone to embed global fill-in; the policy further interacts with symbolic factorization over graphs to extract local, step-level fill-ins, and the resulting feedback is aligned with the value network via an adaptive saturation function to improve convergence. On the SuiteSparse Matrix Collection, our method achieves mean reductions of 29.3 in fill-ins and 31.3 in peak memory usage over state-of-the-art baselines.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 6 of its 22 references that are in the map. First posted on arXiv 17 May 2026.

Builds on

6 of 22 references.

References · 6

  1. 2017Inductive Representation Learning on Large Graphscited by 6,320
  2. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
  3. 2020Learning Algebraic Multigrid Using Graph Neural Networkscited by 54
  4. 2021Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networkscited by 8
  5. 2023Alpha Elimination: Using Deep Reinforcement Learning to Reduce Fill-In during Sparse Matrix Decompositioncited by 4
  6. 2016Collective Influence Algorithm to find influencers via optimal percolation in massively large social mediacited by 3

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025ReFill: Reinforcement Learning for Fill-In Minimization
  2. 2026Reinforcement Learning-Guided Graph Transformations for SpTRSV Optimization
  3. 2025What Fundamental Structure in Reward Functions Enables Efficient Sparse-Reward Learning?
  4. 2025Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization
  5. 2025Reinforcement learning for graph theory, Parallelizing Wagner's approach
  6. 2024Optimal Policy Sparsification and Low Rank Decomposition for Deep Reinforcement Learning
  7. 2025MatRL: Provably Generalizable Iterative Algorithm Discovery via Monte-Carlo Tree Search
  8. 2025On the Interplay Between Sparsity and Training in Deep Reinforcement Learning