GraphNeuralNetworks.jl icon indicating copy to clipboard operation
GraphNeuralNetworks.jl copied to clipboard

Added Personalized PageRank Diffusion [`ppr_diffusion` function]

Open rbSparky opened this issue 11 months ago • 3 comments

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)]

rbSparky avatar Mar 18 '24 21:03 rbSparky