From graph laplacian to hodge laplacian

Preface

Graph laplacian is familiar to computation science researcher, with which we can perform spectral analysis such as diffusion map, eigenmap or spectral clustering. Here, we discuss how to generalize the graph laplacian to it's high-order form, i.e., Hodge laplacian.

Graph laplacian

In the previous post we know that the graph laplacian can be obtianed by degree matrix \(D\) and adjacency matrix \(A\) such that: \[\begin{equation} L_0 = D - A \end{equation}\]

We can find the adjacency matrix and degree matrix of the graph blow with nine vertices:

such that:

\[\begin{equation} A = \begin{array}[r]{c |c c c c c c c c c } & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline 1& 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 2& 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 3& 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 4& 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\ 5& 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0\\ 6& 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0\\ 7& 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 8& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 9& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ \end{array} \end{equation}\]

and

\[\begin{equation} D = \begin{array}[r]{c |c c c c c c c c c } & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline 1& 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 2& 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 3& 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 4& 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0\\ 5& 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0\\ 6& 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0\\ 7& 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 8& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 9& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{array} \end{equation}\]

And the graph laplacian thus can be calculated as:

\[\begin{equation} L_0 = D - A = \begin{array}[r]{c |c c c c c c c c c } & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline 1& 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 2& -1 & 2 & -1 & 0 & 0 & 0 & 0 & 0 & 0\\ 3& 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 4& 0 & 0 & 0 & 2 & -1 & -1 & 0 & 0 & 0\\ 5& 0 & 0 & 0 & -1 & 2 & -1 & 0 & 0 & 0\\ 6& 0 & 0 & 0 & -1 & -1 & 3 & -1 & 0 & 0\\ 7& 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0\\ 8& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1\\ 9& 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1\\ \end{array} \end{equation}\]

However, there's anoth way to represent the graph laplacian. Before that, we first introduce the incidence matrix of a graph. First, we can convert an undirected graph to be directed just assign the direction of edges by book keeping order. Next, let's construct the incidence matrix, each row represent a vertex, and each colum is an edge. We set the entry to be 1 if the the edge enter the vertex -1 when leave the vertex. Set 0 if there's no connection between a vertex and an edge. Thus the incidence matrix of a graph \(G\) is \(B\) such that: \[\begin{equation} B_1 = \begin{array}[r]{c | c c c c c c c} & \cdots & [4,5] & [4,6]& [5,6]& [6,7]& \cdots\\ \hline \vdots & \cdots & & \cdots & & \cdots & \\ 4 & \cdots & -1 & -1 & 0 & 0 & \cdots\\ 5 & \cdots & 1 & 0 & -1 & 0 & \cdots\\ 6 & \cdots & 0 & 1 & 1 & -1 & \cdots\\ 7 & \cdots & 0 & 0 & 0 & 1 & \cdots\\ \vdots & \cdots & & \cdots & & \cdots & \\ \end{array} \end{equation}\] Next, let construct graph laplacian matrix using \(B_1\). Actually, the graph laplacian is： \[\begin{equation} L_0=B_1 B_1^\top = \begin{array}[r]{c |c c c c c c c c c } & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline 1& 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 2& -1 & 2 & -1 & 0 & 0 & 0 & 0 & 0 & 0\\ 3& 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 4& 0 & 0 & 0 & 2 & -1 & -1 & 0 & 0 & 0\\ 5& 0 & 0 & 0 & -1 & 2 & -1 & 0 & 0 & 0\\ 6& 0 & 0 & 0 & -1 & -1 & 3 & -1 & 0 & 0\\ 7& 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0\\ 8& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1\\ 9& 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1\\ \end{array} \end{equation}\] As we can see that, \(L_0\) is the same as the that obtained from degree matrix and adjacency matrix.

Zero eigenvaules of graph laplacian

We know that for the application of diffusion map or spectral analysis, we have to drop the first eigenvector due to its same values and the eigenvaule is 0. The second eigenvector is also called fidler vector. However, these applications usually created a connected graph. Since the graph we show here is an unconnected graph. We can stop here to take a guess: Is the zero eigenvaule still there, or if so, how many zero eigenvaules?

Now, let's perform the eigenvaule decomposition that: \[\begin{equation} L_0 = Q\Lambda Q^\top \end{equation}\]

Interestingly, the top 3 eigenvalues are all zero and we also have 3 connected components in the graph. Is this a coincidence or a property of graph laplacian decomposition?

Furthermore, the top 3 eigenvectors corresponding to the zero eigenvaules are also interesting. Notice that the first eigenvector can differentiate the components \(\{4,5,6,7\}\) from the rest vectices. Likewise, the second eigenvector select the connected component \(\{8,9\}\) and the third choose the component \(\{1,2,3\}\).

