Pith. sign in

REVIEW 3 major objections 5 minor 54 references

Linear-Time Multilevel Graph Partitioning via Edge Sparsification

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read The paper claims that multilevel graph partitioning can be made to run in expected $O(n + m)$ time on any graph by capping every coarsening level with edge sparsification, and reports a $1.49\times$ average speedup over KaMinPar with…

desk verdict Strong paper with a genuinely new idea, but the headline O(n+m) total-work claim is asserted, not proved; worth serious peer review. read the letter →

arxiv 2504.17615 v1 pith:B6HIKOST submitted 2025-04-24 cs.DS

Lars Gottesbüren , Nikolai Maas , Dominik Rosch , Peter Sanders , Daniel Seemaier This is my paper · ORCID
classification cs.DS
keywords graphpartitioningmultilevelalgorithmscoarsening2-hopclusteringedgesparsificationlineartimebalancedmodularity
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

Balanced graph partitioning has asked users to choose between high-quality but slow multilevel algorithms and fast but lower-quality single-level or streaming approaches. This paper claims the choice is unnecessary. It presents a coarsening scheme in which every level of the multilevel hierarchy shrinks by a constant factor: size-constrained label propagation and 2-hop clustering handle nodes, while a sparsification step caps the edge count whenever contraction would leave the level too dense. The paper proves this yields $O(n + m)$ expected total work on any graph with no structural assumptions, and it reports that integrating the scheme into the KaMinPar partitioner gives a $1.49\times$ average speedup (up to $4\times$) with only about $1\%$ larger cuts, beating the single-level and streaming baselines on both speed and quality. It also shows that graphs with low modularity are the ones most likely to trigger the worst-case behavior that sparsification addresses.

What carries the argument

