Streaming Complexity Separations for Dense and Sparse Graphs

In all of the following, the lower bounds hold against insertion-only one-pass streaming algorithms.

We first give a lower bound against randomized algorithms for the problem of outputting an approximate maximum cut. In particular, the hard instance is a family of graphs that contain $n/{\epsilon }^2$ edges. Note that for constant $\epsilon$ this is a sparse graph.

This bound is tight for the range $\epsilon \in [\omega (1/\sqrt{n}),{\epsilon }_0]$ – the matching upper bound follows from the fact that uniformly sampling about $n/{\epsilon }^2$ edges produces a graph whose Max-Cut value is a good approximation, and that there are $\exp ({\epsilon }^{-2}n\log (n{\epsilon }^2))$ graphs with $n/{\epsilon }^2$ edges.

In the dense setting, we use the $F_0$ estimation algorithm of [14] to give an algorithm that returns a $(1-\epsilon )$-approximate maximum cut in $O(n/{\epsilon }^2)$ bits of space in dense graphs (Theorem 16). We also show that $\mathrm{\Omega }(n)$ working space (the space required by the algorithm not including the space for the output) is required for dense graphs.

We give a lower bound against deterministic algorithms for the problem of outputting an approximation to the maximum cut value.

We also give separations for the problem of densest subgraph. We give an $\mathrm{\Omega }(n\log n)$ lower bound for outputting both an approximation of the density of the densest subgraph as well as an approximate densest subgraph itself in sparse graphs (Theorem 26). We then give an algorithm that returns an approximate densest subgraph in $O(n/{\epsilon }^2)$ bits of space in dense graphs (Theorem 27) and show that $\mathrm{\Omega }(n)$ working space is necessary (Theorem 28).

Using similar techniques, we show that for every constant-arity CSP over a constant size alphabet that space complexity $O(n/{\epsilon }^2)$ can be achieved in dense graphs (Theorem 29). Finally, we give algorithms for Similarity (which interestingly doesn’t require a dense stream) and Rarity in dense streams (Theorem 30 and Theorem 31).

In Section 2 we give our preliminaries, and in Section 3 we give a technical overview of our results. Then we give our randomized lower bound for maximum cut for sparse graphs in Section 4, our maximum cut algorithm for dense graphs in Section 5, and our randomized lower bound for maximum cut in dense graphs in Section 6. We give our deterministic lower bound for the maximum cut value in Section 7. All omitted proofs and our alternate algorithm for maximum cut in dense graphs are in the full version on arXiv. We present the problem definitions and our results for densest subgraph and our extensions including to all CSPs, similarity and rarity in Section 8. The full sections are in the full version.

The goal of Theorem 1 is to prove a lower bound against randomized streaming algorithms outputting an approximate maximum cut in a graph.

Given a fixed streaming algorithm and an input graph $G$, let $\mathrm{𝙲𝚘𝚖𝚙𝚛𝚎𝚜𝚜}(G)$ denote the state of the streaming algorithm after processing the edges of $G$. If the streaming algorithm uses space $s$, we can think of this as a (possibly randomized) mapping $\mathrm{𝙲𝚘𝚖𝚙𝚛𝚎𝚜𝚜}:\{\text{graphs}\}\to {\{0,1\}}^s$. Our fundamental idea is then to construct a large family $ℱ$ of graphs on $\mathrm{\Theta }(n)$ vertices ($\log |ℱ|=\mathrm{\Omega }(n\log (n{\epsilon }^2)/{\epsilon }^2)$) and show that $\mathrm{𝙲𝚘𝚖𝚙𝚛𝚎𝚜𝚜}(G)$ (typically) contains enough information about $G$ to uniquely identify it among all graphs in $ℱ$. Since $\mathrm{𝙲𝚘𝚖𝚙𝚛𝚎𝚜𝚜}(G)$ has only $s$ bits, this is information-theoretically impossible unless $s\approx |\log (ℱ)|$, allowing us to conclude the space lower bound.

