Linear-Time Multilevel Graph Partitioning via Edge Sparsification

In this work, we show that the described trade-off can be avoided by constructing a linear time multilevel algorithm. Our coarsening algorithm enforces that the graph shrinks by a constant factor with every successive contraction step, using edge sparsification to reduce the number of edges if necessary. We prove that this guarantees $𝒪(n+m)$ expected total work for $n$ nodes and $m$ edges, without any assumptions on the input graph. Our analysis provides a framework to understand the running time behavior of a broad class of existing multilevel algorithms. In addition, we demonstrate that graphs with low modularity are most likely to trigger worst-case running time behavior, while graphs with high modularity might already allow linear running time without using edge sparsification.

We integrate our approach into the KaMinPar shared-memory graph partitioner [29], preserving its excellent scaling behavior while guaranteeing linear work. For instance classes that approximate the worst case, our algorithm achieves practical speedups of up to 4$\times$ (1.49$\times$ in the geometric mean) over a baseline KaMinPar configuration – which is the fastest available shared-memory multilevel partitioner according to Ref. [26]. Despite this, the loss in partition quality is only 1% on average. Our algorithm outperforms both the single-level partitioner PuLP [50] and the state-of-the-art streaming partitioner CUTTANA [31], achieving 24% and 66% smaller average cuts, respectively, as well as a faster running time.

Let $G=(V,E,c,\omega )$ be an undirected graph with node weights $c:V\to {\mathbb{N}}_{>0}$, edge weights $\omega :E\to {\mathbb{N}}_{>0}$, $n≔|V|$, and $m≔|E|$. We extend $c$ and $\omega$ to sets, i.e., $c(V^{\prime }\subseteq V)≔{\sum }_{v\in V^{\prime }}c(v)$ and $\omega (E^{\prime }\subseteq E)≔{\sum }_{e\in E^{\prime }}\omega (e)$. $N(v)≔\{u\mid \{u,v\}\in E\}$ denotes the neighbors of $v\in V$ and $E(v)≔\{e\mid v\in e\}$ denotes the edges incident to $v$. We are looking for $k$ blocks of nodes $\mathrm{\Pi }≔\{V_1,\mathrm{\dots },V_k\}$ that partition $V$, i.e., $V_1\cup \mathrm{\cdots }\cup V_k=V$ and $V_i\cap V_j=\mathrm{\varnothing }$ for $i\ne j$. The balance constraint demands that $\forall i\in \{1,\mathrm{\dots },k\}$: $c(V_i)\le L_{\max }≔(1+\epsilon )\lceil \frac{c(V)}{k}\rceil$ for some imbalance parameter $\epsilon >0$. The objective is to minimize (weight of all cut edges), where $E_{ij}≔\{\{u,v\}\in E\mid u\in V_i,v\in V_j\}$. A clustering $𝒞≔\{C_1,\mathrm{\dots },C_b\}$ is also a partition of $V$, where the number of blocks $b$ is not given in advance (there is also no balance constraint).

Virtually all high-quality, general-purpose graph partitioners are based on the multilevel paradigm, which consists of three phases. During coarsening, the algorithms construct a hierarchy $\mathscr{H}=⟨G≕G_1,G_2,\mathrm{\dots },G_{\mathrm{\ell }}⟩$ of successively coarser representations of the input graph $G$. Coarse graphs are built by either computing node clusterings or matchings and afterwards contracting them. A clustering $𝒞=\{C_1,\mathrm{\dots },C_b\}$ is contracted by replacing each cluster $C_i$ with a coarse node $c_i$ with weight $c(c_i)=c(C_i)$. For each pair of clusters $C_i$ and $C_j$, there is a coarse edge $e=\{c_i,c_j\}$ with weight $\omega (e)=\omega (E_{ij})$ if $E_{ij}\ne \mathrm{\varnothing }$, where $E_{ij}$ is the set of all edges between clusters $C_i$ and $C_j$. Once the number of coarse nodes falls below a threshold (typically, $kC$ for some tuning constant $C$), initial partitioning computes an initial solution of the coarsest graph $G_{\mathrm{\ell }}$. Subsequently, contractions are undone, projecting the current solution to finer graphs and refining it. The total running time of a multilevel partitioner is the cumulative time for coarsening, initial partitioning, and refinement across all levels of the hierarchy $\mathscr{H}$.

