Question/possible bug with SIGNDiffusion transform

[aaronzo]

In the SIGNDiffusion transform, the original SIGN paper is given for reference. I'm new to DGL, so my understanding could be wrong - but the implementation here seems partial. The original paper mentions 3 diffusion operators:

1. GCN-normalized (symmetric degree normalisation) - The implementation here seems correct
2. PPR-based - The implementation here uses APPNP, an efficient choice. However, a couple of details seem inconsistent with the paper:
   • the k parameter of the transform seems to control the iterations given for the PPR calculation, but in the paper it should control the powers of the converged PPR matrix (like how the gcn diffusion pattern is implemented).
   • The implementation here uses the GCN-normalized adjacency matrix as the transition matrix, but it's likely that the authors of SIGN used a random-walk-normalized transition matrix.
3. Triangle-based - the implementation for this seems to be missing in DGL. To my understanding, this should be a matrix $A$ where entries $A_{ij}$ denote the number of triangles in the graph containing the edge $(i, j)$

Admittedly, the original authors of the paper didn't provide implementation details for 2) and 3).

Lastly, as more of a feature request, it would be useful for these diffusion operators to yield each the diffused features for each matrix power up to k, since the paper utilizes all of these and it would make applying SIGN more efficient.

Thanks in advance for any advice/help!

[jermainewang]

Hi, thanks for nice summary of the implementation difference. I do agree with the points. Our implementation is a simplified version, so we wonder if you've observed significant difference in model performance. This could help us justify the need to update the code.

For 3), we didn't find a nice way to express it in linear algebra so that we can call efficient kernels. If you have good suggestions, please let us know.

Lastly, as more of a feature request, it would be useful for these diffusion operators to yield each the diffused features for each matrix power up to k, since the paper utilizes all of these and it would make applying SIGN more efficient.

This is a good point. A workaround for now is to copy-and-modify the SIGN module outside of DGL library.

[aaronzo]

Hey @jermainewang - sorry for the delay in getting back to you. I was partially waiting for the paper I was working on to be published with some relevant results... (shameless self-plug) here it is.

For 3), we didn't find a nice way to express it in linear algebra so that we can call efficient kernels. If you have good suggestions, please let us know.

you'll find an implementation in Appendix C of the paper. I've implemented all the the operators in my open source package graph-diffusers using python-graphblas - the triangle implementation is here. I created this package alongside the paper, but as yet haven't documented or publicised it at all.