The load-bearing mechanism is a two-part coarsening scheme. Size-constrained label propagation forms clusters of neighboring nodes up to weight $U$, with the rule that no node stays alone if an adjacent cluster has room. A 2-hop clustering step then looks at each remaining singleton cluster, chooses a favorite neighboring cluster (the paper's term for its candidate partner), and merges all singletons that picked the same favorite, provided weights allow. This favorite-cluster rule is what makes Theorem 1's injection argument work: each singleton can be charged to a distinct heavy cluster, giving $|C_1| \le |C_h|$. The second half of the machinery is the sparsification threshold $\hat{m}$ and the weighted threshold sampling that enforces it; this is what converts a logarithmic number of unavoidable dense levels into a linear total.

What would settle it

Run the real coarsening on a graph with many singleton clusters while recording the favorite-cluster assignments, then check whether singleton pairs sharing a favorite remain unmerged; if a positive fraction of such pairs survives, the inequality $|C| \le \frac{1}{2}|V| + \frac{c(V)}{U}$ can fail. Measuring total running time with the number of blocks $k$ growing like $n^\alpha$ would likewise expose whether the $k \log k$ budget holds.

Watch

Extended reading notes

Core claim

At the core of the paper is the observation that the two sources of superlinear work in multilevel partitioning—node counts that fail to shrink and edge counts that grow on coarse levels—can be attacked separately. The paper proves (Theorem 1) that if coarsening uses size-constrained label propagation followed by 2-hop clustering, the number of clusters satisfies $|C| \le \frac{1}{2}|V| + \frac{c(V)}{U}$ for $U \ge \frac{2c(V)}{|V|}$, so every level shrinks by a constant factor once the cluster-weight limit is large enough. For edges, the paper introduces a sparsification step that caps each coarse level at $\hat{m} = \min\{\tau_e |E_i|, \tau_d \frac{|E_i|}{|V_i|}|V_{i+1}|\}$ edges; the preferred weighted threshold sampling keeps the heaviest edges and samples among ties. Because sparsification is triggered only when it reduces the edge count by a constant factor $\rho$, the geometric shrinking of both nodes and edges gives expected $O(n + m)$ total work. The empirical claim is that integrating this into KaMinPar produces a $1.49\times$ average speedup with about $1\%$ larger cuts.

Load-bearing premise

The constant-factor node-reduction proof assumes the 2-hop clustering implementation actually merges every pair of leftover singletons that share the same favorite neighboring cluster when weights allow, and the $O(n + m)$ bound additionally assumes $k \log k$ fits inside the linear budget for the number of blocks $k$; if either fails, the guarantee weakens to more than linear work.

Editorial extensions

If this is right

  • Any graph, regardless of structure, is covered by the $O(n + m)$ expected total-work bound, so multilevel partitioning no longer has an instance-dependent superlinear blow-up.
  • The algorithm remains genuinely multilevel, preserving the refinement quality of the hierarchy while keeping total work linear.
  • Graphs with low modularity, the ones that previously forced worst-case behavior, become the largest beneficiaries, with speedups up to $4\times$ in the reported experiments.
  • In the reported comparisons, the method produces both smaller cuts and lower running times than the single-level baseline PuLP and the streaming baseline CUTTANA.
  • Parallel scalability is retained because the added sparsification step is linear-work and parallelizable.

Reading between the lines

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

  • If a real implementation merges fewer singleton pairs than the idealized favorite-cluster rule, the constant-factor node reduction may still hold with a slightly larger constant, so the linear-time guarantee could survive with adjusted thresholds.
  • The modularity diagnosis suggests a practical pre-screen: compute modularity first and enable aggressive sparsification only for low-modularity graphs, avoiding most of the 1% quality loss.
  • The same recipe—geometric node reduction plus a per-level edge budget—should transfer to other multilevel schemes, including hypergraph partitioning, where coarse-level edge growth is the usual source of superlinear work.
  • Because the proof is expected-time and sampling-based, a deterministic variant that always keeps the heaviest edges could convert the guarantee into deterministic linear time at possibly higher constant cost.
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.

Referee Report

3 major / 5 minor

Summary. The paper proposes a multilevel graph partitioning coarsening scheme that adds edge sparsification to size-constrained label propagation with 2-hop clustering, with the aim of guaranteeing linear total work while retaining multilevel quality. Section 4 proves a constant-factor node-reduction theorem for an idealized 2-hop clustering model, introduces Algorithm 1 with edge/density thresholds and a sparsification trigger, and informally claims a geometric edge shrinkage that yields O(n+m) expected time. Section 5 relates the need for sparsification to low modularity. The engineering component integrates weighted threshold sampling into KaMinPar and reports a 1.49x geometric mean speedup with roughly 1% cut degradation, outperforming PuLP and Cuttana. The experiments are carefully designed and the measured behavior is consistent with the intended mechanism, but the advertised linear-time theorem is not actually stated or proved in the manuscript.

Significance. If the linear-work theorem could be rigorously established, the paper would resolve a well-known trade-off in practical graph partitioning: multilevel quality at single-level speed. The node-reduction proof is clean and the modularity-based characterization is a useful falsifiable empirical claim; the parameter study and comparison against PuLP and Cuttana are thorough, and the implementation-level analysis of where time is spent is strong. These contributions are real. However, the central theoretical claim---the unconditional O(n+m) expected total-work bound---is currently unsupported, so the significance statement must be downgraded until a formal theorem is supplied with explicit parameter conditions.

major comments (3)
  1. [Abstract; §4.2–4.3, Algorithm 1] The advertised O(n + m) expected total-work guarantee is not stated as a theorem and does not follow from the ingredients given. With Algorithm 1, the no-trigger case only yields |E_{i+1}| <= rho * hat_m. For the tuned values tau_e = tau_d = 1/2 and rho = 4, and using the Theorem 1 node bound |V_{i+1}| <= |V_i|/2 + 160k, the density term of hat_m gives |E_{i+1}| <= (1 + 320k/|V_i|) * |E_i|, which is not a contraction for any finite |V_i|. The edge-threshold term gives the even weaker |E_{i+1}| <= 2|E_i|. Thus the analysis does not rule out hierarchies in which the edge count remains essentially constant for Theta(log n) levels, which would yield Theta(m log n) total work. A formal total-work theorem is needed; it must either impose parameter conditions such that rho * max{tau_e, tau_d * |V_{i+1}|/|V_i|} < 1 for all sufficiently large |V_i|, or supply a product/telescoping argument over the hierarchy, including the expectation over the randomized sparsification.
  2. [§4.1, Theorem 1] Theorem 1's proof requires that the 2-hop clustering merges every pair of singleton clusters that share the same favorite cluster; the text introduces this as an assumption ("we will assume that the algorithm assigns a favorite cluster K_S to S..."), but the paper does not establish that KaMinPar's actual 2-hop implementation satisfies this rule. If the implementation only merges singletons in a more restricted way, the bound |C1| <= |Ch|---and hence the geometric node-reduction factor used in Section 4.3---may fail for the integrated algorithm. Please either verify that the implementation matches the model exactly, or explicitly state Theorem 1 for the idealized model and add an empirical test that the implemented coarsening achieves the constant node-reduction factor on the benchmark graphs.
  3. [§4.3] The statement "The recursive bipartitioning then requires total time O(k log k), which is linear under the extremely weak assumption that k log k in O(n+m)" conflicts with the abstract's claim of a guarantee "without any assumptions on the input graph." For valid inputs with k = Theta(n), k log k = Theta(n log n), so the total work is not linear. The formal claim must explicitly state the dependence on k (e.g., k fixed, or k log k in O(n+m)) and cannot be presented as unconditional.
minor comments (5)
  1. [§4.1, proof of Theorem 1] The quantity r is defined as the average cluster size of C2, but the case |C2| = 0 is not handled; the proof divides by r. This can be fixed by treating the case |C2| = 0 separately.
  2. [§4.2, Algorithm 1] The description of the sparsification step says the target is hat_m, but the sampling procedures produce hat_m edges only in expectation; the algorithm should state explicitly that the output size is the realized sample size and that the subsequent level's edge count is the realized one.
  3. [§5, Lemma 2] The definition of alpha in Lemma 2 is imprecise: alpha = max_i a_i is the maximum fraction of edges incident to a single cluster, not "the maximum fraction of edges with endpoints in the same cluster."
  4. [§6.3] The comparison between KaMinPar, PuLP, and Cuttana excludes instances on which Cuttana crashes, but the sentence "we exclude these instances in pairwise aggregates" is ambiguous about whether the speedup and cut comparisons are recomputed on the common subset; please clarify.
  5. [Figure 4 caption] The captions "T □ Weight" and "T □ WFF" appear to contain formatting artifacts (missing hyphens or spaces); please check renderings.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the linear-time analysis is a new bound, and the experimental speedups are external comparisons rather than fitted-input predictions.

full rationale

We walked the chain of claims in the paper and found no step in which a claimed prediction reduces by construction to an input, a fitted parameter, or a self-citation. The central theoretical claims are the node-reduction bound (Theorem 1) and the sparsification-trigger mechanism (Algorithm 1). Theorem 1 is proved from an explicitly stated favorite-cluster model of 2-hop clustering; the bound |C1| <= |Ch| depends on that modeling assumption, but the paper states the assumption openly, and the argument is a genuine inequality rather than a definitional restatement. If KaMinPar's actual 2-hop implementation does not follow the favorite-cluster rule, the guarantee may fail in practice, but that is an assumption-versus-implementation gap, not circularity. The edge-sparsification argument does contain a real proof gap: the paper claims geometric edge shrink and linear expected total work, yet Algorithm 1 only guarantees |E_{i+1}| <= rho * min(tau_e |E_i|, tau_d (|E_i|/|V_i|) |V_{i+1}|) in the non-trigger case, and no telescoping lemma is stated or proved. That is a missing theorem and a correctness risk, but it is not a circular reduction: the bound is not defined to equal the conclusion. The tuned parameters tau_e, tau_d, and rho are fitted on a small tuning set, but the linear-time claim only requires them to be constants satisfying the threshold inequalities; no fitted value is renamed as a predicted result. The speedup and quality comparisons are measured against external baselines (KaMinPar without sparsification, PuLP, Cuttana), so the empirical claims are self-contained and falsifiable. The self-citations to KaMinPar and related prior work provide the base framework and per-level linear-time building blocks; the new paper adds its own formal node-reduction proof and the sparsification mechanism, so the citations are not load-bearing in a circular way. We therefore exhibit no circular step and assign the baseline score.

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

The central claim rests on the coarsening model (label propagation plus 2-hop clustering with favorite clusters), on linear per-level costs of the underlying partitioner, on a small-block assumption k log k in O(n+m), and on several tuned constants (tau_e, tau_d, rho, U) that are fit to a small tuning set but are not needed for the theoretical guarantee beyond satisfying inequalities.

free parameters (6)
  • tau_e (edge threshold) = 1/2
    Limits coarse edge count relative to current level. Tuned on an 8-graph subset in Section 6.1; affects speedup vs. quality trade-off.
  • tau_d (density threshold) = 1/2
    Limits average degree of coarse graphs. Tuned on the same subset; contributes to the geometric edge-reduction guarantee.
  • rho (minimum edge reduction factor) = 4
    Sparsification is triggered only if the edge-count reduction is at least rho. Tuned on the subset; larger rho preserves quality.
  • U (maximum cluster weight) = c(V)/(160k)
    Size-constrained label propagation parameter. The constant 160 appears in the coarsening termination threshold 320k, which lets Theorem 1 apply.
  • max node reduction per level = 2.5x
    Heuristic limit on coarsening speed to avoid too aggressive clustering; used in Section 4.3.
  • Forest Fire parameters p, nu = p=0.6, nu=0.5
    Used for the T-WFF variant, which was not competitive; included as an evaluated alternative in Section 6.1.
assumptions (6)
  • domain assumption Each round of size-constrained label propagation runs in linear time, with a constant number of rounds, so coarsening and refinement are linear per hierarchy level.
    Stated in Section 3 and used throughout the total-work argument in Section 4.
  • domain assumption A node never remains a singleton if an adjacent cluster can absorb it under the weight constraint (essential property of size-constrained label propagation).
    Assumed in Section 4.1 before Theorem 1; if violated, the theorem's bound on singleton clusters fails.
  • domain assumption 2-hop clustering merges all singleton clusters sharing a favorite cluster, subject to the weight limit.
    Stated in Section 4.1; used to prove |C1| <= |Ch| in Theorem 1.
  • domain assumption k log k in O(n+m), i.e., the number of blocks is small enough that initial partitioning time is linear.
    Section 4.3 uses this to absorb the O(k log k) recursive bipartitioning cost into the linear bound.
  • standard math Balanced graph partitioning is NP-hard to approximate to constant factor.
    Cited in the introduction to motivate heuristics.
  • standard math Modularity maximization is NP-hard; Louvain provides a usable approximation.
    Cited in Section 5 to justify using approximate modularity scores.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Linear-Time Multilevel Graph Partitioning via Edge Sparsification." pith.science (2026). https://pith.science/paper/B6HIKOST

@misc{pith2026250417615,
  author       = {Pith},
  title        = {Pith review of: Linear-Time Multilevel Graph Partitioning via Edge Sparsification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/B6HIKOST}},
  note         = {Machine review of arXiv:2504.17615}
}
abstract

