Fully Dynamic Spectral Sparsification for Directed Hypergraphs

We briefly discuss the related work for spectral sparsification on both graphs and hypergraphs below.

In this section, we present the main ideas behind our fully dynamic algorithm for maintaining a $(1\pm \epsilon )$-spectral hypersparsifier $\tilde{H}$ of a directed hypergraph $H$. Our algorithm builds on the static algorithm of [44], which we briefly review.

The algorithm of [44] constructs $\tilde{H}$ by computing a sequence of hypergraphs $H_1,\mathrm{\dots },H_k$, where $H_1$ is a spectral hypersparsifier of $H$, $H_2$ is a spectral hypersparsifier of $H_1$, and so on, until $H_k=\tilde{H}$. Each $H_i$ is obtained via simple sampling scheme (discussed shortly) that guarantees, with high probability, $H_i$ is proportionally smaller than $H_{i-1}$. As a result, the number of iterations is bounded by $k=O(\log m)$. In constructing $H_i$ from $H_{i-1}$, the algorithm obtains two sub-hypergraphs of $H_{i-1}$: the coreset hypergraph $C_i$ and the sampled hypergraph $S_i$.

At a high level, $C_i$ consists of a sufficient number of heavy-weight hyperedges of $H_{i-1}$ (to be specified shortly). This ensures that, when hyperedges are sampled uniformly at random from the remaining hypergraph $H_{i-1}\setminus C_i$ to construct $S_i$, the resulting union $H_i:=C_i\cup S_i$ forms a spectral hypersparsifier of $H_{i-1}$. More precisely, $C_i$ is constructed as follows. For every pair $(u,v)\in V\times V$, the algorithm selects the $O({\log }^{3}m/{\epsilon }^2)$ heaviest hyperedges whose tail¹¹1In a directed hypergraph, each hyperedge $e$ is a pair $(\mathrm{t}\left(e\right),\mathrm{h}\left(e\right))$, with the tail $\mathrm{t}\left(e\right)\subseteq V$ and the head $\mathrm{h}\left(e\right)\subseteq V$ reflecting the direction of $e$. See Section 2 for further details. contains $u$ and whose head contains $v$.²²2If multiple hyperedges have equal weight, the algorithm picks them arbitrarily. These hyperedges are then added to $C_i$.

To construct $S_i$, each hyperedge in $H_{i-1}\setminus C_{i-1}$ is sampled independently with probability $1/2$, and its weight is doubled. They prove that, with high probability, this simple sampling scheme produces a $(1\pm \epsilon )$-spectral hypersparsifier $H_i=C_i\cup S_i$ of $H_{i-1}$. Moreover, with high probability, $|E(H_i)|\le 3|E(H_{i-1})|/4$ and so $k=O(\log m)$. See Figure 1(a) for an illustration of their approach.

Unfortunately, the static algorithm cannot be directly converted into an efficient dynamic algorithm. This is mostly due to the way the hypergraphs in the sequence $H_1,\mathrm{\dots },H_k$ are built on top of each other, as a single change in $H$ can propagate into $O(m)$ changes across the sequence. As an example, we explain how the removal of a hyperedge $e$ from $H_i$ can cause at least two changes in $H_{i+1}$, which can eventually lead to $O(2^k)=O(m)$ changes throughout the sequence. Assume a hyperedge $e$ is removed from $H$ and that $e$ also belongs to the coreset hypergraph $C_i$ of $H_{i-1}$. As $H_{i+1}$ is a sub-hypergraph of $H_i=C_i\cup S_i$, $e$ may also belong to $H_{i+1}$, necessitating its removal from $H_{i+1}$ as well. To maintain $C_i$ as a coreset of $H_{i-1}$, the algorithm must replace $e$ with a next heaviest hyperedge $e^{\prime }$ from $H_{i-1}\setminus C_i$. If $e^{\prime }$ is an unsampled hyperedge (i.e., belongs to $H_{i-1}\setminus S_i$), its addition to $C_i$ (and so $H_i$) may require updating $H_{i+1}$ as well: as $H_{i+1}$ is a sub-hypergraph of $H_i$, the (newly added) hyperedge $e^{\prime }$ could be heavier than some hyperedge $e^{\prime \prime }$ in $C_{i+1}$, necessitating the replacement of $e^{\prime \prime }$ in $C_{i+1}$. Thus, the removal of a hyperedge $e$ from $H_i$ can trigger at least two removals (namely, $e$ and $e^{\prime \prime }$) and one insertion (namely, $e^{\prime }$) in $H_{i+1}$. See Section 3.1 for further details.

