Document Open Access Logo

Advanced Flow-Based Multilevel Hypergraph Partitioning

Authors Lars Gottesbüren, Michael Hamann, Sebastian Schlag, Dorothea Wagner

PDF
Thumbnail PDF

File

LIPIcs.SEA.2020.11.pdf
  • Filesize: 1.84 MB
  • 15 pages

Document Identifiers

Author Details

Lars Gottesbüren
  • Karlsruhe Institute of Technology, Germany
Michael Hamann
  • Karlsruhe Institute of Technology, Germany
Sebastian Schlag
  • Karlsruhe Institute of Technology, Germany
Dorothea Wagner
  • Karlsruhe Institute of Technology, Germany

Funding

This work was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under grants WA654/19-2, WA654/22-2, and SA933/11-1. The authors acknowledge support by the state of Baden-Württemberg through bwHPC.

Cite As Get BibTex

Lars Gottesbüren, Michael Hamann, Sebastian Schlag, and Dorothea Wagner. Advanced Flow-Based Multilevel Hypergraph Partitioning. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SEA.2020.11

Abstract

The balanced hypergraph partitioning problem is to partition a hypergraph into k disjoint blocks of bounded size such that the sum of the number of blocks connected by each hyperedge is minimized. We present an improvement to the flow-based refinement framework of KaHyPar-MF, the current state-of-the-art multilevel k-way hypergraph partitioning algorithm for high-quality solutions. Our improvement is based on the recently proposed HyperFlowCutter algorithm for computing bipartitions of unweighted hypergraphs by solving a sequence of incremental maximum flow problems. Since vertices and hyperedges are aggregated during the coarsening phase, refinement algorithms employed in the multilevel setting must be able to handle both weighted hyperedges and weighted vertices - even if the initial input hypergraph is unweighted. We therefore enhance HyperFlowCutter to handle weighted instances and propose a technique for computing maximum flows directly on weighted hypergraphs.
We compare the performance of two configurations of our new algorithm with KaHyPar-MF and seven other partitioning algorithms on a comprehensive benchmark set with instances from application areas such as VLSI design, scientific computing, and SAT solving. Our first configuration, KaHyPar-HFC, computes slightly better solutions than KaHyPar-MF using significantly less running time. The second configuration, KaHyPar-HFC*, computes solutions of significantly better quality and is still slightly faster than KaHyPar-MF. Furthermore, in terms of solution quality, both configurations also outperform all other competing partitioners.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Hypergraphs
  • Mathematics of computing → Network flows
  • Mathematics of computing → Graph algorithms
