# 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

Graphis anode-edge representation, which can have many applications such as social media network.

- 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**to represent*A***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**of this graph is as follows:*D*

`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
, we got*D*-*A***Laplacian matrix**:

`L=D-A`

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

- 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**like below:*A*

- 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]