cs224w_4
Graph as Matrix: PageRank, Random Walks and Embeddings
매트릭스 관점에서 그래프 분석과 학습을 조사
그래프를 행렬로 처리하면
- Random Walk를 통해 노드 중요도를 결정할 수 있다.(PageRank)
- Matrix factorization(MF)를 통해 노드 임베딩을 얻을 수 있다.
- 다른 노드 임베딩(e.g. Node2Vec)을 MF로 볼 수 있다. Random Walk, matrix factorization, node embedding은 관계가 깊다.
PageRank (aka the Google Algorithm)
Web as a graph: – Nodes = web pages – Edges = hyperlinks 예전에 웹 링크는 탐색형이었지만, 오늘날은 많은 링크가 포스트, 코멘트, 좋아요, 구매 등 다양하게 사용된다.
- 웹은 방향성이 있는 그래프
- 모든 웹 페이지는 동일하게 중요하지 않다.
- 웹 그래프의 노드 연결성에는 큰 다양성이 존재한다. -> 웹그래프의 링크 구조를 사용해 페이지의 랭킹을 정한다.
Link Analysis Algorithms
- PageRank
- Personalized PageRank (PPR)
- Random Walk with Restarts
Link as Votes
연결이 더 많은 페이지가 더 중요하다. (In-coming) 모든 입력 링크가 동일하게 중요한 것이 아니라 더 중요한 페이지로부터의 입력은 더 중요하게 여긴다. 재귀적인 문제
PageRank : The “Flow” Model
- 더 중요한 페이지로부터의 하나의 입력이 더 값지다
- 각 링크의 투표는 그것의 출발 페이지의 중요도에 비례
- 페이지 $i$가 중요도 $r_i$를 가지고 $d_i$개의 아웃링크를 가질 때, 각각의 링크는 $r_i/d_i$의 중요도를 가진다.
- page j의 중요도 $r_j$는 그것의 인링크 중요도의 총합
PageRank : Matrix Formulation
- Stochastic adjacency matrix $M$
- page $j$는 $d_j$의 아웃링크를 가지고,
- $j$ -> $i$면, $M_{ij}$ = $\frac{1}{d_j}$ (M은 열 확률 행렬 : 열의 합이 1)
- Rank vector $r$ : 한 페이지의 항목
- $r_i$는 페이지 $i$의 중요도
- $\sum_ir_i$ = 1
Connection to Random Walk
한 랜덤 윕 서퍼를 떠올리면,
- 어떤 시간 t에 서퍼는 페이지 i에 있다.
- 시간 t+1에 서퍼는 균일하게 무작위로 i의 아웃링크를 따라간다.
- i에서 연결된 어떤 페이지 j로 도착한다.
- 프로세스가 무한히 반복된다.
$p(t)$ : $i^{th}$ 좌표가 시간 t에 i페이지에 있는 확률인 벡터 -> $p(t)$는 페이지에 대한 확률 분포
The Stationary Distribution
- t+1시간에 서퍼는 어디에 있을까?
- 균일하게 랜덤인 한 링크를 따라간다. $p(t+1)$ = $M\cdotp p(t)$
- 랜덤워크가 다음에 상태에 도달했다고 가정하면, $p(t)$는 랜덤워크의 정상분포이다. $p(t+1)$ = $M\cdot p(t)$ = $p(t)$
-
$r = M\cdot r$을 만족 $r$은 랜덤워크에 대한 정상분포
- 랭크 벡터 $r$은 확률 인접 행렬 $M$의 고유벡터(고유값이 1인)
- PageRnak = 제한 분포 = $M$의 주 고유벡터
요약
PageRank
- 웹의 연결 구조를 사용하여 그래프 내 노드의 중요도를 측정
- 확률적 인접행렬 $M$을 사용하여 랜덤 웹 서퍼 모델링
- 페이지랭크는 $r$을 $M$의 주 고유벡터로 보고, 그래프에서 랜덤워크의 정상분포로 봄으로써 $r=Mr$을 해결
PageRank : How to solve?
노드가 n개인 그래프가 주어졌을 때, 우리는 반복적인 절차를 수행한다.
- 각 노드에 초기 page rank를 할당
-
수렴할 때까지 반복 ( $\Sigma_i r^{t+1}_i - r^t_i < \epsilon$ )
Power Iteration Method
N개의 노드를 가진 웹 그래프 -> 노드 - 페이지 / 엣지 - 하이퍼링크
- Power iteration : 간단한 반복 스키마
- 초기화 : $r^0$ = $[1/N, … , 1/N]^T$
- 반복 : $r^{t+1} = M \cdot r^t$
-
$ r^{t+1} - r^t _1 < \epsilon$ 일 때, 정지
약 50번의 반복은 제한적인 해결책을 평가하는데 충분하다.
의문점
- 수렴하긴 하는가?
- 우리가 원하는 결과로 수렴하는가?
- 결과가 합리적인가?
문제점
- Dead ends - 아웃링크를 갖지 않음. -> 중요도가 유실
- Spider traps - 모든 아웃링크들이 그룹에 속함. -> 결과적으로 모든 중요도를 흡수
- Solution to Dead Ends Teleports : Dead-ends에서 토탈 확률이 1.0으로 랜덤 순간이동 링크를 따른다. —-
- Solution to Spider Traps 각 time step에서 random surfer는 2가지 옵션을 갖는다.
- 확률 $\beta$로 하나의 랜덤 링크를 따른다.
- 확률 $1-\beta$로 랜덤 페이지로 점프한다. 일반적으로 $\beta$값은 0.8에서 0.9정도로 한다. 서퍼는 스파이더 트랩에서 몇번의 타임스텝 내에 순간이동해서 스파이더 트랩을 탈출한다.
Why Teleports Solve the Problem?
- Spider-traps은 문제는 아니다. 하지만 트랩들의 PageRank 스코어는 우리가 원하는 방식의 값이 아니다.
- 해결책 : 유한한 횟수의 스탭 내에 순간이동으로 스파이더 트랩에 갇히지 않도록 한다.
- Dead-ends는 문제가 맞다. 행렬이 열에 대해서 확률적이지 않기 때문에 초기 가정이 만족되지 않는다.
- 해결책 : 행렬이 열에 대해서 확률적일 수 있도록 더 갈곳이 없는 상황일 때는 순간이동을 한다.
Solution : Random Teleports
- 확률 $\beta$로 하나의 랜덤 링크를 따른다.
- 확률 $1-\beta$로 랜덤 페이지로 점프한다.
Solving PageRank : Summary
- PageRank는 $r = Gr$을 해결하고 확률적 인접행렬($G$)의 거듭제곱으로 효율적으로 계산할 수 있게 함.
- 균일한 확률의 랜덤 순간이동을 더함으로써 dead-ends, spider-traps 이슈를 해결
Random Walk with Restarts and Personalized PageRank
Bipartite User-Item Graph
- Goal : Proximity to graphs
- Q와 관계가 있는 사용자에게는 어떤 아이템을 추천해야하는가?
- Intuition : 만약 Q와 P가 비슷한 사용자와 관계있다면, Q와 관계가 있는 사용자에게 P를 추천
Proximity on Graphs
- PageRank:
- 중요도에 따라 노드를 순위매긴다.
- 균일한 확률로 네트워크 내 어떤 노드로 순간이동 한다.
- Personalized PageRank:
- 텔레포트 노드 S에 대한 노드 근접성을 순위 매긴다.
- Proximity on graphs:
- Q : 무엇이 아이템 Q와 가장 관계있는가?
- Random Walks with Restarts:
- 시작 노드 S로 다시 순간이동
Random Walks
- Idea :
- 모든 노드는 어떤 중요도를 갖고 있다.
- 중요도는 모든 엣지로 균등하게 분할되어 이웃으로 푸시된다.
- Benefits :
- 왜 이것이 좋은 해결책인가?
- “유사도”에 대한 고려 때문
- Multiple connections
- Multiple paths
- Direct and indirect connections
- Degree of the node
Summary : PageRank Variants
- PageRank:
- 다른 노드로 순간이동
- 노드들은 랜덤 서퍼가 도달할 동일한 확률을 가진다. S = [0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1]
- Topic-Specific PageRank aka Personalized PageRank:
- 특정 세트의 노드로 순간이동
- 노드들은 랜덤 서퍼가 도달할 서로 다른 확률을 가질 수 있다. S = [0.1, 0, 0, 0.2, 0, 0, 0.5, 0, 0, 0.2]
- Random Walk with Restarts:
- 순간이동은 항상 같은 노드를 향하는 Topic-Specific PageRank S = [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
- 그래프는 행렬로 표현될 수 있다.
- 그래프에서의 Random walk process 정의
- 랜덤 서퍼는 연결을 따라서 이동하고 랜덤 순간이동을 한다.
- 확률적 인접행렬 M
- PageRank : 노드 중요도를 나타내는 서퍼 위치에 대한 제한된 분포
- 변환된 인접 행렬 M의 선행 고유 벡터에 해당
Matrix Factorization and Node Embeddings]
Embeddings & Matrix Factorization
Recall : 임베딩 룩업으로서의 인코더
Connection to Matrix Factorization
- simplest node similarity : 노드 u,v가 엣지로 연결되어 있다면 둘은 비슷하다.
- $z_v^T z_u$ = $A_{u,v}$ : 그래프 인접 행렬 A의 (u,v) 항목
- 그러므로, $Z^T Z = A$
Matrix Factorization
- 임베딩 차원 d(Z의 로우 수)는 노드의 수 n보다 훨씬 작다.
- 정확한 인수분해 $A = Z^TZ$는 일반적으로 가능하지 않다.
- 하지만, 우리는 Z를 대략적으로 학습할 수 있다.
- $A - Z^TZ$의 L2 normd이 최소화되도록 Z를 최적화 한다.
- 3장에서 L2 norm대신 소프트맥스를 사용했는데 그 목적은 같다.
- 결론 : 엣지 연결에 의해 정의된 노드 유사도를 가진 내적 디코더는 A의 MF와 동일하다.
Random walk-based Similarity
- DeepWalk 와 node2vec은 random walks보다 더 복잡한 노드 유사도 정의를 가진다.
- DeepWalk는 다음의 복잡한 행렬식의 인수분해와 같다.
- Node2vec 또한 행렬 인수분해로 공식화 될 수 있다.
Limitations
- MF와 Random Walks를 통한 노드 임베딩의 한계 training set에 있지 않은 노드의 임베딩을 얻을 수 없다.
- 구조적 유사성을 포착하지 못한다.
- DeepWalk 와 node2vec은 구조적 유사성을 포착하지 못한다.
- 노드, 엣지, 그래프의 기능을 활용할 수 없다. -> 해결책으로 Deep Representation Learning and Graph Neural Networks
Summary
- PageRank
- 그래프의 노드들의 중요도를 측정
- 인접행렬의 거듭제곱을 통해 효율적으로 계산 할 수 있다.
- Personalized PageRank(PPR)
- 특정 노드 또는 노드 셋에 대한 노드 중요도를 측정
- random walk를 통해 효율적으로 계산
- Node embedding based on random walks can be expressed as matrix factorization
- 그래프를 행렬으로 보는 것이 중요!