## 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 [2].

Recently, the graph partition problem has gained importance due to its application for clustering and detection of

cliques in social, pathological, and biological networks. Since graph partitioning is an NP-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 algorithm, 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 not on an arbitrary initial

partition. The most common example is spectral partitioning, where a partition is derived from the spectrum of the

graph Laplacian matrix. In cases where the nodes of the graph are associated with a coordinate list, inertial bisection

is also a frequent choice of partitioning method.

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 ∈ R

n

such

that

xi =

1 , i ∈ V1,

0 , i ∈ V2.

Some of the n nodes of the graph are connected via m edges, each of which has a positive weight associated with it,

thus

wij =

(

> 0, if vi connected to vj ,

= 0 otherwise.

A bisection is computed using the eigenvector associated with the second smallest eigenvalue of the graph Laplacian

matrix L ∈ R

n×n

, which encodes the degree di =

Pn

j=1 wij , 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 ∈ R

n×n

and the degree matrix D ∈ R

n×n

as follows. The graph Laplacian is a symmetric positive semidefinite

1

Numerical Computing, Fall Semester 2022

Lecturer: Prof. O. Schenk

Assistants: E. Vecchi, L. Gaedke-Merzhauser ¨

W := X

i∈A,j∈B

wij =

0 0.1 0 0.2

0.1 0 0.4 0.7

0 0.4 0 0.8

0.2 0.7 0.8 0

, D := Xn

j=1

wij =

0.3 0 0 0

0 1.2 0 0

0 0 1.2 0

0 0 0 1.7

L := D − W =

0.3 −0.1 0 −0.2

−0.1 1.2 −0.4 −0.7

0 −0.4 1.2 −0.8

−0.2 −0.7 −0.8 1.7

.

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

1

. 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 [4].

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 kuk2 =

p

u

2

1 + u

2

2

1

Please note that we are now using the variable wi to refer to an eigenvector as opposed to the previous vi to not confuse it with a vertex vi

of a graph.

2

Numerical Computing, Fall Semester 2022

Lecturer: Prof. O. Schenk

Assistants: E. Vecchi, L. Gaedke-Merzhauser ¨

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 . bisection of G

7: end function

such that ` = {P + αu | α ∈ R} (Figure 2). Let each node vi have the coordinates (xi

, yi). We then choose

x =

1

n

Xn

i=1

xi

, y =

1

n

Xn

i=1

yi

, (1)

as the center of mass lies on the line `. Finally, we need to compute u in order to minimize the sum of distances

Xn

i=1

d

2

i =

Xn

i=1

(xi − x)

2 + (yi − y)

2 − (u1(xi − x) + u2(yi − y))2

=

Xn

i=1

(xi − x)

2

!

| {z }

Sxx

u

2

1 +

Xn

i=1

(yi − y)

2

!

| {z }

Syy

u

2

2 + 2 Xn

i=1

(xi − x)(yi − y)

!

| {z }

Sxy

u1u2

= u

T

Sxx Sxy

Sxy Syy

u = u

TMu, (2)

where Sxx, Sxy, Syy are the sums as defined in the previous line. The resulting matrix M is symmetric2

, 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 [4] and references therein for a thorough overview of the inertial method.

Figure 2: Illustration of inertial bisection in 2D [4].

2We can obtain matrix M by rewriting the quadratic form Q(u1, u2) in matrix notation.

3

Numerical Computing, Fall Semester 2022

Lecturer: Prof. O. Schenk

Assistants: E. Vecchi, L. Gaedke-Merzhauser ¨

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 of the graph around line 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

i∈V1,j∈V2

wij . (3)

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

T x = kxk

2

2 = |V1|. (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,

b

k = max

V

k

i

V

k

i

Vek

, (5)

where Ve is the average partition weight. The load imbalance b

k = 1 + b

k

r ≥ 1, where b

k

r ≥ 0 characterizes the

deviation from obtaining an evenly balanced partitioning. The optimal value for b

k

r

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 b

k

r

is

bounded from above by a desired threshold.

Software tools

We will use one external partioning software tool for this project. METIS3

[6], 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

3http://glaros.dtc.umn.edu/gkhome/metis/metis/overview

4

Numerical Computing, Fall Semester 2022

Lecturer: Prof. O. Schenk

Assistants: E. Vecchi, L. Gaedke-Merzhauser ¨

by swapping nodes between the partitions that lie in the neighborhood of the cut. Kernighan and Lin [7] 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 [5].

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. We will interface Julia and METIS

through the Julia wrapper Metis.jl which allow us to use the functions METIS PartGraphRecursive and

METIS PartGraphKway with the same arguments and argument order described in the Metis manual.

The assignment

You can find the graph partitioning toolbox Tools on the Moodle webpage. This toolbox contains Julia 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.jl and the other packages, you can install the packages from the Julia package manager

active session, which you can access by pressing the key ] in the REPL:

julia> ]

