pith. sign in

arxiv: 2406.14111 · v2 · submitted 2024-06-20 · 💻 cs.DS · cs.LG

Expander Hierarchies for Normalized Cuts on Graphs

Kathrin Hanauer , Monika Henzinger , Robin M\"unk , Harald R\"acke , Maximilian V\"otsch This is my paper

Pith reviewed 2026-05-24 00:35 UTC · model grok-4.3

classification 💻 cs.DS cs.LG
keywords expander decompositionnormalized cutgraph clusteringhierarchical decompositionpractical graph algorithmsgraph partitioning
0
0 comments X

The pith

A practical algorithm now computes expander decompositions to improve normalized cut clustering quality.

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

The paper introduces the first algorithm for expander decompositions and hierarchies that runs efficiently enough for real-world use. It deploys this procedure as the central engine inside a new solver for the normalized cut objective. Experiments across large citation networks, email graphs, social networks, and web graphs show the resulting clusters have markedly higher quality than those from prior solvers while runtimes stay competitive. The work converts a theoretical graph decomposition technique into a concrete clustering tool.

Core claim

The authors claim that their expander-decomposition procedure and the hierarchies it produces can be computed in practical time and, when used as the core component of a normalized-cut solver, deliver solutions of substantially higher quality than existing methods on citation, e-mail, social, and web graphs while remaining competitive in running time.

What carries the argument

The expander decomposition procedure together with its hierarchy, which recursively partitions the graph into well-expanding pieces and serves as the algorithmic engine for the normalized-cut solver.

If this is right

  • The expander-based solver produces higher-quality normalized cuts than prior methods on citation networks, email graphs, social networks, and web graphs.
  • Running times remain competitive with state-of-the-art normalized-cut solvers on the same large graphs.
  • Expander hierarchies can be incorporated directly into clustering pipelines without sacrificing speed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same decomposition hierarchy may accelerate solvers for other cut-based objectives once the practical procedure is available.
  • If the observed efficiency holds, the technique could be applied to streaming or dynamic graph settings where full recomputation is costly.

Load-bearing premise

The new expander-decomposition procedure runs in practical time on the tested graph classes without hidden constants that would dominate on other inputs or at larger scales.

What would settle it

Measure the running time of the algorithm on a family of graphs from the same domains whose sizes increase by successive factors of two and check whether the observed times remain within a small constant factor of the times reported for the original test set.

Figures

Figures reproduced from arXiv: 2406.14111 by Harald R\"acke, Kathrin Hanauer, Maximilian V\"otsch, Monika Henzinger, Robin M\"unk.

