The Graph Laplacian

--Jason Cantarella, January 2021
MATH/CSCI 4690/6690 Course Materials

Previous code

We start by reloading some of our previous code:

DegreeMatrix[G_] := DiagonalMatrix[VertexDegree[G]]

GraphFunctionPlot[𝒢_?GraphQ,p_,scale_] := Block[{low,hi,faces},
low = scale(Append[#,0] & /@GraphEmbedding[𝒢]);
hi = scale(Append @@@ Transpose[{GraphEmbedding[𝒢],p}]);
faces = Flatten /@ Transpose[{#,VertexCount[𝒢]+(Reverse/@#)}]&@ Map[VertexIndex[𝒢,#]&,List@@@EdgeList[𝒢],{2}]; 
Show[GraphPlot3D[Graph[VertexList[𝒢],EdgeList[𝒢],VertexCoordinates->#],VertexSize->0.05]& /@ {low,hi},
Graphics3D[{Opacity[0.9],LightBlue,GraphicsComplex[Join[low,hi],Polygon[faces]]}]
,ImageSize->Medium]
]/; TrueQ[Length[p] == VertexCount[𝒢]]

GraphFunctionPlot[𝒢_?GraphQ,p_] := GraphFunctionPlot[𝒢,p,1.0]

Defining the graph Laplacian

Now we can define the graph Laplacian:

GraphLaplacian[G_] := DegreeMatrix[G] - AdjacencyMatrix[G]

and check the example we did in the notes:

GraphLaplacian[CycleGraph[4]] // MatrixForm

GraphPlot[CycleGraph[4],VertexLabels->"Name"]

The quadratic form (Subscript[Q, (Subscript[L, G])]).

We can even check our proposition about the quadratic form associated to the graph Laplacian:

QLG[G_,x_] := Dot[x,GraphLaplacian[G].x]

For instance, for the path graph:

Expand@QLG[PathGraph[Range[4]],{x1,x2,x3,x4}]

Expand[(((x1-x2))^2)+(((x2-x3))^2)+(((x3-x4))^2)]

Are these equal?

Simplify[QLG[PathGraph[Range[4]],{x1,x2,x3,x4}] == Expand[(((x1-x2))^2)+(((x2-x3))^2)+(((x3-x4))^2)]]

The spectrum of our example graphs.

The set of eigenvalues of a symmetric matrix is called the “spectrum” of the matrix, and if the matrix is the graph Laplacian, we call these the “spectrum” of the graph. This is what motivates the title “Spectral Graph Theory”.  (Alas, we won’t have any actual spectres, but on the plus side, we are probably safe from S.P.E.C.T.R.E.)

We start by looking at the spectrum of our basic examples:

Spectrum[G_] := Reverse@Eigenvalues[GraphLaplacian[G]]

Spectrum[PathGraph[Range[4]]]

Spectrum[CycleGraph[4]]

Spectrum[CompleteGraph[4]]

We can see that 
	
		all the spectra include zero
		the spectra have 1, 2, or 3 repeated lowest eigenvalues
		the spectra seem to be increasing as the graphs become more connected

PathGraph[Range[4]]

CycleGraph[4]

CompleteGraph[4]

Looking at the eigenvectors.

We can think of the eigenvectors as functions on the graph -- these are vectors in (ℝ^V), which is our space of vertex weights.

EVD[G_] := Manipulate[{MapAt[Style[#,Background-> LightBlue]&,N@Spectrum[G],i] // MatrixForm,
GraphFunctionPlot[G,(Reverse@Eigenvectors[1.0 GraphLaplacian[G]])[[i]]]},{i,1,VertexCount[G],1}]

EVD[CycleGraph[14]]

Spectral Graph Drawing.

We’ve been letting Mathematica decide how to draw our graphs. However, we have no guarantee that the drawings we produce are “natural” consequences of the structure of the graph.

One way to define a standard drawing of a graph is to use the eigenvectors as coordinates.

SpectralDrawing[G_,modes_] := Graph[VertexList[G],EdgeList[G],VertexCoordinates->Transpose@((Reverse@Eigenvectors[1.0GraphLaplacian[G]])[[modes]])]

N@Spectrum[CycleGraph[14]]

SpectralDrawing[CycleGraph[14],{12,13,14}]

Graph[LinguisticAssistant]

Spectrum[LinguisticAssistant]

SpectralDrawing[LinguisticAssistant,{2,3,4}]