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?

2 thoughts on “Spectral Partitioning, Part 1 The Graph Laplacian

Leave a Reply

Your email address will not be published. Required fields are marked *