Metraipolis › archive › dc_5705f1808ecd

CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs — arXiv:2609.09255

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.09255
License (as archived)
CC0-1.0
Archived
2026-10-16T10:13:24.509Z
SHA-256 of the archived text
595e9e4a7f2d466db68fe185576097000c6ab8f393671a0aaa6e060dadf38117
Stable URL of this page
https://metraipolis.com/documento/dc_5705f1808ecd

How to cite

CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs — arXiv:2609.09255 — arXiv (en), https://arxiv.org/abs/2609.09255 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5705f1808ecd (Metraipolis archive dc_5705f1808ecd, sha256 595e9e4a7f2d466db68fe185576097000c6ab8f393671a0aaa6e060dadf38117)
BibTeX
@misc{dc5705f1808ecd,
  title = {CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs — arXiv:2609.09255},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.09255},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5705f1808ecd; sha256 595e9e4a7f2d466db68fe185576097000c6ab8f393671a0aaa6e060dadf38117},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.09255. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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-$\rho$, which replaces each pivot neighbor with $\rho$ copies, each carrying a $1/\rho$ 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(\rho d)$ time, and satisfies a $1/\rho$ bound on the second moment of the normalized local Schur error. Increasing $\rho$ 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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-10 in math.NA).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG); Numerical Analysis (math.NA).
Pagina del lavoro: https://arxiv.org/abs/2609.09255 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T08:46:35.716Z dalla pagina https://arxiv.org/catchup/math.NA/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).