Abstract
Strongly Rayleigh (SR) distributions represent a class of negatively dependent distributions of binary-valued random variables. While these distributions are central to analyzing algorithms for fundamental graph problems, such as the Traveling Salesman Problem, their concentration properties in matrix settings remained largely unexplored. This paper presents a new matrix Chernoff bound for SR distributions. Applying this tool, we demonstrate that the sum of Laplacians from $O(\epsilon^{-2} \log^2 n)$ random spanning trees (RSTs) yields a $(1 \pm \epsilon)$ spectral sparsifier of the original graph Laplacian with high probability. This result positively resolves an open question regarding the number of trees required for spectral approximation, matching the bounds previously established for cut sparsifiers. Additionally, we provide upper and lower bounds on the spectral order of single random trees and establish a lower bound of $\Omega(\epsilon^{-2} \log n)$ trees for spectral sparsification.
Introduction
Graph sparsification is a fundamental technique in combinatorial optimization and network analysis, aimed at reducing the complexity of a graph while preserving its essential structural properties. While "cut sparsifiers" preserve the weights of edges across any cut, "spectral sparsifiers" provide a much stronger guarantee: they approximate the Laplacian matrix of the graph, thereby preserving eigenvalues, electrical resistances, and random walk properties.
A well-established method for spectral sparsification involves sampling edges independently based on their leverage scores. However, a more structured approach involves using Random Spanning Trees (RSTs). Prior to this work, it was known that RSTs could produce cut sparsifiers, but their efficacy in spectral sparsification remained an open conjecture. The primary obstacle was the inherent dependence between edges in a spanning tree; standard concentration inequalities, such as the classical Matrix Chernoff bound, require independence.
The Matrix Chernoff Bound for Strongly Rayleigh Distributions
The core theoretical contribution of this work is the development of a Matrix Chernoff bound for Strongly Rayleigh (SR) distributions. SR distributions characterize a form of "negative dependence" where the selection of one element decreases the likelihood of selecting others. This property is crucial for spanning trees, where the inclusion of an edge reduces the probability of including other edges that would complete a cycle.
To prove this bound, the authors move beyond the standard Laplace transform methods used for independent variables. Instead, they employ:
- Doob Martingales: Constructing a sequence of random variables to track the sum of matrices.
- Matrix Freedman Inequality: Applying this inequality to the martingale to bound large deviations.
- Stochastic Covering: Leveraging the properties of SR distributions to ensure that conditioning on specific elements does not disrupt the overall distribution's stability.
The resulting bound includes an additional $\log k$ factor in the exponent compared to the independent case, reflecting the cost of dependence while still providing powerful concentration guarantees.
Spectral Sparsification via Random Spanning Trees
By applying the new Matrix Chernoff bound to the Laplacians of RSTs, the authors show that $O(\epsilon^{-2} \log^2 n)$ independent trees are sufficient to construct a $(1 \pm \epsilon)$ spectral sparsifier. To ensure the expectation of the sampled trees matches the original graph Laplacian, each edge in a tree is reweighted by the inverse of its leverage score in the original graph.
This result bridges the gap between cut and spectral sparsification for RSTs. Previously, the best-known result for spectral sparsification using RSTs required $O(\epsilon^{-2} n \log n)$ trees—a significantly larger number that scaled with the number of vertices.
Spectral Properties of Single Trees
The paper also investigates the spectral properties of a single RST. It is shown that the Laplacian of a single tree $L_T$, when reweighted by leverage scores, is bounded above in the Positive Semi-Definite (PSD) order by the original graph Laplacian $L_G$ scaled by a factor of $O(\log n)$:
$$L_T \preceq O(\log n) L_G$$
Conversely, the authors provide a lower bound showing that for certain graphs, a single RST is not bounded above by $\frac{\log n}{\log \log n} L_G$ with high probability. This indicates that while a single tree captures some structure, multiple trees are necessary for a robust spectral approximation.
Conclusion and Future Directions
This work provides the first tight analysis of the spectral properties of random spanning trees using the framework of Strongly Rayleigh distributions. While it resolves a major conjecture from 2013, several questions remain. There is a logarithmic gap between the current upper bound of $O(\log^2 n)$ trees and the lower bound of $\Omega(\log n)$ trees. Furthermore, the potential for $O(1)$ trees to provide a $\log n$-factor approximation remains an intriguing area for future research. The general Matrix Chernoff bound for SR distributions likely holds broader applications for other negatively dependent processes, such as determinantal point processes.
Summary updated