Keywords
  • Hypergraph Partitioning
  • Maximum Flows
  • Refinement

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993. Google Scholar
  2. Yaroslav Akhremtsev, Tobias Heuer, Sebastian Schlag, and Peter Sanders. Engineering a direct k-way Hypergraph Partitioning Algorithm. In Proceedings of the 19th Meeting on Algorithm Engineering and Experiments (ALENEX'17), pages 28-42. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974768.3.
  3. Charles J. Alpert. The ISPD98 Circuit Benchmark Suite. In Proceedings of the 1998 International Symposium on Physical Design, pages 80-85, 1998. URL: https://doi.org/10.1145/274535.274546.
  4. Charles J. Alpert, Jen-Hsin Huang, and Andrew B. Kahng. Multilevel Circuit Partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 17(8):655-667, August 1998. URL: https://doi.org/10.1109/43.712098.
  5. Charles J. Alpert and Andrew B. Kahng. Recent Directions in Netlist Partitioning: A Survey. Integration: The VLSI Journal, 19(1-2):1-81, 1995. URL: https://doi.org/10.1016/0167-9260(95)00008-4.
  6. Anton Belov, Daniel Diepold, Marijn JH Heule, and Matti Järvisalo. The SAT Competition 2014, 2014. URL: http://www.satcompetition.org/2014/.
  7. Charles-Edmond Bichot and Patrick Siarry, editors. Graph Partitioning. Wiley, 2011. URL: https://doi.org/10.1002/9781118601181.
  8. Paul Bonsma. Most balanced minimum cuts. Discrete Applied Mathematics, 158(4):261-276, 2010. URL: https://doi.org/10.1016/j.dam.2009.09.010.
  9. Umit Catalyurek and Cevdet Aykanat. Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication. IEEE Transactions on Parallel and Distributed Systems, 10(7):673-693, 1999. URL: https://doi.org/10.1109/71.780863.
  10. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, second edition, 2001. Google Scholar
  11. Nicholas J. Cox. Stata tip 96: Cube roots. The Stata Journal, 11(1):149-154, 2011. URL: https://doi.org/10.1177/1536867X1101100112.
  12. Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software, 38(1), 2011. URL: https://doi.org/10.1145/2049662.2049663.
  13. Karen Devine, Erik Boman, Robert Heaphy, Rob Bisseling, and Umit Catalyurek. Parallel Hypergraph Partitioning for Scientific Computing. In 20th International Parallel and Distributed Processing Symposium (IPDPS'06). IEEE Computer Society, 2006. URL: https://doi.org/10.1109/IPDPS.2006.1639359.
  14. Yefim Dinitz. Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation. Soviet Mathematics-Doklady, 11(5):1277-1280, September 1970. Google Scholar
  15. Elizabeth D. Dolan and Jorge J. Moré. Benchmarking optimization software with performance profiles. Mathematical Programming, 91(2):201-213, 2002. URL: https://doi.org/10.1007/s101070100263.
  16. Jack Edmonds and Richard M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. Journal of the ACM, 19(2):248-264, April 1972. URL: https://doi.org/10.1145/321694.321699.
  17. Charles M. Fiduccia and Robert M. Mattheyses. A linear-time heuristic for improving network partitions. In Proceedings of the 19th ACM/IEEE Conference on Design Automation, pages 175-181, 1982. URL: https://doi.org/10.1145/800263.809204.
  18. Lester R. Ford, Jr. and Delbert R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399-404, 1956. Google Scholar
  19. Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Pushmeet Kohli, Robert E. Tarjan, and Renato F. Werneck. Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA'15), volume 9294 of Lecture Notes in Computer Science, pages 619-630. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_52.
  20. Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Robert E. Tarjan, and Renato F. Werneck. Maximum Flows by Incremental Breadth-First Search. In Proceedings of the 19th Annual European Symposium on Algorithms (ESA'11), volume 6942 of Lecture Notes in Computer Science, pages 457-468. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-23719-5_39.
  21. Lars Gottesbüren, Michael Hamann, Sebastian Schlag, and Dorothea Wagner. Advanced flow-based multilevel hypergraph partitioning. arXiv preprint arXiv:2003.12110, 2020. Google Scholar
  22. Lars Gottesbüren, Michael Hamann, and Dorothea Wagner. Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA'19), Leibniz International Proceedings in Informatics, pages 52:1-52:17, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.52.
  23. Tobias Heuer and Sebastian Schlag. Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure. In Costas S. Iliopoulos, Solon P. Pissis, Simon J. Puglisi, and Rajeev Raman, editors, Proceedings of the 16th International Symposium on Experimental Algorithms (SEA'17), volume 75 of Leibniz International Proceedings in Informatics, 2017. URL: https://doi.org/10.4230/LIPIcs.SEA.2017.21.
  24. Tobias Heuer, Sebastian Schlag, and Peter Sanders. Network Flow-Based Refinement for Multilevel Hypergraph Partitioning. ACM Journal of Experimental Algorithmics, 24(2):2.3:1-2.3:36, September 2019. URL: https://doi.org/10.1145/3329872.
  25. Igor Kabiljo, Brian Karrer, Mayank Pundir, Sergey Pupyrev, Alon Shalita, Yaroslav Akhremtsev, and Alessandro Presta. Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner. Proceedings of the VLDB Endowment, 10(11):1418-1429, 2017. URL: https://doi.org/10.14778/3137628.3137650.
  26. George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. Multilevel Hypergraph Partitioning: Applications in VLSI Domain. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7(1):69-79, 1999. URL: https://doi.org/10.1109/92.748202.
  27. George Karypis and Vipin Kumar. Multilevel K-Way Hypergraph Partitioning. In Proceedings of the 36th Annual ACM/IEEE Design Automation Conference, 1999. URL: https://doi.org/10.1145/309847.309954.
  28. Brian W. Kernighan and Shen Lin. An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Technical Journal, 49(2):291-307, February 1970. URL: https://doi.org/10.1002/j.1538-7305.1970.tb01770.x.
  29. Renaud Lambiotte, Martin Rosvall, and Ingo Scholtes. From networks to optimal higher-order models of complex systems. Nature Physics, 15(4):313-320, 2019. URL: https://doi.org/10.1038/s41567-019-0459-y.
  30. Eugene L. Lawler. Cutsets and Partitions of hypergraphs. Networks, 3:275-285, 1973. URL: https://doi.org/10.1002/net.3230030306.
  31. Thomas Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley, 1990. Google Scholar
  32. Huiqun Liu and D.F. Wong. Network-Flow-Based Multiway Partitioning with Area and Pin Constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 17(1):50-59, 1998. URL: https://doi.org/10.1109/43.673632.
  33. Christian Mayer, Ruben Mayer, Sukanya Bhowmik, Lukas Epple, and Kurt Rothermel. HYPE: Massive Hypergraph Partitioning With Neighborhood Expansion. In IEEE International Conference on Big Data, pages 458-467. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/BigData.2018.8621968.
  34. Viswanath Nagarajan, Charles J. Alpert, Cliff Sze, Zhuo Li, and Yaoguang Wei. The DAC 2012 Routability-driven Placement Contest and Benchmark Suite. In Proceedings of the 49th Annual Design Automation Conference, 2012. URL: https://doi.org/10.1145/2228360.2228500.
  35. David A. Papa and Igor L. Markov. Hypergraph Partitioning and Clustering. In Teofilo F. Gonzalez, editor, Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall/CRC, 2007. URL: https://doi.org/10.1201/9781420010749.
  36. Jean-Claude Picard and Maurice Queyranne. On the Structure of All Minimum Cuts in a Network and Applications. Mathematical Programming, Series A, 22(1):121, December 1982. URL: https://doi.org/10.1007/BF01581031.
  37. Joachim Pistorius and Michel Minoux. An Improved Direct Labeling Method for the Max–Flow Min–Cut Computation in Large Hypergraphs and Applications. International Transactions in Operational Research, 10(1):1-11, 2003. URL: https://doi.org/10.1111/1475-3995.00389.
  38. Peter Sanders and Christian Schulz. Engineering Multilevel Graph Partitioning Algorithms. In Proceedings of the 19th Annual European Symposium on Algorithms (ESA'11), volume 6942 of Lecture Notes in Computer Science, pages 469-480. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-23719-5_40.
  39. Sebastian Schlag. High-Quality Hypergraph Partitioning. PhD thesis, Karlsruhe Institute of Technology, 2020. Google Scholar
  40. Sebastian Schlag, Vitali Henne, Tobias Heuer, Henning Meyerhenke, Peter Sanders, and Christian Schulz. k-way Hypergraph Partitioning via n-Level Recursive Bisection. In Proceedings of the 18th Meeting on Algorithm Engineering and Experiments (ALENEX'16), pages 53-67. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974317.5.
  41. Ruslan Shaydulin, Jie Chen, and Ilya Safro. Relaxation-Based Coarsening for Multilevel Hypergraph Partitioning. Multiscale Modeling and Simulation, 17(1):482-506, 2019. URL: https://doi.org/10.1137/17M1152735.
  42. Aleksandar Trifunovic and William J. Knottenbelt. Parallel Multilevel Algorithms for Hypergraph Partitioning. Journal of Parallel and Distributed Computing, 68(5):563-581, 2008. URL: https://doi.org/10.1016/j.jpdc.2007.11.002.
  43. John W. Tukey. Box-and-whisker plots. Exploratory data analysis, pages 39-43, 1977. Google Scholar
  44. Bora Uçar and Cevdet Aykanat. Encapsulating multiple communication-cost metrics in partitioning sparse rectangular matrices for parallel matrix-vector multiplies. SIAM Journal on Scientific Computing, 25(6):1837-1859, 2004. URL: https://doi.org/10.1137/S1064827502410463.
  45. Brendan Vastenhouw and Rob Bisseling. A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication. SIAM Review, 47(1):67-95, 2005. URL: https://doi.org/10.1137/S0036144502409019.
  46. Chenzi Zhang, Fan Wei, Qin Liu, Zhihao Gavin Tang, and Zhenguo Li. Graph Edge Partitioning via Neighborhood Heuristic. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 605-614. ACM Press, 2017. URL: https://doi.org/10.1145/3097983.3098033.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact