Near-Optimal Hypergraph Sparsification in Insertion-Only and Bounded-Deletion Streams

To start, let us recap how we create hypergraph sparsifiers in the static setting. After an extensive line of works studying hypergraph sparsification [13, 17, 5, 10, 9, 7, 15, 11], the work of Quanrud [16] provided the simplest lens through which one can build hypergraph sparsifiers. Roughly speaking, given a hypergraph $H=(V,E)$, each hyperedge $e\in E$ is assigned a value ${\lambda }_e$ which is called its strength. The strength of a hyperedge is intuitively a measure of the (un)importance of a hyperedge; the smaller the strength of the hyperedge $e$, this means $e$ is crossing smaller cuts in the hypergraph, and so we are more likely to need to keep $e$, while if the strength is larger, then there are many other hyperedges which cross the same cuts as $e$, and thus it is not as necessary for us to keep $e$. [16] showed that for a specific definition of strength, sampling each hyperedge (independently) at rate roughly $p_e\ge \log (n)/({ϵ}^2{\lambda }_e)$ (ignoring constant factors), and assigning weight $1/p_e$ to the surviving hyperedges then yields a $(1\pm ϵ)$ sparsifier with high probability.

In fact, this procedure lends itself to a simple iterative algorithm for designing sparsifiers: starting with the original hypergraph $H$, we recover all of the hyperedges in $H$ whose strength is smaller than $\lambda \approx \log (n)/{ϵ}^2$, and denote these hyperedges by $T^{(1)}$. Then, it must necessarily be the case that all hyperedges in $H-T^{(1)}$ have large strength, and so we can afford to sample these hyperedges at rate $1/2$ (denote this sampled hypergraph by $H^{(1)}$). By the same analysis as above, it turns out that we can show that $T^{(1)}\cup 2\cdot H^{(1)}$ will be a $(1\pm ϵ)$ sparsifier of $H$ with high probability. Now, it remains only to re-sparsify $H^{(1)}$, which we can do by repeating the same procedure. Thus, after $\log (m)$ levels of this procedure (where $m$ is the starting number of hyperedges), we can recover a sparsifier of our original hypergraph.

However, to continue our discussion, we will require the formal definition of strength, as well as some auxiliary facts about strength in hypergraphs. The key notion that [16] introduces to measure strength in hypergraphs is the notion of $k$-cuts in hypergraphs (and here we adopt the language used by [12]):

Note that when we generically refer to a $k$-cut, this refers any choice of $k\in [2..n]$. That is, we are not restricting ourselves to a single choice of $k$, but instead allowing ourselves to range over any partition of the vertex set into any number of parts.

The work of [16] established the following result regarding normalized and un-normalized $k$-cuts:

A direct consequence of the above is that in order to preserve all $k$-cuts (again, simultaneously for every $k\in [2,\mathrm{\dots }n]$) in a hypergraph $H$ to a factor $(1\pm ϵ)$, it suffices to sample each hyperedge at rate $p\ge \frac{C\log (n)}{{ϵ}^2𝚽(H)}$, and re-weight each sampled hyperedge by $1/p$.

Similar to Benczúr and Karger’s [4] approach for creating $\tilde{O}(n/{ϵ}^2)$ size graph sparsifiers, Quanrud [16] next uses this notion to define $k$-cut strengths for each hyperedge. To do this, we fix a minimum normalized $k$-cut, with $V_1,V_2,\mathrm{\dots },V_k$ denoting the partition of the vertices created by this cut. For any hyperedge crossing this minimum normalized $k$-cut, we define its strength to be exactly $𝚽(H)$. For the remaining hyperedges (i.e, those which are completely contained within the components $V_1,\mathrm{\dots }{V}_k$), their strengths are determined recursively (within their respective induced subgraphs) using the same scheme. This allows Quanrud [16] to calculate sampling rates of hyperedges, which when sampled, approximately preserve the size of every $k$-cut (for all $k\in [2,n]$). Note that just as in the graph setting, the reciprocal sum of strengths is bounded, which allows for convenient bounds on the number of low strength hyperedges:

However, the power of the strength definition extends beyond just identifying sampling rates of hyperedges, and can also be used to identify sets of vertices which can be contracted away. In particular, we can define the notion of the strength of a component, as we do below:

We will take advantage of the following fact when working with these “contracted” versions of hypergraphs:

This final claim will be very important for our algorithm. In particular, it implies that once certain components have become sufficiently strongly connected, we no longer have to worry about recovering low-strength hyperedges within the components, and can instead focus only on recovering hyperedges that cross between such components. However, before diving more into the details of this approach, we provide a more detailed re-cap of how prior work [12] recovers low-strength hyperedges generically.

With this formal notion of strength now in hand, we can formally present the algorithm discussed in the previous subsection for sparsification (essentially the framework of [4, 1, 6, 12]):

This approach is exactly what was used by [12] when designing their hypergraph sparsifiers for dynamic streams.

Indeed, their primary contribution was a linear sketch which can be used to exactly recover these low-strength hyperedges at each level of the algorithm. Recall that a linear sketch is simply a set of linear measurements of the hypergraph $H$ and thus is directly implementable as a dynamic streaming algorithm on hypergraphs, as both insertions and deletions can be modeled as linear updates. Formally, when a hypergraph on $n$ vertices is viewed as a vector in ${\{0,1\}}^{2^n}$, then a linear measurement of size $s$ is obtained by mutliplying a (possibly random) $s\times 2^n$ matrix with this vector. Inserting a hyperedge is simply a $+1$ update in the coordinate corresponding to the hyperedge, and a deletion is simply a $-1$.

With this established, we can now summarize the space complexity resulting from the linear sketching implementation of [12]:

1. 1.

   At each of the $\log (m)$ levels of sampling in the above algorithm, the linear sketch Section 1.2.1 can be used to recover the low strength edges. This is accomplished by storing $\log (m)$ independent copies of a sketch for recovering low-strength hyperedges (one copy at each level).

2. 2.

   Within each individual sketch (at a fixed level of the sampling process), there is a specific linear sketch stored for the neighborhood of the $n$ vertices.

3. 3.

   Each such vertex neighborhood sketch requires space $\tilde{O}(r/{ϵ}^2)$ bits.

In total then, this yields a linear sketch (and hence a dynamic streaming algorithm) which stores $\tilde{O}(\log (m)\cdot n\cdot r/{ϵ}^2)$ bits. Once this sketch has been stored, the algorithm can simply iteratively recover the low strength edges at each of the $\log (m)$ levels of sampling, thereby recovering a sparsifier of the original hypergraph.

At first glance, it may seem that none of these parameters from the work of [12] can be optimized in the insertion-only setting: indeed, there are $m$ hyperedges in the hypergraph initially, and thus any iterative procedure will require $\mathrm{\Omega }(\log (m))$ levels before exhausting the hypergraph if the sampling rate is $1/2$. Likewise, the $n$ vertices are fixed, and the linear sketch designed by [12] requires storing the linear sketches for each vertex. Lastly, the complexity of the sketches for each vertex cannot hope to be improved, as simply recovering a single hyperedge yields $\mathrm{\Omega }(r)$ bits of information. Thus, it may seem that one cannot build on top of this framework while achieving a space complexity that beats $O(nr\log (m))$ bits of space.

However, our first theorem shows that by cleverly merging and contracting vertices as hyperedges are inserted, we can in fact improve the space complexity. Perhaps counterintuitively, our optimization actually comes from decreasing the number of vertices (the parameter $n$ above).

