Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/KarypisLab/METIS/llms.txt

Use this file to discover all available pages before exploring further.

METIS partitions graphs using the multilevel paradigm, a three-phase approach that achieves high-quality partitionings with low edge cuts at practical computational cost. Rather than attempting to partition a large graph directly—which is computationally expensive and prone to local minima—METIS progressively simplifies the graph into a sequence of smaller graphs, computes an initial partition on the smallest graph, and then projects and refines that partition back up through the sequence. This strategy is effective because the structural properties of the original graph are preserved at each coarser level, and refinement on coarser graphs is much cheaper while still improving the final partition quality.

​
The three phases

1

Coarsening

METIS repeatedly merges pairs of adjacent vertices to produce a sequence of progressively smaller graphs. At each level, a matching is computed—a set of vertex pairs—and each matched pair is contracted into a single vertex in the coarser graph. The weight of a coarse vertex is the sum of the weights of the vertices it represents. This continues until the graph is small enough for exact or near-exact initial partitioning (typically around 30 * nparts vertices, or at most nvtxs / (40 * log2(nparts))).The coarse graphs form a linked list via the coarser and finer pointers in graph_t (libmetis/struct.h). Each graph knows the graph one level coarser (coarser) and the graph one level finer (finer), enabling the uncoarsening phase to walk back up the sequence.Key source file: libmetis/coarsen.c — CoarsenGraph, Match_RM, Match_SHEM, Match_2Hop, CreateCoarseGraph
2

Initial partitioning

Once the coarsest graph is small enough, METIS computes an initial partition directly. For METIS_PTYPE_KWAY, the initial partition is computed by calling METIS_PartGraphRecursive on the coarsest graph (InitKWayPartitioning in kmetis.c). For METIS_PTYPE_RB, bisection is applied recursively using MultilevelBisect on the coarsest subgraph at each level.Multiple initial partitions may be computed and the best one is kept (controlled by METIS_OPTION_NCUTS and METIS_OPTION_NIPARTS).Available initial partition methods (METIS_OPTION_IPTYPE):
MethodConstantDescription
Greedy growMETIS_IPTYPE_GROWBFS-based region growing from a random seed. Default for bisection.
RandomMETIS_IPTYPE_RANDOMRandom vertex assignment followed by FM refinement.
Edge separatorMETIS_IPTYPE_EDGEGrows a bisection then constructs a vertex separator from the boundary.
Node separatorMETIS_IPTYPE_NODEDirectly grows a node separator for nested dissection ordering.
Recursive bisectionMETIS_IPTYPE_METISRBUsed internally by k-way initial partitioning.
Key source file: libmetis/initpart.c — Init2WayPartition, GrowBisection, RandomBisection, GrowBisectionNode
3

Uncoarsening and refinement

The initial partition is projected back through the coarsening sequence from coarsest to finest. At each level, the partition is projected (each fine vertex inherits the partition of the coarse vertex it was contracted into) and then refined to improve the objective while respecting balance constraints.Refinement moves vertices from one partition to another when doing so reduces the objective value without violating balance. The process iterates until no improving moves are found or the maximum number of iterations (METIS_OPTION_NITER) is reached.Available refinement methods (METIS_OPTION_RTYPE):
MethodConstantApplicable to
FM 2-wayMETIS_RTYPE_FMBisection (recursive bisection mode)
Greedy k-wayMETIS_RTYPE_GREEDYDirect k-way partitioning
Two-sided separator FMMETIS_RTYPE_SEP2SIDEDVertex separators (nested dissection)
One-sided separator FMMETIS_RTYPE_SEP1SIDEDVertex separators (nested dissection)
Key source files: libmetis/fm.c — FM_2WayRefine; libmetis/kwayfm.c — Greedy_KWayOptimize, Greedy_KWayCutOptimize, Greedy_KWayVolOptimize; libmetis/sfm.c — FM_2WayNodeRefine2Sided, FM_2WayNodeRefine1Sided

