Community hub
0 subscribers7 pages, 0 posts
Recent from talks
All channels
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Graph partition.
Nothing was collected or created yet.
Graph partition
View on Wikipediafrom Wikipedia
In mathematics, a graph partition is the reduction of a graph to a smaller graph by partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the groups will produce edges in the partitioned graph. If the number of resulting edges is small compared to the original graph, then the partitioned graph may be better suited for analysis and problem-solving than the original. Finding a partition that simplifies graph analysis is a hard problem, but one that has applications to scientific computing, VLSI circuit design, and task scheduling in multiprocessor computers, among others.[1] Recently, the graph partition problem has gained importance due to its application for clustering and detection of cliques in social, pathological and biological networks. For a survey on recent trends in computational methods and applications see Buluc et al. (2013).[2] Two common examples of graph partitioning are minimum cut and maximum cut problems.
Problem complexity
[edit]Typically, graph partition problems fall under the category of NP-hard problems. Solutions to these problems are generally derived using heuristics and approximation algorithms.[3] However, uniform graph partitioning or a balanced graph partition problem can be shown to be NP-complete to approximate within any finite factor.[1] Even for special graph classes such as trees and grids, no reasonable approximation algorithms exist,[4] unless P=NP. Grids are a particularly interesting case since they model the graphs resulting from Finite Element Model (FEM) simulations. When not only the number of edges between the components is approximated, but also the sizes of the components, it can be shown that no reasonable fully polynomial algorithms exist for these graphs.[4]
Problem
[edit]Consider a graph G = (V, E), where V denotes the set of n vertices and E the set of edges. For a (k,v) balanced partition problem, the objective is to partition G into k components of at most size v · (n/k), while minimizing the capacity of the edges between separate components.[1] Also, given G and an integer k > 1, partition V into k parts (subsets) V1, V2, ..., Vk such that the parts are disjoint and have equal size, and the number of edges with endpoints in different parts is minimized. Such partition problems have been discussed in literature as bicriteria-approximation or resource augmentation approaches. A common extension is to hypergraphs, where an edge can connect more than two vertices. A hyperedge is not cut if all vertices are in one partition, and cut exactly once otherwise, no matter how many vertices are on each side. This usage is common in electronic design automation.
Analysis
[edit]For a specific (k, 1 + ε) balanced partition problem, we seek to find a minimum cost partition of G into k components with each component containing a maximum of (1 + ε)·(n/k) nodes. We compare the cost of this approximation algorithm to the cost of a (k,1) cut, wherein each of the k components must have the same size of (n/k) nodes each, thus being a more restricted problem. Thus,
We already know that (2,1) cut is the minimum bisection problem and it is NP-complete.[5] Next, we assess a 3-partition problem wherein n = 3k, which is also bounded in polynomial time.[1] Now, if we assume that we have a finite approximation algorithm for (k, 1)-balanced partition, then, either the 3-partition instance can be solved using the balanced (k,1) partition in G or it cannot be solved. If the 3-partition instance can be solved, then (k, 1)-balanced partitioning problem in G can be solved without cutting any edge. Otherwise, if the 3-partition instance cannot be solved, the optimum (k, 1)-balanced partitioning in G will cut at least one edge. An approximation algorithm with a finite approximation factor has to differentiate between these two cases. Hence, it can solve the 3-partition problem which is a contradiction under the assumption that P = NP. Thus, it is evident that (k,1)-balanced partitioning problem has no polynomial-time approximation algorithm with a finite approximation factor unless P = NP.[1]
The planar separator theorem states that any n-vertex planar graph can be partitioned into roughly equal parts by the removal of O(√n) vertices. This is not a partition in the sense described above, because the partition set consists of vertices rather than edges. However, the same result also implies that every planar graph of bounded degree has a balanced cut with O(√n) edges.
Graph partition methods
[edit]Since graph partitioning is a hard problem, practical solutions are based on heuristics. There are two broad categories of methods, local and global. Well-known local methods are the Kernighan–Lin algorithm, and Fiduccia-Mattheyses algorithms, which were the first effective 2-way cuts by local search strategies. Their major drawback is the arbitrary initial partitioning of the vertex set, which can affect the final solution quality. Global approaches rely on properties of the entire graph and do not rely on an arbitrary initial partition. The most common example is spectral partitioning, where a partition is derived from approximate eigenvectors of the adjacency matrix, or spectral clustering that groups graph vertices using the eigendecomposition of the graph Laplacian matrix.
Multi-level methods
[edit]A multi-level graph partitioning algorithm works by applying one or more stages. Each stage reduces the size of the graph by collapsing vertices and edges, partitions the smaller graph, then maps back and refines this partition of the original graph.[6] A wide variety of partitioning and refinement methods can be applied within the overall multi-level scheme. In many cases, this approach can give both fast execution times and very high quality results. One widely used example of such an approach is METIS,[7] a graph partitioner, and hMETIS, the corresponding partitioner for hypergraphs.[8] An alternative approach originated from [9] and implemented, e.g., in scikit-learn is spectral clustering with the partitioning determined from eigenvectors of the graph Laplacian matrix for the original graph computed by LOBPCG solver with multigrid preconditioning.
Spectral partitioning and spectral bisection
[edit]Given a graph with adjacency matrix , where an entry implies an edge between node and , and degree matrix , which is a diagonal matrix, where each diagonal entry of a row , , represents the node degree of node . The Laplacian matrix is defined as . Now, a ratio-cut partition for graph is defined as a partition of into disjoint , and , minimizing the ratio
of the number of edges that actually cross this cut to the number of pairs of vertices that could support such edges. Spectral graph partitioning can be motivated[10] by analogy with partitioning of a vibrating string or a mass-spring system and similarly extended to the case of negative weights of the graph.[11]
Fiedler eigenvalue and eigenvector
[edit]In such a scenario, the second smallest eigenvalue () of , yields a lower bound on the optimal cost () of ratio-cut partition with . The eigenvector () corresponding to , called the Fiedler vector, bisects the graph into only two communities based on the sign of the corresponding vector entry. Division into a larger number of communities can be achieved by repeated bisection or by using multiple eigenvectors corresponding to the smallest eigenvalues.[12] The examples in Figures 1,2 illustrate the spectral bisection approach.
Modularity and ratio-cut
[edit]Minimum cut partitioning however fails when the number of communities to be partitioned, or the partition sizes are unknown. For instance, optimizing the cut size for free group sizes puts all vertices in the same community. Additionally, cut size may be the wrong thing to minimize since a good division is not just one with small number of edges between communities. This motivated the use of Modularity (Q)[13] as a metric to optimize a balanced graph partition. The example in Figure 3 illustrates 2 instances of the same graph such that in (a) modularity (Q) is the partitioning metric and in (b), ratio-cut is the partitioning metric.
Applications
[edit]Conductance
[edit]Another objective function used for graph partitioning is Conductance which is the ratio between the number of cut edges and the volume of the smallest part. Conductance is related to electrical flows and random walks. The Cheeger bound guarantees that spectral bisection provides partitions with nearly optimal conductance. The quality of this approximation depends on the second smallest eigenvalue of the Laplacian λ2.
Immunization
[edit]Graph partition can be useful for identifying the minimal set of nodes or links that should be immunized in order to stop epidemics.[14]
Other graph partition methods
[edit]Spin models have been used for clustering of multivariate data wherein similarities are translated into coupling strengths.[15] The properties of ground state spin configuration can be directly interpreted as communities. Thus, a graph is partitioned to minimize the Hamiltonian of the partitioned graph. The Hamiltonian (H) is derived by assigning the following partition rewards and penalties.
- Reward internal edges between nodes of same group (same spin)
- Penalize missing edges in same group
- Penalize existing edges between different groups
- Reward non-links between different groups.
Additionally, Kernel-PCA-based Spectral clustering takes a form of least squares Support Vector Machine framework, and hence it becomes possible to project the data entries to a kernel induced feature space that has maximal variance, thus implying a high separation between the projected communities.[16]
Some methods express graph partitioning as a multi-criteria optimization problem which can be solved using local methods expressed in a game theoretic framework where each node makes a decision on the partition it chooses.[17]
For very large-scale distributed graphs classical partition methods might not apply (e.g., spectral partitioning, Metis[7]) since they require full access to graph data in order to perform global operations. For such large-scale scenarios distributed graph partitioning is used to perform partitioning through asynchronous local operations only.
Software tools
[edit]scikit-learn implements spectral clustering with the partitioning determined from eigenvectors of the graph Laplacian matrix for the original graph computed by ARPACK, or by LOBPCG solver with multigrid preconditioning.[9]
METIS[7] is a graph partitioning family by Karypis and Kumar. Among this family, kMetis aims at greater partitioning speed, hMetis,[8] applies to hypergraphs and aims at partition quality, and ParMetis[7] is a parallel implementation of the Metis graph partitioning algorithm.
KaHyPar[18][19][20] is a multilevel hypergraph partitioning framework providing direct k-way and recursive bisection based partitioning algorithms. It instantiates the multilevel approach in its most extreme version, removing only a single vertex in every level of the hierarchy. By using this very fine grained n-level approach combined with strong local search heuristics, it computes solutions of very high quality.
Scotch[21] is graph partitioning framework by Pellegrini. It uses recursive multilevel bisection and includes sequential as well as parallel partitioning techniques.
Jostle[22] is a sequential and parallel graph partitioning solver developed by Chris Walshaw. The commercialized version of this partitioner is known as NetWorks.
Party[23] implements the Bubble/shape-optimized framework and the Helpful Sets algorithm.
The software packages DibaP[24] and its MPI-parallel variant PDibaP[25] by Meyerhenke implement the Bubble framework using diffusion; DibaP also uses AMG-based techniques for coarsening and solving linear systems arising in the diffusive approach.
Sanders and Schulz released a graph partitioning package KaHIP[26] (Karlsruhe High Quality Partitioning) that implements for example flow-based methods, more-localized local searches and several parallel and sequential meta-heuristics.
The tools Parkway[27] by Trifunovic and Knottenbelt as well as Zoltan[28] by Devine et al. focus on hypergraph partitioning.
References
[edit]- ^ a b c d e
Andreev, Konstantin; Räcke, Harald (2004). "Balanced graph partitioning". Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures. Barcelona, Spain. pp. 120–124. CiteSeerX 10.1.1.417.8592. doi:10.1145/1007912.1007931. ISBN 978-1-58113-840-5.
{{cite book}}: CS1 maint: location missing publisher (link) - ^ Buluc, Aydin; Meyerhenke, Henning; Safro, Ilya; Sanders, Peter; Schulz, Christian (2013). "Recent Advances in Graph Partitioning". arXiv:1311.3144 [cs.DS].
- ^ Feldmann, Andreas Emil; Foschini, Luca (2012). "Balanced Partitions of Trees and Applications". Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science: 100–111.
- ^ a b Feldmann, Andreas Emil (2012). "Fast Balanced Partitioning is Hard, Even on Grids and Trees". Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science. arXiv:1111.6745. Bibcode:2011arXiv1111.6745F.
- ^ Garey, Michael R.; Johnson, David S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co. ISBN 978-0-7167-1044-8.
- ^ Hendrickson, B.; Leland, R. (1995). A multilevel algorithm for partitioning graphs. Proceedings of the 1995 ACM/IEEE conference on Supercomputing. ACM. p. 28.
- ^ a b c d Karypis, G.; Kumar, V. (1999). "A fast and high quality multilevel scheme for partitioning irregular graphs". SIAM Journal on Scientific Computing. 20 (1): 359. CiteSeerX 10.1.1.39.3415. doi:10.1137/S1064827595287997. S2CID 3628209.
- ^ a b Karypis, G.; Aggarwal, R.; Kumar, V.; Shekhar, S. (1997). Multilevel hypergraph partitioning: application in VLSI domain. Proceedings of the 34th annual Design Automation Conference. pp. 526–529.
- ^ a b Knyazev, Andrew V. (2006). Multiscale Spectral Graph Partitioning and Image Segmentation. Workshop on Algorithms for Modern Massive Data Sets Stanford University and Yahoo! Research.
- ^ J. Demmel, [1] Archived 2018-05-06 at the Wayback Machine, CS267: Notes for Lecture 23, April 9, 1999, Graph Partitioning, Part 2
- ^ Knyazev, Andrew (2018). On spectral partitioning of signed graphs. Eighth SIAM Workshop on Combinatorial Scientific Computing, CSC 2018, Bergen, Norway, June 6–8. arXiv:1701.01394. doi:10.1137/1.9781611975215.2.
- ^ Naumov, M.; Moon, T. (2016). "Parallel Spectral Graph Partitioning". NVIDIA Technical Report. nvr-2016-001. Archived from the original on 2016-05-05. Retrieved 2016-04-20.
- ^ Newman, M. E. J. (2006). "Modularity and community structure in networks". PNAS. 103 (23): 8577–8696. arXiv:physics/0602124. Bibcode:2006PNAS..103.8577N. doi:10.1073/pnas.0601602103. PMC 1482622. PMID 16723398.
- ^ Y. Chen, G. Paul, S. Havlin, F. Liljeros, H.E. Stanley (2009). "Finding a Better Immunization Strategy". Phys. Rev. Lett. 101 (5) 058701. doi:10.1103/PhysRevLett.101.058701. PMID 18764435.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - ^ Reichardt, Jörg; Bornholdt, Stefan (July 2006). "Statistical mechanics of community detection". Phys. Rev. E. 74 (1) 016110. arXiv:cond-mat/0603718. Bibcode:2006PhRvE..74a6110R. doi:10.1103/PhysRevE.74.016110. PMID 16907154. S2CID 792965.
- ^ Alzate, Carlos; Suykens, Johan A. K. (2010). "Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted Kernel PCA". IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (2): 335–347. Bibcode:2010ITPAM..32..335A. doi:10.1109/TPAMI.2008.292. ISSN 0162-8828. PMID 20075462. S2CID 200488.
- ^ Kurve, A.; Griffin, C.; Kesidis G. (2011) "A graph partitioning game for distributed simulation of networks", Proceedings of the 2011 International Workshop on Modeling, Analysis, and Control of Complex Networks: 9–16
- ^ Schlag, S.; Henne, V.; Heuer, T.; Meyerhenke, H.; Sanders, P.; Schulz, C. (2015-12-30). "K-way Hypergraph Partitioning via n-Level Recursive Bisection". 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics. pp. 53–67. arXiv:1511.03137. doi:10.1137/1.9781611974317.5. ISBN 978-1-61197-431-7. S2CID 1674598.
- ^ Akhremtsev, Y.; Heuer, T.; Sanders, P.; Schlag, S. (2017-01-01). "Engineering a direct k-way Hypergraph Partitioning Algorithm". 2017 Proceedings of the Nineteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics. pp. 28–42. doi:10.1137/1.9781611974768.3. ISBN 978-1-61197-476-8.
- ^ Heuer, Tobias; Schlag, Sebastian (2017). "Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure". In Iliopoulos, Costas S.; Pissis, Solon P.; Puglisi, Simon J.; Raman, Rajeev (eds.). 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs). Vol. 75. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 21:1–21:19. doi:10.4230/LIPIcs.SEA.2017.21. ISBN 978-3-95977-036-1.
- ^ Chevalier, C.; Pellegrini, F. (2008). "PT-Scotch: A Tool for Efficient Parallel Graph Ordering". Parallel Computing. 34 (6): 318–331. arXiv:0907.1375. doi:10.1016/j.parco.2007.12.001. S2CID 10433524.
- ^ Walshaw, C.; Cross, M. (2000). "Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm". SIAM Journal on Scientific Computing. 22 (1): 63–80. Bibcode:2000SJSC...22...63W. CiteSeerX 10.1.1.19.1836. doi:10.1137/s1064827598337373.
- ^ Diekmann, R.; Preis, R.; Schlimbach, F.; Walshaw, C. (2000). "Shape-optimized Mesh Partitioning and Load Balancing for Parallel Adaptive FEM". Parallel Computing. 26 (12): 1555–1581. CiteSeerX 10.1.1.46.5687. doi:10.1016/s0167-8191(00)00043-0.
- ^ Meyerhenke, H.; Monien, B.; Sauerwald, T. (2008). "A New Diffusion-Based Multilevel Algorithm for Computing Graph Partitions". Journal of Parallel Computing and Distributed Computing. 69 (9): 750–761. CiteSeerX 10.1.1.702.7275. doi:10.1016/j.jpdc.2009.04.005. S2CID 9755877.
- ^ Meyerhenke, H. (2013). Shape Optimizing Load Balancing for MPI-Parallel Adaptive Numerical Simulations. 10th DIMACS Implementation Challenge on Graph Partitioning and Graph Clustering. pp. 67–82.
- ^ Sanders, P.; Schulz, C. (2011). Engineering Multilevel Graph Partitioning Algorithms. Proceedings of the 19th European Symposium on Algorithms (ESA). Vol. 6942. pp. 469–480.
- ^ Trifunovic, A.; Knottenbelt, W. J. (2008). "Parallel Multilevel Algorithms for Hypergraph Partitioning". Journal of Parallel and Distributed Computing. 68 (5): 563–581. CiteSeerX 10.1.1.641.7796. doi:10.1016/j.jpdc.2007.11.002.
- ^ Devine, K.; Boman, E.; Heaphy, R.; Bisseling, R.; Catalyurek, Ü. (2006). Parallel Hypergraph Partitioning for Scientific Computing. Proceedings of the 20th International Conference on Parallel and Distributed Processing. p. 124.
Further reading
[edit]- Bichot, Charles-Edmond; Siarry, Patrick (2011). Graph Partitioning: Optimisation and Applications. ISTE – Wiley. ISBN 978-1-84821-233-6.
Graph partition
View on Grokipediafrom Grokipedia
Graph partitioning is a fundamental problem in graph theory and computer science, involving the division of a graph's vertex set into a specified number of pairwise disjoint subsets, typically with the goals of balancing the sizes of the subsets (e.g., equal node weights) and minimizing the total weight of edges crossing between subsets, known as the cut size.[1][2]
This problem, which generalizes to k-way partitioning for arbitrary k (with bipartitioning as the case k=2), is NP-hard, as it can be reduced from the maximum cut problem, itself NP-hard via polynomial reduction from 3-SAT.[3][2] Due to its intractability for exact solutions on large graphs, practical approaches rely on heuristic and approximation algorithms, such as the Kernighan-Lin algorithm (which iteratively swaps vertices to reduce cut size) and multilevel partitioning methods that coarsen the graph, partition it, and refine the result.[2] Notable variants include the max-cut problem, which maximizes crossing edges, and balanced graph partitioning, which enforces strict size constraints on subsets.[1]
Graph partitioning has broad applications across domains, including very-large-scale integration (VLSI) design for optimizing chip layouts by minimizing wire lengths, parallel computing for load balancing across processors in distributed systems, and sparse matrix computations in scientific simulations to enhance efficiency.[2][4] It also arises in finite element methods for meshing in engineering simulations, quadratic assignment problems, and community detection in social network analysis.[2][4] The field's historical roots trace back to early work on max-cut in the 1970s, with ongoing research exploring spectral methods, genetic algorithms, and extensions to directed graphs and dynamic scenarios.[1]
The algorithm terminates when a pass yields no positive prefix gain, indicating a local minimum in the cut cost. In practice, it often converges in a small number of passes (typically 2–5 for graphs up to hundreds of vertices).[37][36]
The time complexity of the basic implementation is , as each of up to passes involves gain computations and updates. However, using priority queues (e.g., Fibonacci heaps) to track maximum gains can reduce it to per pass.[38]
which represents the external connections gained minus the internal ones lost. This formulation supports weighted edges directly, allowing adaptation to various graph densities. To facilitate rapid access to the highest-gain vertex, vertices are organized into gain buckets—arrays indexed by possible gain values ranging from to , where is the maximum edge weight—using doubly-linked lists for O(1) insertions, deletions, and maximum selections.[39][40][41] The algorithm begins with an initial balanced partition of the graph into two sets. It then performs a pass by repeatedly selecting the unlocked vertex with the maximum gain that preserves balance (e.g., set sizes within a tolerance ), moving it to the opposite set, locking it to prevent reversal, and updating the gains of its unlocked neighbors—typically affected vertices are limited to those adjacent via "critical" edges crossing the partition. This sequence continues until no improving move is possible or balance is violated. The pass computes a prefix gain sequence from the moves; the partition corresponding to the maximum prefix gain is retained as the refinement, and multiple passes are iterated until no further improvement occurs. Locked vertices are unlocked between passes to explore broader improvements.[39][40][42] In terms of complexity, each pass requires O(|E|) time overall, as gain initializations and updates process each edge a constant number of times via the bucket structure, with bucket operations being amortized O(1). Multiple passes, often converging in a small number (e.g., 2–5), enable practical scalability for graphs with thousands of vertices. Historically, FM was developed for optimizing polycell VLSI layouts, where it demonstrated high throughput, such as processing hundreds of moves per second on 1980s hardware for circuits with hundreds of cells and thousands of pins. It is frequently employed as a refinement step in multilevel partitioning frameworks to polish coarse solutions.[39][40][42]
where is the fraction of edges within community , and is the expected fraction of edges within community under a random null model with the same degree sequence; values of above 0.3 typically indicate significant community structure.[59] Label propagation achieves high modularity scores comparable to more complex methods, such as 0.857 to 0.864 on large web graphs, by naturally forming dense groups through label consensus.[58] Post-processing, such as removing small communities or resolving overlapping labels, can further refine partitions to improve solution quality and consistency across runs.[58] The Louvain method extends modularity optimization into a hierarchical framework, combining elements of agglomeration with greedy local moves to detect multi-scale communities in massive graphs. It operates in two alternating phases: first, it iteratively moves individual nodes to neighboring communities that yield the largest increase in modularity; second, it aggregates communities into supernodes for a coarsened graph and repeats until no modularity gain is possible.[60] The modularity gain from moving a node to community is given by
where is the sum of intra-community edge weights, is the total degree of the community, is the degree of node , is the sum of weights from to the community, and is half the total edge weight sum; this simplifies to evaluating for inter-community links in the aggregated view.[60] This approach reveals hierarchical structures, with each level representing coarser partitions, and has been applied to networks with millions of nodes and edges.[60] Probabilistic variants of label propagation introduce randomness beyond tie-breaking to escape local optima and explore diverse partitions. In these extensions, labels are updated with probabilities proportional to neighbor frequencies rather than strict majorities, allowing stochastic propagation that can reveal multiple community structures in ambiguous graphs.[58] Such randomization improves robustness, as deterministic updates may trap solutions in suboptimal configurations, while probabilistic ones maintain the algorithm's simplicity and speed.[58] These methods excel in scalability, with label propagation achieving near-linear time complexity overall, enabling detection on graphs with millions of edges in seconds on standard hardware.[58] The Louvain method similarly processes billion-edge networks efficiently due to its greedy nature and aggregation, making both suitable for real-time partitioning in dynamic or large-scale settings.[60]
Introduction
Definition and Basic Concepts
Graph partitioning is the problem of dividing the vertices of a graph into a set of disjoint subsets such that the number of edges connecting vertices in different subsets—known as the edge cut—is minimized.[5] This process aims to create subgraphs that are as disconnected as possible from one another while preserving the overall structure of the graph. The concept is fundamental in graph theory and arises in various applications, such as optimizing data distribution in parallel computing environments.[6] Graph partitioning typically applies to undirected graphs, where edges represent symmetric connections between vertices without direction. In unweighted graphs, all edges are considered equal, with each contributing equally to the cut size if it crosses subsets. Weighted graphs extend this by assigning non-negative weights to edges (and sometimes vertices), where the cut size is the sum of weights of crossing edges, allowing for more nuanced representations of connection strengths, such as communication costs in networks.[7][1] Formally, consider an undirected graph , where is the set of vertices and is the set of edges. A partition divides into disjoint subsets such that and for . For a balanced -way partition, the sizes of the subsets are approximately equal, satisfying (or a weighted analog using vertex weights).[7][1] As a simple illustrative example, consider an unweighted undirected graph with four vertices forming a cycle: edges connect , , , and . A balanced 2-way partition might assign and , resulting in a cut size of 2 (the edges and ). An alternative partition and would also yield a cut size of 2, demonstrating equivalent minimal cuts for this symmetric graph.[1][7]Historical Development
The origins of graph partitioning can be traced to the early 1970s, when Brian W. Kernighan and Shen Lin developed a heuristic algorithm specifically for circuit design applications, aiming to divide graphs into subsets while minimizing the number of edges crossing between them.[8] This Kernighan-Lin algorithm, published in 1970, marked a pivotal milestone by providing an iterative swapping method that improved upon initial random partitions, influencing subsequent work in very-large-scale integration (VLSI) and parallel computing.[8] In the mid-1970s, foundational theoretical advances laid the groundwork for spectral partitioning methods, with Miroslav Fiedler introducing the concept of algebraic connectivity—the second smallest eigenvalue of the graph Laplacian—in 1973, which quantifies graph cohesion and later proved instrumental in eigenvector-based partitioning.[9] These ideas gained practical traction in the 1980s and 1990s, as researchers like Donath and Hoffman in 1972–1973 first proposed using Laplacian eigenvectors for cuts, followed by key implementations such as Pothen, Simon, and Li's 1990 algorithm for sparse matrix partitioning via spectral bisection.[10] Spectral methods became widely adopted for their ability to reveal global structure, though computational costs limited scalability until refined in works like Hendrickson and Leland's improvements in the mid-1990s.[10] The 1990s saw the rise of multilevel partitioning techniques to address ever-larger graphs in scientific computing and sparse matrix ordering, with George Karypis and Vipin Kumar introducing the METIS software package around 1995 as an open-source tool implementing recursive bisection through coarsening, initial partitioning, and refinement phases.[11] METIS's efficiency on unstructured meshes and graphs set a benchmark for parallel implementations, enabling partitions of millions of vertices and inspiring tools like ParMETIS for distributed environments.[11] Following 2010, graph partitioning evolved to incorporate hypergraph models for capturing n-way interactions in applications like VLSI and social networks, with algorithms extending multilevel approaches to hyperedges for more accurate cut minimization.[12] Concurrently, machine learning integration emerged, using techniques like graph neural networks to predict optimal partitions or select heuristics based on graph features, enhancing adaptability for massive, dynamic datasets as highlighted in recent surveys.[12] More recent advancements as of 2025 include the application of large language models to tackle graph partitioning tasks and specialized techniques for large-scale nearest neighbor search.[13][14]Problem Formulation
Formal Definition
The graph partitioning problem, in its standard formulation, involves dividing the vertex set of an undirected graph into disjoint subsets such that and for all , while minimizing the total weight of edges that connect vertices in different subsets and satisfying balance constraints on the subset sizes.[15] For a weighted graph where each edge has a non-negative weight , the objective is to minimize the cut size , where denotes the partition and is the subset containing vertex . In the unweighted case, for all edges, so the cut size reduces to the number of crossing edges. For the specific case of 2-way partitioning (bisection), the cut is given by .[15][5] To ensure computational balance, the partition must satisfy size constraints: for each , , where is a small imbalance parameter that allows slight deviations from perfect equality (typically in practice). Vertex weights can be incorporated similarly, requiring the sum of weights in each to be at most times the average. This constraint prevents trivial solutions like placing all vertices in one subset.[15][16] The problem can be approached via direct -way partitioning, which optimizes the subsets simultaneously, or recursive bisection, which repeatedly applies 2-way partitioning to subdivide parts until subsets are obtained (requiring levels for a power of 2). Recursive bisection is computationally simpler but may yield suboptimal cuts compared to direct methods due to accumulated errors across levels.[15][5]Common Variants
In graph partitioning, the unbalanced variant removes size constraints on the partitions, allowing one side to be arbitrarily small while focusing solely on minimizing the edge cut size. This formulation, often simply called the minimum cut problem, arises in applications like network reliability analysis where identifying the weakest disconnection point is key, regardless of partition balance. The problem is NP-hard in general graphs when the number of partitions is part of the input.[17] Multi-objective variants extend the standard problem by optimizing multiple criteria simultaneously, such as minimizing the cut size while maximizing modularity to enhance community detection or minimizing the diameter of induced subgraphs for low-latency parallel processing. For instance, modularity optimization in partitioning seeks to maximize the density of intra-partition edges relative to a null model, which is particularly useful in social network analysis. Similarly, low-diameter partitioning prioritizes compact subgraphs to reduce communication delays in distributed systems. These approaches often use evolutionary algorithms or Pareto optimization to balance trade-offs.[18][19] Directed graph partitioning adapts the problem to digraphs by considering edge directions, typically minimizing flow-based cuts that respect arc orientations, such as in traffic networks or dependency graphs where one-way connections matter. Here, the cut is defined by the total capacity of arcs from one partition to another, often modeled via multicommodity flows to capture multiple source-sink pairs. This variant supports applications like load balancing in directed communication topologies.[20] Hypergraph partitioning generalizes the graph model by allowing hyperedges to connect multiple vertices, providing a more accurate representation of multi-way interactions, such as in VLSI design where nets link several components or in sparse matrix computations. In this setting, the objective is to partition vertices into balanced parts while minimizing the number of hyperedges spanning multiple parts, with the connectivity metric adjusted to account for hyperedge cuts. Unlike pairwise graph edges, this captures higher-order dependencies without bipartite expansions.[21] A specific example of an unbalanced variant is the minimum k-cut problem, which seeks to remove the minimum-weight set of edges to disconnect the graph into exactly k components, without imposing size balance on the parts. This is useful in fault-tolerant system design, where isolating k failure modes is prioritized over even distribution. The problem remains NP-hard for variable k.[17]Quality Metrics
Edge Cut Measures
In graph partitioning, the edge cut size serves as a fundamental measure of the connectivity between subsets in a partition. For a graph with edge weights , and a partition where and , the edge cut size is the total weight of edges crossing from to , formally defined as .[22] This metric quantifies the communication cost or boundary strength in applications like parallel computing, where minimizing the cut size reduces inter-processor data transfer.[23] To normalize for graph scale and imbalance, variants such as expansion and conductance adjust the cut size relative to subset properties. The expansion of a cut is given by , which measures the boundary density per vertex in the smaller subset and is central to expander graph theory for assessing expansion properties.[24] Conductance provides a degree-weighted normalization, defining , where is the volume of .[25] This formulation, prominent in spectral graph theory, better captures expansion in non-regular graphs by accounting for vertex degrees.[26] These measures relate to the discrete isoperimetric problem, which seeks partitions minimizing the normalized cut relative to the boundary size, analogous to geometric isoperimetry where perimeter is minimized for a given area.[26] The graph's isoperimetric constant is the minimum such value over balanced cuts, providing a global connectivity benchmark.[27] In spectral partitioning, low-conductance cuts approximate solutions to this problem via eigenvector analysis.[25]Balance and Fairness Constraints
In graph partitioning, vertex balance constraints ensure that the subgraphs induced by the partitions have approximately equal numbers of vertices, promoting equitable load distribution across computational units. For a graph with vertices partitioned into parts , each must satisfy for some tolerance , where quantifies the allowable imbalance.[16] This formulation, often termed -balanced partitioning, prevents any single partition from dominating the others in size, which is crucial for parallel processing efficiency.[16] A common value for in practical implementations is 0.03, corresponding to a 3% imbalance tolerance, as used in widely adopted tools like METIS for high-quality partitions.[28] For instance, in a balanced bisection () of a graph with vertices and , the size of one part is constrained to lie between approximately and , ensuring neither part exceeds the other by more than 3%.[28] These constraints contribute to the NP-hardness of balanced graph partitioning, as even exact balance () yields inapproximability results unless P = NP.[16] For edge-weighted graphs or edge-partitioning variants, edge balance constraints extend this equity to the distribution of edge weights or counts across partitions. Here, if the graph has total edge weight , each partition must satisfy for a load tolerance , balancing computational load in distributed systems like vertex programs.[29] This is particularly relevant in scenarios minimizing communication overhead, where unbalanced edge loads can lead to processing disparities.[29] In multi-objective graph partitioning, especially for heterogeneous graphs with node attributes or labels, fairness constraints enforce proportional representation to avoid bias in subgroup allocations. Proportional fairness requires that the fraction of nodes with a specific label in partition , , approximates the global fraction , where is the set of nodes with label and .[30] This is quantified via a fairness score , ranging from -1 (highly unfair) to 0 (perfectly fair), with partitions and labels; for example, in a graph with equal numbers of two labels, each partition should contain half of each.[30] Such constraints address equity in applications like social network analysis or machine unlearning, integrating with balance to form multi-objective optimizations.[30]Computational Complexity
NP-Completeness Results
The minimum graph bisection problem, which requires partitioning the vertices of an undirected graph into two equal-sized subsets while minimizing the number of edges crossing between the subsets, is NP-complete. This result was established by Garey, Johnson, and Stockmeyer through a polynomial-time reduction from the exact cover by 3-sets problem, demonstrating that deciding whether a bisection of cost at most a given bound exists is NP-complete even for graphs with maximum degree 4.[31] The proof sketch involves constructing a graph from an exact cover instance where each set in the cover corresponds to a gadget that enforces the balance constraint; a minimum bisection of cost zero exists if and only if the instance has a solution, as crossing edges would otherwise be forced by the structure unless the sets are perfectly covered without overlap or omission. This reduction preserves the balance by ensuring the total vertex count is even and the gadgets contribute equally to both sides only in valid coverings.[31] The NP-completeness extends to the more general k-way balanced graph partitioning problem for any fixed k ≥ 2, where the vertices are divided into k subsets of equal size minimizing the total number of crossing edges; this is NP-hard. In contrast, certain special cases admit polynomial-time algorithms. For trees, the minimum bisection can be computed exactly using dynamic programming in O(n^2) time by considering subtrees and possible cut positions along paths.Approximation and Heuristics Overview
The minimum graph bisection problem, a core variant of graph partitioning, does not admit a polynomial-time approximation scheme (PTAS) unless P = NP, as established through reductions from NP-complete problems like 3-SAT in the late 1990s and early 2000s.[32] This inapproximability result implies that no family of polynomial-time algorithms can approximate the minimum cut within a factor of (1 + ε) for arbitrary ε > 0, highlighting the inherent hardness even for approximate solutions in general graphs. Similar barriers apply to balanced partitioning variants, where achieving near-optimal cuts while maintaining balance constraints remains computationally prohibitive. Despite these limits, polynomial-time approximation algorithms exist with guaranteed ratios for specific graph partitioning problems. For instance, the minimum bisection admits an O(log² n)-approximation in general graphs, improving to O(log n) for minor-closed families like planar graphs.[33] For the related sparsest cut problem, the seminal ARV algorithm achieves an O(√log n)-approximation by leveraging geometric embeddings and expander flows, providing a scalable approach for unbalanced partitions. In sparse graphs with bounded degree, constant-factor approximations are possible under additional structural assumptions, though ratios like 1.2 have been reported in specialized settings such as low-density networks. These algorithms establish baseline performance but often fall short of practical needs for very large instances. Given the inapproximability barriers and the scale of modern graphs—often exceeding 10⁶ vertices in applications like social networks and scientific simulations—heuristics are essential, trading guaranteed optimality for computational efficiency and good empirical quality.[34] Heuristics enable partitioning of massive graphs where exact or tight approximations are infeasible, focusing on metrics like edge cut minimization under balance constraints. Common classes include local search methods, which iteratively refine partitions by swapping vertices to reduce the cut (e.g., via neighborhood explorations); global optimization techniques, such as spectral methods that use eigenvectors for coarse initial partitions; and hybrid approaches that combine coarsening, initial placement, and local refinement for balanced scalability. These categories form the foundation for practical tools, with hybrids often dominating in high-performance computing due to their ability to handle irregular, large-scale structures.Classical Partitioning Methods
Kernighan-Lin Algorithm
The Kernighan-Lin algorithm, introduced in 1970, is a foundational local search heuristic for the 2-way graph partitioning problem, aimed at dividing the vertices of an undirected edge-weighted graph into two subsets of roughly equal size while minimizing the edge cut cost.[35] It begins with an arbitrary initial partition and iteratively refines it by considering pairwise swaps of vertices across the partition boundary, selecting those that most reduce the cut size based on a gain metric. This approach is particularly effective for balanced bipartitions in applications like VLSI circuit design, where minimizing inter-partition connections is crucial.[35] The algorithm proceeds as follows: Start with an initial bipartition of the vertex set into subsets and , each of size , assuming an even number of vertices for simplicity. For each vertex , compute its external cost (sum of edge weights to ) and internal cost (sum of edge weights to ); similarly for vertices in . Define the difference for each vertex, representing the net benefit of moving to the other side. In each iteration (or "pass"), pairwise gains are evaluated for unlocked vertices: select the pair that maximizes the gain , where is the weight of the edge between and (zero if none exists). Swap and , lock them to prevent reuse in the pass, and update values for all remaining unlocked vertices affected by the swap—these updates account for changes in external and internal costs due to the boundary shift. Repeat this pairwise selection and update until all vertices are locked, forming a sequence of tentative swaps.[35][36] The gain function quantifies the reduction in edge cut achieved by swapping and : This measures the net decrease in cut edges, subtracting twice the direct connection between and (as it becomes internal post-swap) from the individual move benefits. After completing a full pass, compute the prefix gains for the sequence of swaps: the total gain up to the -th swap is . Select the prefix with the maximum total gain; if positive, apply all swaps up to that point to update the partition and repeat passes until no improvement occurs.[35][36] Here is an outline of the algorithm in pseudocode:Input: Graph G = (V, E, w), initial partition {A, B} with |A| = |B| = n/2
Output: Refined partition {A', B'}
function KernighanLin(G, A, B):
while true:
Compute D_u for all u in A ∪ B // D_u = E_u - I_u
locked_A ← ∅, locked_B ← ∅
sequence ← []
for k = 1 to n/2:
max_gain ← -∞, best_u ← null, best_v ← null
for u in A \ locked_A:
for v in B \ locked_B:
g ← D_u + D_v - 2 * w(u,v)
if g > max_gain:
max_gain ← g, best_u ← u, best_v ← v
swap best_u and best_v // Tentative: move to sequence
append (best_u, best_v, max_gain) to sequence
lock best_u and best_v
update D for unlocked vertices // Adjust based on swap
compute prefix gains for sequence
if max prefix gain ≤ 0:
break // Local minimum reached
else:
apply swaps up to max prefix to A and B
return {A, B}
Input: Graph G = (V, E, w), initial partition {A, B} with |A| = |B| = n/2
Output: Refined partition {A', B'}
function KernighanLin(G, A, B):
while true:
Compute D_u for all u in A ∪ B // D_u = E_u - I_u
locked_A ← ∅, locked_B ← ∅
sequence ← []
for k = 1 to n/2:
max_gain ← -∞, best_u ← null, best_v ← null
for u in A \ locked_A:
for v in B \ locked_B:
g ← D_u + D_v - 2 * w(u,v)
if g > max_gain:
max_gain ← g, best_u ← u, best_v ← v
swap best_u and best_v // Tentative: move to sequence
append (best_u, best_v, max_gain) to sequence
lock best_u and best_v
update D for unlocked vertices // Adjust based on swap
compute prefix gains for sequence
if max prefix gain ≤ 0:
break // Local minimum reached
else:
apply swaps up to max prefix to A and B
return {A, B}
Fiduccia-Mattheyses Heuristic
The Fiduccia-Mattheyses (FM) heuristic is a local search algorithm for refining graph partitions, particularly effective for minimizing the edge cut in weighted graphs while respecting balance constraints. Introduced in 1982, it extends earlier partitioning methods by enabling efficient single-vertex relocations, making it suitable for large-scale applications such as VLSI circuit design. Unlike pairwise swaps, FM processes vertices individually in a sequence, selecting moves based on a gain metric that quantifies the reduction in cut size.[39][40] The primary innovation of FM lies in its use of single-vertex moves combined with a bucket data structure to achieve constant-time updates and selections, addressing the quadratic complexity limitations of prior approaches. In a weighted graph with partition , the gain for moving a vertex to is defined as the change in cut weight:which represents the external connections gained minus the internal ones lost. This formulation supports weighted edges directly, allowing adaptation to various graph densities. To facilitate rapid access to the highest-gain vertex, vertices are organized into gain buckets—arrays indexed by possible gain values ranging from to , where is the maximum edge weight—using doubly-linked lists for O(1) insertions, deletions, and maximum selections.[39][40][41] The algorithm begins with an initial balanced partition of the graph into two sets. It then performs a pass by repeatedly selecting the unlocked vertex with the maximum gain that preserves balance (e.g., set sizes within a tolerance ), moving it to the opposite set, locking it to prevent reversal, and updating the gains of its unlocked neighbors—typically affected vertices are limited to those adjacent via "critical" edges crossing the partition. This sequence continues until no improving move is possible or balance is violated. The pass computes a prefix gain sequence from the moves; the partition corresponding to the maximum prefix gain is retained as the refinement, and multiple passes are iterated until no further improvement occurs. Locked vertices are unlocked between passes to explore broader improvements.[39][40][42] In terms of complexity, each pass requires O(|E|) time overall, as gain initializations and updates process each edge a constant number of times via the bucket structure, with bucket operations being amortized O(1). Multiple passes, often converging in a small number (e.g., 2–5), enable practical scalability for graphs with thousands of vertices. Historically, FM was developed for optimizing polycell VLSI layouts, where it demonstrated high throughput, such as processing hundreds of moves per second on 1980s hardware for circuits with hundreds of cells and thousands of pins. It is frequently employed as a refinement step in multilevel partitioning frameworks to polish coarse solutions.[39][40][42]
Spectral Partitioning
Laplacian Matrix and Eigenvalues
The Laplacian matrix serves as a fundamental tool in spectral graph partitioning, capturing the structure of a graph through its eigenvalues and eigenvectors. For an undirected graph with adjacency matrix , where if and 0 otherwise, the unnormalized Laplacian matrix is defined as , with being the diagonal degree matrix whose entries are the degrees of the vertices.[43] This matrix is symmetric and positive semidefinite, ensuring that its eigenvalues are real and nonnegative.[25] The eigenvalues of , denoted where , provide key insights into graph connectivity. The smallest eigenvalue is always , with corresponding eigenvector the all-ones vector , and its multiplicity equals the number of connected components.[43] The second-smallest eigenvalue for connected graphs, known as the algebraic connectivity, quantifies how well-connected the graph is; smaller values indicate poorer connectivity and potential bottlenecks suitable for partitioning.[43] To address limitations of the unnormalized Laplacian in irregular graphs, the normalized Laplacian is introduced as , where is the identity matrix and is the diagonal matrix with entries .[25] This normalization accounts for degree variations, yielding eigenvalues in , with and for connected graphs, offering a degree-invariant measure of connectivity.[25] The algebraic connectivity connects directly to graph cuts via the Rayleigh quotient: where the Rayleigh quotient relates to graph cuts because, for vectors approximating balanced partition indicators (e.g., +1 on one side, -1 on the other, prior to normalization), is proportional to the cut size (specifically, for the balanced min-cut with unit edge weights), linking spectral properties to partitioning objectives.[43][44] The eigenvector corresponding to , known as the Fiedler vector, is used in subsequent partitioning steps.[43] Computing these eigenvalues for large sparse graphs relies on iterative methods like the Lanczos algorithm, which efficiently approximates extreme eigenvalues of symmetric matrices by tridiagonalizing through orthogonal transformations, enabling scalable spectral partitioning without full matrix diagonalization.[45]Fiedler Vector Applications
The Fiedler vector, named after mathematician Miroslav Fiedler, refers to the eigenvector corresponding to the second smallest eigenvalue λ₂ (known as the algebraic connectivity) of the graph Laplacian matrix.[46] This vector captures structural information about the graph's connectivity and is central to spectral partitioning methods for obtaining balanced bisections.[47] In graph partitioning applications, the Fiedler vector facilitates recursive bisection by sorting the vertices in ascending order of their component values in the vector. A threshold is then applied—typically at the median value—to divide the vertices into two subsets of approximately equal size, ensuring balance while approximating a minimum edge cut. This sweep-cut approach leverages the vector's property that vertices with similar values tend to be closely connected, thereby minimizing the number of edges crossing the cut.[45] The process can be repeated on the induced subgraphs to achieve multi-level partitions.[45] A representative example occurs with a path graph, where the Fiedler vector's components approximate a discrete sine wave, with values increasing smoothly from one end to the other. Selecting the median threshold yields a balanced cut near the graph's center, separating it into two connected components of equal length with a single crossing edge, which is optimal for minimizing the cut size under balance constraints.[48] Despite its effectiveness, the Fiedler vector-based bisection does not always produce optimal partitions, particularly for non-planar graphs where the vector's ordering may not align perfectly with an intuitive embedding. In such cases, the initial partition often requires post-processing through local improvement heuristics, such as the Kernighan-Lin algorithm, to reduce the cut size further while preserving balance.[45] Theoretical guarantees on the quality of partitions derived from the Fiedler vector stem from eigenvalue-based bounds, including those developed by Donath and Hoffman in 1973, which relate λ₂ to lower bounds on the minimum separator size in graphs. These bounds demonstrate that spectral methods, including Fiedler vector sweeps, can approximate the optimal cut within a factor involving the graph's diameter and eigenvalue, providing a quantifiable measure of performance for connected graphs.[49]Ratio Cut and Normalized Cut
The ratio cut is an objective function for graph partitioning that seeks to minimize the cut size while penalizing imbalances in partition sizes, thereby promoting more equitable divisions. For a k-way partition of the vertex set into subsets , the ratio cut is defined as where denotes the total weight of edges crossing between and its complement.[50] This formulation extends the two-way case originally proposed by Hagen and Kahng, which minimizes for subsets and , to multiple partitions by summing the ratio cut terms for each component versus its complement.[51] Unlike the plain edge cut, which can favor uneven partitions (e.g., isolating small components with minimal cuts), the ratio cut incorporates the product of sizes in the denominator to encourage balance, making it suitable for applications requiring roughly equal-sized groups.[50][52] Spectral methods approximate the ratio cut by relaxing the discrete optimization into a continuous one using eigenvectors of the graph Laplacian , where is the degree matrix and is the adjacency weight matrix. For the k-way case, the approach involves computing the k smallest non-trivial eigenvectors and using them to embed vertices into a low-dimensional space, followed by clustering (e.g., via k-means) to obtain the partition; this minimizes a relaxed trace objective subject to , where the columns of approximate the indicator vectors of the partitions scaled by size.[50] This relaxation provides a heuristic solution that often yields high-quality partitions, as validated in VLSI design benchmarks where ratio cut methods outperformed earlier min-cut heuristics in balancing trade-offs.[51] The normalized cut builds on the ratio cut by further refining the normalization to account for the total connection strength (volume) of each partition, addressing limitations in graphs with varying node degrees or weights. Introduced by Shi and Malik for image segmentation, the two-way normalized cut between subsets and is given by where is the volume of , representing the total weight of edges incident to .[53] For multi-way partitions, it generalizes to . This criterion balances inter-group dissimilarity and intra-group similarity, making it particularly effective for segmenting images into coherent regions by modeling pixels as nodes and similarities (e.g., intensity or texture) as edge weights.[53] To approximate the normalized cut, Shi and Malik relax the indicator vectors to real-valued solutions of the generalized eigenvalue problem , where the eigenvectors corresponding to the smallest non-zero eigenvalues provide the embedding; for k-way partitioning, the first k such eigenvectors are used, and the discrete partition is recovered by clustering.[53] Equivalently, the optimization minimizes the trace of the normalized Laplacian applied to the relaxed indicators: subject to and , where has columns as the relaxed indicator vectors.[53] This spectral relaxation ensures global optimality in the continuous domain, leading to partitions that avoid the small-set bias of unnormalized cuts. Both ratio cut and normalized cut improve upon plain Fiedler vector applications by explicitly normalizing for partition sizes or volumes, yielding more robust results in graphs with potential unequal component sizes, such as in non-regular networks or segmentation tasks with varying densities.[53][50]Multilevel Partitioning
Coarsening and Matching Techniques
Coarsening is a key phase in multilevel graph partitioning that aims to iteratively reduce the size of the original graph by contracting vertices and edges, producing a hierarchy of successively smaller graphs while preserving the overall structure, connectivity, and weights of the original graph. This process simplifies the partitioning task by creating a coarse graph from a finer graph through vertex contractions based on a matching, allowing for faster computation on smaller instances before projecting the solution back to the original graph. The goal is to maintain the quality of the partition by ensuring that the coarse graph captures the essential topological features, such as edge cuts and vertex balances, of the finer levels.[15] Matching techniques are employed during coarsening to pair vertices for contraction, determining which edges and vertices are collapsed into supernodes. Random matching (RM) selects unmatched adjacent vertices in a random order, providing a simple and fast approach with linear time complexity , though it may not prioritize structural preservation. Heavy-edge matching (HEM) preferentially matches vertices connected by the heaviest edges, aiming to minimize the edge cut in the coarse graph by concentrating high-weight connections within supernodes, also achieving complexity and demonstrating superior performance in maintaining partition quality across levels. Light-edge matching (LEM), in contrast, favors the lightest edges to promote balance in supernode sizes and weights, helping to avoid overly large or unbalanced contractions that could distort the partitioning problem. For the initial matching at the finest level, algorithms such as linear arrangement—where vertices are ordered sequentially and matched along this line—or region growing, which expands matched clusters from seed vertices in a breadth-first manner, can be used to establish a structured starting point before subsequent iterations.[15][54] During contraction, vertex weights in the coarse graph are updated as the sum of the weights of all contracted vertices, ensuring that the balance constraints of the original graph are preserved across levels; similarly, edge weights between supernodes are set to the sum of the weights of all connecting edges from the finer graph to retain critical connections. This weighted aggregation prevents loss of balance information and supports equitable partitioning in subsequent phases. The coarsening process typically stops when the coarse graph has fewer than 100 vertices or when the reduction ratio between consecutive levels falls below a small threshold, at which point the graph is small enough for direct partitioning methods to be applied efficiently. Following coarsening, the resulting partition is projected back through refinement steps to correct any approximation errors introduced during the contraction.[15][54]Initial Partitioning and Refinement
In multilevel graph partitioning, the initial partitioning phase begins at the coarsest level of the hierarchy, where the graph has been reduced to a small size amenable to exact or high-quality heuristic methods. Common approaches include spectral bisection, which leverages eigenvectors of the Laplacian matrix for balanced cuts, or greedy graph growing techniques that start from a seed vertex and expand partitions iteratively to minimize the edge cut while respecting balance constraints. These methods are computationally feasible on graphs with fewer than 100 vertices, providing a starting solution that captures global structure without the overhead of optimizing the original large graph.[55] The uncoarsening phase projects this coarse partition back to successively finer levels of the hierarchy. For each uncoarsening step, vertex assignments from the coarser graph are interpolated to the finer one: vertices matched in the coarsening process inherit the partition label of their representative, while adjustments are made to ensure balance by potentially moving boundary vertices. This projection preserves the overall structure but may increase the cut size, necessitating refinement.[56] Refinement occurs in a V-cycle manner, applying local improvement heuristics at each level during uncoarsening to iteratively reduce the edge cut. The Fiduccia-Mattheyses (FM) algorithm, a linear-time variant of the Kernighan-Lin heuristic, is commonly used; it greedily swaps boundary vertices between partitions to decrease the cut while monitoring balance via priority queues. Alternatively, label propagation techniques, where vertices asynchronously update their partition labels based on majority neighbors, offer faster parallelizable refinement in modern implementations. These steps repeat upward through the hierarchy, yielding a final partition with minimized cut and balanced sizes.[55][57] The METIS framework exemplifies this process, employing greedy graph growing for initial coarse partitioning and boundary FM refinement in its V-cycle uncoarsening, which achieves 10- to 35-fold speedups over multilevel spectral methods and up to 100-fold over flat heuristics like standalone KL on irregular graphs from finite element and VLSI domains.[56] On standard benchmarks, such multilevel schemes produce edge cuts within 5-10% of optimal solutions for structured graphs, demonstrating high quality while scaling to millions of vertices.[55]Advanced and Emerging Methods
Label Propagation and Community Detection
Label propagation is a simple, iterative algorithm for community detection in graphs, where each vertex initially holds a unique label representing itself as a potential community. In each iteration, a vertex updates its label to the most frequent label among its neighbors, effectively propagating labels through densely connected regions until consensus forms within communities.[58] This process uses asynchronous updates, processing vertices in random order to avoid oscillations, and converges when no vertex changes its label, typically within a few iterations for large networks.[58] The algorithm requires no predefined parameters beyond the graph structure and runs without optimizing an explicit objective function, making it parameter-free and intuitive, inspired by social imitation dynamics.[58] In the context of graph partitioning, label propagation identifies communities by implicitly optimizing modularity, a quality measure that quantifies the strength of divisions in a network. Modularity is defined aswhere is the fraction of edges within community , and is the expected fraction of edges within community under a random null model with the same degree sequence; values of above 0.3 typically indicate significant community structure.[59] Label propagation achieves high modularity scores comparable to more complex methods, such as 0.857 to 0.864 on large web graphs, by naturally forming dense groups through label consensus.[58] Post-processing, such as removing small communities or resolving overlapping labels, can further refine partitions to improve solution quality and consistency across runs.[58] The Louvain method extends modularity optimization into a hierarchical framework, combining elements of agglomeration with greedy local moves to detect multi-scale communities in massive graphs. It operates in two alternating phases: first, it iteratively moves individual nodes to neighboring communities that yield the largest increase in modularity; second, it aggregates communities into supernodes for a coarsened graph and repeats until no modularity gain is possible.[60] The modularity gain from moving a node to community is given by
where is the sum of intra-community edge weights, is the total degree of the community, is the degree of node , is the sum of weights from to the community, and is half the total edge weight sum; this simplifies to evaluating for inter-community links in the aggregated view.[60] This approach reveals hierarchical structures, with each level representing coarser partitions, and has been applied to networks with millions of nodes and edges.[60] Probabilistic variants of label propagation introduce randomness beyond tie-breaking to escape local optima and explore diverse partitions. In these extensions, labels are updated with probabilities proportional to neighbor frequencies rather than strict majorities, allowing stochastic propagation that can reveal multiple community structures in ambiguous graphs.[58] Such randomization improves robustness, as deterministic updates may trap solutions in suboptimal configurations, while probabilistic ones maintain the algorithm's simplicity and speed.[58] These methods excel in scalability, with label propagation achieving near-linear time complexity overall, enabling detection on graphs with millions of edges in seconds on standard hardware.[58] The Louvain method similarly processes billion-edge networks efficiently due to its greedy nature and aggregation, making both suitable for real-time partitioning in dynamic or large-scale settings.[60]