The current landscape of balanced graph partitioning is divided into high-quality but expensive multilevel algorithms and cheaper approaches with linear running time, such as single-level algorithms and streaming algorithms. We demonstrate how to achieve the best of both worlds with a \emph{linear time multilevel algorithm}. Multilevel algorithms construct a hierarchy of increasingly smaller graphs by repeatedly contracting clusters of nodes. Our approach preserves their distinct advantage, allowing refinement of the partition over multiple levels with increasing detail. At the same time, we use \emph{edge sparsification} to guarantee geometric size reduction between the levels and thus linear running time. We provide a proof of the linear running time as well as additional insights into the behavior of multilevel algorithms, showing that graphs with low modularity are most likely to trigger worst-case running time. We evaluate multiple approaches for edge sparsification and integrate our algorithm into the state-of-the-art multilevel partitioner KaMinPar, maintaining its excellent parallel scalability. As demonstrated in detailed experiments, this results in a $1.49\times$ average speedup (up to $4\times$ for some instances) with only 1\% loss in solution quality. Moreover, our algorithm clearly outperforms state-of-the-art single-level and streaming approaches.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 18 canonical work pages

  1. [1]

    Multilevel Algorithms for Partitioning Power-Law Graphs

    Amine Abou-Rjeili and George Karypis. Multilevel Algorithms for Partitioning Power-Law Graphs . In 20th International Conference on Parallel and Distributed Processing ( IPDPS ) . IEEE Computer Society, 2006. https://doi.org/10.1109/IPDPS.2006.1639360 doi:10.1109/IPDPS.2006.1639360

    arXiv 2006

  2. [2]

    Ahmed, Jennifer Neville, and Ramana Rao Kompella

    Nesreen K. Ahmed, Jennifer Neville, and Ramana Rao Kompella. Network Sampling: From Static to Streaming Graphs . ACM Transactions on Knowledge Discovery from Dat , 8(2):7:1--7:56, 2013. https://doi.org/10.1145/2601438 doi:10.1145/2601438

    work page doi:10.1145/2601438 2013

  3. [3]

    High-Quality Shared-Memory Graph Partitioning

    Yaroslav Akhremtsev, Peter Sanders, and Christian Schulz. High-Quality Shared-Memory Graph Partitioning . In 24th European Conference on Parallel Processing (Euro-Par) , pages 659--671. Springer, 8 2018. https://doi.org/10.1007/978-3-319-96983-1_47 doi:10.1007/978-3-319-96983-1_47

    work page doi:10.1007/978-3-319-96983-1_47 2018

  4. [4]

    Balanced Graph Partitioning

    Konstantin Andreev and Harald R \" a cke. Balanced Graph Partitioning . In 16th ACM Symposium on Parallelism in Algorithms and Architectures ( SPAA ) , pages 120--124, 2004. https://doi.org/10.1145/1007912.1007931 doi:10.1145/1007912.1007931

    arXiv 2004

  5. [5]

    Algorithms for Large-Scale Network Analysis and the NetworKit Toolkit

    Eugenio Angriman, Alexander van der Grinten, Michael Hamann, Henning Meyerhenke, and Manuel Penschuck. Algorithms for Large-Scale Network Analysis and the NetworKit Toolkit . In Algorithms for Big Data: DFG Priority Program 1736 , pages 3--20. Springer, 2023. https://doi.org/10.1007/978-3-031-21534-6_1 doi:10.1007/978-3-031-21534-6_1

    doi:10.1007/978-3-031-21534-6_1 2023

  6. [6]

    Prioritized Restreaming Algorithms for Balanced Graph Partitioning

    Amel Awadelkarim and Johan Ugander. Prioritized Restreaming Algorithms for Balanced Graph Partitioning . In 26th Conference on Knowledge Discovery and Data Mining ( SIGKDD ) , pages 1877--1887. ACM , 2020. https://doi.org/10.1145/3394486.3403239 doi:10.1145/3394486.3403239

    arXiv 2020

  7. [7]

    Cevdet Aykanat, Berkant Barla Cambazoglu, Ferit Findik, and Tahsin M. Kur c . Adaptive decomposition and remapping algorithms for object-space-parallel direct volume rendering of unstructured grids. Journal of Parallel and Distributed Computing , 67(1):77--99, 2007. https://doi.org/10.1016/J.JPDC.2006.05.005 doi:10.1016/J.JPDC.2006.05.005

    work page doi:10.1016/j.jpdc.2006.05.005 2007

  8. [8]

    Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner

    David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner. Graph Partitioning and Graph Clustering , volume 588. American Mathematical Society Providence, 2013. https://doi.org/10.1090/conm/588 doi:10.1090/conm/588

    doi:10.1090/conm/588 2013

