Graph Partitioning: METIS_PartGraphKway and Recursive

METIS provides two graph partitioning functions that implement the multilevel paradigm: coarsen the graph, compute an initial partition on the coarsened graph, then refine and uncoarsen back to the original. METIS_PartGraphKway computes a direct k-way partition in a single multilevel pass, while METIS_PartGraphRecursive builds the partition by repeatedly bisecting subgraphs. Both accept the same parameter list, support multi-constraint balancing, and return a partition assignment for every vertex.

CSR Graph Format

Both functions expect the graph in Compressed Sparse Row (CSR) format:

xadj — array of size nvtxs + 1. Vertex i’s neighbors are stored in adjncy[xadj[i] .. xadj[i+1]-1].
adjncy — flat array of all adjacency lists concatenated. Total length equals the sum of all degrees, i.e., twice the number of undirected edges.

Every edge must appear in both directions. Vertex and edge weights, when provided, follow the same indexing.

Example: 4-vertex path 0-1-2-3
xadj   = [0, 1, 3, 5, 6]
adjncy = [1, 0, 2, 1, 3, 2]

METIS_PartGraphKway

Partitions a graph into nparts parts using multilevel k-way partitioning. Produces high-quality partitions for larger values of k and supports both edge-cut and communication-volume objectives.

int METIS_PartGraphKway(
    idx_t  *nvtxs,
    idx_t  *ncon,
    idx_t  *xadj,
    idx_t  *adjncy,
    idx_t  *vwgt,
    idx_t  *vsize,
    idx_t  *adjwgt,
    idx_t  *nparts,
    real_t *tpwgts,
    real_t *ubvec,
    idx_t  *options,
    idx_t  *edgecut,
    idx_t  *part
);

nvtxs

idx_t *

required

Number of vertices in the graph. Passed by pointer.

ncon

idx_t *

required

Number of balancing constraints. For a standard single-weight problem, pass 1. For multi-constraint problems, vertex weights have ncon components each.

xadj

idx_t *

required

CSR row-pointer array of size nvtxs + 1. xadj[i] gives the starting index in adjncy for vertex i.

adjncy

idx_t *

required

CSR column-index array. Stores all adjacency lists back-to-back. Length equals xadj[nvtxs].

vwgt

idx_t *

Vertex weights array of size nvtxs * ncon. For multi-constraint problems, the ncon weights for vertex i are stored at vwgt[i*ncon .. i*ncon+ncon-1]. Pass NULL for unit weights (all vertices weight 1 per constraint).

vsize

idx_t *

Vertex sizes used when minimizing the total communication volume (METIS_OBJTYPE_VOL). Array of size nvtxs. Pass NULL to use unit sizes or when minimizing edge cut.

adjwgt

idx_t *

Edge weights array of the same length as adjncy. adjwgt[j] is the weight of the edge stored at adjncy[j]. Pass NULL for unit edge weights.

nparts

idx_t *

required

Number of desired partitions. Passed by pointer.

tpwgts

real_t *

Target partition weights. Array of size nparts * ncon. Entry tpwgts[i*ncon+j] specifies the desired fraction of the total weight of constraint j to be assigned to partition i. The values for each constraint must sum to 1.0. Pass NULL for equal-weight partitioning (each part receives 1.0 / nparts of the total weight).

ubvec

real_t *

Load imbalance tolerance. Array of size ncon. ubvec[j] is the maximum allowed ratio of actual to target weight for constraint j. Must be greater than 1.0. Pass NULL to use the UFACTOR-based default: 1.030 for k-way (UFACTOR=30), 1.001 for recursive bisection with a single constraint (UFACTOR=1), or 1.010 for recursive bisection with multiple constraints (UFACTOR=10).

options

idx_t *

required

Options array of size METIS_NOPTIONS (40). Initialize with METIS_SetDefaultOptions before setting individual entries. See the Options Reference.

edgecut

idx_t *

required

Output: the edge cut (or communication volume when METIS_OPTION_OBJTYPE = METIS_OBJTYPE_VOL) of the computed partition.

part

idx_t *

required

Output: partition assignment array of size nvtxs. part[i] is the partition number (0-based) assigned to vertex i. Must be pre-allocated by the caller.

METIS_PartGraphRecursive

Partitions a graph into nparts parts using multilevel recursive bisection. At each level the graph is bisected; the two halves are recursively bisected until nparts parts are reached. Typically produces better results than k-way for small nparts (up to about 8).

int METIS_PartGraphRecursive(
    idx_t  *nvtxs,
    idx_t  *ncon,
    idx_t  *xadj,
    idx_t  *adjncy,
    idx_t  *vwgt,
    idx_t  *vsize,
    idx_t  *adjwgt,
    idx_t  *nparts,
    real_t *tpwgts,
    real_t *ubvec,
    idx_t  *options,
    idx_t  *edgecut,
    idx_t  *part
);

All parameters have identical semantics to METIS_PartGraphKway. The differences are algorithmic:

Uses FM 2-way refinement rather than greedy k-way refinement.
The initial coarsened partition is obtained via a grow-bisection strategy (single constraint) or random bisection (multi-constraint).
METIS_OPTION_OBJTYPE must be METIS_OBJTYPE_CUT; volume minimization is not supported.

When to Use Each Function

Use METIS_PartGraphKway when
Use METIS_PartGraphRecursive when

Partitioning into a large number of parts (roughly 8 or more)
Minimizing communication volume (METIS_OBJTYPE_VOL) as well as edge cut
Requiring contiguous partitions (METIS_OPTION_CONTIG = 1)
Requiring minimization of subdomain connectivity (METIS_OPTION_MINCONN = 1)
Performance is important and quality for large k is sufficient

