오늘은 CS224W에서 PageRank를 정리했다.
강의의 핵심은 “PageRank라는 알고리즘 하나”가 아니라, 그래프를 행렬로 표현하는 관점을 얻는 순간
- 링크 기반 직관(투표/흐름)
- 랜덤 워크 직관(랜덤 서퍼)
- 선형대수 직관(고유벡터/파워 반복)
- 더 나아가 노드 임베딩(DeepWalk/node2vec)과 행렬분해 연결
이게 사실상 한 덩어리로 합쳐진다는 점이었다.
1. 웹을 “방향 그래프”로 본다: 노드=페이지, 엣지=하이퍼링크
PageRank의 출발점은 웹 검색이다.
- 노드(node): 웹페이지
- 방향 간선(directed edge): 하이퍼링크 (A 페이지가 B로 링크하면 A → B)
초기의 웹은 “정적 페이지 + 탐색용 링크(navigational links)” 중심이었고, 이런 환경에서는 링크 구조 자체가 꽤 중요한 신호가 된다.
비슷한 예로는
- 논문 인용 네트워크(citation): 논문 i가 논문 j를 인용하면 i → j
- 위키피디아 레퍼런스/링크: 개념 간 참조 관계를 그래프로 표현
이제 질문은 하나로 정리된다.
“링크 구조만으로도 어떤 노드(페이지)가 더 중요하고 신뢰할 만한지 랭킹할 수 있을까?”
2. “링크는 투표다” → 근데 투표의 가치는 투표자가 결정한다 (재귀성)
가장 단순한 생각은 이거다.
- 어떤 페이지가 in-link(들어오는 링크) 를 많이 받으면 중요하다.
- out-link는 내가 마음대로 만들 수 있어서 조작 쉬움
- in-link는 남이 나에게 걸어줘야 하니 상대적으로 조작 어려움
하지만 바로 한 단계 더 가면 이런 생각이 든다.
“중요한 페이지로부터의 링크는 더 가치 있어야 하지 않나?”
여기서부터 재귀(recursive) 가 시작된다.
- 페이지 j의 중요도는
- j를 가리키는 페이지들의 중요도에 달려 있고
- 그 페이지들의 중요도 역시
- 또 그들에게 들어오는 링크에 달려 있다
즉, 모든 노드 중요도가 서로 얽혀 있는 형태가 된다.
3. PageRank의 “흐름(flow) 모델”: 중요도는 out-link로 균등 분배된다
강의에서 수학적으로 공식화한 핵심 룰:
- 페이지 i의 중요도를 r_i
- out-degree(나가는 링크 수)를 d_i 라고 하면,
- i가 가리키는 각 링크는 r_i / d_i 만큼의 “투표량(중요도)”를 보낸다.
그래서 어떤 노드 j의 PageRank는
즉,
- “나를 가리키는 애들이”
- “자기 중요도를 out-link 수만큼 나눈 몫”
- 을 합친 값이 내 중요도다.
이 문장을 더 직관적으로 바꾸면:
중요한 페이지가 나를 링크하면 나도 중요해진다.
(그리고 그 중요함은 out-link로 나뉘어서 전달된다.)
4. 작은 예시(3노드)로 연립방정식이 나온다
강의에서 예시로 3개의 페이지 y,a,my, a, m이 있을 때, 링크 구조에 따라
같은 연립방정식이 생긴다.
여기서 “가우스 소거법으로 풀면 되지 않나?” 라고 생각할 수 있는데, 실제 웹은
- 노드 수: 수십억
- 간선 수: 수백억
이므로 연립방정식을 정직하게 푸는 방식은 확장성 0 이다.
그래서 “우아한 방식”이 필요하고, 그게 바로 행렬화 + 파워 반복이다.
5. 그래프를 행렬로 표현: 확률적 인접행렬 MM (column stochastic)
여기서 강의가 본격적으로 “그래프를 선형대수로 바꾸는 순간”이 온다.
5.1 확률적 인접행렬 MM 정의
노드 j의 out-degree가 일 때,
- j가 i를 가리키면 Mi,j=1/dj
- 아니면 0
즉 j에서 나가는 링크는 확률적으로 균등하게 분배된다.
5.2 column stochastic의 의미
각 열(column)은 “현재 노드 j에서 다음에 어디로 갈지” 확률분포라서
- 한 열의 합은 항상 1
즉 모든 열이 확률분포인 행렬이다.
5.3 rank vector r
노드별 중요도를 모은 벡터 r를 만들고,
- ri: i의 중요도
- 전체 합은 1 (확률분포처럼)
6. PageRank 방정식이 한 줄로 정리된다: r=Mr
위에서 했던 “흐름 기반 정의”는 행렬로 쓰면 딱 한 줄이다.
r=Mr
이게 정말 예쁜 이유는:
- “나에게 들어오는 애들의 중요도/차수 합”이라는 흐름 정의
- “랜덤워크가 한 스텝 진행되는 분포 업데이트”
- “고유벡터(eigenvector) 방정식”
이 세 개가 전부 같은 수식으로 통합되기 때문이다.
7. 랜덤 워크 직관: “랜덤 서퍼”가 오래 걷다 보면 어디에 가장 자주 있나?
랜덤 서퍼(random surfer)를 상상한다.
- 어떤 페이지 i에 있으면
- out-link 중 하나를 균등 확률로 클릭
- 다음 페이지로 이동
- 무한히 반복
시간 t에서의 위치 분포를 p(t)라고 하면
그리고 시간이 충분히 지나면 분포가 안정화되어
이 p∗p^*가 바로 정상분포(stationary distribution)이고, 이걸 다시 쓰면
즉 PageRank rr은
랜덤 워크의 정상분포다.
8. 선형대수 직관: PageRank는 “고유값 1”에 대응하는 고유벡터
r=Mr
이걸 고유값-고유벡터 형태로 보면
- r은 행렬 M의 고유벡터
- 고유값은 1
그리고 M을 계속 곱하는 것은
- 랜덤 워커가 한 스텝 더 걷는 것과 동일
그래서
M^k u 를 k번 반복하면
장기적으로는 주고유벡터 방향으로 수렴한다.
이걸 계산하는 방법이 power iteration이다.
9. Power Iteration: “행렬-벡터 곱”을 반복하면 된다
알고리즘은 정말 단순하다.
- 초기화 (보통 균등분포)
- 반복
- 변화량 이 ϵ보다 작아지면 종료
강의에서 말하길 실제로는 보통 50번 내외 반복이면 수렴한다고.
이게 왜 중요하냐면, 구글은 웹 전체에 대해 매일 이걸 계산해야 하는데
- 연립방정식 풀이는 불가능
- 하지만 파워 반복은 “희소행렬 곱”만 반복하면 되어서 확장성이 엄청 좋다
10. 그런데 문제 발생: Spider trap / Dead end
여기서 “이론은 아름다운데 현실 그래프에서는 망한다” 포인트가 나온다.
10.1 Spider trap (갇힘 문제)
특정 부분 그래프가
- 내부로만 링크가 돌고
- 바깥으로 나가는 링크가 거의 없거나 없으면
랜덤 워커가 들어가는 순간 영원히 못 나옴
→ 그 집단이 PageRank를 다 빨아먹는 현상이 생김
→ 한 노드만 1, 나머지 0 같은 “원치 않는 랭킹” 발생
이건 수학적으로는 문제 아닐 수도 있지만, 우리가 원하는 결과가 아니기 때문에 문제.
10.2 Dead end (막다른 페이지)
out-link가 0인 노드가 있으면
- 랜덤 워커가 거기 도달한 순간 “더 이상 이동 불가”
- 확률질량이 그래프 밖으로 새어 나가듯 사라짐
이건 수학적으로도 문제다.
왜냐하면 해당 열의 합이 1이 아니라서 MM이 더 이상 column-stochastic이 아니게 되고, 기존 가정이 깨진다.
11. 해결책: Teleport(랜덤 점프) 추가 → Google PageRank
그래서 구글이 넣은 핵심 트릭이 “텔레포트”다.
- 확률 : 기존처럼 링크 따라가기
- 확률 1−β: 아무 노드나 랜덤 점프(teleport)
보통 β∈[0.8,0.9]를 쓴다.
11.1 새로운 PageRank 방정식
노드 j의 중요도:
- 링크 타고 j에 올 확률 + 텔레포트로 j에 떨어질 확률
11.2 행렬 형태
- 스파이더 트랩에 갇혀도 텔레포트로 빠져나올 수 있고
- dead end도 “갈 곳 없으면 텔레포트”로 처리하면 column stochastic 유지 가능
12. Personalized PageRank / Random Walk with Restart
PageRank의 “확장”은 사실 딱 한 가지 차이뿐이다.
텔레포트를 어디로 하느냐
12.1 Classical PageRank
- 텔레포트가 모든 노드로 균등
12.2 Personalized PageRank
- 텔레포트가 전체가 아니라 특정 집합 SS로만
- (예: 특정 주제/토픽 노드들로만 점프)
12.3 Random Walk with Restart (RWR)
- 텔레포트 집합 S가 “단 하나의 시작 노드”
- 즉, 랜덤 워커가 걷다가 확률 α\alpha로 항상 출발점으로 돌아감
이게 추천 시스템에서 엄청 직관적이었다.
- 사용자–아이템 bipartite graph에서
- query 아이템 Q를 시작점으로 랜덤워크를 돌리면
- Q와 “관련성이 높은 아이템”이 더 자주 방문됨
- 방문 횟수(또는 정상분포)가 곧 proximity/relatedness 점수가 된다
최단거리만 보는 것보다 훨씬 자연스럽다:
- 경로가 많을수록 점수↑
- 경로가 짧을수록 점수↑
- 중간 노드가 degree가 너무 크면(여기저기 연결) 확률이 흩어져서 점수↓
→ “진짜 강한 관계”를 더 잘 잡는다
13. (마지막 연결) 노드 임베딩 = 암묵적 행렬 분해(implicit matrix factorization)
강의 후반부에서 “이제 임베딩과 행렬 분해를 연결해보자”가 나온다.
13.1 가장 단순한 유사도 정의
“간선으로 연결되어 있으면 비슷하다”라고 정의하면
- adjacency matrix A에서
- 연결이면 1
- 아니면 0
노드 임베딩 Z를 학습해서
ZTZ≈AZ^T Z \
즉 내적 기반 디코더는 결국 “행렬 분해” 문제다.
정확히 같게는 못 만들고(임베딩 차원 D가 작으니까), 보통은 Frobenius norm으로 근사:
- 원소별 제곱오차 합 최소화
13.2 DeepWalk/node2vec는 더 복잡한 “변환된 행렬”을 분해한다
랜덤 워크 기반 유사도(“같이 등장”)를 쓰면
- 단순 A가 아니라
- 랜덤 워크 길이, 컨텍스트 윈도우, negative sampling 등을 반영한
transformed adjacency matrix를 분해하게 된다
즉 겉으로는
- 랜덤워크 샘플링하고
- skip-gram + negative sampling 최적화하는 것처럼 보이지만
다른 관점으로는
“특정 변환을 거친 행렬을 factorization하는 것”과 동치
(강의에서 언급한 “network embedding as matrix factorization” 류의 관점)
14. 지금 방식의 한계 → 그래서 다음은 GNN
랜덤워크/행렬분해 기반 임베딩(DeepWalk/node2vec)의 한계도 짚고 넘어갔다.
- 새 노드(out-of-sample node) 임베딩이 어려움
→ 그래프에 새 노드가 생기면 처음부터 다시 학습해야 함 - 구조적 유사성(structural similarity) 포착이 약함
→ 이웃의 “정체성(identity)”에 너무 민감
(구조는 비슷한데 주변 노드가 다르면 임베딩이 달라짐) - 노드/엣지 feature를 자연스럽게 쓰기 어려움
→ 구조만 보고 임베딩을 만들고, feature는 따로 취급하기 쉬움
이걸 해결하는 방향이 다음 주제:
Graph Neural Networks (GNNs)
구조 + 피처를 함께 섞어서(inductive하게) 임베딩을 만들 수 있다.
오늘의 한 줄 요약
그래프를 행렬 로 표현하는 순간,
- PageRank = 흐름 모델의 해 = 랜덤워크 정상분포 = 고유값 1의 고유벡터
- 계산은 파워 반복(행렬-벡터 곱 반복)으로 끝
- 현실 문제(spider trap/dead end)는 teleport로 해결
- teleport의 “대상”만 바꾸면 personalized PageRank / RWR로 확장
- 그리고 랜덤워크 기반 임베딩(DeepWalk/node2vec)은 결국 암묵적 행렬분해로 연결된다