Parallel Strong Connectivity Based on Faster Reachability

Letong Wang

UC Riverside

Xiaojun Dong

UC Riverside

Yan Gu

UC Riverside

Yihan Sun

UC Riverside

Computing strongly connected components (SCC) is among the most fundamental problems in graph processing.
As today's real-world graphs are getting larger and larger, parallel SCC is increasingly important.
SCC is challenging in the parallel setting and is particularly hard on large-diameter graphs.

Many existing parallel SCC implementations can be even slower than Tarjan's sequential algorithm on large-diameter graphs.

To tackle this challenge, we propose an efficient parallel SCC implementation using a new parallel reachability algorithm.
Our solution is based on a novel idea referred to as vertical granularity control (VGC).
It breaks the synchronization barriers to increase parallelism and hide scheduling overhead.
To use VGC in our SCC algorithm, we also design an efficient data structure called the parallel hash bag.
It uses parallel dynamic resizing to avoid redundant work in maintaining frontiers (vertices processed in a round).

We implement the parallel SCC algorithm by Blelloch et al. (J. ACM, 2020) using our new parallel reachability algorithm.
We compare our implementation to the state-of-the-art systems, including , , , and our highly optimized Tarjan's (sequential) algorithm, on 18 graphs, including social, web, , and lattice graphs.
On a machine with 96 cores, our implementation is the fastest on 16 out of 18 graphs.
On average (geometric means) over all graphs, our SCC is 6.0$\times$ faster than the best previous parallel code (), 12.8$\times$ faster than Tarjan's sequential algorithms, and 2.7$\times$ faster than the best existing implementation on each graph.

We believe that our techniques are of independent interest. We also apply our parallel hash bag and VGC scheme to other graph problems, including connectivity and least-element lists (LE-lists). Our implementations improve the performance of the state-of-the-art parallel implementations for these two problems.

<concept_desc>Theory of computation Shared memory algorithms</concept_desc>
<concept_desc>Theory of computation Graph algorithms analysis</concept_desc>

[500]Theory of computation Shared memory algorithms
[500]Theory of computation Graph algorithms analysis

§ IMPLEMENTATION DETAILS

§ EXPERIMENTS

We run our experiments on a 96-core (192 hyperthreads) machine with four Intel Xeon Gold 6252 CPUs and 1.5 TB of main memory.
We implemented all algorithms in C++ using  <cit.> for fork-join parallelism and parallel primitives (e.g., sorting).
We use  for parallel tests to interleave the memory pages across CPUs in a round-robin fashion.
All reported numbers are the average running time of the last five out of six runs.

We use $\tau=2^9$ in all tests except for those in <ref> which studies the choice of $\tau$.
We tested 18 directed graphs, including social networks, web graphs,  graphs, and lattice graphs.
All social, web, and  graphs are real-world graphs, with up to 3.6 billion vertices and up to 128 billion edges.
The lattice graphs are generated by a similar model in <cit.>,
which uses SCC to study the percolation on isotropically directed lattices.
Basic information on the graphs is given in <ref>.

For social graphs, we use LiveJournal (LJ) <cit.> and Twitter (TW) <cit.>.

For web graphs <cit.>, we use sd-arc (SD), ClueWeb (CW), Hyperlink12 (HL12) and Hyperlink14 (HL14).
graphs are widely used in machine learning algorithms <cit.>.
In  graphs, each vertex is a multi-dimensional data point and has $k$ edges pointing to its $k$-nearest neighbors (excluding itself).
We use Household with $k=5$ (HH5) <cit.>, Chemical with $k=5$ (CH5) <cit.>, GeoLife with $k=2,5,10,15,20$ (GL2, GL5, GL10, GL15, GL20) <cit.>, and Cosmo50 with $k=5$ (COS5) <cit.>.
We also created four lattice graphs <cit.>,
including two $10^4 \times 10^4$ 2D-lattices (SQR and SQR'),
and two $10^3 \times 10^4$ 2D-lattices (REC and REC').
Each row and column in the lattice graphs are circular.
In SQR and REC, for each vertex $u$ and its adjacent vertex $v$, we add a directed edge from $u$ to $v$ with probability 0.5,
and from $v$ to $u$ otherwise, then remove duplicate edges.
In SQR' and REC', for each vertex $u$ and each of its adjacent vertex $v$, we create an edge from $u$ to $v$ with probability 0.3, and from $v$ to $u$ with probability 0.3, and create no edge with probability 0.4, then remove duplicate edges.

To test our connectivity and LE-lists algorithms, we symmetrize all 18 directed graphs and use 4 more real-world undirected graphs, com-orkut (OK) <cit.>, Friendster (FT) <cit.>, RoadUSA (USA) <cit.>, and Germany (GE) <cit.>.
Graph details are given in <ref>.

We call the social and web graphs low-diameter graphs as they usually have low diameters (roughly polylogarithmic in $n$). We call the  and lattice graphs large-diameter graphs as their diameters are large (roughly $\Theta(\sqrt{n})$). When comparing the average running times across multiple graphs, we always use the geometric mean.

Baseline Algorithms. We call all existing algorithms that we compare to the baselines.

We compare the number of SCCs and the largest SCC size reported by each algorithm with  to verify correctness.
For SCC, we compare to  <cit.>,  <cit.>, and  <cit.>.

also implements the BGSS algorithm, so we also compare our breakdown and sequential running times with .
We also implemented and compared to Tarjan's sequential SCC algorithm <cit.>.
We call it .

On six graphs, 's results are off by 1, noted with “?” in <ref>.

For all the eleven graphs that 's can run out, they are either has wrong number of SCCs, noted as “?”;
or has wrong lagest SCC size, noted with “!” in <ref>.

(We communicated with the authors but could not correct it.)
and  do not support CW, HL12, and HL14 because they have more than $2^{32}$ edges.
For connectivity, we apply our two techniques to the LDD-UF-JTB algorithm in  <cit.> and compare it to the original implementation
in . For s, we compare to , which is
the only public parallel LE-lists implementation to the best of our knowledge.

We first summarize the overall performance of the algorithms and scalability tests in <ref>.

Next, we show some experimental studies on performance breakdown in <ref>, and an in-depth study of  in <ref>.

Finally, we provide a brief summary of our experimental results for connectivity and LE-lists in <ref>.

figureSelf-relative speedup for our algorithms and the algorithms in GBBS.Much of our performance improvement comes from better parallelism.

§.§ Overall Performance

We show the running times in <ref> and a heatmap in <ref>.
We mark the parallel running times slower than the sequential algorithms in red in <ref>.

Our implementation is almost always the fastest except on SD and CH5.

On CH5, we are 23% slower than .

CH5 has a very large diameter (4000+) compared to its small size (4M vertices), and none of the parallel implementations outperform .

On SD, we are only 4% slower than  with $\tau=2^9$. SD is one of the graphs that are dense and potentially has good parallelism, and thus may prefer smaller $\tau$.
As we will show in <ref>, using $\tau\le 2^8$ will achieve a better performance than all existing implementations on SD, but we keep the results in <ref> all using $\tau=512$ for simplicity.
The highlighted columns in <ref> show the speedup of our algorithms to the best baseline (including ) on each graph.
Compared to the best baseline, we are up to 10.2$\times$ faster and 3.1$\times$ faster on average.

All the implementations perform favorably on all low-diameter graphs (5–317$\times$ faster than ).
Conceptually, all parallel implementations first use BFS-like algorithms to find the largest SCC.

On all but one low-diameter graph, the largest SCC contains more than 50% vertices.
Therefore, using a parallel BFS (with optimizations such as dense modes) gives decent performance.
Even so, using s and  still gives good performance on low-diameter graphs, and
we are faster (up to 3.8$\times$) than the best baseline on all but one graphs.

One interesting finding is that on TW, our implementation, , and
are faster than  even running sequentially.
Similar trends (running the parallel algorithm sequentially is faster than the classic sequential algorithm) have been observed in other BFS-like graph algorithms <cit.>.
This is mostly due to the dense-mode optimization as described in <ref>.2.
When the frontier size is large, triggering the dense mode can skip many edges, so the number of visited edges can be fewer than $\Theta(m)$ as in the standard sequential solution.
Another reason is that our implementation (and 's) using BFS
is more I/O-friendly than Tarjan's DFS-based algorithm.

In dense mode, every vertex in $V$ that has not been visited explores its in-coming neighbors. Once they find a neighbor in the current frontier, it will mark itself as visited, put itself to the next frontier, and stop exploring its remaining neighbors.

Our algorithm has dominating advantages on large-diameter graphs.
On  and lattice graphs, existing parallel implementations are slower than the sequential algorithms in 24 out of 36 tests.
If we take the average time of the baseline parallel algorithms for  and lattice graphs,
all of them are slower than  (see the “MEAN” columns in <ref>).
In comparison, our implementation is 5.3$\times$ better than  on  graphs and 9.1$\times$  better on lattice graphs.

We believe the high performance is from good parallelism.
We study the scalability of our algorithm in the next paragraph.

Scalability Tests.

We show the speedup of four algorithms (ours, , , ) over the sequential Tajan's algorithm on six representative graphs in <ref>. We vary the number of processors from 1 to 96h (192 hyperthreads). The red horizontal dot lines represent the running time of Tarjan's algorithm (), above which means faster than Tarjan's algorithm.

On low-diameter graphs (TW, SD, and CW), all algorithms show reasonably good speedup.
On large-diameter graphs (SQR', GL5, and COS5), our algorithm achieves significantly better scalability than the baselines.
Our algorithm is the only one that achieves almost linear speedup on all the six graphs.

For all the other algorithms, their performance stops increasing (dropped or flattened) with more than $24$ threads on one or more graphs.
shows good performance on SD, and has better performance than our algorithm especially on a small number of threads.
However,  does not scale well to more processors on most of the graphs.

We also show the self-speedup of our algorithms on six graphs in <ref>. We vary the number of processors from 1 to 96h (192 hyperthreads). Due to page limitation, we do not show the curves for all graphs, but the self-speedup on all graphs on 96h (192 hyperthreads) is given in <ref>.
Our self-speedup is more than 35 except for some very small graphs.

This indicates that high parallelism is a crucial factor contributing to the high performance of our code.
Compared to , the fastest previous parallel SCC implementation, our self-speedup is 1.2–32$\times$  better.

With limited parallelism,  can be slower than  on 8 out of 14 large-diameter graphs—the BGSS SCC algorithm has $O(m\log n)$ work compared to $O(m)$ of Tarjan's sequential algorithm, so with poor self-speedup, the parallelism cannot make up the factor of $O(\log n)$ loss in the total work.

We believe that our good performance comes from using s (saving work on processing sparse frontiers)
and  (reducing the number of rounds in reachability searches and improving parallelism).
We will discuss more details by comparing the performance breakdown with  in <ref>, and studying the benefit brought up by  in <ref>.

§.§ Performance Breakdown

To better understand the performance of our algorithm, we compare the performance breakdown with  in <ref> since
is also based on the BGSS algorithm and we have similar framework.
We compare the running time in six parts (see <ref>):
1) Trimming: trimming vertices with no in- or out-degrees; 2) First SCC: finding the first SCC using two single-reachability searches; 3) Multi-search: all multi-reachability searches;
4) Hash Table Resizing: resizing the hash table storing reachability pairs; 5) Labeling and Others: assigning labels to vertices and other costs.
We show the breakdown figure for all graphs in <ref>.
We tested three versions of our algorithm: the plain version uses parallel s without ,
the “VGC1” version enables  in single-reachability to find the first SCC,
and the “final” version fully enables  in both single- and multi-reachability search.
We note that some graphs requires more time on First-SCC while the others spent more time on Multi-search
because of different graph patterns, which is indicated by the value of $|SCC_1|\%$ as shown in <ref>.

