Clustering large-scale networks is a central topic in unsupervised learning, with critical applications in community detection, spam discovery, and data visualization. This paper, originally presented at ICML 2019, introduces a new suite of massively parallel algorithms for two fundamental graph clustering problems: densest subgraph and $k$-core decomposition. By leveraging novel vertex-sampling techniques and local neighborhood simulations, the authors achieve exponential and quadratic speedups in computation rounds compared to previous state-of-the-art methods.
The Challenge of Sequential "Peeling"
In the era of massive social and biological networks, identifying "dense" regions is paramount. Two primary ways to define these regions are:
- Densest Subgraph: Finding a subset of vertices with the highest edge-to-vertex ratio.
- $k$-core Decomposition: Partitioning a graph into layers where each vertex in a $k$-core belongs to a subgraph where every node has a degree of at least $k$.
The core challenge is that these problems are inherently sequential. The standard approach involves "peeling" the graph—repeatedly removing the lowest-degree vertices. In a parallel environment like MapReduce, Spark, or the theoretical Massively Parallel Computation (MPC) model, this iterative process usually requires $O(n)$ or $O(\log n)$ rounds of communication between machines. For graphs with billions of edges, even $O(\log n)$ rounds can be prohibitively slow due to massive network overhead.
Breaking the Logarithmic Barrier
The authors design MPC algorithms that break the traditional $O(\log n)$ round barrier. They operate within two memory regimes: "almost linear" (memory per machine roughly equals the number of vertices $n$) and "sublinear" (memory scales to $n^\delta$ for a small $\delta$).
Key Techniques
- Vertex-Based Sampling: Instead of traditional edge sampling, the authors use vertex-based sampling to create induced subgraphs. This effectively "compresses" the graph while preserving the density properties needed to estimate coreness.
- Local Simulation (Round Compression): To beat the $O(\log n)$ limit, the authors use a graph exponentiation approach. A machine gathers a $T$-hop neighborhood of a vertex and simulates $T$ iterations of the peeling algorithm locally. This compresses $T$ communication rounds into just $O(\log T)$ or even $O(1)$ rounds.
- Handling "Heavy" Nodes: In the sublinear memory regime, a single high-degree node could exceed a machine's memory. The authors introduce a "freezing" mechanism: nodes with degrees exceeding a specific threshold are handled separately, ensuring no machine is overloaded while maintaining approximation guarantees.
- MWU Compression: For the densest subgraph problem, they adapt the Multiplicative Weights Update (MWU) framework, compressing many iterations of the dual LP solver into fewer MPC rounds.
Datasets and Scale
The authors evaluated their algorithms on several large-scale public graphs from the SNAP collection, ranging from hundreds of thousands to tens of millions of nodes.
The Friendster dataset is particularly notable. With over 1.8 billion edges, it represents the "very large" scale where traditional linear-memory algorithms often fail due to memory constraints.
Key Results
The theoretical "aha moment" of the paper is proving that we don't need to communicate after every peeling step. By carefully sampling and gathering local neighborhoods, the algorithm can predict the "fate" of a vertex many steps in advance.
Theoretical Speedups
- $k$-core (linear memory): Improved from $O(\log n)$ to $O(\log \log n)$ rounds for a $(1+\epsilon)$-approximation.
- $k$-core and Densest Subgraph (sublinear memory): Improved from $O(\log n)$ to $\tilde{O}(\sqrt{\log n})$ rounds.
Empirical Performance
The authors show that sublinear space algorithms are not just a theoretical curiosity—they are faster in practice because each machine processes less data, significantly reducing communication overhead per round.
- Their sublinear algorithm (FKC) was significantly faster than the previous state-of-the-art (SKC).
- On the Orkut dataset, their vertex-partitioning strategy (VKC) outperformed the previous best method by more than a factor of 2.
- Crucially, on the massive Friendster dataset, previous methods (SKC/VKC) failed entirely due to memory requirements. In contrast, the sublinear FKC algorithm completed the task efficiently.
Limitations and Future Work
While the results are a massive leap forward, there is an approximation trade-off. In the sublinear memory regime, the $k$-core algorithm provides a $(2+\epsilon)$-approximation, whereas the linear-memory version provides a tighter $(1+\epsilon)$-approximation.
The authors highlight a compelling open question for the community: Is it possible to achieve a $(1+\epsilon)$-approximation for $k$-core decomposition in $o(\log n)$ rounds using only sublinear memory per machine? Solving this would close the final gap in massively parallel density-based clustering.
Summary updated