To illustrate, let us consider a sequence of hyperedge insertions, and let us suppose that at some point in time, a large polynomial number of hyperedges have been inserted (say, some $n^{1002}$ hyperedges). As one might expect, if so many hyperedges have been inserted, there will naturally emerge certain components in the hypergraph which are very strongly connected. More formally, if we revisit Claim 6, we can observe that the number of hyperedges of strength , must be less than $n^{1001}$. This implies that among the $n^{1002}$ hyperedges which have been inserted, the vast majority are high strength hyperedges, and thus also define many high strength components.

As a consequence, after these hyperedges are inserted, there will be components $C\subseteq V$ for which all of the hyperedges in the component $C$ are high-strength hyperedges, and therefore do not need to be recovered in order to perform sampling by Claim 8. Algorithmically, because we are dealing with an insertion-only stream, once such a component $C$ becomes a high-strength component, it will forever remain a high-strength component, and thus, as per Claim 8, we can effectively contract this component away.

Thus, our algorithmic plan is principled: we will estimate the strength of components as hyperedges are inserted (separately for each level of the $\log (m)$ levels of sampling in the hypergraph), and whenever a component gets sufficiently large strength, we irrevocably contract the component away to a single super-vertex. We do this for the hypergraphs at each of the $\log (m)$ levels of sampling. Thus, there are two key points that must be shown:

1. 1.

   We must show that contracting these vertices saves space in our sketch.

2. 2.

   We must show that we can estimate the strength in $\tilde{O}(nr)$ bits of space in the (insertion-only) streaming setting.

In what follows, we explain how we achieve both of these goals.

First, we show that we can save space by contracting vertices. Let us consider the top level of sampling in the hypergraph. As mentioned above, as hyperedges are inserted, there will naturally become certain strongly connected components. So, let us denote one such component by $C$. Now, once this component is strong, it remains strong, and so we can be sure that we do not need to recover any hyperedges within the component, as per Claim 8. So, instead of storing the individual linear sketches ${𝒮}_v$ for the vertices $v\in C$, we instead add the sketches together, yielding ${𝒮}_C={\sum }_{v\in C}{𝒮}_v$. Note that this operation is not reversible, and we are in fact losing information about the hypergraph when we perform this addition. However, this is the same reason that we will save some space: indeed, if there are $k$ strong components, we end up storing only the linear sketches of [12] for the $k$ super-vertices, leading to a total space usage of $\tilde{O}(kr/{ϵ}^2)$ bits in a single level, as opposed to the $\tilde{O}(nr/{ϵ}^2)$ bits in [12] (note there is no $\log (m)$ here as we are only looking at the top level of sampling for now).

Unfortunately, this analysis alone is not sufficient for us to claim any space savings. Indeed, it is possible that (for instance) in the top level of sampling, there are no strong components. It follows then that we cannot add together any linear sketches, and must instead pay $\tilde{O}(nr/{ϵ}^2)$ at this level of sampling. However, this is where we now use a key bound on the number of low-strength edges Claim 6 [16]. If there are no components of strength say, greater than $n^{1000}$, then there must be fewer than $n^{1001}$ hyperedges remaining. It follows then that instead of storing this sketch of size $\tilde{O}(nr/{ϵ}^2)$ bits at each of the $\log (m)$ levels of sampling, we must only store it at $\log (n^{1001})=O(\log (n))$ levels of sampling, thereby replacing this $\log (m)$ factor with a $\log (n)$ factor.

This argument as we have presented it though is far from general and must be extrapolated to work on all instances. In particular, it is possible that at different levels of sampling, the strong components are different, and thus there is no single set of strong components that we can look at. To address this, we make the observation that the strong components form a laminar family. That is to say, the strong components at the $i+1$st level of sampling are a refinement of the strong components at the $i$th level of sampling. Thus, across all $\log (m)$ levels of sampling, the number of distinct strong components that appear is bounded by $O(n)$. Likewise, because any component of strength $\ge n^{1000}$ is merged away, by the same logic as above, each strong component must have $\le n^{1001}$ incident hyperedges (i.e., hyperedges which touch this component, as well as some other component). Thus, each component that appears will only have a non-empty neighborhood for $O(\log (n))$ levels of sampling (after which point we do not need to store anything - as the sketch of an empty neighborhood is empty).

