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.
- 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,:])
- 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:
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 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.)
[Tutorial] [Graph Laplacian Matrix]