- PageRank: Iteratively do matrix operation to converge the in-link matrix to stationary distribution of a random walk(Power iteration)
- Initialize all rank as equally.
- Converge problem → make Teleport to random(any) page(Escape to random page)
- Spider trap(trapped in some cycle)
- Dead end(absolve inward rank and no outlink)
- More about Markov Chain Converge(Irreduicible(Trapped in a cycle or node), aperiodic(Not converge to a particular state)
from Stats325(Stochastic Process), University of Auckland) Markov Chains, Equilibrium
- Personalized PageRank(PPR)
- Teleport nodes that an user is interested in.
- Random Walk with Restarts
- Teleport back to the staring node
- Procedures:
- Start with given Query Nodes
- Follow one of the below
- random walk record the visit count
- restart walk at one of the with probability
- The node with the highest visit count have highest proximity to the Query Nodes
- Those above(Personalized PageRank, Random Walk with Restarts) are very similar but only different in the ways to teleport
- Node embeddings based on random walks like above can be expressed as matrix factorization but it has inborn problems
- approximate and use the for calculating similarity of nodes
- Deep representation learning and GNN will solve these problems.
- Can’t obtain embeddings for non-seen in the training set
- Can’t capture structural simiarity(→ anonymous walk can solve it)
- Can’t utilize node, edge and graph features
나의 학습일지