# Spectral Partitioning, Part 1 The Graph Laplacian

For me, one of the most fascinating

classes of graph partitioning methods are the so-called spectral methods. That’s spectral as in rainbows,

not ghosts. Spectral methods go back to the linear

algebraic view of graphs, and they have what, for me, is a surprising

physics-based interpretation. We’ll get there, but first, let’s remind

ourselves about the connection between graph structure and certain matrices. Consider an unweighted,

directed graph such as this one. Let’s call this graph G. Now let’s represent it,

not by its adjacency matrix, but by an incidence matrix, C of G. In this form, each row is an edge,

and each column is a vertex. How do you mark edges? Let’s take this edge as an example. It points from vertex 0 to vertex 1. Let’s make it the first edge

in the incidence matrix, and let’s mark it using

the following convention. We’ll put a positive 1 at the source

vertex, and a -1 at the sink. Let me fill in the rest.>From this incidence matrix, let’s construct a new object

called the graph laplacian. We’ll define it as the product

of C transposed times C. To see what this product is, I want

you to compute it algebraically and then interpret it. Start by writing C as

a sequence of its m edges. Here’s C shown symbolically as a list of row vectors where each row

vector corresponds to an edge. Here’s what C transposed

times C would look like. Let’s multiply this out. That is, C transpose C is

the sum of a bunch of products. Each product is an edge,

represented as a column vector, multiplied by itself

represented as a rho vector. To see what this is saying, let’s take

a closer look at one of these products. Each e sub k is some edge,

let’s call it ij. Remember that it’s a vector with

a plus 1 in the Ith position and a minus 1 in the Jth position. So what about the product? This product will be a matrix,

and, in fact, this product will only have

non-zero entries in four places. Let’s do the diagonals first. A diagonal entry will either

be plus 1 times plus 1 or minus 1 times minus 1,

which in either case is just plus 1. In effect, the diagonals are tallying the number

of incident edges on each vertex. That’s the diagonals. What about the off diagonals? The off diagonals will always

multiply a positive 1 times a -1. In effect, the off diagonals

indicate the presence of an edge. However, since both j, i, and i, j are minus 1, you’ve effectively

lost the direction information. Put another way, the Graph Laplacian is telling you

something about the undirected form of the original graph, in the event

that the original graph was directed. Now this is what one of these products

tells us, but what about the sum? Well, let’s see. The diagonals count

the degree of each vertex. Let’s represent that by a diagonal

matrix D, where the diagonal entries are the degrees of each vertex, and

let’s say there are n vertices in all. The off diagonals mark all the edges. That’s basically just the adjacency

matrix of the undirected form of the graph. Remember, the adjacency

matrix would have a positive 1 anywhere there’s an edge

either connecting i, j or j, i. And, of course, to get minus 1s

in the off diagonal positions, we’ll subtract the adjacency matrix. Okay, so let’s construct

a Graph Laplacian on an example. Step one is to throw out the directions,

then build a diagonal matrix, D, that contains

the degrees of each vertex. This example isn’t very exciting

because every vertex has a degree of 3. Then build the adjacency matrix,

which marks all the edges. Again, this example isn’t very exciting

because it’s basically fully connected. So there are ones in all of

the off diagonal entries. Finally, the graph laplacian

is just D minus W. In this case, that’s this thing. Take a moment to contemplate

the Graph Laplacian. Once you’ve done so, you can move

onto a more interesting question of, how do I use this doohickey to

actually partition a graph?

very nice and clear explanation, thanks bro!

PERFECT