📖 AI 总结

本文提出CAST（Canonical Approximate Schur Tree）方法，用于改进图数据上近似Cholesky预条件子的构造。图数据工作负载（如扩散估计、排序、半监督学习）常需对同一系数矩阵反复求解拉普拉斯或SDDM系统，近似Cholesky通过逐个消元并存储稀疏因子来摊销构造成本，但消去一个顶点会在其d个活跃邻居间形成稠密的Schur补团。CAST用从该团中采样的加权随机生成树替代稠密团，每次实现均连通且恰含d-1条边，并按树包含概率的倒数重新加权，使更新保持无偏。作者证明该分布在枢轴邻居顺序下不变，且其杠杆分数边际在无偏逆边际单树估计量中最小化最大归一化重加权边贡献。进一步提出CAST-ρ，通过复制邻居并收缩，可在O(ρd)时间内精确采样，并将归一化局部Schur误差二阶矩限制在1/ρ。实验表明CAST-1为更快的默认选择，CAST-2在额外边贡献较低时更优。

🔑 关键词速览