Early multilevel partitioners, like Chaco [32] and Metis [36], primarily employed coarsening strategies based on contracting graph matchings. While effective for mesh-like graphs due to high matching coverage (often 85-95% [35]), these strategies struggle with graphs exhibiting irregular structures, such as scale-free networks. On these graphs, small maximal matchings can result in much slower coarsening and potentially a linear number of levels. Subsequent developments addressed this limitation. Mt-Metis [39] introduced $2$-hop matchings, extending small maximal matchings by further pairing nodes that have some degree of overlap in their neighborhoods until $\ge 75\%$ of nodes are contracted. This technique was subsequently also implemented by other partitioners [18, 25]. Alternative strategies focus on accelerating coarsening by grouping multiple nodes. These include methods based on cluster contraction [44, 3, 26, 29] and pseudo-matchings where nodes can match with multiple neighbors [1]. While enabling faster node reductions, they often constrain the weight of the clusters to ensure that finding a balanced initial partition is feasible. This can be problematic on graphs with highly connected hubs (e.g., the center of a star graph), potentially limiting the achievable coarsening ratio.

Graph sparsification techniques aim to approximate a given graph with a sparser one (called sparsifier), typically containing substantially fewer edges while preserving specific structural properties important for downstream tasks. This allows handling massive data sets where considering the full graph is computationally infeasible, as well as speeding up a variety of algorithms on graphs or matrices [2, 9, 22]. For graph partitioning, preserving cut properties (and thus approximately preserving the partition objective) is particularly relevant. An $\epsilon$-cut sparsifier guarantees that every cut in the sparsifier has a weight within a $1\pm \epsilon$ factor of the original cut. Benczúr and Karger showed that such sparsifiers with $O(n\log n/{\epsilon }^2)$ edges exist for any graph and gave near-linear time constructions [9].

There are several approaches to construct sparsifiers. Spielman and Srivastava [51] introduced sparsification based on effective resistance, which often yields high-quality sparsifiers and preserves spectral properties closely related to cuts. However, this method can be computationally demanding. Alternatively, various heuristic sampling techniques exist, such as uniform edge sampling, $k$-neighbor sampling, and Forest Fire sampling [40, 42], which uses an analogy to a spreading wildfire. Chen et al. [16] provide a comparative study, suggesting that Forest Fire sampling outperforms uniform sampling for preserving cut-related properties.

We integrate the techniques described in this paper into the KaMinPar [29] framework. KaMinPar is a shared-memory parallel multilevel graph partitioner. Its coarsening and uncoarsening phases are based on the size-constrained label propagation [44] algorithm, which is parameterized by a maximum cluster size (resp. block weight) $U$. In the coarsening resp. uncoarsening phase, each node is initially assigned to its own cluster resp. to its corresponding block of the partition. The algorithm then proceeds in rounds. In each round, the nodes are visited in some order. A node $u$ is moved to the cluster resp. block $K$ that contains the most neighbors of $u$ without violating the size constraint $U$, i.e., $c(K)+c(u)\le U$. The algorithm terminates once no nodes have been moved during a round or a maximum number of rounds has been exceeded. The coarsening further implements a 2-hop clustering strategy [29], which reduces the number of coarse nodes further whenever label propagation alone yields a node reduction factor less than $2$. Since each round of size-constrained label propagation runs in linear time, and there is only a constant number of rounds, KaMinPar achieves linear time per hierarchy level for coarsening and uncoarsening.

The original paper [29] shows that KaMinPar achieves overall linear-time complexity under two key assumptions: (i) a constant node reduction factor between hierarchy levels, and (ii) bounded average degree for coarse graphs. While we will demonstrate in Theorem 1 that KaMinPar’s coarsening strategy satisfies assumption (i), the inability to guarantee assumption (ii) results in a worst-case running time with an extra $log(n)$ factor.