To overcome this issue, our static algorithm deviates from that of [44] in the following way. We ensure that each hyperedge is included in at most one coreset by recursing on the sampled hypergraph $S_i$ rather than on $C_i\cup S_i$. At the same time, we add $C_i$ to the sparsifier $\tilde{H}$. i.e., we set $\tilde{H}=C_1\cup \mathrm{\cdots }\cup C_k\cup S_k$, which can be verified to remain a spectral sparsifier of $H$ (as discussed in Lemma 5). See Figure 1(b) for an illustration. Using this approach, after the deletion of $e$ from $H_i$, each hypergraph $H_{i+1},\mathrm{\dots },H_k$ in the sequence will undergo at most one change. Specifically, in the case of replacing a hyperedge $e^{\prime }$ by $e$ as in the high-recourse example above, there are two possibilities: either (1) $e^{\prime }$ does not belong to $H_{i+1}$ (i.e., it is not in the sampled hypergraph $S_i$), in which case the replacement does not affect $H_{i+1}$, or (2) $e^{\prime }$ belongs to $H_{i+1}$, in which case the update is interpreted as the removal of $e^{\prime }$ from $H_{i+1}$ (note that since $C_i$ is excluded from $H_{i+1}$, the hyperedge $e$ no longer belongs to $H_{i+1},\mathrm{\dots },H_k$). The downside of this approach is that it increases the size of $\tilde{H}$ from $O(n^2/{\epsilon }^2{\log }^3(n/\epsilon ))$ to $O(n^2/{\epsilon }^2\mathrm{poly}\left(\log m\right))$. This increase becomes noticeable only when $m$ is exponential in $n$. Even in that case, however, the size of $\tilde{H}$ stays $\mathrm{poly}\left(n\right)$, which is asymptotically much smaller than the exponential size of $H$.

To dynamize our static algorithm, we adapt an approach similar to that of [1] for graphs. We first design a decremental data structure (Algorithm 4 in Section 3.2.1), where the updates consist of only hyperedge deletions, and then use it to design a fully dynamic data structure (Algorithm 5 in Section 3.2.2) via a reduction technique.

Our decremental algorithm leverages the fact that a hyperedge deletion in $H$ causes at most one hyperedge deletion in each hypergraph in the sequence $H_1,\mathrm{\dots },H_k$. The removal of a hyperedge $e$ from $H_i=C_i\cup S_i$ is handled using a straightforward replacement scheme. If $e$ belongs to the sampled hypergraph $S_i$, then $S_i$ remains valid after the removal of $e$, in the sense that it is still a set of hyperedges sampled uniformly at random from the updated $H_i\setminus C_i$. The update procedure is more involved if $e$ belongs to the coreset hypergraph $C_i$. Recall that $e$ was added to $C_i$ through a pair $(u,v)\in V\times V$, where $u$ belongs to the tail of $e$ and $v$ belongs to the head of $e$. The replacement of $e$ is handled by removing it from all sets representing such pairs and then selecting a hyperedge with high weight that is not already in $C_i$. Since there are $O(r^2)$ such pairs, this results in an $\tilde{O}(r^2)$ update time for maintaining $H_i$. See Section 3.2.1 for more details.

To convert our decremental data structure to a fully dynamic one, we leverage the decomposability property of spectral sparsifiers: the union of spectral sparsifiers of hyperedge partitions of $H$ forms a spectral sparsifier of $H$ (see Lemma 3 for a formal statement). The main idea is to maintain a hyperedge partition $I_1,\mathrm{\dots },I_l$ of $H$ where $|E(I_i)|\le 2^i$ at any time. Deletions are handled by passing them to the respective $I_i$, whereas insertions are more difficult to handle: the data structure finds an integer $j$ and moves all the hyperedges in $I_1,\mathrm{\dots },I_{j-1}$ to $I_j$ along with the inserted hyperedge. The choice of $j$ depends on the number of insertions so far, with smaller values of $j$ (corresponding to hypergraphs considerably smaller than $H$) being chosen more frequently. On each $I_i$, we run our decremental data structure to maintain a spectral sparsifier ${\tilde{I}}_i$ of $I_i$, and upon an insertion, we reinitialize it for $I_j$. The algorithm sets $\tilde{H}={\tilde{I}}_1\cup \mathrm{\cdots }\cup {\tilde{I}}_l$, and since $k=O(\log m)$ the desired size of $\tilde{H}$ follows. See Section 3.2.2 for further discussion.

