The Graph Partitioning Archive (last updated Mar 27 2023)

The partition archive has been in operation since the year 2000 and includes results from most of the major graph partitioning software packages. Furthermore, researchers developing experimental partitioning algorithms regularly submit new partitions for possible inclusion. The software that has been used to produce partitions for the archive is listed below.

Most of the benchmark graphs arise from typical partitioning applications, although the archive also includes results computed for a graph-colouring test suite [Wal04] contained in a separate annexe.

The archive was originally set up as part of a research project into very high quality partitions and authors wishing to refer to the partitioning archive should cite the paper [SWC04].

Acknowledgements: Initially the archive was set up using public domain software from a number of researchers including Bruce Hendrickson & Robert Leland (Sandia National Labs, USA), George Karypis & Vipin Kumar (Univ. Minnesota) and Stephen Barnard & Horst Simon (Cray Research Inc. / NASA Ames).

Subsequently, many researchers have submitted partitions including S. Popinet (NIWA Science, New Zealand); A. Kozhushkin (Program Systems Inst., Russia); R. Banos & C. Gil (Univ. Almeria, Spain); S. Wishko, A. Brandt & D. Ron (Weizmann Inst. Science, Israel); K. Lang & S. Rao (Yahoo! Research, USA); F. Comellas & E. Sapena (Univ. Pol. Catalunya, Spain); J. K. Martinsen & X.Cai (Univ. Oslo, Norway); J. Martin (Trinity College Dublin, Ireland); P. Chardaire, M. Barake & G. P. McKeown (Univ. East Anglia, UK); C.-E. Bichot (ENAC, Toulouse, France); H. Meyerhenke (Univ. Paderborn, Germany); C. Schulz (Univ. Karlsruhe, Germany); Mattias Hein (Univ. Saarland, Germany); Dale Wong; Ilya Safro (Argonne National Lab, USA); Jin-Kao Hao (Univ. Angers, France); Frank Schneider (Inform Software); Bruno Menegola (Federal Univ. Rio Grande do Sul, Brazil); Emmanuel Romero Ruiz & Carlos Segura González (Center for Research in Mathematics, Guanajuato, Mexico).

Contents

• Problem definition
• Submissions
• Archived partitions
• Downloads
• Software
• References
• Benchmark graphs
• Results with 0% imbalance
• Results with up to 1% imbalance
• Results with up to 3% imbalance
• Results with up to 5% imbalance
• Colouring annexe

Problem definition

The usual objective of graph partitioning is to find a partition which evenly balances the vertex weight in each subdomain whilst minimising the total weight of cut edges or cut-weight, |E_c|. To evenly balance the vertex weight, the optimal subdomain weight is given by S_opt := ceil(|V|/P) (where the ceiling function ceil(x) returns the smallest integer greater than x). The graph partitioning problem can then be specified as: find a partition of G such that |E_c| is minimised subject to the constraint that |S_p| <= S_opt.

In fact it has been noted for some time that partition quality can often be improved if a certain amount of imbalance is allowed, [ST97]. The imbalance is defined as the maximum subdomain weight, S' = max |S_p|, divided by the optimal, S_opt. If we allow x% imbalance then the partitioning problem becomes: find a partition of G such that |E_c| is minimised subject to the constraint that |S_p| <= S_opt.(100+x)/100.

The graph partitioning problem arises in many applications such as VLSI circuit design, data mining and parallel computing. In the latter case the subdomains are mapped to processors and the cut-weight then approximates the total communication volume. However, there is some discussion about whether this is the most appropriate metric for partitioning, e.g. [HK00], and indeed it is unlikely that any one metric is appropriate. Currently in the archive, the quality of partitions is determined by cut-weight, however, there is no reason why it should not be extended to incorporate partitions which minimise different cost functions.

Back to top

Submissions

The archive welcomes submissions of partition files. Submitted partition files will be validated and added to the archive if they improve on a particular result. In this context improvement is:

• having a lower cut-weight than the exisiting result whilst not exceeding the maximum subdomain weight; or
• having the same cut-weight as an exisiting result but a smaller maximum subdomain weight; or
• being a new result.

If there are several files to be submitted (more than 10) it is simplest if they are packaged up into a single file.

