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

• 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,:])`
• 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`

## 1.4. Normalized Graph Laplacian

• To get the Normalized Graph Laplacian:
`D2 = Dfor i in range(5):    D2[i,i] = 1/np.sqrt(D2[i,i])L2 = np.matmul(np.matmul(D2, L), D2)`
• 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:
• Then, we have the degree matrix D:
• And the Laplacian Matrix L:
• And the Normalized Graph Laplacian is:
• 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]

--

--