Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
Tommaso d’Orsi, Chris Jones, Jake Ruotolo, Salil Vadhan, Jiyu Zhang · 2024
Read Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs by Tommaso d’Orsi, Chris Jones, Jake Ruotolo, Salil Vadhan, Jiyu Zhang (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17115.txt.
Introduction
Tommaso d'Orsi, Chris Jones, Jake Ruotolo, Salil Vadhan, and Jiyu Zhang present a new spectral algorithm for the sparsest cut problem. That problem asks for the cheapest way to split a graph into two large parts. Whether a fast constant-factor approximation exists is a major open question tied to deep conjectures. Their method blends listing candidate spaces from eigenvectors with a routine that improves a given cut.
The running time depends on a new quantity: how many leading eigenvectors are needed to nearly capture a sparsest cut. For low-degree Cayley graphs over Abelian groups, classic hard cases, they prove this quantity is small. That yields a near-exact approximation in the stated time. Side results bound the repeated eigenvalues of such graphs tightly.
Catalog record
| CREATOR | Tommaso d’Orsi, Chris Jones, Jake Ruotolo, Salil Vadhan, Jiyu Zhang |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-17115
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs Tommaso d’Orsi, Chris Jones, Jake Ruotolo, Salil Vadhan, Jiyu Zhang Abstract Whether or not the Sparsest Cut problem admits an efficient O ( 1 ) O(1) -approximation algorithm is a fundamental algorithmic question with connections to geometry and the Unique Games Conjecture. Revisiting spectral algorithms for Sparsest Cut, we present a novel, simple algorithm that combines eigenspace enumeration with a new algorithm for the Cut Improvement problem. The runtime of our algorithm is parametrized by a quantity that we call the solution dimension SD ε ( G ) \textup{{SD}}_{\varepsilon}(G) : the smallest k k such that the subspace spanned by the first k k Laplacian eigenvectors contains all but ε \varepsilon fraction of a sparsest cut. Our algorithm matches the guarantees of prior methods based on the threshold-rank paradigm, while also extending beyond them. To illustrate this, we study its performance on low degree Cayley graphs over Abelian groups—canonical examples of graphs with poor expansion properties. We prove that low degree Abelian Cayley graphs have small solution dimension, yielding an algorithm that computes a ( 1 + ε ) (1+\varepsilon) -approximation to the uniform Sparsest Cut of a degree- d d Cayley graph over an Abelian group of size n n in time n O ( 1 ) ⋅ exp { ( d / ε ) O ( d ) } n^{O(1)}\cdot\exp\{(d/\varepsilon)^{O(d)}\} . Along the way to bounding the solution dimension of Abelian Cayley graphs, we analyze their sparse cuts and spectra, proving that the collection of O ( 1 ) O(1) -approximate sparsest cuts has an ε \varepsilon -net of size exp { ( d / ε ) O ( d ) } \exp\{(d/\varepsilon)^{O(d)}\} and that the multiplicity of λ 2 \lambda_{2} is bounded by 2 O ( d ) 2^{O(d)} . The latter bound is tight and improves on a previous bound of 2 O ( d 2 ) 2^{O(d^{2})} by Lee and Makarychev. \DeclareCaptionType Algorithm In memory of Luca Trevisan (1971–2024) 1 Introduction For an undirected graph G , the sparsest cut measures how poor of an expander the graph is, characterizing how slowly random walks on G mix. For simplicity in this introduction, we will state our definitions just for the case of regular graphs: Definition 1.1 (Sparsest Cut) . For a d -regular graph G on n vertices and a partition (Q,\bar{Q}) of its vertex set V(G) , the (normalized) density of the cut (Q,\bar{Q}) is defined as: \displaystyle\psi_{G}(Q):=\frac{|E(Q,\bar{Q})|}{|Q|\cdot|\bar{Q}|}\cdot\frac{n}{d}\,. The sparsest cut problem is, given G , to find Q\subseteq V(G) that minimizes \psi_{G}(Q). We write \psi(G) to denote the minimum value of \psi_{G}(Q) over all cuts (Q,\bar{Q}) . The normalization factor of n/d ensures that the largest possible value of \psi(G) is 1 , because for a randomly chosen cut Q , the expectation of |E(Q,\bar{Q})| is nd/4 , and the expectation of |Q|\cdot|\bar{Q}| is n^{2}/4 . We’ll often switch back and forth between \psi(G) and the closely related quantity of conductance , defined as \phi(G)=\min_{|Q|\leqslant n/2}\phi_{G}(Q),\quad\text{ where }\quad\phi_{G}(Q)=\frac{|E(Q,\bar{Q})|}{d\cdot|Q|}. We have \phi(G)\leqslant\psi(G)\leqslant 2\cdot\phi(G) , so the problem of approximating conductance is equivalent to the problem of approximating sparsest cut , up to multiplying the approximation factor by 2. Via known reductions, up to a constant factor of approximation, sparsest cut is also equivalent to approximating several other graph parameters such as edge expansion and balanced separator [ ARV09 ] . Because of its centrality to algorithms, computational complexity, combinatorics, and geometry, efficient algorithms for sparsest cut have been the main focus of a long line of work. A polynomial-time O(\log n) -approximation algorithm was obtained via a linear programming relaxation by Leighton and Rao [ LR99 ] , and later improved to O(\sqrt{\log n}) by Arora, Rao, and Vazirani (ARV) [ ARV09 ] via semidefinite programming. To this day, the ARV algorithm remains the state-of-the-art for general graphs. A central challenge to resolving the approximability of sparsest cut is its intricate relationship with the Unique Games Conjecture (UGC) and the Small Set Expansion Hypothesis (SSEH), themselves outstanding open problems with a close connection [ Kho02 , RS10 , RST12 ] . Assuming the SSEH, sparsest cut does not have a polynomial-time O(1) -approximation algorithm [ RST12 ] (the same holds for “non-uniform” sparsest cut assuming the UGC [ CKK+06 , KV15 , AKK+08 ] ). Thus we have some evidence that beating the O(\sqrt{\log n}) approximation factor of the ARV algorithm may be hard. On the other side of the coin, searching for better approximation algorithms for sparsest cut is an ostensible approach to developing algorithms for related problems, including small-set expansion and unique games . Given the above situation, researchers have attempted to pair interesting instances with interesting algorithms to determine when constant-factor approximation to sparsest cut is possible. Below we summarize the most relevant algorithmic approaches and what is known about them. Fiedler’s Algorithm. The simplest algorithm for sparsest cut is Fiedler’s Algorithm, which is just to threshold the second eigenvector [ Fie73 ] . Fiedler’s Algorithm always finds a cut Q such that \phi(G)\leqslant\sqrt{2\lambda_{2}} , where \lambda_{2} is the second-smallest eigenvalue of the normalized Laplacian of G . Indeed, this performance guarantee for Fiedler’s Algorithm is the proof of the right-hand side of Cheeger’s Inequality, which says: \lambda_{2}/2\leqslant\phi(G)\leqslant\sqrt{2\lambda_{2}}\,. This analysis of Fiedler’s algorithm shows that it gives an O(\sqrt{\lambda_{2}}/\phi(G)) worst-case approximation ratio, which can be quite large. Indeed, examples show that the approximation factor achieved by Fiedler’s Algorithm can be as bad as \Omega(n^{1/3}) in general [ GM98 ] . Expander-like graphs. Starting around 15 years ago, a series of works gave approximation algorithms for sparsest cut and unique games on graphs that are similar to expanders. A constant-factor approximation to sparsest cut is trivial on actual expanders (every cut is a constant-factor approximation since \psi(G)=\Omega(1) ), but it took a nontrivial work of Arora et al. [ AKK+08 ] to approximate unique games on expanders. This in turn led to efficient algorithms for sparsest cut on graphs that are “expander-like” in the sense of having few small eigenvalues, as captured by the following definition: Definition 1.2 ( \tau -threshold-rank) . For a graph G and 2\geqslant\tau\geqslant 0\,, the \tau - threshold-rank \textnormal{{mul}}_{\tau}(G) is the number of eigenvalues of the normalized Laplacian with value at most \tau . Recall that G is an expander if and only if \lambda_{2} is bounded away from 0. Equivalently, there is a constant \tau>0 (independent of n ) such that \textnormal{{mul}}_{\tau}(G)=1 . For every constant \tau>0 , the works [ ABS15 , BRS11 ] give a constant-factor approximation algorithm for sparsest cut that runs in time polynomial in n but exponential in \textnormal{{mul}}_{\tau}(G) . The algorithm of Barak, Raghavendra, and Steurer [ BRS11 ] is based on a rounding of a semidefinite programming relaxation, the O(\textnormal{{mul}}_{\tau}(G)) ’th level of the Sum-of-Squares hierarchy. Recent work has extended the Sum-of-Squares technique based on looser expansion properties, including being a small-set expander [ BBK+21 ] , coming from a high-dimensional expander [ BHKL22 ] , or having a “succinct characterization” of non-expanding sets [ BM23 ] . The algorithm of Arora, Barak, and Steurer [ ABS15 ]