One straightforward improvement of our algorithm is from our better heuristic to estimate the hash table size (see details in <ref>), which avoids frequent size predicting and hash table resizing.
This can be seen by comparing the time of “hash table resizing” (green bars) for  and our versions.
This optimization saves much time on almost all graphs.
In the following, we use the breakdown results to illustrate the performance improvement from our two main techniques: the
and VGC.

Even our plain version is better than  on almost all graphs for two reasons.

First, using parallel s saves time in maintaining the frontiers by avoiding the edge-revisiting scheme.
has to visit the frontiers' edges twice to compute the next frontier, but such redundant work is avoided using parallel hash bags.
This can be seen by comparing the time of “first-SCC” (red bars) on SQR and REC, and “multi-search” (green bars) for TW, GL10, SQR', etc.
Another saving is from our better heuristic to estimate the hash table size (see details in <ref>), which avoids frequent hash table resizing. This can be seen by comparing the time of “hash table resizing” (orange bars) for  and our plain version.
This optimization saves much time on almost all graphs.

Evaluating s.
Parallel s improve the performance by maintaining the frontiers without the edge-revisiting scheme.

Note that both our algorithm and  use the BGSS algorithm and perform the same computation in each round, but  uses edge-revisiting and our algorithm avoids that by using the .
Therefore, we compare our plain version (i.e., disabling VGC) with  to evaluate the improvement from s,
because the major difference between them is the use of s.
We also exclude the hash table resizing time (the green bars) for fair comparison.
On all but one graphs, using s greatly improve the performance in single- and/or multi-reachabilty searches.
Comparing the total running time of reachability searches (red and blue bars), our algorithm is up to 4$\times$ faster than  (2$\times$ faster on average),
and the major improvement is from s.

Evaluating VGC. On top of our plain version,  improves the performance on almost all graphs.
Note that for low-diameter graphs, since the number of needed rounds is small, there is sufficient parallelism to explore.
Therefore, using  does not improve the performance too much.
As mentioned, on SD, the performance drops slightly using local search with $\tau=2^9$, but
using smaller values of $\tau$ can still improve the performance (see <ref>).
To keep the parameter setting simple, we still report the numbers with $\tau=2^9$ in <ref>.
The large-diameter graphs with the largest SCC as 50% of the graph (e.g., COS5, REC, and SQR) greatly benefit from VGC1 (using  in the single-reachability search to find the first SCC). Comparing “first-SCC” of plain and VGC1,  makes the performance 2.2–17$\times$ faster in the single-reachability search on COS5, SQR, and REC.
All the other large-diameter graphs get significant improvement from VGC1 to final (using  also in multi-reachability searches).

For all large-diameter graphs, the “multi-search” time in final is smaller than that in VGC1 (1.43–14.7$\times$ improvement).

As we will show in <ref>, this is because  reduces the number of rounds in reachability searches by 3–200$\times$.

In summary, comparing our plain version with , we can see that  and our heuristic on hash table resizing improves the performance over  by about 1.5–4.3$\times$.
Comparing plain with VGC1 and final, we can see that VGC improves the performance in both single- and multi-reachability queries by up to 14.7$\times$.

§.§ In-depth Performance Study of

Reduced Number of Rounds.
We study the improvement of
by reporting the number of rounds in the reachability searches with or without  (see <ref>).

In a given graph, for all single- and multi-reachability searches in the SCC algorithm, we record the number of rounds $y$ needed in plain BFS
and the number of rounds $x$ with  enabled.
We then plot all such points $(x,y)$ on a 2D plane to illustrate the effectiveness of local search, shown in <ref>.

We also report the average ratio of $y/x$ on the top of each figure.
The conceptual “slope” indicated by the points illustrates the factor in the reduction of the number of rounds by using local search.
For most of the graphs, especially the  graphs, thousands of rounds were needed in each multi-reachability search using BFS.
With , the number of rounds is mostly within 100.
Even for the cases where BFS only needs a few (10–100) rounds,  still reduces the number of rounds
to be within 10 rounds (e.g., LJ, TW, COS5, SQR', REC').

On all graphs, the number of rounds is reduced by 3–200$\times$. As a result, the scheduling and synchronization overhead is greatly reduced.

On SQR, the big improvement is in the first single-source search, where the number of rounds reduces from $10^4$ to about 100.
For the multi-searches, the number of rounds always reduces to one since BFS also just needs a few rounds.
This is consistent with the result in <ref>, where GL5 benefit mostly from the local search on multi-reachability queries, and SQR benefit mostly from adding local search to the first round.

Hash Bag Study. To understand performance gain from hash bags, we compare the sequential running time of our SCC implementation with . This is because we use a similar high-level framework as , and the sequential running time reflects the work of each algorithm. On all large-diameter graphs (where dense mode is hardly used), our sequential time is much faster than theirs (up to more than 2x). We believe this is mostly due to the use of hash bags—we do not need to process the frontier multiple times.
We note that this is not a direct measurement as it is also affected by other techniques such as local search, but conceptually local search should not make much difference in work.

Choice of Parameter $\tau$. To understand the impact of $\tau$ values on performance, we record the speedup over our plain version (i.e., no VGC) with different values of $\tau=1$ to $2^{17}$, and under different number of processors from 96h (192 hyperthreads) to $4$. For page limitation, we show six graphs in <ref> (at least one in each graph type). All the other graphs showed similar trends as one of the six examples.
We start from the curves of 192 hyperthreads on different graphs.
On all graphs except for LJ, TW and SD, we observe improvement as long as  is used (compared to plain BFS where $\tau=1$) for any $1<\tau \le 2^{16}$.
Overall, the performance is not sensitive (and is always better than $\tau=1$) in a large parameter space $2^6\le \tau\le 2^{12}$ on almost all graphs.
Based on the results, we set $\tau=2^9$ as it gives the best overall performance across all graphs.
Using $\tau=2^9$, SD is the only graph that has worse performance than $\tau=1$. We note that SD still benefits from  with $\tau\le 2^8$.
Note that using larger $\tau$ suppresses parallelism, and for dense graphs with sufficient parallelism, a smaller $\tau$ may perform better.

Although we choose the best parameter by using experiments on 96h, we also test how different numbers of processors $P$ affect the choices of $\tau$.
Interestingly, the trends are usually similar regardless of the number of threads used.

With a smaller value of $P$, the performance is less sensitive to the $\tau$ value.

This is because $\tau$ trades off between scheduling overhead and load balancing,
and both affect the performance more when $P$ is large.

We believe that an interesting future work is to set $\tau$ dynamically to achieve the best benefit from , possibly based on the sparseness of the graph and the potential parallelism, e.g.,
the edge-vertex ratio $m/n$, the number of processors $P$, or the frontier size.

§.§ Experiments on Connectivity and LE-Lists

The running time of Connectivity and s are shown in (<ref>) and full discussions for connectivity and s are shown below.

Our CC algorithm is based on the LDD-Union-Find algorithm in  <cit.> (integrated in ),
using hash bags and the local search optimization.
On low-diameter scale-free networks, the most costly rounds are in the dense mode, so our CC has very similar performance as .
On large-diameter graphs, our CC is 1.98$\times$ faster than GBBS on average, mainly due to our local search optimization.
Our CC is faster than GBBS on 20 out of 24 graphs.

For s, we implemented the parallel BGSS s algorithm <cit.>.
Although s have numerous applications, we note that there was no previous parallel implementation,
mainly due to the lack of a suitable bag-like data structure.
Using our parallel hash bag in <ref>, our parallel s implementation can achieve 62$\times$ speedup on average on scale-free graphs compared to the sequential Cohen's algorithm <cit.>.
The speedup for large-diameter is lower (15.4x), since local search optimizations are not applied here.
Our implementation is the first parallel implementation for s.

§.§ Experiments on Connectivity and LE-Lists

Social graphs represent users and friendship on social networks.
Web graphs represent webpages or hosts and their hyperlinks.
Road networks represents roads and their connections on maps.
$k$-NN graphs are widely used in machine learning, such as graph clustering <cit.>, manifold learning <cit.>, outlier detection <cit.>, and proximity search <cit.>.
Each node is multi-dimensional data point from machine learning datasets <cit.>, and has $k$ edges to its $k$-nearest neighbors (excluding itself).
For synthetic graphs, we create four lattice graphs and two chains with different lengths.

When creating 2D lattices (SQR and REC),
we add directed edges from $u$ to each of its neighbor $v$ with probability 0.5,
and from $v$ to $u$ with the same probability. We then remove duplicate edges.
We also created sampled lattice graphs (SQR' and REC'),
where we add directed edges from $u$ to each of its neighbors $v$ with probability $p=0.3$, and from $v$ to $u$ with probability $0.3$.

§ RELATED WORK

Parallel SCC has been widely studied.
Prior to the BGSS algorithm based on (multi-)reachability searches, there had been other approaches.
The first type of approach is based on parallelizing DFS <cit.>.
However, since DFS is inherently sequential <cit.> and hard to be parallelized,

these algorithms are shown to be slower than existing reachability-based solutions  <cit.>.

Another widely-adopted approach is based on single-reachability search (aka. the forward-backward search, or Fw-Bw) <cit.>.
However, Fw-Bw does not provide sufficient parallelism to find all SCCs.
Hence, these systems only use Fw-Bw to find large SCCs
and use other techniques such as coloring and trimming to find small SCCs, which do not have good theoretical guarantees.
For this type of approach, we compared the two newest ones with the released code:  <cit.> and  <cit.>.

They perform well on graphs with a small diameter and a large $\mathit{SCC}_1$ ($\mathit{SCC}_1$ is the largest SCC in the graph),
but do not work well on graphs with a large diameter or a small $\mathit{SCC}_1$ (e.g., the  and lattice graphs in our tests).

Parallel SCC has also been studied on other platforms such as GPUs and distributed systems.
Comparing the wall-clock running times reported in the papers, it seems that shared-memory algorithms are much faster, but we note that different platforms have their own use cases.
On GPUs, many implementations are proposed (e.g., <cit.>).

Because of the limited size of GPU memory, we are not aware of existing GPU algorithms tested on graphs with more than 1 billion edges.

For some large graphs used in this paper, processing them on GPUs seems difficult.

Parallel SCC algorithms were also studied in the distributed settings (e.g., <cit.>).
Most of them also use single-reachability searches and coloring, and Yan et al.'s algorithm <cit.> uses multi-reachability searches.