Figure 1
Figure 1. Figure 1: Relative improvement over Graclus (y-axis) vs. the ratio of the maximum degree and the median degree (x￾axis). The value on the x-axis is larger if the graphs exhibit a distribution with large outliers. Note the negative trend, except for the outlier towards the right corresponding to instance SN7. by either reducing the number of cut edges or making the partition more balanced. For details see the full ve… view at source ↗
Figure 3
Figure 3. Figure 3: Geometric mean of the cut value 𝜽 across all graphs for each 𝒌 for XCutmean, Graclus, METIS, and KaHiP. improvement in 𝜃 for values of 𝜌 below 10−4 . At the same time, the running time increases inversely with 𝜌 as extra iterations are needed to converge, which is shown by the vertical arrangement of the dots in [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 2
Figure 2. Figure 2: Running time vs. normalized cut for different [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: Relative improvement over Graclus (y-axis) vs. the average degree divided by the median degree (x-axis). Larger x-values signify that the graph exhibits a skewed, power-law￾like degree distribution. Note the negative trend, except for the outlier towards the right corresponding to instance SN7. the other solvers in the comparison due to it producing 5–30 times greater 𝜃 on the citation network (CN) instanc… view at source ↗
Figure 5
Figure 5. Figure 5: Percentage deviation of the returned normalized cut value relative to [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
read the original abstract

Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility by incorporating it as the core component in a novel solver for the normalized cut graph clustering objective. Our extensive experiments on a variety of large graphs show that our expander-based algorithm outperforms state-of-the-art solvers for normalized cut with respect to solution quality by a large margin on a variety of graph classes such as citation, e-mail, and social networks or web graphs while remaining competitive in running time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces the first practically efficient algorithm for computing expander decompositions and expander hierarchies on graphs. It incorporates this procedure as the core component of a new solver for the normalized-cut graph clustering objective. The central claim, supported by experiments on large real-world graphs (citation, email, social, and web networks), is that the resulting solver achieves substantially better solution quality than existing state-of-the-art normalized-cut algorithms while remaining competitive in running time.

Significance. If the practical efficiency and quality claims hold under scrutiny, the work would meaningfully narrow the gap between recent theoretical advances on expander decompositions and deployable graph-clustering tools. The explicit construction of expander hierarchies for normalized cut is a novel algorithmic contribution that could influence both theory and practice in spectral graph algorithms.

major comments (2)
  1. [§ Experiments] § Experiments (and associated tables/figures): the abstract and high-level description assert that the expander-based solver “outperforms state-of-the-art solvers … by a large margin” while “remaining competitive in running time,” yet no information is supplied on implementation language, parameter settings for the expander decomposition, statistical testing across runs, or precise baseline implementations and their parameter choices. Without these details the central empirical claim cannot be evaluated or reproduced.
  2. [§ Algorithm] § Algorithm / Runtime Analysis: the paper claims the new expander-decomposition procedure is “practically efficient” and overcomes “large hidden factors in their asymptotic running times,” but supplies neither an explicit asymptotic bound with concrete constants nor scaling plots that isolate recursion depth and decomposition overhead on the tested graph classes. If these factors grow with size or density, the reported competitiveness would not generalize.
minor comments (2)
  1. [Preliminaries] Notation for the expander hierarchy levels and the normalized-cut objective should be introduced once in a dedicated preliminaries section and used consistently thereafter.
  2. [Figures] Figure captions for runtime and quality plots should explicitly state the machine, compiler, and number of independent runs used to generate each data point.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback. We address the two major comments below and will revise the manuscript to enhance reproducibility and support for the practical claims.

read point-by-point responses

  1. Referee: [§ Experiments] § Experiments (and associated tables/figures): the abstract and high-level description assert that the expander-based solver “outperforms state-of-the-art solvers … by a large margin” while “remaining competitive in running time,” yet no information is supplied on implementation language, parameter settings for the expander decomposition, statistical testing across runs, or precise baseline implementations and their parameter choices. Without these details the central empirical claim cannot be evaluated or reproduced.

    Authors: We agree these details are required for proper evaluation and reproducibility. The revised manuscript will include a new subsection (or expanded experimental setup) specifying the implementation language, all parameter values and tuning procedures for the expander decomposition, any statistical testing performed across runs, and complete descriptions of the baseline implementations including their parameter settings and code sources. revision: yes

  2. Referee: [§ Algorithm] § Algorithm / Runtime Analysis: the paper claims the new expander-decomposition procedure is “practically efficient” and overcomes “large hidden factors in their asymptotic running times,” but supplies neither an explicit asymptotic bound with concrete constants nor scaling plots that isolate recursion depth and decomposition overhead on the tested graph classes. If these factors grow with size or density, the reported competitiveness would not generalize.

    Authors: The manuscript prioritizes empirical demonstration of practical efficiency over a new theoretical runtime analysis with explicit constants. We will add scaling plots in the experiments section that isolate recursion depth and per-level decomposition overhead on the evaluated graph classes to better substantiate the claims of practical competitiveness. An explicit asymptotic bound with concrete constants is not provided, as deriving one would require additional theoretical analysis beyond the scope of the current practical contribution. revision: partial

Circularity Check

0 steps flagged

No circularity: algorithmic construction and empirical validation are independent of inputs

full rationale

The paper presents a new practical algorithm for expander decompositions and hierarchies, then evaluates its use as a core component in a normalized-cut solver via direct experiments on real-world graphs. No equations, predictions, or first-principles derivations appear that reduce by construction to fitted parameters, self-citations, or ansatzes; the central claims rest on implementation and comparative runtime/quality measurements rather than any self-referential loop. Self-citations, if present, are not load-bearing for any claimed derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated.

pith-pipeline@v0.9.0 · 5667 in / 1029 out tokens · 17438 ms · 2026-05-24T00:35:21.333492+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

48 extracted references · 48 canonical work pages · 1 internal anchor

  1. [1]

    Isaac Arvestad. 2022. Near-linear time expander decomposition in practice

    work page 2022

  2. [2]

    Bas Fagginger Auer and Rob H Bisseling. 2012. Graph coarsening and clustering on the GPU. Graph Partitioning and Graph Clustering 588, 223 (2012), 2

    work page 2012

  3. [3]

    Charles-Edmond Bichot. 2010. Co-clustering Documents and Words by Mini- mizing the Normalized Cut Objective Function. J. Math. Model. Algorithms 9, 2 (2010), 131–147. https://doi.org/10.1007/S10852-010-9126-0

    work page doi:10.1007/s10852-010-9126-0 2010

  4. [4]

    Deng Cai, Zheng Shao, Xiaofei He, Xifeng Yan, and Jiawei Han. 2005. Mining hidden community in heterogeneous social networks. In Proceedings of the 3rd international workshop on Link discovery, LinkKDD 2005, Chicago, Illinois, USA, August 21-25, 2005, Jafar Adibi, Marko Grobelnik, Dunja Mladenic, and Patrick Pantel (Eds.). ACM, 58–65. https://doi.org/10.1...

    work page doi:10.1145/1134271.1134280 2005

  5. [5]

    Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, and Hengjie Zhang. 2021. Near-optimal Distributed Triangle Enumeration via Expander Decompositions. J. ACM 68, 3 (2021), 21:1–21:36. https://doi.org/10.1145/3446330

    work page doi:10.1145/3446330 2021

  6. [6]

    Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva

    Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. 2022. Maximum Flow and Minimum-Cost Flow in Almost- Linear Time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 . IEEE, 612–623. https://doi.org/10.1109/FOCS54457.2022.00064

    work page doi:10.1109/focs54457.2022.00064 2022

  7. [7]

    Xiaojun Chen, Feiping Nie, Joshua Zhexue Huang, and Min Yang. 2017. Scal- able Normalized Cut with Improved Spectral Rotation. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017 , Carles Sierra (Ed.). ijcai.org, 1518–1524. https://doi.org/10.24963/IJCAI.2017/210

    work page doi:10.24963/ijcai.2017/210 2017

  8. [8]

    Amir Daneshgar and Ramin Javadi. 2012. On the complexity of isoperimetric problems on trees. Discret. Appl. Math. 160, 1-2 (2012), 116–131. https://doi.org/ 10.1016/J.DAM.2011.08.015

    work page doi:10.1016/j.dam.2011.08.015 2012

  9. [9]

    Timothy A Davis and Yifan Hu. 2011. The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software (TOMS) 38, 1 (2011), 1–25

    work page 2011

  10. [10]

    Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. 2007. Weighted graph cuts without eigenvectors a multilevel approach. IEEE transactions on pattern analysis and machine intelligence 29, 11 (2007), 1944–1957

    work page 2007

  11. [11]

    Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan. 2021. The expander hierarchy and its applications to dynamic graph algorithms. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) . SIAM, 2212–2228

    work page 2021

  12. [12]

    Bernhard Haeupler, Harald Räcke, and Mohsen Ghaffari. 2022. Hop-constrained expander decompositions, oblivious routing, and distributed universal optimal- ity. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. 1325–1338

    work page 2022

  13. [13]

    Kathrin Hanauer, Monika Henzinger, Robin Münk, Harald Räcke, and Maxi- milian Vötsch. 2024. Expander Hierarchies for Normalized Cuts on Graphs. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discov- ery and Data Mining, KDD 2023, August 25–29, 2024, Barcelona, Spain . ACM. https://doi.org/10.1145/3637528.3671978 To appear

    work page doi:10.1145/3637528.3671978 2024

  14. [14]

    Kathrin Hanauer, Monika Henzinger, Robin Münk, Harald Räcke, and Maximilian Vötsch. 2024. XCut/XCut v1.0.0. https://doi.org/10.5281/zenodo.12108189. https: //doi.org/10.5281/zenodo.12108189

    work page doi:10.5281/zenodo.12108189 2024

  15. [15]

    Bruce Hendrickson and Robert W. Leland. 1995. A Multi-Level Algorithm For Partitioning Graphs. In Proceedings Supercomputing ’95, San Diego, CA, USA, December 4-8, 1995 , Sidney Karin (Ed.). ACM, 28. https://doi.org/10.1145/224170. 224228

    work page doi:10.1145/224170 1995

  16. [16]

    Monika Henzinger, Stefan Neumann, Harald Räcke, and Stefan Schmid. 2023. Dynamic Maintenance of Monotone Dynamic Programs and Applications. In 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-9, 2023, Hamburg, Germany (LIPIcs, Vol. 254) , Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté...

    work page 2023

  17. [17]

    Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg, and Zihang Wu. 2023. Maintaining expander decompositions via sparse cuts. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) . SIAM, 48–69

    work page 2023

  18. [18]

    George Karypis and Vipin Kumar. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing 20, 1 (1998), 359–392

    work page 1998

  19. [19]

    Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford

    Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. 2014. An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. In Proceedings of the Twenty- Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014 , Chandra Chekuri (Ed.)....

    work page doi:10.1137/1.9781611973402.16 2014

  20. [20]

    Laurent and P

    B. Laurent and P. Massart. 2000. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics 28, 5 (2000), 1302 – 1338. https: //doi.org/10.1214/aos/1015957395

    work page doi:10.1214/aos/1015957395 2000

  21. [21]

    Jason Li. 2021. Deterministic mincut in almost-linear time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing . 384–395

    work page 2021

  22. [22]

    Jia Li, Honglei Zhang, Zhichao Han, Yu Rong, Hong Cheng, and Junzhou Huang

    work page

  23. [23]

    In WWW ’20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, Yennun Huang, Irwin King, Tie-Yan Liu, and Maarten van Steen (Eds.)

    Adversarial Attack on Community Detection by Hiding Individuals. In WWW ’20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, Yennun Huang, Irwin King, Tie-Yan Liu, and Maarten van Steen (Eds.). ACM / IW3C2, 917–927. https://doi.org/10.1145/3366423.3380171

    work page doi:10.1145/3366423.3380171 2020

  24. [24]

    Bojan Mohar. 1989. Isoperimetric numbers of graphs. J. Comb. Theory, Ser. B 47, 3 (1989), 274–291. https://doi.org/10.1016/0095-8956(89)90029-4

    work page doi:10.1016/0095-8956(89)90029-4 1989

  25. [25]

    Danupon Nanongkai and Thatchaphol Saranurak. 2017. Dynamic spanning forest with worst-case update time: adaptive, las vegas, and o (n1/2-𝜀)-time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing . 1122–1129

    work page 2017

  26. [26]

    Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. 2017. Dynamic minimum spanning forest with subpolynomial worst-case update time. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) . IEEE, 950–961

    work page 2017

  27. [27]

    Maxim Naumov and Timothy Moon. 2016. Parallel spectral graph partitioning. NVIDIA, Santa Clara, CA, USA, Tech. Rep., NVR-2016-001 (2016)

    work page 2016

  28. [28]

    Ng, Michael I

    Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. 2001. On Spectral Clustering: Analysis and an algorithm. In Advances in Neural Informa- tion Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001, December 3-8, 2001, Vancouver, British Columbia, Canada], Thomas G. Dietterich, Suzanna Becker, and Zoubin Ghahramani (...

    work page 2001

  29. [29]

    Feiping Nie, Jitao Lu, Danyang Wu, Rong Wang, and Xuelong Li. 2024. A Novel Normalized-Cut Solver With Nearest Neighbor Hierarchical Initialization. IEEE Trans. Pattern Anal. Mach. Intell. 46, 1 (2024), 659–666. https://doi.org/10.1109/ TPAMI.2023.3279394

    work page arXiv 2024

  30. [30]

    Vitaly Osipov and Peter Sanders. 2010. n-Level graph partitioning. InAlgorithms– ESA 2010: 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I 18 . Springer, 278–289

    work page 2010

  31. [31]

    Richard Peng, He Sun, and Luca Zanetti. 2017. Partitioning Well-Clustered Graphs: Spectral Clustering Works! SIAM J. Comput. 46, 2 (2017), 710–743. https://doi.org/10.1137/15M1047209

    work page doi:10.1137/15m1047209 2017

  32. [32]

    Rossi and Nesreen K

    Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Reposi- tory with Interactive Graph Analytics and Visualization. In AAAI. https: //networkrepository.com

    work page 2015

  33. [33]

    Tapasmini Sahoo and Kunal Kumar Das. 2023. Brain Tumor Localization Using N-Cut. International Journal of Online & Biomedical Engineering 19, 15 (2023)

    work page 2023

  34. [34]

    Peter Sanders and Christian Schulz. 2012. High quality graph partitioning.Graph Partitioning and Graph Clustering 588, 1 (2012), 1–17

    work page 2012

  35. [35]

    Thatchaphol Saranurak and Di Wang. 2019. Expander Decomposition and Pruning: Faster, Stronger, and Simpler. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 , Timothy M. Chan (Ed.). SIAM, 2616–2635. https://doi. org/10.1137/1.9781611975482.162

    work page doi:10.1137/1.9781611975482.162 2019

  36. [36]

    Jianbo Shi and Jitendra Malik. 2000. Normalized Cuts and Image Segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22, 8 (2000), 888–905. https://doi.org/10. 1109/34.868688

    work page 2000

  37. [37]

    Daniel A Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Pro- ceedings of the thirty-sixth annual ACM symposium on Theory of computing . 81–90

    work page 2004

  38. [38]

    Chris Walshaw, Mark Cross, and Martin G. Everett. 1995. A Localized Algorithm for Optimizing Unstructured Mesh Partitions. Int. J. High Perform. Comput. Appl. 9, 4 (1995), 280–295. https://doi.org/10.1177/109434209500900403

    work page doi:10.1177/109434209500900403 1995

  39. [39]

    Crowley, and Dominique Vaufreydaz

    Yangtao Wang, Xi Shen, Yuan Yuan, Yuming Du, Maomao Li, Shell Xu Hu, James L. Crowley, and Dominique Vaufreydaz. 2023. TokenCut: Segmenting Objects in Images and Videos With Self-Supervised Transformer and Normalized Cut. IEEE Transactions on Pattern Analysis and Machine Intelligence 45, 12 (2023), 15790–15801. https://doi.org/10.1109/TPAMI.2023.3305122

    work page doi:10.1109/tpami.2023.3305122 2023

  40. [40]

    Christian Wulff-Nilsen. 2017. Fully-dynamic minimum spanning forest with improved worst-case update time. InProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing . 1130–1143

    work page 2017

  41. [41]

    Xing and Richard M

    Eric P. Xing and Richard M. Karp. 2001. CLIFF: clustering of high-dimensional microarray data via iterative feature filtering using normalized cuts. In Proceed- ings of the Ninth International Conference on Intelligent Systems for Molecular Biology, July 21-25, 2001, Copenhagen, Denmark . 306–315

    work page 2001

  42. [42]

    Yu and Jianbo Shi

    Stella X. Yu and Jianbo Shi. 2003. Multiclass Spectral Clustering. In 9th IEEE International Conference on Computer Vision (ICCV 2003), 14-17 October 2003, Nice, France. IEEE Computer Society, 313–319. https://doi.org/10.1109/ICCV.2003. 1238361

    work page doi:10.1109/iccv.2003 2003

  43. [43]

    Jin Zhang, Lei Xie, Wei Feng, and Yanning Zhang. 2009. A Subword Normalized Cut Approach to Automatic Story Segmentation of Chinese Broadcast News. In Information Retrieval Technology, 5th Asia Information Retrieval Symposium, AIRS 2009, Sapporo, Japan, October 21-23, 2009. Proceedings (Lecture Notes in Computer Science, Vol. 5839) , Gary Geunbae Lee, Daw...

    work page doi:10.1007/978-3-642-04769-5_12 2009

  44. [44]

    Zhiqiang Zhao, Yongyu Wang, and Zhuo Feng. 2018. Nearly-linear time spectral graph reduction for scalable graph partitioning and data visualization. arXiv preprint arXiv:1812.08942 (2018). A THEORETICAL ANALYSIS OF THE EXPANDER DECOMPOSITION The key ingredient for the analysis is to show that it is very unlikely that the cut procedure does not return a cu...

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  45. [45]

    that 𝑣 is an arbitrary vector of length ℓ = ∥𝑣 ∥

    Due to the rotation symmetry of the Gaussian distribution we can assume wlog. that 𝑣 is an arbitrary vector of length ℓ = ∥𝑣 ∥. In particular we can assume that 𝑣1 = √ ℓ and all other entries are 0. Then E[(𝑣 ⊤𝑟 )2] = E[ℓ · N (0, 1/𝑑)2] = ℓ/𝑑 ·E[N (0, 1)2] = ℓ/𝑑

    work page

  46. [46]

    Since the distribution of (𝑣 ⊤𝑟 )2 is ℓ 𝑑 · N (0, 1)2 the statement follows

    Using Lemma 1 from Laurent and Massart [ 20] one gets that for a 𝜒-squared distributed variable 𝑋 ∼ N (0, 1)2 fulfills Pr[𝑋 ≥ 1+2√𝑥 +2𝑥] ≤ 𝑒 −𝑥 , which givesPr[𝑋 ≥ 5𝑥] ≤ 𝑒 −𝑥 for 𝑥 ≥ 1. Since the distribution of (𝑣 ⊤𝑟 )2 is ℓ 𝑑 · N (0, 1)2 the statement follows

    work page

  47. [47]

    dynamic programming strategy for a subset of instances for 𝒌 = 32 and 𝝆 = 0.0001

    Using Property 2 with 𝛼 = 15 ln 𝑛 gives that the probability that a vector is overstretched by a factor more than 𝛼 is at most Kathrin Hanauer, Monika Henzinger, Robin Münk, Harald Räcke, and Maximilian Vötsch 10 1 100 101 0 2 4 6 8 10Running Time [s] Graph ID CL1 CL2 CN1 CN3 CN8 FE1 FE2 NS1 NS2 RD1 RN4 TM1 TM2 TM3 TM4 TM5 TM7 US1 Experiment T ype DP gree...

    work page

  48. [48]

    coarsening

    Let 𝑥 𝑗 denote the vector where the𝑖-th entry is 𝑣𝑖 𝑗. Then 𝑍 :=Í 𝑖 (𝑣 ⊤ 𝑖 𝑟 )2 = Í 𝑖 Í 𝑗 (𝑣𝑖 𝑗𝑟 𝑗 )2 = Í 𝑗 Í 𝑖 (𝑥 𝑗𝑖 𝑟 𝑗 )2 = Í 𝑗 ∥𝑥 𝑗 ∥2 2 · (𝑟 𝑗 )2. Let ℓmax denote the largest length of an 𝑥 𝑗 -vector. We classifiy the𝑥 𝑗 - vectors whose length fall in the range (ℓmax/𝑛, ℓmax] into log2 𝑛 classes so that the length of vectors in the same class differs...

    work page 2024