Our approach in designing a decremental data structure and extending it to a fully dynamic one is similar to recent work on dynamic sparsification for undirected hypergraphs [22, 32]. Moreover, [22] also builds on the framework of [44]. The key difference is that we adapt the directed framework of [44] (specifically, $\lambda$-coresets), whereas [22] employs their undirected framework (specifically, $t$-bundle hyperspanners, a concept also used in [32]). Both [22] and [32] rely on spanner-based techniques to bound the effective resistances in the associated graph of the hypergraph as a crucial step in enabling their simple sampling scheme. For the directed case, however, [44] shows that this translates to using coresets, which are structurally simpler than hyperspanners. This structural simplicity allows us to design relatively simpler algorithms compared to those in [22, 32].

It is noteworthy to mention the recent work of [33] that reduces directed hypergraph sparsification to undirected hypergraph sparsification. Combining this reduction with the fully dynamic undirected hypergraph sparsification result of [32] yields a dynamic algorithm for directed hypergraph sparsification with guarantees similar to ours. However, the algorithm of [32] is substantially more involved: (i) it relies on vertex-sampling steps, which our approach does not require, and (ii) it uses dynamic graph spanner constructions in a black-box manner. Moreover, it does not seem straightforward to extend their algorithm to the batch-parallel setting. In comparison, our coreset-based construction is significantly simpler and potentially more practically relevant. It readily extends to the batch-parallel setting and achieves a better and explicit polylogarithmic overhead in both sparsifier size and update time.

Lastly, in the full version of the paper (Appendix A), we show how to parallelize our data structures when $H$ undergoes batches of $k$ hyperedge deletions or additions as a single update. This discussion also explains how to adapt our fully dynamic data structure to support batch updates rather than single updates.

We start by briefly explaining the algorithm of [44], which serves as a foundation for our algorithm. Their algorithm constructs a $(1\pm \epsilon )$-spectral hypersparsifier $\tilde{H}$ of $H$ using an iterative approach: starting with $H_0=H$, each iteration $i$ computes a sub-hypergraph $H_i$ of $H_{i-1}$, until the final iteration computes $H_{i_{\text{last}}}$, where $\tilde{H}=H_{i_{\text{last}}}$.

To compute $H_i$ from $H_{i-1}$, the algorithm first obtains a $\lambda$-coreset $C_i$ of $H_{i-1}$. Roughly speaking, $C_i$ is a sub-hypergraph containing “heavyweight” hyperedges of $H_{i-1}$ and is defined as follows. The algorithm defines an ordering on hyperedges in $H$ by their weights in decreasing order. Note that this ordering naturally extends to every hypergraph $H_i$ as a sub-hypergraph of $H$. To construct $C_i$, the algorithm examines every pair $(u,v)\in V\times V$ and selects the first $\lambda$ hyperedges in the ordering (if any) that are not already in $C_i$, whose tail contains $u$ and whose head contains $v$. These hyperedges are then added to $C_i$. The second building-block of $H_{i-1}$ is the sampled hypergraph $S_i$ of $H_{i-1}$ defined as follows. The algorithm samples the non-heavy hyperedges (i.e., the ones in $H_{i-1}\setminus C_i$) with probability $1/2$ and adds them to $S_i$ while doubling their weight. Consequently, $H_i=C_i\cup S_i$. See Algorithm 1 for a pseudocode.

Having heavyweight hyperedges in $C_i$ ensures that the simple sampling scheme used for constructing $S_i$ results in $H_i=C_i\cup S_i$, which, with high probability, is a $(1\pm \epsilon )$-spectral hypersparsifier of $H_{i-1}$ [44, Lemma 4.3]. Due to the sampling scheme, $H_i$ is roughly half the size of $H_{i-1}$, which ensures the termination of the algorithm after $i_{\text{last}}=O(\log m)$ iterations. Using this sequence $H_1,\mathrm{\dots },H_{i_{\text{last}}}$ of hypergraphs, they achieve a sparsifier $\tilde{H}$ with an almost optimal size of $O(n^2/{\epsilon }^2{\log }^3(n/\epsilon ))$ [44, Theorem 1.1]. See Figure 1(a) for an illustration.