Although we tested the largest publicly-available graph (HL12) in this paper, we acknowledge that some private graphs (e.g., Google's graph and brain connectome) are larger and need to be processed on distributed systems.

Parallel SCC has also been studied on other platforms such as GPUs <cit.> and distributed systems <cit.>.
Comparing the wall-clock running times reported in the papers, it seems that shared-memory algorithms are much faster, but we note that different platforms have their own use cases.

Related Work of Parallel Hash Bag. There exist other variants of hash tables designed for parallel algorithms <cit.>.
The parallel bag <cit.> supports similar interfaces as our , but uses a very different design.

Parallel bags are organized using pointers, causing additional cache misses in practice.
Our  uses flat arrays and is practical and I/O-friendly.

The $k$-level hash table designed for NVRAMs <cit.> requires allocating memory when resizing, while one of the goals of s is to avoid explicit resizing.
Our work is also the first to formalize the interface of maintaining frontiers in parallel reachability search
and proposes a practical data structure (the ) with theoretical analysis.

Parallel BFS. There exist other implementations of parallel BFS, and some of them also consider reducing synchronization costs <cit.>. However, these implementations only consider a single source, and we are unaware of how to directly apply to the multi-reachability search needed in SCC.

DFS based implementations.  DFS is considered hard to parallilize <cit.>. Some novel parallel randomized DFS algorithms <cit.> show DFS-based algorithms can be parallelized more directly, which have $O(p(n+m))$ work, where $p$ is the number of processors. Low and Gavin <cit.> proposed a concurrent DFS algorithm based on Tarjan's algorithm, which has $O(n^2)$ work. As shown in  <cit.>,  <cit.> is more than 16 times faster than UFSCC <cit.>, so we do not compare our algorithm with these DFS based implementations but with  <cit.>.

Reachability based implementations. Most parallel SCC implementations use the idea of single-reachability (refered as Forward-Backward search in some papers) proposed in <cit.>. Usually, they use single-reachability search to find large SCCs, and use other algorithms, such as coloring and trimming <cit.>, to deal with small SCCs.

For multi-core machines, Hone et al. <cit.> explore the small-world property (low-diameter) for social networks and use recursive trimming and coloring algorithms to deal with small SCCs, which inspire many other implementations. Xu et al <cit.> design parallel SCC algorithm based on generalized rough sets theory, on four-core machine, it performs similar to  <cit.>.  <cit.> also explore the low-diameter property, and gain better performance than  <cit.>. So we do not compare with Hong <cit.> in our paper but with  <cit.>.

For distributed machines, Mclendon Iii et al. <cit.> implemented single-reachability search algorithms on distributed systems and proposed the trimming technique.  Barnat J et al. <cit.> exploy OWCTY elimination and use FW-BW and coloring algorithms, known as OBF algorithm.  Google's Pregel <cit.> proposed the vertice-centric computing paradigm for distributed systems. Two Pregel SCC implementations are proposed <cit.>. Note that Yan et al <cit.> proposed a multi-labeling algorithm, which is similar to the multi-reachability search in our paper, but multi-labeling is designed to increase the probability finding the largest SCC, and does not good theoretical work guarantee.

There are also lots of parallel implementations on GPUs <cit.>, which are able to get speedup on synthetic graphs. Due to the limitation of VRAM, the largest graph tested on GPUs is LiveJournal (LJ) <cit.>. Besides implementations on common architectures, there is also an implementation for external memory systems <cit.>.

§ DISCUSSIONS AND FUTURE WORK

In this paper, we show that using faster algorithms on reachability queries can significantly accelerate the performance of SCC and related algorithms, especially for large-diameter graphs.

We tested our SCC algorithm on large-scale graphs with up to hundreds of billions of edges.
On average, our SCC algorithm is 6.0$\times$ faster than the best previous parallel implementation (), 8.1$\times$ faster than , and 12.9$\times$ faster than Tarjan's sequential algorithms.

We believe that the two key techniques in this paper, the hash bag and vertical granularity control, are general and of independent interest.
In this paper, we apply them to graph connectivity and LE-lists.
The experimental results show that they lead to improved performance than prior work.
We believe that they also apply to many other applications.

Hash bags are used to maintain frontiers (a subset of vertices) in graph algorithms.
Many state-of-the-art graph libraries (e.g.,  <cit.> and Ligra <cit.>) use the abstract data type (ADT) called VertexSubset to maintain frontiers
on many graph algorithms.

Hash bags can be used to implement this ADT by replacing the current data structure (fixed-size array).
With careful engineering, we believe hash bags can potentially improve the performance of these implementations. We leave this as future work.

The high-level idea of  applies to traversal-based graph algorithms,
such as BFS, algorithms for connectivity, biconnectity, single source shortest paths (SSSP), and some others in <cit.>.
can potentially accelerate them on large-diameter graphs.
Our specific “local-search” idea does not directly apply as is.
When the traversing order does not matter (e,g., reachability-based algorithms), local search can be applied directly.
In a recent paper, we apply local search to graph biconnectivity <cit.>, which improved the overall performance by up to 4$\times$ on a variety of graphs.
For some distance-based algorithms, we need additional designs on top of local-search,
such as supporting revisiting certain vertices (e.g., in BFS, SSSP, LE-lists) for relaxation,
or some wake-up strategies to find the next frontier (e.g., in $k$-core).
We believe that this is an interesting research direction, and plan to explore it in the future.

§ ACKNOWLEDGEMENT

This work is supported by NSF grants CCF-2103483, CCF-2238358, IIS-2227669, and UCR Regents Faculty Fellowships.
We thank anonymous reviewers for the useful feedbacks.

Due to the space limit, we defer the correctness proof of our algorithm for BCC here.
Throughout the analysis we assume each connected component has more than one vertex since otherwise it is a trivial case.

To start with, we will show two useful conclusions (<ref> and <ref>) for biconnected components that will be used in proving the correctness of our algorithm.

Given a graph $G$, vertices in each BCC $C\subseteq V$ must also be connected in an arbitrary spanning forest $F$ for $G$.

First of all, a BCC must be connected, so they can only be in one spanning tree $T$ in $F$.

Assume to the contrary that $C$ has at least two disconnected components (each is connected) in $T$, and let the shallowest nodes (closest to the root) for both components as $u$ and $v$.
There are two possible positions for $u$ and $v$ in the spanning tree $T$.
The first case is that, neither $u$ or $v$ is the ancestor of the other.
In this case, based on our assumption, there exists at least one path from $u$ to $v$ using vertices in $C$, but not any vertices on the tree path from $u$ to $v$.
We show that the nodes on the tree path from $u$ to $v$ is also biconnected to $u$.
Let $w$ be the parent of $u$ and on the tree path from $u$ to $v$.
We now show that there are two disjoint paths that connects $w$ and $v$: the tree path between $w$ and $v$ that uses no intermediate nodes from $C$, and the path from $w$ to $u$ then to $v$, only using intermediate nodes from $C$.
Hence, $w$ and $v$ are biconnected and $w\in C$, which leads to a contradiction that $u$ and $v$ are the closest nodes to the root in this BCC.

The second case can be proved similarly.
WLOG assume $u$ is $v$'s ancestor, then we look at $v$'s parent $w$, and we can show that there are at least two paths from $w$ to the nearest vertex in $u$'s component, one using the tree path while the other using vertices in $C$.
Hence, $w$ and $u$ are biconnected, which leads to a contradiction.

Since each BCC must be a connected component in one spanning tree in $F$, in the BC-labeling, the unique shallowest vertex (closest to the spanning tree root) is the component head, and the rest of the vertices all have the same label for this BCC.
Using a similar argument in the proof, we can show that:

Each non-root component head is an articulation point.

This is because each connected component $C$ has at least two vertices, so removing the component head $h$ disconnects $h$'s parent and $h$'s child in $C$.
If not, then there are two disjoint paths between these two nodes, so $h$'s parent is also in $C$, leading to a contradiction.

Since each BCC is connected for any spanning tree, we now define a useful concept: the subset tree.
For a given BCC $C\subseteq V$, for a vertex $u \in C$, $u$'s subset tree $S_u$ is the intersection of $u$'s subtree and the set $C$.
Due to <ref>, the subset trees are connected.

Next, we show that every BCC can be found by <ref>.

For each BCC $C\subseteq V$, <ref> assigns them to the same biconnected component.

Directly proving <ref> is highly non-trivial, so we first show an useful lemma that <ref> can correctly find the component heads.

Each component head can be identified by <ref> correctly.

The component heads are the shallowest vertices in the BCCs, and the non-root ones are articulation points (<ref>).

Now let's consider a BCC and the shallowest vertex $h\in C$, and we show that <ref> can identify it.
If $h$ not the root of the spanning tree, we know that removing $h$ cuts $C\setminus \{h\}$ from the $h$'s parent, so all edges that have endpoints in $C\setminus \{h\}$ do not have other endpoints outside $h$'s subtree.
Hence, for each of $h$'s children in $C$ (assume it is $c$), we know $\first[h]\le\low[c]$ and $\high[c]\le\last[h]$, so $(c,h)$ is a critical edge.
This means $h$ is not connected to any of $h$'s children in $C$ on <ref>, so $l[h]\ne l[c]$, and $h$ will be assigned as the component head of $C$.
Later in the proof of <ref>, we will show the other direction—no two heads will be assigned to one BCC $C$.

Alternatively, if $h$ is the root of the spanning tree, then based on the definition, we directly have $\first[h]\le\low[c]$ and $\high[c]\le\last[h]$.
All $h$'s tree edges are critical, so $h$ will be on its own connected component after executing <ref>, and will be assigned as the component head of $C$.

With <ref>, we can now prove <ref>.

An example for different cases discussed in the proof.  Dotted arrows are critical edges.  Blue straight lines are non-critical tree edges.  Orange curve lines are cross edges.  The entire graph is biconnected, and we want to show that all non-root vertices are connected via non-critical tree edges and cross edges.

We have shown in <ref> that we can find the component head $h$ for a BCC $C$ correctly.
Now we show all other vertices in $C\setminus \{h\}$ are connected using the remaining edges on <ref>, so combining them proves the lemma.

We prove this by first checking all tree edges in $C\setminus \{h\}$ and showing that the two endpoints are still connected, and then all $h$'s subtrees (if more than one) are connected.

Since $C$ is biconnected, $C\setminus \{h\}$ is connected in the original graph $G$.
When running the connectivity on <ref>, we skip the back edges and critical tree edges.
We now show that after removing these edges, $C'=C\setminus \{h\}$ is still connected.
Assume $h$'s children in $C$ are $c_1,\dots,c_k$.
Then either $k=1$, or the subset trees $S_{c_1},\dots,S_{c_k}$ in $C$ must be connected via cross edges, since otherwise removing $h$ disconnects them into unconnected components[Here $S_{c_i}$ cannot have back edges to $h$'s ancestors or cross edges to $h$'s ancestors' other subtrees since otherwise $h$'s parent will be biconnected to $C$.].

Now we will inductively prove that all vertices in $S_{c_i}$ are connected when running the connectivity on <ref>.

Let $\bar{C}$ be any subset tree rooted at $\bar{c}$.
There can be three conditions for $\bar{C}$: (1) $|\bar{C}|=1$, (2) $|\bar{C}|>1$, $\bar{c}$ has only one child $c$ in $\bar{C}$; or (3) $\bar{c}$ has at least two children.
We prove inductively: case (1) is the base case and $\bar{C}$ is trivially connected since $|\bar{C}|=1$; cases (2) and (3) are induction steps and can be applied recursively.

For case (2), the there must exist an edge $(u,v)$ such that $u\in S_c$ and $v\in C\setminus S_c$ since otherwise removing $c'$ disconnects $S_c$ and $h$.
In <ref>, an example is when $c'$ is node 1, $c$ is node 2, and $(u,v)$ is $(2,3)$.
Due to the existence of $(u,v)$, either $\low[c]<\first[\bar{c}]$ or $\last[\bar{c}]>\high[c]$ holds, so $(\bar{c},c)$ is a tree edge but not a critical edge, which exists when running the connectivity on <ref>.
Hence, <ref> put $\bar{c}$ and $c$ in the same BCC, and we can apply the same argument on $S_c$ and show all vertices are connected.

Now let's consider the most complicated one: case (3).
Again assume $\bar{c}$'s children in $C$ are $c_1,\dots,c_k$.
For a subset tree $S_{c_i}\in C$, if there exists an edge $(u,v)$ such that $u\in S_{c_i}$ and $v\in C\setminus S_c$ (can either be a back edge or a cross edge), then either $\low[c]<\first[\bar{c}]$ or $\last[\bar{c}]>\high[c]$ holds.
Some example vertices for $c$ in this case are vertices 4, 5, and 6 in <ref>.
In this case, $(\bar{c},c_i)$ is not a critical edge, and <ref> puts them in the same BCC.
We call these subset trees as connected subset trees.
For the other subset trees (e.g., those rooted at vertices 3, 7, or 8), they are either directed connected to the connected subset trees (vertices 3 and 7), or via other unconnected subset trees (vertex 8).
For a specific unconnected subset tree $S_{c_i}$, consider a cross edge $(u,v)$ such that $u\in S_{c_i}$ and $v\in \bar{C}\setminus S_{c_i}$, and let $v$'s subset tree's root be $c_j$.
Since $v\notin S_{c_i}$, the entire tree path from $c_i$ to $u$ has no critical edges, so as the tree path from $c_j$ to $v$.
Hence $c_i$ and  are connected when running the connectivity on <ref>.
In <ref>, an example for $c_i$ is vertex 3, and $(u,v)$ is $(3,5)$ ($\bar{c}$ is vertex 0).
The tree path from 4 to 5 only contains non-critical edges due to the existence of $(5,3)$, so vertices 3 and 4 are connected.
If $v$ is in a connected subset tree, then $c_i$ and $\bar{c}$ are connected using the tree path from $c_i$ to $u$, then the cross edge from $u$ to $v$, and the tree path from $v$ to $\bar{c}$, and none of the edges are critical edges.
In the previous example, this path is 3–5–4–0.
If all such $v$ connect to unconnected subset trees, we can show that $c_i$ connects to the other $c_j$ that $v\in S_{c_j}$.
As shown above, there always exists a path to connect every unconnected subset tree to connected ones.
Otherwise, that means there exists some subset trees (that are connected to others) with no edges going out of $\bar{c}$'s subtree.
In this case, removing $\bar{c}$ disconnects $c_i$ and $\bar{c}$'s parent), which leads to a contradiction.
Hence, <ref> will connect $c_i$ to $\bar{c}$ using these cross edges and the tree paths to connect them, which contains no critical edges.
Again using vertex 8 in <ref> as an example, although $S_8$ does not directly connect to a connected subset tree, there must exist a path to connect 8 with 8's parent 4 via other subset trees (in this example it is 8–7–5–4) since otherwise removing 4 disconnects 8 from 4's parent, which is 0.
If no such connected subset tree 5 exists, say we remove edge $(3,5)$, then vertex 4 becomes an articulation point.
Combining all above cases, we showed that all $c_i$ are connected to $\bar{c}$.
Then we can inductively show $S_{c_i}$ is connected until we reach the base case.

All vertices in each connected component computed by <ref> on <ref> are in a biconnected component.

Consider two vertices $u$ and $v$ in this connected component.
Apparently $u$ and $v$ are connected in the original graph $G$, and we now show they are also biconnected.
Since $u$ and $v$ are connected when running the connectivity on <ref>, let $P=\{u=p_0,p_1,\dots,p_{k-1},v=p_k\}$ be the path that connects $u$ and $v$ that only uses cross edges and non-critical tree edges.

We now show that after removing any vertex $p_i$ that $1\le i<k$ on the path $P$, $p_{i-1}$ and $p_{i+1}$ are still connected.
This indicates that $u$ and $v$ are biconnected.
We prove this constructively.
There three possible cases for the local structure.
Case 1 is that both $p_{i-1}$ and $p_{i+1}$ are the children of $p_i$ in the spanning tree.
Since $(p_{i-1},p_i)$ is not a critical edge, there must be an edge $(x,y)$ such that $x\in S_{p_{i-1}}$ and $y\notin S_{p_i}$.
Similarly, for $(p_i,p_{i+1})$, there exists an edge $(x',y')$ such that $x'\in S_{p_{i+1}}$ and $y\notin S_{p_i}$.
Hence, the without using $p_i$, $p_{i-1}$ and $p_{i+1}$ are still connected using the path that consists: the tree path from $p_{i-1}$ to $x$, then $(x,y)$, the tree path from $y$ to $y'$, $(y',x')$, and finally the tree path from $x'$ to $p_{i+1}$.
Case 2 is that one of $p_{i-1}$ and $p_{i+1}$ is the children of $p_i$ in the spanning tree, and the other is either the parent of $p_i$ or connected to $p_i$ using a cross edge.
WLOG, let's assume $p_{i-1}$ is the child and $p_{i+1}$ is the other vertex.
Again, since $(p_{i-1},p_i)$ is not a critical edge, there must be an edge $(x,y)$ such that $x\in S_{p_{i-1}}$ and $y\notin S_{p_i}$.
Meanwhile, $p_{i+1}\notin S_{p_i}$ since it is either the parent of $p_i$, or the other endpoint of a cross edge (otherwise $(p_i,p_{i+1})$ is a backward edge).
Hence, the without using $p_i$, $p_{i-1}$ and $p_{i+1}$ are still connected using the path that consists: the tree path from $p_{i-1}$ to $x$, then $(x,y)$, the tree path from $y$ to $p_{i+1}$.
Case 3 is that $(p_{i-1},p_i)$ is a cross edge, and either $p_{i+1}$ is $p_i$'s parent or $(p_{i+1},p_i)$ is a cross edge.
In either case, the without using $p_i$, $p_{i-1}$ and $p_{i+1}$ are still connected using the tree path from $p_{i-1}$ to $p_i$'s parent, and the tree path from $p_i$'s parent to $p_{i+1}$ if $p_{i+1}$ is not $p_i$'s parent.

Since removing any vertex on the path $P$ does not disconnect the path, we proved that all vertices in each connected component computed by <ref> on <ref> are biconnected.

<ref> shows that <ref> can identify every BCC, and <ref> indicates that every ouput BCC by <ref> is a correct BCC.
Hence, combining them together indicates that the output for <ref> is correct.
Now, we can formally prove <ref>.

<ref> shows that <ref> computes BCCs correctly.
Regarding the cost of <ref>, <ref> compute two graph connectivity, and the ETT on <ref> requires semisorting at most $2(n-1)$ key-value pairs <cit.>.
The semisorting algorithm from <cit.> uses $O(n)$ expected work and $O(\log n)$ span .
Since computing connectivity requires visiting at least all vertices and edges, the cost for semisort is asymptotically bounded, so as the cost for other steps.
For instance, the $\low$ and $\high$ arrays can be computed using standard range minimum queries (RMQ), which uses $O(m)$ work and $O(\log n)$ span.

For our BCC implementation, we use the connectivity algorithm discussed in <ref> uses $O(m+n)$ expected work and $O(\log^3 n)$ span .
Hence, our BCC is work-efficient and has polylogarithmic span.

In this paper, we show a theoretically efficient  algorithm that performs $O(n+m)$ work Assuming we have semisort in $O(?)$ span. Unlike Tarjan-Vishkin's algorithm, we do not need to construct the transformed graph. Instead, we skip a set of edges in the original graph. To achieve this, we need three key components.

Spanning forest. To start with, we need to know the number of spanning trees in the graph and partition all vertices on the same tree together. This part can be done by the connected component (CC) algorithm. The output spanning forest is a compressed sparse row (CSR), where we have a permutation of vertices and an offset array indicating the range of the $i$-th tree in the vertices array.

Euler Tour Tree. Now we know which tree each vertex belongs to. We can construct the Euler tour tree for each tree in parallel. This is in support of computing the helper values of each vertex. Specifically, we define $\first[v]$ and $\last[v]$ as the rank of the first and last appearance of vertex $v$ in its Euler tour ordering. Also, we define the low value $\low[v]$ and high value $\high[v]$ of a vertex $v \in V$ as follows:

$\low[v]$ = $\min${$w_1[u]$| $u$ is in the subtree rooted at $v$}

$\high[v]$ = $\max${$w_2[u]$| $u$ is in the subtree rooted at $v$}

$w_1[v]=\min\{\first [u] \cup \{\first [u'] | (u, u')$ is a non-tree edge$\}\}$

$w_2[v]=\max\{\first [u] \cup \{\first [u'] | (u, u')$ is a non-tree edge$\}\}$

To query the min and max among a subtree, we first flatten the Euler tour ordering to an array by list ranking. Then we build a sparse table <cit.> to process range minimum/maximum queries (RMQ).

BC-labeling. BC-labeling allows us to efficiently query articulation points, bridges, and the biconnected component labels in $O(n)$ space instead of saving the labels of each edge.
We define a tree edge to be a critical edge if the parent $u$ and child $v$ have $\first[u] \leq \low[v]$ and $\last[u] \geq \high[v]$.
We also define a non-tree edge $(u, v)$ to be a backward edge if $\first[u] \leq \first[v]$ and $\last[u] \geq \first[v]$ or vice versa.
We define an edge to be a non-essential edge if it is either critical edge or backward edge.
Then we run the connected components on the graph skipping all non-eseential edges. The connected components algorithm returns a label for each vertex.
For each component, a component head is the parent of its cluster in the spanning tree (the parent of the root vertex is itself).
A vertex (except for the roots) is an articulation point iff. it is the head of at least one connected component. The root of a spanning tree is an articulation point iff. it is the head of at least two connected components.
An edge $(u, v)$ is a bridge iff. $u$ is the parent of $v$ in the spanning tree and $\first[v] = \low[v]$ and $\last[v] \geq \high[v]$. Assuming we don't have duplicate edges. If we do have, all duplicate edges cannot be bridge. We can use a hashtable to do this.
Two vertices are in the same biconnected component iff. they have the same label in or one is the component head of the other.

assume  $c$'s children in $C$ are $c_1,\dots,c_k$, and we will show that they are connected when running the connectivity on <ref>.
Consider two of them as $c_i$ and $c_j$.
We know $c_i$ and $c_j$ are connected in the original graph $G$ via $(c_i,h,c_j)$, and at least another path that only uses vertices in $C\setminus \{h\}$ (otherwise removing $h$ disconnects $c_i$ and $c_j$).
Let $P=(c_i=v_0,v_1,\dots,v_{l-1},c_j=v_l)$ be such a pass that 1) $P$ does not have backward edges since otherwise we can replace each of them as a list of tree edges in the spanning tree, and 2) contains the minimum number of cross edges.
Now we show that all edges in $P$ remain when running the connectivity on <ref>.
All cross edges in $P$  are remained.
Let $(v_{i'},\dots,v_{j'})$ be a non-empty tree path, and $v_{i'}$ and $v_{j'}$ are either the ends of the path or connect to cross edges.
WLOG assume $v_{i'}$ is deeper in the spanning tree, and in this case $v_{i'}$ cannot be the start or end of the path since $c_i$ and $c_j$ are $h$'s children and are the shallowest vertices in $C$.
This means $(v_{i'-1},v_{i'})$ is a cross edge, so

