CAST: 그래프 상의 근사 콜레스키 분해를 위한 정준 근사 슈어 트리(Canonical Approximate Schur Tree)
CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs
한국어 초록
확산 추정, 랭킹, 준지도 학습, 네트워크 최적화와 같은 그래프 데이터 워크로드는 동일한 계수 행렬을 갖는 다수의 라플라시안(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 원문에서 확인하세요.
- arXiv:2609.09255v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.