Incremental Strongly Connected Components with Predictions

In this paper, we study the incremental strongly connected components (SCC) problem in the algorithms with predictions model. In this problem, the $n$ vertices $V$ of a directed graph $G$ are known a priori and the $m$ directed edges $E$ are inserted one by one. Let $e_1,\mathrm{\dots },e_m$ denote the sequence of edges and let $G_t=(V,\{e_1,\mathrm{\dots },e_t\})$ denote the graph at time $t$. The goal is to maintain the strongly connected components of $G_t$ at all times $t$. A strongly connected component $S\subseteq V$ is a maximal set of vertices of $G$ such that every pair of vertices $u,v$ are mutually reachable, that is, there is a directed path from $v$ to $u$ and vice versa.

Maintaining SCCs is a fundamental building block in many applications, e.g. social networks [9], graph processing [34], program analysis [14] and fault-tolerant networks [2].

DFS-based approaches such as Tarjan’s algorithm [31] can compute the SCCs of a static offline graph $G$ in $O(n+m)$ time. As a step towards solving the incremental SCC problem, consider the offline incremental problem. In this variant, the edge insert sequence $\sigma =e_1,e_2,\mathrm{\dots },e_m$ is known ahead of time and the goal is to design a data structure to answer queries about the SCCs of each intermediate graph $G_t$. Naively running Tarjan’s repeatedly takes $O(m^2)$ time.¹¹1We assume $m\ge n$ to simplify the runtimes. A folklore divide-and-conquer approach [28] improves upon this naive approach and solves the offline incremental SCC problem in $O(m\log m)$ total time.

To design a learned algorithm for the online incremental problem, we assume that a prediction $\widehat{\sigma }$ of the edge sequence $\sigma$ is given to the algorithm. We define the prediction error $\eta$ as the maximum error between when an edge was predicted to arrive in $\widehat{\sigma }$ and its actual arrival time in $\sigma$. To ensure this metric is well-defined, we assume that $\widehat{\sigma }$ is a permutation of $\sigma$ (we discuss this assumption further in Section 2.1). If the prediction is perfect ($\eta =0$), the problem reduces to the offline incremental variant. If the prediction is arbitrarily erroneous ($\eta =m$), the algorithm effectively gets no information about the input and the problem reduces to the worst-case model. The main challenge is to design an algorithm that smoothly interpolates between the two regimes as a function of the prediction error $\eta$.

The subproblem $[\mathrm{\ell },r]$ is rebuilt only when it lies on the path from $\mathrm{LCA}(t,\widehat{t})$ to $t$ for some edge. There are two ways this can happen:

1. 1.

   $[\mathrm{\ell },r]$ is the $\mathrm{LCA}(t,\widehat{t})$ for some pair $(t,\widehat{t})$. This occurs only if $t\le x$ and $\widehat{t}\ge x$. Since $|t-\widehat{t}|\le \eta$, this requires that $\widehat{t}\in [x,x+\eta ]$.

2. 2.

   $[\mathrm{\ell },r]$ lies strictly below the LCA. This only happens if $t$ lies inside $[\mathrm{\ell },r]$, but $\widehat{t}$ lies outside the subtree rooted at $[\mathrm{\ell },r]$; therefore, $\widehat{t}\ge r$. Since $[\mathrm{\ell },r]$ is on the path to $t$, we must have $t\le r$; since $\widehat{t}-t\le \eta$, we have that $\widehat{t}\in [r,r+\eta ]$.

$◀$

Before the next lemma, we motivate the structure of our analysis. Lemma 2 states that each subproblem is rebuilt only $O(\eta )$ times; this means that if we can bound the size of all subproblems (in other words, the total number of edges in all subproblems) we are done. Indeed, the classic analysis of the offline problem with $\eta =0$ states that each edge is in at most one subproblem at each level. This would mean that the total size of all subproblems is $O(m\log m)$; combining with Lemma 2 would give the desired $O(\eta m\log m)$ bound.

Unfortunately, this analysis is incorrect. The reason is that as $\widehat{\sigma }$ changes, what edge belongs to each subproblem changes as well. For example, according to ${\widehat{\sigma }}_0$, the endpoints of an edge $e=(u,v)$ might not be in the same SCC in $G_{m/2}$, which puts $e$ in the right child of the root. But at some later time , an edge originally predicted to arrive at $t^{\prime }>m/2$ might arrive that puts $u$ and $v$ in the same SCC in $G_{m/2}$. This would place $e$ in the left child of the root. Lemmas 3 through 5 bound how often this can happen – i.e., an edge may be a part of $O(\eta \log m)$ builds in total.