We prove this by first checking all tree edges in $C\setminus \{h\}$ and showing that the two endpoints are still connected, and then all $h$'s subtrees (if more than one) are connected.

Consider a tree edge $(u,v)$ where $u,v\in C\setminus \{h\}$ and $u$ is the deeper vertex (the child).
If $(u,v)$ is not a critical edge, then it exists when running the connectivity on <ref>, so $u$ and $v$ are connected.
If $(u,v)$ is a critical edge, we know there exist no edge $(x,y)~|~x\in S_u,y\in C\setminus S_v$ (otherwise either $\first[u]<\low[v]$ or $\high[u]>\last[v]$ is true), and there exists at least one edge $(x,y)~|~x\in S_u,y\in S_v\setminus S_u$.
Otherwise, if all other endpoints $y\in S_u$, then removing $v$ disconnects $S_u$ and $h$, leading to a contradiction that $S_u$ are $h$ biconnected.
Since $x$ and $y$ are in $v$'s different subtrees,
In this case, the path $P$ that contains the tree path from $u$ to $x$, then

First, we show backward edges do not affect the connectivity.
Consider a backward edge $(u,v)$ and $u$ is the deeper vertex.

For each BCC $C$, one of the three following conditions must be true: (1) $|C|=2$ and the other vertex $c$ is $h$'s child, (2) $|C|>2$, $h$ has only one child $c$ in $C$, and there exists a backward edge $(u,h)$ where $h\in C\setminus \{h,c\}$ (otherwise cutting $c$ disconnects $C$); or (3) $h$ has at least two children, and each of them has at least one edge from its subtree to its sibling's subtree (otherwise cutting it disconnects $C$).
For case (1), $\left|C\setminus \{h\}\right|=1$ so it is trivially connected.

