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

• This graph sample is from: https://www.sharetechnote.com/html/Handbook_EngMath_GraphTheory_LaplacianMatrix.html

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.)

Reference

[Tutorial] [Graph Laplacian Matrix]
https://www.sharetechnote.com/html/Handbook_EngMath_GraphTheory_LaplacianMatrix.html

6.1. Models & Related Knowledge

[LSTM Model from Kaggle] [Transformer from D2L.ai] [Transformer from Google TensorFlow] [Graph Laplacian Matrix]

My Other Previous Paper Readings and Tutorials