Parallel Batch-Dynamic Algorithms for $k$-Core Decomposition and Related Graph Problems

Quanquan C. Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, Julian Shun

TL;DR

This paper introduces the first parallel, batch-dynamic algorithm for $(2 + \varepsilon)$-approximate $k$-core decomposition. By leveraging a novel "Parallel Level Data Structure" (PLDS), the authors achieve polylogarithmic depth (parallel time) and massive speedups—up to 723x—over state-of-the-art sequential and parallel baselines on graphs with billions of edges.

What Problem Does This Paper Address?

The $k$-core of a graph is the maximal subgraph where every vertex has at least $k$ neighbors within that subgraph. $k$-core decomposition is a vital tool for community detection and network analysis, but it is notoriously difficult to maintain in dynamic settings where edges are constantly added or removed.

The primary challenge is that a single edge update can trigger a "cascade" of changes across the entire graph. Furthermore, the standard algorithm for finding $k$-cores—iteratively "peeling" low-degree vertices—is inherently sequential. In technical terms, exact $k$-core decomposition is P-complete, meaning it's unlikely to have a highly parallel algorithm. This paper tackles the problem by relaxing the requirement to a $(2 + \varepsilon)$-approximation, allowing for efficient parallelization without sacrificing too much accuracy.

Figure 1: Exact 𝑘-core decomposition (left) and (3/2)-approximate 𝑘-core decomposition (right).

Methods

The authors propose the Parallel Level Data Structure (PLDS). Inspired by sequential level structures, the PLDS partitions vertices into $O(\log^2 n)$ levels based on their induced degrees.

Key technical components include:

  • Invariants: The structure maintains two invariants: an upper bound on the degree of a vertex to neighbors at its level or higher, and a lower bound on its degree to neighbors at its level or lower.
  • Batch Processing: Unlike sequential structures that update one edge at a time, the PLDS processes a batch of updates $\mathcal{B}$ simultaneously. It moves vertices between levels in parallel while maintaining the invariants.
  • Low Out-Degree Orientation: As a side effect, the PLDS maintains a directed version of the graph where every node has a low out-degree (proportional to the graph's arboricity $\alpha$). This orientation serves as a "Swiss Army knife" to solve other problems like maximal matching, clique counting, and vertex coloring.
Figure 5: Example of invariants maintained by the PLDS for 𝛿= 0.4 and 𝜆= 3. There are Θ(log𝑛) groups, each with Θ(log𝑛). Each vertex is in exactly one level of the structure and moves up and down by some movement rules. For example, vertex 𝑥(blue) is on level 3 and in group 1.

Datasets

The algorithms were evaluated on 11 real-world undirected graphs from SNAP, the DIMACS Shortest Paths challenge, and the Network Repository. These include:

  • Social/Web Networks: dblp, wiki, youtube, livejournal, orkut, twitter, friendster.
  • Specialized Networks: brain (dense human brain network), usa, and ctr (road networks).
  • Scale: The largest dataset, friendster, contains over 65 million vertices and 1.8 billion edges.

Key Insights and Ideas

  • The Power of Approximation: By accepting a $(2 + \varepsilon)$ error bound, the authors move the problem from the "inherently sequential" P-complete category into one that can be solved in polylogarithmic parallel time (depth).
  • Level-Based Estimation: A vertex's coreness can be estimated simply by looking at the level it settles into within the PLDS. This avoids the need for complex global recalculations.
  • Parallel Cascades: While sequential algorithms might move a vertex one level at a time (causing long dependency chains), the PLDS deletion algorithm moves vertices to their final level in a single step, significantly reducing parallel depth.
  • Unified Framework: The data structure isn't just for $k$-cores; the low out-degree orientation it provides is a fundamental building block for a variety of other batch-dynamic graph algorithms.

Key Results

The authors implemented their algorithm (PLDS) and an optimized version (PLDSOpt) on a 30-core machine.

  • Speedups: PLDSOpt achieved up to a 114.52x speedup against the best parallel exact implementation and up to 723.72x against the best exact sequential algorithm.
  • Scalability: On massive graphs like twitter and friendster, most existing dynamic algorithms timed out (taking over 3 hours), while the PLDS algorithms finished in seconds or minutes.
  • Accuracy: Despite the theoretical $(2 + \varepsilon)$ bound, the empirical error was much lower, typically staying within a factor of 1.2x to 2.4x of the exact value.
  • Parallel Efficiency: The algorithm demonstrated excellent self-relative speedup, scaling well as more threads were added.

Limitations and Future Work

  • Space Complexity: The current PLDS uses $O(n \log^2 n + m)$ space. While manageable for most modern hardware, it is super-linear in the number of vertices. The authors note that a linear-space version is theoretically possible but might incur higher parallel depth.
  • Adversarial Robustness: Some of the derived algorithms (like vertex coloring) are only proven robust against "oblivious" adversaries (who don't see the algorithm's previous outputs) rather than "adaptive" ones.
  • Future Directions: A major open problem is designing a parallel batch-dynamic algorithm that is strictly space-efficient (linear space) without increasing the parallel time (depth).

Summary updated

Abstract

Maintaining a $k$-core decomposition quickly in a dynamic graph has important applications in network analysis. The main challenge for designing efficient exact algorithms is that a single update to the graph can cause significant global changes. Our paper focuses on \emph{approximation} algorithms with small approximation factors that are much more efficient than what exact algorithms can obtain. We present the first parallel, batch-dynamic algorithm for approximate $k$-core decomposition that is efficient in both theory and practice. Our algorithm is based on our novel parallel level data structure, inspired by the sequential level data structures of Bhattacharya et al [STOC '15] and Henzinger et al [2020]. Given a graph with $n$ vertices and a batch of updates $\mathcal{B}$, our algorithm provably maintains a $(2 + \varepsilon)$-approximation of the coreness values of all vertices (for any constant $\varepsilon > 0$) in $O(|\mathcal{B}|\log^2 n)$ amortized work and $O(\log^2 n \log\log n)$ depth (parallel time) with high probability. As a by-product, our $k$-core decomposition algorithm also gives a batch-dynamic algorithm for maintaining an $O(α)$ out-degree orientation, where $α$ is the current arboricity of the graph. We demonstrate the usefulness of our low out-degree orientation algorithm by presenting a new framework to formally study batch-dynamic algorithms in bounded-arboricity graphs. Our framework obtains new provably-efficient parallel batch-dynamic algorithms for maximal matching, clique counting, and vertex coloring. We implemented and experimentally evaluated our $k$-core decomposition algorithm on a 30-core machine with two-way hyper-threading on $11$ graphs of varying densities and sizes. [...]
BibTeX
@misc{liu2021parallel,
  author = {Quanquan C. Liu and Jessica Shi and Shangdi Yu and Laxman Dhulipala and Julian Shun},
  title = {{Parallel Batch-Dynamic Algorithms for $k$-Core Decomposition and Related Graph Problems}},
  year = {2021},
  eprint = {2106.03824},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.03824},
}

Loading related content...

Figure