Reading Notes: Approximate Gaussian Elimination (Rasmus Kyng, Yale PhD 2017)

A graph Laplacian U is how a weighted graph becomes a matrix, and solving Ux = b is the computational core of electric flows, diffusion, semi-supervised learning, graph partitioning, and PDE solvers built on finite elements. In 2004, Spielman–Teng showed these systems can be solved in nearly-linear time, and their result spawned what Tenenholtz and others call the Laplacian paradigm: many graph optimization problems (max-flow, matchings, spanning tree sampling, min-cost flows) became fast because Laplacian systems became fast.

But there were two uncomfortable facts. First, the classic direct method — Gaussian elimination — suffers fill-in: eliminating vertex i from the graph adds a clique on all of its neighbors, so a sparse matrix turns dense and the runtime degrades to O(n³). Second, all near-linear solvers in the ST line achieved sparsity through heavyweight graph constructions: low-stretch trees, sparsifiers, explicit expanders. Powerful, but a lot of machinery — the original proof spanned roughly a hundred pages across three papers. The popular engineering alternative, incomplete Cholesky (just throw the fill-in away), had no guarantees whatsoever for general Laplacians.

The thesis asks the naïve question directly: what if the incomplete factorization you get by deleting fill-in at random is actually good? The answer is essentially yes, and the proof is short.

The algorithm is three lines long:

1. Randomly permute the vertices;
2. for i = 1 to n−1: eliminate vertex i;
3. instead of adding the fill-in clique on its neighbors, add a random sparse sample of that clique.

Why on earth does this work? The proof strategy is what makes the thesis worth reading:

• Additive, unbiased view. Instead of the classical multiplicative view of elimination, view the process additively: the sampled factorization is an unbiased estimator of the true LU-decomposition, with independent-ish increments you can control.
• Matrix martingales. Eliminations and sampling steps interleave, creating dependencies between the random matrices. The analysis handles this with Tropp's matrix Freedman inequality — the technical engine of the whole thesis.
• Crude leverage scores are enough. Previous solvers needed involved machinery to estimate leverage scores (low-stretch trees, ultrasparsifiers, subsampling). Here every edge starts with the crudest possible estimate “1”, and the bootstrap for newly created fill-in edges comes from a single extra fact: the effective resistance triangle inequality.

Strikingly, the entire algorithm rests on just two algebraic facts about Laplacians: they are closed under Schur complements, and effective resistances satisfy a triangle inequality. No trees, no expanders, no sparsifiers — the first solver based purely on random sampling. And the core proof fits in under ten pages, versus roughly a hundred for Spielman–Teng. Modern random matrix theory simply removed most of the machinery.

Everything above is symmetric. Directed Laplacians (row sums zero, nonpositive off-diagonals, L ≠ L^T) had resisted the paradigm: their asymmetric nature broke essentially all known techniques. The thesis delivers the first nearly-linear-time solver for directed Laplacians, via a sparse approximate LU-factorization of Eulerian Laplacians (where in-degree = out-degree at every vertex), combined with the reductions of Cohen–Kelner–Peebles–Peng–Rao–Sidford from general directed systems to Eulerian ones.

Two things I find genuinely surprising here. First, there exists an unbiased, sparse elimination estimator that preserves the null space exactly — you must maintain every vertex degree perfectly while sampling everything else, and a priori that seems impossible. Second, the analysis is done in a norm that depends on the random choices made by the algorithm itself: Schur complements of Eulerian Laplacians can blow up (the symmetric monotonicity fails), so the algorithm carefully chooses which vertices to eliminate (α-RCDD sets), periodically re-sparsifies, and measures its own error in an execution-dependent norm, proving convergence there and transferring to the usual norm at the end.

The payoff list is long. Through the known reductions, one solver gives nearly-linear-time algorithms on directed graphs for: stationary distributions of Markov chains, personalized PageRank, mixing-time estimates, hitting times, escape probabilities, and all-pairs commute times. This effectively opened a directed Laplacian paradigm.

