[ Day 24 ]

2021 부스트캠프 Day 24.

[Day 24] Graph

---

그래프의 정점을 어떻게 벡터로 표현할까?

정점 표현 학습

정점 표현 학습이란?

• 그래프의 정점들을 벡터의 형태로 표현하는 것

• 간단히 정점 임베딩(Node Embedding)으로도 부른다.

• 벡터 형태의 표현 그 자체를 의미

• 정점이 표현되는 벡터 공간을 임베딩 공간이라고 부른다.

• 입력은 그래프로, 주어진 그래프의 각 정점 $u$에 대한 임베딩, 즉 벡터표현 $z$u가 정점 임베딩의 출력이다.
  
  

정점 표현 학습의 이유

• 정점 임베딩의 결과로, 벡터 형태의 데이터를 위한 도구들을 그래프에도 적용

• 기계학습 도구들이 한가지 예시이다.
  대부분 분류기(로지스틱 회귀분석, 다층 퍼셉트론 등) 그리고 군집 분석 알고리즘(K-Means, DBSCAN 등)은 벡터 형태로 표현된 사례(Instance)들을 입력으로 받는다

• 그래프의 정점들을 벡터 형태로 표현할 수 있다면, 위의 예시와 같은 대표적인 도구들 뿐 아니라, 최신의 기계 학습도구들을 정점 분류(Node Classification), 군집 분석(Community Detection) 등에 활용할 수 있다

정점 표현 학습의 목표

• Q : 어떤 기준으로 정점을 벡터로 변환해야 할까?

  • 그래프에서의 정점간 유사도를 임베딩 공간에서도 보존하는 것을 목표
    

• 임베딩 공간에서의 유사도로는 내적(Inner Product)을 사용한다.

• 내적은 두 벡터가 클수록, 그리고 같은 방향을 향할 수록 큰 값을 갖는다.
  

• 정리하면, 정점 임베딩은 다음 두 단계로 이루어진다.

  • 그래프에서의 정점 유사도를 정의하는 단계
  • 정의한 유사도를 보존하도록 정점 임베딩을 학습하는 단계

인접성 기반 접근법

인접성 기반 접근법

• 두 정점이 인접할 떄 유사하다고 간주.

• 두 정점 u와 v가 인접하다는 것은 둘을 직접 연결하는 간선 (u,v)가 있음을 의미

• 인접행렬(Adjacency Matrix) A의 u행 v열 원소 Au,v은 u와 v가 인접한 경우 1, 아닌 경우 0이다.

• 인접행렬의 원소 Au,v를 두 정점 u와 v의 유사도로 가정.
  

• 손실 함수 (Loss Function)은 아래와 같다.
  

• 즉, 이 손실함수가 최소가 되는 정점 임베딩을 찾는 것을 목표
  손실함수 최소화를 위해서는 (확률적) 경사하강법 등이 사용된다.

인접성 기반 접근법의 한계

• 인접성만으로 유사도를 판단하는 것은 한계가 있다.

• 빨간색 정점과 파란색 정점은 거리가 3인 반면 초록색 정점과 파란색 정점은 거리가 2이다.

• 인접성만을 고려할 경우 이러한 사실에 대한 고려 없이, 두 경우의 유사도는 0으로 같다
  

• 군집 관점에서는 빨간색 정점과 파란색 정점은 다른 군집에 속하는 반면, 초록색 정점과 파란색 정점은 같은 군집에 속한다.

• 인접성만을 고려할 경우 이러한 사실에 대한 고려없이, 두 경우의 유사도는 0으로 같다.

거리/경로/중첩 기반 접근법

거리 기반 접근법

• 거리 기반 접근법에서는 두 정점 사이의 거리가 충분히 가까운 경우 유사하다고 간주

• 예를 들어, “충분히”의 기준을 2로 가정.
  

• 빨간색 정점은 초록색 그리고 파란색 정점들과 유사하다. 즉 유사도가 1이다.
  반면, 빨간색 정점은 보라색 정점과는 유사하지 않다. 즉 유사도가 0이다

경로 기반 접근법

• 두 정점 사이이의 경로가 많을 수록 유사하다고 간주

• 정점 u와 v사이의 경로(Path)는 아래 조건을 만족하는 정점들의 순열이다.

  • u에서 시작해서 v로 끝나야 한다.
  • 순열에서 연속된 정점은 간선으로 연결되어 있어야 한다.

• 두 정점, u와 v사이의 경로중 거리가 k인 것의 수는 Aku,v와 같다.

• 즉, 인접행렬 A의 k제곱의 u행 v열 원소와 같다.

