cs224w | Lecture 4. Link Analysis: PageRank

Link Analysis Algorithms

PageRank: The "Flow" Model

• A page is important if it is pointed to by other important pages

• Connection to random walk

• What is the long-term distribution of the surfers?

• PageRank is the stationary distribution of random-walk

• 결국 eigenvalue가 1인 행렬 M의 eigenvector를 구하는 문제

• Summary

PageRank: How to solve?

• Power Iteration

• Problems of Spider Traps / Dead ends
  -> Use Teleports
• PageRank에서는 구글 행렬을 사용함: $\beta$를 설정하여 다른 노드로 랜덤하게 teleport함

Random Walk with Restarts / Personalized PageRank

• Personalized PageRank는 다른 노드로 teleport하는 확률이 uniform하지 않음

Matrix Factorization and Node Embeddings

• Node가 유사하다는 건 서로 연결되어 있다는 것. 즉,
  $\bold{Z}^{T}\bold{Z} = A$
• 하지만 실제로 embedding dimension d보다 number of node n이 훨씬 큼. 따라서, factorization으로 A size가 나오는건 현실적으로 불가능.
• 하지만 둘의 차이가 작아지도록 $\bold{Z}$를 근사할 수는 있음.

• DeepWalk, Node2Vec

• Limitations
  1. Cannot obtain embeddings for nodes not in the training set

  2. Cannot capture structural similarity
  3. Cannot utilize node, edge and graph features