We propose that the modularity of a graph allows to estimate whether sparsification is necessary.³³3There are also multiple other locality metrics, but these are less useful. For example, the clustering coefficient is based on the number of triangles. However, this does not result in any useful bounds. Modularity was introduced by Newman and Girvan to evaluate the quality of a clustering with regards to community structure [46], and modularity based community detection algorithms are used in many applications [33, 54, 55]. Given a clustering $C=\{V_1,\mathrm{\dots },V_{|C|}\}$, let $e_{ij}:=\frac{1}{2|E|}|E(V_i,V_j)|$ denote the fraction of edges that connect cluster $i$ and cluster $j$ (only counted in one direction). Further, let $a_i:={\sum }_j{e}_{ij}$ be the fraction of edges with one endpoint in cluster $i$. The modularity of the clustering is then defined as $Q_C:={\sum }_i\left(e_{ii}-a_i^2\right)$, where $Q_C\in [-\frac{1}{2},1]$. The modularity $Q\in [0,1]$ of the graph itself is the maximum modularity of all possible clusterings. As demonstrated in the following, modularity is a good fit for our purpose.

Since $Q_C={\sum }_i\left(e_{ii}-a_i^2\right)$, the left side of the inequality follows immediately. Further, ${\sum }_i{e}_{ii}=Q_C+{\sum }_i{a}_i^2\le Q_C+{\sum }_i({\max }_j{a}_j)a_i=Q_C+{\max }_i{a}_i$. Note that ${\sum }_i{a}_i=1$ since each edge is connected to exactly two clusters. $◀$

Lemma 2 provides a lower bound of $1-Q_C-{\alpha }_C$ for the fraction of edges connecting different clusters. Unfortunately, this does not correspond directly to the edges of $G^{\prime }$ – if multiple edges connect the same pair of clusters (we say that the edges are parallel), they are combined into a single edge, thereby further reducing the number of remaining edges. The actual bound is thus $1-Q_C-{\alpha }_C-p_C\le \frac{|E(G^{\prime })|}{|E(G)|}$, where $p_C$ is the number of parallel edges.

Let us consider the case where the clusters are small, such as during the first steps of multilevel coarsening. Then, $1-Q$ is an approximate lower bound for the number of edges. If clusters are small, any cluster is only incident to a small fraction of all edges and edges are unlikely to be parallel, i.e., both ${\alpha }_C$ and $p_C$ are small. Moreover, $Q_C$ is almost certainly smaller than $Q$ as achieving maximum modularity often necessitates large clusters [23]. Consequently, we expect that $1-Q\lesssim 1-Q_C-{\alpha }_C-p_C\le \frac{|E(G^{\prime })|}{|E(G)|}$ if clusters are small, making $1-Q$ an accurate bound.

To verify whether $1-Q$ is a useful bound in practice, we provide an empirical evaluation on a set of 71 large graphs which is used in multiple recent works on graph partitioning [37, 43, 49]. Figure 3 shows computed modularity scores of the graphs in relation to the fraction of edges that remains after one step of our multilevel coarsening algorithm (see Section 4.1). Since computing the modularity of a graph is itself NP-hard [12], we calculate approximate scores with the well-known Louvain algorithm [10], using the implementation from NetworKit [5, 52].

With regards to the total edge weight of $G^{\prime }$ (left, corresponds to inter-cluster edges in $G$), $1-Q$ is almost a strict lower bound. For most graphs, the fraction of remaining weight is much larger than $1-Q$. The actual number of edges after combining parallel edges (right) is often significantly smaller than the weight. However, $1-Q$ is still a mostly accurate bound. Therefore, modularity is indeed useful to predict the coarsening behavior of multilevel algorithms – graphs with low modularity are likely to be worst-case instances.

