Reaves.dev

v0.1.0

built using

Phoenix v1.7.21

@rapscallionreaves Gitlab Posts Notes Talks Showcase About

Graph Partitioning

Stephen M. Reaves

::

 2024-11-30

Notes about Lecture 11 for CS-6220

Required Readings

Optional

Requires VPN

Summary

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=V0∪V1∪…∪Vp−1 V = V_0 \cup V_1 \cup \ldots \cup V_{p-1} such that:

  • Partitions are disjoint
    • (∀Vi∈V)(∀Vj∈V)(Vi∩Vj=∅) \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
    • ∣Vi∣≈∣Vj∣ |V_i| \approx |V_j|
  • Minimize number of cuts
    • min(Ecut≡{(u,v)∣u∈Vi, v∈Vj, i≠j}) 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∪S∪B 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∣≤23n |A|, |B| \le \frac{2}{3}n
  • ∣S∣≤22n=On |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

let x1⊆V1, x2⊆V2, with ∣x1∣=∣x2∣ \text{let} , x_1 \subseteq V_1, , x_2 \subseteq V_2, , \text{with} , \lvert x_1 \rvert = \lvert x_2 \rvert

External Cost:

E1(a∈V1)≡Num of edges(a,b∈V2) E_1 \left( a \in V_1 \right) \equiv \text{Num of edges}\left(a,b \in V_2 \right)

E2(b∈V2)≡Num of edges(b,a∈V1) E_2 \left( b \in V_2 \right) \equiv \text{Num of edges}\left(b,a \in V_1 \right)

Internal Cost:

I1(a∈V1)≡Num of edges(a,i∈V1) I_1 \left( a \in V_1 \right) \equiv \text{Num of edges}\left(a,i \in V_1 \right)

I2(b∈V2)≡Num of edges(b,j∈V2) 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(V1,V2)=Cost(V1−{a},V2−{b})+E1(a)+E2(b)−Ca,b Cost(V_1, V_2) = Cost\left( V_1 - {a}, V_2 - {b} \right) + E_1(a) + E_2(b)- C_{a,b}

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

We subtract Ca,b 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(V1,V2)=Cost(V1−{a},V2−{b})+I1(a)+I2(b)+Ca,b 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(V1,V2)−Cost(V1,V2)=E1(a)+E2(b)−I1(a)−I2(b)−2Ca,b 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}

Cost(V1,V2)−Cost(V1,V2)≡gain(a∈V1,b∈V2) \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

G00110->1220->2330->32->12->33->1
0123
01-1
11-1
21-1
3-11
41-1
5-11

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

Diagonals of the CT⋅C 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=(d0d1d2d3)= degrees D = \left( \begin{array}{cc} d_0 & & & \ & d_1 & & \ & & d_2 & \ & & & d_3 \end{array} \right) = \text{ degrees}

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

W≡[0111101111011110]= adjacency 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≡[3−1−1−1−13−1−1−1−13−1−1−1−13] 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

G22332->3002->00->3550->5660->6111->2444->0775->7888->08->1

“0 has 7 edges”

012345678
07
13
23
32
41
52
61
71
82

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

012345678
07-1-1-1-1-1-1-1
1-13-1-1
2-1-13-1
3-1-12
4-11
5-12-1
6-11
7-11
8-1-12

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 = 14xTL(G)x \frac{1}{4}x^TL(G)x

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

xTL(G)x=+∑i=jlijxixj+∑i,j∈V+,i≠jlijxixj+∑i,j∈V−,i≠jlijxixj+∑i∈V+,j∈V−lijxixj+∑i∈V−,j∈V+lijxixj \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}

xTL(G)x=+∑i=jliixi2+∑i,j∈V+,i≠jlijxixj+∑i,j∈V−,i≠jlijxixj+∑i∈V+,j∈V−lijxixj+∑i∈V−,j∈V+lijxixj \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}

xTL(G)x=+∑i=jdi⋅1+∑i,j∈V+,i≠jlijxixj+∑i,j∈V−,i≠jlijxixj+∑i∈V+,j∈V−lijxixj+∑i∈V−,j∈V+lijxixj \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}

xTL(G)x=+2× number of edges +∑i,j∈V+,i≠jlijxixj+∑i,j∈V−,i≠jlijxixj+∑i∈V+,j∈V−lijxixj+∑i∈V−,j∈V+lijxixj \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}

xTL(G)x=+2× number of edges +∑i,j∈V+,i≠jlij−1⋅1⋅1+∑i,j∈V−,i≠jlij−1⋅1⋅1+∑i∈V+,j∈V−lij−1⋅1⋅−1+∑i∈V−,j∈V+lij−1⋅−1⋅1 \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}

xTL(G)x=+−2× number of edges +−2× number of edges in V++−2× number of edges in V−+−2× number of edges from V+ to V−+−2× number of edges from V− to V+ \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+∪V−  ⟹  x={+1i∈V+−1i∈V− 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: 14xTL(G)x \frac{1}{4}x^TL(G)x

We want:

min⁡14xTL(G)x {x∣∑ixi=0,xi=±1} \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 ±1 \pm 1 to every vertex, then we can use Courant-Fisher Minimax Theorem to get:

14yTL(G)y=14nq1T⇀L(G)q1⇀ \frac{1}{4}y^TL(G)y = \frac{1}{4}n \overrightharpoon{q_1^T}L(G)\overrightharpoon{q_1}

14yTL(G)y=14nλ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 (λ1,q1⇀) \left( \lambda_1 , \overrightharpoon{q_1} \right) eigenpair of L(G)
  3. Choose xi←sign(q1(i)⇀) x_i \leftarrow \text{sign}\left(\overrightharpoon{q_1 (i)}\right)