(Project) pkg> add DelimitedFiles MAT Arpack LinearAlgebra Metis Random SparseArrays

Statistics Graphs SGtSNEpi GLMakie Colors CairoMakie PrettyTables

For more information about packages management and environement, please refer to the Pkg.jl documentation. After

installing the required packages, please remember to import them:

julia> using DelimitedFiles, MAT, Arpack, LinearAlgebra

julia> using Random, SparseArrays, Statistics

julia> using Metis, Graphs, SGtSNEpi, GLMakie

julia> using Colors, CairoMakie, PrettyTables

The file add paths.jl contains everything which is needed to run the provided code. When you start working on

the mini-project, please include it as:

include(“path/to/add_paths.jl”);

and you are ready to go. Remember to include this file each time you make updates to the provided files (e.g.,

part spectral.jl or part inertial.jl) and you want to re-run bench bisection.jl.

1. Implement various graph partitioning algorithms [50 points]

• Open the Julia file bench bisection.jl and familiarize yourself with the code.

• Implement spectral graph bisection based on the entries of the Fiedler eigenvector. Use the incomplete Julia

file part spectral.jl for your solution. Justify the threshold you chose.

• 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 Julia file

part inertial.jl for your solution.

• Report the bisection edgecut for all toy meshes that are loaded in the script bench bisection.jl. Use

Table 1 to report these results. Comment on your results.

5

Numerical Computing, Fall Semester 2022

Lecturer: Prof. O. Schenk

Assistants: E. Vecchi, L. Gaedke-Merzhauser ¨

Table 1: Bisection results

Mesh Coordinate Metis 5.0.2 Spectral Inertial

grid(12, 100) 12

grid(100, 12) 12

grid(100, 12, pi/4)

gridt(50)

gridt(40)

Smallmesh

Tapir

Eppstein

2. Recursively bisecting meshes [20 points]

We will now partition 2D graphs emerging from structural engineering matrices of NASA, available in the SuiteSparse

Matrix Collection (SSMC) [3]. A robust algorithm that allows us to create a 2

l partition, with l being an integer, is

presented in Algorithm 3. It uses the recursive function Recursion that takes as inputs the part C

0 of the graph

to partition, the number of parts p

0

into which we will partition C

0

, and the index (an integer) of the first part of the

partition of C

0

into the final partitioning result Gp. In practize, only strongly balanced bisection routines are utilized

within this algorithm [1].

Algorithm 3 Recursive bisection.

Require: G(V, E),

Ensure: A p-way partition of G

1: Gp = {C1, . . . , Cp}

2: p = 2l . p is a power of 2

3: function RECURSIVEBISECTION(graph G(V, E), number of parts p)

4: function RECURSION(C

0

, p0

, index)

5: if p

0

is even then . If p

0

is even, a bisection is possible

6: p

0 ← p

0

2

7: (C

0

1

, C0

2

) ← bisection(C

0

)

8: RECURSION(C

0

1

, p0

,index)

9: RECURSION(C

0

2

, p0

,index+k

0

)

10: else . No more bisection possible, C

0

is in a partition of G

11: Cindex ← C

0

12: end if

13: end function

14: RECURSION(C, p, 1)

15: return Gp . Gp is a partition of G in p = 2l parts

16: end function

