작성자: 이정은

해당 포스팅은 ToBigs GNN스터디에서 발표를 진행했습니다.
https://velog.io/@tobigsgnn1415/4.-Link-Analysis-PageRank

1. The Web as a Graph

웹을 그래프로 본다면, 각 웹페이지를 노드로, 페이지 간의 하이퍼링크를 엣지로 볼 수 있습니다.

이때 동적인 웹페이지나 다크웹과 같은 접근할 수 없는 페이지 등에서 이슈가 발생하는데, 이는 묻어두고 정적인 웹페이지만 고려합니다.
초기의 웹은 페이지와 페이지 간의 링크로만 이루어져 있어 navigational했지만, 현재는 좋아요, 댓글 등의 transcational link로 이루어집니다. PageRank에서는 navigational link만 취급합니다.

웹 이외에도 논문의 인용구와 사전의 레퍼런스도 노드와 엣지로 이루어진 그래프 구조를 가집니다.

1.1. What Does the Web Look Like?

실제 웹은 위와 같이 방향성을 가진 그래프로 in-link와 out-link를 가집니다. 이를 통해 페이지 A가 어떤 다른 페이지로 연결되는지를 알 수 있습니다.

2. PageRank

2.1. Ranking nodes on the graph

모든 웹페이지는 다른 중요도(important)를 가지고 있습니다. 따라서 웹 그래프를 가지고 웹페이지에 rank를 매기고자 합니다.

2.2. Main Idea: Links as votes

해당 아이디어는 페이지가 많은 링크를 가질수록 더 중요하다는 것을 의미합니다. 웹페이지는 앞서 말했듯이 방향성을 가진 directed 그래프이므로 in-link와 out-link가 존재합니다.
이때 out-link보다는 in-link를 중요도의 지표로서 사용하여 in-link를 더 많이 갖고 있는 페이지가 중요도가 높다고 판단합니다.
만약 in-link의 개수가 같다면, 더 중요한 페이지에서 들어온 링크의 개수가 많을수록 중요하다고 판단합니다. 이는 중요한 페이지로 다른 중요한 페이지를 찾는 recursive 문제임을 보여줍니다.

2.3. PageRank: The "Flow" Model

위 내용을 수식으로 표현하면 다음과 같습니다.

• 각 페이지의 링크는 해당 페이지의 중요도에 비례합니다.
• 페이지 i가 중요도 $r_i$와 $d_i$ out-links를 가지고 있으면, 각 링크는 $r_i/d_i$의 vote를 갖습니다.
• 페이지 j의 중요도 $r_j$는 in-links의 vote의 합계입니다.

따라서 $r_i$의 중요도는 in-links의 중요도인 $r_i$를 사용한 식으로 정의할 수 있습니다. 노드가 3개인 우측 예시처럼 해당 방정식을 가우시안 소거법을 사용해 풀 수 있습니다. 이는 당연하게도 그래프가 커질수록 너무 많은 시간이 소요되기 때문에 실제로 활용하기엔 문제가 있습니다.

2.4. PageRank: Matrix Formulation

위 문제를 보완한 방법이 Stochastic adjacency matrix를 사용해 그래프를 표현하여 방정식을 해결하는 것입니다.

행렬의 크기는 노드의 개수x노드의 개수가 됩니다.
페이지 j가 $d_j$ out-links를 가지고 있으면, 페이지 j에서 페이지 i로 향하는 vote는 $M_{ij}=1/d_j$ 입니다. 따라서 각 열의 합은 1이 되므로 Column stochastic matrix라고 말합니다.

중요도 벡터 $r$은 각 페이지의 중요도를 나타내며 $r_i$는 페이지 i의 중요도를 말합니다. 이 또한 $\sum_i r_i=1$이 됩니다.

따라서 flow 방정식을 $r = M \cdot r$으로 나타낼 수 있습니다.

2.5. Connection to Random Walk