Show all 54 references
  1. [9]

    Bencz\' u r and David R

    Andr\' a s A. Bencz\' u r and David R. Karger. Approximating s-t minimum cuts in \ O ( n^2 ) time. In 28th Symposium on Theory of Computing ( STOC ) , pages 47--55. ACM, 1996. https://doi.org/10.1145/237814.237827 doi:10.1145/237814.237827

    1996

  2. [10]

    Blondel, Jean Guillaume, Renaud Lambiotte, and Etienne Lefebvre

    Vincent D. Blondel, Jean Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast Unfolding of Communities in Large Networks . Journal of Statistical Mechanics: Theory and Experiment , 2008. https://doi.org/10.1088/1742-5468/2008/10/P10008 doi:10.1088/1742-5468/2008/10/P10008

    2008 doi

  3. [11]

    Boman, Karen D

    Erik G. Boman, Karen D. Devine, and Sivasankaran Rajamanickam. Scalable Matrix Computations on Large Scale-Free Graphs Using 2D Graph Partitioning . In International Conference for High Performance Computing, Networking, Storage and Analysis (SC) , pages 50:1--50:12. ACM , 201...

    2013

  4. [12]

    Maximizing Modularity is Hard , 2006

    Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert G \"o rke, Martin Hoefer, Zoran Nikoloski, and Dorothea Wagner. Maximizing Modularity is Hard , 2006. https://doi.org/10.48550/arXiv.physics/0608255 doi:10.48550/arXiv.physics/0608255

    2006 doi arXiv

  5. [13]

    Recent Advances in Graph Partitioning

    Aydin Bulu c , Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. Recent Advances in Graph Partitioning . In Algorithm Engineering , volume 9220, pages 117--158. Springer, 2016. https://doi.org/10.1007/978-3-319-49487-6_4 doi:10.1007/978-3-319-49487-6_4

    2016 doi

  6. [14]

    U mit C ataly \

    \"U mit C ataly \"u rek, Karen Devine, Marcelo Faraj, Lars Gottesb \"u ren, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Sebastian Schlag, Christian Schulz, Daniel Seemaier, et al. More Recent Advances in (Hyper)Graph Partitioning . ACM Computing Surveys , 55(12):253--253,...

    2023 doi

  7. [15]

    R-MAT: A Recursive Model for Graph Mining

    Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. R-MAT: A Recursive Model for Graph Mining . In 4th International Conference on Data Mining (ICDM) , pages 442--446. SIAM , 2004. https://doi.org/10.1137/1.9781611972740.43 doi:10.1137/1.9781611972740.43

    2004 doi

  8. [16]

    Bronstein, Ronald G

    Yuhan Chen, Haojie Ye, Sanketh Vedula, Alex M. Bronstein, Ronald G. Dreslinski, Trevor N. Mudge, and Nishil Talati. Demystifying Graph Sparsification Algorithms in Graph Properties Preservation . Proceedings of the VLDB Endowment , 17(3):427--440, 2023. https://doi.org/10.1477...

    2023

  9. [17]

    Partitioning Trillion Edge Graphs on Edge Devices , 2024

    Adil Chhabra, Florian Kurpicz, Christian Schulz, Dominik Schweisgut, and Daniel Seemaier. Partitioning Trillion Edge Graphs on Edge Devices , 2024. https://arxiv.org/abs/2410.07732 arXiv:2410.07732

    2024 arXiv

  10. [18]

    Davis, William W

    Timothy A. Davis, William W. Hager, Scott P. Kolodziej, and S. Nuri Yeralan. Algorithm 1003: Mongoose, a Graph Coarsening and Partitioning Library . ACM Transactions on Mathematical Software , 46(1), 2020. https://doi.org/10.1145/3337792 doi:10.1145/3337792

    2020 doi

  11. [19]

    Davis and Yifan Hu

    Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection . ACM Transactions on Mathematical Software , 38(1):1:1--1:25, 11 2011. https://doi.org/10.1145/2049662.2049663 doi:10.1145/2049662.2049663

    2011

  12. [20]

    Dolan and Jorge J

    Elizabeth D. Dolan and Jorge J. Mor \' e . Benchmarking Optimization Software with Performance Profiles . Mathematical Programming , 91(2):201--213, 2002. https://doi.org/10.1007/s101070100263 doi:10.1007/s101070100263

    2002 doi

  13. [21]

    Buffered Streaming Graph Partitioning

    Marcelo Fonseca Faraj and Christian Schulz. Buffered Streaming Graph Partitioning . ACM Journal of Experimental Algorithmics (JEA) , 27:1.10:1--1.10:26, 2022. https://doi.org/10.1145/3546911 doi:10.1145/3546911

    2022 doi

  14. [22]

    Faster Cut Sparsification of Weighted Graphs

    Sebastian Forster and Tijn de Vos. Faster Cut Sparsification of Weighted Graphs . Algorithmica , 85(4):929–964, 2022. https://doi.org/10.1007/s00453-022-01053-4 doi:10.1007/s00453-022-01053-4

    2022 doi

  15. [23]

    Resolution limit in community detection

    Santo Fortunato and Marc Barthélemy. Resolution limit in community detection. National Academy of Sciences , 104(1):36--41, 2007. https://doi.org/10.1073/pnas.0605965104 doi:10.1073/pnas.0605965104

    2007 doi

  16. [24]

    Communication-free Massively Distributed Graph Generation

    Daniel Funke, Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Moritz von Looz. Communication-free Massively Distributed Graph Generation . In 32nd International Parallel and Distributed Processing Symposium (IPDPS) , pages 336--347. IEEE Computer Society, 2...

    2018

  17. [25]

    Gilbert, Kamesh Madduri, Erik G

    Michael S. Gilbert, Kamesh Madduri, Erik G. Boman, and Siva Rajamanickam. Jet: Multilevel Graph Partitioning on Graphics Processing Units . SIAM Journal of Scientific Computing. , 46(5):700, 2024. https://doi.org/10.1137/23M1559129 doi:10.1137/23M1559129

    2024 doi

  18. [26]

    Scalable High-Quality Hypergraph Partitioning

    Lars Gottesb \" u ren, Tobias Heuer, Nikolai Maas, Peter Sanders, and Sebastian Schlag. Scalable High-Quality Hypergraph Partitioning . ACM Transactions on Algorithms , 20(1):9:1--9:54, 2024. https://doi.org/10.1145/3626527 doi:10.1145/3626527

    2024 doi

  19. [27]

    Scalable Shared-Memory Hypergraph Partitioning

    Lars Gottesbüren, Tobias Heuer, Peter Sanders, and Sebastian Schlag. Scalable Shared-Memory Hypergraph Partitioning . In 23st Workshop on Algorithm Engineering & Experiments (ALENEX) , 2021. https://doi.org/10.1137/1.9781611976472.2 doi:10.1137/1.9781611976472.2

    2021 doi

  20. [28]

    Deep Multilevel Graph Partitioning

    Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz, and Daniel Seemaier. Deep Multilevel Graph Partitioning . In 29th European Symposium on Algorithms (ESA) , pages 48:1--48:17, 2021. https://doi.org/10.4230/LIPIcs.ESA.2021.48 doi:10.4230/LIPIcs.ESA.2021.48

    2021 doi

  21. [29]

    Milad Rezaei Hajidehi, Sraavan Sridhar, and Margo I. Seltzer. CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics . Proceedings of the VLDB Endowment , 18(1):14--27, 2024. https://doi.org/10.14778/3696435.3696437 doi:10.14778/3696435.3696437

    2024

  22. [31]

    Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure

    Tobias Heuer and Sebastian Schlag. Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure . In 16th International Symposium on Experimental Algorithms (SEA) , pages 21:1--21:19, 06 2017. https://doi.org/10.4230/LIPIcs.SEA.2017.21 doi:10.4230...

    2017 doi

  23. [32]

    Faster Fully Compressed Pattern Matching by Recompression

    Artur Jez. Faster Fully Compressed Pattern Matching by Recompression . ACM Transactions on Algorithms (TALG) , 11(3):20:1--20:43, 2015. https://doi.org/10.1145/2631920 doi:10.1145/2631920

    2015 doi

  24. [33]

    Analysis of Multilevel Graph Partitioning

    George Karypis and Vipin Kumar. Analysis of Multilevel Graph Partitioning . In ACM/IEEE Conference on Supercomputing , pages 29--es. ACM, 1995. https://doi.org/10.1145/224170.224229 doi:10.1145/224170.224229

    1995

  25. [34]

    A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs

    George Karypis and Vipin Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs . SIAM Journal on Scientific Computing , 20(1):359--392, 1998. https://doi.org/10.1137/S1064827595287997 doi:10.1137/S1064827595287997

    1998 doi

  26. [35]

    Deterministic Parallel High-Quality Hypergraph Partitioning , 2025

    Robert Krause, Lars Gottesbüren, and Nikolai Maas. Deterministic Parallel High-Quality Hypergraph Partitioning , 2025. https://arxiv.org/abs/2504.12013 arXiv:2504.12013

    2025 arXiv

  27. [36]

    Multi-threaded Graph Partitioning

    Dominique Lasalle and George Karypis. Multi-threaded Graph Partitioning . In 27th IEEE International Symposium on Parallel and Distributed Processing ( IPDPS ) , pages 225--236, 2013. https://doi.org/10.1109/IPDPS.2013.50 doi:10.1109/IPDPS.2013.50

    2013 doi

  28. [37]

    Mostofa Ali Patwary, Nadathur Satish, Narayanan Sundaram, Pradeep Dubey, and George Karypis

    Dominique LaSalle, Md. Mostofa Ali Patwary, Nadathur Satish, Narayanan Sundaram, Pradeep Dubey, and George Karypis. Improving Graph Partitioning for Modern Graphs and Architectures . In 5th Workshop on Irregular Applications - Architectures and Algorithms ( IA3 ) , pages 14:1-...

    2015

  29. [38]

    Sampling from Large Graphs

    Jure Leskovec and Christos Faloutsos. Sampling from Large Graphs . In 12th International Conference on Knowledge Discovery and Data Mining (KDD) , pages 631--636. ACM , 2006. https://doi.org/10.1145/1150402.1150479 doi:10.1145/1150402.1150479

    2006

  30. [39]

    Graph Evolution: Densification and Shrinking Diameters

    Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph Evolution: Densification and Shrinking Diameters . ACM Transactions on Knowledge Discovery from Data , 1(1):2--es, 2007. https://doi.org/10.1145/1217299.1217301 doi:10.1145/1217299.1217301

    2007

  31. [40]

    SNAP Datasets: Stanford Large Network Dataset Collection

    Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford Large Network Dataset Collection . http://snap.stanford.edu/data, June 2014

    2014

  32. [41]

    Staudt, Michael Hamann, Henning Meyerhenke, and Dorothea Wagner

    Gerd Lindner, Christian L. Staudt, Michael Hamann, Henning Meyerhenke, and Dorothea Wagner. Structure-Preserving Sparsification of Social Networks . In IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) , pages 448--454. ACM, 2015. ht...

    2015

  33. [42]

    Parallel Unconstrained Local Search for Partitioning Irregular Graphs

    Nikolai Maas, Lars Gottesb \" u ren, and Daniel Seemaier. Parallel Unconstrained Local Search for Partitioning Irregular Graphs . In 26st Workshop on Algorithm Engineering & Experiments (ALENEX) , pages 32--45. SIAM , 2024. https://doi.org/10.1137/1.9781611977929.3 doi:10.1137...

    2024 doi

  34. [43]

    Partitioning Complex Networks via Size-Constrained Clustering

    Henning Meyerhenke, Peter Sanders, and Christian Schulz. Partitioning Complex Networks via Size-Constrained Clustering . In 13th International Symposium on Experimental Algorithms (SEA) , pages 351--363. Springer, 2014. https://doi.org/10.1007/978-3-319-07959-2_30 doi:10.1007/...

    2014 doi

  35. [44]

    Miller and Aric A

    Joel C. Miller and Aric A. Hagberg. Efficient Generation of Networks with Given Expected Degrees . In 8th International Workshop on Algorithms and Models for the Web Graph (WAW) , pages 115--126. Springer, 2011. https://doi.org/10.1007/978-3-642-21286-4_10 doi:10.1007/978-3-64...

    2011 doi

  36. [45]

    Mark E. J. Newman and Michelle Girvan. Finding and Evaluating Community Structure in Networks . Physical Review E , 69, 2 2004. https://doi.org/10.1103/PhysRevE.69.026113 doi:10.1103/PhysRevE.69.026113

    2004 doi

  37. [46]

    Intel Threading Building Blocks

    Chuck Pheatt. Intel Threading Building Blocks . Journal of Computing Sciences in Colleges , 23(4):298--298, 2008

    2008

  38. [47]

    Rossi and Nesreen K

    Ryan A. Rossi and Nesreen K. Ahmed. The Network Data Repository with Interactive Graph Analytics and Visualization . In 29th Conference on Artificial Intelligence ( AAAI ) , 2015. URL: http://networkrepository.com, https://doi.org/10.1609/AAAI.V29I1.9277 doi:10.1609/AAAI.V29I1.9277

    2015 doi

  39. [48]

    GPS: A Graph Processing System

    Semih Salihoglu and Jennifer Widom. GPS: A Graph Processing System . In Conference on Scientific and Statistical Database Management ( SSDBM ) , pages 22:1--22:12. ACM , 2013. https://doi.org/10.1145/2484838.2484843 doi:10.1145/2484838.2484843

    2013

  40. [49]

    Tera-Scale Multilevel Graph Partitioning , 2024

    Daniel Salwasser, Daniel Seemaier, Lars Gottesbüren, and Peter Sanders. Tera-Scale Multilevel Graph Partitioning , 2024. https://arxiv.org/abs/2410.19119 arXiv:2410.19119

    2024 arXiv

  41. [50]

    Slota, Kamesh Madduri, and Sivasankaran Rajamanickam

    George M. Slota, Kamesh Madduri, and Sivasankaran Rajamanickam. PuLP: Scalable Multi-Objective Multi-Constraint Partitioning for Small-World Networks . In IEEE International Conference on Big Data , pages 481--490. IEEE , 2014. https://doi.org/10.1109/BIGDATA.2014.7004265 doi:...

    2014

  42. [51]

    Spielman and Nikhil Srivastava

    Daniel A. Spielman and Nikhil Srivastava. Graph Sparsification by Effective Resistances . SIAM Journal on Computing , 40(6):1913--1926, 2011. https://doi.org/10.1137/080734029 doi:10.1137/080734029

    1913 doi

  43. [52]

    Staudt and Henning Meyerhenke

    Christian L. Staudt and Henning Meyerhenke. Engineering Parallel Algorithms for Community Detection in Massive Networks . IEEE Transactions on Parallel and Distributed Systems , 27(1):171--184, 2016. https://doi.org/10.1109/TPDS.2015.2390633 doi:10.1109/TPDS.2015.2390633

    2016

  44. [53]

    Tsourakakis, Christos Gkantsidis, Bozidar Radunovic, and Milan Vojnovic

    Charalampos E. Tsourakakis, Christos Gkantsidis, Bozidar Radunovic, and Milan Vojnovic. FENNEL: Streaming Graph Partitioning for Massive Scale Graphs . In 7th International Conference on Web Search and Data Mining ( WSDM ) , pages 333--342. ACM , 2014. https://doi.org/10.1145/...

    2014

  45. [54]

    Event Detection in Twitter

    Jianshu Weng and Bu - Sung Lee. Event Detection in Twitter . In 5th International Conference on Weblogs and Social Media . AAAI , 2011. https://doi.org/10.1609/icwsm.v5i1.14102 doi:10.1609/icwsm.v5i1.14102

    2011 doi

  46. [55]

    Lyu, and Irwin King

    Tom Chao Zhou, Hao Ma, Michael R. Lyu, and Irwin King. UserRec: A User Recommendation Framework in Social Tagging Systems . In 24th AAAI Conference on Artificial Intelligence , pages 1486--1491. AAAI , 2010. https://doi.org/10.1609/AAAI.V24I1.7524 doi:10.1609/AAAI.V24I1.7524

    2010 doi

Pith tools

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