This algorithm is implemented in the file recursive bisection.jl of the toolbox. Utilize the script bench recusriveto recursively bisect the finite element meshes loaded in 8 and 16 subgraphs. Use your inertial and spectral partitioning implementations, as well as the coordinate partitioning and the METIS bisection routine. Summarize your results

in 2 and comment about these results. Finally, visualize the results for p = 16 for the case ”crack”. An example for

spectral recursive partitioning is illustrated in Figure 3.

6

Numerical Computing, Fall Semester 2022

Lecturer: Prof. O. Schenk

Assistants: E. Vecchi, L. Gaedke-Merzhauser ¨

Table 2: Edge-cut results for recursive bi-partitioning.

Case Spectral Metis 5.1.0 Coordinate Inertial

mesh3e1

airfoil1

3elt

barth4

crack

Figure 3: Left: The finite element mesh ”crack” with 10240 nodes and 30380 edges. Right: 16-way recursive bisection

of the mesh using Metis 5.1.0. Number of cut edges: 1186.

3. Comparing recursive bisection to direct k-way partitioning [15 points]

Recursive bisection is highly dependent on the decisions made during the early stages of the process, and also suffers

from the lack of global information. Thus, it may result in suboptimal partitions [8]. This necessitated the development

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 [6]. We will compare the quality of the cut resulting from the application of

recursive bipartitioning and direct multiway partitioning as implemented in Metis 5.1.0. Our test cases will be the

commanche dual and the skirt example.

Use the incomplete file bench metis.jl for your implementation. Compare the cut obtained from Metis 5.1.0 after

applying recursive bisection and direct multiway partitioning for the graphs in question. Consult the Metis manual

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.

7

Numerical Computing, Fall Semester 2022

Lecturer: Prof. O. Schenk

Assistants: E. Vecchi, L. Gaedke-Merzhauser ¨

Table 3: Comparing the number of cut edges for recursive bisection and direct multiway partitioning in Metis 5.1.0.

Partitions Helicopter Skirt

16-recursive bisection

16-way direct bisection

32-recursive bisection

32-way direct bisection

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

Summarize your results and experiments for all exercises by writing an extended LaTeX report, by using the template provided on iCorsi (https://www.icorsi.ch/course/view.php?id=14666). Submit your gzipped

archive file (tar, zip, etc.) – named project number lastname firstname.zip/tgz – on iCorsi (see [NC

2022] Project 3 – Submission Graph Partitioning) before the deadline. Submission by email or through any other

channel will not be considered. Late submissions will not be graded and will result in a score of 0 points for that

project. You are allowed to discuss all questions with anyone you like, but: (i) your submission must list anyone you

discussed problems with and (ii) you must write up your submission independently. Please remember that plagiarism

will result in a harsh penalization for all involved parties.

In-class assistance

If you experience difficulties in solving the problems above, please join us in class either on Tuesdays (16:30-18:15)

or on Wednesdays (14:30-16:15) in room C1.03.

References

[1] C.E. Bichot and P. Siarry. Graph Partitioning. ISTE. Wiley, 2013.

[2] Aydin Buluc, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. Recent Advances in Graph

Partitioning, pages 117–158. Springer International Publishing, Cham, 2016.

[3] Timothy A. Davis and Yifan Hu. The university of florida sparse matrix collection. ACM Trans. Math. Softw.,

38(1):1:1–1:25, December 2011.

[4] U. Elsner. Graph Partitioning: A Survey. Technical report, Technische Universitat Chemnitz, Germany, 97-27, ¨

1997.

8

Numerical Computing, Fall Semester 2022

Lecturer: Prof. O. Schenk

Assistants: E. Vecchi, L. Gaedke-Merzhauser ¨

[5] C. M. Fiduccia and R. M. Mattheyses. A linear-time heuristic for improving network partitions. In Proceedings

of the 19th Design Automation Conference, DAC ’82, pages 175–181, Piscataway, NJ, USA, June 1982. IEEE

Press.

[6] 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.

[7] B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical

Journal, 49(2):291–307, Feb 1970.

[8] Horst D. Simon and Shang-Hua Teng. How good is recursive bisection? SIAM J. Sci. Comput., 18(5):1436–1445,

September 1997.

9