Parallel Batch-Dynamic k-Core Decomposition

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

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 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(\alpha)$ out-degree orientation, where $\alpha$ is the current arboricity of the graph. Our framework obtains new provably-efficient parallel batch-dynamic algorithms for maximal matching, clique counting, and vertex coloring.

Introduction

In network analysis, a $k$-core is a maximal subgraph where every vertex has at least $k$ neighbors within that subgraph. Identifying these cores is essential for uncovering dense communities, but maintaining them in dynamic settings—where edges are constantly added or deleted—is notoriously difficult.

The core challenge is the "cascade effect": a single edge update can theoretically alter the coreness values of every other vertex in the graph. While sequential algorithms exist, they are too slow for modern massive graphs. Previous parallel attempts lacked theoretical guarantees on "depth" (the longest chain of sequential dependencies), meaning they couldn't effectively utilize many-core processors for large batches of updates. This paper introduces the first parallel, batch-dynamic algorithm for $(2+\epsilon)$-approximate $k$-core decomposition with provable polylogarithmic depth.

Comparison between exact k-core and approximate k-core structures.

The Parallel Level Data Structure (PLDS)

The authors introduce the Parallel Level Data Structure (PLDS), which is fundamentally redesigned to handle batches of updates simultaneously in a parallel environment.

  • Level Partitioning: Vertices are partitioned into $O(\log^2 n)$ levels based on their induced degrees. The "level" of a vertex serves as a proxy for its coreness.
  • Batch Processing: Instead of processing updates one by one, the PLDS processes a batch $B$ of updates. It uses a movement rule where vertices move levels only when specific degree invariants are violated, preventing unnecessary recomputations.
  • Polylogarithmic Depth: By allowing all vertices at a specific level to be checked and moved in parallel, the algorithm achieves a depth of $O(\log^2 n \log \log n)$, ensuring it scales well on multicore machines.

A General Framework for Dynamic Graph Problems

The PLDS also maintains a "low out-degree orientation," which the authors leverage to create a general framework for other dynamic graph problems.

The PLDS framework and its applications to various graph problems.

As illustrated above, the framework provides efficient parallel batch-dynamic solutions for:

  • k-Core Decomposition and Out-Degree Orientation (using levels).
  • Maximal Matching and k-Clique Counting (using orientation).
  • Vertex Coloring (using both levels and orientation).

Key Insights and Results

By relaxing the goal to a $(2+\epsilon)$-approximation, the authors break the theoretical barrier of P-completeness associated with exact $k$-core decomposition. The algorithm uses "hysteresis"—waiting until enough error accumulates before updating a vertex's level—to amortize update costs over many edge changes, leading to $O(|B| \log^2 n)$ total work.

Evaluated on a 30-core machine across 11 diverse graphs (including twitter and friendster with billions of edges), the PLDS demonstrated dramatic performance gains:

  • Speedup: Up to 723x faster than the best sequential exact algorithms and 114x faster than state-of-the-art parallel exact algorithms.
  • Scalability: While other dynamic algorithms timed out on the largest datasets, the PLDS completed all experiments within the three-hour limit.
  • Accuracy: Despite being an approximation, the empirical error remained very close to exact values, far outperforming the theoretical $(2+\epsilon)$ bound.

Conclusion

This work provides the first parallel batch-dynamic algorithm for approximate $k$-core decomposition that is efficient in both theory and practice. While the current structure requires $O(n \log^2 n + m)$ space to achieve optimal depth, future work may focus on achieving linear space without sacrificing performance.

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(\alpha)$ out-degree orientation, where $\alpha$ 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 k-Core Decomposition}},
  year = {2021},
  eprint = {2106.03824},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.03824},
}
Figure