Normalization change in AddRandomWalkPE: From A D⁻¹ to D⁻¹ May Deviate from Paper

[ywangmy]

🐛 Describe the bug

Hi! I've been using AddRandomWalkPE and noticed a potential discrepancy between the current implementation and the RWPE methodology as described in the paper “Graph Neural Networks with Learnable Structural and Positional Representations” (arXiv:2110.07875).

• The current implementation seems to use $D^{-1}$ as the transition matrix.
• The initial implementation f35c85f appears to handle the normalization correctly as $A D^{-1}$, which was changed in 0ea43bb.

Could you please confirm whether the current normalization approach aligns with the paper?

Versions

PyTorch version: 2.3.0                                                         
Is debug build: False      
CUDA used to build PyTorch: 12.1
ROCM used to build PyTorch: N/A
                                                                               
OS: Red Hat Enterprise Linux release 8.10 (Ootpa) (x86_64)                     
GCC version: (conda-forge gcc 13.3.0-1) 13.3.0                                 
Clang version: 11.1.0 (https://github.com/conda-forge/clangdev-feedstock 2816c2c
f231a2d3a6d621af9bbb2c590c9e63fe7)                                             
CMake version: version 3.30.5                                                  
Libc version: glibc-2.28                                                       
                                                                               
Python version: 3.11.10 | packaged by conda-forge | (main, Oct 16 2024, 01:27:36
) [GCC 13.3.0] (64-bit runtime)                                                 
Python platform: Linux-4.18.0-553.33.1.el8_10.x86_64-x86_64-with-glibc2.28     
Is CUDA available: True                                                        
CUDA runtime version: Could not collect                                        
CUDA_MODULE_LOADING set to: LAZY                                               
GPU models and configuration:                                                  
GPU 0: NVIDIA RTX 6000 Ada Generation                                          
GPU 1: NVIDIA RTX 6000 Ada Generation                                           
GPU 2: NVIDIA RTX 6000 Ada Generation                                          
GPU 3: NVIDIA RTX 6000 Ada Generation                                          
GPU 4: NVIDIA RTX 6000 Ada Generation                                           
GPU 5: NVIDIA RTX 6000 Ada Generation                                           
GPU 6: NVIDIA RTX 6000 Ada Generation                                          
GPU 7: NVIDIA RTX 6000 Ada Generation                                           
                                                                                
Nvidia driver version: 565.57.01                                                
cuDNN version: Probably one of the following:                                   
/usr/lib64/libcudnn.so.8.9.7                                                    
/usr/lib64/libcudnn_adv_infer.so.8.9.7                                          
/usr/lib64/libcudnn_adv_train.so.8.9.7                                          
/usr/lib64/libcudnn_cnn_infer.so.8.9.7                                          
/usr/lib64/libcudnn_cnn_train.so.8.9.7                                          
/usr/lib64/libcudnn_ops_infer.so.8.9.7                                         
/usr/lib64/libcudnn_ops_train.so.8.9.7                                         
HIP runtime version: N/A                                                       
MIOpen runtime version: N/A                                                    
Is XNNPACK available: True                                                     
                                       
CPU:
Architecture:         x86_64
CPU op-mode(s):       32-bit, 64-bit
Byte Order:           Little Endian
CPU op-mode(s):       32-bit, 64-bit                                     [41/95]
Byte Order:           Little Endian  
CPU(s):               256                                                      
On-line CPU(s) list:  0-254
Off-line CPU(s) list: 255       
Thread(s) per core:   1        
Core(s) per socket:   64                                                       
Socket(s):            2                                                        
NUMA node(s):         2                                                        
Vendor ID:            AuthenticAMD                                              
CPU family:           25                                                       
Model:                1                                                        
Model name:           AMD EPYC 7763 64-Core Processor                          
Stepping:             1                                                        
CPU MHz:              2450.000                                                  
CPU max MHz:          3529.0520                                                 
CPU min MHz:          1500.0000                                                
BogoMIPS:             4899.95                                                  
Virtualization:       AMD-V                                                    
L1d cache:            32K                                                      
L1i cache:            32K                                                      
L2 cache:             512K                                                     
L3 cache:             32768K                                                    
NUMA node0 CPU(s):    0-63,128-191                                             
NUMA node1 CPU(s):    64-127,192-254                                           
Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca c
mov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rd
tscp lm constant_tsc rep_good nopl nonstop_tsc cpuid extd_apicid aperfmperf pni
pclmulqdq monitor ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsav
e avx f16c rdrand lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignss
e 3dnowprefetch osvw ibs skinit wdt tce topoext perfctr_core perfctr_nb bpext pe
rfctr_llc mwaitx cpb cat_l3 cdp_l3 invpcid_single hw_pstate ssbd mba ibrs ibpb s
tibp vmmcall fsgsbase bmi1 avx2 smep bmi2 invpcid cqm rdt_a rdseed adx smap clfl
ushopt clwb sha_ni xsaveopt xsavec xgetbv1 xsaves cqm_llc cqm_occup_llc cqm_mbm_
total cqm_mbm_local clzero irperf xsaveerptr wbnoinvd amd_ppin brs arat npt lbrv
 svm_lock nrip_save tsc_scale vmcb_clean flushbyasid decodeassists pausefilter p