For any edge $(u,v)$ and prediction $\widehat{\sigma }$, let the combining time $C_{u,v}(\widehat{\sigma })$ be the first time in $\widehat{\sigma }$ when $u$ and $v$ are in the same SCC. If $u$ and $v$ are never in the same SCC in $\widehat{\sigma }$, then $C_{u,v}(\widehat{\sigma })$ is undefined. Lemma 3 shows that at any time $t$, an edge $(u,v)$ is only in a subproblem that contains its combining time. This lemma is useful both in analyzing the running time and proving correctness.

We argue by contradiction.

First, consider the case where $C_{u,v}({\widehat{\sigma }}_t)$ is undefined; assume by contradiction that $e$ is in a subproblem $[\mathrm{\ell },r]$ with $r\ne m$. Let $[\mathrm{\ell },r]$ be the subproblem closest to the root containing $e$ where $r\ne m$. Then $[\mathrm{\ell },r]$ was a left child – but by definition, this means that $u$ and $v$ were in the same component in the graph of the parent of $[\mathrm{\ell },r]$; a contradiction.

If $C_{u,v}({\widehat{\sigma }}_t)$ is defined, let $[\mathrm{\ell },r]$ be the subproblem in the current path closest to the root such that $e$ is an edge in $[\mathrm{\ell },r]$, but $C_{u,v}({\widehat{\sigma }}_t)\notin [\mathrm{\ell },r]$.

If , let $[{\mathrm{\ell }}_a,r_a]$ be the ancestor of $[\mathrm{\ell },r]$ with midpoint $\mathrm{\ell }$. $[{\mathrm{\ell }}_a,r_a]$ must exist since if $C_{u,v}({\widehat{\sigma }}_t)$ exists, $\mathrm{\ell }>0$. Furthermore, $[\mathrm{\ell },r]$ must be a descendant of the right child of $[{\mathrm{\ell }}_a,r_a]$. But since , $u$ and $v$ are in the same SCC in the midpoint of $[{\mathrm{\ell }}_a,r_a]$, so $e$ cannot be in the right edges of $[{\mathrm{\ell }}_a,r_a]$, contradicting that it is an edge in $[\mathrm{\ell },r]$.

If $C_{u,v}({\widehat{\sigma }}_t)>r$, let $[{\mathrm{\ell }}_a,r_a]$ be the ancestor of $[\mathrm{\ell },r]$ with midpoint $r$. $[{\mathrm{\ell }}_a,r_a]$ must exist since if $C_{u,v}({\widehat{\sigma }}_t)$ exists, . Furthermore, $[\mathrm{\ell },r]$ is a descendant of the left child of $[{\mathrm{\ell }}_a,r_a]$. But since $C_{u,v}({\widehat{\sigma }}_t)>r$, $u$ and $v$ are in different SCCs in the midpoint of $[{\mathrm{\ell }}_a,r_a]$, so $e$ cannot be in the left edges of $[{\mathrm{\ell }}_a,r_a]$, contradicting that it is an edge in $[\mathrm{\ell },r]$. $◀$

Now, we show that the error bound $\eta$ implies that the combining time of any pair of vertices cannot differ significantly as $\widehat{\sigma }$ is updated. First, we need a lemma showing that the way we update predictions does not increase the error of any edge beyond $\eta$.

We prove this by induction on $t$; it is trivially true for $t=0$.

Note that when we move from ${\widehat{\sigma }}_{t-1}$ to ${\widehat{\sigma }}_t$, we move an edge from $\widehat{t}\ge t$ to its final location $t$; all edges in positions from $t$ to $\widehat{t}-1$ move forward one, and all others remain unchanged. By definition, $\widehat{t}-t\le \eta$. The edge $e$ being moved to $t$ has $i_t(e)=i(e)$.

Any edge $e$ being moved forward one (i.e. an edge between $t$ and $\widehat{t}-1$ in ${\widehat{\sigma }}_{t-1}$) that has $i(e)\ge \widehat{t}$ is being moved closer to $i(e)$; by the inductive hypothesis the lemma holds. Now suppose an edge $e$ is being moved forward one, and $i(e)\le \widehat{t}$. For all the edges that move forward we have $i_t(e)\le \widehat{t}$. Furthermore, since $e$ has not arrived, $i(e)>t$. Combining with $\widehat{t}-t\le \eta$ implies $|i_t(e)-i(e)|\le \eta$. $◀$