Partitioning into a small number of parts (2–8)
You need the highest possible partition quality for small k
Multi-constraint balancing with tight tolerances is required
You are using METIS as the initial partitioner inside ParMETIS

Complete Example: Partitioning a 5-Vertex Graph

#include <stdio.h>
#include <metis.h>

int main(void) {
    /*
     * Graph:
     *   0 --- 1 --- 2
     *   |     |     |
     *   3 --- 4 ----+
     *
     * Adjacency:
     *   0: 1, 3
     *   1: 0, 2, 4
     *   2: 1, 4
     *   3: 0, 4
     *   4: 1, 2, 3
     */
    idx_t nvtxs  = 5;
    idx_t ncon   = 1;
    idx_t nparts = 2;

    /* CSR representation */
    idx_t xadj[]   = {0, 2, 5, 7, 9, 12};
    idx_t adjncy[] = {1,3,  0,2,4,  1,4,  0,4,  1,2,3};

    /* Output arrays */
    idx_t edgecut;
    idx_t part[5];

    idx_t options[METIS_NOPTIONS];
    METIS_SetDefaultOptions(options);
    options[METIS_OPTION_SEED] = 0;   /* reproducible */

    int ret = METIS_PartGraphKway(
        &nvtxs, &ncon,
        xadj, adjncy,
        NULL, NULL, NULL,    /* unit vertex weights, no vsize, unit edge weights */
        &nparts,
        NULL, NULL,          /* equal target weights, default imbalance */
        options,
        &edgecut, part
    );

    if (ret != METIS_OK) {
        fprintf(stderr, "METIS error %d\n", ret);
        return 1;
    }

    printf("Edge cut: %d\n", (int)edgecut);
    for (int i = 0; i < nvtxs; i++)
        printf("  vertex %d -> part %d\n", i, (int)part[i]);

    return 0;
}

Multi-Constraint Partitioning

When vertices carry multiple weights (e.g., memory and compute load), set ncon > 1 and provide a flat vwgt array:

idx_t ncon   = 2;     /* two balancing constraints */
idx_t nvtxs  = 4;
idx_t nparts = 2;

/* Two weights per vertex: [mem, compute] */
idx_t vwgt[] = {
    2, 1,   /* vertex 0 */
    1, 3,   /* vertex 1 */
    3, 1,   /* vertex 2 */
    1, 2    /* vertex 3 */
};

/* Allow 10% imbalance on each constraint */
real_t ubvec[] = {1.10, 1.10};

Additional Graph Functions

METIS_ComputeVertexSeparator

Computes a vertex separator of a graph — a set of vertices whose removal makes the graph disconnected into two roughly equal halves. Primarily used internally by ParMETIS.

int METIS_ComputeVertexSeparator(
    idx_t  *nvtxs,
    idx_t  *xadj,
    idx_t  *adjncy,
    idx_t  *vwgt,
    idx_t  *options,
    idx_t  *sepsize,
    idx_t  *part
);

nvtxs

idx_t *

required

Number of vertices.

xadj

idx_t *

required

CSR row-pointer array of size nvtxs + 1.

adjncy

idx_t *

required

CSR column-index array.

vwgt

idx_t *

Vertex weights of size nvtxs. Pass NULL for unit weights.

options

idx_t *

required

Options array initialized with METIS_SetDefaultOptions.

sepsize

idx_t *

required

Output: the weight of the computed separator.

part

idx_t *

required

Output: three-way assignment array of size nvtxs. Values are 0 (left partition), 1 (right partition), or 2 (separator).

METIS_CacheFriendlyReordering

Computes a cache-friendly reordering of vertices within each partition to improve memory access patterns during subsequent computation. Primarily used by the DGL graph learning framework.

int METIS_CacheFriendlyReordering(
    idx_t  nvtxs,
    idx_t *xadj,
    idx_t *adjncy,
    idx_t *part,
    idx_t *old2new
);

nvtxs

idx_t

required

Number of vertices. Passed by value (not a pointer).

xadj

idx_t *

required

CSR row-pointer array.

adjncy

idx_t *

required

CSR column-index array.

part

idx_t *

required

Partition assignment from a prior call to METIS_PartGraphKway or METIS_PartGraphRecursive.

old2new

idx_t *

required

Output: mapping from old vertex IDs to new IDs after reordering. Must be pre-allocated to size nvtxs.

Get Started

CLI Tools

API Reference

Concepts

Graph Partitioning: METIS_PartGraphKway and Recursive

CSR Graph Format

METIS_PartGraphKway

METIS_PartGraphRecursive

When to Use Each Function

Complete Example: Partitioning a 5-Vertex Graph

Multi-Constraint Partitioning

Additional Graph Functions

METIS_ComputeVertexSeparator

METIS_CacheFriendlyReordering

Build docs developers (and LLMs) love

Get Started

CLI Tools

API Reference

Concepts

Documentation Index

​CSR Graph Format

​METIS_PartGraphKway

​METIS_PartGraphRecursive

​When to Use Each Function

​Complete Example: Partitioning a 5-Vertex Graph

​Multi-Constraint Partitioning

​Additional Graph Functions

​METIS_ComputeVertexSeparator

​METIS_CacheFriendlyReordering

Build docs developers (and LLMs) love

CSR Graph Format

METIS_PartGraphKway

METIS_PartGraphRecursive

When to Use Each Function

Complete Example: Partitioning a 5-Vertex Graph

Multi-Constraint Partitioning

Additional Graph Functions

METIS_ComputeVertexSeparator

METIS_CacheFriendlyReordering