Tutorial: Normalized Graph Laplacian

My Study on Graph & Normalized Laplacian Matrix

When I read Self-supervised Semi-supervised Learning for Data Labeling and Quality Evaluation (2021 NeurIPSW), I come across some equations related to graph.

  • To know more about it, I tried two simple cases, one is graph with all edge strengths=1, one is graph with different edge strengths. Indeed, it is more like a record for my study on Adjacent Matrix, Degree Matrix, Laplacian Matrix to Normalized Graph Laplacian.
  • For some works, this Normalized Graph Laplacian can then go through convolutions such as using Graph Convolutional Network (GCN).

1. From Graph to Normalized Graph Laplacian

Graph is a node-edge representation, which can have many applications such as social media network.

A Graph Sample

1.1. Adjacent Matrix

  • Suppose we have 5 nodes, with some edges connecting two nodes together. And the weight for each edge is equal. Then we can use a 5×5 adjacent matrix A to represent the graph:
A = np.array([[0, 1, 0, 0, 0],
[1, 0, 1, 1, 1],
[0, 1, 0, 1, 0],
[0, 1, 1, 0, 1],
[0, 1, 0, 1, 0]])
  • Each 1 means the connection/edge between 2 nodes.
  • Some of the graphs will have value larger than 1, or even with different edge strengths for different directions, e.g.: value of 2 from A to B but with value of 3 from B to A. (This will be mentioned in the next section.)

1.2. Degree Matrix

  • The degree matrix D of this graph is as follows:
D = np.zeros((5,5))
for i in range(5):
D[i,i] = np.sum(A[i,:])
Degree Matrix D
  • In the matrix, each value is the sum of each row, which is the number of connections for that node.

1.3. Laplacian Matrix

  • By D-A, we got Laplacian matrix:
L=D-A
Laplacian Matrix L

1.4. Normalized Graph Laplacian

  • To get the Normalized Graph Laplacian:
D2 = D
for i in range(5):
D2[i,i] = 1/np.sqrt(D2[i,i])
L2 = np.matmul(np.matmul(D2, L), D2)
Normalized Graph Laplacian
  • where the main diagonals are all 1 now.

2. For Graph with Unequal Weighting Edges

  • Similarly, For graph with different edge strengths, let say we have adjacent matrix A like below:
Adjacent Matrix A
  • Then, we have the degree matrix D:
Degree Matrix D
  • And the Laplacian Matrix L:
Laplacian Matrix L
  • And the Normalized Graph Laplacian is:
Normalized Graph Laplacian
  • where the main diagonals are all 1s now.
  • I am not expert of graph, GSP, or GNN. I just follow the tutorial and go through some very simple examples by myself to have more understanding. There maybe a faster way to estimate the Normalized Graph Laplacian.
  • (If there is something wrong, please kindly tell me.)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store