A Schur complement is what remains of a matrix after you eliminate a block of variables — electrically, the effective network after shorting out part of the graph. The thesis gives an algorithm producing ε-approximate Laplacian Schur complements whose sparsity scales as ε⁻² (vs. ε⁻⁴ in prior work), which is exactly the regime where applications become feasible.

The headline application is random spanning trees. In a weighted graph, an edge's marginal probability under the w-uniform spanning tree distribution can be read off a tiny Schur complement, so approximate Schur complements give fast approximate edge probabilities. Starting from the O(n^ω) conditional-decimation scheme of Harvey–Xu and accelerating its bottleneck (Schur complement computation), the thesis samples a w-uniform random spanning tree in expected time Õ(max{n^4/3 m^1/2, n²}) — the first improvement for dense and/or weighted graphs in more than 20 years, and the reason this matters is that random spanning trees sat at the core of breakthroughs on symmetric and asymmetric TSP approximation, and even give cut sparsifiers. A cute trick worth stealing: the sampling is exact, not approximate — edge probabilities are recomputed adaptively to higher precision only where an error could actually flip the sampled edge.

The dissertation predates the current GNN era and makes no learning claims; everything in this section is my own reading of the transfer. But the transfer is real:

• Random-walk features at scale. Random-walk structural encodings (RWSE), hitting times, commute times, stationary distributions and escape probabilities are the raw material of many positional encodings and graph features. After this thesis, all of them are computable in nearly-linear time — including on directed graphs, where GNNs are weakest. For work like mine on positional encodings for digraphs (Hermitian/Krylov spectral PEs, analytic-walk RoPEs), this is the algorithmic license: the walk quantities we encode are not just computable, they are computable fast, with provable guarantees, at million-node scale.
• The sampling engine of spectral preprocessing. Leverage scores and effective resistances — the two protagonists of approximate Cholesky — are exactly the quantities behind spectral sparsification. Graph-learning pipelines increasingly use sparsification-style tools for rewiring (oversmoothing/oversquashing fixes), graph condensation, and multilevel coarsening. Kron reduction, the workhorse of coarsening, is a Schur complement; approximate Schur complements give coarsening with a provable spectral fidelity guarantee rather than a heuristic.
• A variance-control template for neighbor sampling. Training GNNs on sampled neighborhoods is, at its core, unbiased estimation plus variance control. The thesis's recipe — unbiased sparse estimator, martingale concentration, ordering choices that bound variance growth — is the same logical skeleton used in convergence analyses of sampling-based graph learning. It is a good place to learn the technique properly.
• Elimination as one-shot message passing. Eliminating vertex i turns its neighborhood into a clique: aggregate, then connect everyone. That is one round of global message passing, and clique sampling is a principled, effective-resistance-weighted sparse attention over exactly the edges that matter. I find this a useful mental model when thinking about pooling/attention hybrids.

