Graph Global Overlap Measure: Random Walk Similarity

#Graph #Basics #Clustering

Random Walk

Construct a stochastic transfer matrix $P$ by normalizing the adjacency matrix $\mathbf A$ using the node degrees of the target nodes,

$$ \mathbf P = \mathbf A \mathbf D^{-1}, $$

where $\mathbf A$ is the adjacency matrix Graph Adjacency Matrix A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice and clear examples on wikipedia1, for example, $$ \begin{pmatrix} 2 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $$ for the graph Public Domain, Link and $\mathbf D$ is a diagonalized matrix with the diagonal elements being the degrees.

Given a random walk associated with $\mathbf P$ that starts from node $u$, we find the probability that visits each node $v$, $\mathbf q_u[v]$1,

$$ \mathbf q_u = c \mathbf P \mathbf q_u + (1-c) \mathbf e_u, $$

where $\mathbf e_u$ is the onehot encoding of node $u$ and $c$ is a probability that the walk restarts at $u$.

  • If $c=0$, we have a constant solution.
  • If $c=1$, we have $\mathbf q_u = \mathbf P \mathbf q_u$, which is the Eigenvector Centrality of a Graph Eigenvector Centrality of a Graph Given a graph with adjacency matrix $\mathbf A$, the eigenvector centrality is $$ \mathbf e_u = \frac{1}{\lambda} \sum_{v\in\mathcal V} \mathbf A[u,v] \mathbf e_v, \qquad \forall u \in \mathcal V. $$ Why is it called Eigenvector Centrality The definition is equivalent to $$ \lambda \mathbf e = \mathbf A\mathbf e. $$ Power Iteration The solution to $\mathbf e$ is the eigenvector that corresponds to the largest eigenvalue $\lambda_1$. Power iteration method can help us get this eigenvector, … .

The solution is1,

$$ \mathbf q_u = (1-c) ( \mathbf I - c \mathbf P )^{-1} \mathbf e_u. $$

Random Walk Similarity

The random walk similarity is defined using $\mathbf q_u$,

$$ \mathbf S_{\text{RW}}[u, v] = \mathbf q_u[v] + \mathbf q_v[u], $$

which is symmetry under permutation of $u$ and $v$.


  1. Hamilton2020 Hamilton WL. Graph Representation Learning. Morgan & Claypool Publishers; 2020. pp. 1–159. doi:10.2200/S01045ED1V01Y202009AIM046  ↩︎

Published: by ;

L Ma (2021). 'Graph Global Overlap Measure: Random Walk Similarity', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/cards/graph/graph-global-overlap-random-walk-similarity/.

Current Ref:

  • cards/graph/graph-global-overlap-random-walk-similarity.md