Brief Announcement: Distributed Sparsest Cut via Eigenvalue Estimation

A graph cut is a partition of the vertices into two disjoint subsets, where the size of the cut is the total number of edges crossing between them, and the sparsity of the cut measures how small this cut is relative to total edge weight of the smaller side, i.e., in comparison to the sum of its vertex degrees. Graph cuts are a central object in theoretical computer science and algorithm design. Cuts are especially important in communication networks because they represent the capacity for information to flow between different parts of the system. A sparse cut – where only a few edges connect two large subsets – can become a bottleneck, severely limiting bandwidth or throughput. A central question for guaranteeing the performance of network algorithms is to determine the minimum sparsity of cuts in a given communication network. For example the runtime of the famous PUSH-PULL protocol depends on the sparsest cut value [11]. More generally, graphs without sparse cuts support fast mixing of random walks [20], and enable efficient routing due to their strong connectivity [9, 10]. This motivates the use of expander decompositions, which partition a graph into high-conductance clusters (i.e, no sparse internal cuts), and sparse inter-cluster connections. Such decompositions are powerful algorithmic tools: thanks to efficient routing, many algorithms run significantly faster on high-conductance subgraphs, allowing problems to be solved locally within clusters before handling the sparse inter-cluster parts.

In this work, we present simple, time and bandwidth efficient distributed algorithms to approximate the sparsest cut value. Our randomized algorithms run in the classic $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ model of distributed computing where a communication network is abstracted as an $n$-vertex graph with vertices being computing entities and edges serving as bandwidth-limited communication links. Communication happens in synchronous rounds, in each of which each vertex can send a $O(\log n)$-bit message to each of its neighbors and the complexity measure is the number of communication rounds until the vertices have computed their outputs, e.g., until they have output an approximate value of the sparsest cut.

Formally, the sparsity of a set (or cut) $S\subseteq V$ in a graph $G=(V,E)$ is defined as as

where the volume $\mathrm{Vol}(S)$ of a set of vertices $S$ is the sum of of the degrees of the vertices in the set ${\sum }_{v\in S}\mathrm{deg}(v)$. The value $\varphi (S)$ is also known as the conductance of the set $S$. The sparsest cut $\varphi (G)\in [0,1]$ of a graph $G$ is the minimum sparsity of a subset $S\subseteq V$. This is also known as the conductance of the graph.

The relative notion $\varphi (G)$ can be viewed as a normalized quantification of cut size. In contrast to computing minimum cuts, which quantify the absolute size of a cut, determining the sparsest cut or the conductance is not only NP-complete [17] but also APX-hard under the unique games conjecture [6]. Consequently, although no polynomial-time algorithm can approximate the optimum arbitrarily well (unless $P=NP$), a variety of approximation algorithms with provable – albeit weaker – guarantees have been developed across different computational models. Next, we present our results and compare them with the state of the art in the field. As the sparsest cut and the conductance have been extensively studied we provide further background and related work in the full version.

Our first result is an efficient $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ algorithm to approximate the sparsest cut.

In general, there are two approaches for developing approximation algorithms for the sparsest cut, the flow approach, that we detail in the full version, and the spectral approach, which we use to prove Theorem 1. On a high-level, one computes the spectrum (or parts of it) of the graph, i.e., its eigenvalues, and then uses Cheeger’s Inequality²²2Cheeger’s Inequality [2, 1, 21] relates the second-smallest eigenvalue ${\lambda }_2$ of the normalized Laplacian to the graph’s conductance $\varphi$, showing that $\frac{1}{2}{\lambda }_2\le \varphi \le \sqrt{2{\lambda }_2}$. to derive an approximation of $\varphi (G)$ from the eigenvalues. Due to the limitations imposed by Cheeger’s Inequality, the best possible approximation achievable through spectral methods is $\sqrt{2\varphi }$. Our technical result is slightly stronger than Theorem 1. In fact, we can attain this theoretical bound – up to an arbitrarily small additive error – in $O({\log }^{2}n/{\epsilon }^2+\log n/{\epsilon }^4)$ rounds. See the proof of Theorem 1 for the details.

For unweighted graphs, we compare our result against the previously best algorithm by Chen, Meierhans, Probst Gutenberg, and Saranurak that provides a $O(\varphi {\log }^{2}n)$-approximation of $\varphi$ [7]³³3They do not state this result explicitly, but they implement the cut-matching game from [18] (see Appendix A) in the distributed setting. As stated in [18], this cut-matching game gives such an approximation.. Our approximation is more precise than [7] when $\varphi =\mathrm{\Omega }(1/{\log }^{4}n)$, and is faster in all cases: [7] takes $O(\text{poly}\log n/{\varphi }^4)$ rounds. Upon inspection of their $\text{poly}\log n$, they have a total round complexity of at least $O({\log }^{20}n)$ in the regime where their approximation is better.

Prior to [7], Das Sarma, Molla, and Pandurangan [19] gave a different algorithm to approximate the sparsest cut, which also works for weighted graphs. They computed an $O(\sqrt{\varphi }\text{poly}\log n)$-approximation in $O(\frac{1}{b}(n+\frac{1}{\varphi }){\log }^{2}n)$ rounds if the graph has a sparse cut of balance $b$, i.e., both sides $S$ of the cut satisfy $\mathrm{Vol}(S)\ge 2b|E|$. Building on the methods of [19], Kuhn and Molla improved the approximation ratio to $O(\sqrt{\varphi \log n})$ and the runtime to $O(D+\frac{{\log }^{2}n}{b\varphi })$ [14]. For balanced cuts $b=\mathrm{\Omega }(1)$, we improve their approximation ratio by a factor $\sqrt{\log n}$, while matching their running time. For unbalanced cuts, also their algorithm can take as much as $\mathrm{\Omega }(n^2)$ time, so we do not only improve the approximation ratio, but also the running time exponentially.

Our core technical contributions are efficient $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ algorithms to compute the approximate (partial) spectrum of a graph. In essence, Theorems 1 and 2 then follow as direct consequences via Cheeger’s Inequality. Nevertheless, we chose to present these theorems first, as they are more accessible to a broader audience and can be compared with prior work.

As mentioned, Theorems 1 and 2 follow as direct consequences from our eigenvalue estimation results via Cheeger’s Inequality. Here, we focus on our core technical contribution: efficient $\mathrm{𝖢𝖮𝖭𝖦𝖤𝖲𝖳}$ algorithms to compute the approximate (partial) spectrum of a graph. The main ingredient of our algorithms is the well-known power method for approximating the largest eigenvalue of a matrix. Let $M$ be any matrix. The power method, also known as power iteration or Von Mises iteration, starts with a random vector and converges to the eigenvector corresponding to the largest eigenvalue of $M$. It is a standard technique in numerical linear algebra, see, e.g., [12]. The procedure is as follows:

With constant probability over the randomness of the start vector $x_0$, the power method outputs a vector $x_k$ whose Rayleigh coefficient $\frac{x_k^{T}M{x}_k}{x_k^T{x}_k}$ is close to the largest eigenvalue of the matrix $M$. In the full version, we provide both intuition and a formal proof.

In community detection, [5] used an algorithm that is in the same spirit as the power method but not entirely equal. In case of a sufficiently small balanced cut, and some additional technical assumptions, they can provide an approximate sparsest cut. Since the approximation factor depends on the technical assumptions, we will not state their exact guarantees here.

In the full version, we describe the power method in detail, provide a proof, and discuss the challenges of implementing it in a distributed setting.