normalized adjcency or laplacian matrix ?

[JoeHEZHAO]

normalized adjcency or laplacian matrix ?

[abduallahmohamed]

Thanks for asking.

If you have an adjacency matrix A, and a degree node matrix D you can normalize it by doing what I call Kipf's normalization which is a form of reduced adjacency matrix [1]:

But in graph CNN this is slightly different: The A becomes

Then the normalization becomes:

I believe what we used here was a Laplacian normalization with accounting to self nodes by adding identity to the nodes

Social-STGCNN/utils.py

Line 43 in 9347d30

A[s,h,h] = 1

.

I did a quick test to illustrate the difference:

import networkx as nx
import numpy as np 

#Kipf's normalization

A = np.asarray([[0,5,9],[5,0,8],[9,8,0]])
print("A Matrix")
print(A)
A_hat = A+np.eye(3)
print("A_hat Matrix")
print(Ahat)
D_hat = np.eye(3)*2 +np.eye(3) #Fully connected graph degree matrix of A_hat
print("D_hat Matrix")
print(D)
D_half_inv = np.linalg.inv(np.sqrt(D)) 
Kip_normalization = np.matmul(np.matmul(D_half_inv,A_hat),D_half_inv)
print("\n Kipf normalization")
print(Kip_normalization)

#Using laplacian 
G = nx.from_numpy_matrix(A_hat) #create a graph 
A_lapl = nx.normalized_laplacian_matrix(G).toarray()
print("\n Laplacian normalization")
print(A_lapl)

which yields:

A Matrix
[[0 5 9]
 [5 0 8]
 [9 8 0]]
A_hat Matrix
[[1. 5. 9.]
 [5. 1. 8.]
 [9. 8. 1.]]
D_hat Matrix
[[3. 0. 0.]
 [0. 3. 0.]
 [0. 0. 3.]]

 Kipf normalization
[[0.33333333 1.66666667 3.        ]
 [1.66666667 0.33333333 2.66666667]
 [3.         2.66666667 0.33333333]]

 Laplacian normalization
[[ 0.93333333 -0.34503278 -0.54772256]
 [-0.34503278  0.92857143 -0.50395263]
 [-0.54772256 -0.50395263  0.94444444]]

Thanks for noticing this, I will check into more details and either update the paper or the code to see which works best, according to [2] I think the proposed normalization by Kipf is to avoid the computation of lapalcian.

[1] https://en.wikipedia.org/wiki/Laplacian_matrix
[2] https://tkipf.github.io/graph-convolutional-networks/

[JoeHEZHAO]

Dear Authors

Thanks for your detailed reply ! The example you provided is exactly what I have observed.

Just wondering: could your way be another approach to do approximation in [2] ?

#1. Original paper assumes learning will adapt theta = theta_{0} = -theta_{1}, which leads to the proposed formular (the 2nd equation of your reply).

#2. However, if assume theta = theta_{0} = theta_{1}, then the RHS of equation (6) from [2] becomes:
theta * L * x, which is also ok (I guess).

Thanks again for your time and effort !

[abduallahmohamed]

Can you refer to which equation you mean in [2]?
I'm not sure I'm following theta thing

[JoeHEZHAO]

Sorry for the confusion.

First, in Kipf's paper, the reason why we use normalized adjacency matrix is from below two deductions:

Notice the assumption:

Second, if it is possible to assume , then above equations will be re-formulated as:

So, normalized lapalcian fits the approximation.

[abduallahmohamed]

I will get back to this by the beginning of next weak, sorry for the delay

[hzzzzjzyq]

Dear Authors
Thanks for your detailed reply
can i believe the difference between stgcn and social-stgcnn as below
1.stgcn use

2.social-stgcnn use

lapalcian=Dhat -Ahat


What is the difference between the two

[abduallahmohamed]

Hi, I will try to answer to my best:
Kipf normalization [ Not sure if this is stgcn or not]
[[0.33333333 1.66666667 3. ]
[1.66666667 0.33333333 2.66666667]
[3. 2.66666667 0.33333333]]

Laplacian normalization [Ours]
[[ 0.93333333 -0.34503278 -0.54772256]
[-0.34503278 0.92857143 -0.50395263]
[-0.54772256 -0.50395263 0.94444444]]

This how the A matrix looks like after normalization, so ours row and columns sums to 0.
I didn't try the Kipf's normalization method to see the outcome on our approach. You can test both and understand how it effects your results @hzzzzjzyq

[DarrenRuan]

Hi, I just want to ask the following question: why are the sums of rows and columns of the Laplacian normalization matrix equal to 0? Is there any strict proof?

>>> A_lapl
array([[ 0.93333333, -0.34503278, -0.54772256],
       [-0.34503278,  0.92857143, -0.50395263],
       [-0.54772256, -0.50395263,  0.94444444]])
>>> np.sum(A_lapl,axis=0)
array([ 0.040578  ,  0.07958602, -0.10723074])
>>> np.sum(A_lapl,axis=1)
array([ 0.040578  ,  0.07958602, -0.10723074])

[abduallahmohamed]

I'm not aware of a proof for this ------------------------------------------ Abduallah Mohamed abduallahmohamed.com

…

On Wed, Oct 20, 2021 at 2:04 PM DarrenRuan ***@***.***> wrote: Hi, I just want to ask the following question: why are the sums of rows and columns of the Laplacian normalization matrix equal to 0? Is there any strict proof? >>> A_laplarray([[ 0.93333333, -0.34503278, -0.54772256], [-0.34503278, 0.92857143, -0.50395263], [-0.54772256, -0.50395263, 0.94444444]])>>> np.sum(A_lapl,axis=0)array([ 0.040578 , 0.07958602, -0.10723074])>>> np.sum(A_lapl,axis=1)array([ 0.040578 , 0.07958602, -0.10723074]) — You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub <#22 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AFIVLGZXTYKXXKRU7XCY2LLUH4HFVANCNFSM4M76V4PA> .