Recall that $\mathrm{𝙲𝚘𝚖𝚙𝚛𝚎𝚜𝚜}(G)$ encapsulates the state of the streaming algorithm after $G$’s edges are streamed. Thus, knowledge of $\mathrm{𝙲𝚘𝚖𝚙𝚛𝚎𝚜𝚜}(G)$ can help us to identify $G$ from among a large family of graphs $ℱ$. In particular, we can “pick up where we left off” in the stream; that is, we can pick a graph $H$, add $H$’s edges to the stream, and then ask for an approximate maximum cut in $G\cup H$ (with good probability). Modulo failure probability, we can now forget about the streaming model, and think instead about the following query problem: when can $G\in ℱ$ be identified given the ability to query an approximate maximum cut in $G\cup H$ for $H$ of our choosing?

Note that in the simplest case, we might set $H$ to the empty graph, and query an approximate maximum cut in $G$ itself. However, this gives us just $n$ bits of information about $G$,¹¹1After all, a cut is just a string in ${\{0,1\}}^n$. which is not enough to identify $G$ in general (since $\log |ℱ|\gg n$). Instead, we will need to query with many different $H$’s. But which $H$’s should we use to “learn” about $G$?

Our main conceptual insight is that, by carefully constructing the graph family $ℱ$ and the query graphs $H$, we can also compute certain approximate conditional maximum cuts in $G$ itself. By this, we mean the following. If $G$ is a graph with vertex-set $V$, then a cut in $G$ is just a string in ${\{\pm 1\}}^V$, i.e., a labeling of vertices by $\{\pm 1\}$ values. The standard maximum cut problem is to find the cut in ${\{\pm 1\}}^V$ cutting the most edges in $G$. In the “conditional” maximum cut problem, we are given, in addition to $G$, a subset $S\subseteq V$ of the vertices and a cut $x\in {\{\pm 1\}}^S$ on those vertices, and we want to find the cut $y\in {\{\pm 1\}}^{V\setminus S}$ on the remaining vertices such that the full cut $xy\in {\{\pm 1\}}^V$ cuts as many edges as possible. In other words, we want to maximize the number of cut edges not over the full cube ${\{\pm 1\}}^V$, but over the subcube where the coordinates in $S$ are fixed to $x$.

Specifically, in our setup, the graphs $G\in ℱ$ are certain bipartite graphs on a vertex set $L\bigsqcup R$, with $|L|=|R|=n$, and for every partial cut $x\in {\{\pm 1\}}^L$ on the left vertices, we hope to find an approximate conditional maximum cut $y\in {\{\pm 1\}}^R$ on the right vertices. We achieve this by defining a graph $H_x$ on vertex set $V^{\prime }\supseteq V$ in such a way that when we query an approximate maximum cut $z\in {\{\pm 1\}}^{V^{\prime }}$ for $G\cup H_x$, $z_L$ is forced to (mostly) equal $x$, and $z_R$ correspondingly (mostly) recovers an approximate conditional maximum cut. (Here $z_L$ and $z_R$ denote, respectively, $z$’s restriction onto the left and right vertices of $G$.)

Our technical work now splits into two parts:

1. 1.

   We construct a very large family $ℱ$ of bipartite graphs on vertex-set $L\bigsqcup R$ such that for every $G_1\ne G_2\in ℱ$, except with probability 1% over the choice of the left-cut $𝒙\in {\{\pm 1\}}^L$, the set of approximate maximum right-cuts for $G_1$ and $G_2$ conditioned on $𝒙$ are disjoint. Specifically, to construct $ℱ$, we sample a set of random bipartite graphs with right-regularity $k=\mathrm{\Theta }(1/{\epsilon }^2)$, and then filter out graphs which fail certain desired criteria.

2. 2.

   We show how approximate maximum cut queries can be used to identify members of this family. This step combines the standard Yao’s minimax lemma / averaging ideas and a careful construction of graphs $H_x$.

To conclude this subsection, we shed some additional light on Step (1), the construction of the large family of $k$-right-regular graphs $ℱ$. $ℱ$ is required to satisfy two important properties: firstly, the distribution of left-degrees of every graph in $ℱ$ should be pseudorandom, in the sense that the total of squared left-degrees is $O(n{k}^2)$ and the total left-degree of vertices with left-degree $\mathrm{\Omega }(k)$ is $O(n\sqrt{k})$. Secondly, the pairwise overlap in the edge-sets of graphs in $ℱ$ is small.

