{"id":"adda2212-457a-433e-9646-fd3717509fc1","arxiv_id":"2412.13592","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"PASCO coarsens a graph into several small copies, clusters them in parallel, and fuses the partitions with optimal transport to speed up clustering while keeping quality.","lead":"This paper introduces PASCO, a three-step method that makes graph clustering faster by shrinking the graph several times, clustering each small copy in parallel, then merging the results. It is useful for very large networks where methods like spectral clustering are too slow.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Coarsening's 'structure-preserving' premise is only a conjecture; Algorithm 2's already-visited-neighbor relaxation permits rich-get-richer hypernode collapse, and no hypernode size/purity analysis is reported, so quality preservation may not generalize beyond the tested graphs.","rationale":"The strongest claim is an empirical one, and the paper's experiments plus available code are genuine evidence supporting it. I therefore do not raise a general correctness objection. The load-bearing vulnerability is the mechanism that purports to explain why quality is preserved: the random coarsening of Section 3 is said to be structure-preserving, but this is explicitly left as a conjecture (Section 3.3), and the algorithm's design (u unvisited, v unrestricted) creates a concrete rich-get-richer failure mode. Because the overlay's quality guarantee—especially for SC/CSC where AMI improves—has no other theoretical support, and because the paper never reports hypernode size or purity statistics, the generality of the claim is the point at risk. The proposed test directly measures whether the failure mode occurs on the paper's own graphs. This matches the reader's weakest_assumption, so my recommendation is to keep the CONDITIONAL verdict (UNCHANGED), with the condition being this empirical check and repeated real-graph timings.","tokens_in":27725,"tokens_out":12890,"duration_ms":121321,"concrete_test":"Run the released PASCO coarsening (Algorithm 2) with rho=10 for 20 random seeds on the three OGB graphs and on SSBM graphs with alpha on both sides of 1/(k-1). For each run, extract the coarsening table and compute (1) the fraction of nodes in the largest hypernode and the Gini coefficient of hypernode sizes, and (2) the fraction of hypernodes whose member nodes belong to more than one ground-truth community (impure hypernodes) and the AMI between the hypernode partition and the ground-truth communities. If the largest hypernode contains >10% of all nodes, or >10% of hypernodes are impure, on any tested graph, the rich-get-richer collapse is real and the unproven 'structure-preserving' premise of Section 3.3 is violated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"PASCO's quality-preservation claim rests on the coarsening step's ability to preferentially contract intra-community edges (Section 3.3). In Algorithm 2, u is sampled uniformly from unvisited nodes but v may already have been visited, so a high-degree node can absorb many later u's into its existing hypernode. Because v is drawn uniformly among neighbors, degree hubs become attractors; if a hub connects multiple communities, the resulting hypernode can span community boundaries and collapse inter-community edges. The paper only conjectures the structural-preservation condition ('This remains a conjecture, not yet supported by rigorous proof', Section 3.3) and never reports the hypernode size or purity distribution for real graphs. Appendix B rejects alternative unbalanced sampling rules but defends Algorithm 2 only by an unreported simulation. If this rich-get-richer effect is strong on heterogeneous or disassortative graphs, the coarsened graph can lose the community signal before clustering and fusion, so the observed quality gains would not generalize. The concern is not merely a missing proof: the mechanism is concrete and the algorithm's relaxation is deliberate (to create larger hypernodes), making the failure mode plausible.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"PASCO is a three-stage overlay for accelerating graph clustering: it generates several small coarsened graphs with a randomized edge-contraction algorithm, applies any chosen clustering method to each coarsened graph in parallel, lifts the resulting partitions to the original node set, and combines them by an optimal-transport barycenter procedure with majority-vote fusion. The paper claims that this pipeline reduces runtime by large factors for spectral clustering, Compressive Spectral Clustering, and Infomap on real graphs, while maintaining or improving partition quality, and that the coarsening step is fast and preserves spectral structure. The mathematical framework includes a complexity bound for coarsening, optimal-transport-based alignment lemmas, and a conjectured phase-transition condition for structure preservation on symmetric stochastic block models.","tokens_in":27976,"tokens_out":6544,"duration_ms":64731,"significance":"If the reported speedups and quality preservation hold, PASCO would be a practically useful, modular overlay for large-scale graph clustering, especially when the number of communities is large. The paper's strengths include a clear algorithmic pipeline, a public code release, experiments on three large Open Graph Benchmark graphs, a spectrum-preservation comparison against heavy-edge and variation-edge coarsening, and a useful ablation of the fusion step. The mathematical lemmas for alignment and fusion appear internally consistent, and the complexity analysis of coarsening is explicit. The main weaknesses are empirical: the real-graph evidence is based on single runs, the timing comparison partially conflates algorithmic speedup with parallel resource use, and the structure-preservation guarantee is only conjectured with no analysis of the coarsening hypernode composition.","major_comments":[{"comment":"The structural-preservation claim is load-bearing but rests on an explicit conjecture. Algorithm 2 allows v to be an already-visited neighbor, so a high-degree node can absorb many later u's into one hypernode; if such a hub connects multiple communities, the contraction can merge inter-community edges and destroy the community signal. The paper labels the preservation condition as a conjecture and defends Algorithm 2 in Appendix B only by an unreported simulation. Moreover, Table E2 gives estimated alpha values for arxiv, mag, and products of 0.044, 0.031, and 0.028, which exceed the conjectured thresholds 1/(k-1) of 0.026, 0.0029, and 0.022, respectively, so the real graphs are not even in the regime covered by the conjecture. I am not requiring a full proof, but the manuscript should either prove a suitable relaxation of the conjecture or report hypernode size distributions and intra-community purity on the real graphs; without one of these, the claim that the coarsening step preserves structural properties beyond the tested graphs is not supported.","section":"Section 3.3, Algorithm 2"},{"comment":"The real-graph experiments report a single run per configuration. Because the coarsening step is randomized, both wall-clock times and quality metrics have run-to-run variance, and Figure 7's disks appear to represent individual runs rather than summary statistics. Claims such as 'PASCO improves AMI for SC and CSC' rest on differences like products SC AMI 0.202 versus SC+PASCO(t=10) AMI 0.332, which have no error bars and could be partly due to randomness. Please report means and quantiles over several repetitions, or at minimum state explicitly that the tables are single illustrative runs and soften the assertive improvement claims accordingly.","section":"Section 5.3, Tables E3-E5"},{"comment":"The headline speedups conflate algorithmic acceleration with the use of parallel resources. PASCO clusters R coarsened graphs in parallel, while the standalone baseline is run on a single core. The paragraph controls for intra-algorithm parallelism of the clustering methods, but it does not account for the number of cores or processes consumed by PASCO's own parallel execution. The factor-10 runtime reductions are therefore a comparison of a parallel pipeline against a serial baseline. To make the speedup claims meaningful, report the number of cores/processes used and total CPU time, or include a sequential-mode PASCO comparison as an additional baseline.","section":"Section 5.3, Measuring Computational time"}],"minor_comments":[{"comment":"The matrix P is described as 'column-stochastic' and satisfies P 1_k = 1_N, but this is row-stochasticity; the column sums are cluster sizes. Please correct the terminology.","section":"Definition 1"},{"comment":"The summation is written as sum_{i=r}^R but should be sum_{r=1}^R; please fix the typo.","section":"Equation (1)"},{"comment":"The notation [ [n] ] for the integer set is nonstandard and visually awkward; [n] or {1,...,n} would be clearer.","section":"Notation throughout"},{"comment":"The tables use t for the number of coarsened repetitions while the main text and Figure 7 use R; please unify the notation.","section":"Tables E3-E5 and Figure 7"},{"comment":"The statement 'Simulations showed that...' is used to justify the choice of sampling rule, but no simulation results are shown. Please add a figure or table in the appendix supporting this claim.","section":"Appendix B"},{"comment":"The phrase 'The experiment is repeated hundred five times' should read 'one hundred five times' or '105 times'.","section":"Appendix E.3"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for a machine learning/graph mining journal, and the public code release and breadth of clustering methods tested are clear strengths. The main uncertainty is empirical: the real-graph conclusions currently rest on single runs and a timing protocol that mixes parallel and serial execution. These issues are fixable within the manuscript's scope, so I recommend major revision rather than rejection. The self-citation to [10] is minor and does not affect my assessment."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does something real: it packages randomized coarsening, parallel clustering on multiple coarsened graphs, and OT-based fusion into a modular overlay that gives order-of-magnitude speedups for spectral clustering, CSC, and Infomap while keeping or improving partition quality. The integrated framework is new, the code is public, and the experiments cover both synthetic SSBM graphs and large OGB datasets. The complexity analysis is honest — coarsening is O((1+log ρ)|E|) and fusion scales linearly in N — and the OT fusion lemmas in the appendix check out. This is a solid engineering contribution, not a paradigm shift.\n\nNow the soft spots, in proportion. The biggest one is the structural-preservation claim. Section 3.3 explicitly labels the condition as a conjecture, and the mechanism in Algorithm 2 — where the second sampled node v can already be visited — can create rich-get-richer hypernode growth. A high-degree hub with cross-community edges can absorb many later unvisited nodes and produce hypernodes that span communities. The paper never reports hypernode size or purity distributions on real graphs. That is a genuine gap, but it is not fatal: the empirical evidence across many graphs and methods suggests the coarsening usually preserves enough structure, and the fusion step compensates for noisy individual coarsenings. Still, the abstract calls the coarsening \"structure-preserving\" without hedging, which overstates what is proven.\n\nThe second issue is experimental hygiene. Tables E3–E5 report single runs without error bars, and the timing comparison appears to give PASCO the benefit of parallel execution while the standalone clustering methods are single-core. The paper says clustering methods are run on a single core whether alone or with PASCO, but PASCO's own parallelized coarsening and clustering steps still count. That makes the reported speedup partly a hardware-parallelism effect. The authors should state clearly how many cores PASCO uses and rerun with error bars.\n\nMinor points: the self-citation to [10] includes a coauthor but is not load-bearing; the fusion phase uses standard OT solvers and the comparison to lin-reg and many-to-one is useful. The conjectured phase transition in SSBM parameters is interesting but not proved, and the paper would be stronger if it at least reported hypernode statistics to support the conjecture.\n\nWho is this for? Anyone doing large-scale graph clustering with spectral or Infomap-style methods. It deserves a serious referee: the contribution is useful, the code is real, and the main concerns are addressable with additional analysis and reruns. I would accept it for peer review with the expectation of a conditional decision requiring the missing error bars, a fairer timing protocol, and a more cautious abstract.","headline":"PASCO is a genuinely useful speedup overlay for spectral clustering and Infomap, with credible empirical support, but the structure-preserving mechanism is an explicit conjecture and the real-graph timings need error bars and a fairer parallel-vs-single-core comparison.","tokens_in":28523,"tokens_out":1710,"would_cite":true,"duration_ms":22757,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C82","68R10","62H30"],"pacs":[],"model":"deepseek-v4-flash","headline":"PASCO claims that coarsening a graph into several small copies, clustering them in parallel, and fusing the partitions by optimal transport speeds up graph clustering dramatically without sacrificing partition quality.","keywords":["graph clustering","community detection","graph coarsening","optimal transport","parallel computation","spectral clustering","large-scale networks"],"falsifier":"Run PASCO on a symmetric stochastic block model with $\\alpha = p_{\\text{out}}/p_{\\text{in}} > 1/(k-1)$ and measure the community purity of the hypernodes plus the AMI of the final partition: if the hypernodes are no purer than random and the output AMI collapses toward zero while the standalone method still recovers communities, the central structural-preservation claim is refuted. A second check would track the hypernode size distribution under Algorithm 2 to see whether a single giant hypernode forms.","tokens_in":27530,"feed_emoji":"⚡","tokens_out":4970,"duration_ms":42801,"temperature":0.7,"pith_summary":"This paper introduces PASCO, a three-step overlay that wraps any graph clustering method to make it faster: coarsen the input graph into several smaller graphs with a new randomized edge-contraction rule, cluster each small graph in parallel, then align and fuse the resulting partitions with an optimal-transport barycenter. The authors claim this pipeline materially reduces runtime or improves clustering quality for most methods and graphs tested, with spectral clustering and Infomap often sped up by a factor of 10 or more while matching or exceeding standalone partition quality. The gains matter because methods like spectral clustering become prohibitive on large networks, and PASCO is designed as a drop-in acceleration layer that does not require changing the clustering objective.","feed_headline":"PASCO speeds spectral clustering 10x without losing quality","feed_subtitle":"An overlay that coarsens a graph, clusters small copies in parallel, and fuses partitions to cut runtime.","key_machinery":"The load-bearing mechanism is the randomized edge-contraction coarsening of Algorithm 2: at each level, an unvisited node $u$ is chosen uniformly and merged with a uniformly chosen neighbor $v$ (which may already be visited), producing hypernodes larger than the classical two-node contractions; repeated with compression factor $\\rho$ until the target size $n = \\lfloor N/\\rho \\rfloor$ is reached, this costs $O((1+\\log \\rho)|E|)$. The second mechanism is the OT barycenter fusion: partitions are encoded as partition matrices, aligned by solving a Wasserstein distance linear program against a reference, and the reference is updated by majority vote until convergence.","core_discovery":"The central discovery is that a deliberately simple, randomized coarsening—sample an unvisited node uniformly, sample one of its neighbors uniformly, and merge them into a hypernode—combined with many independent coarsened copies and an optimal-transport fusion step is enough to preserve community structure while slashing computation time. On real graphs, PASCO wrapping spectral clustering, Compressive Spectral Clustering, or Infomap often achieves order-of-magnitude runtime reductions with AMI equal to or better than the standalone method, and the quality scores it outputs tend to sit closer to the ground-truth scores. The paper presents the structural-preservation property of the coarsening as a conjecture tied to a stochastic block model phase transition, supported empirically.","pith_inferences":["If the coarsening conjecture is proven, the same random-contraction plus fusion scheme could be applied to other graph algorithms bottlenecked by graph size, such as node classification or visualization, as the paper itself floats as future work.","The majority-vote fusion step suggests that the number of coarsened copies $R$ is the key tuning lever; a principled rule for choosing $R$ given $\\rho$ and the estimated number of communities would remove the current grid-search cost.","The unanalyzed rich-get-richer behavior of hypernode growth in Algorithm 2 means the method could be strengthened by a size-balancing variant, which would make the structural-preservation argument more robust in graphs with skewed degree distributions.","Because the gains concentrate in methods whose per-node cost grows with the number of clusters, PASCO should be most attractive for networks with many small communities, such as gene or trading networks."],"forward_implications":["Spectral clustering and other eigendecomposition-based methods can be run on graphs with many communities at a fraction of the cost, because the expensive decomposition happens on coarsened graphs of size $N/\\rho$.","PASCO is algorithm-agnostic: any clustering method that accepts weighted undirected graphs, including methods that choose the number of clusters automatically, can be accelerated by the same overlay.","The fusion step turns several noisy partitions into a more robust one, so increasing the number of coarsened copies $R$ improves quality even when the coarsening is aggressive.","For multilevel methods like Louvain and Leiden, PASCO does not reliably reduce runtime, but it often pushes AMI and intrinsic scores (modularity, description length) closer to the ground-truth partition.","The conjectured phase transition $\\alpha = p_{\\text{out}}/p_{\\text{in}} < 1/(k-1)$ in the stochastic block model gives a concrete regime where the coarsening is expected to preserve communities and where experiments show PASCO's behavior changes."],"supporting_citations":[{"why":"Supplies the classical multilevel edge-contraction coarsening scheme that PASCO's Algorithm 2 relaxes by allowing the neighbor $v$ to already be visited.","marker":"[16]"},{"why":"Provides the heavy-edge heuristic used as a baseline coarsening method and as the basis for more evolved coarsening approaches.","marker":"[29]"},{"why":"Defines the Restricted Spectral Approximation criterion used to measure structural preservation and provides the variation-edges coarsener that PASCO is compared against.","marker":"[18]"},{"why":"Gives the Compressive Spectral Clustering method that PASCO accelerates and supplies the SSBM parametrization used in the synthetic experiments.","marker":"[10]"},{"why":"Establishes the optimal-transport distance between partitions and the mean-partition consensus idea that PASCO's fusion step adopts.","marker":"[30]"},{"why":"Provides the alternating alignment-and-update method for Wasserstein barycenters that Algorithm 3 follows for partition fusion.","marker":"[32]"},{"why":"Is the Python optimal transport library used to solve the OT alignment problems in the implementation and experiments.","marker":"[31]"},{"why":"Defines Infomap, one of the multilevel description-length clustering methods that PASCO is shown to accelerate.","marker":"[5]"}],"fun_headline_variants":["PASCO accelerates graph clustering 10x","Parallel coarsening speeds clustering 10x","10x faster graph clustering with PASCO","Random coarsening cuts clustering runtime 10x","PASCO: 10x speedup, same cluster quality"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claimed speedups rely on the unproven assumption that randomly contracting edges preferentially merges nodes from the same community, and that the coarsened graphs retain enough community signal for the fusion step to recover; the paper labels this a conjecture in Section 3.3.","fun_headline_variants_meta":{"raw":{"variants":["PASCO accelerates graph clustering 10x","Parallel coarsening speeds clustering 10x","10x faster graph clustering with PASCO","Random coarsening cuts clustering runtime 10x","PASCO: 10x speedup, same cluster quality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000236,"raw_usage":{"total_tokens":1477,"prompt_tokens":891,"completion_tokens":586,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":507,"completion_tokens_details":{"reasoning_tokens":511}},"tokens_in":507,"tokens_out":586,"duration_ms":5819,"temperature":1.0,"reasoning_tokens":511,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:58:17.010228+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run PASCO on a symmetric stochastic block model with $\\alpha = p_{\\text{out}}/p_{\\text{in}} > 1/(k-1)$ and measure the community purity of the hypernodes plus the AMI of the final partition: if the hypernodes are no purer than random and the output AMI collapses toward zero while the standalone method still recovers communities, the central structural-preservation claim is refuted. A second check would track the hypernode size distribution under Algorithm 2 to see whether a single giant hypernode forms.","supporting_citations":[{"cited_title":"SC 95(28) (1995)","cited_arxiv_id":null,"evidence_quote":"Supplies the classical multilevel edge-contraction coarsening scheme that PASCO's Algorithm 2 relaxes by allowing the neighbor $v$ to already be visited."},{"cited_title":"SIAM Journal on scientific Computing 20(1) (1998)","cited_arxiv_id":null,"evidence_quote":"Provides the heavy-edge heuristic used as a baseline coarsening method and as the basis for more evolved coarsening approaches."},{"cited_title":"Journal of Machine Learning Research 20(116) (2019)","cited_arxiv_id":null,"evidence_quote":"Defines the Restricted Spectral Approximation criterion used to measure structural preservation and provides the variation-edges coarsener that PASCO is compared against."},{"cited_title":"ICML (2016)","cited_arxiv_id":null,"evidence_quote":"Gives the Compressive Spectral Clustering method that PASCO accelerates and supplies the SSBM parametrization used in the synthetic experiments."},{"cited_title":"Statistical Analysis and Data Mining: The ASA Data Science Journal 12(5) (2019)","cited_arxiv_id":null,"evidence_quote":"Establishes the optimal-transport distance between partitions and the mean-partition consensus idea that PASCO's fusion step adopts."},{"cited_title":"In: ICML (2014)","cited_arxiv_id":null,"evidence_quote":"Provides the alternating alignment-and-update method for Wasserstein barycenters that Algorithm 3 follows for partition fusion."},{"cited_title":"JMLR 22(78) (2021)","cited_arxiv_id":null,"evidence_quote":"Is the Python optimal transport library used to solve the OT alignment problems in the implementation and experiments."},{"cited_title":"PLOS ONE 6 (2011)","cited_arxiv_id":null,"evidence_quote":"Defines Infomap, one of the multilevel description-length clustering methods that PASCO is shown to accelerate."}],"review_version":1}