• 경로기반 접근법의 손실함수는 다음과 같다.
  

중첩 기반 접근법

• 두 정점이 많은 이웃을 공유할 수록 유사하다고 간주.

• 아래 그램에서 빨간색 정점은 파란색 정점과 두 명의 이웃을 공유하기 때문에 유사도는 2가 된다.
  

• 정점 u의 이웃집합을 N(u), 그리고 정점 v의 이웃 집합을 N(v)라고 하면, 두 정점 공통이웃 수는 다음과 같이 정의된다.
  

• 손실함수는 다음과 같다.
  

• 공통 이웃 수 대신 자카드 유사도 혹은 Adamic Adar 점수를 사용할 수도 있다.

• 자카드 유사도(Jaccard Similarity)는 공통 이웃의 수 대신 비율을 계산하는 방식
  

• Adamic Adar 점수는 공통 이웃 각각에 가중치를 부여하는 가중합을 계산하는 방식
  

임의보행 기반 접근법

임의보행 기반 접근법

• 한 정점에서 싲가하여 임의보행을 할 때 다른 정점에 도달할 확률을 유사도로 간주.

• 임의 보행이란 현재 정점의 이웃 중 하나를 균일한 확률로 선택하는 이동과정을 반복하는 것을 의미

• 임의보행을 사용할 경우 시작 정점 주변의 지역적 정보와 그래프 전역정보를 모두 고려한다는 장점이 있다.

• 다음 세 단계를 거친다.

  • 각 정점에서 시작하여 임의보행을 반복 수행.
  • 각 정점에서 시작한 임의보행 중 도달한 정점들의 리스트NR(u)를 구성한다.
    한 정점을 여러 번 도달한 경우, 해당 정점은 NR(u)에 여러번 포함 될 수 있다.
  • 다음 손실함수를 최소화하는 임베딩을 학습한다.
    

• Q : 어떻게 임베딩으로부터 도달 확률을 추정할까?
  

  • 즉 유사도 zTvzu가 높을 수록 도달 확률이 높다.
    

DeepWalk와 Node2Vec

• 임의보행의 방법에 따라 DeepWalk와 Node2Vec이 구분

• DeepWalk는 앞서 설명한 기본적인 임의보행을 사용
  즉, 현재 정점의 이웃 중 하나를 균일한 확률로 선택하는 이동하는 과정을 반복

• Node2Vec은 2차 치우친 임의보행(Second-order Biased Random Walk)을 사용
  현재 정점(예시에서 𝑣)과 직전에 머물렀던 정점(예시에서 𝑢)을 모두 고려하여 다음 정점을 선택, 직전 정점의 거리를 기준으로 경우를 구분하여 차등적인 확률을 부여
  

• Node2Vec에서는 부여하는 확률에 따라서 다른 종류의 임베딩을 얻는다.
  아래 그림은 Node2Vec으로 임베딩을 수행한 뒤, K-means 군집 분석을 수행한 결과
  

• 멀어지는 방향에 높은 확률을 부여한 경우, 정점의 역할(다리 역할, 변두리 정점 등)이 같은 경우 임베딩이 유사하다.

• 가까워지는 방향에 높은 확률을 부여한 경우, 같은 군집(Community)에 속한 경우 임베딩이 유사하다.

손실 함수 근사

• 임의 보행 기법의 손실함수는 계산에 정점의 수의 제곱에 비례하는 시간이 소요된다.
  

• 따라서 많은 경우 근사식을 사용한다.
  모든 정점에 대해서 정규화하는 대신 몇 개의 정점을 뽑아서 비교하는 형태이다.
  이 때 뽑힌 정점들을 네거티브 샘플이라고 부른다.
  연결성에 비례하는 확률로 네거티브 샘플을 뽑으며, 네거티브 샘플이 많을 수록 학습이 더욱 안정적이다.
  

변환식 정점 표현 학습의 한계

변환식 정점 표현 학습과 귀납식 정점 표현 학습

• 위 정점 임베딩 방법들은 변환식(Transductive)방법이다.

• 변환식 방법은 학습의 결과로 정점의 임베딩 자체를 얻는다는 특성이 있다.

• 정점을 임베딩으로 변화시키는 함수, 즉 인코더를 얻는 귀납식(Inductive)방법과 대조된다.

변환식 정점 표현 학습의 한계

• 변환식 임베딩 방법은 여러 한계를 갖는다.
  • 학습이 진행된 이후에 추가된 정점에 대해서는 임베딩을 얻을 수 없습니다
  • 모든 정점에 대한 임베딩을 미리 계산하여 저장해두어야 합니다
  • 정점이 속성(Attribute) 정보를 가진 경우에 이를 활용할 수 없습니다

