On a 30-core machine with two-way hyper-threading, our parallel hierarchy construction algorithm achieves up to a 58.84x speedup over the state-of-the-art sequential hierarchy construction algorithm by Sariyuce et al. and up to a 30.96x self-relative parallel speedup. On the same machine, our approximation algorithm achieves a 3.3x speedup over our exact algorithm, while generating coreness estimates with a multiplicative error of 1.33x on average.]]>
Dense subgraph and substructure detection is a fundamental tool in graph mining, with many applications in areas including social network analysis [13,61], fraud detection [24], and computational biology [3,21]. Sariyüce et al. [52] introduced the nucleus decomposition problem, a generalization of the 𝑘-core [45,53] and 𝑘-truss [12] problems which better captures higher-order structures in graphs. In this problem, a 𝑐-(𝑟, 𝑠) nucleus is defined to be the maximal induced subgraph such that every 𝑟 -clique in the subgraph is contained in at least 𝑐 𝑠-cliques. The goal of the (𝑟, 𝑠) nucleus decomposition problem is to (1) identify for each 𝑟 -clique in the graph, the largest 𝑐 such that it is in a 𝑐-(𝑟, 𝑠) nucleus (known as the coreness value) and (2) generate a nucleus hierarchy over the nuclei, where for 𝑐 ′ < 𝑐 a 𝑐 ′ -(𝑟, 𝑠) nucleus 𝐴 is a descendant of a 𝑐-(𝑟, 𝑠) nucleus 𝐵 if 𝐴 is a subgraph of 𝐵. Figure 1 shows the hierarchy for (1, 3) nucleus. The nucleus hierarchy is an unsupervised method for revealing dense substructures at different resolutions in the graph. Since the hierarchy is a tree, it is easy to visualize and explore as part of structural graph analysis tasks [49].
Sariyüce and Pinar present the first algorithm for solving the nucleus decomposition problem [49]. However, their algorithm is sequential, and in order to scale to the large graph sizes of today, it is important to design parallel algorithms that take advantage of modern parallel hardware. The existing parallel algorithms for nucleus decomposition include those by Sariyüce et al. [51] and by Shi et al. [55], but these algorithms only compute the coreness values. Importantly, they do not generate the hierarchy, which limits their applicability and which is non-trivial to generate in parallel. In this paper, we design the first work-efficient parallel algorithm for hierarchy construction in nucleus decomposition, where the work, or the total number of operations, matches the best sequential time complexity. Our algorithm runs in 𝑂 (𝑚𝛼 𝑠 -2 ) expected work and 𝑂 (𝑘 log 𝑛 + 𝜌 (𝑟,𝑠 ) (𝐺) log 𝑛 + log 2 𝑛) span w.h.p. (parallel time), where 𝛼 is the arboricity of the input graph 𝐺, 𝜌 (𝑟,𝑠 ) (𝐺) is the (𝑟, 𝑠) peeling complexity of 𝐺, and 𝑘 is the maximum (𝑟, 𝑠)-clique core number in 𝐺. The key to our theoretical efficiency is our careful construction of subgraphs representing the 𝑠-clique-connectivity of 𝑟 -cliques, that allows us to exploit linear-work graph connectivity instead of more expensive union-finds as used in prior work. Our approach gives as a byproduct the most theoreticallyefficient serial algorithm for computing the hierarchy, improving upon the previous best known serial bounds by Sariyüce and Pinar [49].
We also present a practical parallel algorithm that interleaves the hierarchy construction with the computation of the coreness values. Prior work by Sariyüce and Pinar [49] also includes a (serial) interleaved hierarchy algorithm. However, their algorithm requires storing all adjacent 𝑟 -cliques with different coreness values, which could potentially be proportional to the number of 𝑠-cliques in 𝐺 (i.e., use 𝑂 (𝑚𝛼 𝑠 -2 ) space), and which results in sequential dependencies in their post-processing step to construct the hierarchy. Our parallel algorithm fully interleaves the hierarchy construction with the coreness computation, and uses only two additional arrays of size proportional to the number of 𝑟 -cliques in 𝐺. Our algorithm uses a concurrent union-find data structure in an innovative way. Also, our post-processing step to construct the hierarchy tree is fully parallel. Our main insight is a technique to fully extract the connectivity information from adjacent 𝑟 -cliques with different core numbers while computing the coreness values.
Note that the span of the above algorithms can be large for graphs with large peeling complexity (𝜌 (𝑟,𝑠 ) (𝐺)). We introduce an approximate algorithm for nucleus decomposition and show that it can achieve work efficiency and polylogarithmic span. Our algorithm relaxes the peeling order by allowing all 𝑟 -cliques within a ( 𝑠 𝑟 + 𝜖) factor of the current value of 𝑘 to be peeled in parallel. We show that our algorithm generates coreness estimates that are an ( 𝑠 𝑟 + 𝜖)-approximation of the true coreness values.
We experimentally study our parallel algorithms on real-world graphs using different (𝑟, 𝑠) values, for up to 𝑟 < 𝑠 ≤ 7. On a 30-core machine with two-way hyper-threading, our exact algorithm which generates both the coreness numbers and the hierarchy achieves up to a 30.96x self-relative parallel speedup, and a 3.76-58.84x speedup over the state-of-the-art sequential algorithm by Sariyüce and Pinar [49]. In addition, we show that on the same machine our approximate algorithm is up to 3.3x faster than our exact algorithm for computing coreness values, while generating coreness estimates with a multiplicative error of 1-2.92x (with a median error of 1.33x). Our algorithms are able to compute the (𝑟, 𝑠) nucleus decomposition hierarchy for 𝑟 > 3 and 𝑠 > 4 on graphs with over a hundred million edges for the first time.
We summarize our contributions below: • The first exact and approximate parallel algorithms for nucleus decomposition that generates the hierarchy with strong theoretical bounds on the work, span, and approximation guarantees. • A number of practical optimizations that lead to fast implementations of our algorithms. • Experiments showing that our new exact algorithm achieves 3.7-58.8x speedups over state of the art on a 30-core machine with two-way hyper-threading. • Experiments showing that our new approximate algorithm achieves up to 3.3x speedups over our exact algorithm, while generating coreness estimates with a multiplicative error of 1-2.9x (with a median error of 1.3x).
Our code is publicly available at https://github.com/jeshi96/arb-nucleus-hierarchy.
The 𝑘-core [45,53] and 𝑘-truss problems [12,65,68] are classic problems relating to dense substructures in graphs. Many algorithms have been developed for 𝑘-cores and 𝑘-trusses in the static [5, 8, 9, 14, 16, 17, 20, 23, 33-35, 42, 46, 58, 62, 64, 69] and dynamic [1, 2, 26-28, 32, 38, 39, 41, 43, 44, 48, 59, 64, 66, 67] settings. Similar ideas have been studied in bipartite graphs [29,36,40,50,57,63].
A related problem is the 𝑘-clique densest subgraph problem [60], which defines the density of subgraphs based on the number of 𝑘-cliques in it, rather than the number of edges. Fang et al. [19] further generalize this notion to arbitrary fixed-sized subgraphs (although they only present experiments for cliques). Similar to 𝑘-core and 𝑘-truss, algorithms for approximating the 𝑘-clique densest subgraph are based on iteratively peeling (removing) elements from the graph. Shi et al. [54] present efficient parallel algorithms for solving the 𝑘-clique densest subgraph problem.
Sariyüce et al. define the (𝑟, 𝑠) nucleus decomposition problem and show that it can be used to find higher quality dense substructures in graphs that previous approaches. They provide efficient sequential [49,52] and parallel algorithms [51] for this problem. Sariyüce et al. [51] present two parallel algorithms for the nucleus decomposition problem: (1) a global peeling-based algorithm and (2) a local update model that iterates until convergence. They also introduce a sequential algorithm for constructing the nucleus decomposition hierarchy [49], but as far as we know there are no parallel algorithms for constructing this hierarchy. Their algorithm is not work-efficient as it uses union-find. We also note that their space-usage can in theory be as large as 𝑂 (𝑛𝛼 𝑠 -2 ), i.e., proportional to the number of 𝑠-cliques in the graph. Chu et al. [11] present a parallel algorithm for generating the 𝑘-core decomposition hierarchy, which is a special case of nucleus decomposition for 𝑟 = 1 and 𝑠 = 2, but their algorithm does not trivially generalize to higher 𝑟 and 𝑠. Their serial and parallel algorithms both use union-find and run in 𝑂 (𝑚𝛼 (𝑛)) work (where 𝛼 (𝑛) is the inverse Ackermann function), which is not work-efficient, and their parallel algorithm has depth that depends on the peeling-complexity of the input. Shi et al. [55] present an improved parallel algorithm for nucleus decomposition, with good theoretical guarantees and practical performance, but it does not generate the hierarchy. Their algorithm is work-efficient, in that it runs in work proportional to enumerating all 𝑠-cliques, i.e., 𝑂 (𝑚𝛼 𝑠 -2 ) work. They leverage a work-efficient parallel clique counting algorithm [54], along with a multi-level hash table structure to store data associated with cliques space efficiently, and techniques for traversing this structure in a cache-friendly manner. More recently, Sariyüce generalizes the 𝑟 -cliques and 𝑠-cliques in nucleus decomposition to any pair of subgraphs [47]. There has also been work on nucleus decomposition in probabilistic graphs [18].
Model of Computation. We use the work-span model of computation for our theoretical analysis, which is a standard model for shared-memory parallel algorithms [15,30]. The work W of an algorithm is the total number of operations, and the span (parallel time) S of an algorithm is the longest dependency path. Using a randomized work-stealing scheduler [7] on P processors, we can obtain a running time of W/P + 𝑂 (S) in expectation. Our goal is to develop work-efficient parallel algorithms under this model, or algorithms with a work complexity that asymptotically matches the best-known sequential time complexity for the given problem. Graph Notation and Definitions. We consider simple and undirected graphs 𝐺 = (𝑉 , 𝐸). We let 𝑛 = |𝑉 | and 𝑚 = |𝐸|. For analysis, we assume 𝑚 = Ω(𝑛). The arboricity (𝜶 ) of a graph is the minimum number of spanning forests needed to cover the graph. 𝛼 is upper bounded by 𝑂 ( √ 𝑚) and lower bounded by Ω(1) [10]. An 𝑘-clique is a set of vertices such that all 𝑘 2 edges exist among them. Enumerating 𝑘-cliques can be done in 𝑂 (𝑚𝛼 𝑘 -2 ) work and 𝑂 (log 2 𝑛) span with high probability (w.h.p.) [54]. 1A 𝑐-(𝑟, 𝑠) nucleus is a maximal subgraph 𝐻 of an undirected graph formed by the union of 𝑠-cliques 𝑆, such that each 𝑟 -clique 𝑅 in 𝐻 has induced 𝑠-clique degree at least 𝑐 (i.e., each 𝑟 -clique is contained within at least 𝑐 induced 𝑠-cliques). The goal of the (𝑟, 𝑠) nucleus decomposition problem is to compute the following: (1) the (𝑟, 𝑠)-clique core number of each 𝑟 -clique 𝑅, or the maximum 𝑐 such that 𝑅 is contained within a 𝑐-(𝑟, 𝑠) nucleus and (2) a hierarchy over the nuclei, where for
In this paper, similar to all prior work on nucleus computations, we take 𝑟 and 𝑠 to be constants and ignore constants depending on these values in our bounds. The 𝑘-core and 𝑘-truss problems correspond to the 𝑘-(1, 2) and 𝑘-(2, 3) nucleus, respectively. Figure 1 shows the hierarchy for (1, 3) nucleus. We call two 𝑟 -cliques 𝑠-clique-adjacent if there exists an 𝑠-clique 𝑆 such that both 𝑟 -cliques are subgraphs of 𝑆. We also define the 𝑠-clique-degree of a 𝑟 -clique 𝑅 to be the number of 𝑠-cliques that 𝑅 is contained within.
We also consider approximate nucleus decompositions in this paper. If the true (𝑟, 𝑠)-clique core number of an 𝑟 -clique 𝑅 is 𝑘 𝑅 , then a 𝛾-approximate (𝑟, 𝑠)-clique core number of 𝑅 is a value that is at least 𝑘 𝑅 and at most 𝛾𝑘 𝑅 , where 𝛾 > 1.
An 𝑎-orientation of an undirected graph is a total ordering on the vertices such that when edges in the graph are directed from vertices lower in the ordering to vertices higher in the ordering, the out-degree of each vertex is bounded by 𝑎. Shi et al. and Besta et al. [4] provide parallel workefficient algorithms for computing an 𝑂 (𝛼)-orientation, which take 𝑂 (𝑚) work and 𝑂 (log 2 𝑛) span.
A connected component in an undirected graph is a maximal subgraph such that all vertices in the subgraph are reachable from one another. Computing the connected components in a graph can be done in 𝑂 (𝑚) work and 𝑂 (log 𝑛) span w.h.p. [22].
A union-find data structure is used to represent collections of sets and supports the following two operations: unite(𝑥,𝑦) joins the sets that contain 𝑥 and 𝑦 and find(𝑥) returns the identifier of the set containing 𝑥. Trees are used to implement union-find data structures, where elements have a parent pointer, and the root of a tree corresponds to the representative of the set. Path compression can be done during unite and find operations to shortcut the pointers of elements traversed to point to the root of the set. We use the concurrent union-find data structure by Jayanti et al. [31].
We use the notation [𝑛] to refer to the range of integers [1, . . . , 𝑛].
Parallel Primitives. We use the following parallel primitives in our algorithms. We use parallel hash tables, which support 𝑛 insertion, deletion, and membership queries, in 𝑂 (𝑛) work and 𝑂 (log 𝑛) span w.h.p. [25]. List ranking takes a linked list as input and returns the distance of each element to the end of the linked list. For a linked list of 𝑛 elements, list ranking can be solved in 𝑂 (𝑛) work and 𝑂 (log 𝑛) span [30]. In our algorithms, we use list ranking to compute a unique identifier for each element in a linked list so that we can write them to an array in parallel.
Compare-and-swap(𝑥, 𝑜𝑙𝑑, 𝑛𝑒𝑤) attempts to atomically write the value 𝑛𝑒𝑤 into memory location 𝑥 if 𝑥 current stores the value 𝑜𝑙𝑑; it returns true if the write succeeds and false otherwise (meaning the value of 𝑥 was changed by another thread after it was read into 𝑜𝑙𝑑). We assume compare-and-swaps take 𝑂 (1) work and span.
A parallel bucketing structure maintains a mapping from identifiers to buckets, which we use to group 𝑟 -cliques according to their incident 𝑠-clique counts [16]. The buckets can change, and the structure can efficiently update these buckets. We take identifiers to be values associated with 𝑟 -cliques, and use the structure to repeatedly extract all 𝑟 -cliques in the minimum bucket, which can cause the buckets of other 𝑟 -cliques to change (other 𝑟 -cliques sharing vertices with extracted 𝑟 -cliques in our algorithm).
We present several novel algorithms for efficient parallel hierarchy construction for (𝑟, 𝑠) nucleus decomposition. The prior state-of-the-art work on parallel (𝑟, 𝑠) nucleus decomposition, arbnucleus [55], only computes the (𝑟, 𝑠)-clique core numbers and does not construct the hierarchy, which is non-trivial to accomplish. We first present in Section 5 a new theoretically efficient parallel hierarchy construction algorithm, arb-nucleus-hierarchy, that given the (𝑟, 𝑠)-clique core numbers from [55], constructs the full hierarchy. In this two-phase algorithm, the hierarchy construction is entirely separate from the computation of the core numbers. The main innovation is a clever technique to store subgraphs corresponding to each (𝑟, 𝑠)-clique core, such that the each subgraph only needs to be materialized when processing the corresponding level in the hierarchy tree. This limits the number of times we must iterate over each 𝑟 -clique, and allows us to use a linear-work connectivity subroutine, giving us our theoretically efficient bounds.
We also present in Section 6 a new parallel approximation algorithm, approx-arb-nucleus, that computes approximate (𝑟, 𝑠)-clique core numbers in polylogarithmic span without increasing the work. Notably, our parallel approximation algorithm is the first to achieve the dual guarantees of work-efficiency and polylogarithmic span. We then combine approx-arb-nucleus with our theoretically efficient hierarchy construction subroutine, to form an approximate hierarchy algorithm, arb-approx-nucleus-hierarchy.
We observe that it is often not practically efficient to conduct a two-phase hierarchy algorithm (separating the hierarchy construction from the computation of the core numbers), and it is instead faster to construct the hierarchy directly while computing the core numbers. However, this presents a new series of challenges, where core numbers obtained later in the algorithm given by [55] may affect all levels of the hierarchy tree, causing significant global changes in the tree structure as core numbers are computed. We present practical solutions in Section 7 limiting the cascading effects of these changes by compactly storing the tree using two simple data structures, a union-find structure and a hash table, and grouping 𝑟 -cliques on-the-fly to reduce the propagating changes. We then introduce an efficient parallel post-processing step, to explicitly construct the final hierarchy tree from the two data structures.
Finally, we implement all of our algorithms, and present a comprehensive experimental evaluation in Section 8.
Algorithm 1 Parallel (𝑟, 𝑠) nucleus hierarchy algorithm 1: Initialize 𝑟 , 𝑠 ⊲ 𝑟 and 𝑠 for (𝑟, 𝑠 ) nucleus decomposition 2: procedure arb-nucleus-hierarchy(𝐺 = (𝑉 , 𝐸 )) 3: 𝑁 𝐷 ← arb-nucleus(𝐺) ⊲ Compute the nucleus core numbers, where 𝑁 𝐷 maps 𝑟 -cliques to their core numbers 4: 𝑘 ← maximum core number in 𝑁 𝐷 5: For each 𝑖 ∈ [𝑘 ], let 𝐿 𝑖 denote a hash table, where the keys are 𝑟 -cliques and the values are linked lists 6: parfor all 𝑠-cliques 𝑆 in 𝐺 do 7: parfor all pairs of 𝑟 -cliques 𝑅, 𝑅 ′ in 𝑆 where 𝑁 𝐷 [𝑅 ′ ] ≤ 𝑁 𝐷 [𝑅 ] do 8: Add 𝑅 ′ to the linked list keyed by 𝑅 in 𝐿 𝑁 𝐷 [𝑅 ′ ] 9: Initialize the hierarchy tree 𝑇 with leaves corresponding to each 𝑟 -clique 10: For each 𝑖 ∈ [𝑘 ], let 𝐼 𝐷 𝑖 denote a hash table, where the keys are 𝑟 -cliques and the values are 𝑟 -cliques 11:
Initialize each 𝐼 𝐷 𝑖 to contain each key in 𝐿 𝑖 , mapped to itself 12:
for 𝑖 ∈ {𝑘, 𝑘 -1, . . . , 1} do 13:
Relabel each 𝑟 -clique in each linked list in 𝐿 𝑖 with its corresponding value in 𝐼 𝐷 𝑖 14:
Apply parallel list ranking to transform the linked lists in 𝐿 𝑖 into arrays, which forms a graph 𝐻 (where the edges are given by each key paired with each element in its corresponding linked list) 15:
Run parallel linear-work connectivity on 𝐻 16:
parfor
Construct a new parent in 𝑇 for all of the nodes corresponding to each 𝑅 ℓ (for ℓ ∈ [𝑐 ]), and represent the parent as the 𝑟 -clique 𝑅 1 18:
parfor each 𝑗 < 𝑖 do 19:
Concatenate in parallel the linked lists corresponding to all 𝑅 ℓ (for ℓ ∈ [𝑐 ]) in 𝐿 𝑗 , as the updated value for the key 𝑅 1 in 𝐿 𝑗 20:
For each 𝑅 ℓ (for ℓ ∈ [𝑐 ]), update the value of 𝑅 ℓ in 𝐼 𝐷 𝑗 to be 𝑅 1
return 𝑇 Fig. 2. An example of the 𝐿 𝑖 data structures maintained by arb-nucleus-hierarchy while computing the (1, 3)-nucleus hierarchy on the graph in Figure 1. For each round 𝑖 of the hierarchy construction, the connected components of 𝐻 and the 𝐼𝐷 𝑖 table used to construct 𝐻 is shown (except 𝐼𝐷 4 , which maps every 𝑟 -clique to itself).
We now describe our theoretically efficient parallel nucleus decomposition hierarchy algorithm, arb-nucleus-hierarchy. arb-nucleus-hierarchy computes the hierarchy by first running an efficient parallel nucleus decomposition algorithm, arb-nucleus [55], in order to obtain the (𝑟, 𝑠)clique core numbers corresponding to each 𝑟 -clique. It then constructs a data structure consisting of 𝑘 levels, where 𝑘 is the maximum (𝑟, 𝑠)-clique core number. Each level is represented by a hash table mapping sets of 𝑟 -cliques to a linked list of 𝑟 -cliques, which is used to efficiently store 𝑠-clique-adjacent 𝑟 -cliques. arb-nucleus-hierarchy proceeds in levels through this data structure to construct the hierarchy tree from the bottom up, by performing linear-work connectivity on each level and updating the connectivity information in prior levels as a result.
Parallel Algorithms for Hierarchical Nucleus Decomposition 32:7 Fig. 3. An example of the intermediate hierarchy trees 𝑇 after each round 𝑖 in arb-nucleus-hierarchy, while computing the (1, 3)-nucleus hierarchy on the graph in Figure 1.
Our Algorithm. We now provide a more detailed description of our algorithm. The pseudocode is in Algorithm 1. Note that we have highlighted in blue the parts that derive directly from prior work; the remaining pseudocode is novel to this paper. We refer to the example of (1, 3)-nucleus decomposition in Figure 1. For simplicity, we have omitted labeling some of the vertices in the graph, and do not include them in our discussion. The number in front of each vertex label is its core number. arb-nucleus-hierarchy first calls arb-nucleus on Line 3, to compute the (𝑟, 𝑠)-clique core numbers of each 𝑟 -clique. Note that this is the only instance where arb-nucleus-hierarchy uses a subroutine from the prior work [55], and the rest of the pseudocode is novel. It stores these values in a hash table, 𝑁 𝐷, keyed by the 𝑟 -cliques. Then, it constructs a data structure consisting of 𝑘 hash tables on Line 5, where 𝑘 is the maximum (𝑟, 𝑠)-clique core number. Each hash table, 𝐿 𝑖 , maps 𝑟 -cliques to a linked list of 𝑟 -cliques, where 𝑖 corresponds to a core number. The first stage of arb-nucleus-hierarchy inserts all 𝑠-clique-adjacent 𝑟 -cliques into the hash tables on Lines 6-8. Specifically, for adjacent 𝑟 -cliques 𝑅 and 𝑅 ′ where 𝑁 𝐷 [𝑅 ′ ] ≤ 𝑁 𝐷 [𝑅], we insert 𝑅 ′ into the hash table corresponding to 𝑅 ′ 's core number, 𝐿 𝑁 𝐷 [𝑅 ′ ] , with {𝑅} as the key. If an entry for {𝑅} already exists in 𝐿 𝑁 𝐷 [𝑅 ′ ] , we append 𝑅 ′ to the existing linked list. The hash tables are shown in Figure 2. For instance, 𝑅 ′ = 1𝑎 is adjacent to 𝑅 = 3𝑎, so we add 1𝑎 to the linked list keyed by 3𝑎 in 𝐿 1 . In order to iterate in parallel over all 𝑟 -cliques and over all 𝑠-cliques containing each 𝑟 -clique, our algorithm uses a 𝑠-clique enumeration algorithm based on previous work by Shi et al. [54], which recursively finds and lists 𝑐-cliques in parallel and which can efficiently extend given 𝑟 -cliques to find the 𝑠-cliques they are contained within. arb-nucleus-hierarchy then takes all combinations of 𝑟 vertices in each discovered 𝑠-clique to find adjacent 𝑟 -cliques in Lines 7-8. Note that this 𝑠-clique enumeration subroutine is already used in arb-nucleus in order to compute the (𝑟, 𝑠)-clique core numbers of each 𝑟 -clique, and in practice, we construct the hash tables 𝐿 𝑖 while computing the core numbers in arb-nucleus (rather than running the 𝑠-clique enumeration subroutine twice).
After constructing the initial set of hash tables, arb-nucleus-hierarchy proceeds to construct the nucleus decomposition hierarchy on Lines 9-20. The broad idea is to construct the hierarchy starting at the leaf nodes, each of which correspond to an 𝑟 -clique, and to merge tree nodes from the bottom up (i.e., in decreasing order of core number). The algorithm begins by considering only connected components formed by 𝑟 -cliques with the greatest core number, 𝑘, which dictate the leaf nodes to be merged into super-nodes at the second-to-last level of the hierarchy tree based on their 𝑠-clique connectivity. In subsequent rounds, when processing core number 𝑖, the algorithm considers connected components formed by 𝑟 -cliques with core numbers ≥ 𝑖, which similarly dictate the merges to be performed in the next level of the hierarchy tree. arb-nucleus-hierarchy efficiently maintains connected components from higher core numbers when computing connected components at lower core numbers, by concatenating the relevant linked lists in the hash tables corresponding to the lower core numbers when processing higher core numbers. Figure 3 shows the construction of this hierarchy throughout the different rounds (for 𝑖 = 4, . . . , 1), and Figure 2 lists the connected components computed in each round. In our example, since we omit the other vertices in the 4-(1, 3)-nucleus besides 4𝑎, 4𝑏, 4𝑐, and 4𝑑 (for simplicity), we begin with singleton leaf nodes after processing round 𝑖 = 4.
In more detail, on Line 9, we begin with a hierarchy tree 𝑇 consisting only of leaf nodes corresponding to each 𝑟 -clique. We also initialize a data structure consisting of 𝑘 hash tables on Lines 10-11, where each hash table 𝐼 𝐷 𝑖 maps 𝑟 -cliques to 𝑟 -cliques. The idea is to maintain a mapping of each 𝑟 -clique to the component that it is contained within in 𝐿 𝑖 , for the corresponding level. Initially, each 𝐼𝐷 𝑖 maps each key in 𝐿 𝑖 to itself.
Then, arb-nucleus-hierarchy considers each core number 𝑖, starting from 𝑘 and going down to 1 (Line 12). For each 𝑖, we relabel each 𝑟 -clique in each linked list in 𝐿 𝑖 with its corresponding value in 𝐼 𝐷 𝑖 (Line 13). Then, it uses parallel list ranking to convert all linked lists in 𝐿 𝑖 to arrays, forming a graph 𝐻 , where edges are given by each key paired with each element in its corresponding linked list (Line 14). Note that the edges actually denote 𝑠-clique-adjacent 𝑟 -cliques (or components of 𝑟 -cliques). The vertices correspond to 𝑟 -cliques, which represent components of 𝑟 -cliques in 𝐺. In our example, we note that there is nothing to be done for round 𝑖 = 4, since 𝐿 4 is empty. Therefore, we begin by processing the hash table 𝐿 3 in round 𝑖 = 3. 𝐼 𝐷 3 maps every vertex to itself, so we do not relabel any of the labels in 𝐿 3 . The graph 𝐻 that we construct consists of the vertices 3𝑎, 3𝑏, 3𝑐, 4𝑎, 4𝑏, and 4𝑐, with edges given by {3𝑎, 3𝑏, 3𝑐} × {4𝑎, 4𝑏, 4𝑐}.
arb-nucleus-hierarchy proceeds by running a linear-work parallel connectivity algorithm on 𝐻 (Line 15), and processes the given connected components. Note that each connected component 𝐶 consists of a set of vertices in 𝐻 , which represents a set of 𝑟 -cliques, say {𝑅 1 , . . . , 𝑅 𝑐 }. In our example, in round 𝑖 = 3, we have a single connected component in 𝐻 consisting of all of the vertices, 3𝑎, 3𝑏, 3𝑐, 4𝑎, 4𝑏, and 4𝑐. Then, for each such connected component representing more than one 𝑟 -clique, in the hierarchy tree 𝑇 , we construct a new parent for the nodes corresponding to each 𝑅 ℓ for ℓ ∈ [𝑐] (Line 17). Note that each 𝑅 ℓ could correspond to a subtree containing multiple tree nodes, owing to parent nodes constructed in previous steps. We represent the new parent by the 𝑟 -clique 𝑅 1 , which we designate arbitrarily as the representative for the connected component 𝐶. In Figure 3, under 𝑖 = 3, we construct a new parent node labeled by 3𝑎, which we designate as the representative of the component {3𝑎, 3𝑏, 3𝑐, 4𝑎, 4𝑏, 4𝑐}.
Finally, for each core number 𝑗 < 𝑖, we update the connectivity information on each hash table 𝐿 𝑗 , by concatenating all linked lists in 𝐿 𝑗 corresponding to the 𝑟 -cliques in the component 𝐶 (Line 19). More precisely, we update the value of the key 𝑅 1 to be the concatenation, or we insert the concatenation into 𝐿 𝑗 with 𝑅 1 as the key if 𝑅 1 does not already exist in the hash table (this is possible if 𝑅 1 had no neighbors with core number 𝑗). We use tombstones to delete the other keys 𝑅 ℓ (ℓ ≠ 1) in each 𝐿 𝑗 . Additionally, on Line 20, we update the component ID in 𝐼 𝐷 𝑗 of each 𝑅 ℓ to be 𝑅 1 . For 𝑖 = 3, we see that in our example there are no lists to concatenate, but in 𝐼 𝐷 2 , we map each of 3𝑏, 3𝑐, 4𝑎, 4𝑏, and 4𝑐 to the representative 3𝑎.
We repeat this process until we have processed all 𝑘 rounds. In our example, for round 𝑖 = 2, we relabel 4𝑐 in 𝐿 2 with 3𝑎, as given by 𝐼 𝐷 2 , and we construct a subgraph 𝐻 with vertices 2𝑎, 3𝑎, and 4𝑑, and edges (2𝑎, 3𝑎) and (2𝑎, 4𝑑). Again, there is only one connected component, given by {2𝑎, 3𝑎, 4𝑑 }. In the hierarchy tree for round 𝑖 = 2, we construct a new parent labeled with the representative 2𝑎, whose children are the leaves 2𝑎 and 4𝑑, and the previously constructed parent node 3𝑎. Again, there are no lists to concatenate in 𝐿 1 , but in 𝐼 𝐷 1 , we map both 3𝑎 and 4𝑑 to the representative 2𝑎. Then, for round 𝑖 = 1, we relabel 3𝑎 in 𝐿 1 with 2𝑎, as given by 𝐼 𝐷 1 . We construct a subgraph 𝐻 with vertices 1𝑎 and 2𝑎, and a single edge between them. There is only one connected component, {1𝑎, 2𝑎}, and in the hierarchy tree for round 𝑖 = 1, we construct a new parent labeled with the representative 1𝑎, whose children are the leaf 1𝑎 and the previously constructed parent node 2𝑎. This concludes the construction of the hierarchy 𝑇 in our example.
Parallel Algorithms for Hierarchical Nucleus Decomposition 32:9
Theoretical Efficiency. We now analyze the theoretical efficiency of our hierarchy algorithm, arb-nucleus-hierarchy. Note that as in Shi et al.'s [55] work, 𝜌 (𝑟,𝑠 ) (𝐺) is defined to be the (𝒓, 𝒔) peeling complexity of 𝐺, or the number of rounds needed to peel the graph where in each round, all 𝑟 -cliques with the minimum 𝑠-clique count are peeled (removed). Importantly, 𝑘 ≤ 𝜌 (𝑟,𝑠 ) (𝐺) ≤ 𝑂 (𝑚𝛼 𝑟 -2 ), since at least one 𝑟 -clique is peeled in each round, and the number of rounds is at least the maximum (𝑟, 𝑠)-clique core number in 𝐺.
Theorem 5.1. arb-nucleus-hierarchy computes the (𝑟, 𝑠) nucleus decomposition hierarchy in 𝑂 (𝑚𝛼 𝑠 -2 ) expected work and 𝑂 (𝑘 log 𝑛 + 𝜌 (𝑟,𝑠 ) (𝐺) log 𝑛 + log 2 𝑛) span w.h.p., where 𝜌 (𝑟,𝑠 ) (𝐺) is the (𝑟, 𝑠) peeling complexity and 𝑘 is the maximum (𝑟, 𝑠)-clique core number.
Proof. First, the theoretical complexity of computing the (𝑟, 𝑠)-clique core numbers of each 𝑟 -clique (Line 3) is given by Shi et al. [55], which they show takes 𝑂 (𝑚𝛼 𝑠 -2 ) work and 𝑂 (𝜌 (𝑟,𝑠 ) (𝐺) log 𝑛 + log 2 𝑛) span w.h.p. for constant 𝑟 and 𝑠. Note that the work bound is given by the version of their algorithm that takes space proportional to the number of 𝑠-cliques in 𝐺, which we incur regardless to store the hash tables 𝐿 𝑖 . Additionally, iterating through all 𝑠-cliques in 𝐺 (Line 6) is superseded by the work required to compute the (𝑟, 𝑠)-clique core numbers. For every pair of 𝑟 -cliques in each 𝑠-cliques, we hash each 𝑟 -clique and append to a linked list (Lines 7-8), which in total takes 𝑂 (𝑚𝛼 𝑠 -2 ) work and 𝑂 (log 2 𝑛) span w.h.p. for constant 𝑟 and 𝑠.
We now discuss the work and span of constructing the hierarchy tree 𝑇 level-by-level, in 𝑘 rounds (Lines 12-20). The key idea here is that the linked lists in each hash table 𝐿 𝑖 are iterated over at most once across all rounds, and the concatenation of linked lists in intermediate rounds incurs minimal costs (since concatenating linked lists does not require iterating through the linked lists). The sum of the lengths of the linked lists in each 𝐿 𝑖 remains invariant throughout this portion of the construction, so in total, the cost of iterating over the linked lists is bounded by 𝑂 (𝑚𝛼 𝑠 -2 ) work, matching the work needed to construct each linked list in each 𝐿 𝑖 originally. Also, the number of keys in each 𝐿 𝑖 only monotonically decreases, so processing the connected components of the constructed subgraphs 𝐻 takes at most 𝑂 (𝑚𝛼 𝑠 -2 ) work as well.
In more detail, for fixed 𝑖, let the sum of the lengths of the linked lists in 𝐿 𝑖 be ℓ 𝑖 , and let the number of keys in 𝐿 𝑖 be 𝑦 𝑖 . For each round 𝑖 ∈ [𝑘], applying 𝐼 𝐷 𝑖 and parallel list ranking on the linked lists in 𝐿 𝑖 (Lines 13-14) takes work proportional to ℓ 𝑖 and 𝑂 (log 𝑛) span w.h.p.. The number of edges in the subgraph 𝐻 constructed from the linked lists in 𝐿 𝑖 is at most ℓ 𝑖 , so performing connectivity on 𝐻 (Line 15) takes work linear in ℓ 𝑖 and 𝑂 (log 𝑛) span w.h.p. [22]. Also, there are at most 𝑂 (𝑦 𝑖 ) vertices in 𝐻 , so processing each connected component and updating the hierarchy tree 𝑇 (Line 17) takes 𝑂 (𝑦 𝑖 ) work and 𝑂 (1) span. In total, for Lines 13-17, we incur 𝑂 ( 𝑖 (ℓ 𝑖 + 𝑦 𝑖 )) = 𝑂 (𝑚𝛼 𝑠 -2 ) expected work and 𝑂 (𝑘 log 𝑛) span w.h.p.
It remains to bound the cost of of the loop in Lines 18-20. First, note that across all rounds, each value corresponding to every key in each 𝐿 𝑖 is concatenated at most once (Line 19). This is because we concatenate linked lists and store the concatenation under exactly one existing key. We empty the corresponding values for the previously associated keys, which allows us to maintain the invariant that the sum of the lengths of the linked lists in each 𝐿 𝑖 remains fixed. Also, the previously associated keys are never used again, since we update the value associated with each 𝑟 -clique in 𝐼 𝐷 𝑗 . Thus, the concatenations are bounded by 𝑂 (𝑚𝛼 𝑠 -2 ) work across all rounds, matching the work of constructing all 𝐿 𝑖 . Additionally, iterating through all levels 𝑗 ≤ 𝑖 for each component C does not increase the work. This is because we only reach this loop if |C| ≥ 2, which means that we are effectively merging multiple 𝑟 -cliques together in each hash table 𝐿 𝑗 for 𝑗 ≤ 𝑖, and assigning the 𝑟 -clique 𝑅 1 as the new representative for the other 𝑟 -cliques in the component (updating 𝐼 𝐷 𝑗 ). Thus, we can assign the work of iterating through all 𝑗 ≤ 𝑖 to the 𝑟 -cliques that are being merged (𝑅 ℓ where ℓ ≠ 1). Once the 𝑟 -clique 𝑅 ℓ is merged, due to the concatenation on Line 19 and the update in 𝐼 𝐷 𝑗 on Line 20, it never participates as a vertex in 𝐻 again in future rounds, so is never re-processed in a future connected component of 𝐻 ; this is due to the mapping on Line 13. The amount of work that we assign per merged 𝑟 -clique 𝑅 ℓ is at most the core number of 𝑅 ℓ . This is because the amount of work we assign to 𝑅 ℓ is given by the number of rounds in which we merge, or 𝑖, and 𝑅 ℓ only appears in 𝐿 𝑖 if 𝑁 𝐷 [𝑅 ℓ ] ≥ 𝑖, by construction on Line 8. Thus, in total, for each 𝑟 -clique, we incur work upper bounded by the core number. We have in total 𝑂 ( 𝑟 -clique 𝑅 ∈𝐺 𝑁 𝐷 [𝑅]) = 𝑂 (𝑚𝛼 𝑠 -2 ) work, since the sum of the (𝑟, 𝑠)-clique core numbers in 𝐺 is necessarily bounded by the number of 𝑠-cliques for constant 𝑟 and 𝑠. This is because each 𝑠-clique contributes to at most 𝑠 𝑟 𝑟 -clique's core numbers, so the summation across all core numbers is upper bounded by 𝑠 𝑟 • (the number of 𝑠-cliques). Thus, in total, the loop in Lines 18-20 incurs 𝑂 (𝑚𝛼 𝑠 -2 ) work and 𝑂 (𝑘 log 𝑛) span, where the span is due to list ranking.
In total, we have 𝑂 (𝑚𝛼 𝑠 -2 ) expected work and 𝑂 (𝑘 log 𝑛 + 𝜌 (𝑟,𝑠 ) (𝐺) log 𝑛 + log 2 𝑛) span w.h.p., as desired. □
Comparison to Prior Work. The prior state-of-the-art algorithm is the sequential (𝑟, 𝑠) nucleus decomposition hierarchy algorithm by Sariyüce and Pinar [49]. They provide an algorithm similar to arb-nucleus-hierarchy in that it first computes the (𝑟, 𝑠)-clique core numbers of each 𝑟 -clique, and then builds the hierarchy tree from the bottom up. They show that the time complexity is upper bounded by the time complexity of computing the (𝑟, 𝑠)-clique core numbers. Note that they omit a factor of 𝑂 (𝛼 (𝑛 𝑠 , 𝑛 𝑟 )) where 𝛼 is the inverse Ackermann function and 𝑛 𝑠 and 𝑛 𝑟 are the number of 𝑠-cliques and 𝑟 -cliques, respectively, in the graph; this factor is necessary for their algorithm, since they use union-find to construct the hierarchy tree. Thus, the time complexity of Sariyüce and Pinar's algorithm is 𝑂 (𝑚𝛼 𝑠 -2 𝛼 (𝑛 𝑠 , 𝑛 𝑟 )) (this is achieved using the state-of-the-art algorithm for computing the (𝑟, 𝑠)-clique core numbers [55]). Our arb-nucleus-hierarchy algorithm avoids the additional inverse Ackermann factor, by efficiently constructing graphs to represent different levels of the hierarchy tree and using linear-work graph connectivity to construct the hierarchy tree. Thus, we improve the sequential running time of constructing the (𝑟, 𝑠) nucleus decomposition hierarchy to 𝑂 (𝑚𝛼 𝑠 -2 ), and arb-nucleus-hierarchy is work-efficient. Shi et al. [55] present a parallel algorithm to compute the (𝑟, 𝑠)-clique core numbers in 𝑂 (𝑚𝛼 𝑠 -2 ) expected work. A vanilla extension of their algorithm to compute the hierarchy would be to run connected components for each non-empty core number 𝑖, with vertices being the (𝑟, 𝑠)-cliques that have core number 𝑖 or above, in a top-down manner. This incurs 𝑂 (𝑚𝛼 𝑠 -2 ) expected work per level, and there can be 𝜌 (𝑟,𝑠 ) (𝐺) levels in the worst case, leading to 𝑂 (𝜌 (𝑟,𝑠 ) (𝐺)𝑚𝛼 𝑠 -2 ) total expected work. In contrast, our algorithm has a much lower total expected work of 𝑂 (𝑚𝛼 𝑠 -2 ).
Given the potentially large span (i.e., longest critical path) of computing the exact nucleus decomposition hierarchy, we develop a new parallel approximate nucleus decomposition hierarchy algorithm, arb-approx-nucleus-hierarchy. Instead of computing exact (𝑟, 𝑠)-clique-core numbers of each 𝑟 -clique, the main idea of the new algorithm is to compute an approximation of the (𝑟, 𝑠)-clique core number. Specifically, we compute a ( 𝑠 𝑟 +𝜀)-approximate (𝑟, 𝑠)-clique core number of each 𝑟 -clique; that is to say, if we let the true (𝑟, 𝑠)-clique core number of each 𝑟 -clique be 𝑘 𝑅 , our approximation is at least 𝑘 𝑅 and at most ( 𝑠 𝑟 + 𝜀) • 𝑘 𝑅 . Our approximate computation uses the same peeling paradigm from Shi et al. [55] for exact nucleus decomposition, but with an important modification that allows it to take only 𝑂 (log 2 𝑛) peeling rounds, thus significantly improving upon the span. As a result, we only have polylogarithmically many core numbers, leading to a hierarchy tree with polylogarithmic height. Our hierarchy construction for arb-approx-nucleus-hierarchy is exactly the same as that of arb-nucleushierarchy, and the only salient difference is that for arb-approx-nucleus-hierarchy, we replace the arb-nucleus subroutine in Line 3 of Algorithm 1 with our approximate nucleus decomposition subroutine, approx-arb-nucleus. Our Algorithm. We present our pseudocode for approx-arb-nucleus in Algorithm 2. Again, we have highlighted in blue the parts that derive directly from prior work, and the remainder is novel to this work. Note that it takes as input a parameter 𝛿 > 0, which controls the 𝜀 in the ( 𝑠 𝑟 + 𝜀)approximation. Specifically, approx-arb-nucleus gives a ( 𝑠 𝑟 +𝛿) • (1+𝛿) = ( 𝑠 𝑟 +𝜀)-approximation, which we prove in Theorem 6.1.
First, on Line 3, approx-arb-nucleus computes a low out-degree orientation of the graph 𝐺, which directs the edges such that every vertex has out-degree at most 𝑂 (𝛼), using an efficient algorithm by Shi et al. [54]. Then, on Lines 4-5, it counts the number of 𝑠-cliques per 𝑟 -clique in 𝐺, and stores the result in a parallel hash table 𝑈 . It uses an 𝑠-clique counting subroutine, rec-listcliqes, from Shi et al.'s previous work [54]. The key difference between approx-arb-nucleus and arb-nucleus is on Line 6, where the buckets in the bucketing structure hold 𝑟 -cliques with a range of 𝑠-clique-degrees instead of a single 𝑠-clique-degree. Specifically, for an input parameter 𝛿, we define the range of each bucket 𝐵 𝑖 to be
) is a trivial upper bound on the maximum 𝑠-clique-degree possible in any given graph.
The peeling algorithm then proceeds as it does in [55], except using our modified bucketing structure. While not all 𝑟 -cliques have been peeled, approx-arb-nucleus processes the set of 𝑟 -cliques 𝐴 (that have not yet been peeled) within the lowest bucket 𝐵 𝑖 (starting with 𝑖 = 0), and peels them from the graph (Lines 8-20). For each 𝑟 -clique 𝑅 in 𝐴, we iterate over all 𝑠-clique-adjacent 𝑟 -cliques 𝑅 ′ , and update the recorded 𝑠-clique-degree of 𝑅 ′ given 𝑅's removal (Lines 12-15). Then, we peel (remove) the 𝑟 -cliques in 𝐴 from the graph and update the buckets of all unpeeled 𝑟 -cliques based on the updated 𝑠-clique-degrees on Line 16. Notably, if a 𝑟 -clique 𝑅's 𝑠-clique-degree falls below the range of the current bucket of 𝑟 -cliques that is being peeled, we do not rebucket 𝑅 into a lower bucket, and instead aggregate these 𝑟 -cliques within the current bucket. As such, in any given round of peeling, we are actually peeling all 𝑟 -cliques with 𝑠-clique-degree ≤ ( 𝑠 𝑟 + 𝛿) • (1 + 𝛿) 𝑖 , which is important for our theoretical bounds. Note that we process a given bucket 𝐵 𝑖 at most 𝑂 (log 1+ 𝛿/( 𝑠 𝑟 ) (𝑛)) times; if we have exceeded this threshold, or if 𝐵 𝑖 is empty, then we move on to processing the next bucket, 𝐵 𝑖+1 (Lines 17-20). If there are unpeeled 𝑟 -cliques remaining in 𝐵 𝑖 once we reach this threshold, we include them in the next bucket 𝐵 𝑖+1 (Line 18). Note that the approximate (𝑟, 𝑠)-clique core number that we compute for each 𝑟 -clique is given by the upper bound of the bucket in which it was peeled. In practice, we can improve this by taking the minimum of the upper bound of the bucket, and the 𝑠-clique-degree of each 𝑟 -clique (in the original graph).
Once we have peeled all 𝑟 -cliques, this concludes our subroutine. arb-approx-nucleus-hierarchy is then given by replacing arb-nucleus in Line 3 of Algorithm 1 with approx-arb-nucleus. Theoretical Guarantees and Efficiency. We now discuss the theoretical guarantees and theoretical efficiency of approx-arb-nucleus, and by extension, arb-approx-nucleus-hierarchy.
The main idea is to bound the proportion of 𝑟 -cliques with core numbers ≤ ℓ for some fixed ℓ, but with 𝑠-clique-degree > ℓ ( 𝑠 𝑟 + 𝛿). We can then set ℓ such that at any given step of our peeling process, we obtain a bound on the maximum proportion of 𝑟 -cliques with core number at most ℓ that is not within the current bucket to be peeled. In essence, this gives us a bound on the number of times that a bucket must be reprocessed, such that moving on to the next bucket does not degrade the approximation factor, which gives us our approximation guarantees. Due to space constraints, we defer the proof of the following theorem to the full paper [56].
Algorithm 2 Approximate parallel (𝑟, 𝑠) nucleus algorithm 1: Initialize 𝑟 , 𝑠 ⊲ 𝑟 and 𝑠 for (𝑟, 𝑠 ) nucleus decomposition 2: procedure approx-arb-nucleus(𝐺 = (𝑉 , 𝐸 ), 𝛿) 3: 𝐷𝐺 ← Arb-Orient(𝐺) ⊲ Apply an arboricity-orientation algorithm 4: Initialize 𝑈 to be a parallel hash table with 𝑟 -cliques as keys, and 𝑠-clique counts as values 5: rec-list-cliqes(𝐷𝐺, 𝑠, 𝑈 ) ⊲ Count 𝑠-cliques, and store the counts per 𝑟 -clique in 𝑈 6: Let 𝑁 𝐷 be a bucketing structure mapping each 𝑟 -clique to a bucket based on # of 𝑠-cliques, where each bucket 𝐵 𝑖 contain all 𝑟 -cliques with 𝑠-clique-degree in the range [ ( 𝑠 𝑟 +𝛿 ) • (1+𝛿 ) 𝑖 , ( 𝑠 𝑟 +𝛿 ) • (1+𝛿 ) 𝑖+1 ], for all 𝑖 ∈ [𝑠 log ( 𝑠 𝑟 )+𝛿 𝑛] 7: finished ← 0, num_rounds ← 0, 𝑖 ← 0 8: while finished < |𝑈 | do 9: 𝐴 ← 𝑟 -cliques in the bucket 𝐵 𝑖 in 𝑁 𝐷 (to be peeled) 10: finished ← finished + |𝐴| 11: num_rounds ← num_rounds + 1 12: parfor all 𝑟 -cliques 𝑅 in 𝐴 do 13: parfor all 𝑠-cliques 𝑆 containing 𝑅 do 14: parfor all 𝑟 -cliques 𝑅 ′ in 𝑆 where 𝑅 ′ ≠ 𝑅 do 15: Update 𝑠-clique count of 𝑅 ′ in 𝑈 16: Peel 𝐴, assign the upper bound of the bucket as the coreness value for peeled 𝑟 -cliques, and update the buckets of 𝑟 -cliques with updated 𝑠-clique counts 17: if num_rounds ≥ 𝑂 (log 1+ 𝛿/ ( 𝑠 𝑟 ) (𝑛) ) or 𝐵 𝑖 is empty then 18: Add the remaining 𝑟 -cliques in 𝐵 𝑖 (if it is non-empty) to 𝐵 𝑖+1 19: 𝑖 ← 𝑖 + 1 20: num_rounds ← 0 21: return 𝑁 𝐷 Theorem 6.1. arb-approx-nucleus-hierarchy computes a ( 𝑠 𝑟 + 𝜀)-approximate (𝑟, 𝑠) nucleus decomposition hierarchy in 𝑂 (𝑚𝛼 𝑠 -2 ) expected work and 𝑂 (log 3 𝑛) span w.h.p.
Note that in the theorem above, 𝜖 does not affect the work bound, and affects the base of one of the logarithms in the span bound (which we omitted as we treat 𝜖 as a constant).
While the algorithm presented in Section 5 (Algorithm 1) is efficient in theory, we present a number of optimizations that improve its practical performance. Algorithm 1 requires two passes over the 𝑟 -cliques and their 𝑠-clique-adjacent neighbors, first to compute the (𝑟, 𝑠)-clique core numbers and then to construct the hierarchy. We present algorithms that interleave these two computations, so that only a single pass is required. Specifically, we present two algorithms that are not as theoretically efficient as Algorithm 1, but are faster in practice, particularly when the difference between 𝑟 and 𝑠 is large, as we demonstrate in Section 8.1.
Our algorithms use the same framework, given in Algorithm 3, and the main difference between the two algorithms is the implementation of the key subroutines link and construct-tree. The framework is based on the peeling process used to compute the (𝑟, 𝑠)-clique core numbers in Shi et al.'s work [55]. The main idea is that when we peel an 𝑟 -clique 𝑅, while computing the updated 𝑠-clique counts due to peeling 𝑅, we are already iterating over all 𝑠-clique-adjacent 𝑟 -cliques 𝑅 ′ . Note that additionally, the nucleus decomposition algorithm in Shi et al. [55] uses a bucketing structure that maintains the intermediate (𝑟, 𝑠)-clique core numbers of each 𝑟 -clique throughout the peeling process (which begin as simply the 𝑠-clique count of each 𝑟 -clique, and throughout the peeling process are updated to the actual (𝑟, 𝑠)-clique core numbers). Then, if the intermediate (𝑟, 𝑠)-clique core number of 𝑅 ′ is less than or equal to that of 𝑅, as maintained in the bucketing structure, the intermediate (𝑟, 𝑠)-clique core numbers of 𝑅 and 𝑅 ′ are actually the final (𝑟, 𝑠)-clique
Parallel Algorithms for Hierarchical Nucleus Decomposition 32:13 Algorithm 3 Parallel (𝑟, 𝑠) nucleus hierarchy framework 1: Initialize 𝑟 , 𝑠 ⊲ 𝑟 and 𝑠 for (𝑟, 𝑠 ) nucleus decomposition 2: procedure arb-nucleus-decomp-hierarchy-framework(𝐺 = (𝑉 , 𝐸 )) 3: 𝐷𝐺 ← Arb-Orient(𝐺) ⊲ Apply an arboricity-orientation algorithm 4: Initialize 𝑈 to be a parallel hash table with 𝑟 -cliques as keys, and 𝑠-clique counts as values 5: rec-list-cliqes(𝐷𝐺, 𝑠, 𝑈 ) ⊲ Count 𝑠-cliques, and store the counts per 𝑟 -clique in 𝑈 6: Let 𝑁 𝐷 be a bucketing structure mapping each 𝑟 -clique to a bucket based on # of 𝑠-cliques 7: finished ← 0 8: while finished < |𝑈 | do 9: 𝐴 ← 𝑟 -cliques in the next bucket in 𝑁 𝐷 (to be peeled) 10: finished ← finished + |𝐴| 11: parfor all 𝑟 -cliques 𝑅 in 𝐴 do 12: parfor all 𝑠-cliques 𝑆 containing 𝑅 do 13: parfor all 𝑟 -cliques 𝑅 ′ in 𝑆 where 𝑅 ′ ≠ 𝑅 do 14: if 𝑁 𝐷 [𝑅 ′ ] ≤ 𝑁 𝐷 [𝑅 ] then 15: link(𝑅 ′ , 𝑅, 𝑁 𝐷 ) 16: else Update 𝑠-clique count of 𝑅 ′ in 𝑈 17: Update the buckets of 𝑟 -cliques with updated 𝑠-clique counts, peeling 𝐴 18:
return construct-tree(𝑁 𝐷) ⊲ Return the hierarchy tree 𝑇 , constructed based on link core numbers of 𝑅 and 𝑅 ′ , respectively. Thus, each such 𝑅 and 𝑅 ′ pair are connected in the nucleus decomposition hierarchy up to the level given by min(𝑁 𝐷 [𝑅], 𝑁 𝐷 [𝑅 ′ ]), and after the peeling process completes, we will have all of the relevant connectivity information to completely compute the nucleus decomposition hierarchy. In this sense, it suffices to define a link subroutine to process the 𝑠-clique-adjacent 𝑟 -cliques given the intermediate (𝑟, 𝑠)-clique core numbers throughout the peeling algorithm. Based on link, construct-tree constructs the final hierarchy tree.
In more detail, arb-nucleus-decomp-hierarchy-framework first uses an efficient low outdegree orientation algorithm by Shi et al. [54] to direct the graph 𝐺 such that every vertex has out-degree at most 𝑂 (𝛼) (Line 3). Then, it counts the number of 𝑠-cliques per 𝑟 -clique in 𝐺 and stores the counts in a parallel hash table 𝑈 , where the keys are 𝑟 -cliques and the values are the counts (Lines 4-5). Note that arb-nucleus-decomp-hierarchy-framework uses a subroutine rec-list-cliqes based on previous work by Shi et al. [54], to count the number of 𝑠-cliques per 𝑟 -clique. Also, our algorithm initializes a parallel bucketing structure 𝑁 𝐷 that maps 𝑟 -cliques to buckets, initially based on their 𝑠-clique counts (Line 6). We use the bucketing structure by Dhulipala et al. [16]. This structure 𝑁 𝐷 stores the aforementioned intermediate (𝑟, 𝑠)-clique core numbers of each 𝑟 -clique, and supports efficient operations to update buckets and return the lowest unpeeled bucket. Our algorithm then proceeds with a classic peeling paradigm, where until all 𝑟 -cliques have been peeled, it processes the 𝑟 -cliques (that have not yet been peeled) incident to the lowest number of 𝑠-cliques and peels them from the graph (Lines 8-17). For a set 𝐴 of 𝑟 -cliques with the lowest number of incident 𝑠-cliques (Line 9), we iterate over all 𝑠-clique-adjacent 𝑟 -cliques 𝑅 ′ to each 𝑟 -clique 𝑅 in 𝐴 (Lines 11-13).
Note that if 𝑁 𝐷 [𝑅 ′ ] ≤ 𝑁 𝐷 [𝑅], this means that 𝑅 ′ was either previously peeled or is currently being peeled (and is also in 𝐴); this is because at any given peeling step, we process the bucket of unpeeled 𝑟 -cliques with the minimum incident 𝑠-clique count. This also means that 𝑁 𝐷 [𝑅 ′ ] and 𝑁 𝐷 [𝑅] are the actual (𝑟, 𝑠)-clique core numbers of 𝑅 ′ and 𝑅 respectively, which follows directly from the correctness of the peeling paradigm [52]. Thus, each such 𝑅 and 𝑅 ′ pair are connected in the nucleus decomposition hierarchy up to the level given by min(𝑁 𝐷 [𝑅], 𝑁 𝐷 [𝑅 ′ ]), which we process using the link subroutine (Lines 14-15). The link subroutine will construct the hierarchy, and we describe it in Sections 7.2 and 7.3.
1: Initialize 𝑘 union-find data structures, 𝑢 𝑓 𝑖 for 𝑖 ∈ [𝑘 ], where 𝑘 is the maximum (𝑟, 𝑠 )-clique core number 2: procedure link-basic(𝑅, 𝑄, 𝑁 𝐷) 3: parfor 𝑖 ∈ [min(𝑁 𝐷 [𝑅 ], 𝑁 𝐷 [𝑄 ] ) ] do 4: 𝑢 𝑓 𝑖 .unite(𝑅, 𝑄 ) 5: procedure construct-tree-basic(𝑁 𝐷) 6: Initialize the hierarchy tree 𝑇 with leaves corresponding to each 𝑟 -clique 7: for 𝑖 ∈ {𝑘, 𝑘 -1, . . . , 1} do 8: parfor each connected component 𝐶 = {𝑅 1 , . . . , 𝑅 𝑐 } in 𝑢 𝑓 𝑖 do 9: Construct a new parent in 𝑇 , to be the parent of the roots of the leaf nodes corresponding to each 𝑅 ℓ (for ℓ ∈ [𝑐 ]) 10: return 𝑇 On the other hand, if 𝑁 𝐷 [𝑅] > 𝑁 𝐷 [𝑅 ′ ], then this means that 𝑅 ′
has not yet been peeled, and the 𝑠-clique removed by 𝑅 must be properly accounted for. In this case, arb-nucleus-decomphierarchy-framework updates the 𝑠-clique count of 𝑅 ′ in the hash table 𝑈 (Line 16). After processing all 𝑅 and 𝑅 ′ pairs, we then update the buckets of the 𝑟 -cliques with updated 𝑠-clique counts in 𝑈 (Line 17). We omit the details of these steps for conciseness, since they are described in Shi et al.'s parallel nucleus decomposition algorithm [55].
The remaining details are in how we perform the link subroutine (Line 15) and how we construct the hierarchy tree 𝑇 with construct-tree (Line 18).
In Algorithm 4, we present a basic link subroutine, link-basic, and the corresponding constructtree subroutine, construct-tree-basic. link-basic maintains a parallel union-find data structure 𝑢 𝑓 𝑖 per core number 𝑖 ∈ [𝑘], which corresponds to a level of the hierarchy tree 𝑇 . Each 𝑢 𝑓 𝑖 connects 𝑟 -cliques that are 𝑠-clique-adjacent considering only 𝑟 -cliques with core numbers ≥ 𝑖. To construct these 𝑢 𝑓 𝑖 's, given two 𝑟 -cliques 𝑅 and 𝑄, link-basic simply unites 𝑅 and 𝑄 in each 𝑢 𝑓 𝑖 where 𝑖 ≤ max(𝑁 𝐷 [𝑅], 𝑁 𝐷 [𝑄]) (Lines 3-4). Then, given the 𝑢 𝑓 𝑖 for all 𝑖 ∈ [𝑘], we construct the hierarchy tree 𝑇 from the bottom up, starting with leaf nodes corresponding to 𝑟 -cliques. construct-tree-basic begins with 𝑖 = 𝑘, where for each connected component in 𝑢 𝑓 𝑘 (Line 8), we construct a parent in 𝑇 where its children are the leaf nodes corresponding to the 𝑟 -cliques in the connected component (Line 9). Then, for 𝑖 = 𝑘 -1, . . . , 1 (Line 7), we construct a new parent for each connected component in 𝑢 𝑓 𝑖 , where its children are the parents of the leaf nodes corresponding to the 𝑟 -cliques that compose the component (Line 9). This produces the desired 𝑇 .
However, link-basic is not efficient, since it requires a union-find data structure per level, and for every pair of 𝑟 -cliques, we could perform up to 𝑘 unite operations. Indeed, in Section 8.1, we empirically show that link-basic performs many unnecessary unite operations in practice. If we let 𝑛 𝑟 and 𝑛 𝑠 denote the number of 𝑟 -cliques and the number of 𝑠-cliques in the graph, respectively, link-basic incurs additional space proportional to 𝑂 (𝑘𝑛 𝑟 ) and total work upper bounded by 𝑂 (𝑘𝑛 𝑠 ) (since there are at most 𝑂 (𝑛 𝑠 ) pairs of 𝑠-clique-adjacent 𝑟 -cliques). In the next subsection, we introduce more efficient link and construct-tree subroutines.
Our improved subroutines link-efficient and construct-tree-efficient are shown in Algorithm 5. We refer to an example of (1, 3)-nucleus decomposition in the graph in Figure 1. Recall that we have omitted labeling some vertices in the graph for simplicity.
The main idea of link-efficient is instead of maintaining 𝑘 union-find data structures, we maintain a single parallel union-find data structure 𝑢 𝑓 and an additional hash table 𝐿 that maps 𝑟 -cliques to 𝑟 -cliques. First, 𝑢 𝑓 stores connected 𝑟 -cliques considering only other 𝑟 -cliques with equal core numbers. For instance, in Figure 1, the vertices 3𝑎, 3𝑏, and 3𝑐 are connected and all have
Parallel Algorithms for Hierarchical Nucleus Decomposition 32:15 Algorithm 5 Efficient link and tree construction 1: Initialize a union-find data structure, 𝑢 𝑓 , of length equal to the number of 𝑟 -cliques 2: Initialize a hash table, 𝐿, where the keys and values are 𝑟 -cliques 3: procedure link-efficient(𝑅, 𝑄, 𝑁 𝐷) 4: if 𝑅 or 𝑄 is empty then return 5: if 𝑁 𝐷 [𝑄 ] < 𝑁 𝐷 [𝑅 ] then Swap 𝑅 and 𝑄 6: 𝑅 ← 𝑢 𝑓 .parent(𝑅), 𝑄 ← 𝑢 𝑓 .parent(𝑄 ) 7: if 𝑁 𝐷 [𝑅 ] = 𝑁 𝐷 [𝑄 ] then 8: 𝑢 𝑓 .unite(𝑅, 𝑄 ) 9: if 𝑢 𝑓 .parent(𝑅) ≠ 𝑅 then link-efficient(𝐿[𝑅 ], 𝑢 𝑓 .parent(𝑅), 𝑁 𝐷 ) 10: if 𝑢 𝑓 .parent(𝑄 ) ≠ 𝑄 then link-efficient(𝐿[𝑄 ], 𝑢 𝑓 .parent(𝑄 ), 𝑁 𝐷 ) 11: else ⊲ 𝑁 𝐷 [𝑅 ] < 𝑁 𝐷 [𝑄 ] 12: while true do 13: 𝐿𝑄 ← 𝐿[𝑄 ] 14: 𝑄 ← 𝑢 𝑓 .parent(𝑄 ) 15: if compare-and-swap(𝐿[𝑄 ], empty, 𝑅) then 16: if 𝑢 𝑓 .parent(𝑄 ) ≠ 𝑄 then 17: link-efficient(𝑅, 𝑢 𝑓 .parent(𝑄 ), 𝑁 𝐷) 18: break 19: else if 𝑁 𝐷 [𝐿𝑄 ] < 𝑁 𝐷 [𝑅 ] then 20: if compare-and-swap(𝐿[𝑄 ], 𝐿𝑄, 𝑅) then 21: if 𝑢 𝑓 .parent(𝑄 ) ≠ 𝑄 then 22: link-efficient(𝑅, 𝑢 𝑓 .parent(𝑄 ), 𝑁 𝐷) 23: link-efficient(𝑅, 𝐿𝑄, 𝑁 𝐷) 24: break 25: else 26: link-efficient(𝑅, 𝐿[𝑄 ], 𝑁 𝐷) 27: break 28: procedure construct-tree-efficient(𝑁 𝐷) 29: Initialize the hierarchy tree 𝑇 with leaves corresponding to each 𝑟 -clique 30: parfor each connected component C = {𝑅 1 , . . . , 𝑅 𝑐 } in 𝑢 𝑓 do 31: Construct a parent node 𝑢 𝑓 C in 𝑇 , where its children are the leaves corresponding to the 𝑟 -cliques in C 32: parfor each parent node 𝑢 𝑓 C in 𝑇 do 33: if 𝐿[ C ] is non-empty then 34: 𝑅 ← 𝑢 𝑓 .parent(𝐿[ C ] ) ⊲ Note that C is the 𝑟 -clique representing the component in 𝑢 𝑓 35: Make 𝑢 𝑓 C a child of 𝑢 𝑓 𝑅 in 𝑇 ⊲ Note that 𝑢 𝑓 𝑅 necessarily exists since 𝑅 represents a component in 𝑢 𝑓 36:
return 𝑇 core number 3, so we would store these as a component in 𝑢 𝑓 . Note that for all core numbers 𝑖, we can store this information using a single union-find data structure because the sets of 𝑟 -cliques with distinct core numbers are disjoint. We can arbitrarily represent each connected component in 𝑢 𝑓 by a single 𝑟 -clique in that component.
The main idea of 𝐿 is to connect the components in 𝑢 𝑓 to the "nearest" core with a different core number that it is contained within (if it exists). For instance, in Figure 1, we note that the component in 𝑢 𝑓 corresponding to 4𝑎 (consisting of vertices with core number 4) is contained within the 3-core consisting of the component {3𝑎, 3𝑏, 3𝑐}. In 𝐿, we would store one of 3𝑎, 3𝑏, or 3𝑐 in an entry corresponding to key 4𝑎, indicating that this is the "nearest" core that 4𝑎 must join in the hierarchy. We note that 4𝑎 is also contained within a larger 2-core and a larger 1-core, but its "nearest" core, or the smallest core such that the component 4𝑎 is a proper subset of that core, is given by the 3-core. It is sufficient to store only the "nearest" core to 4𝑎 in 𝐿, because the component in 𝑢 𝑓 corresponding to {3𝑎, 3𝑏, 3𝑐} is responsible for storing its "nearest" core in 𝐿 as well, to the 2-core it is contained within. On the other hand, the component corresponding to 4𝑑 is not contained within the 3-core, and its "nearest" core would be the 2-core containing the component 2𝑎, so 4𝑑 would store in 𝐿 the value 2𝑎.
More formally, for each 𝑟 -clique 𝑅 representing a connected component in 𝑢 𝑓 , let 𝑅 ′ be an 𝑟 -clique with the maximum 𝑁 𝐷 [𝑅 ′ ] such that 𝑁 𝐷 [𝑅 ′ ] < 𝑁 𝐷 [𝑅], and 𝑅 ′ is connected to 𝑅 through 𝑠-cliques considering only 𝑟 -cliques with core number ≥ 𝑁 𝐷 [𝑅 ′ ]. Then, each such 𝑟 -clique 𝑅 is a key in 𝐿, and 𝐿 stores the corresponding 𝑅 ′ that satisfies these conditions as the value. Note that if there are multiple such 𝑅 ′ where 𝑁 𝐷 [𝑅 ′ ] is maximized under these conditions, it is irrelevant which 𝑅 ′ is stored in 𝐿, because it is simple to look up the component that 𝑅 ′ corresponds to using 𝑢 𝑓 . That is to say, it is irrelevant which of 3𝑎, 3𝑏, and 3𝑐 we store for 4𝑎 in 𝐿, because we can look up the parent of 3𝑎, 3𝑏, and 3𝑐 in 𝑢 𝑓 , which would resolve to the same parent. link-efficient updates 𝑢 𝑓 and 𝐿, depending on the core numbers of the given 𝑟 -cliques 𝑅 and 𝑄. Tree Construction. We describe first how construct-tree-efficient constructs the hierarchy tree 𝑇 given the specifications for 𝑢 𝑓 and 𝐿. We refer to the construction shown in Figure 5, where 𝑢 𝑓 and 𝐿 are given under "After Round 4" in Figure 4.
The main idea for the construction is that if we begin with a hierarchy tree 𝑇 consisting of only leaf nodes corresponding to each 𝑟 -clique, the highest (bottom-most) level in which that leaf node may join a non-trivial connected component is the level corresponding to the leaf node's 𝑟 -clique's (𝑟, 𝑠)-clique core number. That is to say, starting from 𝑖 = 𝑘 and iterating to 𝑖 = 1, an 𝑟 -clique 𝑅 is necessarily a singleton component from 𝑖 = 𝑘 to 𝑖 = 𝑁 𝐷 [𝑅] + 1. The union-find structure 𝑢 𝑓 denotes the parent of each leaf node on the level corresponding to its core number.
Then, once we have the connected components per level corresponding to each core number, it remains to describe how components with different core numbers are contained within each other. This containment is necessarily hierarchical, where components corresponding to larger core numbers are contained within successive components corresponding to smaller core numbers, as can be seen in Figure 1. This containment is precisely what 𝐿 describes; it points each component within a given core 𝑖 to a component on the greatest core number 𝑗 such that 𝑗 < 𝑖, where the two components are connected on level 𝑗 (that is to say, connected through 𝑟 -cliques with core numbers ≥ 𝑗). Thus, using 𝐿, we can point each parent constructed using our 𝑢 𝑓 to another parent, which represents the first instance (from the bottom up in 𝑇 ) in which the original parent is merged into another component.
In more detail, in construct-tree-efficient, we begin with a hierarchy tree 𝑇 consisting of isolated 𝑟 -cliques (Line 29). For each component C = {𝑅 1 , . . . , 𝑅 𝑐 } in 𝑢 𝑓 , representing a connected component of 𝑟 -cliques with the same core number, we construct a parent in 𝑇 , where its children are leaves corresponding to the 𝑟 -cliques in C (Lines 30-31). C is one of these cliques, and is chosen arbitrarily. The new parent is 𝑢 𝑓 C . This process is shown in Stage 1 in Figure 5; each vertex has itself as its parent in 𝑢 𝑓 , except the vertices 3𝑎, 3𝑏, and 3𝑐, which have 3𝑏 as their parent. Thus, we create a new parent node 𝑢 𝑓 3𝑏 for the leaves 3𝑎, 3𝑏, and 3𝑐.
Then, for each parent node 𝑢 𝑓 C , we look up the nearest connected component that it should hierarchically connect to using 𝐿. What this means is that the component 𝑢 𝑓 We make a subtle note that it is not strictly necessary to maintain parent nodes in the hierarchy tree with exactly one child; we can remove all such parents 𝑃 and make the child 𝐶 a direct child of its grandparent 𝐺. This is because it is inherently implied that the component that the child 𝐶 represents in unchanged until it joins the component represented by 𝐺. For instance, 𝑢 𝑓 4𝑑 's sole child is 4𝑑. If we set 4𝑑 to be a direct child of its grandparent, 𝑢 𝑓 2𝑎 , and remove 𝑢 𝑓 4𝑑 , then it is implied that the vertex 4𝑑 remains its own component until it joins the 2-core containing 2𝑎 (and notably, 4𝑑 represents an unchanged component in the 3-core and in the 4-core of the graph). In this sense, the final hierarchy tree produced in Figure 5 is actually equivalent to that in Figure 3. link Subroutine. We now describe link-efficient. The key to link-efficient is to properly maintain 𝑢 𝑓 and 𝐿 according to their definitions given new information obtained by connected 𝑟 -cliques. The main subtlety is that after updating the connectivity information of 𝑅 or 𝑄, in 𝑢 𝑓 or in 𝐿, there may be cascading effects resulting in new calls to link-efficient.
In more detail, link-efficient first ensures that 𝑁 𝐷 [𝑅] ≤ 𝑁 𝐷 [𝑄] (Line 5). We need only perform operations on the parents of the components of the 𝑟 -cliques in 𝑢 𝑓 , so we set 𝑅 and 𝑄 to their respective parents in 𝑢 𝑓 (Line 6).
The first case is if 𝑁 𝐷 [𝑅] = 𝑁 𝐷 [𝑄] (Line 7). Then, we need only unite 𝑅 and 𝑄 in 𝑢 𝑓 , to maintain that 𝑢 𝑓 tracks the connectivity between 𝑟 -cliques with the same core number (Line 8). However, the new parent 𝑃 may now need to update its value in 𝐿 based on 𝐿[𝑅] and 𝐿[𝑄]. This is because it is possible that 𝐿[𝑃] must be updated; for instance, if 𝐿[𝑅] has a strictly greater core number than the current 𝐿[𝑃], 𝐿[𝑃] must be updated to be 𝐿 [𝑅]. link-efficient performs these updates by calling itself on 𝐿[𝑅] and 𝑃, and on 𝐿[𝑄] and 𝑃, if 𝑃 ≠ 𝑅 and 𝑃 ≠ 𝑄, respectively (Lines 9-10).
The second case is if 𝑁 𝐷 [𝑅] < 𝑁 𝐷 [𝑄] (Line 11). There are two main considerations. First, 𝑅 may replace the current value of 𝐿[𝑄], which we call 𝐿𝑄, if 𝑁 𝐷 [𝑅] > 𝑁 𝐷 [𝐿𝑄]. Second, 𝑅 and 𝐿𝑄 must be linked, since they are connected through 𝑄 and could affect each other's parent or value in 𝑢 𝑓 or 𝐿, respectively. We handle these cases with a series of if statements and compare-and-swaps.
We first perform a compare-and-swap, checking if 𝐿[𝑄] is empty and replacing it with 𝑅 if so (Line 15); if this compare-and-swap succeeds, then there is still the possibility that 𝑄's parent in 𝑢 𝑓 changed before the compare-and-swap completed, in which case 𝑄's new parent is unaware of its connection to 𝑅. In this scenario, we must call link-efficient again on 𝑅 and the new parent of 𝑄, since 𝑅 could potentially modify the 𝑟 -clique stored in 𝐿 corresponding to 𝑄's new parent (Lines [16][17].
If the previous compare-and-swap failed, then we check if 𝑁 𝐷 [𝐿𝑄] < 𝑁 𝐷 [𝑅] (Line 19), which if true, means that 𝑅 is a candidate to replace 𝐿𝑄 in 𝐿. We perform another compare-and-swap to replace 𝐿𝑄 with 𝑅 (Line 20), and if it succeeds, we must again check if 𝑄's parent in 𝑢 𝑓 has potentially changed before the compare-and-swap completed. Again, if this occurs, we must call link-efficient on 𝑅 and the new parent 𝑄 (Lines 21 -22). We must also call link-efficient on 𝑅 and 𝐿𝑄 (Line 23), to store 𝑅's connectivity to 𝐿𝑄. This is because 𝑅's "nearest" core as stored in 𝐿 may be superseded by 𝐿𝑄. If the compare-and-swap fails, we simply try again, hence the while loop (Line 12).
The last case is if 𝑁 𝐷 [𝐿𝑄] ≥ 𝑁 𝐷 [𝑅] (Line 25), in which case 𝑅 is not a candidate to replace 𝐿𝑄 in 𝐿, and we store 𝑅's connectivity to 𝑄 by calling link-efficient on 𝑅 and 𝐿 [𝑄]. Note that this is necessary because 𝑅 and 𝐿[𝑄] could be united in 𝑢 𝑓 if they have the same core number, or 𝑅 could be a "nearest" core to 𝐿[𝑄].
This concludes our efficient link subroutine, link-efficient. We show in Section 8.1 that linkefficient performs many fewer unite and link operations, and achieves significant speedups, over link-basic. We provide an example of running link-efficient. Example of link-efficient. As an example of these cascading effects, we refer to an intermediate state of 𝑢 𝑓 and 𝐿 on the example graph in Figure 1, given after the third round of peeling in arb-nucleus-decomp-hierarchy-framework (immediately before peeling the final set of vertices in the graph, given by the components 4𝑎, 4𝑏, 4𝑐, and 4𝑑). This state is shown in the data structures under "After Round 3" in Figure 4. In 𝑢 𝑓 , every vertex is its own parent, and in 𝐿, we have identified that the component corresponding to 3𝑎 is connected to 1𝑎. Note that many link operations occur from peeling 4𝑎, 4𝑏, 4𝑐, and 4𝑑, including for the (𝑅, 𝑄) pairs (3𝑎, 4𝑐), (3𝑏, 4𝑐), and (2𝑎, 4𝑐), which we consider in this example. We show in Figure 4 the state of 𝑢 𝑓 and 𝐿 after each of these three calls to link-efficient (including the cascading calls that these calls generate). We list the 𝑅 and 𝑄 for each link-efficient operation, as well as the cascading calls that they invoke. We assume the operations happen sequentially for clarity, although in practice they can happen concurrently.
• 𝑅 = 3𝑎, 𝑄 = 4𝑐: We now know that 4𝑐 is connected to 3𝑎's component, and 4𝑐 does not have a previously set "nearest" core, so we set 𝐿[4𝑐] = 3𝑎 (Line 15). • 𝑅 = 3𝑏, 𝑄 = 4𝑐: We note that 𝐿[4𝑐] is now already set to a "nearest" core with core number 3, so there is nothing new to update for 𝐿[𝑄]. However, we gain from this new link the knowledge that 3𝑎 and 3𝑏 are connected (since 𝐿[4𝑐] = 3𝑎), so we must cascade a new link-efficient call to (𝑅, 𝐿[𝑄]) = (3𝑏, 3𝑎) (Line 26), so that 3𝑎 and 3𝑏 can be set to the same component in 𝑢 𝑓 .
-𝑅 = 3𝑎, 𝑄 = 3𝑏: We now call unite on 3𝑎 and 3𝑏 in 𝑢 𝑓 (Line 8). Say that arbitrarily, 3𝑏 is set as the new parent of 3𝑎 and 3𝑏 in 𝑢 𝑓 . Since the parents in 𝑢 𝑓 are responsible for maintaining the connection to the "nearest" core, we must transfer
We do so by calling link-efficient on (𝐿[𝑅], 𝑢 𝑓 .parent(𝑅)) = (1𝑎, 3𝑏) (Line 9). * 𝑅 = 1𝑎, 𝑄 = 3𝑏: Now, we can set 𝐿[𝑄] = 𝐿[3𝑏] to 𝑅 = 1𝑎, since 3𝑏's "nearest" core is now 1𝑎 (Line 15).
• 𝑅 = 2𝑎, 𝑄 = 4𝑐: Since 4𝑐 already has an entry in 𝐿 that's "nearer" to it than 2𝑎, there is nothing new to update for 𝐿 [𝑄]. However, we now know that 3𝑎 and 2𝑎 are connected, so we must cascade a new link-efficient call to (𝑅, 𝐿[𝑄]) = (2𝑎, 3𝑎) (Line 26).
-𝑅 = 2𝑎, 𝑄 = 3𝑎: Since the parent of 𝑄 in 𝑢 𝑓 is 3𝑏, we can treat this as 𝑅 = 2𝑎 and 𝑄 = 3𝑏 (since we only need to maintain connections in 𝐿 for the parents in 𝑢 𝑓 ). Now, we find that 3𝑏 has recorded its "nearest" core as 𝐿[3𝑏] = 1𝑎, but 2𝑎 is "nearer". Thus, we update 𝐿[3𝑏] to be 2𝑎 (Line 20), but now we know that 2𝑎 is connected to 1𝑎. So, we call link-efficient on (𝑅, 𝐿[𝑄]) = (2𝑎, 1𝑎) (Line 23). * 𝑅 = 1𝑎, 𝑄 = 2𝑎: We discover that 2𝑎's "nearest" core is given by 1𝑎. We set
Note that it is necessary for us to perform these cascading calls to link-efficient, because the only way for 3𝑎 and 3𝑏 to discover that they should be connected is through one of the 4-core components, and the only way for 3𝑏 to realize that the component with 2𝑎 is its "nearest" core is also through one of the 4-core components. Similarly, the only way for 2𝑎 to realize that the component with 1𝑎 is its "nearest" core is through first one of the 4-core components, then through the 3-core component, in which 3𝑎, which we now know is connected to 3𝑏, had the original adjacency to 1𝑎. Thus, information must be constantly propagated through 𝑢 𝑓 and 𝐿. Comparison to Prior Work. Sariyüce and Pinar [49] also provide a hierarchy construction algorithm, nh, that is performed interleaved with the peeling process. They maintain a union-find data structure that stores the connectivity of all 𝑟 -cliques considering only 𝑟 -cliques with the same core number. However, for adjacent 𝑟 -cliques with different core numbers, they simply store all pairs of such 𝑟 -cliques in a list. They process this list after the peeling process to construct the hierarchy tree, and their method for processing this list requires a global view, since nh first sorts the pairs of 𝑟 -cliques in the list based on their core numbers. Storing this list incurs additional space potentially proportional to the number of 𝑠-cliques in the graph, which is a significant overhead.
Our main innovation in link-efficient is that we need only incur additional space overhead proportional to the number of 𝑟 -cliques in the graph, because we process adjacent 𝑟 -cliques with different core numbers while performing the peeling process. We are able to process this information into a hash table 𝐿 proportional to the number of 𝑟 -cliques, so our memory overhead overall is 2𝑛 𝑟 , where 𝑛 𝑟 is the number of 𝑟 -cliques. In contrast, nh uses 𝑠 𝑟 • 𝑛 𝑠 + 𝑛 𝑟 additional space, where 𝑛 𝑠 is the number of 𝑠-cliques. In addition, nh is sequential, whereas link-efficient is thread-safe and carefully resolves conflicts in updating 𝑢 𝑓 and 𝐿. Also, the post-processing step to construct the hierarchy tree in nh involves many sequential dependencies, where even merges on the same level of the tree may conflict with each other, whereas our post-processing step, construct-treeefficient, is fully parallel.
Finally, we make certain optimizations to our theoretically-efficient (𝑟, 𝑠) nucleus decomposition hierarchy algorithm, arb-nucleus-hierarchy (Algorithm 1) to improve its performance in practice. We maintain the two-pass paradigm of first computing the (𝑟, 𝑠)-clique core numbers of each 𝑟clique and then constructing the hierarchy tree 𝑇 . However, we do not explicitly store linked lists containing all pairs of 𝑠-clique-adjacent 𝑟 -cliques, since this represents too much of a memory overhead to be practical, particularly for larger 𝑟 and 𝑠. We also do not explicitly generate the graph 𝐻 given by these linked lists (Line 14).
Instead, we use a single union-find data structure to maintain the connected components (throughout the loop on Lines 12-20), and for each 𝑖 ∈ {𝑘, 𝑘 -1, . . . , 1} (Line 12), we iterate through all 𝑟 -cliques 𝑅 with core number 𝑖 and their 𝑠-clique-adjacent 𝑟 -cliques 𝑅 ′ . We perform a parallel sort on the 𝑟 -cliques based on their core numbers, which allows us to efficiently extract 𝑟 -cliques
𝑛 𝑚 amazon 334,863 925,872 dblp 317,080 1,049,866 youtube 1,134,890 2,987,624 skitter 1,696,415 11,095,298 livejournal 3,997,962 34,681,189 orkut 3,072,441 117,185,083 friendster 65,608,366 1.806 × 10 9
Table 1. Sizes of our input graphs, which are from SNAP [37].
with the same core numbers; this adds a small additional memory overhead, which we observe in Section 8.1. For each such pair of 𝑟 -cliques 𝑅 and 𝑅 ′ where 𝑁 𝐷 [𝑅 ′ ] ≥ 𝑁 𝐷 [𝑅], we directly unite them in our union-find data structure to obtain the desired connected components; this replicates the same information stored in the linked lists (on Lines 6-8). We construct the requisite new parents in the hierarchy tree 𝑇 given the computed connected components, and we reuse the same union-find data structure for subsequent 𝑖.
Environment and Inputs. We run our experiments on a Google Cloud Platform instance with a 30-core machine with two-way hyper-threading, with 3.9 GHz Intel Cascade Lake processors and 240 GB of main memory. We use all cores when testing parallel implementations, unless specified otherwise. Our implementations are written in C++ and we compile our code using g++ (version 7.4.0) with the -O3 flag. We use parallel primitives and the work-stealing scheduler from ParlayLib by Blelloch et al. [6]. We terminate any experiment that takes over 4 hours. We test our algorithms on real-world graphs from the Stanford Network Analysis Project (SNAP) [37], shown in Table 1.
We implement all three versions of our exact (𝑟, 𝑠) nucleus decomposition hierarchy algorithms, including our theoretically-efficient arb-nucleus-hierarchy (Algorithm 1, with the optimizations described in Section 7.4), which we call anh-te, and our nucleus decomposition hierarchy framework arb-nucleus-decomp-hierarchy-framework (Algorithm 3) using both link-basic (Algorithm 4) and link-efficient (Algorithm 5), which we call anh-bl and anh-el, respectively.
We also implement our approximate (𝑟, 𝑠) nucleus decomposition hierarchy algorithm, arbapprox-nucleus-hierarchy (using Algorithm 2). We integrate approx-arb-nucleus with each of anh-te, anh-el, and anh-bl for the hierarchy construction, giving us three implementations, approx-anh-te, approx-anh-el, and approx-anh-bl, respectively.
We compare our hierarchy algorithms to nh, the state-of-the-art sequential (𝑟, 𝑠) nucleus decomposition hierarchy implementation by Sariyüce and Pinar [49] for (1, 2), (2, 3), and (3, 4) nucleus decomposition. Note that nh does not generalize to other 𝑟 and 𝑠 values. nh, like anh-bl and anh-el, constructs the hierarchy while computing the (𝑟, 𝑠)-clique-core numbers of the graph. For the special case of 𝑘-core, we also compare to phcd, the state-of-the-art parallel 𝑘-core hierarchy implementation by Chu et al. [11]. 8.1 Comparison of anh-te, anh-el, and anh-bl Figure 6 compares our exact (𝑟, 𝑠) nucleus decomposition hierarchy algorithms, anh-te, anh-el, and anh-bl, against each other, for various 𝑟 and 𝑠. We show 𝑟 < 𝑠 ≤ 5 here, but we ran all of our algorithms for 𝑟 < 𝑠 ≤ 7. Also, the running times listed in these figures do not include the time needed to compute the low out-degree orientation or to compute the initial 𝑠-clique-degrees of each 𝑟 -clique, which are the same across all of our algorithms (note that we do include these times when comparing to other work in Section 8.2). However, our running times do include the time required to compute the (𝑟, 𝑠)-clique-core numbers of each 𝑟 -clique, which notably for anh-te is given by arb-nucleus from [55].
Parallel Algorithms for Hierarchical Nucleus Decomposition 32:21 1 amazon (0.034 s) dblp (0.058 s) youtube (0.12 s) skitter (0.28 s) livejournal (1.03 s) orkut (2.61 s) friendster (35.53 s) 0 20 40 60 80 100 120 140 160 180 200 220 240 260 280 Multiplicative slowdowns (1, 2) ANH-TE ANH-EL ANH-BL amazon (0.074 s) dblp (0.098 s) youtube (0.3 s) skitter (2.82 s) livejournal (8.64 s) orkut (36.56 s) friendster (436.28 s) 0 1 2 3 4 5 6 7 8 9 10 11 12 Multiplicative slowdowns (2, 3) ANH-TE ANH-EL ANH-BL 1 amazon (0.12 s) dblp (2.67 s) youtube (4.22 s) skitter (75.51 s) friendster (1141.32 s)
0 10 20 30 40 50 60 70 80 Multiplicative slowdowns (2, 4) ANH-TE ANH-EL ANH-BL amazon (0.09 s) dblp (80.69 s) youtube (9.38 s) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Multiplicative slowdowns (2, 5) ANH-TE ANH-EL ANH-BL amazon (0.1 s) dblp (1.39 s) youtube (3.2 s) skitter (42.59 s) livejournal (652.26 s) orkut (1091.51 s) 0 1 2 3 4 5 6 7 8 9 10 Multiplicative slowdowns (3, 4) ANH-TE ANH-EL ANH-BL amazon (0.07 s) dblp (88.32 s) youtube (8.18 s) 1 2 3 4 5 6 7 8 9 10 11 12 13 Multiplicative slowdowns (3, 5) ANH-TE ANH-EL ANH-BL amazon (0.058 s) dblp (51.63 s) youtube (7.09 s) skitter (478.27 s) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Multiplicative slowdowns (4, 5)
ANH-TE ANH-EL ANH-BL Fig. 6. Multiplicative slowdowns of our parallel nucleus decomposition hierarchy implementations anh-te, anh-el, and anh-bl, over the fastest of the three for each graph, for 𝑟 < 𝑠 ≤ 5. We have omitted bars where our implementations run out of memory or time out after 4 hours, and we have omitted graphs where only one of anh-te, anh-el, and anh-bl completes. Below each graph in parentheses is the fastest running time among the three implementations. We have also included a line marking a multiplicative slowdown of 1.
Overall, we find that anh-el is faster if the difference between 𝑠 and 𝑟 is small (generally, if 𝑠 -𝑟 ≤ 2), and anh-te is faster in all other cases. The exception is for 𝑘-core (or (1, 2)-nucleus) decomposition, where anh-te is 2.38-21.95x faster than anh-el. This is because the 𝑘-core decomposition requires far lower overhead to compute the core numbers per vertex compared to higher 𝑟 and 𝑠, since we need only maintain the degree of each vertex. The benefit of anh-el is due to the improved locality in iterating over and processing 𝑠-cliques once, rather than recomputing the 𝑠-cliques twice. This is not a benefit for 𝑘-core, because iterating over edges is a much simpler and cache-friendly pattern. Also, anh-bl is significantly slower than both anh-te and anh-el, and runs out of memory for many values of 𝑟 and 𝑠, since it has a much larger memory footprint from storing a union-find structure per core number. Overall, anh-el is up to 2.37x faster than anh-te, and anh-te is up to 41.55x faster than anh-el, where we see the largest speedups in anh-te over anh-el when 𝑠 is much larger than 𝑟 . anh-bl is up to 14.55x slower than anh-el, and up to 11.96x slower than anh-te.
The cases in which anh-el outperforms anh-te and vice versa, and the reason for the slowness of anh-bl, is due to the number of link and unite operations. Indeed, for the dblp and youtube graphs, particularly for larger 𝑟 and when the difference between 𝑟 and 𝑠 is small, the number of times in which anh-te calls link and unite is 1.08-13.67x the number of times in which anh-el calls link and unite. For smaller 𝑟 and when the difference between 𝑟 and 𝑠 is large, anh-el calls link and unite between 1.02-18.94x more than anh-te. Looking at fixed 𝑟 and increasing 𝑠, we observe that anh-el performs many more cascading calls to itself as 𝑠 increases, since 𝑠 𝑟 increases and anh-el more likely needs to connect two 𝑟 -cliques across multiple levels of the hierarchy tree. anh-bl is much slower than both anh-te and anh-el, performing up to 39.75x the number of link and unite calls. anh-bl repeatedly performs unite operations equal to the core number of each 𝑟 -clique, which can be redundant, since if two 𝑟 -cliques are connected in a higher core, they are necessarily connected in the lower core.
In terms of memory usage, considering the memory overhead of building and constructing the hierarchy (not including the space required to store the graph or the (𝑟, 𝑠)-clique-core numbers of each 𝑟 -clique), on dblp and youtube, anh-bl uses 1.53-10.03x the amount of overhead that anh-el uses, and anh-te uses 1.08-1.11x the amount of overhead that anh-el uses. We observe
10 2 10 3 10 4 amazon (0.002 s) dblp (0.058 s) youtube (0.12 s) skitter (0.28 s) livejournal (1.03 s) orkut (2.61 s) friendster (35.53 s) 0 5 10 15 20 25 30 35 40 45 50 Multiplicative slowdowns (1, 2) (2, 3) (2, 4) (2, 5) (2, 6) (2, 7) (3, 5) (3, 6) (3,7) (4,5) (4,6) (4, 7) (5,6) (5,7) (6,7) Fig. 7. Multiplicative slowdowns of parallel arbnucleus-hierarchy for each (𝑟, 𝑠) combination over the fastest running time for parallel arb-nucleushierarchy across all 𝑟 < 𝑠 ≤ 7 for each graph, considering the fastest of anh-te, anh-el, and anh-bl. The fastest time is labeled in parentheses below each graph. We have omitted bars where arb-nucleus-hierarchy runs out of memory or times out after 4 hours. 1 2 4 8 16 30 30h 0 5 10 15 20 25 30 Number of workers Speedup over single-threaded (2, 3) dblp (2, 4) dblp (2, 5) dblp (3, 4) dblp (3, 5) dblp (4, 5) dblp (2, 3) skitter (2, 4) skitter (3, 4) skitter (4, 5) skitter 1 2 4 8 16 30 30h 0 5 10 15 20 25 30 Number of workers Speedup over single-threaded (2, 3) dblp (2, 4) dblp (2, 5) dblp (3, 4) dblp (3, 5) dblp (4, 5) dblp (2, 3) skitter (2, 4) skitter (3, 4) skitter (4, 5) skitter that anh-el is the most memory efficient overall, since it only maintains two arrays proportional to the number of 𝑟 -cliques (𝑢 𝑓 and 𝐿). anh-te incurs almost the same memory overhead, with a minor additional cost attributed to maintaining 𝑟 -cliques sorted by their core numbers (which we discuss in Section 7.4), and anh-bl incurs much more overhead to maintain union-find data structures proportional to the number of 𝑟 -cliques per core number.
To provide some context into how long the hierarchy construction takes compared to the coreness computation, we measured the time for just computing coreness values and compared it to the total time for each of our algorithms. The coreness computation time represents 46.53%, 35.26%, and 36.08% of the total time on average in anh-el, anh-bl, and anh-te, respectively. Note that this ignores the locality effects of interleaving the computations in anh-el and anh-bl. Nevertheless, we see that on average, anh-el spends the least amount of time on hierarchy construction, indicating the effectiveness of our optimizations.
Figure 7 shows the best running times for all graphs, over 𝑟 < 𝑠 ≤ 7, considering all of our exact (𝑟, 𝑠) nucleus decomposition hierarchy algorithms, anh-te, anh-el, and anh-bl, excluding the time needed to compute our low out-degree orientation and the initial 𝑠-clique-degrees of each 𝑟 -clique. In general, larger (𝑟, 𝑠) values correspond to longer running times. However, some of the times for larger values of (𝑟, 𝑠) are faster than for smaller values of (𝑟, 𝑠) (especially on amazon) because the maximum coreness values for the larger values of (𝑟, 𝑠) are small and the algorithms finish quickly.
Figure 8 shows the scalability of anh-te and anh-el over different numbers of threads on dblp and skitter, and we see good scalability overall. Across all of our graphs and for 𝑟 < 𝑠 ≤ 7, we observe up to 24.75x self-relative speedups (and a median of 15.57x) for anh-te and up to 30.96x self-relative speedups (and a median of 14.13x) for anh-el. Generally, we observe greater self-relative speedups for larger 𝑟 and 𝑠 and for larger graphs. Comparison to Other Implementations. Figure 9 shows the comparison of our parallel (1, 2), (2, 3), and (3, 4) nucleus decomposition hierarchy implementations to other implementations. Note that here, we include in our implementations the time needed to compute the low out-degree orientation and to compute the initial 𝑠-clique-degrees of each 𝑟 -clique. We do not include the time required to load the graph in both our and other implementations.
For (1, 2) nucleus (𝑘-core) decomposition, we compare to the parallel phcd [11] and the sequential nh [49]. Our fastest implementation for 𝑘-core is anh-te, and we see that anh-te is up to 2.57x slower than phcd overall, but 1.87x faster than phcd on dblp. We note that phcd is optimized
Parallel Algorithms for Hierarchical Nucleus Decomposition 32:23 1 amazon (0.031 s) dblp (0.058 s) youtube (0.1 s) skitter (0.18 s) livejournal (0.49 s) orkut (1.02 s) friendster (32 s)
0 5 10 15 20 25 30 35 40 45 50 55 60 Multiplicative slowdowns (1, 2) ANH-TE (parallel) PHCD (parallel) NH (sequential) ANH-TE (single-threaded) 1 amazon (0.097 s) dblp (0.12 s) youtube (0.35 s) skitter (2.89 s) livejournal (9.29 s) orkut (40.43 s) friendster (526.3 s) 0 5 10 15 20 25 30 35 40 45 50 55 Multiplicative slowdowns (2, 3) ANH-TE (parallel) ANH-EL (parallel) NH (sequential) ANH-TE (single-threaded) ANH-EL (single-threaded) 1 amazon (0.12 s) dblp (1.5 s) youtube (3.27 s) skitter (43.46 s) livejournal (677.92 s) orkut (1113.85 s) 0 5 10 15 20 25 30 35 40 Multiplicative slowdowns (3, 4) ANH-TE (parallel) ANH-EL (parallel) NH (sequential)
ANH-TE (single-threaded) ANH-EL (single-threaded) Fig. 9. Multiplicative slowdowns, comparing anh-te, anh-el, the parallel phcd [11], and the sequential nh [49], for (1, 2), (2, 3), and (3, 4) nucleus decomposition. We give the multiplicative slowdown over the fastest implementation for each graph and each (𝑟, 𝑠), where the fastest running time is labeled in parentheses below each graph. We include end-to-end running times in this comparison, excluding only the time required to load the graph. We have omitted bars where the implementation runs out of memory or times out after 4 hours. We have also included a line marking a multiplicative slowdown of 1. for the 𝑘-core decomposition, rather than general (𝑟, 𝑠) nucleus decomposition, whereas anh-te generalizes for larger 𝑟 and 𝑠. Like anh-te, phcd constructs the hierarchy tree from the bottom-up after computing the core numbers of each vertex, but unlike anh-te, phcd leverages the information from computing the core numbers to optimize for the 𝑘-core hierarchy, by reordering vertices based on their core numbers. This optimization allows them to more efficiently divide the work of constructing the hierarchy across different threads, and allows them to reduce the work in practice when iterating over the neighbors of a vertex 𝑣 with larger core numbers than that of 𝑣. Compared to the sequential nh, anh-te is 4.67-58.84x faster, particularly on larger graphs. For (1, 2), (2, 3), and (3, 4) nucleus decomposition, we compare our parallel anh-te and anh-el to the sequential nh [49]. Considering the fastest of anh-te and anh-el for each graph, our implementations are 3.76-23.54x faster, demonstrating that we achieve good speedups from our use of parallelization. Sequentially, our fastest algorithm is between 2.02x faster and 4.2x slower than nh. We get slowdowns due to the additional overheads of parallel subroutines and the fact that our code has a general structure for supporting arbitrary (𝑟, 𝑠) values, whereas the code of [49] is specialized for the specific values of (1, 2), (2, 3), and (3, 4). These slowdowns are somewhat counteracted by our faster clique enumeration algorithm, leading to speedups in some cases. Usefulness of the Hierarchy. In Figure 10, we show the edge densities of various (2, 𝑠)-nuclei in the youtube graph. The edge density of a subgraph 𝑆 is defined to be the number of edges in 𝑆 divided by |𝑆 | 2 (the total possible number of edges). Edge density is the metric used to evaluate the quality of subgraphs from nucleus decompositions [52], and finding dense subgraphs subject to a size constraint has important applications.
For a fixed 𝑟 and 𝑠, having the nucleus hierarchy enables us to efficiently find all of the 𝑐-(𝑟, 𝑠) nuclei for any value of 𝑐 by simply removing all internal nodes corresponding to 𝑐 ′ -(𝑟, 𝑠) nuclei for 𝑐 ′ < 𝑐, and having each resulting subtree be a 𝑐-(𝑟, 𝑠) nucleus that contains all of its leaves. On the other hand, given only the core numbers and no hierarchy, to find the 𝑐-(𝑟, 𝑠) nuclei for a given value of 𝑐, one would need to run connected components on all 𝑟 -cliques with core number ≥ 𝑐, with connectivity defined by 𝑠-clique adjacency, which is much more expensive than simply cutting the hierarchy. Indeed, Figure 10 shows the time needed to generate all (2, 𝑠) nuclei for various values of 𝑠 with and without the hierarchy for the youtube graph. We see that using the hierarchy is 5.84-834.09x faster than not using the hierarchy.
We considered 𝛿 = 0.1, 0.5, and 1 for our experiments for approximate (𝑟, 𝑠) nucleus decomposition (𝛿 is the approximation parameter in Algorithm 2). We first compare approx-arb-nucleus to arb-nucleus [55] and see a speedup of up to 16.16x for 𝛿 = 0.1, up to 8.35x for 𝛿 = 0.5, and up to 10.88x for 𝛿 = 1.
Besides the computation of the (𝑟, 𝑠)-clique-core numbers, approx-anh-te, approx-anh-el, and approx-anh-bl are identical to anh-te, anh-el, and anh-bl, respectively. In other words, their hierarchy construction procedure is the same. We observe up to a 3.3x speedup considering the fastest of our approximate algorithms for each graph and 𝑟 < 𝑠 ≤ 7, over the fastest of our exact algorithms. Notably, for 𝛿 = 0.1, we are able to compute the (2, 5) nucleus decomposition hierarchy on friendster in 8783.2 seconds, where our exact implementations timeout at 4 hours. The improvements in running time using our approximate algorithms are lower than when comparing approx-arb-nucleus to arb-nucleus [55] because even in our approximate algorithms, 𝑠-cliques must be exactly counted per 𝑟 -clique, and much of the time is spent doing this.
In terms of accuracy, the average error in the (𝑟, 𝑠)-clique-core number per 𝑟 -clique is relatively low for all of our 𝛿 values. For 𝛿 = 0.1, across all of our graphs and for 𝑟 < 𝑠 ≤ 7, our coreness estimates per 𝑟 -clique are have a multiplicative error of 1-2.92x on average (with a median of 1.33x) compared to the exact coreness numbers. For 𝛿 = 0.5, the coreness estimates range from having a multiplicative error of 1-2.92x on average as well, with a median of 1.34x, and for 𝛿 = 1, the coreness estimates range from having a multiplicative error of 1-3.05x on average, with a median of 1.35x. The multiplicative errors of the maximum (𝑟, 𝑠)-clique-core number, across all graphs and for 𝑟 < 𝑠 ≤ 7, are also reasonably low, with a median of 1.6x for 𝛿 = 0.1, a median of 2x for 𝛿 = 0.5, and a median of 2x for 𝛿 = 1. The maximum multiplicative error for a given 𝑟 -clique is 6.73x for 𝛿 = 0.1, 6.98x for 𝛿 = 0.5, and 7.32x for 𝛿 = 1, but these arise for large 𝑠, notably when 𝑟 = 5 and 𝑠 = 7 for all 𝛿, and these errors are still much lower than the theoretical guarantee of ( 𝑠 𝑟 + 𝛿) • (1 + 𝛿) given by Theorem 6.1. Note that the theoretical bound is a worst case bound. In practice, (𝑟, 𝑠)-cliques whose core numbers are close to the end of the range of each bucket will have a much better approximation. Furthermore, graphs with a low peeling complexity will likely have more (𝑟, 𝑠)-cliques peeled before moving to the next round (Line 17 of Algorithm 2), which will make the approximation better.
We have presented new parallel exact and approximate algorithms for nucleus hierarchy construction with strong theoretical guarantees. We have developed optimized implementations of our algorithms, which interleave the coreness number computation with the hierarchy construction. Our experiments showed that our implementations outperform state-of-the-art implementations while achieving good parallel scalability.
Proc. ACM Manag. Data, Vol. 2, No. 1 (SIGMOD), Article 32. Publication date: February 2024.
We say 𝑂 (𝑓 (𝑛) ) with high probability (w.h.p.) to indicate 𝑂 (𝑐 𝑓 (𝑛) ) with probability at least 1 -𝑛 -𝑐 for 𝑐 ≥ 1, where 𝑛 is the input size.Proc. ACM Manag. Data, Vol.
2, No. 1 (SIGMOD), Article 32. Publication date: February 2024.