CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs
Abstract
Graph-data workloads such as diffusion estimation, ranking, semi-supervised learning, and network optimization often solve many Laplacian or symmetric diagonally dominant M-matrix (SDDM) systems with the same coefficient matrix. Approximate Cholesky preconditioners eliminate vertices one at a time and store the resulting sparse approximate factorization, the \emph{factor}, whose construction cost is amortized across these solves. But eliminating a vertex, the \emph{pivot}, creates a dense Schur-complement clique among its d active neighbors. We introduce CAST (Canonical Approximate Schur Tree), which replaces this clique with a weighted random spanning tree sampled directly from it. Every realization is connected and contains exactly d-1 edges, while reweighting each selected edge by the reciprocal of its tree-inclusion probability makes the update unbiased. The distribution is independent of the ordering of the pivot neighbors, and we prove that its leverage-score marginals minimize the largest normalized reweighted-edge contribution among unbiased inverse-marginal one-tree estimators. We also introduce CAST-ρ, which replaces each pivot neighbor with ρ copies, each carrying a 1/ρ share of that neighbor's incident weight, samples a weighted random spanning tree on the expanded clique, and contracts the copies back to the original neighborhood. The resulting update remains unbiased and connected, can be sampled exactly in O(ρd) time, and satisfies a 1/ρ bound on the second moment of the normalized local Schur error. Increasing ρ therefore reduces certified local sampling variability, but may increase construction cost and downstream fill. Empirically, we observe that CAST-1 is the faster default, whereas CAST-2 is preferable when its additional edge contributions remain inexpensive.
Related
- Schur States and Many-Body Quantum Walks on Line Graphs
- Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
- Sparse Approximate Chromatic Profiles of Triangle-Free Graphs
- Direct Message Approximation (DMA): A Consistency-Based Framework for Tractable Approximate Inference on Factor Graphs
- Asymptotical results on the automorphism groups of canonical double cover of graphs
BibTeX
@misc{chaitanya2026cast,
title = {{CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs}},
author = {Meher Chaitanya and Cameron Musco and Aristides Gionis},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09255},
eprint = {2609.09255},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09255},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs
AU - Meher Chaitanya
AU - Cameron Musco
AU - Aristides Gionis
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.09255
UR - https://arxiv.org/abs/2609.09255
AB - Graph-data workloads such as diffusion estimation, ranking, semi-supervised learning, and network optimization often solve many Laplacian or symmetric diagonally dominant M-matrix (SDDM) systems with the same coefficient matrix. Approximate Cholesky preconditioners eliminate vertices one at a time and store the resulting sparse approximate factorization, the \emph{factor}, whose construction cost is amortized across these solves. But eliminating a vertex, the \emph{pivot}, creates a dense Schur-complement clique among its d active neighbors. We introduce CAST (Canonical Approximate Schur Tree), which replaces this clique with a weighted random spanning tree sampled directly from it. Every realization is connected and contains exactly d-1 edges, while reweighting each selected edge by the reciprocal of its tree-inclusion probability makes the update unbiased. The distribution is independent of the ordering of the pivot neighbors, and we prove that its leverage-score marginals minimize the largest normalized reweighted-edge contribution among unbiased inverse-marginal one-tree estimators. We also introduce CAST-ρ, which replaces each pivot neighbor with ρ copies, each carrying a 1/ρ share of that neighbor's incident weight, samples a weighted random spanning tree on the expanded clique, and contracts the copies back to the original neighborhood. The resulting update remains unbiased and connected, can be sampled exactly in O(ρd) time, and satisfies a 1/ρ bound on the second moment of the normalized local Schur error. Increasing ρ therefore reduces certified local sampling variability, but may increase construction cost and downstream fill. Empirically, we observe that CAST-1 is the faster default, whereas CAST-2 is preferable when its additional edge contributions remain inexpensive.
ER -