{"id":"de4170f1-6b12-4e76-8e31-ae13c2282f44","arxiv_id":"2502.06879","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"CluStRE is a streaming graph clustering algorithm that combines one-pass node assignment, on-the-fly quotient graph construction, memetic refinement, and re-streaming local search to approach Louvain-quality modularity at low memory cost.","lead":"This paper introduces CluStRE, a streaming graph clustering algorithm that assigns nodes one at a time, then refines the result with an evolving quotient graph, evolutionary search, and repeated local-search passes. The authors report that it reaches about 96% of Louvain's clustering quality while using only a fraction of Louvain's memory.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2's on-the-fly quotient graph construction uses stale cluster assignments, so the described refinement step may optimize a graph that does not correspond to the current clustering.","rationale":"The reader's weakest assumption targets the fairness of the modified Hollocou baseline. That is a valid empirical concern, but it is not the most load-bearing issue. The paper's core contribution is the multi-stage refinement via a dynamic quotient graph. Algorithm 2, as stated, cannot maintain a correct quotient graph because it freezes the cluster of the larger endpoint at the time the smaller endpoint is processed. This is a concrete, internal technical flaw: it violates the precondition of Theorem 1 and invalidates the claimed mechanism by which CluStRE-Evo and CluStRE-Strong achieve near-in-memory quality. Even if the baseline were perfectly fair, the described algorithm would not support the headline claim. The fix is straightforward in principle (update GQ when cluster assignments change, or rebuild it after the first pass), but the paper must either provide that logic or the claims must be retracted. I therefore keep the reader's conditional verdict, but the required condition is different and more severe: correct and verify the quotient graph construction, not merely re-run the baseline. I disagree with the reader's identification of the single weakest assumption because the internal inconsistency of Algorithm 2 is a logical blocker upstream of any empirical comparison.","tokens_in":17505,"tokens_out":7541,"duration_ms":78286,"concrete_test":"Implement Algorithm 2 exactly as written on a tiny graph, e.g., a path 1-2-3 with node IDs as stream order, and compare the resulting GQ to the true quotient graph of the final clustering after the one-pass streaming. Verify whether the modularity of a clustering of GQ equals the modularity of the corresponding clustering of G (as Theorem 1 requires). A mismatch confirms the construction is broken. Additionally, if the authors' code is available, instrument updateQuotientGraph to log whether any existing GQ edge is modified when a node changes cluster; absence of such updates confirms the bug.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central quality claim of CluStRE-Evo and CluStRE-Strong depends on the quotient graph GQ preserving modularity under the memetic refinement (Theorem 1). However, Algorithm 2 (Section 3.3) constructs GQ while streaming nodes and only inserts edges: for each processed node v, it iterates neighbors u with v < u and adds an edge between C[v] and C[u] at that moment. If u has not yet been streamed, C[u] is still u's initial singleton cluster. When u is later assigned to a non-singleton cluster, no code path updates or removes the previously inserted edge. Consequently, GQ contains supernodes that are not clusters of the final clustering, misses self-loops for nodes that joined other clusters, and can be dramatically larger than the true quotient graph. The modularity equivalence proven in the appendix assumes GQ is built from the final clustering C, but the algorithm as specified does not guarantee this. The reported 96% of in-memory quality therefore cannot be attributed to the described algorithm; the published description is internally inconsistent and not reproducible as written. This concern is more fundamental than the baseline-fairness issue raised by the reader, because it affects the correctness of the method itself, not just the comparison.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes CluStRE, a node-streaming graph clustering algorithm that assigns nodes by modularity gain and optionally refines the clustering by (i) memetic clustering on a quotient graph constructed during streaming and (ii) re-streaming local search. Four configurations are compared against a modified version of Hollocou's streaming algorithm and against Louvain and VieClus on large graphs, with claims of 89.8% quality improvement over Hollocou, 2.6x speedup, lower memory consumption, and over 96% of the modularity of in-memory methods. A quotient-graph modularity equivalence theorem is stated in the appendix.","tokens_in":1489,"tokens_out":2979,"duration_ms":110853,"significance":"If the empirical claims hold, CluStRE would be a useful practical contribution: it demonstrates that streaming clustering can approach in-memory modularity while using a fraction of the memory, and the four-mode design gives a transparent speed/quality trade-off. The paper is also careful in reporting resource usage and in describing algorithmic components. However, the central experimental claims rest on two unresolved issues: the on-the-fly quotient graph construction as written does not satisfy the theorem used to justify it, and the Hollocou baseline is modified and tuned in ways that may inflate the reported improvements. The paper would be publishable after a major revision that fixes the algorithmic description, re-runs the comparison against a fair baseline, and reports variance.","major_comments":[{"comment":"Algorithm 2 constructs the quotient graph GQ while nodes are streamed, but it evaluates C[u] for each neighbor u at the moment the lower-ID endpoint v is processed. For every neighbor u that has not yet appeared in the stream, C[u] is still the initial singleton label; the algorithm never revisits or rewires these edges after u is later assigned to a non-singleton cluster. Consequently GQ contains supernodes that are not clusters of the final clustering, omits the self-loops that should represent internal edges of clusters formed by later-processed nodes, and in general is not the quotient graph of the final clustering C. The modularity equivalence in Appendix Theorem 1 is proved under the assumption that GQ is built from the final C, so the equivalence cannot be invoked for the graph actually built by Algorithm 2. The reported quality for CluStRE-Evo and CluStRE-Strong is therefore not attributable to the algorithm as written; the pseudocode needs an update rule that reroutes incident edges when a node joins a cluster (or a second construction pass after streaming).","section":"§3.3, Algorithm 2; Appendix Theorem 1"},{"comment":"The headline comparison to 'the state-of-the-art streaming clustering algorithm' is made against a modified Hollocou. The authors changed the edge order from the original randomized order to disk order, and selected vmax = 10,000 after testing multiple values because it gave the best quality. Since the paper itself states that Hollocou's quality is highly sensitive to edge-streaming order, this modification and parameter tuning can severely disadvantage the baseline; the reported 89.8% and 149.5% quality improvements and the 'best streaming method' conclusion are not supported without also reporting results for the original randomized order (or several orders) and for the parameter sensitivity of vmax.","section":"§4, Baselines paragraph"},{"comment":"The claim that CluStRE-Strong achieves 96.8% of Louvain and 96.5% of VieClus solution quality is averaged only over the instances on which the in-memory algorithms did not run out of memory (many rows in Table 1 are missing for these baselines). The abstract presents this as an unconditional statement. The paper should report the exact subset, per-instance quality ratios, and ideally also state what happens on the large instances where Louvain/VieClus fail; otherwise the 'over 96% of the quality of clustering approaches' claim is misleading.","section":"§4.2, Table 1"},{"comment":"All experiments appear to be single runs per instance, with no repeated trials, error bars, or variance reporting. This is problematic for the quantitative claims because Hollocou is order-sensitive, VieClus and CluStRE's memetic phase are stochastic, and the local-search time limit introduces run-to-run variation. The paper should report at least the range or standard deviation over several runs for the central quality, runtime, and memory comparisons.","section":"§4, Methodology"}],"minor_comments":[{"comment":"The key-handling in lines 9-12 of Algorithm 2 is ambiguous: if Q is meant to store undirected edges, the condition should be based on a canonical sorted pair; as written, when (Cj,Ci) exists but (Ci,Cj) does not, the code inserts a second entry and can double-count edge weights. Please clarify the canonical key representation.","section":"§3.3, Algorithm 2"},{"comment":"The statement that code will be publicly available 'on acceptance' makes it impossible to verify the implementation against Algorithm 2; providing the artifact (or at least a detailed correction of the pseudocode) would strengthen reproducibility.","section":"§4, Experimental Setup and Reproducibility"},{"comment":"The modularity performance profile in Figure 3(c) has a decreasing x-axis; the caption explains that higher modularity is better, but the axis direction should be labeled explicitly to avoid confusion.","section":"Figure 3 caption"}],"recommendation":"major_revision","confidential_remarks":"The Algorithm 2 issue is the most serious: as written, the method does not build the quotient graph of the final clustering, so the theorem that justifies the memetic refinement does not apply. This is fixable in a revision, but the authors must correct the pseudocode, confirm that the implementation matches the corrected description, and re-run the affected experiments. The baseline-fairness issue with Hollocou also needs to be addressed before the 'state-of-the-art streaming' claim can be accepted. I would not reject the paper outright, because the underlying idea is plausible and the modularity equivalence is standard if the quotient graph is built correctly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth reading. The combination of node-streaming assignment, on-the-fly quotient graph construction, memetic refinement with VieClus, and re-streaming local search is a sensible and genuinely new algorithmic recipe. The appendix theorem on modularity equivalence is correct for a quotient graph built from a fixed clustering, and the experimental coverage is broad, including billion-edge graphs. If the reported numbers hold, the memory savings are real and useful.\n\nBut there is a load-bearing problem in the description. Algorithm 2 builds GQ while streaming: for node v, it looks at neighbors u with v < u and adds an edge between C[v] and C[u] at that moment. If u has not been streamed yet, C[u] is still the singleton cluster. When u is later assigned to a non-singleton cluster, nothing updates or removes the previously inserted edge. So the graph handed to the memetic refinement is not the quotient graph of the final clustering, and Theorem 1 does not apply. The paper's claim that CluStRE-Evo and CluStRE-Strong achieve over 96% of in-memory quality is therefore not actually justified by the described algorithm. This is not a minor implementation detail; it is an internal inconsistency between the method and the proof meant to support it.\n\nThe baseline comparison is also softer than the abstract suggests. Hollocou was modified to stream edges from disk in input order, and vmax was tuned to 10,000 after testing. No repeated runs or error bars are reported, and the code is not yet public. Those issues are secondary to the GQ flaw, but they mean the specific 89.8% and 149.5% improvements should be treated as provisional.\n\nMy recommendation: send this to peer review, but expect major revision. The core idea is promising and the GQ construction flaw is identifiable and likely fixable (for example, by building GQ in a second pass or by tracking and updating edges when a node's cluster changes). The authors should also release code, compare against the unmodified Hollocou or justify the modification, and report variance across runs. As written, the paper's central quality claims do not follow from the stated algorithm.","headline":"A promising streaming clustering pipeline whose quotient-graph construction, as described, does not match the theorem used to justify it.","tokens_in":18284,"tokens_out":3001,"would_cite":false,"duration_ms":31392,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A streaming graph clustering algorithm, CluStRE, claims to close the quality gap with in-memory methods by refining an initial node-stream clustering through evolutionary optimization on a quotient graph and re-streaming local search.","keywords":["graph clustering","community detection","streaming algorithm","modularity","quotient graph","memetic algorithm","re-streaming","local search"],"falsifier":"Run the original Hollocou implementation, which randomizes edge order in memory, on the same benchmark set and compare modularity and memory against CluStRE; if the quality gap falls well below the reported 89.8% improvement or the memory advantage reverses, the central bridging claim is refuted.","tokens_in":17289,"feed_emoji":"🕸️","tokens_out":8025,"duration_ms":64257,"temperature":0.7,"pith_summary":"CluStRE is a streaming graph clustering algorithm that tries to close the quality gap between streaming methods and in-memory methods like Louvain and VieClus. Its central proposal is to process the graph as a node stream, computing the locally best modularity gain for each node, then refine the result using two cheap global-information stages: evolutionary clustering on a dynamically built quotient graph, and re-streaming with local search. The paper reports that the strongest configuration reaches over 96% of Louvain's and VieClus's modularity on the tested graphs, while using less than a fifth of their memory, and that even the lightest configuration beats the streaming baseline Hollocou by about 90% modularity while running 2.6 times faster and using about 59% of its memory. If these numbers hold, the paper establishes that the streaming/in-memory quality trade-off is not as fundamental as often assumed.","feed_headline":"Streaming clustering reaches 96% of in-memory quality","feed_subtitle":"Beats the streaming state of the art in quality, speed, and memory while nearly matching Louvain.","key_machinery":"The load-bearing object is the quotient graph $G_Q$ built on the fly during streaming: each cluster becomes a weighted supernode, inter-cluster edges are aggregated into weighted edges, and intra-cluster edges become doubled self-loops. The paper proves (Theorem 1 in the appendix) that modularity of any clustering of $G_Q$ equals modularity of the corresponding clustering of the original graph, so refining the small quotient graph refines the original clustering. Two complementary refinement mechanisms exploit this: memetic (evolutionary) clustering, which recombines and mutates a population of quotient-graph clusterings, and re-streaming local search, which re-scans only the neighborhoods of nodes that changed cluster in the previous pass to accumulate modularity gain. The delta-modularity formula (Equation 3) drives every assignment decision.","core_discovery":"The paper proposes that the conventional quality ceiling of streaming graph clustering is an artifact of the one-pass constraint, not of streamed data itself. Its method, CluStRE, reads nodes one at a time and assigns each to the cluster that maximizes local modularity gain; then, in optional stages, it uses the current clustering to build a quotient graph on the fly and runs a memetic (evolutionary) clustering algorithm on that quotient graph, followed by re-streaming local search that revisits only the neighborhoods of changed nodes. The paper proves that modularity is exactly preserved under the quotient-graph contraction, so improvements found on the small graph are genuine improvements to the original. The reported outcome is that the strongest configuration reaches 96.8% of Louvain's and 96.5% of VieClus's modularity on average, while using 18.3% of Louvain's and 10.8% of VieClus's memory; the lightest configuration surpasses the Hollocou streaming baseline by 89.8% modularity, is 2.6 times faster, and uses 58.8% of its memory.","pith_inferences":["A natural stress test is to replace the VieClus-based memetic optimizer on the quotient graph with a different modularity optimizer (e.g., Leiden) and re-measure the 96% figure; the quotient-graph invariance proof suggests the quality bridge is a property of the pipeline, not of one optimizer.","Because the paper's streaming baseline is a modified version of Hollocou that reads edges in input order, an editorially conservative check is to rerun the comparison with the original randomized-order implementation and with a second streaming algorithm; the 89.8% and 149.5% headline gaps are the most likely numbers to shift.","The memory measurements on uk-2007-05 (2.18 GB peak for the strongest mode) suggest that trillion-edge graphs become clusterable on commodity hardware; a direct follow-up is to scale the configuration curve to larger synthetic RGG and RHG instances and report the memory/quality crossover point."],"forward_implications":["CluStRE-Strong can replace in-memory clustering on graphs too large for memory, losing only 3–4% modularity on average against Louvain and VieClus.","CluStRE-Light gives a strictly better streaming option than Hollocou: higher modularity, lower runtime, lower memory on the tested instances.","The quotient-graph modularity equivalence makes any modularity-based in-memory optimizer applicable to a streamed graph through CluStRE's on-the-fly contraction.","The active-node re-streaming scheme bounds I/O growth: only neighborhoods of reassigned nodes are re-read, so multiple refinement passes remain cheap.","Ground-truth community recovery, measured by NMI, also improves by about 17% over Hollocou, so the quality gain is not an artifact of the modularity objective alone."],"supporting_citations":[{"why":"The streaming baseline CluStRE must beat; supplies the one-pass edge-streaming algorithm with vmax parameter.","marker":"[27]"},{"why":"Supplies the memetic clustering algorithm (VieClus) that CluStRE runs on the quotient graph for evolutionary refinement.","marker":"[7]"},{"why":"The Louvain in-memory algorithm whose modularity quality CluStRE is compared against for the 96.8% claim.","marker":"[8]"},{"why":"Re-streaming graph partitioning heuristic that motivates CluStRE's re-streaming local search stage.","marker":"[45]"},{"why":"Provides the performance profile methodology used to present the runtime/quality/memory comparisons.","marker":"[19]"},{"why":"Defines the modularity objective that the method optimizes and that is proved invariant under quotient-graph contraction.","marker":"[44]"}],"fun_headline_variants":["Streaming clustering hits 96% of Louvain quality","CluStRE: Stream graphs, rival Louvain quality","Multi-stage refinement lifts streaming clustering to 96% of Louvain","CluStRE: 96% Louvain quality, 82% less memory"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central numbers depend on the baseline streaming algorithm being fairly represented by the authors' modification that streams edges from disk in input order with the parameter set to 10,000; if that baseline or another streaming method were compared differently, the reported quality advantages could change.","fun_headline_variants_meta":{"raw":{"variants":["Streaming clustering hits 96% of Louvain quality","CluStRE: Stream graphs, rival Louvain quality","Multi-stage refinement lifts streaming clustering to 96% of Louvain","CluStRE: 96% Louvain quality, 82% less memory"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001262,"raw_usage":{"total_tokens":5179,"prompt_tokens":967,"completion_tokens":4212,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":583,"completion_tokens_details":{"reasoning_tokens":4132}},"tokens_in":583,"tokens_out":4212,"duration_ms":32708,"temperature":1.0,"reasoning_tokens":4132,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T18:45:02.649965+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the original Hollocou implementation, which randomizes edge order in memory, on the same benchmark set and compare modularity and memory against CluStRE; if the quality gap falls well below the reported 89.8% improvement or the memory advantage reverses, the central bridging claim is refuted.","supporting_citations":[{"cited_title":"A Streaming Algorithm for Graph Clustering","cited_arxiv_id":"1712.04337","evidence_quote":"The streaming baseline CluStRE must beat; supplies the one-pass edge-streaming algorithm with vmax parameter."},{"cited_title":"Biedermann, M","cited_arxiv_id":null,"evidence_quote":"Supplies the memetic clustering algorithm (VieClus) that CluStRE runs on the quotient graph for evolutionary refinement."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Louvain in-memory algorithm whose modularity quality CluStRE is compared against for the 96.8% claim."},{"cited_title":"Nishimura and J","cited_arxiv_id":null,"evidence_quote":"Re-streaming graph partitioning heuristic that motivates CluStRE's re-streaming local search stage."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the performance profile methodology used to present the runtime/quality/memory comparisons."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the modularity objective that the method optimizes and that is proved invariant under quotient-graph contraction."}],"review_version":1}