{"id":"9dd44963-2003-48dd-9276-f679d348701a","arxiv_id":"2504.17615","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A multilevel graph partitioner with edge sparsification achieves proven linear expected work and a 1.49x average speedup in KaMinPar with only about 1% average cut increase.","lead":"This paper shows how to make multilevel graph partitioning run in time proportional to the graph size by pruning edges at every coarsening level, and it builds this into the KaMinPar partitioner, achieving a 1.49x average speedup with about 1% average quality loss. A generalist might read it because it removes a long-standing trade-off between partition quality and running time in large-scale graph processing.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Missing total-work lemma: Algorithm 1's rho-threshold gives no per-level edge shrink, so the O(n+m) claim needs a product bound that the paper never states or proves.","rationale":"I read the paper as making two distinct claims: a practical engineering claim (sparsification inside KaMinPar gives roughly 1.5x speedup with about 1% quality loss on selected hard instances) and a theoretical claim (provably O(n+m) expected work for every graph). The engineering claim is supported by careful experiments, though the benchmark set is deliberately biased toward sparsification-heavy graphs, as acknowledged in Section 6. The theoretical claim is the load-bearing part of the abstract. Theorem 1 is a real proof and appears correct under the idealized 2-hop rule stated in Section 4.1, and the construction has independent empirical support. The gap I found is that the transition from Theorem 1 plus Algorithm 1 to O(n+m) total work is not a theorem in the paper. The rho-threshold in Algorithm 1 intentionally skips sparsification when the ratio is below rho, so the per-level edge bound is rho * hat_m, not hat_m. With the tuned rho = 4 and tau_d = 1/2, this allows edge counts to increase by a factor up to about 1 + 320k/n_i at each level. A telescoping argument may still give a constant product, because n_i shrinks geometrically and the additive 160k term is O(k) at the stopping level, but the manuscript does not provide that argument. Since the central claim is precisely the linear-work guarantee, and since the missing argument is not merely cosmetic (the abstract overstates per-level shrink), the reader's conditional verdict is appropriate. My concern is partial agreement with the reader: the reader focused on the idealized 2-hop node-reduction assumption and the k log k term, whereas my strongest concern is the absent edge-sum/product lemma. Both are addressable by adding a formal statement and proof; neither by itself suggests the approach is wrong.","tokens_in":18352,"tokens_out":22318,"duration_ms":218722,"concrete_test":"Independently derive the missing total-work lemma: starting from Algorithm 1 and Theorem 1, track m_i+1 <= rho * min(tau_e, tau_d * n_i+1 / n_i) * m_i and n_i+1 <= n_i/2 + 160k, and verify whether sum_i m_i = O(m0) for the tuned rho = 4, tau_e = tau_d = 1/2 over all levels down to n_i = 160k. In particular, check whether the product prod_i (1 + 320k/n_i) is bounded by an absolute constant; if it is not, the implemented parameters do not certify linear work, and the paper must either restrict rho/tau_d or add the missing lemma before claiming O(n+m) in general.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline claim is an O(n+m) expected total work guarantee, but no theorem in the manuscript proves it. Section 4.2's Algorithm 1 triggers sparsification only if |E'_i+1| > rho * hat_m, with hat_m = min(tau_e |E_i|, tau_d (|E_i|/|V_i|) |V_i+1|). In the no-trigger case the only bound is |E_i+1| <= rho * hat_m. With the tuned parameters rho = 4, tau_e = tau_d = 1/2 and the Theorem 1 node bound |V_i+1| <= |V_i|/2 + 160k, this yields |E_i+1| <= 2 * ((|V_i|/2 + 160k)/|V_i|) * |E_i| = (1 + 320k/|V_i|) |E_i|. The factor exceeds 1 for every finite level, so there is no geometric edge reduction per level. The linear-time conclusion therefore depends on an unstated product/telescoping argument over the hierarchy; Section 4.3 only gives an informal sentence. Without such a lemma, an adversarial or even natural family in which contraction halves the node count while retaining almost all edges (e.g., edge count multiplied by 0.99 per level) would keep edge counts nearly constant for O(log n) levels, giving O(m log n) total work, matching the very worst case the paper claims to eliminate. The abstract's stronger statement that the graph shrinks by a constant factor at every successive step is not supported by the supplied argument, and the expected-work theorem alluded to in the abstract is never stated as a theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a multilevel graph partitioning coarsening scheme that adds edge sparsification to size-constrained label propagation with 2-hop clustering, with the aim of guaranteeing linear total work while retaining multilevel quality. Section 4 proves a constant-factor node-reduction theorem for an idealized 2-hop clustering model, introduces Algorithm 1 with edge/density thresholds and a sparsification trigger, and informally claims a geometric edge shrinkage that yields O(n+m) expected time. Section 5 relates the need for sparsification to low modularity. The engineering component integrates weighted threshold sampling into KaMinPar and reports a 1.49x geometric mean speedup with roughly 1% cut degradation, outperforming PuLP and Cuttana. The experiments are carefully designed and the measured behavior is consistent with the intended mechanism, but the advertised linear-time theorem is not actually stated or proved in the manuscript.","tokens_in":18671,"tokens_out":10401,"duration_ms":93820,"significance":"If the linear-work theorem could be rigorously established, the paper would resolve a well-known trade-off in practical graph partitioning: multilevel quality at single-level speed. The node-reduction proof is clean and the modularity-based characterization is a useful falsifiable empirical claim; the parameter study and comparison against PuLP and Cuttana are thorough, and the implementation-level analysis of where time is spent is strong. These contributions are real. However, the central theoretical claim---the unconditional O(n+m) expected total-work bound---is currently unsupported, so the significance statement must be downgraded until a formal theorem is supplied with explicit parameter conditions.","major_comments":[{"comment":"The advertised O(n + m) expected total-work guarantee is not stated as a theorem and does not follow from the ingredients given. With Algorithm 1, the no-trigger case only yields |E_{i+1}| <= rho * hat_m. For the tuned values tau_e = tau_d = 1/2 and rho = 4, and using the Theorem 1 node bound |V_{i+1}| <= |V_i|/2 + 160k, the density term of hat_m gives |E_{i+1}| <= (1 + 320k/|V_i|) * |E_i|, which is not a contraction for any finite |V_i|. The edge-threshold term gives the even weaker |E_{i+1}| <= 2|E_i|. Thus the analysis does not rule out hierarchies in which the edge count remains essentially constant for Theta(log n) levels, which would yield Theta(m log n) total work. A formal total-work theorem is needed; it must either impose parameter conditions such that rho * max{tau_e, tau_d * |V_{i+1}|/|V_i|} < 1 for all sufficiently large |V_i|, or supply a product/telescoping argument over the hierarchy, including the expectation over the randomized sparsification.","section":"Abstract; §4.2–4.3, Algorithm 1"},{"comment":"Theorem 1's proof requires that the 2-hop clustering merges every pair of singleton clusters that share the same favorite cluster; the text introduces this as an assumption (\"we will assume that the algorithm assigns a favorite cluster K_S to S...\"), but the paper does not establish that KaMinPar's actual 2-hop implementation satisfies this rule. If the implementation only merges singletons in a more restricted way, the bound |C1| <= |Ch|---and hence the geometric node-reduction factor used in Section 4.3---may fail for the integrated algorithm. Please either verify that the implementation matches the model exactly, or explicitly state Theorem 1 for the idealized model and add an empirical test that the implemented coarsening achieves the constant node-reduction factor on the benchmark graphs.","section":"§4.1, Theorem 1"},{"comment":"The statement \"The recursive bipartitioning then requires total time O(k log k), which is linear under the extremely weak assumption that k log k in O(n+m)\" conflicts with the abstract's claim of a guarantee \"without any assumptions on the input graph.\" For valid inputs with k = Theta(n), k log k = Theta(n log n), so the total work is not linear. The formal claim must explicitly state the dependence on k (e.g., k fixed, or k log k in O(n+m)) and cannot be presented as unconditional.","section":"§4.3"}],"minor_comments":[{"comment":"The quantity r is defined as the average cluster size of C2, but the case |C2| = 0 is not handled; the proof divides by r. This can be fixed by treating the case |C2| = 0 separately.","section":"§4.1, proof of Theorem 1"},{"comment":"The description of the sparsification step says the target is hat_m, but the sampling procedures produce hat_m edges only in expectation; the algorithm should state explicitly that the output size is the realized sample size and that the subsequent level's edge count is the realized one.","section":"§4.2, Algorithm 1"},{"comment":"The definition of alpha in Lemma 2 is imprecise: alpha = max_i a_i is the maximum fraction of edges incident to a single cluster, not \"the maximum fraction of edges with endpoints in the same cluster.\"","section":"§5, Lemma 2"},{"comment":"The comparison between KaMinPar, PuLP, and Cuttana excludes instances on which Cuttana crashes, but the sentence \"we exclude these instances in pairwise aggregates\" is ambiguous about whether the speedup and cut comparisons are recomputed on the common subset; please clarify.","section":"§6.3"},{"comment":"The captions \"T □ Weight\" and \"T □ WFF\" appear to contain formatting artifacts (missing hyphens or spaces); please check renderings.","section":"Figure 4 caption"}],"recommendation":"major_revision","confidential_remarks":"The paper's experimental contribution is solid and the node-reduction proof is elegant, but the headline theoretical result is currently absent from the manuscript. I would like the editor to treat the addition of a formal total-work theorem with explicit parameter conditions as a hard requirement, not a stylistic improvement; without it the abstract overclaims. If the authors can supply such a theorem, the paper would be a strong contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a strong engineering paper with a genuinely new idea, but the headline complexity claim is not actually proved. Theorem 1 is clean and useful, and the experimental work is careful, but the O(n+m) expected-work guarantee appears in the abstract and is only gestured at in Section 4.3.\n\nWhat's new and good: combining edge sparsification with multilevel coarsening to force hierarchy shrinkage is fresh. Theorem 1's constant-factor node-reduction bound for size-constrained label propagation with 2-hop clustering is a solid formal contribution. The modularity-based explanation of when sparsification is needed is a nice conceptual addition. The integration into KaMinPar with 1.49x geometric mean speedup and ~1% quality loss on a challenging benchmark is real, and the comparison against PuLP and Cuttana is honest.\n\nThe soft spot is exactly what the stress-test flags: there is no theorem in the body proving O(n+m) total work. Algorithm 1's trigger condition with rho=4 and tau_e=tau_d=1/2 does not obviously force a geometric edge decrease per level. If coarsening halves nodes but edges shrink by only a factor close to 1, the density term hat_m is about 0.25|E_i|, and rho*hat_m can be near or above |E_i|, so sparsification may not trigger. The worst case then remains O(m log n). The abstract's claim that the graph shrinks by a constant factor at every step is not supported by the supplied argument; a telescoping/product bound is missing. The k log k in O(n+m) assumption is mild but should be stated as a hypothesis rather than buried.\n\nThe benchmark set is deliberately selected to trigger sparsification; this is disclosed in Section 6 but not in the abstract, which overstates the universality of the practical gains. That does not invalidate the experiments, but it tempers the 'best of both worlds' framing.\n\nThis paper deserves a serious referee. The idea is valuable, the gap is likely addressable, and the engineering is credible. I would push for a formal statement and proof of the total-work bound, or a weaker but accurately stated bound, plus a clearer qualification of the benchmark selection.","headline":"Strong paper with a genuinely new idea, but the headline O(n+m) total-work claim is asserted, not proved; worth serious peer review.","tokens_in":19263,"tokens_out":13563,"would_cite":true,"duration_ms":114125,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that multilevel graph partitioning can be made to run in expected $O(n + m)$ time on any graph by capping every coarsening level with edge sparsification, and reports a $1.49\\times$ average speedup over KaMinPar with…","keywords":["graph partitioning","multilevel algorithms","coarsening","2-hop clustering","edge sparsification","linear time algorithms","balanced partitioning","modularity"],"falsifier":"Run the real coarsening on a graph with many singleton clusters while recording the favorite-cluster assignments, then check whether singleton pairs sharing a favorite remain unmerged; if a positive fraction of such pairs survives, the inequality $|C| \\le \\frac{1}{2}|V| + \\frac{c(V)}{U}$ can fail. Measuring total running time with the number of blocks $k$ growing like $n^\\alpha$ would likewise expose whether the $k \\log k$ budget holds.","tokens_in":18099,"feed_emoji":"⚡","tokens_out":14229,"duration_ms":124067,"temperature":0.7,"pith_summary":"Balanced graph partitioning has asked users to choose between high-quality but slow multilevel algorithms and fast but lower-quality single-level or streaming approaches. This paper claims the choice is unnecessary. It presents a coarsening scheme in which every level of the multilevel hierarchy shrinks by a constant factor: size-constrained label propagation and 2-hop clustering handle nodes, while a sparsification step caps the edge count whenever contraction would leave the level too dense. The paper proves this yields $O(n + m)$ expected total work on any graph with no structural assumptions, and it reports that integrating the scheme into the KaMinPar partitioner gives a $1.49\\times$ average speedup (up to $4\\times$) with only about $1\\%$ larger cuts, beating the single-level and streaming baselines on both speed and quality. It also shows that graphs with low modularity are the ones most likely to trigger the worst-case behavior that sparsification addresses.","feed_headline":"Proven linear time for multilevel graph partitioning","feed_subtitle":"Sparsification caps each level, giving linear expected time and a 1.49x speedup with 1% larger cuts.","key_machinery":"The load-bearing mechanism is a two-part coarsening scheme. Size-constrained label propagation forms clusters of neighboring nodes up to weight $U$, with the rule that no node stays alone if an adjacent cluster has room. A 2-hop clustering step then looks at each remaining singleton cluster, chooses a favorite neighboring cluster (the paper's term for its candidate partner), and merges all singletons that picked the same favorite, provided weights allow. This favorite-cluster rule is what makes Theorem 1's injection argument work: each singleton can be charged to a distinct heavy cluster, giving $|C_1| \\le |C_h|$. The second half of the machinery is the sparsification threshold $\\hat{m}$ and the weighted threshold sampling that enforces it; this is what converts a logarithmic number of unavoidable dense levels into a linear total.","core_discovery":"At the core of the paper is the observation that the two sources of superlinear work in multilevel partitioning—node counts that fail to shrink and edge counts that grow on coarse levels—can be attacked separately. The paper proves (Theorem 1) that if coarsening uses size-constrained label propagation followed by 2-hop clustering, the number of clusters satisfies $|C| \\le \\frac{1}{2}|V| + \\frac{c(V)}{U}$ for $U \\ge \\frac{2c(V)}{|V|}$, so every level shrinks by a constant factor once the cluster-weight limit is large enough. For edges, the paper introduces a sparsification step that caps each coarse level at $\\hat{m} = \\min\\{\\tau_e |E_i|, \\tau_d \\frac{|E_i|}{|V_i|}|V_{i+1}|\\}$ edges; the preferred weighted threshold sampling keeps the heaviest edges and samples among ties. Because sparsification is triggered only when it reduces the edge count by a constant factor $\\rho$, the geometric shrinking of both nodes and edges gives expected $O(n + m)$ total work. The empirical claim is that integrating this into KaMinPar produces a $1.49\\times$ average speedup with about $1\\%$ larger cuts.","pith_inferences":["If a real implementation merges fewer singleton pairs than the idealized favorite-cluster rule, the constant-factor node reduction may still hold with a slightly larger constant, so the linear-time guarantee could survive with adjusted thresholds.","The modularity diagnosis suggests a practical pre-screen: compute modularity first and enable aggressive sparsification only for low-modularity graphs, avoiding most of the 1% quality loss.","The same recipe—geometric node reduction plus a per-level edge budget—should transfer to other multilevel schemes, including hypergraph partitioning, where coarse-level edge growth is the usual source of superlinear work.","Because the proof is expected-time and sampling-based, a deterministic variant that always keeps the heaviest edges could convert the guarantee into deterministic linear time at possibly higher constant cost."],"forward_implications":["Any graph, regardless of structure, is covered by the $O(n + m)$ expected total-work bound, so multilevel partitioning no longer has an instance-dependent superlinear blow-up.","The algorithm remains genuinely multilevel, preserving the refinement quality of the hierarchy while keeping total work linear.","Graphs with low modularity, the ones that previously forced worst-case behavior, become the largest beneficiaries, with speedups up to $4\\times$ in the reported experiments.","In the reported comparisons, the method produces both smaller cuts and lower running times than the single-level baseline PuLP and the streaming baseline CUTTANA.","Parallel scalability is retained because the added sparsification step is linear-work and parallelizable."],"supporting_citations":[{"why":"Supplies the KaMinPar coarsening and refinement machinery, including the 2-hop clustering step the analysis builds on.","marker":"[28]"},{"why":"Defines size-constrained label propagation, the clustering rule whose termination property Theorem 1 requires.","marker":"[43]"},{"why":"Provides the theoretical basis for cut-sparsification guarantees that motivate using edge sparsification.","marker":"[9]"},{"why":"Empirically compares sparsification methods and supports choosing Forest Fire sampling as a cut-preserving candidate.","marker":"[16]"},{"why":"Introduces the Forest Fire edge-scoring algorithm whose scores the threshold-sampling variant uses.","marker":"[41]"},{"why":"Defines modularity, the quantity Lemma 2 uses to bound the fraction of intra-cluster edges.","marker":"[45]"},{"why":"Provides the Louvain heuristic used to estimate modularity on the benchmark graphs.","marker":"[10]"},{"why":"The single-level linear-time partitioner used as a quality and speed baseline.","marker":"[50]"},{"why":"The streaming partitioner used as a baseline for both quality comparisons and runtime comparisons.","marker":"[29]"}],"fun_headline_variants":["Linear-time multilevel graph partitioning via edge sparsification","Sparsification makes multilevel partitioning linear-time","Multilevel partitioning hits linear time with sparsification","Edge sparsification slashes multilevel partitioning time","Faster multilevel partitioning: sparsification guarantees linearity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The constant-factor node-reduction proof assumes the 2-hop clustering implementation actually merges every pair of leftover singletons that share the same favorite neighboring cluster when weights allow, and the $O(n + m)$ bound additionally assumes $k \\log k$ fits inside the linear budget for the number of blocks $k$; if either fails, the guarantee weakens to more than linear work.","fun_headline_variants_meta":{"raw":{"variants":["Linear-time multilevel graph partitioning via edge sparsification","Sparsification makes multilevel partitioning linear-time","Multilevel partitioning hits linear time with sparsification","Edge sparsification slashes multilevel partitioning time","Faster multilevel partitioning: sparsification guarantees linearity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000276,"raw_usage":{"total_tokens":1693,"prompt_tokens":1035,"completion_tokens":658,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":651,"completion_tokens_details":{"reasoning_tokens":579}},"tokens_in":651,"tokens_out":658,"duration_ms":6080,"temperature":1.0,"reasoning_tokens":579,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T10:36:15.461367+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the real coarsening on a graph with many singleton clusters while recording the favorite-cluster assignments, then check whether singleton pairs sharing a favorite remain unmerged; if a positive fraction of such pairs survives, the inequality $|C| \\le \\frac{1}{2}|V| + \\frac{c(V)}{U}$ can fail. Measuring total running time with the number of blocks $k$ growing like $n^\\alpha$ would likewise expose whether the $k \\log k$ budget holds.","supporting_citations":[{"cited_title":"Partitioning Complex Networks via Size-Constrained Clustering","cited_arxiv_id":null,"evidence_quote":"Defines size-constrained label propagation, the clustering rule whose termination property Theorem 1 requires."}],"review_version":1}