A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees

Rasmus Kyng, Zhao Song

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:

  1. Doob Martingales: Constructing a sequence of random variables to track the sum of matrices.
  2. Matrix Freedman Inequality: Applying this inequality to the martingale to bound large deviations.
  3. 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

Abstract

Strongly Rayleigh distributions are a class of negatively dependent distributions of binary-valued random variables [Borcea, Branden, Liggett JAMS 09]. Recently, these distributions have played a crucial role in the analysis of algorithms for fundamental graph problems, e.g. Traveling Salesman Problem [Gharan, Saberi, Singh FOCS 11]. We prove a new matrix Chernoff bound for Strongly Rayleigh distributions. As an immediate application, we show that adding together the Laplacians of $\epsilon^{-2} \log^2 n$ random spanning trees gives an $(1\pm \epsilon)$ spectral sparsifiers of graph Laplacians with high probability. Thus, we positively answer an open question posed in [Baston, Spielman, Srivastava, Teng JACM 13]. Our number of spanning trees for spectral sparsifier matches the number of spanning trees required to obtain a cut sparsifier in [Fung, Hariharan, Harvey, Panigraphi STOC 11]. The previous best result was by naively applying a classical matrix Chernoff bound which requires $\epsilon^{-2} n \log n$ spanning trees. For the tree averaging procedure to agree with the original graph Laplacian in expectation, each edge of the tree should be reweighted by the inverse of the edge leverage score in the original graph. We also show that when using this reweighting of the edges, the Laplacian of single random tree is bounded above in the PSD order by the original graph Laplacian times a factor $\log n$ with high probability, i.e. $L_T \preceq O(\log n) L_G$. We show a lower bound that almost matches our last result, namely that in some graphs, with high probability, the random spanning tree is $\it{not}$ bounded above in the spectral order by $\frac{\log n}{\log\log n}$ times the original graph Laplacian. We also show a lower bound that in $\epsilon^{-2} \log n$ spanning trees are necessary to get a $(1\pm \epsilon)$ spectral sparsifier.
BibTeX
@inproceedings{kyng2018matrix,
  author = {Rasmus Kyng and Zhao Song},
  title = {{A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees}},
  booktitle = {FOCS},
  year = {2018},
  doi = {10.1109/focs.2018.00043},
}
Figure