Day 24. 정점 표현 & 추천시스템(심화)

1. 정점 표현 학습이란?

• 그래프의 정점들을 벡터의 형태로 표현하는 것 = 정점 임베딩
• 정점 표현 학습을 하는 이유
  • 정점 임베딩의 결과로, 벡터 형태의 데이터를 위한 도구들을 그래프에도 적용할 수 있음
• 목표
  • 임베딩 공간에서의 유사도로는 내적(inner product)를 사용함
    • 내적은 두 벡터가 클수록, 그리고 같은 방향을 향할수록 큰 값을 가짐
• 정점 표현 학습(정점 임베딩)의 두 단계
  • 1. 그래프에서 정점 유사도를 정의하는 단계
  • 2. 정의한 유사도를 보존하도록 정점 임베딩을 학습하는 단계

 

 

2. 인접성 기반 접근법

• 두 정점이 인접할 때 유사하다고 간주
• 두 정점 u와 v가 인접하다는 것은 둘을 직접 연결하는 간선 (u, v)가 있음을 의미
• 손실 함수
  • 이 손실 함수가 최소가 되는 정점 임베딩을 찾는 것이 목표
  • 손실 함수 최소화를 위해 (확률적) 경사하강법 등이 사용됨
• 인접성 기반 접근법의 한계
  • 직접 연결되어 있지 않으면 가까이 있어도 유사도 0

 

 

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

• 거리 기반 접근법: 두 정점 사이의 거리가 충분히 가까운 경우 유사하다고 간주
• 경로 기반 접근법: 두 정점 사이의 경로가 많을수록 유사하다고 간주
• 중첩 기반 접근법: 두 정점이 많은 이웃을 공유할수록 유사하다고 간주, 공통 이웃 수를 대신 자카드 유사도 혹은 Adamic Adar 점수를 사용할 수도 있음
  • 자카드 유사도: 공통 이웃의 수 대신 비율을 계산하는 방식
  • Adamic Adar: 공통 이웃 각각에 가중치를 부여하여 가중합을 계산하는 방식

 

 

4. 임의보행 기반 접근법

• 한 정점에서 시작하여 임의보행을 할 때 다른 정점에 도달할 확률을 유사도로 간주
  • 임의보행: 현재 정점의 이웃 중 하나를 균일한 확률로 선택하며 이동하는 과정을 반복하는 것
  • 임의보행을 사용할 경우 시작 정점 주변의 지역적 정보와 그래프 전역 정보를 모두 고려한다는 장점이 있음
• 임의보행 기반 접근법의 3단계
  • 1. 각 정점에서 시작하여 임의보행을 반복 수행
  • 2. 각 정점에서 시작한 임의보행 중 도달한 정점들의 리스트를 구성함
  • 3. 다음 손실 함수를 최소화하는 임베딩을 학습함

• 임의보행 방법에 따라 DeepWalk와 Node2Vec이 구분됨
• DeepWalk
  • 위의 기본적인 임의보행 사용
  • 즉, 현재 정점의 이웃 중 하나를 균일한 확률로 선택하며 이동하는 과정을 반복
• Node2Vec
  
  • 2차 치우진 임의보행(Second-order Biased Random Walk) 사용
  • 현재 정점과 직저넹 머물렀던 정점을 모두 고려하여 다음 정점을 선택
  • 직전 정점의 거리를 기준으로 경우를 구분하여 차등적인 확률을 부여
  • 따라서, 부여하는 확률(멀어지는 방향에 높은 확률 등)에 따라서 다른 종류의 임베딩을 얻음
    • 멀어지는 방향에 높은 확률을 부여한 경우, 정점의 역할(다리 역할, 변두리 정점 등)이 같은 경우 임베딩이 유사함
    • 가까워지는 방향에 높은 확률을 부여한 경우, 같은 군집(community)에 속한 경우 임베딩이 유사함
• 손실 함수 근사
  • 임의보행 기법의 손실함수는 계산에 정점의 수의 제곱에 비례하는 시간이 소요됨(중첩된 합 때문)

•  
  
  • 따라서 많은 경우 근사식을 사용함
  • 연결성에 비례하는 확률로 네거티브 샘플을 뽑으며, 네거티브 샘플이 많을수록 학습이 더욱 안정적
  • [참고] 임베딩 학습에 있어, multinomial classification을 학습의 효율을 위해 binary classification의 문제로 바꿀 수 있을 것. 이렇게 하면 sigmoid만으로도 학습이 가능해질 것. 시그모이드를 이용해 확률로 계산할 수 있음
  • [참고] 네거티브 샘플링은 Word2Vec이 학습 과정에서 전체 단어 집합이 아니라 일부 단어 집합에만 집중할 수 있도록 하는 방법

 

 

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

• 위의 정점 임베딩 방법들은 변환식(Transductive) 방법임
• 변환식 방법은 학습의 결과로 정점의 임베딩 자체를 얻는다는 특성이 있음
• 정점을 임베딩으로 변화시키는 함수, 즉 인코더를 얻는 귀납식(Inductive) 방법과 대조됨
• 한계
  • 학습이 진행된 이후 추가된 정점에 대해서는 임베딩을 얻을 수 없음
  • 모든 정점에 대한 임베딩을 미리 계산하여 저장해두어야 함
  • 정점이 속성(Attribute) 정보를 가진 경우에 이를 활용할 수 없음
  • 이런 단점을 극복한 귀납식 임베딩 방법 중 대표적인 것이 그래프 신경망(Graph Neural Network)