[CS246] PageRank

 

반응형

PageRank: Ranking Nodes on the Graph

Web as a Directed Graph

Web 데이터는 방향그래프로 나타낼 수 있다. 노드는 webpage, edge는 hyperlink로 대응하여 생각할 수 있다.

그래프 용어가 나오므로 익숙하지 않다면 여기를 참고해도 좋다.

https://trivia-starage.tistory.com/213

[CS224w, 2018] Network Representation

 

과거에는 웹페이지를 디렉토리(directory)로 나타냈다. 그러나 사람이 일일이 디렉토리를 만들어야한다.

두번째 방법으로 web search를 이용한 information retrieval이다. 관련성 높은 문서를 찾아주는 것이다. 그러나 web scale은 매우 크고, 신뢰할 수 없는 문서들이 너무 많다는 문제가 있다.

 

Challenge 1: Who to trust? → 신뢰할 수 있는 페이지는 서로 링크로 가리킬 것이다.

Challenge 2: What is the best answer? → 각 페이지는 각 페이지들이 많은 페이지를 가리키는 것을 알고 있다.

 

모든 web page가 동일하게 중요하지 않다는 것에서 시작한다.

All web pages are not equally "important" (Stanford CS246)

위 그림에서 파란색 노드(페이지)는 많은 노드와 연결되어 있으므로 많이 중요한(그리고 신뢰할 수 있는) 페이지이다. 빨간색 노드(페이지)는 하나와 연결되어있으므로 (파란색 노드에 비해) 중요도가 낮다고 할 수 있다.

Intuition of PageRank

(1) Links as votes: 중요한 페이지는 더 많은 링크를 가질 것이다.

(2) Random Surfing: 중요한 페이지는 많은 사람들이 방문할 것이다. 그러나 모든 사용자의 실제 페이지 방문 활동을 모니터링할 수 없다. 대신에 사람들이 링크를 따라 페이지를 방문할 것이라고 가정하는 모델을 차용한다. 임의의 페이지에서 시작하여, 연결된 링크를 랜덤하게 방문하는 모델을 random surfer model이라 한다. PageRank는 페이지 방문 확률을 제한시키는 것이다. (균등하지 않다)

(3) Transition Matrix: 중요한 페이지는 결국 중요한 페이지의 이전 페이지와도 중요도를 공유한다. (recursive equation). 수학적으로 importance는 transition matrix의 principal eigenvector와 동일하다.

 

PageRank Scores (Stanford CS246)

위 그림에서 PageRank를 직관적으로 이해해보자. 빨간색 노드들은 out-link만 존재하고 in-link는 없으므로 중요하지 않은 페이지이다. A는 in-link가 하나뿐이므로 중요도가 비교적 작다. B는 많은 노드로부터 링크가 연결되어서 많이 중요한 페이지이다. C는 A처럼 in-link는 한개이지만 그 in-link는 중요도가 높은 B이므로 C 역시 중요한 페이지이다. (정확한 score를 계산하는 것은 아래 설명함)

PageRank: Flow Equations

각 link의 vote는 source page의 중요도에 비례한다.

page $j$의 중요도를 $r_j$라 하고, $j$의 out-link가 $n$개 있다면, 각 out-link는 $\frac{r_j}{n}$의 vote를 갖는다.

그리고 $j$의 중요도는 in-link의 vote의 합으로 정의한다.

Link as a vote (Stanford CS246)

위 그림에서 $j$의 중요도는 $r_j  = \cfrac{r_i}{3} + \cfrac{r_k}{4}$ 이다.

이를 일반화하면 다음과 같다.

\[ r_j = \sum_{i \to j} \cfrac{r_i}{d_i} \]

이때 $d_i$는 $i$번째 노드의 out-degree이다.

 

$N$개의 노드가 있다면 우리는 $N$차 연립방정식을 풀어야 한다. 전통적 방법으로 가우시안 소거법을 이용할 수 있지만 web-scale size에서는 사실상 사용할 수 없다.

 

Stochastic Adjacency Matrix을 새로 정의하여 해결할 수 있다. 

$i$번째 page의 out-link 개수를 $d_i$라 하자. $i \to j$인 link가 있다면 $M_{ji}=\frac{1}{d_i}$이고, link가 없다면 $M_{ji}=0$으로 정의한다. ($i \to j$일때 $M_{ji}$를 정의한다. $M_{ij}$가 아니다.) 이렇게 만들어진 행렬 $M$은 column stochastic matrix이다. (각 컬럼의 합은 $1$이 된다.)

$r_i$는 $i$번째 노드의 importance score라 하면 $r_j = \sum_{i \to j}\frac{r_i}{d_i}$이고 $\sum_i r_i = 1$이다. 

