[기계학습] GML - Ranking

Background 

그래프란? 

그래프란 엔티티(노드)와 관계(엣지)를 표현하는 일반적인 구조이다. 

 

그래프는 행렬로 표현할 수 있는데, 이 행렬 표현을 통해 노드 랭킹, 행렬 분해, 노드 임베딩 등의 다양한 응용이 가능하다. 

 

 

 

웹과 그래프 

웹페이지는 방향 그래프로 볼 수 있다. 

각 노드는 웹 페이지로, 각 엣지는 하이퍼링크로 해석할 수 있다. 

 

특정 노드 v에서 어디에 도달 가능하고, 누가 v에 도달가능할까? 라는 질문을 할 수 있고, 이 질문은 어떤 페이지가 더 중요한가?라는 질문으로 이어진다. 

 

그럼 모든 웹 페이지는 다 동일한 중요도를 가지고 있을까? 

그것은 아니다. 

 

예를 들어 naver.com는 엄청 많은 사이트에서 링크되지만, 내 개인 블로그는 링크가 거의 없다.. 

이 둘이 중요도가 같을 수는 없는 것이다. 

 

그럼 웹 페이지의 랭크는 어떤 방식으로 부여할 수 있을까? 

과거에 검색 시스템은 단순히 단어 빈도수로 랭킹을 매겼는데, 이 방식은 악용이 가능해서 지금은 사용되지 않는다. 

 

---

Ranking 

Node Ranking on Graphs 

💡 핵심 아이디어 

핵심 아이디어는 링크를 투표라고 생각하는 것이다. 

어떤 펭지가 다른 많은 페이지로부터 링크를 많이 받으면 해당 페이지는 더 중요한 페이지라고 판단할 수 있다. 

이 때 들어오는 링크를 투표로 간주한다. 

 

예를 들어 naver.com는 많은 웹사이트에서 링크되어 있다. 이는 이 페이지의 중요도가 높다고 판단할 수 있다. 

하지만 단순히 링크 개수만으로 중요도를 판단하는 것은 위험하다. 

모든 링크가 똑같이 중요한 것은 아니기 때문이다. 

 

 

PageRank : Google Algorithm 

💡 핵심 아이디어 

PageRank의 핵심 아이디어는 중요한 페이지로부터의 링크는 더 가치가 크다는 것이다. 

어떤 페이지가 다른 중요한 페이지들로부터 링크를 받으면, 그 페이지 또한 중요하다고 여기는 것이다. 

 

📍 수식 

아래 식은 페이지 j의 중요도를 구하는 수식이다. 

 

rj : 페이지 j의 중요도

ri : 페이지 i의 중요도 

di : 페이지 i에서 나가는 링크 수 

 

이 수식을 통해 알 수 있는 것은 PageRank는 링크의 가중치를 고려한 투표 시스템이라는 것이다. 

PageRank의 수학적 정의 

📍 M : 확률적 인접 행렬 (stochastic adjacency matrix) 

어떤 노드 i에서 j로 링크가 있을 경우 아래 식을 따른다는 것이다. 

 

이 랭크 벡터 r은 아래처럼 업데이트 된다. 

 

 

 

예시 

3개의 노드의 관계를 인접 행렬로 나타낸다. 

여기서 M은 노드 1이 각각 노드 1, 노드 2로 갈 확률은 1/2, 노드 2가 각각 노드 1, 노드 3으로 갈 확률은 1/2, 노드 3이 노드 2로 갈 확률은 1이라는 의미를 가진다. 

초기 PageRank값은 모두 동일해야 하기 때문에 1/3씩 넣어준다. 

공식에 맞게 계산만 하면 끝 ! 

 

 

 

PageRank와 Random walk 

PageRank는 실제로는 랜덤 서퍼(random surfur) 모델이다. 

사용자가 아무 웹페이지에서 시작하여 무작위로 링크를 따라간다고 가정하면 어떨까?

 

 

위의 식은 결국 랜덤 워커가 어느 페이지에 있을 확률 분포를 나타낸다. 

이 과정을 계속해서 반복하다보면, 수렴하는 순간이 오고, 그게 바로 PageRank의 결과가 된다. 

 

 