특정 노드에서 다른 노드로 랜덤하게 옮겨가는 랜덤워크처럼 랜덤하게 페이지를 돌아다니는 web surfer가 특정 시간 t에 페이지 i에 있다고 가정합니다. 그럼 시간 t+1에는 uniformly random하게 선택된 out-link로 서퍼가 이동하고, 이 과정을 페이지 j에 도달할 때까지 계속해서 반복합니다.

$p(t)$는 전체 페이지 개수만큼의 벡터로, i번째 원소는 서퍼가 시간 t에 페이지 i에 있을 확률을 의미합니다. 즉, $p(t)$는 서퍼가 시간 t에 각 페이지에 있을 확률 분포를 뜻합니다. uniformly random에 따라 서퍼가 움직인다면, 시간 t+1에 서퍼가 어디에 있을지는 $p(t+1) = M \cdot p(t)$로 알 수 있습니다.

만약 랜덤워크가 state에 도달했다면, $p(t+1) = M \cdot p(t) = p(t)$가 됩니다. 이때 $p(t)$는 $aP=a$를 만족하는 더 이상 변화하지 않는 stationary distribution 상태입니다.

앞서 보았던 PageRank의 중요도 벡터 r도 $r=M \cdot r$ 의 형태였으므로, r은 랜덤워크에서 stationary distribution 상태라고 할 수 있습니다.

2.6. Eigenvector Formulation

Lecture2에서 다뤘던 eigenvector centrality는 인접행렬 A를 이용해 $\lambda c = Ac$ 으로 노드의 중심성을 나타내는 고유벡터 c를 계산해냈다.

PageRank의 flow 방정식은 $1 \cdot r=M \cdot r$으로 고유값이 1이고, 중요도 벡터 r은 인접행렬 M의 고유벡터라고 할 수 있습니다.

2.7. Solve: Power Iteration

실제 Pagerank 방정식은 앞서 말했듯이 랜덤워크에서 stationary distribution 상태로 존재하는 중요도 벡터 r을 계산해야 합니다.

이에 Power Iteration을 사용합니다. 해당 방법은 n개의 노드에 대한 벡터 r가 수렴할 때까지 즉, 벡터 r이 시점에 영향을 받지 않을 때까지 계속 반복하여 계산합니다.
전체 과정은 아래와 같습니다.
1. 벡터 r 초기화: $r^0 = [1/N,...1/N]^T$
2. 반복 계산 진행: $r^{(t+1)} = M \cdot r^t$
3. 반복하다가 수렴을 만족하면 종료: $|r^{(t+1)}-r^t|_1<\epsilon$

이때 일반적으로 쓰는 L1 norm대신 다른 norm을 사용해도 되고, 보통 반복 횟수 50회 정도에 수렴하게 됩니다.

2.8. Problems

이런 PageRank에도 두 가지 문제점이 존재합니다.

2.8.1. Spider traps

Spider traps는 모든 out-links가 그룹 안에 속하는 페이지가 존재할 때 발생합니다. 해당 페이지에 서퍼가 한번 들어가면 갇히게 됩니다. 그리고 power iteration 진행 시 수렴에 문제가 발생하는데, 이 페이지가 중요도를 모두 흡수해 다른 페이지는 중요도를 잃게 됩니다.

2.8.2. Dead ends

Dead ends는 in-links는 있지만 out-links가 없는 페이지가 존재하는 경우를 말합니다. 이러한 페이지는 out-links가 없기 때문에 인접행렬 M이 더 이상 column stochastic하지 않고, 중요도에 leakage가 발생합니다. Dead ends는 수렴에는 문제가 되지 않지만 결과로 나온 스코어가 좋지 않을 수도 있습니다.

2.9. Solutions

2.9.1. Spider traps

Random Teleport를 이용해 랜덤 서퍼가 매 스텝마다 두 가지 옵션을 가지게 합니다. $\beta$ 만큼의 확률로 링크를 따라 이동하거나, $(1-\beta)$ 의 확률로 다른 웹페이지로 teleport하게 됩니다. 이때 다른 페이지로 이동할 확률은 페이지마다 모두 동일하며, $\beta$는 보통 0.8-0.9 사이로 설정합니다.

