[Study]Chapter 4. Link Analysis: PageRank
해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.
해당 강의에서는 행렬관점에서의 그래프 분석과 학습을 소개합니다.
I. Graph as Matrix
Web은 방향 그래프로 초기에는 탐색을 위한 것이었으나 오늘날에는 너무 많은 link가 생성되면서 중요하지 않은 link도 많이 생성되었습니다.
1. Link Anlysis Algorithms
따라서 우리는 Link Anlysis라는 방법으로 웹페이지의 중요도를 계산할 것입니다.
- Page Rank(a.k.a Google Algorithm)
- Personalized PageRank(PPR)
- Random Walk with Restarts
2. Link as Votes
웹 페이지 상에서 해당 페이지로 들어오는 In-coming links와 나가는 Out-goint links가 있을때, 들어오는 모든 link는 동등하다고 볼 수 있을까? 그렇지 않고, 분명 중요한 페이지에서의 연결(vote)이 더 중요하다.
Figure 1 : In-coming link에 비례하는 j노드의 중요도를 투표(계산).
- \(M\) : 열의 합이 1이고, \(M_{ij}=\frac{1}{d_j}\), \(d_j\):j에서의 out-link
- \(r_i\) : Rank vector, 들어오는 i 페이지의 중요도 점수로 그 합은 1이다.
따라서 페이지의 중요도는 가르키는\(_{point}\) 페이지가 중요할수록 더 중요해진다.
3. Eigenvector of A Matrix
- \(p(t)\); 페이지의 확률분포이다.
- \(p(t+1) = M \cdot p(t) = p(t)\); p(t) : stationary distribution.
이는 rank vector는 \(r = M \cdot r\)를 만족하여, stationary distribuion이라 할 수 있습니다.\
2번째 챕터에서의 인접행렬의 고유벡터는 \(\lambda c = Ac\)를 만족하는 것을 보았고, \(1\cdot r = M \cdot r\)로 정의할 수 있어 \(r\)은 \(M\)의 eigenvector가 됩니다. 따라서, 벡터 u에서 시작하는 \(M(M(...M(Mu)))\)를 장기 분포로 제한하는 “Power iteration”으로 효과적인 풀이가 가능하다.
즉, PageRank는 \(M\)의 극한 분포이자 주요 고유벡터이다.
II. PageRank : How to solve?
그래프 n 노드가 주어졌을때 반복 절차를 사용하여 아래와 같이 수렴할 때까지 반복하여 각 노드의 page rank(\(r_j^{t+1}=\sum_{i \rightarrow j}\frac{r_i^{(t)}}{d_i}\))를 계산할 수 있습니다.
\[\sum_i|r_i^{t+1}-r_i^t| < \epsilon\] Figure 2 : \(|x|_1 = \sum^N_1|x_1|\)은 L1 norm으로 유클리디안 이나 다른 vector norm으로 변경 가능
이러한 방법을 통해 두가지 의문점이 발생한다.
- 수렴성 : Spider traps; 모든 out-link가 그룹 안에 존재해 중요도를 흡수.
- 적합성 : Dead-end; out-link가 없는 경우, “leak out”의 주요 원인.
수렴성을 해결하기 위한 해결책으로 \(1- \beta\)의 확률로 다른 무작위 페이지로 넘어가는 것으로 spider trap의 구조를 teleport out으로 건너간다. 또한, 적합성도 마찬가지로 dead-end의 상황에서 무조건 무작위 teleport(1/N) 하도록 한다.
왜 이러한 텔레포트 전략이 문제를 풀 수 있는가?
이러한 전략은 우리가 원하는 PageRank 점수가 나오지 않는 Spider trap에 갇히지 않게 하고, Dead-end는 문제에서 행렬의 확률이 항상 무작위로 텔레포트 하는 것으로 풀 수 있다.
\[\begin{array}{ll} r_j = \sum_{i \rightarrow j}\beta\frac{r_i}{d_i}+(1-\beta)\frac{1}{N} \\ G = \beta M + (1-\beta)[\frac{1}{N}]_{N \times N} \end{array}\]PageRank equation
이렇게 텔레포트 전략을 포함한 Google Matrix \(G\)에서는 여전히 Power method가 작동한다.(\(\beta\) = 0.8 or 0.9)
출처 : https://en.wikipedia.org/wiki/PageRank
III. Personalized PageRank
아이템과 유저의 이분 그래프\(_{bipartite}\) 주어졌을때, 그래프의 근접성\(_{Proximity}\)을 계산하는 것으로 두 아이템이 유사한 유저들로 연결되어있다면 Q를 골랐을때 P를 추천하게끔한다.
- PageRank : 중요도로 순위를 매김, 시작노드 확률은 균일
- Personalized PageRank : 근접성으로 순위를 매김, 시작노드 확률은 비균일
그러면 여기서 그래프에서의 근접성(Q와 관련된 아이템)은 어떻게 계산하는가?
다양한 방법들(최단 거리, 공통 이웃 등)이 존재하는데 아래와 같은 방법이 존재한다.
IV. Random Walks with Restats
Query node \(Q\)가 주어졌을때 시작 노드(\(S={Q}\))에서 무작위 보행을 시뮬레이션하는 방법이다.
Figure 4 : 쿼리 노드에서 시작하여 연결된 유저들이 가진 item의 방문 count를 1씩 늘리는 작업을 반복
이는 여러 유사도를 고려하기 때문에 좋은 방법이다.
이러한 방법을 활용하면 각 노드에 방문횟수로 근접성이 평가되며 아이템과 유저로 이루어진 이분 그래프의 예시에서 가장 높은 근접성을 가진 node를 추천하게 되는 방법이다.
V. Matrix Factorization and Node Embeddings
가장 간단한 노드 유사도는 edge로 연결되어있으면 그래프의 인접행렬 A의 항목 (u,v)는 유사하다는 생각이다.
\[\begin{array}{ll} z_v^Tz_u = A_{u,v} \\ Z^TZ =A \end{array}\]여기서 일반적으로 \(Z^TZ =A\)는 불가능지만 \(Z\)를 근사하도록 학습은 가능하다.
Figure 10 : 각 임베딩 차원의 노드 vector 들이 모인 임베딩 행렬, d(임베딩 차원) « n(노드 수)
위와 같은 목적함수는 노드 쌍 (u,v)에서 유사성인 \(z_v^Tz_u\)를 최대화하는 것이다.
- \(A-Z^TZ\)의 L2 norm Frobenius norm을 최소화하는 방식으로 Z를 최적화할 수 있다.
- softmax 대신 L2를 사용하는데 \(A\)를 \(Z^TZ\)로 근사하는 목표는 같다.
가장 간단한 노드 유사성은 edge로 연결이 되어있으면 노드 u,v를 유사하다고 가정하는 것인데 이것은 \(z_v^Tz_u=A_{u,v}\)로 는 의 항목이다.
즉, edges의 연결성을 노드의 유사도로 정의하는 내적 곱(decoder)은 A의 행렬분해와 동일하게 볼 수 있다.
Figure 11 : 무작위 보행 기반의 유사도, node2vec1은 복잡한 행렬이더라도 행렬 분해 형식화가 가능
Limiatation
- 훈련 집합에 없는 노드의 임베딩은 얻을 수 없다.
- 구조적인 유사도를 수집할 수 없다.구조적으로 유사한 노드일지라도 매우 다른 임베딩을 얻게 된다.
- node, edge 그리고 graph의 특징을 활용할 수 없다.
이러한 제한의 해결방법은 깊은 표현 학습과 GNN이다!!!