Are these three different notions of a graph Laplacian?

Question

I seem to see three different things that are being called the Laplacian of a graph,

• One is the matrix $L_1 = D - A$ where $D$ is a diagonal matrix consisting of degrees of all the vertices and $A$ is the (possibly signed) adjacency matrix.

• The other is to say that the matrix $L_2$ is a $\vert V \vert \times \vert V \vert$ matrix such that $(L_2)_{ii} = deg(v_i)$ and $(L_2)_{ij} = -\frac{1}{\sqrt{deg(v_i)deg(v_j) } }$

• The third is to say that $L_3 = BB^T$ (where $B$ is the incidence matrix)

Can someone kindly clarify what is the relation between these three pictures (and or may be all these are the same somehow!?). [..for example for which of them would the positive-semi-definiteness and the the heat-equation intuition hold?...]

Answer 1

These are usually known as the Laplacian, the normalized Laplacian and the unsigned Laplaian. All three are positive semidefinite. If the graph is regular, they all provide the same information.

If the graph is not regular they are, in general, independent. The normalized Laplacian is the right tool for the analysis of random walks. The spectral information provided by the unsigned Laplacian is equivalent to what you get from the spectrum of the line graph of the original graph.

To expand on the last comment: if $B$ is the vertex-edge incidence matrix, then $BB^T$ is the unsigned Laplacian and $B^TB=2I+A(L(G))$. This appears for example on page 16 of the first edition of Cvetkovic et al "Spectra of Graphs", but it is older. (I know I did not learn it from there.) Note that it follows that $BB^T$ and $B^TB$ have the same non-zero eigenvalues with the same multiplicities.

Answer 2

Let me comment a bit on Chris Godsil's answer. The fact that $L_1\ne L_3$ follows from the easy-to-check fact that $L_1=\mathcal I\mathcal I^T$, where $\mathcal I$ is the incidence matrix of an arbitrary orientation of the graph. The nullity of $\mathcal I^T$ is the number of connected components of the graph, whereas the nullity of the transpose of the signless incidence matrix (which is what you presumably denote by $B^T$) is the number of bipartite connected components. So these matrices are clearly different. However, as pointed out by Chris Godsil, they yield the same information in the regular case: the difference is that the upper end of the spectrum of $L_3$ corresponds to the lower end of the spectrum of $L_1$, and vice versa: This was in fact, as far as I can judge, the main reasons for the introduction of $L_3$ in a 1994 paper by Desai and Rao.

The fact that the nullities of $L_1,L_2$ coincide can be seen by an argument that might be interesting for your purposes: $L_2$ (or at least the matrix $L_2:=D^{-\frac12}L_1 D^{-\frac12} $ suggested in the comment by Aaron Meyerowitz) is similar to $\tilde{L}_2:=D^{-1}L_1$, which is often called normalized Laplacian as well. It turns out that both $L_1,\tilde{L}_2$ can be seen as Fréchet derivatives of the same energy functional $\mathcal E:f\mapsto\|\mathcal I^T f\|_{\ell^2(E)}^2$, but with respect to two different Hilbert spaces -- more precisely, to the vector space $\mathbb R^V$ endowed with the inner products $$ (f|g):=\sum_{v\in V}f(v)g(v) $$ and $$ (f|g):=\sum_{v\in V}f(v)g(v)\deg(v) $$ respectively (obvious modifications are needed in the case of infinite graphs).

Answer 3

For analyzing spectral properties (spectral gap for instance), it is more convenient to use the normalized version since the spectra are kind of independent of the number of vertices.