The files should conform to this archive's partition file naming convention and format:

• The partition file naming convention is [graph name].[P].ptn, where P is the number of subdomains.
• The format of the partition file is a list of |V| integers {p}, one per line, with 0 <= p < P and each integer, p, denotes the subdomain to which the corresponding vertex has been assigned (e.g. if the integer on line 200 of the file is 0 then, assuming vertex numbering starts at one, vertex number 200 is in subdomain 0).

The easiest way for me to deal with them is if all the 0% results are put in a directory called 0, all the 1% results in a directory called 1, etc, and then all the directories compiled into a .tar.gz or .zip file.

Submitted files should also include some indication of how the partition was derived which, if a public domain software package, may be subject to verification. The archive reserves the right not to accepted submitted files (either for reasons of disk space or for other unspecified reasons).

Please note that updating the website with new partitions is not a high priority and so it make take a couple of months before I get a chance to do so. However, updates are always added in chronological order.

Back to top

Archived partitions

Back to top

Downloads

Back to top

Software

Notes:

• CHACO was run using the multilevel KL method with recursive bisection and a coarsening threshold of 200.
• JOSTLE was run with the imbalance threshold set to 0%, 1%, 3% (default) and 5% (i.e. 4 different tests for each graph and value of P).
• JOSTLE Evolutionary (JE) was run with the imbalance threshold set to 0% and 3% (i.e. 2 different tests for each graph and value of P). It was only tested in full on a subset of the graphs (add20, 3elt, uk, add32, whitaker3, crack, wing_nodal, fe_4elt2, vibrobox, 4elt, fe_sphere, cti, memplus, cs4, fe_pwt, bcsstk32, t60k, wing, brack2) although occasional JE attributions may be found for other graphs.

Back to top

References

ASS18

Robin Andre, Sebastian Schlag and Christian Schulz. Memetic multilevel hypergraph partitioning. In GECCO'18: Proc. Genetic & Evolutionary Computation Conf., pages 347-354, 2018.

BGOM03

R. Banos, C. Gil, J. Ortega and F. G. Montoya. Multilevel Heuristic Algorithm for Graph Partitioning. In 3rd European Workshop on Evolutionary Computation in Combinatorial Optimization, volume 2611 of LNCS, pages 143-153, Springer, Berlin, 2003.

BH10

U. Benlic and J.-K. Hao. An Effective Multilevel Memetic Algorithm for Balanced Graph Partitioning. In Proc. 22nd IEEE Intl Conf. Tools with Artificial Intelligence, pages 121-128, 2010.

BH11a

U. Benlic and J.-K. Hao. A Multilevel Memetic Approach for Improving Graph k-Partitions. IEEE Trans. Evolutionary Computation, 15(5):624-642, 2011.

BH11b

U. Benlic and J.-K. Hao. An Effective Multilevel Tabu Search Approach for Balanced Graph Partitioning. Comput. Oper. Res., 38(7):1066-1075, 2011.

BS94

S. T. Barnard and H. D. Simon. A Fast Multilevel Implementation of Recursive Spectral Bisection for Partitioning Unstructured Problems. Concurrency: Practice & Experience, 6(2):101-117, 1994.

CBM07

P. Chardaire, M. Barake and G. P. McKeown. A PROBE based heuristic for Graph Partitioning. IEEE Trans. Comp., 56(12):1707-1720, 2007.

CS05

F. Comellas and E. Sapena. A multiagent algorithm for graph partitioning. Tech. Rep. UPC-MA4-2005-05C-21, Univ. Politècnica de Catalunya, 2005.

F88

C. Farhat. A Simple and Efficient Automatic FEM Domain Decomposer. Comput. & Structures, 28(5):579-602, 1988.

HB10

M. Hein and T. Bühler. An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA. Machine Learning Group, Saarland Univ., 2010.

HK00

B. Hendrickson and T. G. Kolda. Graph Partitioning Models for Parallel Computing. Parallel Comput., 26(12):1519-1534, 2000.

HL95

B. Hendrickson and R. Leland. A Multilevel Algorithm for Partitioning Graphs. In S. Karin, editor, Proc. Supercomputing '95, San Diego (CD-ROM), ACM Press, New York, 1995.

