{"id":"71752b58-897f-4280-a5fb-7249d67d065d","arxiv_id":"2411.19901","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"Replacing per-vertex hash tables with 8-slot Misra-Gries sketches makes GPU label propagation use O(|V|) memory instead of O(|E|), cutting memory up to 98x with roughly 5% modularity loss.","lead":"Community detection finds groups of densely connected nodes in a huge network. This paper shows a new GPU version of the label propagation algorithm that uses small summary sketches instead of large per-node tables, cutting memory use by up to 98x while staying fast and keeping most of the community quality.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Single-scan shortcut (Sec 4.4) rests on MG sketch weights tracking true neighbor-label weights; it is only tested on the same 13 graphs, and road/k-mer graphs already show much larger quality drops, so 'minimal quality loss' is not established generally.","rationale":"The reader's weakest assumption correctly identifies Section 4.4's single-scan shortcut as the key unproven step. My concern is the same section but with a sharper mechanism: the MG sketch's slot weights are not true aggregate weights because decrements bias them, so the max sketch weight can point to a label that is not the true max-weight neighbor label. The paper's only defense is an in-sample experiment on the same 13 graphs used for final claims, and even there the quality loss is uneven, with road and k-mer graphs dropping far more than the average. This is load-bearing because the abstract's 'minimal quality loss' is the trade-off that makes the memory savings attractive; if the shortcut is unsafe on other graph families, the headline claim overstates the method's generality. The memory-efficiency contribution (O(|V|) working space) is structurally sound and independently supported by the design and the sk-2005 result, so the concern does not warrant rejection. It does, however, reinforce the reader's conditional verdict: the paper needs out-of-sample validation of the shortcut, not just the same graphs used for parameter selection and final reporting. I chose UNCHANGED because the reader's CONDITIONAL verdict already captures this need; my analysis provides a more precise mechanism but does not move the verdict.","tokens_in":132,"tokens_out":5801,"duration_ms":70753,"concrete_test":"Run the released code on 5 held-out graphs not in Table 1, spanning different domains (e.g., soc-Friendster, roadNet-CA, a large web crawl such as uk-2014, and two LFR synthetic graphs with mixing parameters 0.3 and 0.6). For each graph, execute both the single-scan variant (Algorithm 1) and the double-scan variant (Algorithm 4 with rescan enabled) using identical parameters, then compute the modularity difference and the per-vertex fraction of labels where the single-scan choice differs from the true max-weight label obtained by the second scan. If any held-out graph shows a modularity drop greater than 5% or a label mismatch rate greater than 10%, the single-scan shortcut is not generally valid and the abstract's 'minimal quality loss' must be qualified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quality claim depends on the single-scan decision rule introduced in Section 4.4: after populating an 8-slot Misra-Gries sketch, the algorithm selects the label with the largest sketch weight without a second scan. This is only correct if the MG sketch's internal slot weights are faithful proxies for the true total neighbor-label weights. They are not: the MG decrement operation subtracts a constant from all slots whenever a new label arrives and all slots are full, so slot weights are systematically reduced and the maximum-slot label can differ from the true max-weight label. The paper's only evidence that this error is negligible is Figure 5, an in-sample comparison on the same 13 graphs used for all final measurements, and even there the quality loss relative to GVE-LPA/ν-LPA is 4.7%/2.9% on average, with road and protein k-mer graphs losing substantially more (the paper itself notes lower-quality communities on those types). Because the error rate of the sketch approximation depends on the label distribution (number of distinct neighbor labels, weight concentration, degree), the average 'minimal' loss cannot be assumed to transfer to other graph families. This is load-bearing because the abstract's headline trade-off (98x/44x memory savings for only ~3-5% quality loss) would not hold for graphs where the single-scan rule chooses a suboptimal label.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two GPU-based label propagation algorithms, νMG8-LPA and νBM-LPA, that replace per-vertex/per-thread hash tables with fixed-size weighted Misra-Gries and Boyer-Moore sketches, thereby reducing the algorithm's working memory from O(|E|) to O(|V|) excluding the input graph. The main claimed results are that νMG8-LPA uses 98x and 44x less memory than GVE-LPA and ν-LPA, is 2.4x faster than GVE-LPA and only 1.1x slower than ν-LPA, with modularity drops of 4.7% and 2.9% relative to those two baselines. The evaluation is carried out on 13 SuiteSparse graphs, and the paper also reports results for νBM-LPA, which is faster but has substantially lower community quality.","tokens_in":30872,"tokens_out":6473,"duration_ms":56034,"significance":"If the memory claims hold, the work is significant: reducing the auxiliary memory of GPU LPA from O(|E|) to O(|V|) is a structural improvement that can make billion-edge graphs processable on a single GPU. The design is plausible and the paper gives credit for using mergeable MG summaries, warp-level primitives, and a publicly available implementation. However, the empirical speed and quality claims are currently in-sample estimates because all hyperparameters are tuned on the same 13 graphs used for the reported benchmarks, and the single-scan shortcut that drives the quality trade-off is validated only by one in-sample experiment. The structural O(|V|) memory result is solid by design, but the headline numeric claims need stronger validation.","major_comments":[{"comment":"The decision to skip the second scan is justified only by the assertion that the most weighted candidate label c@ will 'likely align' with the label c# found by a second scan, and by the experiment summarized in Figure 5. The weighted MG sketch does not guarantee that the maximum-weight slot equals the true maximum-weight neighbor label: the decrement operation subtracts from all slot weights whenever a new label arrives with all slots full, so slot weights are systematically distorted, and labels with true weight below K_i/(k+1) may be absent entirely. Figure 5 reports only mean relative runtime and states that modularity is 'nearly identical' without showing per-graph modularity differences; Section 5.2 itself acknowledges that road networks and protein k-mer graphs yield lower-quality communities. Because the abstract's quality-loss numbers depend on this shortcut, the paper should report the per-graph and per-iteration disagreement rate between c@ and the label chosen by an exact scan over all neighbor labels, the per-graph modularity deltas underlying Figure 5, and results on a held-out or otherwise disjoint set of graphs. Without this, the 'minimal quality loss' claim is not established beyond the benchmark set used to tune the algorithm.","section":"Section 4.4"},{"comment":"All major hyperparameters are selected using the same 13 graphs on which the final results are reported: the sketch size k is chosen via Figure 2 in Section 4.1; the degree threshold D_H, thread-group count R_H, and kernel launch configurations are tuned by manual gradient descent in Section 4.2; and the Pick-Less period rho is tuned in Section 4.5. The speedups and quality deltas reported in Section 5 are therefore in-sample estimates, not out-of-sample assessments. This is load-bearing for the speed claims (2.4x faster than GVE-LPA, 1.1x slower than nu-LPA), though it does not affect the structural O(|V|) memory claim. The authors should either tune on a disjoint subset of graphs and evaluate on a held-out set, report sensitivity of runtime and modularity to each parameter, or explicitly frame all performance numbers as in-sample and discuss how much the tuning might overstate them.","section":"Sections 4.1, 4.2, 4.5"},{"comment":"Memory usage is measured with cudaMemGetInfo(), which reports global device memory, but the MG sketches are stored in shared memory as described in Section 4.1. The reported memory values for nuMG8-LPA and nuBM-LPA in Figure 7(d) are identical to three decimal places for every graph, which suggests the sketch storage is not included in the reported footprint. The paper should state explicitly whether the headline '98x/44x lower memory' claim refers only to global memory or to the total memory footprint, and should report peak shared-memory usage and occupancy. This matters because shared memory per SM is a finite resource that can limit graph size and kernel occupancy, so the memory-efficiency story is incomplete without those numbers.","section":"Section 5.2 / memory measurement"}],"minor_comments":[{"comment":"The first sentence of the abstract contains a grammatical error: 'dense connections within groups, than between them' should be 'dense connections within groups than between them.'","section":"Abstract and Section 1"},{"comment":"The text says the Boyer-Moore majority vote algorithm was developed in 1981, but reference [13] is the 1991 MJRTY paper; please correct or clarify the citation.","section":"Section 3.4"},{"comment":"There is a typo in 'a larger value of k is expected to improve community quality, as it increased the likelihood'; it should be 'it increases the likelihood.'","section":"Section 4.1"},{"comment":"The quality comparisons are reported as percentages (e.g., '4.7% lower'), but the paper does not state whether these are relative or absolute modularity differences; please define this clearly and consider reporting per-graph absolute modularity deltas.","section":"Section 5.2"},{"comment":"The text in Section 4.2 says that only the first thread group updates the changed-vertex count when multiple groups process a vertex, but the pseudocode as written increments the count for every group; please align the pseudocode and the prose.","section":"Algorithms 1 and 4"},{"comment":"The claim that fixed-size sketches residing in shared memory yield O(|V|) space complexity is stated without derivation; please add a sentence explaining that the number of simultaneously live sketches is bounded by the number of resident thread blocks rather than by |V|.","section":"Section 4.6"}],"recommendation":"major_revision","confidential_remarks":"The central structural memory result is plausible and worth publishing after revision, but the paper currently oversells the empirical speed/quality trade-off: the single-scan shortcut is the main correctness risk, and all parameters and the shortcut are validated on the same benchmark set used for the final numbers. If the authors can provide an exact-scan comparison, per-graph quality deltas, and preferably a held-out evaluation, the result would be much stronger. The paper reads like a technical report; the editor may also want to consider whether the level of validation is appropriate for the venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe headline is real: this paper shows an 8-slot Misra-Gries sketch can replace per-vertex hashtables in GPU label propagation, cutting working memory from O(|E|) to O(|V|) without a catastrophic slowdown. The authors demonstrate this on graphs up to 3.8 billion edges, and nuMG8-LPA runs on sk-2005 where their earlier nu-LPA runs out of memory. The 98x/44x memory reduction is structural, by design, and the measurements back it up.\n\nThe genuinely new pieces are the GPU-specific adaptations: warp-vote sketch updates, partial-sketch merging for high-degree vertices, and the single-scan label selection. These are real engineering contributions, not just a port of the author's prior multicore sketch work. The code is on GitHub, though without a commit hash.\n\nThe soft spots are in the speed/quality claims, not the memory claim. All key parameters—k=8, the degree threshold, thread block sizes, the Pick-Less period—are tuned by manual gradient descent on the same 13 graphs used for the final reported numbers. That is textbook in-sample tuning, and there are no error bars (five runs are averaged, but no variance is reported). So the \"2.4x faster than GVE-LPA, 1.1x slower than nu-LPA\" figures are point estimates with unknown variance. The single-scan shortcut in Section 4.4 is load-bearing: it assumes the maximum-weight sketch slot matches the true maximum-weight neighbor label often enough to skip a second scan. The evidence is one in-sample experiment, and the paper itself says road and protein k-mer graphs lose substantially more quality. So the abstract's \"minimal quality loss\" is an average across mostly web/social graphs, not a general property. This does not sink the paper, but the claim should be scoped. The other gap is the missing comparison to GLP, the existing GPU LPA framework they cite; without it, the speed comparison is incomplete.\n\nWho is this for? Anyone working on large-scale community detection on GPUs, and systems researchers generally. The core idea is sound, and Section 5.2 honestly admits the graph-type dependence. I'd send it to peer review. A serious referee should ask for out-of-sample validation or a tuning/test split, error bars, and a GLP comparison before the general quality claims are accepted. The memory result deserves to be published regardless.","headline":"Solid engineering result: replacing per-vertex hashtables with 8-slot MG sketches cuts GPU LPA working memory to O(|V|), demonstrated on 3.8B edges; the speed/quality numbers are in-sample and need scoping.","tokens_in":31410,"tokens_out":2789,"would_cite":true,"duration_ms":24565,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Replacing per-vertex hashtables with 8-slot sketches cuts GPU label-propagation memory by 44-98x with only a few points of modularity loss.","keywords":["community detection","label propagation","GPU","Misra-Gries sketch","Boyer-Moore","memory efficiency","large graphs","modularity"],"falsifier":"Run $\\nu$MG8-LPA on a graph whose communities have near-equal sizes and where many vertices have degrees below $k+1$, with and without the second scan; if the modularity gap between single-scan and double-scan exceeds the 4.7% figure reported on the 13 graphs, the single-scan claim does not hold beyond the tested set. A more direct test: instrument per-vertex disagreements between the sketch's max-slot label and the true argmax of neighbor weights; the fraction of disagreeing vertices is the quantity the single-scan claim implicitly assumes is negligible.","tokens_in":30287,"feed_emoji":"🧩","tokens_out":7206,"duration_ms":57097,"temperature":0.7,"pith_summary":"Label Propagation Algorithm (LPA) is a fast way to find communities in large graphs, but the best parallel LPA implementations pay for speed with memory: they keep per-thread or per-vertex hashtables whose total size grows with the number of edges. This paper argues that those hashtables can be replaced by fixed-size sketches—weighted Boyer-Moore (one candidate) and weighted Misra-Gries (eight candidates)—that summarize the most important neighboring community labels. The resulting GPU implementation, $\\nu$MG8-LPA, uses 98x less memory than the multicore GVE-LPA and 44x less than the GPU $\\nu$-LPA, is 2.4x faster than GVE-LPA and only 1.1x slower than $\\nu$-LPA, and loses 4.7%/2.9% modularity relative to those baselines. Because the working set is now proportional to the number of vertices rather than edges, graphs with billions of edges fit on a single GPU. The claim is attractive if one cares about processing large graphs on shared-memory systems where the input graph itself already consumes most of the available memory.","feed_headline":"8-slot sketch cuts GPU LPA memory by 44-98x","feed_subtitle":"The sketch makes memory scale with vertices, not edges, so a 3.8-billion-edge graph fits on one GPU.","key_machinery":"The load-bearing object is the weighted Misra-Gries (MG) sketch: a fixed-size summary of up to $k=8$ (candidate label, accumulated weight) pairs maintained in GPU shared memory. A neighbor's label-weight pair $(c,w)$ is accumulated by incrementing the matching slot if $c$ is present, otherwise inserting into a free slot, otherwise decrementing every slot's weight by $w$. This keeps the labels with total weight exceeding $K_i/(k+1)$ among the candidates, where $K_i$ is the vertex's weighted degree. The paper uses warp-level vote functions (group.ballot, group.all) to coordinate the eight threads that own the eight slots, uses partial per-group sketches for high-degree vertices and merges them via the mergeability of MG summaries, and skips the second scan by directly taking the maximum-weight slot as the new label. Together these choices reduce the per-iteration working set from $O(|E|)$ to $O(|V|)$ and keep the sketch updates in fast shared memory.","core_discovery":"The central discovery is that LPA's per-vertex vote over neighbor labels can be computed from a stream summary instead of an exact frequency map. The authors define a weighted Misra-Gries sketch with $k=8$ slots, where each slot holds a candidate community label and an accumulated edge weight; labels are inserted or evicted by decrementing all slot weights when the sketch is full. They implement this on a GPU with warp-level ballot primitives, assigning one thread per slot, giving each low-degree vertex its own thread group and splitting high-degree vertices across thread groups whose partial sketches are merged afterward (aided by the fact that Misra-Gries summaries are mergeable). They then show that a second scan over the neighbors to recompute exact weights of the top-$k$ candidates is unnecessary: picking the highest-weight slot directly gives nearly identical modularity. The result is a space complexity of $O(|V|)$ excluding the input graph, versus $O(|E|)$ for the per-vertex hashtables of $\\nu$-LPA, which is what lets a 3.8-billion-edge graph (sk-2005) run on a single A100 GPU that previously ran out of memory.","pith_inferences":["The same $O(|V|)$ sketch machinery should transfer to other per-vertex aggregation algorithms that currently allocate degree-proportional hashtables, such as connected-component labeling and graph partitioning by label diffusion; the memory saving would be identical.","Because the quality loss concentrates on road and k-mer graphs, a hybrid scheme that uses full exact counting for low-degree vertices (where the sketch's $k+1$ threshold rarely binds) and sketches only for high-degree vertices might recover most of the lost modularity at small memory cost.","With the input graph placed in unified memory, the practical ceiling for this algorithm on an A100-class GPU is set by graph storage rather than algorithm scratch space; the paper's own conclusion gestures at this but does not quantify it."],"forward_implications":["The 3.8-billion-edge sk-2005 graph runs on a single 80 GB A100 GPU under $\\nu$MG8-LPA, while $\\nu$-LPA runs out of memory.","Compared with GVE-LPA, $\\nu$MG8-LPA is 2.4x faster and uses 98x less memory; compared with $\\nu$-LPA it is 1.1x slower and uses 44x less memory.","Modularity loss is 4.7% versus GVE-LPA and 2.9% versus $\\nu$-LPA for $\\nu$MG8-LPA; the one-slot $\\nu$BM-LPA sells far more quality (20-27% lower) for its speed.","Algorithmic memory (excluding the input graph) scales as $O(|V|)$ rather than $O(|E|)$, so the per-iteration working set no longer grows with edge count."],"supporting_citations":[{"why":"The GPU LPA baseline whose per-vertex hashtables set the $O(|E|)$ memory cost that this paper eliminates.","marker":"[77]"},{"why":"The multicore LPA baseline providing the 98x memory comparison and the 2.4x speedup target.","marker":"[74]"},{"why":"The previous result showing 8-slot MG sketches work for LPA on multicore, motivating the GPU port.","marker":"[76]"},{"why":"The MG heavy-hitters algorithm whose weighted variant underlies the sketch.","marker":"[58]"},{"why":"The original LPA algorithm whose per-vertex argmax the sketch approximates.","marker":"[68]"},{"why":"NetworKit LPA, a third baseline for runtime and modularity comparisons.","marker":"[84]"},{"why":"Establishes that MG summaries are mergeable, justifying the partial-sketch merge strategy.","marker":"[2]"},{"why":"The SuiteSparse graph collection used in all experiments.","marker":"[45]"}],"fun_headline_variants":["8-slot MG sketch cuts GPU LPA memory up to 98x","Misra-Gries sketch: GPU LPA memory scales with vertices","O(V) memory for GPU LPA via 8-slot sketch","GPU LPA goes O(V) memory with Misra-Gries sketch"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The single-scan shortcut assumes that the label with the highest sketch weight is almost always the same as the label with the highest true connecting weight, a property tested only on the same 13 graphs used for the headline results; road and k-mer graphs show visibly larger quality drops, so the shortcut's reliability on other graph types is not established.","fun_headline_variants_meta":{"raw":{"variants":["8-slot MG sketch cuts GPU LPA memory up to 98x","Misra-Gries sketch: GPU LPA memory scales with vertices","O(V) memory for GPU LPA via 8-slot sketch","GPU LPA goes O(V) memory with Misra-Gries sketch"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000696,"raw_usage":{"total_tokens":3170,"prompt_tokens":992,"completion_tokens":2178,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":608,"completion_tokens_details":{"reasoning_tokens":2099}},"tokens_in":608,"tokens_out":2178,"duration_ms":13914,"temperature":1.0,"reasoning_tokens":2099,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:41:32.039400+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run $\\nu$MG8-LPA on a graph whose communities have near-equal sizes and where many vertices have degrees below $k+1$, with and without the second scan; if the modularity gap between single-scan and double-scan exceeds the 4.7% figure reported on the 13 graphs, the single-scan claim does not hold beyond the tested set. A more direct test: instrument per-vertex disagreements between the sketch's max-slot label and the true argmax of neighbor weights; the fraction of disagreeing vertices is the quantity the single-scan claim implicitly assumes is negligible.","supporting_citations":[{"cited_title":"GVE-LPA: Fast Label Propagation Algorithm (LPA) for Community Detection in Shared Memory Setting","cited_arxiv_id":"2312.08140","evidence_quote":"The multicore LPA baseline providing the 98x memory comparison and the 2.4x speedup target."},{"cited_title":"Memory-Efficient Community Detection on Large Graphs Using Weighted Sketches","cited_arxiv_id":"2411.02268","evidence_quote":"The previous result showing 8-slot MG sketches work for LPA on multicore, motivating the GPU port."},{"cited_title":"Staudt, A","cited_arxiv_id":null,"evidence_quote":"NetworKit LPA, a third baseline for runtime and modularity comparisons."}],"review_version":1}