Unfortunately, employing the sequence of hypergraphs $H_1,\mathrm{\dots },H_{i_{\text{last}}}$ can result in $O(m)$ recourse (and consequently, update time) in the dynamic setting. For example, consider the removal of a hyperedge $e$ from $H$ that also belongs to the coreset $C_i$ of $H_{i-1}$. In this scenario, to ensure $C_i$ remains a $\lambda$-coreset and so $H_i=C_i\cup S_i$ remains a $(1\pm {\epsilon }_i)$-spectral hypersparsifier of $H_{i-1}$, we need to replace $e$ with another hyperedge $e^{\prime }$ from $H_{i-1}\setminus C_i$. i.e., if $e$ was added to $C_i$ through the pair $(u,v)$, hyperedge $e^{\prime }$ in $H_{i-1}\setminus C_i$ is the next hyperedge in the ordering whose tail contains $u$ and whose head contains $v$. Since $S_i$ is a set of sampled hyperedges uniformly at random, it may be the case that $e^{\prime }$ does not belong to $S_i$, and therefore to none of $H_j$ for $j>i$. Since $e^{\prime }$ is added to $H_i$ after the update (as it now belongs to $C_i$), it must be taken into account in the update of $H_{i+1}$ as a sub-hypergraph of (newly updated) $H_i$. But now, $e^{\prime }$ may be heavier than another hyperedge $e^{\prime \prime }$ in $C_{i+i}$, which necessitates the replacement of $e^{\prime \prime }$ with $e^{\prime }$. Since $e$ can be present in $C_{i+1}$ as well, this means that the deletion of $e$ from $H_i$ can result in at least $2$ changes in $H_{i+1}$, and at least $2^{k-i}=O(m)$ changes in the sequence, which is too expensive to afford.

To alleviate this issue, our static algorithm deviates from that of [44] by recursing on $S_i$ instead of $C_i\cup S_i$ as follows. At each iteration $i$, the algorithm recurses on $S_{i-1}$, adds the coreset $C_i$ of $S_{i-1}$ to $\tilde{H}$, and samples the rest, $S_{i-1}\setminus C_i$, to obtain a smaller hypergraph $S_i$ for the next iteration. More precisely, the algorithm starts with $S_0=H$ and an empty sparsifier $\tilde{H}$. In the first iteration, it computes the coreset $C_1$ of $S_0$, and adds it to $\tilde{H}$. The algorithm then samples the remaining hypergraph $S_0\setminus C_1$ to compute $S_1$ by sampling every hyperedge in $S_0\setminus C_1$ with probability $1/2$ and doubling their weight. Similar to [44], with high probability, $C_i\cup S_i$ is a $(1\pm {\epsilon }_i)$-spectral hypersparsifier of $S_{i-1}$ (Lemma 4). The algorithm then recurses on $S_1$, and so on. Thus, our algorithm adds the sequence of coresets $C_1,\mathrm{\dots },C_{i_{\text{last}}}$ to $\tilde{H}$ while recursing on the sequence of hypergraphs $S_1,\mathrm{\dots },S_{i_{\text{last}}}$. In the last iteration $i_{\text{last}}$, our algorithm adds $C_{i_{\text{last}}}$ as well as $S_{i_{\text{last}}}$ to $\tilde{H}$. See Algorithm 2 for a pseudocode and Figure 1(b) for an illustration.

This technique, which is similar to the one used in [1] for graphs, ensures that each hyperedge of $\tilde{H}$ is associated with at most one coreset. This guarantees $O(\log m)$ hyperedge deletions from $S_1,\mathrm{\dots },S_{i_{\text{last}}}$ after a hyperedge deletion in $H$ (Lemma 8), but in return, results in a $\mathrm{poly}\left(\log m\right)$ overhead in the size of $\tilde{H}$ as we include the coresets $C_1,\mathrm{\dots },C_{i_{\text{last}}}$ in $\tilde{H}$. i.e., our algorithm ensures that $\tilde{H}$ is a desired sparsifier of size $O(n^2/{\epsilon }^2\mathrm{poly}\left(\log m\right))$, which is asymptotically much smaller than $H$ even when $m$ is exponential in $n$.

The rest of this section examines the correctness of Algorithms 1 and 2. Algorithm 1, used as a subroutine of Algorithm 2, computes a coreset and a sampled hypergraph of the input hypergraph. The guarantees of Algorithm 1 are stated in the following lemma.

In this section, we dynamize our static algorithm (Algorithm 2). We first design a decremental data structure in Section 3.2.1, where $H$ undergoes only hyperedge deletions. Then, we reduce it to a fully dynamic data structure in Section 3.2.2 using the following lemma.

The fully dynamic to decremental reduction (Lemma 6) uses the batching technique [1, 22, 32] and is explained in Section 3.2.2.