We implemented the described sparsification algorithms within the KaMinPar [29] framework and compiled it using gcc 14.2.0 with flags -O3 -mtune=native -march=native. The code is parallelized using TBB [47]. All experiments are performed on a machine equipped with two 32-core Intel Xeon Gold 6530 processors (2.1 GHz) and 3 TB RAM running Rocky Linux 9.5. We only use one of the two processors (i.e., 32 cores) to avoid NUMA effects.

In Section 6.3, we compare our algorithm against PuLP [50] (v1.1) and Cuttana [31] (commit ed0c182 in the official GitHub repository⁴⁴4https://github.com/cuttana/cuttana-partitioner). PuLP is a linear time single-level partitioner which focuses on shared-memory scalability and low memory usage. PuLP starts by growing (unbalanced) initial clusters from a random assignment and then performs multiple iterations of alternating balancing and cut minimization. Each phase is implemented with a fixed number of label propagation rounds. The authors showed that PuLP achieves considerable speedups in comparison to multiple well-known multilevel algorithms. Cuttana is a streaming partitioner which improves upon the solution quality of previous streaming approaches with a node buffering technique. Instead of assigning each node greedily, it uses a buffer of fixed size to delay assignment until more information on the neighborhood is available or the buffer overflows. In addition, Cuttana uses a more fine-grained subpartition which allows to further refine the solution quality after the initial assignment. We use the default settings for PuLP and configure Cuttana following the parameters described by the authors, i.e., $\frac{{𝒦}^{\prime }}{𝒦}=\mathrm{4\hspace{0.17em}096}$, $D_{\max }=\mathrm{1\hspace{0.17em}000}$ and $\text{max\_qsize}={10}^6$.

We focus on graphs for which coarsening increases edge density substantially. This happens on 17 out of 71 graphs of a benchmark set used in previous works on graph partitioning [43, 37, 49] (mostly real-world k-mer and social graphs, and graphs deduced from text recompression [34]). We only use these graphs since sparsification is not triggered on the remaining instances, thus leaving the algorithm unchanged. Note that there is no running time overhead in this case. We further include 6 social graphs from the Sparse Matrix Collection [19] and generate random graphs: Erdős-Rényi graphs (using KaGen [24]), as well as Chung-Lu [45], Planted Partition, and R-MAT [15] graphs (using NetworKit [5]). These graphs are inherently non-local, thus especially challenging for linear-time partitioning. Overall, the benchmark set comprises 39 graphs (see Ref. [30]) with 511 K to 1.8 G undirected edges. The graphs deduced from text recompression feature node weights. All other graphs are unweighted. Tuning experiments are performed on a subset containing 8 randomly drawn graphs spanning different types.

We consider an instance as the combination of a graph and a number of blocks $k$. We set the imbalance tolerance to $\epsilon =3\%$, use $k\in \{3,7,8,16,37,64\}$ and perform 5 repetitions for each instance using different seeds. Results (running time, edge cut) are averaged arithmetically per instance over these repetitions. When aggregating across multiple instances, we use the geometric mean to ensure that each instance has equal influence.

To compare the edge cuts of different algorithms, we use performance profiles [20]. Let $𝒜$ be the set of all algorithms we want to compare, $ℐ$ the set of instances, and ${\text{cut}}_A(I)$ the edge cut of algorithm $A\in 𝒜$ on instance $I\in ℐ$. For each algorithm $A$, we plot the fraction of instances

on the $y$-axis and $\tau$ on the $x$-axis. Achieving higher fractions at lower $\tau$-values is considered better. In particular, ${𝒫}_A(1)$ denotes the fraction of instances for which algorithm $A$ performs best, while ${𝒫}_A(\tau )$ for $\tau >1$ illustrates the robustness of the algorithm. For example, an algorithm $A$ with ${𝒫}_A(1)=0.49$ but ${𝒫}_A(1.01)=1.0$ (i.e., never more than 1% worse than the best) might be preferable to an algorithm $B$ with ${𝒫}_B(1)=0.51$ that only achieves ${𝒫}_B(\tau )=1.0$ at much larger $\tau$ (indicating much worse partitions on some inputs).