이렇게 flow equation을 행렬으로 나타내면 다음과 같다.

\[ r = M \cdot r \]

위 방정식의 해 $r$를 구하면 곧 각 노드(페이지)의 importance를 구한 것이다.

 

Example: Flow Equations and $M$ (Stanford CS26)

 

Power Iteration Method

$r = Mr$의 rank vector $r$은 stochastic web matrix $M$의 eigenvector이다. 즉 임의의 stochastic vector $u (\neq \mathbf{0}$로부터 $M(M(\cdots M(Mu)))$의 극한을 취하면 곧 $r$이다. (증명은 아래)

Power Iteration Algorithm

input: $N$개의 node를 가진 web graph; node와 edge는 각각 page와 hyperlink이다.
initialize: $r^{(0)} = [1/N, \dots, 1/N]^\top$
iterate: $r^{(t+1)} = M \cdot r^{(t)}$
stop: $|r^{(t+1)} - r^{(t)}|_1 < \epsilon$

Notation
$r^{(t+1)}_j = \sum_{i \to j} \cfrac{r^{(t)}_i}{d_i}$
$|\mathbf{x}|_1 = \sum_{1 \le i \le N}|x_i|$ (L1 norm, $r$이 distribution이기 때문)

※ PageRank의 원래 논문인 "The PageRank Citation Ranking: Bringing Order to the Web"에 따르면 약 50번의 iteration이면 수렴한다고 한다.

The figure from original PageRank paper

 

위의 R, A, M 세 노드에 대한 rank vector를 power iteration을 이용하여 구하면 다음과 같다.

Example of Power Iteration (Stanford CS246)

Why power iteration works?

Claim: $M^k \cdot r$은 점점 $M$의 dominant(principal) eigenvector로 수렴한다.
Proof:
$M$이 $n$개의 eigenpair $(x_1, \lambda_1), \dots, (x_n, \lambda_n)$을 갖는다고 하자. 이때 $x_1, \dots, x_n$은 linearly independent하고, $\lambda_1 > \lambda_2 > \cdots > \lambda_n$이라 하자.

$x_1, \dots, x_n$은 basis로 간주할 수 있으므로 $r^{(0)}$은 다음과 같이 나타낼 수 있다.
\[ r^{(0)}=c_1 x_1 + c_2 x_2 + \cdots + c_n x_n \]
그러면 $Mr^{(0)}$은 다음과 같이 나타낼 수 있다.
\begin{align} Mr^{(0)} &= M(c_1 x_1 + \cdots c_n x_n) \\ &= c1(Mx_1) + \cdots c_n(Mx_n) \\ &= c1(\lambda_1 x_1) + \cdots c_n(\lambda_n x_n) \ (\because Mx_i = \lambda_i x_i)\end{align}

$k$번 반복하면
\begin{align} M^{(k)}r &= c_1(\lambda_1^k x_1) + c_2(\lambda_2^k x_2) + \cdots c_n(\lambda_n^k x_n) \\ &= \lambda_1^k \bigg[ c_1x_1 + c_2 \bigg( \cfrac{\lambda_2}{\lambda_1} \bigg)^k x_2 + \cdots + c_n \bigg( \cfrac{\lambda_n}{\lambda_1} \bigg)^k x_n \bigg] \end{align}
$k \to \infty$이면 $\bigg( \cfrac{\lambda_i}{\lambda_1} \bigg)^k \to 0 \ (i > 1)$가 된다.
따라서 $M^{(k)}r^{(0)} \approx c_1 (\lambda_1^k x_1)$

※ 참고로 Undirected Graph에서 PageRank를 계산할 때는 $r_i = \frac{d_i}{2m}$으로 바꾸어서 똑같이 계산하면 된다. 이때 $d_i$는 $i$번째 노드의 degree이고, $m$은 그래프 내의 전체 edge 개수이다.

Problems and Google's Solution

Problem 1: Dead-end problem

in-link만 있고 out-link가 없는 노드가 존재하면 생기는 문제다. random surfer가 이 노드에 갇혀서 어떤 페이지로도 방문이 불가능한 상황이다. 이를 importance "leak out"으로도 말하기도 한다. $r=Mr$을 계산하면 수렴하긴 하지만 $r=\mathbf{0}$으로 수렴하므로 이는 우리가 원하는 값이 아니다.

Dead end problem (Stanford CS246)

Problem 2: Spider trap

어떤 노드들끼리는 서로 그룹을 이루는 경우에 발생하는 문제다. random surfer는 해당 그룹내의 페이지에서만 방문하게 된다. (stuck in a trap). 즉 이 trap이 모든 importance를 흡수하는 문제가 발생한다. 

아래 예시에서는 spider trap인 $m$이 모든 importance를 흡수하여 혼자 $1$이고 나머지는 $0$이 된다.

Spider trap problem (Stanford CS246)

Dead ends & Spider trap problems (Stanford CS246)

Solution for Spider traps: Prababilistically Teleport

surfer가 trap에서 빠져나오도록 일정 확률로 아무 페이지(노드)를 방문하도록 한다. 즉 random surfer는 $\beta$의 확률로 주어진 link를 따라 방문하고, $(1-\beta)$의 확률로 임의의 랜덤 페이지로 점프하여 방문한다.

Surfer will teleport out of spider trap within a few time steps (Stanford CS246)

Solution for Dead ends: Always Teleport

Dead end는 Spider strap과 다르게 $M$ 자체가 column-stochastic하지 않아서 생기는 문제다. (애초에 numerically wrong)

Dead end가 발생하는 노드는 해당 노드 컬럼이 $\mathbf{0}$이므로, column stochastic하게 바꾸면 된다. 일반적으로 $[1/N]_N^\top$으로 바꾼다. 이는 곧 임의의 페이지 노드에 항상 텔레포트하도록 하는 효과를 갖는다. 

아래 예시에서 dead end인 $m$의 벡터를 $[1/3, 1/3, 1/3]^\top$으로 바꾼다. 

Adjust matrix accordingly (Stanford CS246)

 

PageRank Equation [Brin-Page, 1998]

dead end 노드도 $[1/N]$으로 채우고, spider trap을 해결한 PageRank 식은 다음과 같다.

\[ r_j = \sum_{i \to j} \beta \cfrac{r_i}{d_i} + (1-\beta)\cfrac{1}{N} \]

그리고 행렬의 형태로 나타낸 Google Matrix $A$는 다음과 같다. ($M$은 이미 dead end를 해결한 형태이다.)

\[ A = \beta M + (1-\beta) \left[ \cfrac{1}{N} \right]_{N \times N} \ (\beta \in [0.8, \ 0.9]) \]

Example of Random Teleports with $\beta=0.8 (Stanford CS246)

Computing PageRank

PageRank의 주된 연산은 반복적인 행렬-벡터 곱셈이다. ($r^{\text{new}} = A \cdot r^{\text{old}}$)

web-scale을 고려했을 때, 이 행렬-벡터 곱셈을 할 때 메모리를 초과하는 문제가 있다. 

 

PageRank 방정식을 다시 재배열하면 다음과 같다.

Google matrix $A$의 entry를 $A_{ji} = \beta M + \cfrac{1-\beta}{N}$이라 하면

\begin{align} r_j &= \sum_{i=1}^{N} A_{ji}r_i \\ &= \sum_{i=1}^{N} \left[ \beta M_{ji} + \frac{1-\beta}{N} \right] \cdot r_i \\ &= \sum_{i=1}^{N} \beta M_{ji} \cdot r_i + \frac{1-\beta}{N} \end{align}

\[ \therefore r = \beta M \cdot r + \left[ \frac{1-\beta}{N} \right]_{N} \]

 

원래 식보다 더 유리한 점은 $A$는 dense matrix이지만 $M$은 sparse matrix하다는 것이다.

Sparse Matrix Encoding

sparse matrix는 nonzero entry 정보만 저장한다. 따라서 main memory에는 맞지 않아고, disk에는 충분히 저장할 수 있다.

Sparse Matrix Encoding (Stanford CS246)

물론, 실제 디스크에는 2차원 표가 아니라 1차원으로 저장된다. source node 읽고, degree를 읽고, degree의 값만큼 destination을 읽고, 또 source node 읽고, ... 이런식으로 disk scan이 이루어진다. 이렇게 하면 disk를 1번만 읽고도 PageRank를 계산할 수 있다.

Sparse Matrix on Disk

1 step of power iteration

initialize $r^{\text{new}} = (1-\beta)/N$
for each page $i$:
    read into memory: $i$, $d_i$, $dest_1, \dots, dest_{d_i}$, $r^{(old)}(i)$
    for $j=1 \dots d_i$
        $r^{(new)}(dest_{j}) \pm \beta r^{(old)}(i) / d_i$ 

illustrate of update step

※ Still slow? Use MapReduce or Partitioning a matrix into square blocks (See MMDS textbook)

 

Still some problems with PageRank

• page의 popularity만 이용하여 topic-specific authority에 편향됨 → Topic-Specific PageRank
• importance의 지표를 하나만 이용 → Hubs-and-Authorities
• Link spam에 취약 → TrustRank