PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms

Etienne Lasalle (OCKHAM); M\`arton Karsai (CEU); Paulo Gon\c{c}alves (OCKHAM); Pierre Borgnat (Phys-ENS); R\'emi Gribonval (OCKHAM); R\'emi Vaudaine (OCKHAM); Titouan Vayer (OCKHAM)

REVIEW 3 major objections 6 minor 47 references

PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms

T0 review · 3 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2412.13592 v2 pith:UPISJMKZ submitted 2024-12-18 cs.LG stat.ML

Etienne Lasalle (OCKHAM) , Rémi Vaudaine (OCKHAM) , Titouan Vayer (OCKHAM) , Pierre Borgnat (Phys-ENS) , Rémi Gribonval (OCKHAM) , Paulo Gonçalves (OCKHAM) , Màrton Karsai (CEU) This is my paper · ORCID

classification cs.LGstat.ML MSC 05C8268R1062H30

keywords graphclusteringcommunitydetectioncoarseningoptimaltransportparallelcomputationspectrallarge-scalenetworks

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

Now 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.

The 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.

Minor 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.

Who 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.

Referee Report

3 major / 6 minor

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.

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 (3)

[Section 3.3, Algorithm 2] 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 5.3, Tables E3-E5] 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 5.3, Measuring Computational time] 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.

minor comments (6)

[Definition 1] 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.
[Equation (1)] The summation is written as sum_{i=r}^R but should be sum_{r=1}^R; please fix the typo.
[Notation throughout] The notation [ [n] ] for the integer set is nonstandard and visually awkward; [n] or {1,...,n} would be clearer.
[Tables E3-E5 and Figure 7] The tables use t for the number of coarsened repetitions while the main text and Figure 7 use R; please unify the notation.
[Appendix B] 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.
[Appendix E.3] The phrase 'The experiment is repeated hundred five times' should read 'one hundred five times' or '105 times'.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: PASCO's speed and quality claims are benchmarked against external methods and datasets; the only self-citations are non-load-bearing.

full rationale

PASCO's derivation chain is not circular in any load-bearing sense. The three pipeline components are defined independently of the claims: coarsening is a randomized edge-contraction procedure (Algorithms 1-2), clustering is any off-the-shelf method, and fusion solves an OT barycenter problem (Equation 1) using a majority-vote update (Equation 3). The main claims—speedups and partition quality—are evaluated against external baselines (plain SC, Louvain, Leiden, Infomap, etc.) on OGB graphs with ground-truth partitions and externally defined metrics (AMI, modularity, gnCut, DL, and Loukas's RSA). No parameter is fitted to a subset of the data and then reported as a prediction; the hyperparameters rho and R are swept and their effects are reported. The Section 3.3 'structure-preserving' premise is explicitly labeled a conjecture ('This remains a conjecture, not yet supported by rigorous proof'), and its supporting derivation is only an expectation comparison in the SSBM, not a conclusion imported from prior work. The only self-citations involving the authors are [10] (used for SSBM parametrization and as a baseline method) and [35] (the code repository); neither carries the burden of the central claim. The skeptical concern about rich-get-richer hypernode growth is a valid correctness risk, not a circularity, because the paper never defines coarsening quality in terms of the final AMI that it later reports.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

PASCO introduces algorithmic components and hyperparameters rather than new physical or model entities. The central assumptions are the unproved structural-preservation conjecture for random coarsening, the SSBM modeling of synthetic graphs, and the practical convergence of the OT fusion loop.

free parameters (4)

Compression factor rho = default 10; swept over {1,3,5,10,15,20}
Sets the target coarsened graph size n = floor(N/rho) and directly controls the speed/quality tradeoff in all experiments.
Number of coarsened graphs R = default 10; swept over {1,3,5,10,15,20}
Ensemble size in the fusion step; larger R improves AMI but increases total runtime.
Target number of clusters k in OT barycenter = median(k_1,...,k_R), or k_1 if all equal
Heuristic in Algorithm 3 that fixes the output cluster count and initializes the reference partition for the fusion step.
Fusion convergence criterion = not specified; reported around 10 iterations
Algorithm 3 loops until P converges, but no formal stopping rule, tolerance, or convergence guarantee is given.

assumptions (4)

domain assumption The symmetric stochastic block model is the generative model for synthetic graphs used to analyze coarsening behavior.
Definition 3 introduces SSBM(N,k,d,alpha), and Section 3.3 uses it to argue that intra-community edges are preferentially contracted.
ad hoc to paper Random coarsening preserves community structure when alpha = pout/pin < 1/(k-1).
Section 3.3 explicitly labels this as a conjecture, not a proof, and the paper relies on it to explain performance thresholds in the synthetic experiments.
domain assumption The input graph has no isolated nodes, bounding the coarsening complexity proof.
Appendix C states that a graph with no isolated nodes can be assumed, and uses this to reduce the coarsening complexity to O((1+log rho)|E|).
ad hoc to paper Alternating minimization for the OT barycenter converges to a useful consensus in a small number of iterations.
Algorithm 3 uses a while loop until convergence, with no convergence proof; Section 4 observes empirically that niter is small, around 10.

how reviews work

0 comments

Cite this review

Pith. "Pith review of PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms." pith.science (2026). https://pith.science/paper/UPISJMKZ

@misc{pith2026241213592,
  author       = {Pith},
  title        = {Pith review of: PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UPISJMKZ}},
  note         = {Machine review of arXiv:2412.13592}
}

read the original abstract

Clustering the nodes of a graph is a cornerstone of graph analysis and has been extensively studied. However, some popular methods are not suitable for very large graphs: e.g., spectral clustering requires the computation of the spectral decomposition of the Laplacian matrix, which is not applicable for large graphs with a large number of communities. This work introduces PASCO, an overlay that accelerates clustering algorithms. Our method consists of three steps: 1-We compute several independent small graphs representing the input graph by applying an efficient and structure-preserving coarsening algorithm. 2-A clustering algorithm is run in parallel onto each small graph and provides several partitions of the initial graph. 3-These partitions are aligned and combined with an optimal transport method to output the final partition. The PASCO framework is based on two key contributions: a novel global algorithm structure designed to enable parallelization and a fast, empirically validated graph coarsening algorithm that preserves structural properties. We demonstrate the strong performance of 1 PASCO in terms of computational efficiency, structural preservation, and output partition quality, evaluated on both synthetic and real-world graph datasets.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 46 canonical work pages

[10]

ICML (2016)

Tremblay, N., Puy, G., Gribonval, R., Vandergheynst, P.: Compressive spectral clustering. ICML (2016)

work page 2016
[1]

Statistics and computing 17 (2007)

Von Luxburg, U.: A tutorial on spectral clustering. Statistics and computing 17 (2007)

work page 2007
[2]

Physics reports 486 (2010)

Fortunato, S.: Community detection in graphs. Physics reports 486 (2010)

work page 2010
[3]

Physics Reports 659 (2016)

Fortunato, S., Hric, D.: Community detection in networks: A user guide. Physics Reports 659 (2016). Community detection in networks: A user guide

work page 2016
[4]

In: 2018 International Congress on Big Data, Deep Learning and Fighting Cyber Terrorism (IBIGDELFT) (2018)

Karata¸ s, A., S ¸ahin, S.: Application areas of community detection: A review. In: 2018 International Congress on Big Data, Deep Learning and Fighting Cyber Terrorism (IBIGDELFT) (2018)

work page 2018
[5]

PLOS ONE 6 (2011)

Rosvall, M., Bergstrom, C.T.: Multilevel compression of random walks on net- works reveals hierarchical organization in large integrated systems. PLOS ONE 6 (2011)

work page 2011
[6]

Physical Review E 89(1) (2014)

Peixoto, T.P.: Efficient monte carlo and greedy heuristic for the inference of stochastic block models. Physical Review E 89(1) (2014)

work page 2014
[7]

Journal of statistical mechanics: theory and experiment 2008(10) (2008)

Blondel, V.D., Guillaume, J.-L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment 2008(10) (2008)

work page 2008

Show all 47 references

[8]

IEEE Open Journal of Signal Processing 1 (2020)

Pourkamali-Anaraki, F.: Scalable spectral clustering with nystr¨ om approxima- tion: Practical and theoretical aspects. IEEE Open Journal of Signal Processing 1 (2020)

2020
[9]

In: ICML (2015)

Boutsidis, C., Kambadur, P., Gittens, A.: Spectral clustering via the power method-provably. In: ICML (2015)

2015
[11]

SIAM Journal on Computing 40(4) (2011) 19

Spielman, D.A., Teng, S.-H.: Spectral sparsification of graphs. SIAM Journal on Computing 40(4) (2011) 19

2011
[12]

In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (2008)

Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (2008)

2008
[13]

Sampling Techniques for Supervised or Unsupervised Tasks (2020)

Tremblay, N., Loukas, A.: Approximating spectral clustering via sampling: a review. Sampling Techniques for Supervised or Unsupervised Tasks (2020)

2020
[14]

In: Pro- ceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2009)

Yan, D., Huang, L., Jordan, M.I.: Fast approximate spectral clustering. In: Pro- ceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2009)

2009
[15]

In: AAAI (2015)

Li, Y., Nie, F., Huang, H., Huang, J.: Large-scale multi-view spectral clustering via bipartite graph. In: AAAI (2015)

2015
[16]

SC 95(28) (1995)

Hendrickson, B., Leland, R.W., et al.: A multi-level algorithm for partitioning graphs. SC 95(28) (1995)

1995
[17]

IEEE transactions on pattern analysis and machine intelligence 29(11) (2007)

Dhillon, I.S., Guan, Y., Kulis, B.: Weighted graph cuts without eigenvectors a multilevel approach. IEEE transactions on pattern analysis and machine intelligence 29(11) (2007)

2007
[18]

Journal of Machine Learning Research 20(116) (2019)

Loukas, A.: Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research 20(116) (2019)

2019
[19]

Applied Mathematics & Nonlinear Sciences 4(1) (2019)

Bunimovich, L., Smith, D., Webb, B.: Finding hidden structures, hierarchies, and cores in networks via isospectral reduction. Applied Mathematics & Nonlinear Sciences 4(1) (2019)

2019
[20]

In: International Conference on Artificial Intelligence and Statistics, pp

Jin, Y., Loukas, A., JaJa, J.: Graph coarsening with preserved spectral properties. In: International Conference on Artificial Intelligence and Statistics, pp. 4452– 4462 (2020). PMLR

2020
[21]

SeMA Journal 79(1), 187–223 (2022)

Chen, J., Saad, Y., Zhang, Z.: Graph coarsening: from scientific computing to machine learning. SeMA Journal 79(1), 187–223 (2022)

2022
[22]

arXiv preprint arXiv:2105.02022 (2021)

Gottesb¨ uren, L., Heuer, T., Sanders, P., Schulz, C., Seemaier, D.: Deep multilevel graph partitioning. arXiv preprint arXiv:2105.02022 (2021)

2021 arXiv
[23]

Journal of Experimental Algorithmics (JEA) 16, 2–1 (2011)

Rotta, R., Noack, A.: Multilevel local search algorithms for modularity clustering. Journal of Experimental Algorithmics (JEA) 16, 2–1 (2011)

2011
[24]

The European physical journal B 86, 1–14 (2013)

Waltman, L., Van Eck, N.J.: A smart local moving algorithm for large-scale modularity-based community detection. The European physical journal B 86, 1–14 (2013)

2013
[25]

Data Clustering (2018) 20

Ghosh, J., Acharya, A.: Cluster ensembles: Theory and applications. Data Clustering (2018) 20

2018
[26]

IEEE transactions on knowledge and data engineering 27(1) (2014)

Wu, J., Liu, H., Xiong, H., Cao, J., Chen, J.: K-means-based consensus cluster- ing: A unified view. IEEE transactions on knowledge and data engineering 27(1) (2014)

2014
[27]

In: International Work- shop on Multiple Classifier Systems (2001)

Fred, A.: Finding consistent clusters in data partitions. In: International Work- shop on Multiple Classifier Systems (2001)

2001
[28]

Foundations and Trends® in Machine Learning 11(5-6) (2019)

Peyr´ e, G., Cuturi, M., et al.: Computational optimal transport: With applications to data science. Foundations and Trends® in Machine Learning 11(5-6) (2019)

2019
[29]

SIAM Journal on scientific Computing 20(1) (1998)

Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing 20(1) (1998)

1998
[30]

Statistical Analysis and Data Mining: The ASA Data Science Journal 12(5) (2019)

Li, J., Seo, B., Lin, L.: Optimal transport, mean partition, and uncertainty assess- ment in cluster analysis. Statistical Analysis and Data Mining: The ASA Data Science Journal 12(5) (2019)

2019
[31]

JMLR 22(78) (2021)

Flamary, R., Courty, N., Gramfort, A., Alaya, M.Z., Boisbunon, A., Chambon, S., Chapel, L., Corenflos, A., Fatras, K., Fournier, N., et al.: Pot: Python optimal transport. JMLR 22(78) (2021)

2021
[32]

In: ICML (2014)

Cuturi, M., Doucet, A.: Fast computation of wasserstein barycenters. In: ICML (2014)

2014
[33]

Pattern Recognition 43(5) (2010)

Ayad, H.G., Kamel, M.S.: On voting-based consensus of cluster ensembles. Pattern Recognition 43(5) (2010)

2010
[34]

In: AISTATS (2018)

Blondel, M., Seguy, V., Rolet, A.: Smooth and sparse optimal transport. In: AISTATS (2018)

2018
[35]

https://hal.science/hal-05086352

Lasalle, E., Vaudaine, R., Vayer, T.: PASCO. https://hal.science/hal-05086352
[36]

In: ICML (2018)

Loukas, A., Vandergheynst, P.: Spectrally approximating large graphs with smaller graphs. In: ICML (2018)

2018
[37]

arXiv preprint arXiv:2005.00687 (2020)

Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., Leskovec, J.: Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687 (2020)

2020 arXiv
[38]

In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2004)

Dhillon, I.S., Guan, Y., Kulis, B.: Kernel k-means: spectral clustering and normal- ized cuts. In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2004)

2004
[39]

Scientific reports 9(1) (2019)

Traag, V.A., Waltman, L., Van Eck, N.J.: From louvain to leiden: guaranteeing well-connected communities. Scientific reports 9(1) (2019)

2019
[40]

Physical review E 69 (2004) 21

Newman, M.E., Girvan, M.: Finding and evaluating community structure in networks. Physical review E 69 (2004) 21

2004
[41]

Rissanen, J.: Information and complexity in statistical modeling (2007)

2007
[42]

Mathematical programming 45(1) (1989)

Liu, D.C., Nocedal, J.: On the limited memory bfgs method for large scale optimization. Mathematical programming 45(1) (1989)

1989
[43]

Newman, M.E.J.: Networks : an introduction (2010)

2010
[44]

Linux Journal 2013(235), 3 (2013)

Quemener, E., Corvellec, M.: Sidus—the solution for extreme deduplication of an operating system. Linux Journal 2013(235), 3 (2013)

2013
[45]

AAAI (2015)

Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. AAAI (2015)

2015
[46]

re-aligned partition

Vinh, N.X., Epps, J., Bailey, J.: Information theoretic measures for clusterings comparison: is a correction for chance necessary? In: ICML (2009) 22 Appendix A Finding consensus between partitions In this section we describe the different approaches that we investigated for a...

2009
[47]

We emphasize that the K-means algorithm benefits from the spatial coordinates of the data points, whereas the alignment+fusion methods operate solely on the different partitions P1, · · ·, PR, and ignore the positions. The experiment is repeated hundred five times, and the ave...

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [10]

ICML (2016)

Tremblay, N., Puy, G., Gribonval, R., Vandergheynst, P.: Compressive spectral clustering. ICML (2016)

work page 2016

[2] [1]

Statistics and computing 17 (2007)

Von Luxburg, U.: A tutorial on spectral clustering. Statistics and computing 17 (2007)

work page 2007

[3] [2]

Physics reports 486 (2010)

Fortunato, S.: Community detection in graphs. Physics reports 486 (2010)

work page 2010

[4] [3]

Physics Reports 659 (2016)

Fortunato, S., Hric, D.: Community detection in networks: A user guide. Physics Reports 659 (2016). Community detection in networks: A user guide

work page 2016

[5] [4]

In: 2018 International Congress on Big Data, Deep Learning and Fighting Cyber Terrorism (IBIGDELFT) (2018)

Karata¸ s, A., S ¸ahin, S.: Application areas of community detection: A review. In: 2018 International Congress on Big Data, Deep Learning and Fighting Cyber Terrorism (IBIGDELFT) (2018)

work page 2018

[6] [5]

PLOS ONE 6 (2011)

Rosvall, M., Bergstrom, C.T.: Multilevel compression of random walks on net- works reveals hierarchical organization in large integrated systems. PLOS ONE 6 (2011)

work page 2011

[7] [6]

Physical Review E 89(1) (2014)

Peixoto, T.P.: Efficient monte carlo and greedy heuristic for the inference of stochastic block models. Physical Review E 89(1) (2014)

work page 2014

[8] [7]

Journal of statistical mechanics: theory and experiment 2008(10) (2008)

Blondel, V.D., Guillaume, J.-L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment 2008(10) (2008)

work page 2008