Finding the $k$-core of a graph means repeatedly deleting every vertex with fewer than $k$ remaining neighbors until none is left. The resulting "coreness" numbers are a standard tool for finding dense communities in social and web graphs. The deletion process, called peeling, is inherently sequential, because one deletion can lower a neighbor's degree and trigger the next. On clusters where each machine holds only a small slice of the graph, the best known method trades away accuracy to stay fast. Improved Parallel Algorithms for Density-Based Network Clustering gets a $(1+\epsilon)$-approximation in $O(\log\log n)$ rounds when a machine can hold $O(n)$ words. When machines hold only $n^\delta$ words it falls to a $(2+\epsilon)$-approximation in $\tilde O(\sqrt{\log n})$ rounds. The authors leave open whether $(1+\epsilon)$ is possible in $o(\log n)$ rounds in that regime.
The loss comes from high-degree "heavy" vertices whose neighborhoods do not fit on one machine, so the algorithm freezes them and handles them coarsely. We propose to borrow a trick from graph coloring. In palette sparsification and the nibble method, each element keeps only a small random sample of its options and commits only a small fraction of choices per round, so that the sample stays statistically faithful. Here, each vertex keeps a small random set of neighbors, which we call a certificate, sized to the degree threshold currently being tested rather than to its full degree. Vertices whose fate is ambiguous are peeled cautiously so that surviving certificates do not erode faster than they can be checked. If this works, heavy vertices fit in sublinear memory without being frozen. The aim is to keep $(1+\epsilon)$ accuracy at round counts comparable to the sublinear method.
Core Claim
Freezing heavy vertices is not necessary for round compression. A vertex's role in peeling at threshold $\tau$ depends only on whether its live degree is above or below $\tau$. That question can be answered to within a $(1\pm\epsilon)$ factor from about $\log n/\epsilon^2$ random neighbors, however large the true degree is. The certificate size follows from a Chernoff bound on a sample with expected size $\Theta(\log n/\epsilon^2)$ at the threshold.
For each threshold $\tau$ on a geometric ladder $\tau_i=(1+\epsilon)^i$, vertex $v$ keeps each incident edge independently with probability
$$p_\tau = \min\left(1, \frac{C\log n}{\epsilon^2 \tau}\right),$$
where $C$ is a constant. The vertex then estimates its live degree as the number of surviving sampled neighbors divided by $p_\tau$. In the sampled graph every vertex near the threshold has degree $O(\log n/\epsilon^2)$. A vertex far above the threshold needs to retain only $O(\log n/\epsilon^2)$ sampled edges as proof that it survives, so the rest can be discarded. $T$-hop neighborhoods in the sampled graph then fit in $n^\delta$ memory for $T$ up to roughly $\delta\log n/\log(\log n/\epsilon^2)$. Ghaffari et al.'s local simulation, where each machine gathers a $T$-hop neighborhood and runs $T$ peeling rounds without communication, can therefore be applied to every vertex, heavy ones included.
The second ingredient addresses certificate erosion, which is what breaks a naive version. Once some of a vertex's sampled neighbors are deleted, its estimate is computed from fewer samples and grows noisier. Its true degree may also have dropped through neighbors that were never sampled. We split vertices each round into three groups. Those clearly below the threshold, with estimate under $(1-\epsilon)\tau$, are peeled at once, which is safe. Those clearly above it are kept. Those in the ambiguous band peel only with a small probability per round, the analogue of the nibble's tentative commitment.
This bounds how much any survivor's certificate can change per round. In the coloring analyses of Near-Optimal, Distributed Edge Colouring via the Nibble Method and Palette Sparsification Beyond (Δ+1) Vertex Coloring, the same bound is what keeps palettes concentrated. A certificate is redrawn, which costs one communication round, only when it has lost an $\epsilon$-fraction of its samples. The theoretical target is to show that each threshold needs only $O(\mathrm{poly}(1/\epsilon))$ redraws, which together with round compression would give $(1+\epsilon)$-approximate coreness in $o(\log n)$ rounds at sublinear memory.
Relation to Prior Work
Three works define the problem and three supply methods.
The gap and the reference design come from Ghaffari, Lattanzi and Mitrović. Our protocol keeps their $T$-hop local simulation and vertex sampling. It replaces their heavy-vertex freezing with threshold-scaled certificates. A secondary motivation is Parallel Batch-Dynamic k-Core Decomposition, which also settles for $(2+\epsilon)$ to stop cascades, in that case by using slack between levels. We do not target the dynamic setting.
The closest method is Parallel and Streaming Algorithms for K-Core Decomposition. It samples edges globally at one rate, peels the sample, locks vertices whose coreness is confidently high, doubles the rate and repeats, which gives $O(\log n)$ MapReduce rounds. We differ in three ways. Our sampling rate is set per threshold and capped per vertex, rather than being a single global rate that doubles. We pair sampling with local simulation, which is the source of the round savings. We control estimates that go stale as neighbors are deleted, which their analysis avoids by recomputing each phase.
The cautious-commitment mechanism comes from the coloring literature. Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time shows that nibbling combined with subsampling keeps dependency chains short. We use the same logic to keep certificate erosion small.
Nibbling at Long Cycles also imposes a constraint we take seriously. Nibble concentration needs degrees of order $\mathrm{polylog}(n)$, and that requirement carries over here. At thresholds $\tau \le C\log n/\epsilon^2$ we sample nothing, setting $p_\tau=1$, and peel exactly. Low thresholds are exactly where neighborhoods are small, so the two regimes complement each other.
Research Program
The theory question is whether the redraw count per threshold can be bounded. Each band vertex is peeled with probability $q$ per round. Then a survivor's certificate loses in expectation at most a $q$-fraction of its band neighbors per round, plus the clearly-below neighbors. The difficulty is that clearly-below deletions can cascade within a single round. We plan to bound that cascade by the same argument that controls palette shock: a martingale over the random sample, conditioned on the deletion history.
If the bound holds with $q=\Theta(\epsilon)$, each threshold needs $O(1/\epsilon)$ nibble rounds per compressed batch. The thresholds are processed in parallel as in Ghaffari et al. The round complexity would then be their $\tilde O(\sqrt{\log n})$ times a $\mathrm{poly}(1/\epsilon)$ factor, with no fall to $(2+\epsilon)$. If the bound fails, the analysis should identify a concrete adversarial structure, such as hub-and-spoke cascades, that forces $\Omega(\log n)$ redraws. That would be a useful negative result on the open question.
The engineering side is a simulator of the Massively Parallel Computation (MPC) model: many machines, each with an $n^\delta$-word memory cap, communicating in synchronous rounds. The simulator enforces the memory cap and counts rounds and total communication. We implement our protocol, Ghaffari et al.'s sublinear algorithm (which they call FKC) and the Esfandiari adaptive sketching algorithm in the same simulator.
Baselines
The naive reference point is exact sequential peeling by bucket sort, run on one large-memory machine as SNAP permits. SNAP: A General-Purpose Network Analysis and Graph-Mining Library reports holding over 120 billion edges in 1TB of RAM. Exact peeling supplies ground-truth coreness and a wall-clock reference. It is not an MPC competitor, since it ignores the memory cap.
The strongest competitor on round count is Ghaffari et al.'s FKC. It is the only cited method that runs at $n^\delta$ memory in $o(\log n)$ rounds, and the paper reports that it completed on Friendster where the earlier linear-memory methods "failed entirely due to memory requirements." No reported result found on Lacuna for FKC's per-vertex coreness error or its exact round count on these graphs.
The strongest competitor on accuracy is Esfandiari et al.'s adaptive sketching, which gives $(1+\epsilon)$ guarantees in $O(\log n)$ rounds. It reports that "for nodes with a coreness of at least 5, the median error was consistently below 25%" when tuned.
All methods run in the same simulator with the same $\delta$, number of machines and $\epsilon$. Each receives the same budget of hyperparameter configurations for sampling constants and thresholds, tuned on a held-out small graph. We beat FKC if we achieve strictly lower maximum and 99th-percentile multiplicative coreness error at no more than a constant factor more rounds. We beat adaptive sketching if we match its error with asymptotically fewer rounds as $n$ grows across SNAP graphs of increasing size.
Three ablations isolate the ingredients:
- Freezing instead of certificates. Heavy vertices are frozen as in FKC while everything else is kept, which tests whether certificates are what remove the factor-2 loss.
- Peeling the whole band at once. The ambiguous band is peeled in a single step with no nibbling, which tests whether cautious commitment matters.
- No redraws. Certificates are never redrawn, which measures erosion directly.
Why not just…?
Why not just sample edges uniformly once and simulate peeling on the sample? Esfandiari et al. tested this and report that "simple uniform sampling fails here because it cannot accurately estimate the coreness of low-degree nodes." Ghaffari et al. likewise found that uniform edge sampling did not keep neighborhoods within memory bounds. Threshold-scaled rates address both failures. We include uniform sampling with local simulation as an extra baseline so the claim is checked on our own graphs, not taken on trust.
Why not just run FKC, since $(2+\epsilon)$ algorithms are near-exact in practice? This is the most serious threat. PLDS reports that "the empirical error remained very close to exact values, far outperforming the theoretical $(2+\epsilon)$ bound." On SNAP graphs FKC's empirical error might already be small, which would leave our empirical advantage marginal. We will therefore report error on the tail, the maximum and the vertices with the highest coreness, not only the median. We will also add adversarial instances: planted dense cores attached to high-degree hubs, where freezing hubs should visibly misestimate coreness. If FKC is near-exact on both the real and the planted graphs, the contribution reduces to the worst-case theorem and we will say so.
Why not just run adaptive sketching longer, accepting $O(\log n)$ rounds? On a fixed graph the difference between $\log n$ and $\sqrt{\log n}$ rounds is a small constant factor. Coordination overhead might hide that difference in practice. The experiment that settles this plots rounds against $n$ across graphs from Enron to Friendster at fixed error. If the two curves are indistinguishable, the round advantage is only asymptotic and we will report it that way.
Proposed Experiments
We will use the SNAP graphs used by the cited works, from Enron through Orkut, plus Friendster with more than 1.8 billion edges, where linear-memory methods fail, at $\delta\in\{0.5,0.7\}$. We measure four things:
- communication rounds;
- peak machine memory relative to $n^\delta$;
- total communication volume;
- multiplicative coreness error against exact peeling, reported as median, 99th percentile and maximum, overall and stratified by coreness band.
Planted-hub graphs at controlled sizes stress the heavy-vertex case.
Three checks are decisive. First, on Friendster at $\delta=0.5$, our protocol should stay under the memory cap while achieving lower maximum error than FKC. Second, the no-redraw ablation should show error growing with the number of peeling rounds, and full redraws should restore it. That would confirm that erosion is the real obstacle and that the cautious peeling controls it. Third, on planted-hub graphs, the freezing ablation should reproduce error near a factor of 2 that certificates remove. If the first check holds and the third does not, heavy-vertex freezing was not the bottleneck and the hypothesis is wrong.
References
- Improved Parallel Algorithms for Density-Based Network Clustering
- Near-Optimal, Distributed Edge Colouring via the Nibble Method
- Palette Sparsification Beyond (Δ+1) Vertex Coloring
- Parallel Batch-Dynamic k-Core Decomposition
- Parallel and Streaming Algorithms for K-Core Decomposition
- Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time
- SNAP: A General Purpose Network Analysis and Graph Mining Library