• Simplicity as an accelerator. Ten pages vs. a hundred changed who can enter the field. The sampled-Cholesky proof is now standard course material, and the algorithm is simple enough to implement — see the Laplacians.jl effort, which the dissertation itself points to as a sign the Laplacian paradigm is ready for practice.
• New standard tools. Matrix martingales (Freedman's inequality) applied to interleaved elimination + sampling; the additive/unbiased view of Gaussian elimination; and error measured in an execution-dependent norm. The last of these in particular reappears in the subsequent wave of directed-graph algorithms (directed flows and negative-weight shortest paths), where norms defined on the fly by the algorithm became part of the standard toolkit.
• The directed Laplacian paradigm. For a decade, near-linear graph algorithmics was an undirected privilege. This thesis closed the gap up to logarithmic factors and unlocked Markov chain computations that previously needed super-quadratic time.
• A model of how theory simplifies. The historical arc — Spielman–Teng (2004, ~100 pp.) → a decade of refinements → Kyng–Sachdeva (2016, ~10 pp., sampling only) — is the clearest recent example of a field digesting its own breakthroughs into something a first-year student can fully understand. I wish every area had its version of this dissertation.

• Everyone: Chapter 1 — ten pages, the best summary of the Laplacian paradigm I know.
• Want the machinery: Sections 3.1–3.2 (Master Cholesky + martingale analysis). Chapter 2's preliminaries are self-contained.
• Markov chains / digraphs: Chapter 5, plus the CKP⁺16 reductions for context.
• Only here for spanning trees: Chapter 4; the Schur complement–spanning tree dictionary in Section 2.4 is the key.

Gaussian elimination has been studied since antiquity (the Nine Chapters on the Mathematical Art, ~179 CE). That there were still results this clean and this general to be found — you just have to look at the algorithm additively, and be willing to throw almost everything away at random — is the real lesson of this dissertation.

这篇笔记总结 Rasmus Kyng 在 Yale 的博士论文《Approximate Gaussian Elimination》 （导师 Daniel A. Spielman，2017）。核心思想一句话：对图的拉普拉斯矩阵做高斯消元时， 随机丢弃消元产生的大部分 fill-in（新出现的稠密元素），得到的稀疏近似分解依然是高质量的 预处理子。由此得到三大成果：

• 近似 Cholesky 分解（第 3 章，与 Sachdeva，FOCS'16）。随机置换顶点、逐个消元、 对消元产生的 fill-in 团随机采样，得到 LL^T ≈_1/2 U， 非零元数与运行时间均为 O(m log²(1/δ) log n)；配合迭代精化即得 近线性时间 Laplacian 求解器。这是第一个不依赖任何图构造（低拉伸树、稀疏化、扩展图） 而纯粹基于随机采样的求解器：算法只用到两条代数事实（Laplacian 对 Schur 补封闭、有效电阻 满足三角不等式），证明核心是矩阵鞅（Tropp 的 Freedman 不等式）+ 无偏估计视角， 正文不到十页 — 对比 Spielman–Teng 的约一百页。
• 有向 Laplacian 的首个近线性求解器（第 5 章，FOCS'17）。对 Eulerian Laplacian 做 无偏、精确保持零空间的稀疏近似 LU 分解，并在一个随算法自身随机选择而定的范数下 分析收敛（对称情形的 Schur 补单调性在有向情形失效）。结合已有归约，首次让有向图上的 平稳分布、个性化 PageRank、混合时间、hitting time、escape probability、commute time 等 随机游走量都能近线性计算，开启了"有向 Laplacian paradigm"。
• Schur 补逼近与随机生成树（第 3.4–4 章，STOC'17）。ε-近似 Laplacian Schur 补的非零元数达 O(k ε⁻²)（此前为 ε⁻⁴）； 由此在 Õ(max{n^4/3m^1/2, n²}) 时间内按 权重均匀分布采样随机生成树，是二十多年来稠密/加权图上首次超越矩阵乘法时间 O(n^ω) 的改进。

对 Graph Learning 的帮助（笔者的个人解读，非论文原意）： (i) RWSE、commute time、平稳分布等随机游走类特征/位置编码，如今即使有向图也能近线性 计算 — 这为有向图 PE（如我自己的 Hermitian/Krylov 谱 PE、analytic-walk RoPE 方向）提供了 算法层面的可行性保障；(ii) leverage score 与有效电阻采样是谱稀疏化、graph rewiring、图粗化的 共同引擎，而粗化常用的 kron reduction 本质上就是 Schur 补，近似 Schur 补给出了带谱逼近保证的 粗化方式；(iii) "无偏估计 + 鞅集中不等式"的配方，与 GNN 邻域采样训练的收敛性分析是同一副 骨架，是学习这套技术的最佳范本之一。

对理论（theory）的帮助：Laplacian paradigm 的证明从约百页压缩到十页，大幅降低了 入行门槛；矩阵鞅、消元的无偏加法视角、算法执行依赖范数，已成为后续有向流、负权最短路等 一系列工作的标准工具；加上 Laplacians.jl 等实现，"理论快 + 实现快"的 Laplacian 求解器正在 真正走向实用。

Comments welcome — find me on GitHub or by email. All errors in these notes are mine; the science is Kyng's (and his coauthors').