Graph Partitioning

Required Readings

• Course Notes

Optional

Requires VPN

• A separator theorem for planar graphs
• An efficient heuristic procedure for partitioning graphs
• Parallel multilevel k-way partitioning scheme for irregular graphs
• Algebraic connectivity of graphs
• Partitioning sparse matrices with eigenvectors of graphs
• An experimental comparison of Pregel-like graph partitioning systems
• Berkeley Lectures
• Berkeley Lectures Continued

Summary

• The Graph Partitioning Problem
• Graph Bisection and Planar Separators
• Kernighan-Lin
• Graph Coarsening
  • Matching
• Spectral Partitioning
  • Laplacian Example
  • Handy Factoids
  • Putting it all together
  • Spectral Partition Algorithm

The Graph Partitioning Problem

Given: a graph G with vertices V and edges E, and a number of partitions P

Output a vertex partition $V = V_0 \cup V_1 \cup \ldots \cup V_{p-1}$ such that:

• Partitions are disjoint
  • $\left(\forall V_i \in V\right)\left(\forall V_j \in V\right)\left(V_i \cap V_j = \empty \right)$
• Partitions are roughly balanced
  • $|V_i| \approx |V_j|$
• Minimize number of cuts
  • $min\left( E_{cut} \equiv {(u,v) \mid u \in V_i,, v \in V_j,, i \neq j} \right)$

Graph Bisection and Planar Separators

Graph partitioning is NP-Complete

NEED HEURISTICS

Bisection
Recursively divide graph in half until you get P partitions

Planar
A graph that can be drawn on a plane with no edge crossings

A planar graph G=(V,E) with n vertices, has a disjoint partition $V = A \cup S \cup B$
Liptun & Tarjan

• S seperates A and B
  • Removing S means there are no connections between A and B
• $|A|, |B| \le \frac{2}{3}n$
• $|S| \le 2\sqrt{2}\sqrt{n} = O\sqrt{n}$

You can find a separator by using a BFS and using half of the max distance

Kernighan-Lin

Given a partition of a subgraph, the Cost is the number of edges between the subgraphs.

Imagine swapping small subsets of each subgraph of roughly equal size

$\text{let} , x_1 \subseteq V_1, , x_2 \subseteq V_2, , \text{with} , \lvert x_1 \rvert = \lvert x_2 \rvert$

External Cost:

$E_1 \left( a \in V_1 \right) \equiv \text{Num of edges}\left(a,b \in V_2 \right)$

$E_2 \left( b \in V_2 \right) \equiv \text{Num of edges}\left(b,a \in V_1 \right)$

Internal Cost:

$I_1 \left( a \in V_1 \right) \equiv \text{Num of edges}\left(a,i \in V_1 \right)$

$I_2 \left( b \in V_2 \right) \equiv \text{Num of edges}\left(b,j \in V_2 \right)$

Cost of a partition:

$Cost(V_1, V_2) = Cost\left( V_1 - {a}, V_2 - {b} \right) + E_1(a) + E_2(b)- C_{a,b}$

$C_{a,b} = \begin{cases} 1 & \text{when}, \exists(a,b) \ 0 & \text{when}, \not\exists(a,b) \end{cases}$

We subtract $C_{a,b}$ because if there is an edge between a and b, then it would have been counted twice, once for the external edges of a and once for the external edges of b. Subtracting it means we only keep one counting.

Cost after swap:

$Cost\left(\hat V_1, \hat V_2 \right) = Cost\left( V_1 - {a}, V_2 - {b} \right) + I_1(a) + I_2(b) + C_{a,b}$

Change in cost:

$Cost(V_1,V_2) - Cost(\hat V_1, \hat V_2) = E_1(a) + E_2(b) - I_1(a) - I_2(b) - 2C_{a,b}$

$\phantom{Cost(V_1,V_2) - Cost(\hat V_1, \hat V_2)} \equiv gain\left( a \in V_1, b \in V_2 \right)$