For case (2), we show that $c$ is connected to $c$'s child $c'\in C$, and we can recursively apply the same argument for $C\setminus \{h,c\}$.
since the existence of $(u,h)$, we have  $\low[c']<\first[c]$ and $\last[c']>\high[c]$, which means $(c,c')$ is a tree edge but not a critical edge, which exists when running the connectivity on <ref>.
Hence, <ref> put $c$ and $c'$ in the same BCC, and we can apply the same argument and indicate that $C\setminus \{h,c\}$ are also in the same BCC.

Now let's consider the most complicated one: case (3).
Assume $h$'s children in $C$ are $c_1,\dots,c_k$.
First of all, $S_{c_1},\dots,S_{c_k}$ must be connected via cross edges, since otherwise removing $h$ disconnects them into unconnected components.
Secondly, at least

consider $h$'s children in $C$.
At least one of them, denoted as $c$, has $\low[c]<\first[c]$ or $\high[c]>\last[c]$, since there exists at least one edge from $c$'s subtree to a vertex in $C$ but not $c$'s subtree, .
Hence, $(c,h)$ is a critical edge, and $h$ will be assigned as the component head to $c$'s BCC.

Since $C$ is biconnected, $C\setminus \{h\}$ is connected in the original graph $G$.
When running the connectivity on <ref>, we skip the backward edges and the tree edges that are critical.
We now show that after removing these edges, $C'=C\setminus \{h\}$ is still connected.
There can be three conditions for $C'$: (1) $|C'|=1$ and the other vertex $c$ is $h$'s child, (2) $|C'|>1$, $h$ has only one child $c$ in $C'$; or (3) $h$ has at least two children.
We prove inductively: case (1) is the base case and $C'$ is trivially connected since $|C'|=1$; cases (2) and (3) are induction steps and can be applied recursively.

For case (2), the there must exist an edge $(u,v)~|~u\in S_c,v\in C\setminus S_c$ since otherwise removing $c$ disconnects $S_c\subset\{c\}$ and $h$.
we show that $c$ is connected to $c$'s child $c'\in C$, and we can recursively apply the same argument for $C\setminus \{h,c\}$.
since the existence of $(u,h)$, we have  $\low[c']<\first[c]$ and $\last[c']>\high[c]$, which means $(c,c')$ is a tree edge but not a critical edge, which exists when running the connectivity on <ref>.
Hence, <ref> put $c$ and $c'$ in the same BCC, and we can apply the same argument and indicate that $C\setminus \{h,c\}$ are also in the same BCC.

Now let's consider the most complicated one: case (3).
Assume $h$'s children in $C$ are $c_1,\dots,c_k$.
First of all, $S_{c_1},\dots,S_{c_k}$ must be connected via cross edges, since otherwise removing $h$ disconnects them into unconnected components.
Secondly, at least

consider $h$'s children in $C$.
At least one of them, denoted as $c$, has $\low[c]<\first[c]$ or $\high[c]>\last[c]$, since there exists at least one edge from $c$'s subtree to a vertex in $C$ but not $c$'s subtree, .
Hence, $(c,h)$ is a critical edge, and $h$ will be assigned as the component head to $c$'s BCC.

On <ref>, each BCC will be assigned a unique component head.

On <ref>, each BCC will be assigned a unique component head.

We first show that each BCC $C\subseteq V$ will not be assigned for more than one component head.
Assume to the contrary that two vertices $u,v\in C$ are both the children of critical edges (the lower ones), and their parents $p_u$ and $p_v$ are different.
Since $(u,p_u)$ and $(v,p_v)$ are critical edges that are filtered out in <ref>,

We also observed that hash table resizing is an expensive component in GBBS (see <ref>), and thus we adopt a better heuristic for estimating the size of the hash table needed to maintain all reachable pairs.

Such estimation is necessary when local search is enabled, because we can no longer upper bound of the reachability pairs, which decides the hash table size.
In GBBS, since each round only visits one-hop neighbors, they use $\sum_{v\in \ff_{i}} |N(v)| \cdot |T(v)|$ as an upper bound for number of reachability pairs in each round, where $N(v)$ are neighbors of $v$ whose labels are the same as $v$, and $T(v)$ are the pairs containing $v$ in the hash table.
In our implementation, we calculate constant fractions for the previous frontier size and the number of remaining vertices, and take the maximum of them to estimate the hash table size.
It is based on the observation that the number of reachability pairs is usually highly correlated to these two sizes.
When the hash table is too full, we restart from a larger hash table.
In most cases, resizing is not needed.
As shown in <ref>, on many graphs, the resizing hash tables in GBBS is costly, and we can save this part in our implementation.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

titleOpenStreetMap  OpenStreetMap

[Acar, Aksenov, Charguéraud, and
RaineyAcar et al2019]
authorpersonUmut A Acar, personVitaly
Aksenov, personArthur Charguéraud, and
personMike Rainey. year2019.
Provably and practically efficient granularity
control. In booktitleACM Symposium on Principles and
Practice of Parallel Programming (PPOPP). pages214–228.

[Acar, Blelloch, and BlumofeAcar
et al2002]
authorpersonUmut A. Acar, personGuy E.
Blelloch, and personRobert D. Blumofe.
The Data Locality of Work Stealing.
journalTheoretical Computer Science (TCS)
volume35, number3 (year2002).

[Agrawal and JagadishAgrawal and
authorpersonRakesh Agrawal and personHV
Jagadish. year1990.
Hybrid Transitive Closure Algorithms.. In
booktitleProceedings of the VLDB Endowment (PVLDB).

[Aho Alfred, Hopcroft John, Ullman Jeffrey,
Aho Alfred, Bracht Glenn, Hopkin Kenneth, Stanley Julian, Jean-Pierre,
Samler, Peter, et alAho Alfred et al1983]
authorpersonV Aho Alfred, personE
Hopcroft John, personD Ullman Jeffrey, personV
Aho Alfred, personH Bracht Glenn, personD
Hopkin Kenneth, personC Stanley Julian, personBrachu
Jean-Pierre, personBrown A Samler, personBrown A
Peter, et al year1983.
booktitleData structures and algorithms.
publisherUSA: Addison-Wesley.

[Allesina, Bodini, and BondavalliAllesina
et al2005]
authorpersonStefano Allesina, personAntonio
Bodini, and personCristina Bondavalli.
Ecological subsystems via graph theory: the role of
strongly connected components.
journalOikos volume110,
number1 (year2005), pages164–176.

[Andoni, Song, Stein, Wang, and ZhongAndoni
et al2018]
authorpersonAlexandr Andoni, personZhao
Song, personClifford Stein, personZhengyu Wang,
and personPeilin Zhong. year2018.
Parallel graph connectivity in log diameter
rounds. In booktitleIEEE Symposium on Foundations of
Computer Science (FOCS). IEEE, pages674–685.

authorpersonAnonymous Authors.
Manuscript on Parallel Biconnectivity (we do not
provide the information due to double-blind policy).

[Backstrom, Huttenlocher, Kleinberg, and
LanBackstrom et al2006]
authorpersonLars Backstrom, personDan
Huttenlocher, personJon Kleinberg, and
personXiangyang Lan. year2006.
Group formation in large social networks:
membership, growth, and evolution. In booktitleACM
International Conference on Knowledge Discovery and Data Mining (SIGKDD).

[Barnat, Bauch, Brim, and CeskaBarnat
et al2011a]
authorpersonJiří Barnat,
personPetr Bauch, personLuboš Brim, and
personMilan Ceska. year2011a.
Computing strongly connected components in parallel
on CUDA. In booktitleIEEE International Parallel and
Distributed Processing Symposium (IPDPS). pages544–555.

[Barnat, Chaloupka, and Van De PolBarnat
et al2011b]
authorpersonJiří Barnat,
personJakub Chaloupka, and personJaco Van De Pol.
Distributed algorithms for SCC decomposition.
journalJournal of Logic and Computation
volume21, number1 (year2011),

[Beamer, Asanović, and PattersonBeamer
et al2012]
authorpersonScott Beamer, personKrste
Asanović, and personDavid Patterson.
Direction-optimizing breadth-first search. In
booktitleInternational Conference for High Performance
Computing, Networking, Storage, and Analysis (SC).

[Beamer, Asanović, and PattersonBeamer
et al2015]
authorpersonScott Beamer, personKrste
Asanović, and personDavid Patterson.
The GAP benchmark suite.
journalarXiv preprint arXiv:1508.03619

[Blelloch, Anderson, and DhulipalaBlelloch
et al2020a]
authorpersonGuy E. Blelloch, personDaniel
Anderson, and personLaxman Dhulipala.
ParlayLib - a toolkit for parallel algorithms on
shared-memory multicore machines. In booktitleACM
Symposium on Parallelism in Algorithms and Architectures (SPAA).

[Blelloch, Dhulipala, Gibbons, Gu, McGuffey,
and ShunBlelloch et al2021]
authorpersonGuy E Blelloch, personLaxman
Dhulipala, personPhillip B Gibbons, personYan Gu,
personCharles McGuffey, and personJulian Shun.
The read-only semi-external model. In
booktitleSIAM Symposium on Algorithmic Principles of
Computer Systems (APOCS). SIAM, pages70–84.

[Blelloch, Fineman, Gibbons, and ShunBlelloch
et al2012]
authorpersonGuy E. Blelloch, personJeremy T.
Fineman, personPhillip B. Gibbons, and personJulian
Shun. year2012.
Internally deterministic parallel algorithms can be
fast. In booktitleACM Symposium on Principles and
Practice of Parallel Programming (PPOPP).

[Blelloch, Fineman, Gu, and SunBlelloch
et al2020b]
authorpersonGuy E. Blelloch, personJeremy T.
Fineman, personYan Gu, and personYihan Sun.
Optimal parallel algorithms in the binary-forking
model. In booktitleACM Symposium on Parallelism in
Algorithms and Architectures (SPAA).

[Blelloch, Gu, Shun, and SunBlelloch
et al2020c]
authorpersonGuy E. Blelloch, personYan Gu,
personJulian Shun, and personYihan Sun.
Parallelism in Randomized Incremental Algorithms.
journalJ. ACM (year2020).

[Blelloch, Gu, and SunBlelloch
et al2017]
authorpersonGuy E. Blelloch, personYan Gu,
and personYihan Sun. year2017.
Efficient Construction of Probabilistic Tree
Embeddings. In booktitleIntl. Colloq. on Automata,
Languages and Programming (ICALP).

[Blelloch, Gu, Sun, and TangwongsanBlelloch
et al2016]
authorpersonGuy E. Blelloch, personYan Gu,
personYihan Sun, and personKanat Tangwongsan.
Parallel Shortest Paths Using Radius Stepping. In
booktitleACM Symposium on Parallelism in Algorithms and
Architectures (SPAA).

authorpersonVincent Bloemen.
titleOn-the-fly parallel decomposition of strongly
connected components.
thesistypeMaster's thesis. schoolUniversity
of Twente.

[Bloemen, Laarman, and van de PolBloemen
et al2016]
authorpersonVincent Bloemen, personAlfons
Laarman, and personJaco van de Pol.
Multi-core on-the-fly SCC decomposition. In
booktitleACM Symposium on Principles and Practice of
Parallel Programming (PPOPP). pages1–12.

[Cao, Fineman, and RussellCao
et al2020]
authorpersonNairen Cao, personJeremy T
Fineman, and personKatina Russell.
Improved work span tradeoff for single source
reachability and approximate shortest paths. In
booktitleACM Symposium on Parallelism in Algorithms and
Architectures (SPAA). pages511–513.

[Chávez and Sadit TellezChávez and
Sadit Tellez2010]
authorpersonEdgar Chávez and
personEric Sadit Tellez. year2010.
Navigating K-Nearest Neighbor Graphs to Solve
Nearest Neighbor Searches. In booktitleAdvances in Pattern
Recognition. pages270–280.

[Chen, Wang, and YangChen
et al2009]
authorpersonWei Chen, personYajun Wang,
and personSiyu Yang. year2009.
Efficient influence maximization in social
networks. In booktitleACM International Conference on
Knowledge Discovery and Data Mining (SIGKDD). pages199–208.

[Cheng, Huang, Wu, and FuCheng
et al2013]
authorpersonJames Cheng, personSilu Huang,
personHuanhuan Wu, and personAda Wai-Chee Fu.
Tf-label: a topological-folding labeling scheme for
reachability querying in a large graph. In booktitleACM
SIGMOD International Conference on Management of Data (SIGMOD).

authorpersonEdith Cohen.
Size-estimation framework with applications to
transitive closure and reachability.
journalJ. Comput. System Sci.
volume55, number3 (year1997),

authorpersonEdith Cohen.
Using selective path-doubling for parallel
shortest-path computations.
journalJournal of Algorithms volume22,
number1 (year1997), pages30–56.

[Cohen and KaplanCohen and Kaplan2004]
authorpersonEdith Cohen and personHaim
Kaplan. year2004.
Efficient estimation algorithms for neighborhood
variance and other moments. In booktitleACM-SIAM
Symposium on Discrete Algorithms (SODA). pages157–166.

[Coppersmith, Fleischer, Hendrickson, and
PinarCoppersmith et al2003]
authorpersonDon Coppersmith, personLisa
Fleischer, personBruce Hendrickson, and personAli
Pinar. year2003.
booktitleA divide-and-conquer algorithm for
identifying strongly connected components.
typeTechnical Report. institutionIBM

[Cormen, Leiserson, Rivest, and SteinCormen
et al2009]
authorpersonThomas H. Cormen,
personCharles E. Leiserson, personRonald L. Rivest,
and personClifford Stein. year2009.
booktitleIntroduction to Algorithms (3rd edition).
publisherMIT Press.

[De Noronha, Moreira, Vieira, Herrmann,
Andrade Jr, and CarmonaDe Noronha et al2018]
authorpersonAurelio WT De Noronha,
personAndré A Moreira, personAndré P Vieira,
personHans J Herrmann, personJosé S Andrade Jr,
and personHumberto A Carmona. year2018.
Percolation on an isotropically directed lattice.
journalPhysical Review E volume98,
number6 (year2018), pages062116.

[Devshatwar, Amilkanthwar, and
NasreDevshatwar et al2016]
authorpersonShrinivas Devshatwar,
personMadhur Amilkanthwar, and personRupesh Nasre.
GPU centric extensions for parallel strongly
connected components computation. In booktitleWorkshop on
General Purpose Processing using Graphics Processing Unit.

[Dhulipala, Blelloch, and ShunDhulipala
et al2017]
authorpersonLaxman Dhulipala, personGuy E.
Blelloch, and personJulian Shun.
Julienne: A Framework for Parallel Graph
Algorithms using Work-efficient Bucketing. In
booktitleACM Symposium on Parallelism in Algorithms and
Architectures (SPAA).

[Dhulipala, Blelloch, and ShunDhulipala
et al2021]
authorpersonLaxman Dhulipala, personGuy E
Blelloch, and personJulian Shun.
Theoretically efficient parallel graph algorithms
can be fast and scalable.
journalACM Transactions on Parallel Computing
(TOPC) volume8, number1 (year2021),

[Dhulipala, Hong, and ShunDhulipala
et al2020a]
authorpersonLaxman Dhulipala, personChangwan
Hong, and personJulian Shun.
ConnectIt: a framework for static and incremental
parallel graph connectivity algorithms.
journalProceedings of the VLDB Endowment (PVLDB)
volume14, number4 (year2020),

[Dhulipala, Shi, Tseng, Blelloch, and
ShunDhulipala et al2020b]
authorpersonLaxman Dhulipala, personJessica
Shi, personTom Tseng, personGuy E Blelloch, and
personJulian Shun. year2020b.
The graph based benchmark suite (GBBS). In
booktitleInternational Workshop on Graph Data Management
Experiences & Systems (GRADES). pages1–8.

[Dong, Gu, Sun, and ZhangDong
et al2021]
authorpersonXiaojun Dong, personYan Gu,
personYihan Sun, and personYunming Zhang.
Efficient Stepping Algorithms and Implementations
for Parallel Shortest Paths. In booktitleACM Symposium on
Parallelism in Algorithms and Architectures (SPAA).

[Du, Song, Gomez-Rodriguez, and ZhaDu
et al2013]
authorpersonNan Du, personLe Song,
personManuel Gomez-Rodriguez, and personHongyuan
Zha. year2013.
Scalable influence estimation in continuous-time
diffusion networks. In booktitleAdvances in Neural
Information Processing Systems (NIPS). pages3147–3155.

[Dua and GrafDua and Graf2017]
authorpersonDheeru Dua and personCasey
Graf. year2017.
titleUCI Machine Learning Repository.

[Fan, Li, Ma, Wang, and WuFan
et al2010]
authorpersonWenfei Fan, personJianzhong Li,
personShuai Ma, personHongzhi Wang, and
personYinghui Wu. year2010.
Graph homomorphism revisited for graph matching.
journalProceedings of the VLDB Endowment (PVLDB)
volume3, number1-2 (year2010),

authorpersonJeremy T. Fineman.
Nearly Work-Efficient Parallel Algorithm for
Digraph Reachability. In booktitleACM Symposium on Theory
of Computing (STOC). pages457–470.

[Fleischer, Hendrickson, and
PınarFleischer et al2000]
authorpersonLisa K Fleischer, personBruce
Hendrickson, and personAli Pınar.
On identifying strongly connected components in
parallel. In booktitleIEEE International Parallel and
Distributed Processing Symposium (IPDPS). Springer,

[Fonollosa, Sheik, Huerta, and MarcoFonollosa
et al2015]
authorpersonJordi Fonollosa, personSadique
Sheik, personRamón Huerta, and personSantiago
Marco. year2015.
Reservoir computing compensates slow response of
chemosensor arrays exposed to fast varying gas concentrations in continuous
journalSensors and Actuators B: Chemical
volume215 (year2015), pages618–629.

[Franti, Virmajoki, and HautamakiFranti
et al2006]
authorpersonPasi Franti, personOlli
Virmajoki, and personVille Hautamaki.
Fast Agglomerative Clustering Using a k-Nearest
Neighbor Graph.
journalIEEE Transactions on Pattern Analysis and
Machine Intelligence volume28, number11
(year2006), pages1875–1881.

[Gama-Castro, Salgado, Santos-Zavaleta,
Ledezma-Tejeida, Muñiz-Rascado, García-Sotelo,
Alquicira-Hernández, Martínez-Flores, Pannier, Castro-Mondragón,
et alGama-Castro et al2016]
authorpersonSocorro Gama-Castro,
personHeladia Salgado, personAlberto Santos-Zavaleta,
personDaniela Ledezma-Tejeida, personLuis
Muñiz-Rascado, personJair Santiago García-Sotelo,
personKevin Alquicira-Hernández, personIrma
Martínez-Flores, personLucia Pannier,
personJaime Abraham Castro-Mondragón, et al
RegulonDB version 9.0: high-level integration of
gene regulation, coexpression, motif clustering and beyond.
journalNucleic acids research
volume44, numberD1 (year2016),

[Gu, Napier, and SunGu et al2022]
authorpersonYan Gu, personZachary Napier,
and personYihan Sun. year2022.
Analysis of Work-Stealing and Parallel Cache
Complexity. In booktitleSIAM Symposium on Algorithmic
Principles of Computer Systems (APOCS). SIAM, pages46–60.

[Gu, Sun, and BlellochGu
et al2018]
authorpersonYan Gu, personYihan Sun, and
personGuy E. Blelloch. year2018.
Algorithmic Building Blocks for Asymmetric
Memories. In booktitleEuropean Symposium on Algorithms

[Hautamaki, Karkkainen, and FrantiHautamaki
et al2004]
authorpersonVille Hautamaki, personIsmo
Karkkainen, and personPasi Franti.
Outlier detection using k-nearest neighbour graph.
In booktitleInternational Conference on Pattern
Recognition, Vol. volume3. pages430–433.

[Hong, Rodia, and OlukotunHong
et al2013]
authorpersonSungpack Hong, personNicole C
Rodia, and personKunle Olukotun.
On fast parallel detection of strongly connected
components (SCC) in small-world graphs. In
booktitleInternational Conference for High Performance
Computing, Networking, Storage, and Analysis (SC). pages1–11.

[Hou, Wang, Wu, Fu, Jia, Wang, Li, and
ZhangHou et al2019]
authorpersonJunteng Hou, personShupeng
Wang, personGuangjun Wu, personGe Fu,
personSiyu Jia, personYong Wang,
personBinbin Li, and personLei Zhang.
Parallel strongly connected components detection
with multi-partition on gpus. In booktitleInternational
Conference on Computational Science. Springer, pages16–30.

[Hou, Wang, Wu, Ma, and ZhangHou
et al2020]
authorpersonJunteng Hou, personShupeng
Wang, personGuangjun Wu, personBingnan Ma, and
personLei Zhang. year2020.
Parallel SCC Detection Based on Reusing Warps and
Coloring Partitions on GPUs. In booktitleInternational
Conference on Algorithms and Architectures for Parallel Processing.
Springer, pages31–46.

[Jain, Flick, Pan, Green, and AluruJain
et al2017]
authorpersonChirag Jain, personPatrick
Flick, personTony Pan, personOded Green, and
personSrinivas Aluru. year2017.
An adaptive parallel algorithm for computing
connected components.
journalIEEE Transactions on Parallel and
Distributed Systems volume28, number9
(year2017), pages2428–2439.

authorpersonJoseph JáJá.
booktitleIntroduction to Parallel Algorithms.
publisherAddison-Wesley Professional.

[Jambulapati, Liu, and SidfordJambulapati
et al2019]
authorpersonArun Jambulapati, personYang P
Liu, and personAaron Sidford.
Parallel reachability in almost linear work and
square root depth. In booktitleIEEE Symposium on
Foundations of Computer Science (FOCS). IEEE, pages1664–1686.

[Jayanti, Tarjan, and Boix-AdseràJayanti
et al2019]
authorpersonSiddhartha Jayanti,
personRobert E Tarjan, and personEnric
Boix-Adserà. year2019.
Randomized concurrent set union and generalized
wake-up. In booktitleACM Symposium on Principles of
Distributed Computing (PODC). pages187–196.

[Ji, Liu, and HuangJi et al2018]
authorpersonYuede Ji, personHang Liu, and
personH Howie Huang. year2018.
ispan: Parallel identification of strongly
connected components with spanning trees. In
booktitleInternational Conference for High Performance
Computing, Networking, Storage, and Analysis (SC). IEEE,

[Karypis, Han, and KumarKarypis
et al1999]
authorpersonGeorge Karypis, personEui-Hong
Han, and personVipin Kumar. year1999.
Chameleon: Hierarchical clustering using dynamic
journalComputer volume32,
number8 (year1999), pages68–75.

[Khan, Kuhn, Malkhi, Pandurangan, and
TalwarKhan et al2012]
authorpersonMaleq Khan, personFabian Kuhn,
personDahlia Malkhi, personGopal Pandurangan, and
personKunal Talwar. year2012.
Efficient distributed approximation algorithms via
probabilistic tree embeddings.
journalDistributed Computing volume25,
number3 (year2012), pages189–205.

[King and SagertKing and Sagert2002]
authorpersonValerie King and personGarry
Sagert. year2002.
A fully dynamic algorithm for maintaining the
transitive closure.
journalJ. Computer and System Sciences
volume65, number1 (year2002),

[Klein and SubramanianKlein and
authorpersonPhilip N Klein and
personSairam Subramanian. year1997.
A randomized parallel algorithm for single-source
shortest paths.
journalJournal of Algorithms volume25,
number2 (year1997), pages205–220.

[Kwak, Lee, Park, and MoonKwak
et al2010]
authorpersonHaewoon Kwak, personChanghyun
Lee, personHosung Park, and personSue Moon.
What is Twitter, a social network or a news
media?. In booktitleInternational World Wide Web Conference
(WWW). pages591–600.

[Kwon, Nunley, Gardner, Balazinska, Howe, and
LoebmanKwon et al2010]
authorpersonYongChul Kwon, personDylan
Nunley, personJeffrey P Gardner, personMagdalena
Balazinska, personBill Howe, and personSarah
Loebman. year2010.
Scalable clustering algorithm for N-body
simulations in a shared-nothing cluster. In
booktitleInternational Conference on Scientific and
Statistical Database Management. Springer, pages132–150.

authorpersonCharles E. Leiserson.
The Cilk++ concurrency platform.
journalThe Journal of Supercomputing
volume51, number3 (year2010).

[Leiserson and SchardlLeiserson and
authorpersonCharles E. Leiserson and
personTao B. Schardl. year2010.
A work-efficient parallel breadth-first search
algorithm (or how to cope with the nondeterminism of reducers). In
booktitleACM Symposium on Parallelism in Algorithms and
Architectures (SPAA).

[Li, Zhu, Cong, and YangLi
et al2014]
authorpersonGuohui Li, personZhe Zhu,
personZhang Cong, and personFumin Yang.
Efficient decomposition of strongly connected
components on GPUs.
journalJournal of Systems Architecture
volume60, number1 (year2014),

[Li, Chen, and SongLi et al2022]
authorpersonLin Li, personXiang Chen, and
personChengyun Song. year2022.
A robust clustering method with noise
identification based on directed K-nearest neighbor graph.
journalNeurocomputing  volume508
(year2022), pages19–35.

[Li, Chen, Shen, Fang, Tang, and YangLi
et al2017]
authorpersonPingfan Li, personXuhao Chen,
personJie Shen, personJianbin Fang,
personTao Tang, and personCanqun Yang.
High performance detection of strongly connected
components in sparse graphs on GPUs. In
booktitleProceedings of the 8th International Workshop on
Programming Models and Applications for Multicores and Manycores.

authorpersonGavin Lowe.
Concurrent depth-first search algorithms based on
Tarjan’s algorithm.
journalInternational Journal on Software Tools for
Technology Transfer volume18, number2
(year2016), pages129–147.

[Lucińska and
WierzchońLucińska and Wierzchoń2012]
authorpersonMałgorzata Lucińska and
personSławomir T. Wierzchoń.
Spectral Clustering Based on k-Nearest Neighbor
Graph. In booktitleComputer Information Systems and
Industrial Management. pages254–265.

[Maier, Hein, and Von LuxburgMaier
et al2009]
authorpersonMarkus Maier, personMatthias
Hein, and personUlrike Von Luxburg.
Optimal construction of k-nearest-neighbor graphs
for identifying noisy clusters.
journalTheoretical Computer Science
volume410, number19 (year2009),

[Malewicz, Austern, Bik, Dehnert, Horn, Leiser,
and CzajkowskiMalewicz et al2010]
authorpersonGrzegorz Malewicz,
personMatthew H Austern, personAart JC Bik,
personJames C Dehnert, personIlan Horn,
personNaty Leiser, and personGrzegorz Czajkowski.
Pregel: a system for large-scale graph processing.
In booktitleProceedings of the 2010 ACM SIGMOD International
Conference on Management of data. pages135–146.

[Mclendon Iii, Hendrickson, Plimpton, and
RauchwergerMclendon Iii et al2005]
authorpersonWilliam Mclendon Iii,
personBruce Hendrickson, personSteven J Plimpton,
and personLawrence Rauchwerger.
Finding strongly connected components in
distributed graphs.
journalJ. Parallel Distrib. Comput.
volume65, number8 (year2005),

[Meusel, Lehmberg, Bizer, and VignaMeusel
et al2014]
authorpersonRobert Meusel, personOliver
Lehmberg, personChristian Bizer, and
personSebastiano Vigna. year2014.
titleWeb Data Commons - Hyperlink Graphs.

[Miller, Peng, and XuMiller
et al2013]
authorpersonGary L Miller, personRichard
Peng, and personShen Chen Xu.
Parallel graph decompositions using random shifts.
In booktitleACM Symposium on Parallelism in Algorithms and
Architectures (SPAA).

[Mislove, Marcon, Gummadi, Druschel, and
BhattacharjeeMislove et al2007]
authorpersonAlan Mislove, personMassimiliano
Marcon, personKrishna P Gummadi, personPeter
Druschel, and personBobby Bhattacharjee.
Measurement and analysis of online social
networks. In booktitleACM SIGCOMM conference on Internet
measurement. pages29–42.

[Morone, Leifer, and MakseMorone
et al2020]
authorpersonFlaviano Morone, personIan
Leifer, and personHernán A Makse.
Fibration symmetries uncover the building blocks of
biological networks.
journalProceedings of the National Academy of
Sciences volume117, number15
(year2020), pages8306–8314.

[Nadini, Alessandretti, Di Giacinto, Martino,
Aiello, and BaronchelliNadini et al2021]
authorpersonMatthieu Nadini, personLaura
Alessandretti, personFlavio Di Giacinto, personMauro
Martino, personLuca Maria Aiello, and personAndrea
Baronchelli. year2021.
Mapping the NFT revolution: market trends, trade
networks, and visual features.
journalScientific reports volume11,
number1 (year2021), pages1–11.

[Nguyen, Lenharth, and PingaliNguyen
et al2013]
authorpersonDonald Nguyen, personAndrew
Lenharth, and personKeshav Pingali.
A lightweight infrastructure for graph analytics.
In booktitleProceedings of the Twenty-Fourth ACM Symposium
on Operating Systems Principles. pages456–471.

[Ohsaka, Akiba, Yoshida, and
KawarabayashiOhsaka et al2014]
authorpersonNaoto Ohsaka, personTakuya
Akiba, personYuichi Yoshida, and personKen-ichi
Kawarabayashi. year2014.
Fast and accurate influence maximization on large
networks with pruned monte-carlo simulations. In
booktitleAAAI Conference on Artificial Intelligence,
Vol. volume28.

[Paredes and ChávezParedes and
authorpersonRodrigo Paredes and
personEdgar Chávez. year2005.
Using the k-Nearest Neighbor Graph for Proximity
Searching in Metric Spaces. In booktitleString Processing
and Information Retrieval. pages127–138.

[Randall, Stata, Wickremesinghe, and
WienerRandall et al2002]
authorpersonKeith H Randall, personRaymie
Stata, personRajiv G Wickremesinghe, and
personJanet L Wiener. year2002.
The link database: Fast access to graphs of the
web. In booktitleIEEE Data Compression Conference
(DCC). IEEE, pages122–131.

authorpersonJohn H Reif.
Depth-first search is inherently sequential.
journalInform. Process. Lett.
volume20, number5 (year1985),

[Roditty and ZwickRoditty and Zwick2008]
authorpersonLiam Roditty and personUri
Zwick. year2008.
Improved dynamic reachability algorithms for
directed graphs.
journalSIAM J. on Computing
volume37, number5 (year2008),

[Rugina and RinardRugina and Rinard2000]
authorpersonRadu Rugina and personMartin
Rinard. year2000.
Symbolic bounds analysis of pointers, array
indices, and accessed memory regions.
journalACM Sigplan Notices volume35,
number5 (year2000), pages182–195.

[Sacharidis, Papadopoulos, and
PapadiasSacharidis et al2009]
authorpersonDimitris Sacharidis,
personStavros Papadopoulos, and personDimitris
Papadias. year2009.
Topologically sorted skylines for partially ordered
domains. In booktitleIEEE International Conference on Data
Engineering (ICDE). IEEE, pages1072–1083.

[Salihoglu and WidomSalihoglu and
authorpersonSemih Salihoglu and
personJennifer Widom. year2014.
Optimizing Graph Algorithms on Pregel-like
journalProceedings of the VLDB Endowment (PVLDB)
volume7, number7 (year2014),

authorpersonWarren Schudy.
Finding strongly connected components in parallel
using $O(\log^2 n)$ reachability queries. In
booktitleACM Symposium on Parallelism in Algorithms and
Architectures (SPAA). pages146–151.

[Sebastian and KimiaSebastian and
authorpersonThomas B. Sebastian and
personBenjamin B. Kimia. year2002.
Metric-Based Shape Retrieval in Large Databases.
In booktitleInternational Conference on Pattern Recognition

[Sharma and SharmaSharma and Sharma2017]
authorpersonAnkush Sharma and personAmit
Sharma. year2017.
KNN-DBSCAN: Using k-nearest neighbor information
for parameter-free density based clustering. In
booktitle2017 International Conference on Intelligent
Computing, Instrumentation and Control Technologies (ICICICT). IEEE,

[Shekhar, Thomas, and KarlapalemShekhar
et al2018]
authorpersonMihir Shekhar, personLini
Thomas, and personKamalakar Karlapalem.
High Dimensional Clustering: A Strongly Connected
Component Clustering Solution (SCCC). In booktitle2018 IEEE
International Conference on Data Mining Workshops (ICDMW). IEEE,

[Shi and SpencerShi and Spencer1999]
authorpersonHanmao Shi and personThomas H.
Spencer. year1999.
Time-Work Tradeoffs of the Single-Source Shortest
Paths Problem.
journalJournal of Algorithms volume30,
number1 (year1999), pages19–32.

[Shiloach and VishkinShiloach and
authorpersonYossi Shiloach and personUzi
Vishkin. year1982.
An ${O}(\log n)$ Parallel Connectivity Algorithm.
journalJ. Algorithms volume3,
number1 (year1982), pages57–67.

[Shun and BlellochShun and Blelloch2013]
authorpersonJulian Shun and personGuy E.
Blelloch. year2013.
Ligra: A Lightweight Graph Processing Framework for
Shared Memory. In booktitleACM Symposium on Principles
and Practice of Parallel Programming (PPOPP).

[Shun and BlellochShun and Blelloch2014]
authorpersonJulian Shun and personGuy E
Blelloch. year2014.
Phase-concurrent hash tables for determinism. In
booktitleACM Symposium on Parallelism in Algorithms and
Architectures (SPAA). pages96–107.

[Shun, Dhulipala, and BlellochShun
et al2014]
authorpersonJulian Shun, personLaxman
Dhulipala, and personGuy Blelloch.
A Simple and Practical Linear-work Parallel
Algorithm for Connectivity. In booktitleACM Symposium on
Parallelism in Algorithms and Architectures (SPAA).

[Slota, Rajamanickam, and MadduriSlota
et al2014]
authorpersonGeorge M Slota,
personSivasankaran Rajamanickam, and personKamesh
Madduri. year2014.
BFS and coloring-based parallel algorithms for
strongly connected components and related problems. In
booktitleIEEE International Parallel and Distributed
Processing Symposium (IPDPS). IEEE, pages550–559.

authorpersonMiroslav Stuhl.
Computing Strongly Connected Components with CUDA.
journalMaster's thesis, Masaryk University

[Sutton, Ben-Nun, and BarakSutton
et al2018]
authorpersonMichael Sutton, personTal
Ben-Nun, and personAmnon Barak.
Optimizing parallel graph connectivity computation
via subgraph sampling. In booktitleIEEE International
Parallel and Distributed Processing Symposium (IPDPS). IEEE,

authorpersonRobert Tarjan.
Depth-first search and linear graph algorithms.
journalSIAM J. on Computing volume1,
number2 (year1972), pages146–160.

[Tenenbaum, Silva, and LangfordTenenbaum
et al2000]
authorpersonJoshua B. Tenenbaum,
personVin de Silva, and personJohn C. Langford.
A Global Geometric Framework for Nonlinear
Dimensionality Reduction.
journalScience volume290,
number5500 (year2000), pages2319–2323.

[Tomkins, Smith, Amato, and
RauchwergerTomkins et al2014]
authorpersonDaniel Tomkins, personTimmie
Smith, personNancy M Amato, and personLawrence
Rauchwerger. year2014.
SCCMulti: an improved parallel strongly connected
components algorithm.
journalACM Symposium on Principles and Practice of
Parallel Programming (PPOPP) volume49, number8
(year2014), pages393–394.

[Trißl and LeserTrißl and
authorpersonSilke Trißl and personUlf
Leser. year2007.
Fast and practical indexing and querying of very
large graphs. In booktitleACM SIGMOD International
Conference on Management of Data (SIGMOD). pages845–856.

[Ullman and YannakakisUllman and
authorpersonJeffrey D Ullman and
personMihalis Yannakakis. year1991.
High-probability parallel transitive-closure
journalSIAM J. Comput. volume20,
number1 (year1991), pages100–125.

[Wang, Dong, Gu, and SunWang
et al2022]
authorpersonLetong Wang, personXiaojun
Dong, personYan Gu, and personYihan Sun.

[Wang, Yu, Dhulipala, Gu, and ShunWang
et al2021]
authorpersonYiqiu Wang, personShangdi Yu,
personLaxman Dhulipala, personYan Gu, and
personJulian Shun. year2021.
GeoGraph: A Framework for Graph Processing on
Geometric Data.
journalACM SIGOPS Operating Systems Review
volume55, number1 (year2021),

[Wijs, Katoen, and BošnačkiWijs
et al2014]
authorpersonAnton Wijs, personJoost-Pieter
Katoen, and personDragan Bošnački.
GPU-based graph decomposition into strongly
connected and maximal end components. In
booktitleInternational Conference on Computer Aided
Verification. Springer, pages310–326.

[Xu and WangXu and Wang2018]
authorpersonTaihua Xu and personGuoyin
Wang. year2018.
Finding strongly connected components of simple
digraphs based on generalized rough sets theory.
journalKnowledge-Based Systems
volume149 (year2018), pages88–98.

[Yan, Cheng, Xing, Lu, Ng, and BuYan
et al2014]
authorpersonDa Yan, personJames Cheng,
personKai Xing, personYi Lu, personWilfred
Ng, and personYingyi Bu. year2014.
Pregel algorithms for graph connectivity problems
with performance guarantees.
journalProceedings of the VLDB Endowment (PVLDB)
volume7, number14 (year2014),

[Yang and LeskovecYang and Leskovec2015]
authorpersonJaewon Yang and personJure
Leskovec. year2015.
Defining and evaluating network communities based
on ground-truth.
journalKnowledge and Information Systems
volume42, number1 (year2015),

[Zhang, Yang, Baghdadi, Kamil, Shun, and
AmarasingheZhang et al2018]
authorpersonYunming Zhang, personMengjiao
Yang, personRiyadh Baghdadi, personShoaib Kamil,
personJulian Shun, and personSaman Amarasinghe.
Graphit: A high-performance graph dsl.
journalProceedings of the ACM on Programming
Languages volume2, numberOOPSLA
(year2018), pages1–30.

[Zheng, Liu, Wang, and XieZheng
et al2008]
authorpersonYu Zheng, personLike Liu,
personLonghao Wang, and personXing Xie.
Learning transportation mode from raw gps data for
geographic applications on the web. In
booktitleInternational World Wide Web Conference (WWW).

1c     6c|Graph Information     3c|Ours     3c|GBBS     3c|Other Benchmarks     1c$\textbf{T}_\textbf{best}$

1c     1c$\boldsymbol{n}$     1c$\boldsymbol{m}$     1c@$\boldsymbol{D}$     1c@$\boldsymbol{|\mathit{SCC}_1|}$     1@  r$\boldsymbol{|\mathit{SCC}_1|\%}$     1c|#SCC    1cpar.      1cseq.     1c|spd.     1cpar.    1cseq.     1c|spd.     1ciSpan     1cMS    1c|SEQ     1c/ ours

LJ     4.85M      69.0M         16         3,828,682     78.98%     971,232
0.038     1.06      27.7      0.118      1.44      12.1      0.050$^?$     0.141      2.90      1.30

TW     41.7M     1.47B     65         33,479,734     80.38%     8,044,729
0.226      14.3     63.2      0.387      19.7      50.9      c         1.32      71.7      1.71

SD     89.2M     2.04B     241      47,965,727     53.74%     39,205,039
1.96      104     46.6      5.25      110       21.0      4.78$^?$     1.86      104       0.95

CW     978M     42.6B      666       774,373,029     79.15%     135,223,661
17.6      1189     67.4      40.4      1,166     28.9      n         n         589       2.29

HL14     1.72B     64.4B      793      320,754,363     18.60%     1,290,550,195
20.6      1,622     78.8      67.3      2,041     30.3      n         n         620       3.27

HL12     3.56B     128B      5,275      1,827,543,757     51.28%     1,279,696,892
95.5       8528     89.3      361       7,022     19.5      n         n         1822      3.78

HH5     2.05M     10.2M     980      257,914     12.59%     94,010
0.208     3.10      14.9      3.95      3.51      0.89       0.791      2.21         0.449      2.16

CH5     4.21M     21.0M      4,550      497,331     11.82%     248,227
0.557      5.83      10.5       8.39      5.84      0.70       2.15      17.6      0.427      0.77

GL2     24.9M     49.8M     4,142      5,368     0.02%     9,705,931
0.598      39.1      65.3      3.00      82.4      27.5      t         8.36         3.39      5.01

GL5     24.9M     124M      12,059     860,403     3.46%     3,198,626
0.865      45.8      53.0      10.5      91.0      8.69       t         19.1         4.83      5.58

GL10     24.9M     249M      4,531      3,042,330     12.23%     326,811
1.49      61.6      41.4      12.3      76.5      6.24       35.2      7.14         9.30      4.79

GL15     24.9M     373M      5,491      3,239,156     13.02%     187,646
2.09      75.5      36.1      13.7      84.5      6.15       29.4      10.6         11.3      5.06

GL20     24.9M     498M     5,275     3,336,963     13.41%     128,021
2.38      86.0      36.1      14.5      96.6      6.68       27.3      12.3         13.3      5.18

COS5     321M     1.61B     1,148    301,413,787     93.88%     2,273,690
3.22      284       88.2      12.0      367       30.7      t         57.4         189       3.72

SQR     100M     300M     10,002      99,101,606     99.10%     829,495
0.577      24.7      42.8      11.1      28.5      2.57       4.45$^?$     12.6      15.5      7.72

REC     10M     30M      5,946      9,890,647     98.91%     101,059
0.117      2.08      17.8      3.82      2.14      0.56       1.19$^?$     5.24      1.57      10.2

SQR'     100M     120M     51       58        0.00%     78,052,793
1.38      105       76.3      4.76      243       51.0      26.4$^?$     3.19         6.90      2.31

REC'     10M     12M     80       42        0.00%     7,819,050
0.159      9.38      59.0      1.00      18.7      18.8      0.851$^?$     0.645         0.60      3.75

The running times (in seconds) of all tested algorithms on SCC. $n=$ number of vertices. $m=$ number of edges. $D=$ estimated diameter (a lower bound of the actual value). $|\mathit{SCC}_1|=$ largest strongly connected component (SCC) size. $|\mathit{SCC}_1|\%= |\mathit{SCC}_1|/n$, ratio of the largest SCC. #SCC $=$ number of SCCs.

“iSpan” $=$ iSpan algorithm <cit.>. “MS” $=$ Multi-step algorithm <cit.>. “SEQ” $=$ classic sequential SCC <cit.>.
“par.” $=$ parallel running time (on 192 hyperthreads). “seq.”$=$ sequential running time. “spd.”$=$ self-relative speedup.
“?”$=$ number of SCCs is different from other implementations.

“!”$=$ largest SCC size is different from other implementations.
“t”$=$ timeout (more than 5 hours). “c”$=$ crash. “n”$=$ no support.
We set $\tau=2^9$.
The fastest runtime for each graph is underlined.
Red numbers are parallel running times slower than .

BCC Breakdown For All Graphs

3c|Connectivity    3cLE-Lists   1l@   1@ l@ 1*New

Ours     1@c@  DHS'21    Spd.     Ours     1@c@  Parlay     Spd.    1l   1@ l@ Graphs

OK    0.010    0.008    0.76    0.577    1.52    2.63    1l   1@lOK <cit.>
LJ    0.013    0.012    0.91    0.502    1.96    3.91       com-orkut

TW    0.093    0.099    1.05    4.88    16.6    3.41       $n=3M$

FT    0.197    0.150    0.76    24.9    30.0    1.20       $m=234M$
SD    0.222    0.271    1.22    13.9    49.3    3.56    1l   1@lFT <cit.>
CW    2.425    2.844    1.17    3cout of memory       Friendster

HL14    3.694    4.463    1.21    3cout of memory       $n=65M$

HL12    8.446    10.39    1.23    3cout of memory       $m=3.6B$

HH5    0.017    0.041    2.40    2.06    15.5    7.55    1l   1@lUSA <cit.>
CH5    0.035    0.026    0.76    5.38    54.2    10.1       RoadUSA

GL2    0.045    0.132    2.97    2.89    14.1    4.87       $n=24M$

GL5    0.074    0.177    2.40    12.4    68.1    5.49       $m=58M$

GL10    0.123    0.210    1.71    11.0    56.6    5.15    1l   1@lGE <cit.>
GL15    0.147    0.236    1.61    11.7    59.2    5.06       Germany

GL20    0.166    0.242    1.46    11.9    63.7    5.37       $n=12M$

COS5    1.310    2.697    2.06    132    329    2.49       $m=32M$
USA    0.045    0.092    2.07    14.9    101    6.74    1l   1l

GE    0.040    0.129    3.23    5.98    32.4    5.42    1l   1l

SQR    0.161    0.290    1.80    45.4    184    4.05

REC    0.023    0.037    1.66    7.28    520$^?$    71.4

SQR'    0.134    0.275    2.06    46.8    202$^?$    4.32

REC'    0.021    0.043    2.08    8.57    648$^?$    75.7

Running time (in seconds) of connectivity and LE-Lists implementations.
DHS'21$=$the LDD-UF-JTB connectivity implementation in  <cit.>.
Parlay$=$the LE-lists implementation in ParlayLib <cit.>.
Spd.$=$Baseline_time $/$ our_time.

“?”$=$results different from our parallel and sequential version, and the running time may not be accurate.

Number of rounds with and without local search for each batch.

The number $k$ in the title of each figure means that on that graph, using local search reduces the number of rounds in reachability searches by $k$ times on average.