Aaron Schild

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2019-136

September 19, 2019

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-136.pdf

Graph partitioning has played an important role in theoretical computer science, particularly in the design of approximation algorithms and metric embeddings. In some of these applica- tions, fundamental tradeoffs in graph partitioning prevented further progress. To overcome these barriers, we consider partitions of certain derived graphs of an undirected graph G ob- tained by applying Gaussian elimination to the Laplacian matrix of G to eliminate vertices from G. We use this technique and others to obtain new results on the following fronts: Cheeger’s Inequality: Cheeger’s inequality shows that any undirected graph G with min- imum √ nonzero normalized Laplacian eigenvalue λ G has a cut with conductance at most O( λ G ). Qualitatively, Cheeger’s inequality says that if the relaxation time of a graph is high, there is a cut that certifies this. However, there is a gap in this relationship, as cuts can have conductance as low as Θ(λ G ). To better approximate the relaxation time of a graph, we consider a more general object. Specifically, instead of bounding the mixing time with cuts, we bound it with cuts in graphs obtained via Gaussian elimination from G. Combinatorially, random walks in these graphs are equivalent in distribution to random walks in G restricted to a subset of its vertices. As a result, all Schur complement cuts have conductance at least Ω(λ G ). We show that unlike with cuts, this inequality is tight up to a constant factor. Specifically, there is a derived graph containing a cut with conductance at most O(λ G ). Oblivious Routing: We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is O(log 2 n). This is a consequence of a more general result which shows that the spectral norm of the entrywise absolute value of the transfer impedance matrix of a graph is O(log 2 n). This result implies a simple oblivious routing scheme based on electrical flows in the case of transitive graphs. Random Spanning Tree Sampling: We give an m 1+o(1) β o(1) -time algorithm for generat- ing uniformly random spanning trees in weighted graphs with max-to-min weight ratio β. In2 the process, we illustrate how fundamental tradeoffs in graph partitioning can be overcome by eliminating vertices from a graph using Schur complements of the associated Laplacian matrix. Our starting point is the Aldous-Broder algorithm, which samples a random spanning tree using a random walk. As in prior work, we use fast Laplacian linear system solvers to shortcut the random walk from a vertex v to the boundary of a set of vertices assigned to v called a “shortcutter.” We depart from prior work by introducing a new way of employing Laplacian solvers to shortcut the walk. To bound the amount of shortcutting work, we show that most random walk steps occur far away from an unvisited vertex. We apply this observation by charging uses of a shortcutter S to random walk steps in the Schur complement obtained by eliminating all vertices in S that are not assigned to it.

Advisors: Satish Rao

---

BibTeX citation:

@phdthesis{Schild:EECS-2019-136,
    Author= {Schild, Aaron},
    Title= {Faster Algorithms and Graph Structure via Gaussian Elimination},
    School= {EECS Department, University of California, Berkeley},
    Year= {2019},
    Month= {Sep},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-136.html},
    Number= {UCB/EECS-2019-136},
    Abstract= {Graph partitioning has played an important role in theoretical computer science, particularly
in the design of approximation algorithms and metric embeddings. In some of these applica-
tions, fundamental tradeoffs in graph partitioning prevented further progress. To overcome
these barriers, we consider partitions of certain derived graphs of an undirected graph G ob-
tained by applying Gaussian elimination to the Laplacian matrix of G to eliminate vertices
from G. We use this technique and others to obtain new results on the following fronts:
Cheeger’s Inequality: Cheeger’s inequality shows that any undirected graph G with min-
imum
√ nonzero normalized Laplacian eigenvalue λ G has a cut with conductance at most
O( λ G ). Qualitatively, Cheeger’s inequality says that if the relaxation time of a graph is
high, there is a cut that certifies this. However, there is a gap in this relationship, as cuts
can have conductance as low as Θ(λ G ).
To better approximate the relaxation time of a graph, we consider a more general object.
Specifically, instead of bounding the mixing time with cuts, we bound it with cuts in graphs
obtained via Gaussian elimination from G. Combinatorially, random walks in these graphs
are equivalent in distribution to random walks in G restricted to a subset of its vertices. As
a result, all Schur complement cuts have conductance at least Ω(λ G ). We show that unlike
with cuts, this inequality is tight up to a constant factor. Specifically, there is a derived
graph containing a cut with conductance at most O(λ G ).
Oblivious Routing: We show that in any graph, the average length of a flow path in an
electrical flow between the endpoints of a random edge is O(log 2 n). This is a consequence of
a more general result which shows that the spectral norm of the entrywise absolute value of
the transfer impedance matrix of a graph is O(log 2 n). This result implies a simple oblivious
routing scheme based on electrical flows in the case of transitive graphs.
Random Spanning Tree Sampling: We give an m 1+o(1) β o(1) -time algorithm for generat-
ing uniformly random spanning trees in weighted graphs with max-to-min weight ratio β. In2
the process, we illustrate how fundamental tradeoffs in graph partitioning can be overcome
by eliminating vertices from a graph using Schur complements of the associated Laplacian
matrix.
Our starting point is the Aldous-Broder algorithm, which samples a random spanning tree
using a random walk. As in prior work, we use fast Laplacian linear system solvers to shortcut
the random walk from a vertex v to the boundary of a set of vertices assigned to v called a
“shortcutter.” We depart from prior work by introducing a new way of employing Laplacian
solvers to shortcut the walk. To bound the amount of shortcutting work, we show that most
random walk steps occur far away from an unvisited vertex. We apply this observation by
charging uses of a shortcutter S to random walk steps in the Schur complement obtained by
eliminating all vertices in S that are not assigned to it.},
}

EndNote citation:

%0 Thesis
%A Schild, Aaron 
%T Faster Algorithms and Graph Structure via Gaussian Elimination
%I EECS Department, University of California, Berkeley
%D 2019
%8 September 19
%@ UCB/EECS-2019-136
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-136.html
%F Schild:EECS-2019-136