따라서 매 스텝마다 $(1-\beta)$의 확률로 랜덤한 페이지로 이동하게 되면 특정 페이지에서 빠져나올 수 있고, 다른 페이지가 중요도를 잃는 문제를 해결하게 됩니다.

2.9.2. Dead ends

위와 같은 방법으로 문제를 해결하는데, Dead ends의 경우 무조건 다른 페이지로 이동하게 하여 dead ends 페이지에서 다른 노드로 갈 확률을 균등하게 배분합니다. 이는 column stochastic을 만족하게 하여 문제를 해결합니다.

2.10. The Google Matrix

Random Teleport를 포함한 PageRank의 방정식은 $r_j = \sum_{i->j} \beta \frac{r_i}{d_i} + (1-\beta) \frac{1}{N}$ 입니다. 이는 spider traps의 문제를 해결했고, 행렬 M에 균등확률을 배정하는 전처리를 진행하여 dead ends 고려하지 않아도 되게 했습니다.

이를 Google matrix G를 사용해 표현하면, $G=\beta M + (1-\beta)[\frac{1}{N}]_{NxN}$ 이 됩니다. 이 식은 여전히 recursive 문제를 가지고 있지만 Power iteration을 사용하여 계산합니다.

PageRank로 계산된 중요도를 보게 되면,

• 페이지 B와 같이 in-links가 많으면 높은 중요도를 가집니다.
• 페이지 E도 페이지 B와 비슷한 in-links를 갖지만 상대적으로 덜 중요한 페이지에서 온 링크들이므로 중요도가 낮게 측정된 것을 볼 수 있습니다.

3. Extenstion of PageRank

위와 같은 사용자와 아이템으로 이루어진 biparatite graph가 존재합니다. 이때 특정 아이템을 구매한 사용자에게 다른 아이템을 추천하려고 한다면, 아이템 간의 유사성을 파악하여 사용자에게 추천해줘야 합니다.

단순히 아이템 간의 최단 경로로 본다면, 아이템 A와 A'가 B와 B'보다 더 관계가 있다고 볼 수 있습니다. 같은 길이의 경로를 가진 C와 C' 그리고 D와 D'의 경우에는 너무 많은 사용자가 연관된 D보다는 C와 C'이 더 관계가 높다고 판단할 수 있습니다.

기존 PageRank는 노드의 중요도를 가지고 rank를 측정하고, 그래프 내 모든 노드에 대해 균등한 확률로 teleport를 실시합니다. 따라서 teleport 집합 S는 [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1]로 나타낼 수 있습니다.

3.1. Personalized PageRank

Personalized Rank는 모든 노드가 아닌 특정 노드만 포함된 부분 집합 S에서 랜덤하게 teleport를 진행합니다. 이 집합은 균등하거나 가중치가 반영된 S = [0.1,0,0,0.2,0,0,0.5,0,0,0.2]로 표현할 수 있습니다.

3.2. Random walk with restarts

이 경우는 부분 집합 S를 랜덤워크를 재시작할 특정 노드 하나로 지정합니다. S = [0,0,0,0,1,0,0,0,0,0,0]와 같이 특정 노드에만 값을 표시합니다.

3.3. Random walk Algorithm

전체 알고리즘은 다음과 같이 진행됩니다.
랜덤워크를 재시작할 수 있는 확률인 ALPHA가 존재하고, 그 이외에는 기존의 랜덤워크와 동일하고 각각 쿼리 노드만 다르게 구성되어 있습니다.

해당 알고리즘은 Multiple connections / Multiple paths / Direct and indirect connections / Degree of the node에 대해 유사도가 모두 고려할 수 있기 때문에 좋은 해결책이 됩니다.

---

참고자료
Youtube-Stanford : CS224W Lecture 4.1 - PageRank
CS224W-notes: PageRank
Youtube-설레는 수학: 페이지링크 알고리즘