Graph Coarsening

Replace graph with smaller graph that has fewer nodes and edges but still somehow “looks-like” the original graph. Repeat this until you get a version of the graph that is able to be partitioned quickly. You partition that graph then reverse the steps to get the original graph.

Similar to scaling down the resolution of an image, performing some transformation on the scaled down version, then upscaling back to the original resolution.

1. Identify some subset of the vertices in the graphs to merge/collapse.
2. Replace subset with a “super vertex”
3. Assign a weight to the super vertex equal to the number of nodes that constitute the super vertex
4. Any two edges that got mapped to a single edge in this process now has a weight equal to the sum of the original two edges.

Matching

matching
A subset of a graph of edges with no common endpoints

maximal matching
A matching to which you cannot add anymore edges

maximum matching
The larges maximal matching

If you find a separator in the coarsened graph, then all the mapped edges/nodes from the original graphs of the separator create the projected separator.

If the projected separator has a triangle (or greater shape), then you will need to refine your separator.

Spectral Partitioning

Take an incidence matrix (as opposed to an adjacency matrix) to represent a graph

	0	1	2	3
0	1	-1
1	1		-1
2	1			-1
3		-1	1
4			1	-1
5		-1		1

$$\text{Graph Laplacian},, L(G) \equiv C^T \cdot C = D - W$$

Diagonals of the $C^T \cdot C$ tell us the count of incident edges. The off-diagonals tell us the presence of an edge, without direction (converting a directed graph to an undirected graph).

THe diagonals of the overal Laplacian tell us the degree of each vertex. The off-diagonals mark all the edges (i.e. the adjacency matrix of the undirected graph).

$D = \left( \begin{array}{cc} d_0 & & & \ & d_1 & & \ & & d_2 & \ & & & d_3 \end{array} \right) = \text{ degrees}$

$D \equiv \left[ \begin{array}{cc} 3 & & & \ & 3 & & \ & & 3 & \ & & & 3 \end{array} \right]$

$W \equiv \left[ \begin{array}{cc} 0 & 1 & 1 & 1 \ 1 & 0 & 1 & 1 \ 1 & 1 & 0 & 1 \ 1 & 1 & 1 & 0 \end{array} \right] = \text{ adjacency}$

$L(G) = D - W \equiv \left[ \begin{array}{cc} 3 & -1 & -1 & -1 \ -1 & 3 & -1 & -1 \ -1 & -1 & 3 & -1 \ -1 & -1 & -1 & 3 \end{array} \right]$

Laplacian Example

“0 has 7 edges”

	0	1	2	3	4	5	6	7	8
0	7
1		3
2			3
3				2
4					1
5						2
6							1
7								1
8									2

“Every where there is an undirected edge, put a -1”

	0	1	2	3	4	5	6	7	8
0	7	-1	-1	-1	-1	-1	-1		-1
1	-1	3	-1						-1
2	-1	-1	3	-1
3	-1		-1	2
4	-1				1
5	-1					2		-1
6	-1						1
7						-1		1
8	-1	-1							2

Matrix should be symmetrical, and rows and columns should sum to zero.

Handy Factoids

Mostly from Pothen et al, 1990

• L(G) is symmetric
• L(G) has real-valued, non-negative eigenvalues and real-valued, orthogonal eigenvectors.
• Graph has k connected components if and only iff the k smallest eigenvalues are identically zero. (Fiedler, 1973)
  • Spectrum of L(G) $\iff$ Connectivity of G
• Number of cut edges = $\frac{1}{4}x^TL(G)x$

$x^T L(G)x = \sum_{i,j}l_{ij}x_ix_j$

$\phantom{x^T L(G)x} = \begin{array}{l}\phantom{+}\sum_{i = j}l_{ij}x_ix_j \ +\sum_{i,j \in V_+, i \neq j}l_{ij}x_ix_j \ +\sum_{i,j \in V_-, i \neq j}l_{ij}x_ix_j \ +\sum_{i \in V_+, j \in V_-}l_{ij}x_ix_j \ +\sum_{i \in V_-, j \in V_+}l_{ij}x_ix_j \end{array}$

