Document Open Access Logo

Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure

Authors Tobias Heuer, Sebastian Schlag

PDF
Thumbnail PDF

File

LIPIcs.SEA.2017.21.pdf
  • Filesize: 6.74 MB
  • 19 pages

Document Identifiers

Author Details

Tobias Heuer
Sebastian Schlag

Cite As Get BibTex

Tobias Heuer and Sebastian Schlag. Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SEA.2017.21

Abstract

We present an improved coarsening process for multilevel hypergraph partitioning that incorporates global information about the community structure. Community detection is performed via modularity maximization on a bipartite graph representation. The approach is made suitable for different classes of hypergraphs by defining weights for the graph edges that express structural properties of the hypergraph. We integrate our approach into a leading multilevel hypergraph partitioner with strong local search algorithms and perform extensive experiments on a large benchmark set of hypergraphs stemming from application areas such as VLSI design, SAT solving, and scientific computing. Our results indicate that respecting community structure during coarsening not only significantly improves the solutions found by the initial partitioning algorithm, but also consistently improves overall solution quality.

Subject Classification

Keywords
  • multilevel hypergraph partitioning
  • coarsening algorithms
  • community detection

Metrics

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

References

  1. Y. Akhremtsev, T. Heuer, P. Sanders, and S. Schlag. Engineering a direct k-way hypergraph partitioning algorithm. In 19th Workshop on Algorithm Engineering and Experiments, (ALENEX), pages 28-42, 2017. Google Scholar
  2. Rodrigo Aldecoa and Ignacio Marin. Deciphering Network Community Structure by Surprise. PLOS ONE, 6(9):1-8, 09 2011. Google Scholar
  3. F. A. Aloul, I. L. Markov, and K. A. Sakallah. MINCE: A Static Global Variable-Ordering Heuristic for SAT Search and BDD Manipulation. Journal of Universal Computer Science, 10(12):1562-1596, 2004. Google Scholar
  4. C. J. Alpert. The ISPD98 Circuit Benchmark Suite. In Proceedings of the 1998 International Symposium on Physical Design, pages 80-85. ACM, 1998. Google Scholar
  5. C. J. Alpert, J.-H. Huang, and A. B. Kahng. Multilevel Circuit Partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 17(8):655-667, 1998. Google Scholar
  6. C. J. Alpert and A. B. Kahng. Recent Directions in Netlist Partitioning: a Survey. Integration, the VLSI Journal, 19(1-2):1 - 81, 1995. Google Scholar
  7. C. Ansótegui, J. Giráldez-Cru, and J. Levy. The community structure of sat formulas. In Alessandro Cimatti and Roberto Sebastiani, editors, 15th International Conference of Theory and Applications of Satisfiability Testing (SAT), pages 410-423. Springer, 2012. Google Scholar
  8. C. Aykanat, B. B. Cambazoglu, and B. Uçar. Multi-level Direct K-way Hypergraph Partitioning with Multiple Constraints and Fixed Vertices. Journal of Parallel and Distributed Computing, 68(5):609-625, 2008. Google Scholar
  9. D. A. Bader, H. Meyerhenke, P. Sanders, and D. Wagner, editors. Proc. Graph Partitioning and Graph Clustering - 10th DIMACS Implementation Challenge Workshop, volume 588 of Contemporary Mathematics. AMS, 2013. Google Scholar
  10. M. J. Barber. Modularity and community detection in bipartite networks. Physical Review E, 76:066102, Dec 2007. Google Scholar
  11. A. Belov, D. Diepold, M. Heule, and M. Järvisalo. The SAT Competition 2014. http://www.satcompetition.org/2014/, 2014.
  12. V. D. Blondel, J. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008, 2008. Google Scholar
  13. U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski, and D. Wagner. On Modularity Clustering. IEEE Trans. Knowledge and Data Engineering, 20(2):172-188, 2008. Google Scholar
  14. T. N. Bui and C. Jones. Finding Good Approximate Vertex and Edge Partitions is NP-Hard. Information Processing Letters, 42(3):153-159, 1992. Google Scholar
  15. T. N. Bui and C. Jones. A Heuristic for Reducing Fill-In in Sparse Matrix Factorization. In SIAM Conference on Parallel Processing for Scientific Computing, pages 445-452, 1993. Google Scholar
  16. Ü. V. Catalyürek and C. Aykanat. Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication. IEEE Transactions on Parallel and Distributed Systems, 10(7):673-693, Jul 1999. Google Scholar
  17. Ü. V. Catalyürek and C. Aykanat. PaToH: Partitioning Tool for Hypergraphs. http://bmi.osu.edu/umit/PaToH/manual.pdf, 1999.
  18. J. Cong and S. K. Lim. Edge separability-based circuit clustering with application to multilevel circuit partitioning. IEEE Trans. on CAD of Integrated Circuits and Systems, 23(3):346-357, 2004. Google Scholar
  19. J. Cong and M. Smith. A Parallel Bottom-up Clustering Algorithm with Applications to Circuit Partitioning in VLSI Design. In 30th Conference on Design Automation, pages 755-760, June 1993. Google Scholar
  20. N. J. Cox. Stata tip 96: Cube roots. Stata Journal, 11(1):149-154(6), 2011. URL: http://www.stata-journal.com/article.html?article=st0223.
  21. T. A. Davis and Y. Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software, 38(1):1:1-1:25, 2011. Google Scholar
  22. K. D. Devine, E. G. Boman, R. T. Heaphy, R. H. Bisseling, and Ü. V. Catalyürek. Parallel Hypergraph Partitioning for Scientific Computing. In 20th International Conference on Parallel and Distributed Processing, IPDPS, pages 124-124. IEEE, 2006. Google Scholar
  23. W. E. Donath. Logic partitioning. Physical Design Automation of VLSI Systems, pages 65-86, 1988. Google Scholar
  24. V. Durairaj and P. Kalla. Guiding CNF-SAT Search via Efficient Constraint Partitioning. In Proceedings of the 2004 IEEE/ACM International Conference on Computer-aided Design, ICCAD, pages 498-501. IEEE, 2004. Google Scholar
  25. S. Dutt and W. Deng. VLSI Circuit Partitioning by Cluster-removal Using Iterative Improvement Techniques. In Proceedings of the 1996 IEEE/ACM International Conference on Computer-aided Design, ICCAD, pages 194-200. IEEE, 1996. Google Scholar
  26. S. Fortunato and M. Barthélemy. Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104(1):36-41, 2007. Google Scholar
  27. S. Fortunato and D. Hric. Community detection in networks: A user guide. Physics Reports, 659:1-44, 2016. Google Scholar
  28. Santo Fortunato. Community detection in graphs. Physics Reports, 486(3-5):75-174, 2010. Google Scholar
  29. J. Giráldez-Cru and J. Levy. Generating sat instances with community structure. Artificial Intelligence, 238:119 - 134, 2016. Google Scholar
  30. R. Guimerà, M. Sales-Pardo, and L. A. N. Amaral. Module identification in bipartite and directed networks. Physical Review E, 76:036102, Sep 2007. Google Scholar
  31. S. W. Hadley. Approximation Techniques for Hypergraph Partitioning Problems. Discrete Applied Mathematics, 59(2):115-127, 1995. Google Scholar
  32. L. Hagen and A. B. Kahng. A New Approach to Effective Circuit Clustering. In Proceedings of the 1992 IEEE/ACM International Conference on Computer-aided Design, ICCAD, pages 422-427. IEEE, 1992. Google Scholar
  33. S. Hauck and G. Borriello. An Evaluation of Bipartitioning Techniques. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 16(8):849-866, Aug 1997. Google Scholar
  34. B. Heintz and A. Chandra. Beyond graphs: Toward scalable hypergraph analysis systems. ACM SIGMETRICS Performance Evaluation Review, 41(4):94-97, April 2014. Google Scholar
  35. B. Hendrickson. Graph partitioning and parallel solvers: Has the emperor no clothes? In International Symposium on Solving Irregularly Structured Problems in Parallel, pages 218-225, 1998. Google Scholar
  36. B. Hendrickson and T. G. Kolda. Graph partitioning models for parallel computing. Parallel Computing, 26(12):1519-1534, 2000. Google Scholar
  37. B. Hendrickson and R. Leland. A Multi-Level Algorithm For Partitioning Graphs. SC Conference, 0:28, 1995. Google Scholar
  38. T. C. Hu and K. Moerder. Multiterminal Flows in a Hypergraph. In T.C. Hu and E.S. Kuh, editors, VLSI Circuit Layout: Theory and Design, chapter 3, pages 87-93. IEEE Press, 1985. Google Scholar
  39. K. Suzuki and K. Wakita. Extracting Multi-facet Community Structure from Bipartite Networks. In Proceedings of the 12th IEEE International Conference on Computational Science and Engineering, CSE, pages 312-319, 2009. Google Scholar
  40. G. Karypis. Multilevel hypergraph partitioning. In Jason Cong and Joseph R. Shinnerl, editors, Multilevel Optimization in VLSICAD, pages 125-154. Springer, 2003. Google Scholar
  41. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel Hypergraph Partitioning: Applications in VLSI Domain. IEEE Transactions on Very Large Scale Integration VLSI Systems, 7(1):69-79, 1999. Google Scholar
  42. G. Karypis and V. Kumar. Multilevel K-way Hypergraph Partitioning. In Proceedings of the 36th ACM/IEEE Design Automation Conference, pages 343-348. ACM, 1999. Google Scholar
  43. S. Klamt, U. Haus, and F. Theis. Hypergraphs and Cellular Networks. PLOS Computational Biology, 5(5):e1000385, 05 2009. Google Scholar
  44. R. Lambiotte. Multi-scale modularity in complex networks. In 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, pages 546-553, May 2010. Google Scholar
  45. A. Lancichinetti and S. Fortunato. Community detection algorithms: A comparative analysis. Physical Review E, 80:056117, Nov 2009. Google Scholar
  46. T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. John Wiley &Sons, Inc., 1990. Google Scholar
  47. F. Lotfifar and M. Johnson. A Multi-level Hypergraph Partitioning Algorithm Using Rough Set Clustering. In 21st International Conference on Parallel and Distributed Computing (Euro-Par), pages 159-170, 2015. Google Scholar
  48. Z. Mann and P. Papp. Formula partitioning revisited. In Daniel Le Berre, editor, POS-14. Fifth Pragmatics of SAT workshop, volume 27 of EPiC Series in Computing, pages 41-56. EasyChair, 2014. Google Scholar
  49. T. Murata. Modularity for Bipartite Networks. In N. Memon, J. J. Xu, D. L. Hicks, and H. Chen, editors, Data Mining for Social Network Data. Springer, 2010. Google Scholar
  50. N. Neubauer and K. Obermayer. Towards community detection in k-partite k-uniform hypergraphs. In Proceedings of the NIPS 2009 Workshop on Analyzing Networks and Learning with Graphs, pages 1-9, 2009. Google Scholar
  51. M. E. J. Newman. Analysis of weighted networks. Physical Review E, 70:056131, Nov 2004. Google Scholar
  52. M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69:026113, Feb 2004. Google Scholar
  53. D. A. Papa and I. L. Markov. Hypergraph Partitioning and Clustering. In T. F. Gonzalez, editor, Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall/CRC, 2007. Google Scholar
  54. M. Rosvall, D. Axelsson, and C. T. Bergstrom. The map equation. The European Physical Journal Special Topics, 178(1):13-23, 2009. Google Scholar
  55. S. E. Schaeffer. Graph clustering. Computer Science Review, 1(1):27-64, August 2007. Google Scholar
  56. S. Schlag, V. Henne, T. Heuer, H. Meyerhenke, P. Sanders, and C. Schulz. k-way Hypergraph Partitioning via n-Level Recursive Bisection. In 18th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 53-67, 2016. Google Scholar
  57. D. G. Schweikert and B. W. Kernighan. A Proper Model for the Partitioning of Electrical Circuits. In Proceedings of the 9th Design Automation Workshop, DAC, pages 57-62. ACM, 1972. Google Scholar
  58. A. Trifunovic. Parallel Algorithms for Hypergraph Partitioning. PhD thesis, University of London, 2006. Google Scholar
  59. A. Trifunović and W. J. Knottenbelt. Parallel Multilevel Algorithms for Hypergraph Partitioning. Journal of Parallel and Distributed Computing, 68(5):563 - 581, 2008. Google Scholar
  60. Ü. V. Çatalyürek and M. Deveci and K. Kaya and B. Uçar. UMPa: A multi-objective, multi-level partitioner for communication minimization. In Bader et al. [9], pages 53-66. Google Scholar
  61. B. Vastenhouw and R. H. Bisseling. A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector Multiplication. SIAM Review, 47(1):67-95, 2005. Google Scholar
  62. N. Viswanathan, C. Alpert, C. Sze, Z. Li, and Y. Wei. The DAC 2012 Routability-driven Placement Contest and Benchmark Suite. In Proceedings of the 49th Annual Design Automation Conference, DAC'12, pages 774-782. ACM, 2012. Google Scholar
  63. S. Wichlund. On multilevel circuit partitioning. In 1998 International Conference on Computer-aided Design, ICCAD, pages 505-511. ACM, 1998. Google Scholar
  64. F. Wilcoxon. Individual Comparisons by Ranking Methods. Biometrics Bulletin, 1(6):80-83, 1945. URL: http://www.jstor.org/stable/3001968.
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