arXiv:2609.09255v1 stat.ML

CAST: 그래프 상의 근사 콜레스키 분해를 위한 정준 근사 슈어 트리(Canonical Approximate Schur Tree)

CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs

Meher Chaitanya, Cameron Musco, Aristides Gionis

제출 2026-09-08

한국어 초록

확산 추정, 랭킹, 준지도 학습, 네트워크 최적화와 같은 그래프 데이터 워크로드는 동일한 계수 행렬을 갖는 다수의 라플라시안(Laplacian) 또는 대칭 대각 우세 M-행렬(SDDM) 시스템을 푸는 경우가 많다. 근사 콜레스키(Approximate Cholesky) 전처리기는 정점을 한 번에 하나씩 소거하고, 그 결과로 얻어지는 희소 근사 분해인 \emph{팩터(factor)}를 저장하며, 이 팩터의 구성 비용은 여러 번의 풀이에 걸쳐 분할 상환된다. 그러나 정점, 즉 \emph{피벗(pivot)}을 소거하면 그 피벗의 $d$개 활성 이웃 사이에 조밀한 슈어 보수(Schur-complement) 클리크가 생성된다. 본 논문은 이 클리크를 그로부터 직접 샘플링한 가중 랜덤 신장 트리(weighted random spanning tree)로 대체하는 CAST(Canonical Approximate Schur Tree)를 제안한다. 모든 실현(realization)은 연결되어 있으며 정확히 d-1개의 간선을 포함하고, 선택된 각 간선을 해당 간선의 트리 포함 확률의 역수로 재가중하면 갱신이 불편(unbiased)이 된다. 이 분포는 피벗 이웃의 순서와 무관하며, 우리는 그 레버리지 점수(leverage-score) 주변 확률이 역주변확률(inverse-marginal) 기반의 불편 단일 트리 추정량들 중에서 정규화된 재가중 간선 기여도의 최댓값을 최소화함을 증명한다. 또한 CAST-$ρ$도 제안한다. 이는 각 피벗 이웃을 $ρ$개의 복사본으로 대체하되 각 복사본이 해당 이웃의 인접 가중치(weight)의 $1/ρ$만큼을 갖게 하고, 확장된 클리크 위에서 가중 랜덤 신장 트리를 샘플링한 뒤, 복사본들을 다시 원래의 이웃으로 수축(contract)하는 방식이다. 그 결과로 얻는 갱신은 여전히 불편이며 연결되어 있고, $O(ρd)$ 시간에 정확히 샘플링할 수 있으며, 정규화된 국소 슈어 오차의 2차 모멘트에 대해 $1/ρ$ 상한을 만족한다. 따라서 $ρ$를 늘리면 보증된 국소 샘플링 변동성은 감소하지만, 구성 비용과 이후의 필-인(fill)은 증가할 수 있다. 실험적으로, CAST-1이 더 빠른 기본 선택이며, CAST-2는 추가되는 간선 기여도의 비용이 크지 않을 때 더 바람직함을 관찰하였다.

원문 초록

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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2609.09255v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.