PageRank : How to Solve 

PageRank의 목표는 정상 분포(stationary distribution)를 찾는 것이다. 

즉, 더 이상 중요도 값이 변하지 않는 상태를 찾는 것이다. 

 

수렴 조건은 아래와 같다. (ϵ - 아주 작은 값으로 작은 오차 범위는 허용한다는 의미) 

 

결국 모든 노드에 방문하는 사용자의 비율이 고정되면, 그게 바로 최종 PageRank가 되는 것이다. 

 

 

🔸 계산 예시 

PageRank를 구하는 과정은 2가지로 나뉜다. 

1. 초기화 

모든 노드에 동일한 점수를 할당한다. 

여기서는 노드가 3개이므로 1/3씩 할당한다. 

 

2. 반복 계산 (수렴까지) 

수렴할 때까지 계속해서 반복해주면 된다. 

계속 곱하다 보면 점수들이 변하지 않는 구간이 오는데, 그 때가 수렴하는 순간인 것이다. 

 

 

 

PageRank의 문제점 

PageRank에도 문제점이 있는데 크게 2가지로 나뉜다. 

이 문제는 PageRank가 수렴하지 않거나, 왜곡된 결과를 낼 수 있는 문제이다. 

 

 

1️⃣  Dead End : 막다른 골목 

어떤 노드에 나가는 링크가 아예 없을 때, 그 노드에 들어온 중요도가 증발한다. (점수 유출) 

예를 들어 마지막 페이지나 외부 링크가 없는 페이지 등이 여기에 해당된다. 

 

🛠️ 해결법 

해당 문제를 해결하기 위해서는 텔레포트 개념을 도입해야 한다. 

랜덤 서퍼가 더 이상 갈 곳이 없으면, 무작위로 다른 모든 노드 중 하나로 순간이동 하도록 하는 것이다. 

 

이렇게 하면 막힌 노드도 일정 확률로 빠져나게 되고, 중요도 유출 문제도 방지할 수 있다. 

결과적으로 모든 노드가 연결된 확률적 인접 행렬이 유지되고 수렴 가능성이 높아지는 것이다. 

 

 

 

2️⃣  Spider Trap : 거미 덫 

특정 그룹 내에서만 링크가 순환할 때, 중요도가 그 그룹 안에서만 계속 맴돌며 빠져나오지 못한다. 

몇 개의 페이지가 서로만 연결된 사이클일 때 등이 여기에 해당된다. 

 

🛠️ 해결법 

해당 문제를 해결하기 위해서는 확률을 섞어야 한다. 

매 시간마다 확률 β (보통 0.8~0.9)가 링크를 따라 이동하고, 확률 (1-β)는 랜덤으로 아무 노드로나 텔레포트를 한다.

 

즉, 사용자가 링크를 누르기도 하고, 가끔은 새로 검색해서 랜덤한 페이지로 이동하는 것처럼 행동하는 것이다. 

이렇게 하면 Spider Trap에서 자연스럽게 빠져나올 수 있는 가능성이 생기고, 전체 그래프에서 공정한 순위 평가도 가능해진다. 

 

 

Google Matrix 

위의 문제를 해결하는 해결책을 모두 반영한 최종 PageRank 수식은 아래와 같다. 

 

앞쪽 부분은 기존의 링크 기반 중요도 방식을, 뒷부분은 텔레포트 개념을 추가하여 새로운 수식을 만든 것이다. 

 

이 수식을 행렬로 정리한 것이 바로 Google Matrix G이다.

 

 

예를 들어 β가 0.8이고 N이 3이면 아래와 같이 그래프를 구할 수 있다. 

 

 

 

PageRank 정리 

PageRank는 그래프의 구조를 분석하여 노드의 상대적 중요도를 계산하는 알고리즘이다. 

수식 r = r x G를 반복하여 계산하는 방식이다.

문제 해결을 위해 Google Matrix를 사용하고, 텔레포트 기법으로 Dead End & Spider Trap 문제를 해결한다. 

 

이렇게 계산된 중요도는 검색 엔진이나 추천 시스템 등에 사용된다.