{"id":"6d06c9f4-3a6d-4860-a8da-2ed492363b5b","arxiv_id":"2502.08042","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A parallel peeling framework with O(n+m) work, combined with sampling, vertical granularity control, and hierarchical buckets, beats three prior parallel k-core implementations on 23 of 25 graphs.","lead":"This paper presents a parallel algorithm for k-core decomposition that is simple, provably work-efficient in the shared-memory setting, and fast on a 96-core machine. It adds sampling to reduce contention on high-degree vertices and a local-search technique that hides synchronization overhead on sparse graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2's correctness proof only handles vertices whose true degree is already below k at round start; mid-round crossings can delay peeling to round k+1 and are not bounded by the Las Vegas restart analysis.","rationale":"The reader's weakest-assumption analysis correctly identifies the mid-round crossing as the most load-bearing gap in the paper's central correctness claim. The proof of Theorem 4.2 is the only formal guarantee that the sampling scheme does not cause vertices to miss their peeling round. The argument relies on the vertex having already been below k at the start of the round, so that the number of coin tosses since the last SetSampler is at least d~[v]-k and the Chernoff bound applies before any wrong coreness is assigned. If the vertex crosses below k during the round, the same lower bound is not available at the moment of crossing: the degree may drop sharply after only a few neighbors are peeled, and unless cnt reaches μ, no resampling is triggered. At the next round, even a successful Validate failure does not repair the already-passed round; it merely assigns coreness k+1. The paper's Las Vegas recovery could in principle catch this and restart, but the trigger condition is described only informally in Sec. 4.1.4 and is not included in the probability bound of Theorem 4.2. This leaves the algorithm's exactness and its work bound unproven for a demonstrable execution scenario. The work-efficiency issue of repeated O(d(v)) resampling (Sec. 4.1.5) is also under-analyzed, but the correctness gap is more fundamental: an unproven error in coreness values undermines the practical claim of exact decomposition. The proposed synthetic test directly exposes whether the mid-round crossing alters the output or forces a restart, and would settle whether the concern is merely a missing proof case or an actual algorithmic flaw. The paper's other contributions—the O(n+m) framework of Alg. 1 without sampling, the VGC analysis, and the extensive experimental study—are not affected by this critique and are independent evidence of the framework's value.","tokens_in":31253,"tokens_out":24993,"duration_ms":201609,"concrete_test":"Construct a small synthetic graph (e.g., one high-degree vertex v with d~=101, r=0.1, μ=200, k=10) whose 92 neighbors all have coreness 10, so v crosses below 10 during round 10. Run the released implementation of Alg. 4 with sampling enabled on this graph, and check whether v is assigned coreness 10 or 11 (or whether a restart occurs). Repeat 1000 times with different random seeds. If v ever receives coreness 11 without a restart, the algorithm is incorrect; if restarts occur, compare the observed restart frequency against the claimed n^{-c} probability.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The sampling correctness proof (Theorem 4.2, Sec. 4.1.3) explicitly restricts the dangerous event to a sampled vertex whose true induced degree is below k at the beginning of round k. It shows that Validate(v,k) then fails whp and Resample adds v to the frontier before any coreness is assigned. However, a vertex can start round k with true degree at least k and cross below k during the round. If v is in sample mode and its sample counter cnt does not reach μ, it is not added to C in Peel (Alg. 5, line 7), so it is not resampled in the same round. Its stale d~[v] remains above k, so the active-set refinement on line 11 keeps v in A. At round k+1, validation may still return true (e.g., when r·d~[v] > k+1 and cnt < rate·(d~[v]-(k+1))/4), or may return false only after the correct round has passed, leading to coreness k+1 instead of k. The Las Vegas restart of Sec. 4.1.4 is described informally; the probability of triggering a restart for this mid-round crossing is not bounded, so neither the whp-correctness nor the work bound of Alg. 4 is established for this case.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a parallel k-core decomposition algorithm built on a simple frontier-based framework (Alg. 1). It claims an O(n+m)-work bound under natural assumptions (Thm. 3.1), and then introduces three practical optimizations: a sampling scheme for high-degree vertices (Sec. 4.1), vertical granularity control (VGC) to reduce subround synchronization overhead (Sec. 4.2), and a hierarchical bucketing structure (HBS) (Sec. 5). The experimental section compares the implementation against Julienne, ParK, and PKC on 25 real-world and synthetic graphs, reporting that it is fastest on 23 of 25 graphs and giving speedups of up to 315x over ParK.","tokens_in":31536,"tokens_out":22212,"duration_ms":206495,"significance":"If the theoretical claims are correct, the paper is a valuable contribution: Thm. 3.1 is a clean formalization of why simple active-set maintenance yields work efficiency, and the three optimizations address real bottlenecks that the experiments document carefully. The evaluation is extensive, including ablations for each technique, self-relative speedups, burdened-span measurements, and a heatmap over all eight combinations of the techniques. The code is released. However, the formal correctness and work-efficiency of the sampling-enabled algorithm are not established as written: the correctness proof covers only one failure mode, and the cost analysis of repeated resampling is incomplete. These points are load-bearing because sampling is one of the three main techniques and the paper's central claim is work efficiency.","major_comments":[{"comment":"Theorem 4.2 only analyzes vertices whose true induced degree is already below k at the start of round k. A vertex can instead cross from d* >= k to d* <= k during the round while it is in sample mode. If its sample counter has not reached mu, the vertex is not placed in C (Alg. 5, line 7), and the stale dtilde[v] keeps it in A at line 11. In round k+1, Validate may fail and Resample adds the vertex to F, after which coreness k+1 is assigned, even though the correct coreness is k. The probability of this mid-round event is not bounded anywhere in the proof. The Las Vegas restart discussion in Sec. 4.1.4 is informal and is not part of Alg. 4; it does not specify a check that runs before an incorrect coreness is written. A star graph gives a concrete instance: the center remains in sample mode while the leaves are peeled in round k=1, and if fewer than mu successful samples are collected, the center is subsequently assigned coreness 2 instead of 1. The analysis needs to validate/resample after the active set is refined, or else explicitly bound the mid-round crossing probability in the whp argument.","section":"Sec. 4.1.3, Thm. 4.2; Alg. 4 lines 5-11"},{"comment":"The claim that sampling preserves the O(n+m) work bound is not justified. Resample(v,k,F) scans the full neighbor list N(v) each time it is called, because it must count active neighbors. A vertex can be resampled many times: whenever cnt reaches mu, SetSampler re-enters sample mode as long as r*dtilde[v] > k and dtilde[v] > threshold, and each resampling reduces dtilde[v] only by a constant factor r. For a vertex with original degree d(v), this can happen Theta(log d(v)) times before dtilde[v] falls to the constant threshold, giving Theta(d(v) log d(v)) work for that vertex. The sentence 'the total cost to recount the true induced degree of v is O(d(v))' is therefore false without an additional amortized argument, for example, resampling in time proportional to the current active degree or maintaining a compact list of active neighbors. As written, Theorem 3.1 does not apply to Algorithm 4 because the cost of Resample is not charged in the theorem's Peel assumption.","section":"Sec. 4.1.5; Alg. 5, Resample lines 19-21"},{"comment":"The validation loop is written as 'parallel_foreach v in V : v is in sample mode', which as written appears to scan all of V in every round and would cost O(n) per round, hence O(kmax * n) total. Section 4.1.5 asserts that the validation cost is proportional to the number of vertices in sample mode and is therefore bounded by the active-set size, but no data structure is described that enumerates sample-mode vertices in that time. Please state explicitly that sample-mode vertices are maintained in a separate set (for example, the parallel hash bag) and that SetSampler and Resample update that set; otherwise the O(n+m) work bound for Algorithm 4 does not follow from the pseudocode as given.","section":"Sec. 4.1.1, Alg. 4 line 5"}],"minor_comments":[{"comment":"There is a typo: 'Another case to ressample v' should be 'resample v'.","section":"Sec. 4.1.1"},{"comment":"The line 'atomic_inc(sigma[u].cnt) with probability sigma[u].rate' is ambiguous: it should specify whether the random draw happens before the atomic increment and whether concurrent increments that fail the draw simply do nothing. A brief implementation note would remove the ambiguity.","section":"Alg. 5, line 6"},{"comment":"The statement that VGC 'does not change work-efficiency' should include a short argument that a vertex cannot be enqueued twice in the local queue or in both a local queue and Fnext under concurrent decrements; the current text asserts uniqueness without proving it.","section":"Sec. 4.2"},{"comment":"The contention bound 'O(kappa[v] + log n)' should clarify that the threshold in SetSampler is a fixed implementation constant and should be included in the asymptotic statement (or stated as a tunable parameter whose value does not affect the asymptotic bound).","section":"Sec. 4.1.5"}],"recommendation":"major_revision","confidential_remarks":"The experimental contribution appears solid and the reported speedups are plausible, but the theoretical analysis of the sampling technique needs substantial rework before the paper can be accepted. The gaps are fixable in principle: one can add a post-round validation step or bound mid-round crossings, and one can either prove an amortized bound on Resample or modify the resampling procedure to avoid scanning the full neighbor list repeatedly. I do not see evidence of bad faith, and the authors should be given a chance to address these points."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main thing you should know: this is a genuinely good systems paper with a clean O(n+m) parallel framework, but the sampling correctness proof has a real gap. It's not a fatal flaw for the practical contribution, but the theoretical claim is weaker than stated.\n\nThe framework in Alg. 1 is the nicest part. The observation that the active-set sizes sum to O(n+m) via kappa(v) <= d(v) is elementary but apparently new in this context, and it makes work-efficiency analysis very clean. Theorem 3.1 is correct. The two practical techniques -- sampling to reduce contention and VGC to hide scheduling overhead -- are well-motivated and the experiments support them. HBS is a reasonable bucketing improvement. The evaluation is extensive: 25 graphs, a broad mix, and the algorithm beats all baselines on 23 of them, often by huge margins. Code is released. That is real evidence.\n\nThe soft spot is the sampling analysis. Theorem 4.2 only handles vertices whose true degree is already below k at the start of a round. It does not cover a vertex that starts the round above k, crosses below k during the round, fails to collect enough samples, and then gets peeled in the next round with coreness k+1 instead of k. The Las Vegas recovery in Sec. 4.1.4 is informal; there is no bound on the probability of triggering a restart, so the whp correctness of Alg. 4 is not established. This is not a nitpick -- it's a load-bearing gap in the theoretical claim. It is probably fixable, either by extending the analysis or by changing the sampling scheme to validate more frequently, but as written the proof doesn't cover it.\n\nMinor issues: no error bars on the timing experiments, and Lemma 4.1's derivation has a sloppy sign handling in the Chernoff bound. Neither changes the practical picture.\n\nWho is this for? Anyone implementing k-core at scale or working on parallel graph primitives. The systems contribution stands on its own, and the framework is likely to influence future work. The paper was accepted at SIGMOD, so it already went through serious review. If I were refereeing it now, I would ask for the sampling gap to be addressed, but I would not desk-reject it. I'd cite it for the framework and the experimental comparison.","headline":"Strong practical parallel k-core paper with a clean work-efficient framework, but the sampling correctness proof has a real gap around mid-round crossings.","tokens_in":32075,"tokens_out":6879,"would_cite":true,"duration_ms":56661,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68W10","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A simple parallel framework computes exact $k$-core decompositions in $O(n+m)$ work, and its tuned implementation is the fastest among four state-of-the-art parallel codes on 23 of 25 test graphs.","keywords":["k-core decomposition","parallel algorithms","work-efficiency","graph peeling","sampling scheme","granularity control","hierarchical bucketing"],"falsifier":"Construct a graph with a high-degree vertex whose induced degree drops below $k$ in the middle of a subround, run Algorithm 4 with the stated sample-rate parameters, and inspect the final coreness values; a single vertex peeled one round late (coreness overestimated by 1) would disprove the whp correctness claim.","tokens_in":31036,"feed_emoji":"🕸️","tokens_out":8043,"duration_ms":62084,"temperature":0.7,"pith_summary":"The paper claims that work-efficient parallel $k$-core decomposition can be achieved by a simple frontier-peeling framework, without the heavy bucketing machinery previously thought necessary. The key observation is that maintaining an active set and spending time proportional to that set in each round sums to $O(n+m)$ over all rounds, because every vertex appears in as many active sets as its coreness value. To make the framework fast in practice, the paper adds three mechanisms: a sampling scheme that reduces atomic-operation contention on high-degree vertices, vertical granularity control that processes small local queues to hide scheduling overhead on low-degree vertices, and a hierarchical bucketing structure for graphs with large coreness values. If these claims hold, the result is a single parallel algorithm that avoids the worst-case slowdowns each existing baseline suffers on some graph type.","feed_headline":"A simpler parallel k-core method wins on 23 of 25 graphs","feed_subtitle":"Sampling, granularity control, and hierarchical buckets remove the worst-case slowdowns of existing parallel peelers.","key_machinery":"The load-bearing identity is the active-set summation $\\sum_{i=0}^{k_{\\max}} |A_i| = \\sum_{v\\in V}(1+\\kappa(v)) \\le n+m$, which bounds the cost of re-scanning the active set once per round. Algorithm 1 extracts a frontier $F$ of vertices whose induced degree equals $k$, assigns them coreness $k$, peels them by decrementing neighbors' induced degrees, and then packs the active set down to vertices with induced degree above $k$. The three practical techniques are implementations of these steps: sampling replaces atomic decrements on high-degree vertices with probabilistic sample counts; vertical granularity control runs a bounded local search inside each subround to merge small tasks; and the hierarchical bucketing structure organizes vertices by exponentially growing degree ranges so frontier extraction costs $O(\\log d(v))$ per vertex instead of $O(d(v)/b+b)$.","core_discovery":"The central claim is Theorem 3.1: in the frontier-based peeling framework of Algorithm 1, if peeling a frontier $F$ costs $O(|F| + \\sum_{v\\in F} d(v))$ and each round's initial-frontier extraction and active-set refinement cost $O(|A|)$, then the total work is $O(n+m)$. The proof rests on the identity $\\sum_{i=0}^{k_{\\max}} |A_i| = \\sum_{v\\in V} (1+\\kappa(v)) \\le n+m$, since coreness never exceeds degree. The paper then shows that an online peeling version with a sampling scheme for high-degree vertices, a local-search vertical granularity control for low-degree vertices, and a hierarchical bucketing structure preserves this work bound while improving parallelism and burdened span. On a 96-core machine the implementation is the fastest on 23 of 25 graphs, with speedups up to $315\\times$ over ParK, $33.4\\times$ over PKC, and $52.5\\times$ over Julienne, and self-relative speedups of roughly $7.5$--$86\\times$.","pith_inferences":["The active-set summation argument is generic enough that the same framework should transfer to other peeling-based computations such as degeneracy ordering, nucleus decomposition, or D-core decomposition, where a round-based frontier loop scans a shrinking set.","A sharper correctness analysis would explicitly bound the mid-round crossing case, where a sampled vertex falls below $k$ after the round-start validation but before the active-set refinement; this is the natural stress test for the high-probability guarantee.","The burdened-span reduction suggests a reusable design principle: any synchronous peeling implementation with many subrounds should benefit from bounded local queues that merge small tasks, even outside $k$-core decomposition."],"forward_implications":["The simplified Julienne implementation is work-efficient, and the existing $O(m+k_{\\max} n)$ online algorithms become work-efficient once they maintain an active set.","Sampling lowers the contention on a high-degree vertex from $O(d(v))$ to $O(\\kappa(v)+\\log n)$ while keeping the algorithm exact with high probability.","Vertical granularity control reduces the number of subrounds by 5--40$\\times$ on tested graphs and cuts the burdened span by up to about 147$\\times$ relative to Julienne.","The hierarchical bucketing structure reduces per-vertex maintenance cost from $O(d(v)/b+b)$ to $O(\\log d(v))$, and stays competitive with a single bucket on sparse graphs.","The full implementation is the fastest parallel code on 23 of 25 graphs, always beating the best sequential time by 7.3--84$\\times$."],"supporting_citations":[{"why":"Supplies the prior bucketing-based work-efficient framework and the offline peeling baseline that the paper analyzes and compares against.","marker":"[19]"},{"why":"The sequential BZ algorithm whose O(m) time sets the work-efficiency target and is used as a sequential baseline.","marker":"[10]"},{"why":"The ParK online peeling algorithm, a main baseline and example of the O(m + kmax n) work bound the framework improves.","marker":"[18]"},{"why":"The PKC online algorithm with thread-local buffers, another main baseline and the source of the scheduling trade-off discussed.","marker":"[38]"},{"why":"The GBBS library that provides the Julienne implementation used in the experiments.","marker":"[20]"},{"why":"Defines burdened span, the metric used to quantify scheduling overhead that vertical granularity control reduces.","marker":"[37]"},{"why":"Source of the vertical granularity control idea adapted here to hide scheduling overhead in graph peeling.","marker":"[24]"},{"why":"Provides the parallel hash bag used to implement frontiers and the hierarchical buckets.","marker":"[25]"}],"fun_headline_variants":["Parallel k-core: simpler, faster on 23 of 25 graphs","New parallel k-core wins 23 of 25 benchmarks","Simple parallel k-core: sampling, granularity, buckets","K-core parallelism: up to 315x faster on 96 cores","Parallel k-core: simple framework, huge speedups"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The sampling proof assumes the only dangerous event is a vertex whose true remaining degree is already below $k$ when round $k$ begins; a vertex that crosses below $k$ during the round is not explicitly bounded in the analysis.","fun_headline_variants_meta":{"raw":{"variants":["Parallel k-core: simpler, faster on 23 of 25 graphs","New parallel k-core wins 23 of 25 benchmarks","Simple parallel k-core: sampling, granularity, buckets","K-core parallelism: up to 315x faster on 96 cores","Parallel k-core: simple framework, huge speedups"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000612,"raw_usage":{"total_tokens":2875,"prompt_tokens":1001,"completion_tokens":1874,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":617,"completion_tokens_details":{"reasoning_tokens":1788}},"tokens_in":617,"tokens_out":1874,"duration_ms":11778,"temperature":1.0,"reasoning_tokens":1788,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T11:04:38.250473+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a graph with a high-degree vertex whose induced degree drops below $k$ in the middle of a subround, run Algorithm 4 with the stated sample-rate parameters, and inspect the final coreness values; a single vertex peeled one round late (coreness overestimated by 1) would disprove the whp correctness claim.","supporting_citations":[{"cited_title":"Blelloch, and Julian Shun","cited_arxiv_id":null,"evidence_quote":"Supplies the prior bucketing-based work-efficient framework and the offline peeling baseline that the paper analyzes and compares against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The ParK online peeling algorithm, a main baseline and example of the O(m + kmax n) work bound the framework improves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The PKC online algorithm with thread-local buffers, another main baseline and the source of the scheduling trade-off discussed."},{"cited_title":"Blelloch, and Julian Shun","cited_arxiv_id":null,"evidence_quote":"The GBBS library that provides the Julienne implementation used in the experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines burdened span, the metric used to quantify scheduling overhead that vertical granularity control reduces."}],"review_version":1}