We then show that we can separate each pair of distinct graphs $G_1,G_2\in ℱ$. Fix such a pair and sample left assignment $𝒙$ uniformly at random. We show that with high probability over $𝒙$, there does not exist any right assignment that is simultaneously near-optimal for both conditional instances $(G_1,𝒙)$ and $(G_2,𝒙)$. This is because fixing $x$ induces at each right vertex $v$ a signed imbalance which is the difference between the number of neighbors labeled $+1$ and $-1$ by $𝒙$; any near-optimal right assignment must agree with these imbalances on most vertices. Thus, if $G_1$ and $G_2$ shared a near-optimal right assignment under the same $x$, the difference in imbalance between the two has to be small. On the other hand, the low-overlap property ensures that for most right vertices these imbalances are driven by essentially disjoint neighborhoods in $G_1$ and $G_2$, leading to a large expected inconsistency under random $𝒙$. The bounded degree conditions allow us to amplify this to high probability via concentration, ruling out shared near-optimal right assignments. This separation implies that any algorithm which succeeds on a constant fraction of the instances must distinguish between a constant fraction of the pairs of graphs in $ℱ$ yielding the desired lower bound.

Our algorithm is very simple and is an application of the $F_0$ estimation algorithm from [14]. The algorithm of [14] estimates the number of distinct elements (so distinct edges here) in a stream up to a multiplicative $\epsilon$ approximation using $O(\log ({\delta }^{-1})/{\epsilon }^2+\log n)$ space with probability $1-\delta$. For any cut $x$, take $\mathrm{cut}(x)$ to denote the set of edges that crosses $x$ in the complete graph. Inclusion-exclusion therefore gives us

We can maintain $|G|$ exactly in $\log n$ bits and $|\mathrm{cut}(x)|$ is known offline. We can use the $F_0$ estimation algorithm to estimate $|G\cup \mathrm{cut}(x)|$ in the following way: run the algorithm on the input stream and then add the edges of $\mathrm{cut}(x)$ to the stream. Although the $F_0$ algorithm gives a multiplicative approximation to $|G\cup \mathrm{cut}(x)|$, this translates to $\epsilon n^2$ additive error on every cut value. Therefore, the density of the graph gives the desired approximation. Setting $\delta =2^{-\mathrm{\Theta }(n)}$ so that we can union bound over all cuts gives space $O(n/{\epsilon }^2)$. We also note that since we are using an $F_0$ sketch, we can handle the case where the same constraint is present in the stream multiple times. In this case, it is treated as if the constraint was only presented once.

Given that we are working in the setting where $\delta$ is very small, the update time of the $F_0$ sketch of [14] is $\mathrm{poly}n$. It is unclear how to speed up the update time while preserving the exact space complexity (note that in contrast uniform sampling has fast update time but suboptimal space). So, we also present an alternate algorithm which has a slightly worse space dependence (by a $\log (1/\epsilon )$ factor) but has only amortized $\mathrm{polylog}n$ update time.

Our alternate algorithm goes as follows. The first key idea is to sample $n$ random edges before the stream, as opposed to the naive approach of sampling $n$ edges during the stream. Then during the stream, we simply record which of the pre-sampled edges were actually present in the input graph with a simple bit array of size $n$ and use these edges as our sample. But how do we sample $n$ random edges before the stream in only $O(n)$ bits of space? Our second key idea is that we do not need truly i.i.d. uniform samples. So we construct a $d$-regular expander graph on vertex-set $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ ($d$ depends only on $\epsilon$) and take a random walk of length $n$ in this graph starting from a random vertex. We can then use well-known concentration inequalities for random walks on expanders (see [61]) to conclude this gives a good estimator. Crucially, there is an $O(n+\log n)$-bit implicit representation of the list of vertices on the walk (which correspond to possible edges in the graph), since all we need to store is the starting vertex and a “next-step pointer” saying “go to my $i$-th neighbor” for $i\in [d]$ for each vertex along the walk. We note that our techniques differ from [14] since we define the expander on all the possible edges of the input graph versus to generate random seeds.