HNS18

A. Henzinger, A. Noe and C. Schulz. ILP-based Local Search for Graph Partitioning. Tech. Rep., 2018.

HS11

M. Hein and S. Setzer. Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts. In NIPS'11: Proc. 24th Intl Conf. Neural Information Processing, pages 2366-2374, 2011.

HSS09

M. Holtgrewe, P. Sanders and C. Schulz. Engineering a Scalable High Quality Graph Partitioner. Tech. Rep., 2009.

KK98a

G. Karypis and V. Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM J. Sci. Comput., 20(1):359-392, 1998.

KK98b

G. Karypis and V. Kumar. Multilevel k-way Partitioning Scheme for Irregular Graphs. J. Parallel Distrib. Comput., 48(1):96-129, 1998.

LR04

K. Lang and S. Rao. A flow-based method for improving the expansion or conductance of graph cuts. 2004.

M05

J. Martin. Subproblem Optimization by Gene Correlation with Singular Value Decomposition. In Proc. Genetic & Evolutionary Comput. Conf. (GECCO-2005), ACM, 2005.

MMS08

H. Meyerhenke, B. Monien and T. Sauerwald. A New Diffusion-based Multilevel Algorithm for Computing Graph Partitions of Very High Quality. In Proc. 22nd IEEE Intl. Parallel & Distributed Processing Symp. (IPDPS'08), 2008.

OS10

V. Osipov and P. Sanders. n-Level Graph Partitioning. Inst. Theoretische Informatik, Univ. Karlsruhe, 2010.

RS18

Emmanuel Romero Ruiz and Carlos Segura. Memetic Algorithm with Hungarian Matching Based Crossover and Diversity Preservation. Computación y Sistemas, 22(2):347-361, 2018.

RSB11

D. Ron, I. Safro and A. Brandt. Relaxation-based coarsening and multiscale graph organization. SIAM J. Multiscale Modeling Simulations, 9:407-423, 2011.

S91

H. D. Simon. Partitioning of Unstructured Problems for Parallel Processing. Computing Systems Engrg., 2:135-148, 1991.

SS10

P. Sanders and C. Schulz. Engineering Multilevel Graph Partitioning Algorithms. Inst. Theoretische Informatik, Univ. Karlsruhe, 2010.

SS11

P. Sanders and C. Schulz. Distributed Evolutionary Graph Partitioning. Inst. Theoretische Informatik, Univ. Karlsruhe, 2011.

SS12

P. Sanders and C. Schulz. Think Locally, Act Globally: Perfectly Balanced Graph Partitioning. Inst. Theoretische Informatik, Univ. Karlsruhe, 2012.

SS13

P. Sanders and C. Schulz. Think Locally, Act Globally: Highly Balanced Graph Partitioning. In Experimental Algorithms, volume 7933 of LNCS, pages 164-175, Springer, Berlin, 2013.

ST97

H. D. Simon and S.-H. Teng. How Good is Recursive Bisection? SIAM J. Sci. Comput., 18(5):1436-1445, 1997.

SWC04

A. J. Soper, C. Walshaw and M. Cross. A Combined Evolutionary Search and Multilevel Optimisation Approach to Graph Partitioning. J. Global Optimization, 29(2):225-241, 2004.

W04

C. Walshaw. Multilevel Refinement for Combinatorial Optimisation Problems. Annals Oper. Res., 131:325-372, 2004.

WC00

C. Walshaw and M. Cross. Mesh Partitioning: a Multilevel Balancing and Refinement Algorithm. SIAM J. Sci. Comput., 22(1):63-80, 2000.

Back to top

Benchmark Graphs

Please note that, although weighted graphs can be handled by most of the software listed above, they were not common when the archive was compiled and so there are no weighted graph in the benchmark dataset, partition results or downloads. Sorry.

Back to top

Results with up to 0% imbalance
S_max <= 1.00 x S_opt

Back to top

Results with up to 1% imbalance
S_max <= 1.01 x S_opt

Back to top

Results with up to 3% imbalance
S_max <= 1.03 x S_opt

Back to top

Results with up to 5% imbalance
S_max <= 1.05 x S_opt

Back to top

©