In summary then, for each of the $O(n)$ strong component that appears, we store the sketch from [12] of size $\tilde{O}(r/{ϵ}^2)$ for $O(\log (n))$ different levels of sampling. This then yields the desired complexity of $\tilde{O}(nr/{ϵ}^2)$ bits of space for the final algorithm.

Finally, we show that we can approximately find the strong components in the hypergraph in an insertion-only stream. Fortunately, the foundation for this algorithm was presented in [12]: let us consider again the hypergraph at the top level of sampling, which we denote by $H$. Simultaneously, we consider an auxiliary hypergraph $\widehat{H}$ which is the result of sampling the hyperedges of $H$ at rate $1/n^{1000}$.

As shown in [12], it turns out the connected components in $\widehat{H}$ exactly correspond to the strong components in $H$. Thus, in the insertion-only streaming model, this admits an exceedingly simple implementation: as hyperedges arrive, we sample them at rate $1/n^{1000}$, and keep track of the components. Then, whenever a new component is formed, we simply add together the corresponding linear sketches as discussed in the previous section (i.e., merging those vertices together). Note that storing the set of connected components can be done in $\tilde{O}(n)$ bits of space, and thus across $\log (m)$ levels of sampling, requires only $\tilde{O}(n\log (m))$ bits. Because $m\le n^r$, this then yields the desired space complexity. These ideas then suffice for the insertion-only implementation.

The key observation for generalizing the bounded deletion setting is that once a component has strength $k+n^{1000}$, then after any sequence of $k$ deletions, the strength of the component remains at least $n^{1000}$. Thus, instead of adding samplers together after the components reach strength $n^{1000}$, we instead add samplers together once the strength reaches $k+n^{1000}$. Observe then that the $\log (k)$ term is a natural artifact: each strong component can have a non-empty neighborhood of incident hyperedges for $\log (k+n)$ levels of sampling, as opposed to simply $O(\log (n))$ levels of sampling, and this yields the final complexity.

We now finish with some remarks:

1. 1.

   The primary work-horse of [12] is a linear sketch known as an ${\mathrm{\ell }}_0$-sampler, and it is tempting to simply try to replace the ${\mathrm{\ell }}_0$-samplers via linear sketching in their paper with an ${\mathrm{\ell }}_0$-sampler specifically for insertion-only streams, thereby saving space. However, such a replacement would necessitate an entirely new analysis: even though the stream itself may not have deletions, the process of recovering hyperedges, merging vertices together, and more all rely on the ability to linearly add together ${\mathrm{\ell }}_0$-samplers (which causes deletions). While the aforementioned approach may work, it would not build on the existing framework. The same goes for the bounded deletion setting, where it is tempting to use ${\mathrm{\ell }}_0$-samplers defined for bounded-deletion streams (as discussed in [8]).

2. 2.

   There are several subtleties that arise in the analysis regarding the estimation of strong components, as this will never be an exact decomposition of the graph. We instead provide upper and lower bounds on the strength of the components and remaining hyperedges, and use this to facilitate our analysis. We defer a more complete description to the technical sections below.

3. 3.

   Likewise, in the bounded-deletion setting, there is considerable difficulty in optimizing the dependence on $k$ to not be ${\log }^2(k)$. Roughly speaking, this is because the $k$ dependence tries to show up in both (1) the number of levels of sampling in which a strong component has a non-empty neighborhood (a $\log (k)$ factor as described above) and (2) the support size of the ${\mathrm{\ell }}_0$-samplers that are needed when using the sketch of [12] (another factor of $\log (k)$). We use a more refined analysis along with a second round of component merging to bypass this other factor of $\log (k)$.

4. 4.

   The lower bound follows from the augmented index problem along with an argument from [8] on bounding the complexity of this problem in the bounded-deletion setting. We defer a proof to the full version of the paper.