​
Coarsening schemes

METIS supports two matching strategies, controlled by METIS_OPTION_CTYPE:
Sorted Heavy-Edge Matching (METIS_CTYPE_SHEM) visits vertices in order of increasing degree (using bucket sort) and matches each unmatched vertex to its unmatched neighbor with the heaviest incident edge. For graphs with equal edge weights, SHEM falls back to random matching automatically.SHEM tends to produce coarser graphs with fewer, heavier edges, which leads to better initial partitions and lower final edge cuts. It is the default for METIS_PartGraphKway.

​
2-hop coarsening

Standard 1-hop matching can fail to contract a significant fraction of vertices in graphs with a highly skewed degree distribution (power-law graphs, web graphs, social networks). When more than 10% of vertices remain unmatched after 1-hop matching, METIS automatically falls back to 2-hop matching, which matches vertices that are two hops away from each other rather than directly adjacent. Two-hop matching proceeds in two sub-phases (Match_2Hop in coarsen.c):
  1. Match_2HopAny: matches pairs of unmatched low-degree vertices that share at least one common neighbor.
  2. Match_2HopAll: matches pairs of unmatched vertices with identical neighbor sets (using a hash of the adjacency list).
2-hop coarsening is enabled by default and is triggered automatically when needed. It significantly improves partitioning quality and reduces memory use for power-law graphs. If you observe worse-than-expected quality on regular finite-element meshes (where 2-hop should never trigger), you can disable it with options[METIS_OPTION_NO2HOP] = 1.

​
Recursive bisection vs direct k-way

METIS offers two top-level partitioning strategies:
Direct k-way partitioning (METIS_PartGraphKway) coarsens the graph once, computes a k-way initial partition on the coarsest graph (using recursive bisection internally), then refines the k-way partition during uncoarsening. Refinement is done with greedy k-way moves that optimize for either cut or volume.
  • Generally faster than recursive bisection for large k.
  • Produces better balance control for many partitions.
  • Supports both METIS_OBJTYPE_CUT and METIS_OBJTYPE_VOL.
  • Recommended for nparts >= 8.

​
Objective types

METIS_OPTION_OBJTYPE controls what METIS minimizes during refinement:
ObjectiveConstantUse when
Minimize edge cutMETIS_OBJTYPE_CUTReducing the number (or total weight) of cut edges. Standard choice for most parallel computing applications.
Minimize communication volumeMETIS_OBJTYPE_VOLReducing total communication volume in parallel sparse matrix-vector products and similar operations. More expensive to compute but better models actual MPI communication cost.
The volume objective counts, for each vertex, the number of distinct partitions that need a copy of that vertex’s value—a more faithful model of all-to-all communication than edge cut. Volume-based refinement uses Greedy_KWayVolOptimize in kwayfm.c and requires the vsize array to be set when vertex sizes are non-uniform.

​
Key options reference

OptionConstantDefaultDescription
Partition typeMETIS_OPTION_PTYPEMETIS_PTYPE_KWAYRB or KWAY
Objective typeMETIS_OPTION_OBJTYPEMETIS_OBJTYPE_CUTCUT or VOL
Coarsening typeMETIS_OPTION_CTYPEMETIS_CTYPE_SHEMRM or SHEM
Initial partition typeMETIS_OPTION_IPTYPEMETIS_IPTYPE_GROWSee table above
Refinement typeMETIS_OPTION_RTYPEMETIS_RTYPE_GREEDYSee table above
Disable 2-hopMETIS_OPTION_NO2HOP0 (enabled)Set to 1 to disable 2-hop coarsening
Number of cutsMETIS_OPTION_NCUTS1Try this many independent partitionings and keep the best
Refinement iterationsMETIS_OPTION_NITER10Iterations of refinement per uncoarsening level
Random seedMETIS_OPTION_SEED-1 (random)Fixed seed for reproducible results

Build docs developers (and LLMs) love

Get started for freeTalk to us