In fact, in the field of Topological Data Analysis (TDA), the \(L_0\) is the special case of hodge laplacian (\(L_k\)). The number of connected components is call 0-dimensional cycles. And the graph laplaican can capture these cycles. The 1-dimensional cycles are correspond to holes, we will go into detail in the next section.

Hodge laplacian

We can see the graph laplacian zero-order of hodge laplacian, and the formalu can be represented as: \[\begin{equation} L_0 = \mathbf{0}^\top \mathbf{0} + B_1 B_1^\top \end{equation}\]

Similarly, we can obtian \(L_1\):

\[\begin{equation} L_1 = B_1^\top B_1 + B_2 B_2^\top \end{equation}\]

You must ask where is \(B_2\) coming from? We know that \(B_1\) captures the relationship between vertices and edges. Thus, \(B_2\) captures the relationship between edges and triangles. We can also define \(B_3\) to capture relationship between triangles and tetrahedron and so on and so forth. So what is a triangle or a tetrahedron in a graph? We would not go into the detail of the thory of Simplex and Simplicial complex. Here we just need to know that three connected vertices forms a triangle. Similarly, four connected vertices forms a tetrahedron which is a high-order of triangles. To define \(B_2\), of a graph \(G\), we would check the direction of an edge \(e_j\) to the triangle \(\bigtriangleup_q\) it beblongs, if it has the same direction as the triangle, the entry would be \(1\), if the direction is opposite, the entry would be -1, otherwise the entry would be zero. Specifically:

\[\begin{equation} {B}_2[j, q] = \begin{cases} 1 & \text{if } e_j \in \bigtriangleup_q \quad \text{with}\quad \text{same}\quad \text{direction} \\ -1 & \text{if } e_j \in \bigtriangleup_q \quad \text{with}\quad \text{opposite}\quad \text{direction} \\ 0 & \text{otherwise} \end{cases} \end{equation}\]

With the definition, we can obtian \(B_2\) of the graph aforementioned: \[\begin{equation} B_2 = \begin{array}[r]{c | c } & [4,5,6]\\ \hline \vdots & \cdots \\ [4,5] & 1\\ [4,6] & -1\\ [5,6]& 1\\ [6,7] & 0\\ \vdots & \cdots \\ \end{array} \end{equation}\]

We next introduce the normalized form and the decomposition of hodge 1-laplacian. The normalized form of hodge 1-laplacian is given:

\[\begin{equation} \mathcal{L}_1 = {D}_2 {B}_1^\top {D}_1^{-1} {B}_1 + {B}_2 {D}_3 {B}_2^\top {D}_2^{-1} \end{equation}\] where \(\mathbf{D}_1\) is the vertices degree matrix, \({D}_2\) is \(\max{(\text{diag}(|{B}_2| \mathbf{1}), \mathbf{I})}\) and \({D}_3\) is \(\frac{1}{3}\mathbf{I}\). Since the normalized \(L_1\) is not neccessarily symmetric, we next need to define the symmetric normalized Hodge 1-Laplacian such that: \[\begin{equation} \begin{aligned} \mathcal{L}_1^s & = {D}_2^{-1/2} \mathcal{L}_1 {D}_2^{1/2}\\ & = {D}_2^{1/2} {B}_1^\top {D}_1^{-1} {B}_1 {D}_2^{1/2} + {D}^{-1/2} {B}_2 {D}_3 {B}_2^\top {D}_2^{-1/2} \end{aligned} \end{equation}\]

We use the graph with three holes to present hodge 1-laplacian:

We next can perform eigenvalues decomposition on \(\mathcal{L}_1\): \[\begin{equation} \begin{aligned} \mathcal{L}_1 & = \mathbf{D}_2^{1/2} \mathcal{L}_1^s \mathbf{D}_2^{-1/2} \\ & = \mathbf{D}_2^{1/2} Q \Lambda Q^\top \mathbf{D}_2^{-1/2} \\ & = \mathbf{U} \Lambda \mathbf{U}^{-1} \end{aligned} \end{equation}\] Interestingly, the top 3 eigenvector also all zero which corresponding to the 3 holes, namely, the three 1-dimensional cycles.

When it comes to the eigenvectors, we can also notice that the top three eigenvectors are around the three holes.

In algebraic geometry, these the eigenvectors with zero eigenvaules are called harmonic function or harmonic. These harmonic function around holes is useful for some analysis like clustering to find the 1-dimensional cycles etc.

Conclusion

Today, we review the graph laplacian, and we can find the zeor eigenvalues and theirs corresponding eigenvectors can be used to find connected components. The high order graph laplacian hodge laplacian have the similar properties, we presented the hodge 1-laplaican and its eigenvalues decomposition. We can find that the zero eigenvalues indicates the number of holes of a graph. Furthermore, the corresponding eigenvectors with zero eigenvalues are around holes.