GraphNeuralNetworks.jl
GraphNeuralNetworks.jl copied to clipboard
Added Personalized PageRank Diffusion [`ppr_diffusion` function]
Continues Issue #412, takes inspiration from DGL implementation
This PR introduces a new function, ppr_diffusion
. It calculates Personalized PageRank (PPR) diffusion based on the edge weight matrix and updates the graph with new edge weights derived from the PPR matrix.
Implementation:
The function operates in several key steps:
- Construct Modified Adjacency Matrix (A): Utilizes existing edge weights (w) to build a matrix $A$ representing the graph's structure, adjusted by $(α - 1)$, where $α$ is the damping factor. This adjustment incorporates both direct connections and global graph structure.
A[dst, src] += w[idx]
A .*= (alpha_f32 - 1)
- Incorporate Identity Matrix (I): Adds the identity matrix to A to account for self-transitions, forming $I + (α - 1) \times A$.
A[i, i] += 1
- Apply PPR Formula: Calculates the PPR diffusion matrix as $α \times (I + (α - 1) \times A)^{-1}$, which effectively models the probability of transitioning from one node to another, considering random jumps governed by α.
PPR = alpha_f32 * inv(A)
- Update Edge Weights: Assigns new weights to each edge based on the corresponding values in the PPR matrix, effectively updating the graph's edge weights to reflect the calculated PPR diffusion.
new_w = [PPR[dst, src] for (src, dst) in zip(s, t)]