fthreshold v_vmsave_vmload vgif v_spec_ctrl umip pku ospke vaes vpclmulqdq rdpid
 overflow_recov succor smca                                                    
                                                                               
Versions of relevant libraries:                                                
[pip3] mypy-extensions==1.0.0                                                  
[pip3] numpy==1.24.3                                                           
[pip3] torch==2.3.0                    
[pip3] torch_cluster==1.6.3+pt23cu121
[pip3] torch-geometric==2.6.1
[pip3] torch_scatter==2.1.2+pt23cu121
[pip3] torch_sparse==0.6.18+pt23cu121
[pip3] numpy==1.24.3                                                      [0/95]
[pip3] torch==2.3.0                  
[pip3] torch_cluster==1.6.3+pt23cu121                                          
[pip3] torch-geometric==2.6.1
[pip3] torch_scatter==2.1.2+pt23cu121
[pip3] torch_sparse==0.6.18+pt23cu121
[pip3] torch_spline_conv==1.2.2+pt23cu121                                      
[pip3] torchaudio==2.3.0                                                       
[pip3] torchvision==0.18.0                                                     
[pip3] triton==2.3.0                                                            
[conda] blas                      1.0                         mkl              
[conda] cuda-cudart               12.1.105                      0    nvidia    
[conda] cuda-cupti                12.1.105                      0    nvidia    
[conda] cuda-libraries            12.1.0                        0    nvidia    
[conda] cuda-nvrtc                12.1.105                      0    nvidia     
[conda] cuda-nvtx                 12.1.105                      0    nvidia     
[conda] cuda-opencl               12.6.77                       0    nvidia    
[conda] cuda-runtime              12.1.0                        0    nvidia    
[conda] libblas                   3.9.0            12_linux64_mkl    conda-forge
[conda] libcblas                  3.9.0            12_linux64_mkl    conda-forge
[conda] libcublas                 12.1.0.26                     0    nvidia    
[conda] libcufft                  11.0.2.4                      0    nvidia    
[conda] libcurand                 10.3.7.77                     0    nvidia     
[conda] libcusolver               11.4.4.55                     0    nvidia    
[conda] libcusparse               12.0.2.55                     0    nvidia    
[conda] libjpeg-turbo             2.0.0                h9bf148f_0    pytorch    
[conda] liblapack                 3.9.0            12_linux64_mkl    conda-forge
[conda] libnvjitlink              12.1.105                      0    nvidia    
[conda] mkl                       2021.4.0           h06a4308_640               
[conda] mkl-service               2.4.0           py311h5eee18b_0               
[conda] mkl_fft                   1.3.1           py311h30b3d60_0               
[conda] mkl_random                1.2.2           py311hba01205_0               
[conda] numpy                     1.24.3          py311hc206e33_0               
[conda] numpy-base                1.24.3          py311hfd5febd_0               
[conda] pytorch                   2.3.0           py3.11_cuda12.1_cudnn8.9.2_0  
  pytorch                                                                       
[conda] pytorch-cuda              12.1                 ha16c6d3_6    pytorch    
[conda] pytorch-mutex             1.0                        cuda    pytorch   
[conda] torch-cluster             1.6.3+pt23cu121          pypi_0    pypi      
[conda] torch-geometric           2.6.1                    pypi_0    pypi      
[conda] torch-scatter             2.1.2+pt23cu121          pypi_0    pypi      
[conda] torch-sparse              0.6.18+pt23cu121          pypi_0    pypi     
[conda] torch-spline-conv         1.2.2+pt23cu121          pypi_0    pypi
[conda] torchaudio                2.3.0               py311_cu121    pytorch
[conda] torchtriton               2.3.0                     py311    pytorch
[conda] torchvision               0.18.0              py311_cu121    pytorch