$\phantom{x^T L(G)x} = \begin{array}{l}\phantom{+}\sum_{i = j}l_{ii}x_i^2 \ +\sum_{i,j \in V_+, i \neq j}l_{ij}x_ix_j \ +\sum_{i,j \in V_-, i \neq j}l_{ij}x_ix_j \ +\sum_{i \in V_+, j \in V_-}l_{ij}x_ix_j \ +\sum_{i \in V_-, j \in V_+}l_{ij}x_ix_j \end{array}$

$\phantom{x^T L(G)x} = \begin{array}{l}\phantom{+}\sum_{i = j}d_{i} \cdot 1 \ +\sum_{i,j \in V_+, i \neq j}l_{ij}x_ix_j \ +\sum_{i,j \in V_-, i \neq j}l_{ij}x_ix_j \ +\sum_{i \in V_+, j \in V_-}l_{ij}x_ix_j \ +\sum_{i \in V_-, j \in V_+}l_{ij}x_ix_j \end{array}$

$\phantom{x^T L(G)x} = \begin{array}{l}\phantom{+}2 \times \text{ number of edges } \ +\sum_{i,j \in V_+, i \neq j}l_{ij}x_ix_j \ +\sum_{i,j \in V_-, i \neq j}l_{ij}x_ix_j \ +\sum_{i \in V_+, j \in V_-}l_{ij}x_ix_j \ +\sum_{i \in V_-, j \in V_+}l_{ij}x_ix_j \end{array}$

$\phantom{x^T L(G)x} = \begin{array}{l}\phantom{+}2 \times \text{ number of edges } \ +\sum_{i,j \in V_+, i \neq j}l_{ij}-1 \cdot 1 \cdot 1 \ +\sum_{i,j \in V_-, i \neq j}l_{ij}-1 \cdot 1 \cdot 1 \ +\sum_{i \in V_+, j \in V_-}l_{ij}-1 \cdot 1 \cdot -1 \ +\sum_{i \in V_-, j \in V_+}l_{ij}-1 \cdot -1 \cdot 1 \end{array}$

$\phantom{x^T L(G)x} = \begin{array}{l}\phantom{+ -}2 \times \text{ number of edges } \ +-2 \times \text{ number of edges in } V_+ \ +-2 \times \text{ number of edges in } V_- \ +-2 \times \text{ number of edges from } V_+ \text { to } V_- \ +-2 \times \text{ number of edges from } V_- \text { to } V_+ \ \end{array}$

Putting it all together

1. Start witha a graph
2. Construct it’s laplacian
3. Create a partition of graph

The partition correlates to a partition vector.

$V = V_+ \cup V_- \implies x = \begin{cases} +1 & i \in V_+ \ -1 & i \in V_- \end{cases}$

To know the number of cut edges in graph: $\frac{1}{4}x^TL(G)x$

We want:

$\min{\frac{1}{4}x^TL(G)x} , { x \mid \sum_ix_i = 0, x_i = \pm 1 }$

This is NP-Complete…

If we relax the requirement that we assign exactly a $\pm 1$ to every vertex, then we can use Courant-Fisher Minimax Theorem to get:

$\frac{1}{4}y^TL(G)y = \frac{1}{4}n \overrightharpoon{q_1^T}L(G)\overrightharpoon{q_1}$

$\phantom{\frac{1}{4}y^TL(G)y} = \frac{1}{4}n \lambda_1$

Or vector that minimizes the number of cut edges is related to the eigenvalue of the second smallest eigenvector.

Spectral Partition Algorithm

1. Compute laplacian for graph
2. Compute $\left( \lambda_1 , \overrightharpoon{q_1} \right)$ eigenpair of L(G)
3. Choose $x_i \leftarrow \text{sign}\left(\overrightharpoon{q_1 (i)}\right)$