{"id":"b64a6e1b-0786-4055-987f-e656e4779eeb","arxiv_id":"2411.11468","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A GPU label propagation algorithm reaches 3B edges per second and claims large speedups over existing CPU and GPU community detection tools while producing slightly lower modularity.","lead":"This paper presents a GPU implementation of label propagation for finding communities in networks, reaching billions of edges per second on an NVIDIA A100. It is useful for anyone who needs to cluster very large graphs quickly, at the cost of modestly lower community quality than slower methods.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Per-vertex hashtable capacity nextPow2(degree)-1 is smaller than the degree for power-of-two degrees (e.g., degree 2 gives capacity 1), so Algorithm 1 silently drops neighbor labels and the reported modularity may characterize a truncated LPA.","rationale":"The reader's weakest assumption identifies exactly this hashtable capacity issue: for a power-of-two degree D, the table capacity nextPow2(D)-1 is D-1, so if all neighbor labels are distinct the last insertion has no empty slot and Algorithm 2's FAILED return is ignored. I agree this is the most load-bearing concern because it directly undermines the correctness of the label aggregation on which the modularity claims rest. The concern is not merely theoretical: degree 2 is extremely common in the benchmark set, and since all labels are initially unique, the first iteration will drop at least one neighbor for every degree-2 vertex. This means the implemented algorithm deviates from the stated LPA update rule for a large fraction of vertices, so the reported speedups and modularity numbers may not be reproducible from the paper's description. The reader's conditional verdict is appropriate: the paper should not be rejected outright because the implementation may deviate from the pseudocode or the results may be salvageable with a simple capacity fix, but the central claim cannot be accepted until the authors show that the dropped keys do not change the reported outcomes. I therefore keep the verdict unchanged from the reader's CONDITIONAL assessment.","tokens_in":18392,"tokens_out":6138,"duration_ms":62614,"concrete_test":"Instrument hashtableAccumulate to increment a global counter whenever it returns FAILED, or count vertices with power-of-two degree in each benchmark graph and verify that the first iteration attempts to insert more distinct labels than the table capacity. Then rerun lpa() with the corrected capacity p1 = nextPow2(2*degree(i))-1 (or p1 = nextPow2(degree(i)+1)-1) on com-Orkut, it-2004, and europe_osm, and compare modularity and runtime to Figure 6. If modularity changes by more than a small epsilon, the reported community quality depends on the dropped keys and the central claim is not supported as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's per-vertex hashtable capacity is set to p1 = nextPow2(degree(i))-1 in Algorithm 1 line 19. For any vertex whose degree is a power of two, p1 = degree - 1, so the table has fewer slots than there are neighbors. In particular, degree 2 yields p1 = 1, allowing only one of the two neighbor labels to be stored. Algorithm 2 returns FAILED after exhausting MAX_RETRIES (line 18), but Algorithm 1 line 28 ignores that return value. In the first LPA iteration every vertex has a unique label, so every degree-2 vertex attempts to insert two distinct keys into a one-slot table and silently drops one. This is not a rare corner case: in road networks (asia_osm, europe_osm) and many web/social graphs, a large fraction of vertices have degree 2. Consequently the label selected in lpaMove is not the argmax over all neighbor labels required by Equation 3, and the reported modularity and speed numbers characterize a truncated version of LPA rather than the algorithm claimed. Section 4.2 states that the hashtable 'must be at least as large as the degree' and that the allocation keeps the load factor below 100%, which directly contradicts the nextPow2(degree)-1 formula used in the pseudocode.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This report describes ν-LPA, a CUDA implementation of asynchronous label propagation for community detection. The main technical contributions are a per-vertex open-addressing hash table stored in global memory with a hybrid quadratic-double probing collision strategy, a Pick-Less symmetry-breaking rule applied every four iterations, and a two-kernel decomposition that processes low-degree vertices with one thread per vertex and high-degree vertices with one block per vertex. The authors benchmark ν-LPA on 13 SuiteSparse graphs and report large speedups over FLPA, NetworKit LPA, Gunrock LPA, and cuGraph Louvain on an A100 GPU, together with modularity values that are higher than FLPA but lower than NetworKit LPA and cuGraph Louvain.","tokens_in":18672,"tokens_out":9104,"duration_ms":93784,"significance":"If the algorithm and measurements are taken at face value, the paper would be a useful engineering contribution: it gives a concrete GPU LPA design with public code, benchmark results on very large graphs, and a plausible mechanism for convergence problems on SIMT hardware. The per-vertex hash table idea is relevant, and the comparison against several baselines is informative. However, the two algorithmic defects identified below directly affect which labels are computed and therefore the reported modularity and speed numbers; until those defects are resolved, the empirical claims are not supported. The paper's strengths are its clear pseudocode, the public repository link, and the breadth of the experimental dataset.","major_comments":[{"comment":"Algorithm 1 sets p1 = nextPow2(degree(i))-1 and sizes the hash table as H_k[theta_H : theta_H+p1]. For any vertex whose degree is a power of two, p1 = degree-1, so the table has one fewer slot than the number of neighbors. In the first LPA iteration all labels are distinct, so, for example, a degree-2 vertex must insert two distinct keys into a one-slot table. Algorithm 2's probing loop cannot find alternative slots (with p1=1 every slot index is 0), and it returns FAILED after MAX_RETRIES, but Algorithm 1 line 28 ignores this return value. The same issue gives p1=0 for degree-1 vertices, which implies a modulo-by-zero in Algorithm 2 line 4. This directly contradicts the statement in Section 4.2 that the table size 'must be at least as large as the degree' and that the allocation keeps the load factor below 100%. Since degree-2 vertices are abundant in the road and k-mer graphs (average degree 2.1), the reported modularity and throughput numbers may characterize a truncated LPA rather than the algorithm of Eq. (3). The authors should correct the capacity formula or explain how insertion failures are handled and show that they do not affect the reported results.","section":"Section 4.2, Algorithm 1 line 19, Algorithm 2 lines 3-18"},{"comment":"In the non-shared branch, when the slot already contains the key, the code executes H_v[s] <- v, which overwrites the previously accumulated weight instead of adding the new value. The shared branch uses atomicAdd, so the two kernels implement different semantics. In the thread-per-vertex kernel (degree < SWITCH_DEGREE = 32), any vertex with two or more neighbors in the same community will have its aggregated label weight replaced by the last edge weight rather than summed, so the argmax required by Eq. (3) is not computed. This is a load-bearing error for all low-degree vertices, and it may explain part of the modularity gap relative to NetworKit LPA. The pseudocode should use H_v[s] <- H_v[s] + v, and the experiments should be rerun if the implementation mirrors the current text.","section":"Algorithm 2 lines 5-9"},{"comment":"The design parameters (rho = 4, SWITCH_DEGREE = 32, quadratic-double probing) are selected using the same 13 graphs on which the headline results are reported. Figures 1, 3, and 4 show relative runtime or modularity averaged over these graphs, so the final speedups are post-selection values rather than independent predictions. In addition, the speedup averages are computed over different subsets for different baselines because Gunrock LPA and cuGraph Louvain fail on several graphs, but the paper does not state which graphs are included in each average. The authors should either validate the selected parameters on a separate set of graphs or report per-graph results for all configurations, and should state the subset used for every reported average.","section":"Section 5.2, Figures 1, 3, 4"},{"comment":"For Gunrock LPA, the authors state that they 'measure the only iteration time using cpu_timer', whereas for the other baselines they measure total end-to-end runtime. Comparing an iteration-only time against full end-to-end time is not an apples-to-apples comparison and can materially affect the reported 2.6x speedup over Gunrock LPA. Please report Gunrock's end-to-end runtime including preprocessing and graph loading, or clearly state that the speedup is for the compute phase only and provide corresponding phase-level timings for ν-LPA.","section":"Section 5.2, Gunrock timing"}],"minor_comments":[{"comment":"The word 'Quadriatic' is misspelled in Section 4.2 and in Figure 3; it should be 'Quadratic'.","section":"Section 4.2, Figure 3"},{"comment":"The quantities p1 and p2 are repeatedly described as primes, but p1 = nextPow2(degree)-1 and p2 = nextPow2(p1)-1 are not prime in general (for example, degree 16 gives p1 = 15). The text should call them hash moduli rather than primes, or the formulas should be changed to actually produce primes.","section":"Algorithm 2, Section 4.2"},{"comment":"Table 1 has several presentation issues: 'LA W' should be 'LAW' or 'Web Graphs', 'obtained SuiteSparse' is missing 'from', and the graph categories are not consistently labeled.","section":"Table 1"},{"comment":"The value of MAX_RETRIES is never stated, and its relation to p1 is not discussed. Since the pseudocode relies on this bound to decide when to return FAILED, the default value should be given and justified.","section":"Algorithm 2"}],"recommendation":"major_revision","confidential_remarks":"The paper is written as a technical report, and the repository link is a useful artifact. Before any recommendation for acceptance is meaningful, the authors should be asked to confirm whether their implementation matches the pseudocode: the capacity formula and the non-shared accumulation issue are both easily fixable in the text, but if the code matches the current pseudocode, the reported modularity values would characterize a different algorithm. The tuning of rho, switch degree, and collision strategy on the same benchmark set is a further concern that should be addressed in revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: this paper is a genuine engineering contribution with surprisingly large speedups, but the pseudocode has two concrete bugs that make the exact numbers hard to trust as written. What is new: a GPU implementation of asynchronous LPA using per-vertex open-addressing hashtables in global memory, hybrid quadratic-double probing, a Pick-Less symmetry-breaking rule applied every 4 iterations, and a thread-per-vertex / block-per-vertex kernel split. The reported speedups (364x over FLPA, 62x over NetworKit, 2.6x over Gunrock, 37x over cuGraph Louvain) and 3.0B edges/s on the it-2004 graph are impressive if reproducible. Modularity is about 5% above FLPA and 6-10% below Louvain, which is the expected trade-off for LPA. The paper also fills a real gap: there are few publicly available GPU LPA implementations. The soft spots are concrete. First, the stress-test concern holds up: Algorithm 1 sizes the per-vertex hashtable as nextPow2(degree)-1. For any power-of-two degree, that capacity is one less than the number of neighbors; for degree 2 it is 1 slot. The text says the table 'must be at least as large as the degree' and that the load factor stays below 100%, which is directly contradicted by the formula. Since the road network and k-mer graphs in the test set have average degree about 2.1, a large fraction of vertices are degree 2, and in the first iteration every neighbor label is distinct. Algorithm 1 ignores the FAILED return from hashtableAccumulate, so labels get silently dropped and the reported modularity may be for a truncated LPA. Second, Algorithm 2's non-shared path sets H_v[s] <- v instead of adding v, which would not accumulate weights for repeated labels; that looks like a simple pseudocode error, but it needs fixing. Less severe: the pick-less period, switch degree, and probing strategy are all tuned on the same 13 graphs used for the headline numbers, and no error bars or variance are reported. That is common in systems papers, but it means the speedups are probably optimistic. The underlying claim—that a GPU LPA can be made dramatically faster with acceptable modularity—is plausible and not falsified by anything here. The bugs are correctable; if the actual code on GitHub sizes the tables correctly and accumulates properly, the results likely stand. This deserves a serious referee, but the author should be asked to fix the pseudocode, confirm the implementation does not drop keys, and report variance.","headline":"Solid GPU LPA engineering with impressive speedups, but two concrete hashtable bugs in the pseudocode—undersized capacity for power-of-two degrees and a non-accumulating update—undermine the exact numbers until fixed.","tokens_in":19187,"tokens_out":4430,"would_cite":false,"duration_ms":41965,"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":"This paper claims that two GPU-specific changes — a Pick-Less rule every fourth iteration and a per-vertex hashtable with hybrid quadratic-double probing — let label propagation detect communities at 3.0 billion edges per second on an…","keywords":["community detection","label propagation algorithm","GPU computing","CUDA","open addressing","per-vertex hashtable","quadratic-double probing","modularity"],"falsifier":"Run nu-LPA on a graph whose vertices all have power-of-two degrees, such as a collection of disjoint 4-, 8-, and 16-vertex cliques with distinct initial labels, and compare the resulting communities against the same algorithm run with tables of capacity nextPow2(D) instead of nextPow2(D)-1; if the two outputs differ or the small-capacity version yields lower modularity, the silent-drop premise is violated.","tokens_in":18154,"feed_emoji":"⚡","tokens_out":5651,"duration_ms":47390,"temperature":0.7,"pith_summary":"Label propagation is one of the fastest heuristics for finding communities in large networks, but its natural parallel form on GPUs can fail to converge because symmetric vertices keep swapping labels. This paper claims that two changes make it converge and run fast on SIMT hardware: a Pick-Less rule applied every fourth iteration, which only allows a vertex to move to a smaller community ID, and a per-vertex open-addressing hashtable that resolves collisions with a hybrid of quadratic probing and double hashing. On an NVIDIA A100, the resulting implementation, called nu-LPA, processes up to 3.0 billion edges per second on a 2.2 billion edge graph and reports average speedups of 364x over FLPA, 62x over NetworKit LPA, 2.6x over Gunrock LPA, and 37x over cuGraph Louvain. The detected communities have 4.7% higher modularity than FLPA but 6.1% and 9.6% lower modularity than NetworKit LPA and cuGraph Louvain, so the paper's case is that LPA can be made dramatically faster on GPUs at a modest quality cost.","feed_headline":"GPU label propagation processes 3 billion edges per second","feed_subtitle":"A Pick-Less rule plus a per-vertex hashtable make LPA converge on GPUs at 3B edges per second.","key_machinery":"The load-bearing object is the per-vertex open-addressing hashtable with quadratic-double probing. Each vertex i gets a hashtable of capacity p1 = nextPow2(degree)-1 storing neighbor labels as keys and accumulated edge weights as values; memory is allocated in two flat arrays of size 2|E|, with vertex i's table at offset 2*CSR_offset(i). On a collision, the probe step is the sum of a quadratic component (doubling the delta) and a double-hash component using a secondary prime p2 = nextPow2(p1)-1, which the paper argues balances clustering against cache efficiency. A second mechanism, Pick-Less every 4 iterations, is what prevents community swaps; the paper's experiments choose it over cross-checking and hybrid variants on the basis of relative runtime and modularity, using 32-bit floats for hashtable values and a degree-32 switch between thread-per-vertex and block-per-vertex kernels.","core_discovery":"The central claim is that asynchronous label propagation can be made to converge reliably on GPU hardware, and to do so at multi-billion-edge-per-second rates, without a quality collapse. The convergence fix is the Pick-Less (PL) method: every four iterations, a vertex may change its label only to a community ID strictly smaller than its current one, breaking the symmetric label-swap cycles that otherwise keep the algorithm running for all 20 allowed iterations. The speed fix is a global-memory per-vertex hashtable, sized at twice each vertex's degree and given capacity nextPow2(degree)-1, using hybrid quadratic-double probing, plus a thread-per-vertex kernel for low-degree vertices and a block-per-vertex kernel for high-degree ones, and 32-bit floats for accumulated label weights. The paper reports the resulting nu-LPA outperforming FLPA, NetworKit LPA, Gunrock LPA, and cuGraph Louvain by 364x, 62x, 2.6x, and 37x on an A100, processing 3.0B edges/s on the it-2004 graph, while producing 4.7% higher modularity than FLPA but 6.1% and 9.6% lower than NetworKit LPA and cuGraph Louvain.","pith_inferences":["The capacity choice nextPow2(D)-1 makes the modulo hash cheap, but it leaves no empty slot for the last insertion when D is a power of two and all neighbor labels are distinct; a simple fix would be capacity nextPow2(D) with masking, or checking the return status of hashtableAccumulate.","The speedups are measured against CPU baselines for FLPA and NetworKit LPA, so those gaps blend hardware and algorithm differences; the GPU-vs-GPU comparisons (2.6x vs Gunrock LPA, 37x vs cuGraph Louvain) are the cleaner speed claims.","Because PL4 restricts label movement to lower IDs every fourth iteration, it biases communities toward earlier (smaller-ID) labels; this may explain part of the modularity gap versus NetworKit LPA and suggests testing with randomized initial label orderings to separate bias from quality."],"forward_implications":["A single A100 can detect communities on a 2.2-billion-edge graph in about 1.6 seconds, making LPA practical for interactive or repeated partitioning of very large graphs.","For applications that can tolerate 6-10% lower modularity, nu-LPA offers a 37x speed advantage over cuGraph Louvain on the tested graphs; for applications that need maximum modularity, Louvain remains the better choice.","The per-vertex hashtable design bounds total hashtable memory by O(|E|), so the method scales to graphs whose degree distribution is skewed as long as the edge list fits in GPU memory.","The same PL4 symmetry-breaking recipe can be dropped into other asynchronous label-diffusion algorithms on SIMT hardware, not just LPA."],"supporting_citations":[{"why":"Defines the original Label Propagation Algorithm that this work parallelizes and optimizes for GPUs.","marker":"[40]"},{"why":"FLPA is the sequential queue-based baseline that nu-LPA is compared against and reported to beat by 364x.","marker":"[57]"},{"why":"NetworKit's parallel LPA is the multicore baseline that nu-LPA is compared against and reported to beat by 62x.","marker":"[54]"},{"why":"Gunrock's GPU LPA is the GPU baseline that nu-LPA is compared against and reported to beat by 2.6x.","marker":"[62]"},{"why":"cuGraph Louvain is the GPU Louvain baseline used to highlight the speed-quality trade-off, with nu-LPA 37x faster but 9.6% lower modularity.","marker":"[25]"},{"why":"GVE-LPA is the multicore predecessor whose asynchronous LPA design and pruning strategy nu-LPA adapts to GPU memory constraints.","marker":"[45]"},{"why":"SuiteSparse Matrix Collection provides all 13 benchmark graphs used for runtime and modularity measurements.","marker":"[28]"}],"fun_headline_variants":["GPU label propagation hits 3 billion edges per second","Pick-Less rule makes GPU label propagation convergent at 3B edges/s","3B edges/s GPU label propagation with stable convergence","GPU LPA beats CPU by 364x, hits 3B edges/s","Per-vertex hashtable enables 3B-edge/s GPU label propagation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The collapse point is in Section 4.2 and Algorithm 1: each vertex's hashtable is sized nextPow2(degree)-1, and when degree is a power of two this capacity is one less than the number of neighbors, so a table holding all distinct labels has no empty slot for the last insertion; Algorithm 1 ignores the failed status returned by hashtableAccumulate, and all reported speed and modularity numbers assume this never changes a label.","fun_headline_variants_meta":{"raw":{"variants":["GPU label propagation hits 3 billion edges per second","Pick-Less rule makes GPU label propagation convergent at 3B edges/s","3B edges/s GPU label propagation with stable convergence","GPU LPA beats CPU by 364x, hits 3B edges/s","Per-vertex hashtable enables 3B-edge/s GPU label propagation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000783,"raw_usage":{"total_tokens":3507,"prompt_tokens":1047,"completion_tokens":2460,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":663,"completion_tokens_details":{"reasoning_tokens":2383}},"tokens_in":663,"tokens_out":2460,"duration_ms":31610,"temperature":1.0,"reasoning_tokens":2383,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:29:50.527490+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run nu-LPA on a graph whose vertices all have power-of-two degrees, such as a collection of disjoint 4-, 8-, and 16-vertex cliques with distinct initial labels, and compare the resulting communities against the same algorithm run with tables of capacity nextPow2(D) instead of nextPow2(D)-1; if the two outputs differ or the small-capacity version yields lower modularity, the silent-drop premise is violated.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gunrock's GPU LPA is the GPU baseline that nu-LPA is compared against and reported to beat by 2.6x."},{"cited_title":"Kolodziej, M","cited_arxiv_id":null,"evidence_quote":"SuiteSparse Matrix Collection provides all 13 benchmark graphs used for runtime and modularity measurements."}],"review_version":1}