Causal Structure Learning for Sparse Matrix Fill-in Reduction

The performance of sparse direct solvers is fundamentally governed by fill-in, i.e. new nonzero entries arising from the LU factorization of a sparse matrix, as they dictate memory footprint and subsequent computation time. For decades, a variety of graph-theoretic algorithms have aimed to minimize fill-in, a problem known to be both NP-hard and critically important. While recent deep learning methods, optimizing surrogate fill-in objectives, show empirical promise and can outperform classical algorithms on certain matrices, they offer limited interpretability into the underlying mechanism of fill-in generation. To address this, we propose a novel reordering approach, Causal Triplet Structure Learning (CTS), which is grounded in the Fill-Path Theorem and reduces arbitrary-length fill-paths to length-two candidate triplets, identifies the causal structures that trigger fill-in, and intervenes to block their formation. Empirically, we design a multigrid-style GAT with KAN activations to learn vertex embeddings and introduce a causal triplet loss that discourages such structures during training. Experiments on the SuiteSparse Matrix Collection demonstrate that our method reduces fill-in by 6$\times$, leading to 12$\times$ speedup in factorization time compared to state-of-the-art methods on Chemical Process Simulation and Computational Fluid Dynamics matrices.