Description
Graph Partitioning
In computational science and high-performance computing, the graph partition problem is defined on data represented in the form of a graph G = (V,E) with V vertices and E edges, such that it is possible to partition G into smaller components with specific properties. For instance, a k-way partition divides the vertex set into k smaller components. In general, good solutions for the graph partitioning problem require that cuts are small and partitions have equal size. The problem arises, for instance, when assigning work to a parallel computer. In order to achieve efficiency, the workload (partition size) should be balanced evenly among the processors while communication between them (edge cut) should be kept to a minimum. Other important application domains of graph partitioning, and a detailed overview of advances in the field can be found at [1].
Spectral Bisection
The spectral method was initially considered the standard to solve graph partitioning problems. It utilizes the spectral graph theorem of linear algebra, that enables the decomposition of a real symmetric matrix into eigenvalues, within an orthonormal basis of eigenvectors. For an undirected graph G(V,E), with vertex set V = {v1,··· ,vn} and two complementary subsets V1,V2, such that V1 ∪V2 = V and V1 ∩V2 = ∅, we consider an indicator vector x ∈ Rn such that
,
Some of the n nodes of the graph are connected via m edges, each of which has a positive weight associated with it, thus
(
> 0, if vi connected to vj, wij =
= 0 otherwise.
A bisection is computed using the eigenvector associated with the second smallest eigenvalue of the graph Laplacian matrix L ∈ Rn×n, which encodes the degree , i.e.; the number of connected edges, of each vertex along its diagonal, and the negative weights −wij. For an undirected and connected graph G(V,E), as illustrated in Figure 1, with n vertices and m edges, the graph Laplacian can be realized in terms of the adjacency matrix W ∈ Rn×n and the degree matrix D ∈ Rn×n as follows. The graph Laplacian is a symmetric positive semidefinite 0 0.1 0 0.2 0.3 0 0 0 n
W := := Xwij = 0 1.2 0 0
0 0 1.2 0
i∈A,j∈B j=1
0.3 −0.1 0 −0.2
0.2 0.7 0.8 0 0 0 0 1.7
L := D − W.
Figure 1: A weighted, undirected and connected graph G(V,E), with 4 vertices and 5 edges, with its degree D, adjacency W, and graph Laplacian L matrices.
matrix, with its smallest eigenvalue being λ1 = 0, and the associated eigenvector w1 = c1 . The eigenvector w2 being the constant one associated with the second smallest eigenvalue λ2 is Fiedler’s celebrated eigenvector, and is crucial for spectral graph partitioning. Each node vi of the graph is associated with one entry in w2. Thresholding the values of w2 around 0 results in two roughly balanced (equal sized) partitions, with minimum edgecut, while thresholding around the median value of w2 produces two strictly balanced partitions. The procedure to compute a bisection using spectral partitioning is summarized in Algorithm 1. For a much more detailed description of the method we refer to [3].
Inertial Bisection
Inertial bisection is a very different approach, relying on the geometric layout of the graph, i.e. geometric coordinates attached to the vertices of the graph. The main idea of the method is to find a hyperlane running though the ”center of gravity of the points”. In 2 dimensions (2D) such a line ` is chosen such that the sum of squares of the distance of the nodes to the line is minimized. It is defined by a point P = (x,y) and a vector u = (u1,u2) with
Algorithm 1 Spectral bisection
Require: G(V,E),
Ensure: A bisection of G
1: function SPECTRALBISECTION(graph G(V,E))
2: Form the graph Laplacian matrix L
3: Calculate the second smallest eigenvalue λ2 and its associated eigenvector w2.
4: Set 0 or the median of all components of w2 as threshold.
5: Choose V1 := {vi ∈ V |wi < thres},V2 := {vi ∈ V |wi ≥ thres}.
6: return V1,V2
7: end function . bisection of G
such that ` = {P + αu|α ∈ R} (Figure 2). Let each node vi have the coordinates (xi,yi). We then choose
, (1)
as the center of mass lies on the line `. Finally, we need to compute u in order to minimize the sum of distances
, (2)
where Sxx,Sxy,Syy are the sums as defined in the previous line. The resulting matrix M is symmetric , thus the minimum of (2) is achieved by choosing u to be the normalized eigenvector corresponding to the smallest eigenvalue of M. The procedure of bisecting a graph using inertial partitioning is summarized in Algorithm 2. We refer again to [3] and references therein for a thorough overview of the inertial method.
Figure 2: Illustration of inertial bisection in 2D [3].
Algorithm 2 Inertial bisection.
Require: G(V,E),Pi = (xi,yi), i = 1,…,n the coordinates of the nodes
Ensure: A bisection of G
1: function INERTIALBISECTION(graph G(V,E),Pi)
2: Calculate the center of mass of the points . acc. to (1)
3: Compute the eigenvector associated with the smallest eigenvalue of M . M acc. to (2)
4: Partition the nodes along the line H which goes through the center of mass and is orthogonal to L.
5: return V1,V2 . bisection of G
6: end function
The last task of the inertial partitioning routine (line 4), i.e partitioning nodes associated with geometric coordinates around a direction normal to the partitioning plane, is already implemented in the toolbox provided to you in function partition.m. The eigenvalue computations, both for spectral and inertial bisection should be performed with the in-Matlab function eig. Type help eig, or help eigs in your command line for more information.
Partitioning metrics
In what follows we will use the number of cut edges between partitions to determine the quality of the partitioning result. The size of an edge separator, or edgecut, which partitions the graph into a vertex subset and its complement V1 ∪ V2 = V is defined as follows: cut(V1,V2) = X wij. (3)
i∈V1,j∈V2
The calculation of cut edges is implemented in the function cutsize.m of our toolbox. The cardinality of each subset (i.e the number of nodes in each partition) is given by the 2-norm of indicator vector x
x . (4)
Good scalability of parallel distributed memory solvers requires equally sized (balanced) cardinalities, so that the waiting time of the individual threads is minimized. For a k-way partition the load imbalance bk is defined as the ratio of the highest partition cardinality over the average partition cardinality,
, (5)
where Ve is the average partition weight. The load imbalance , where characterizes the deviation from obtaining an evenly balanced partitioning. The optimal value for is therefore zero, and it implies that the k partitions contain exactly the same number of nodes. In most applications it suffices to ensure that is bounded from above by a desired threshold.
Software tools
We will use one external partitioning software tool for this project. METIS [5], probably the most widely used graph partitioning software, was developed by Karypis and Kumar and is probably the most widely used graph partitioning software. It consists of a set of serial programs for partitioning graphs, partitioning finite element meshes, and producing fill reducing orderings for sparse matrices. It is based on local techniques that iteratively improve starting solutions by swapping nodes between the partitions that lie in the neighborhood of the cut. Kernighan and Lin [6] were the first to propose a local search method in this fashion. Their partition refinement strategy, which swaps pairs of vertices that result in the largest decrease in the size of the edgecut, was later accelerated by Fiduccia and Mattheyses [4]. METIS is based on this method, and subsequent improvements of it. Finally, in terms of computational efficiency, numerical experiments have demonstrated that graphs with several millions of vertices can be partitioned to 256 parts in a few seconds on current generation workstations and laptops using METIS.
The assignment
You can find the graph partitioning toolbox Tools on the iCorsi webpage. This toolbox contains Matlab code for the creation of several graph and graph partitioning methods, e.g., coordinate bisection, and has routines to generate recursive multiway partitions and visualize the partitioning results.
Set up the environment
In order to use METIS you need the corresponding Matlab interface, since METIS is written in the C language. You can use the precompiled Matlab interface (metismex.mexmaci64) for Mac and a precompiled version for Linux (metismex.mexa64, Ubuntu, glibc 2.27) that are provided on iCorsi. Then, all you need to do is to tell Matlab where to find the binary (see addpath command in Matlab). If you want to compile the package yourself (e.g., if you are using a different OS), read carefully the instruction on https://github.com/dgleich/metismex on how to install METIS 5.0.2, and how to use cmake, mex, and Matlab to build a mex interface between MATLAB and METIS.
Copy your Matlab interface metismex.mexa64 in the PartToolbox directory so that it can be used for the partitioning of meshes using METIS. Alternatively, specify the path where the interface is located (use the addpath command). Check that the interface works using the following code snippet:
>> A = blkdiag(ones(5),ones(5));
>> A(1,10) = 1; A(10,1) = 1; A(5,6) = 1; A(6,5) = 1;
>> [map,edgecut] = metismex(’PartGraphRecursive’, sparse(A),2) map =
1 1 1 1 1 0 0 0 0 0
edgecut =
2
1. Implement various graph partitioning algorithms [50 points]
• Run in Matlab the script Benchbisection.m and familiarize yourself with the Matlab codes in the directory PartToolbox. An overview of all functions and scripts is offered in Contents.m.
• Implement spectral graph bisection based on the entries of the Fiedler eigenvector. Use the incomplete Matlab file bisection spectral.m for your solution.
• Implement inertial graph bisection. For a graph with 2D coordinates, this inertial bisection constructs a line such that half the nodes are on one side of the line, and half are on the other. Use the incomplete Matlab file bisectioninertial.m for your solution.
• Report the bisection edgecut for all toy meshes that are either generated or loaded in the script ”Bench bisection.m.” Use Table 1 to report these results.
Table 1: Bisection results
Mesh Coordinate Metis 5.0.2 Spectral Inertial
grid5rec(12,100) 12
grid5rec(100,12) grid5recRotate(100,12,-45) gridt(50) grid9(40)
Smallmesh
Tapir
Eppstein 12
2. Recursively bisecting meshes [20 points]
A recursive k-way partitioning algorithm is already implemented in the file recbisection.m of the toolbox. It allows us to create a 2l partition, with l being an integer. Utilize this function within the script Benchrecbisection.m to recursively bisect the finite element meshes loaded within the script in 8 and 16 subgraphs. These graphs emerge from the SuiteSparse Matrix Collection (SSMC) [2]. Use your inertial and spectral partitioning implementations, as well as the coordinate partitioning and the METIS bisection routine. Summarize your results in Table 2 (hint: check the mesh sizes carefully). Finally, visualize the results for p = 8 and p = 16 for the case ”de-2010”. An example for spectral recursive partitioning is illustrated in Figure 3.
Figure 3: Left: The finite element mesh ”bodyy-4” with 17546 nodes and 52002 edges. Right: 8-way recursive bisection of the mesh using Metis 5.0.2. Number of cut edges: 965.
Hint: If calculating the edge-cuts takes some time consider debugging your code using the smaller meshes.
3. Comparing recursive bisection to direct k-way partitioning [15 points]
Case Spectral Metis 5.0.2 Coordinate Inertial
mesh3e1 bodyy4 de-2010 biplane-9
L-9
of robust methods for direct k-way partitioning.
Besides recursive bi-partitioning, METIS also employs a multilevel k-way partitioning algorithm. The graph G = (V,E) is initially coarsened down to a small number of vertices, a k-way partitioning of this much smaller graph is computed, and then this partitioning is projected back towards the original finer graph by successively refining the partitioning at each intermediate level [5]. We will compare the quality of the cut resulting from the application of recursive bipartitioning and direct multiway partitioning, as implemented in Metis 5.0.2. Our test cases will be the ’helicopter’ (original name ’commanche dual’) and the ’skirt’ example.
Use the incomplete Bench metis.m for your implementation. Compare the cut obtained from Metis 5.0.2 after applying recursive bisection and direct multiway partitioning for the graphs in question. Consult the Metis manual, and type help metismex in your MATLAB command line to familiarize yourself with the way the Metis recursive and direct multiway partitioning functionalities should be invoked. Summarize your results in Table 3 for 16 and 32 partitions. Comment on your results. Which one did you expect to perform better and why? Was your guess confirmed by the results of the example meshes? Visualize the partitioning results for both graphs for 32 partitions. Use the ”Rotate 3D” option from the MATLAB figure selection “Tools” to better visualize the output.
Table 3: Comparing the number of cut edges for recursive bisection and direct multiway partitioning in Metis 5.0.2.
Partitions helicopter skirt
16 – recursive bisection
16-way direct partition
32 – recursive bisection
32-way direct partition
Quality of the code and of the report [15 Points]
The highest possible score of each project is 85 points and up to 15 additional points can be awarded based on the quality of your report and code (maximum possible grade: 100 points). Your report should be a coherent document, structured according to the template provided on iCorsi. If there are theoretical questions, provide a complete and detailed answer. All figures must have a caption and must be of sufficient quality (include them either as .eps or .pdf). If you made a particular choice in your implementation that might be out of the ordinary, clearly explain it in the report. The code you submit must be self-contained and executable, and must include the set-up for all the results that you obtained and listed in your report. It has to be readable and, if particularly complicated, well-commented.
Additional notes and submission details
In-class assistance
If you experience difficulties in solving the problems above, please join us in class either on Tuesdays 15:30-17:00 or on Wednesdays 13:30-15:00 in room C1.03.
References
[3] U. Elsner. Graph Partitioning: A Survey. Technical report, Technische Universitat Chemnitz, Germany, 97-27,¨ 1997.
Press.
[5] George Karypis and Vipin Kumar. Parallel multilevel k-way partitioning scheme for irregular graphs. In Proceedings of the 1996 ACM/IEEE Conference on Supercomputing, Supercomputing ’96, page 35–es, USA, 1996. IEEE Computer Society.
[6] B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291–307, Feb 1970.