We note that since $|V|=n$, $n$ bits of space are required to write down the output. However, our lower bound shows that $\mathrm{\Omega }(n)$ bits of working space (i.e., not counting the output space) is also required for this task.

To establish our lower bound, we design an exponentially large family of inputs $ℱ$ where the sets of approximately optimal solutions are pairwise disjoint. We then show that one can leverage an approximate Max-Cut streaming algorithm to correctly identify an input graph $G\in ℱ$. The set of inputs are complete bipartite graphs.

Our framework is similar to that of our randomized $\mathrm{\Omega }(n\log (n{\epsilon }^2)/{\epsilon }^2)$ lower bound. We design a large family of graphs $ℱ$ and show that $G\in ℱ$ can be identified given the ability to query an approximate maximum cut value in $G\cup H$ for $H$ of our choosing. In the deterministic setting, the query access we assume is stronger than in the randomized setting: we may augment $G$ with any $H$ and obtain exact deterministic approximations to the maximum cut value of $G\cup H$ with no failure probability and therefore with an unbounded number of queries.

We instantiate $ℱ$ as the family of graphs formed by the union of $\mathrm{\Theta }(1/{\epsilon }^2)$ perfect bipartite matchings on a vertex set of size $2n$. For every pair of distinct graphs $G_1,G_2\in ℱ$, we construct a deterministic distinguishing test $𝒯(G_1,G_2)$. Specifically, we show that for each such pair there exists a cut $x$ satisfying $|{\mathrm{𝗏𝖺𝗅}}_{G_1}\left(x\right)-{\mathrm{𝗏𝖺𝗅}}_{G_2}\left(x\right)|=\mathrm{\Omega }(n/\epsilon ).$ Using this cut, we define augmentation $H$ such that the maximum cut value of $G\cup H$ encodes ${\mathrm{𝗏𝖺𝗅}}_G\left(x\right)$. By thresholding the resulting approximate maximum cut value, we can deterministically distinguish whether the unknown graph $G$ is equal to $G_1$ or $G_2$ (with arbitrary behavior permitted otherwise). Running $𝒯(G_1,G_2)$ over all possible pairs of graphs in $ℱ$ and selecting the graph consistent with the largest number of tests uniquely identifies $G$, yielding the desired space lower bound.

We construct the hard family $ℱ$ of graphs using the so-called “deletion method”: we sample a large family of random graphs, delete all graphs which violate desired criteria, and show that the resulting family is still large because violations are improbable.

Let ${𝒢}_{\text{right-regular}}(n,k)$ be the space of $k$-right-regular bipartite simple graphs, generated by having each $v\in R$ independently choose a uniform random $k$-subset of $L$ as its neighbors.

For a bipartite graph $G=(L\bigsqcup R,E)$ and a threshold $d$, we define

Note that the first three properties impose requirements on each graph in the family $ℱ$ individually; the fourth property involves pairs of graphs, and the fifth property involves the size of the entire family.

Now we show that distinct graphs in the hard family admit incompatible sets of near-optimal right-assignments once the left assignment $x$ is fixed at random. In particular, for two different graphs $G_1,G_2$, with high probability over the choice of $x$, there does not exist any right-assignment that is simultaneously near-optimal for both conditional Max Cut instances $(G_1,x)$ and $(G_2,x)$. We will later show how to lift this to a lower bound for the standard (unconditional) Max Cut problem.

Define the density parameter $C_{\mathrm{den}}≔{10}^6$, and a corresponding regularity parameter $k≔\lfloor 1/{({10}^5{C}_{\mathrm{den}}\epsilon )}^2\rfloor$. Let ${\epsilon }_0>0$ be a sufficiently small absolute constant such that $k$ is large enough to invoke the prior lemma for all $\epsilon \le {\epsilon }_0$. The slack threshold is defined as $\tau ≔\frac{n\sqrt{k}}{2000}$. We will invoke Lemma 10 with ${\eta }_{\mathrm{tail}}≔\frac{1}{8000}$, ${\eta }_{\mathrm{near}}≔{10}^{-8}$, and $C_{\mathrm{deg}}≔10$.

Note that the graphs $G$ and $H_x$ are individually bipartite, but their union $G\cup H_x$ need not be.