Finally, Lemma 5 states that the combining time does not change significantly as we update the predictions.

Consider the graph $G^{\prime }$ constructed using all vertices in $V$, and the first $C_{u,v}({\widehat{\sigma }}_0)$ edges in ${\widehat{\sigma }}_0$; $u$ and $v$ are in the same strongly connected component in $G^{\prime }$. Let $G^{\prime \prime }$ be the graph constructed using vertices in $V$, and the first $C_{u,v}({\widehat{\sigma }}_0)+2\eta$ edges in ${\widehat{\sigma }}_t$. By Lemma 4, all edges in $G^{\prime }$ must have already arrived by time $C_{u,v}({\widehat{\sigma }}_0)+2\eta$ in ${\widehat{\sigma }}_t$, so the edges of $G^{\prime \prime }$ are a superset of the edges of $G^{\prime }$; that is, $u$ and $v$ must be in the same SCC in $G^{\prime \prime }$. Therefore, $C_{u,v}({\widehat{\sigma }}_t)\le C_{u,v}({\widehat{\sigma }}_0)+2\eta$.

Let $G^{\prime }$ be the graph at time $C_{u,v}({\widehat{\sigma }}_0)-1$ for ${\widehat{\sigma }}_0$; $u$ and $v$ are not in the same strongly connected component in $G^{\prime }$. Let $G^{\prime \prime }$ be the graph at time $C_{u,v}({\widehat{\sigma }}_0)-2\eta -1$ for ${\widehat{\sigma }}_t$. By Lemma 4, all edges in $G^{\prime \prime }$ must have already arrived by $C_{u,v}({\widehat{\sigma }}_0)-1$ in ${\widehat{\sigma }}_0$, so $G^{\prime }$ has every edge $G^{\prime \prime }$ has. This means that $u$ and $v$ are not in the same strongly connected component in $G^{\prime \prime }$, which implies that $C_{u,v}({\widehat{\sigma }}_t)\ge C_{u,v}({\widehat{\sigma }}_0)-2\eta$. $◀$

We are ready to prove Theorem 1.

Each time a node is relabeled in the Node Label Data Structure, the size of its SCC doubles; thus the total cost of all merges is $O(n\log n)$.

The cost to build a subproblem is linear in the number of vertices of ${\tilde{G}}_x$ and the number of edges ${\tilde{E}}_x$. Let $𝒮(t)$ be the set of subproblems built at time $t$. The total cost to build all subproblems is

We bound this final sum. First, any $e=(u,v)$ where $C_{u,v}({\widehat{\sigma }}_t)$ is undefined can only be in subproblems with $r=m$ by Lemma 3; there are at most $\log m$ such subproblems, and each is rebuilt $O(\eta )$ times by Lemma 2, so the total cost of these edges is $O(m\eta \log m)$.

Now suppose $C_{u,v}({\widehat{\sigma }}_t)$ is defined and $e=(u,v)$ is in $[\mathrm{\ell },r]$ built at time $t$. We show that in each level, over time, there are $O(\eta )$ such subproblems. Summing over all $\log m$ levels gives a cost of $O(\eta m\log m)$.

If $e$ is in $[\mathrm{\ell },r]$ at time $t$, by Lemma 3 we have $C_{u,v}({\widehat{\sigma }}_t)\in [\mathrm{\ell },r]$, and Lemma 5 implies that $C_{u,v}({\widehat{\sigma }}_0)\in [\mathrm{\ell }-2\eta ,r+2\eta ]$.

Consider a depth $d$, such that $r-\mathrm{\ell }\ge \eta$ for subproblems at depth $d$. There are at most five subproblems at depth $d$ that have $C_{u,v}({\widehat{\sigma }}_0)\in [\mathrm{\ell }-2\eta ,r+2\eta ]$. Each is rebuilt $O(\eta )$ times by Lemma 2; therefore, there are $O(\eta )$ subproblem builds at depth $d$ that contain $e$.

Now we consider a depth $d$ such that all subproblems have . If a subproblem $[\mathrm{\ell },r]$ in this level contains $e$, then and $C_{u,v}({\widehat{\sigma }}_0)\ge \mathrm{\ell }-2\eta >r-3\eta$, which imply $\mathrm{\ell }>C_{u,v}({\widehat{\sigma }}_0)-3\eta$ and , respectively. Then if $e^{\prime }$ causes the subproblem $[\mathrm{\ell },r]$ to be rebuilt, by Lemma 2, $e^{\prime }$ was predicted to arrive at time steps $[\mathrm{\ell },r+\eta ]$ in $\widehat{\sigma }$. The length of this interval is $O(\eta )$, which means that $e$ has been involved in $O(\eta )$ rebuilds at depth $d$ over time. $◀$