---

그래프를 추천시스템에 어떻게 활용할까? (심화)

넷플릭스 챌린지 소개

넷플릭스 챌린지 데이터셋

• 사용자별 영화 평점 데이터가 사용.

• 훈련 데이터(Training Data)는 2000년 부터 2005년 까지 수집한 48만명 사용자의 1만 8천개의 영화에 대한 1억개의 평점으로 구성

• 평가 데이터(Test Data)는 각 사용자의 최신 평점 280만개로 구성되어 있다.
  

넷플릭스 챌린지 대회 소개

• 넷플릭스 챌린지의 목표는 추천시스템의 성능을 10%이상 향상시키는 것

• 평균 제곱근 오차 0.9514을 0.8563까지 낮출 경우 100만불의 상금을 받는 조건

• 2006년부터 2009년까지 진행되었으며, 2700개의 팀이 참여

• 넷플릭스 챌린지를 통해 추천시스템의 성능이 비약적으로 발전
  

기본 잠재 인수 모형

잠재 인수 모형 개요

• 위 넷플릭스 챌린지에서 성공한 모델로 현재까지도 많이 사용되고 있다.

• 핵심은 사용자와 상품을 벡터로 표현하는 것.
  

• 고정된 인수 대신 효과적인 인수를 학습하는 것을 목표로 한다.
  학습한 인수를 잠재 인수(Latent Factor)라고 한다.
  

손실 함수

• Q : 사용자와 상품을 임베딩 하는 기준은 무엇인가?

  • 사용자와 상품의 임베딩의 내적(Inner Product)이 평점과 최대한 유사하도록 하는 것.
  • 사용자 x의 임베딩을 px, 상품 i의 임베딩을 qi
  • 사용자 x의 상품 i에 대한 평점을 rxi
  • 임베딩의 목표는 pxTqi이 rxi와 유사하도록 하는 것이다.

• 행렬 차원으로 보면 아래와 같다.
  (R : 평점 행렬, P : 사용자 행렬, Q : 상품 행렬)
  

• 잠재 인수 모형은 다음 손실함수를 최소화하는 P와 Q를 찾는 것을 목표로 한다.
  

• 하지만, 위 손실함수를 사용할 경우 과적합(Overfitting)이 발생할 수 있다.

• 따라서 과적합을 방지하기 위해 정규화 항을 손실함수에 더해준다.
  

• 정규화의 세기가 클수록 모형 복잡도에 조금더 집중해서 최소화를 하고, 작을수록 오차에 집중해서 최소화를 한다.

최적화

• 손실함수를 최적화하는 P와 Q를 찾기 위해서는 (확률적)경사하강법을 사용한다.
  

고급 잠재 인수 모형

사용자와 상품의 편향을 고려한 잠재 인수 모형

• 각 사용자의 편향은 해당 사용자의 평점 평균과 전체 평점 평균의 차이다.

• 예시:

  • 나연이 매긴 평점의 평균이 4.0, 다현이 매긴 평점평균이 3.5이고 전체 평점평균이 3.7일때, 나연의 사용자 편향은 4.0-3.7=0.3이고, 다현의 사용자 편향은 3.5-3.7=-0.2이다.

• 개선된 잠재 인수 모형에서는 평점을 전체평균, 사용자 편향, 상품 편향, 상호작용 으로 분리한다.
  

• 손실함수는 아래와 같다.
  

• 결과
  

시간에 따른 편향을 고려한 잠재 인수 모형

• 넷플릭스 시스템의 변화로 평균 평점이 크게 상승하는 사건이 있었다.
  

• 영화의 평점은 출시일 이후 시간이 지남에 따라 상승하는 경향을 갖는다.
  

• 개선된 잠재 인수 모형에서는 이러한 시간적 편향을 고려한다.

• 구체적으로 사용자 편향과 상품 편향을 시간에 따른 함수로 가정.
  

• 결과
  

넷플릭스 챌린지의 결과

앙상블 학습

• BellKor 팀은 앙상블 학습을 사용하여 처음으로 목표 성능에 도달하였다.
  

• BellKor 팀의 독주에 위기감을 느낀 다른 팀들은 연합팀 Ensemble을 만들었다.
  

• 그 결과 Ensemble팀 역시 목표 성능에 도달하였다.

넷플릭스 챌린지의 우승팀

• 넷플릭스 챌린지 종료 시점에 BellKor 팀 Ensemble 팀의 오차는 정확히 동일했다.
  하지만 BellKor 팀의 제출이 20분 빨랐고, 우승을 하였다.