We compare against the state-of-the-art heuristic for the problem: ${\text{IncSCC}}^{+}$ [12]. In ${\text{IncSCC}}^{+}$, the algorithm maintains a topological ordering of the nodes at all times, that is, each node $v$ in the current (possibly contracted) graph is assigned a topological rank $r(v)$ such that for every arc $(u,u^{\prime })$ between distinct SCCs, we have $r(u)>r(u^{\prime })$. When a new arc $(v,w)$ is added in the “wrong” direction, i.e., , the algorithm identifies potentially affected nodes by running forward and backward depth-first searches from $w$ and $v$, respectively. It then applies Tarjan’s algorithm on the affected nodes to determine whether a new cycle has been formed. We were not able to obtain the authors’ original code, so we implemented our own version of their algorithm. In this implementation, when a cycle is formed, we merge the SCCs in the cycle into a new SCC, and run DFS on the whole graph to find the new topological ordering.

We also made an optimized version (IncSCC+ optimized) with two modifications. First, we skip the final run of Tarjan’s algorithm, as cycle formation can be detected immediately from the affected nodes. Second, after a node is contracted, in order to find a new valid topological ordering, we only rearrange the affected nodes. These factors do not change the main ideas of the algorithm, but lead to a noticeable performance improvement in practice. In our tests, we compare to both ${\text{IncSCC}}^{+}$ implementations.

We also include the performance of the offline incremental algorithm from Section 2.2, which has access to the entire edge arrival sequence ahead of time.

Our datasets are from SNAP⁴⁴4https://snap.stanford.edu/data/ [18]. The sx-superuser-c2a and sx-askubuntu datasets are graphs based on two stackexchange forums; a link represents one user posting an answer or comment on another user’s question or answer. These two are temporal, i.e., links are ordered based on the time the comments occurred. The other dataset used, Slashdot0811, is not temporal; edges arrive in random order. Each edge represents a user who tagged another as “friend” or “foe.” The number of vertices and number of unique edges for each of these datasets is given in Table 1.

Our implementations are in Python. Our experiments were run on an Ubuntu Linux machine with a 2.8GHz i7-1165G7 Intel CPU with 32GB RAM.

We parameterize how to generate predictions with a variable $S$, which is roughly the standard deviation of the error. For each value of $S$, we construct a perturbed edge sequence from the original ordering as follows. We traverse the edges in their original order, and for each edge, we sample an offset from a normal distribution with mean $0$ and standard deviation $S$. The target index is set to the current index plus this offset. If both the current and target indices have not yet been modified, we swap the edges at these positions; otherwise, the edge remains fixed.

After processing all edges, we measure the prediction quality using two metrics relative to the original sequence: the average prediction error (${\eta }_{\text{avg}}$) and the maximum prediction error (${\eta }_{\text{max}}$). For each $S\in \{0,10,20,\mathrm{\dots }\}$, we generate 10 independent perturbed sequences using the procedure described above. Each sequence yields its own average and maximum error values. We then run the algorithm on each sequence and report the average runtime and error across the 10 runs. In the plots, ${\eta }_{\text{avg}}$ is the mean of the 10 average-error values and ${\eta }_{\text{max}}$ is the mean of the 10 maximum-error values.

We include the plot for sx-askubuntu in Figure 2, and include the results for the remaining datasets in the full version of the paper. With sufficiently accurate predictions, our algorithm gives significantly improved performance over both versions of ${\text{IncSCC}}^{+}$. The experiments show our performance grows roughly linearly with the error; in fact it grows linearly with both the ${\eta }_{\text{avg}}$ and ${\eta }_{\text{max}}$ (our theoretical analysis bounds performance only in terms of ${\eta }_{\text{max}}$).

Table 1 summarizes further results, including the largest average and maximum $\eta$ for which our algorithm improves on optimized ${\text{IncSCC}}^{+}$.

In Table 1, we also compare our algorithm with perfect predictions to the offline incremental algorithm from Section 2.2. While both algorithms are given the entire edge sequence, our algorithm can adapt to errors on-the-fly, while the offline algorithm is static. Despite this overhead, our running time is not only comparable but in fact slightly better than the offline algorithm. This demonstrates that our method is lightweight, while still allowing for potential error.