[Week 5-4] 🔗정점 표현 학습

5주차 목요일

• 정점 표현 학습 - 변환식 임베딩

---

📝[정점 표현 학습 - 변환식 임베딩]

정점 표현 학습 : 그래프의 정점들을 벡터 형태로 표현하는 것으로, 정점 임베딩, 노드 임베딩이라고 부르기도 한다.
기계학습에 사용되는 분류기(로지스틱 회귀, MLP)나 군집 분석 알고리즘 등은 벡터 형태로 표현된 데이터를 입력으로 사용한다. 따라서 그래프의 정점들을 벡터 형식으로 표현하기 위해 정점 임베딩을 사용한다. 그래프를 입력받아 각 정점 u에 대한 임베딩(벡터 표현) z_u를 출력하는데, 이 때 정점이 표현되는 벡터 공간을 임베딩 공간이라고 부른다.

정점을 벡터로 변환할 때는 그래프에서의 정점 간 유사도를 임베딩 공간 내에서도 보존할 수 있도록 해야 한다. 임베딩 공간 내에서의 유사도를 측정할 때는 내적을 사용한다. 내적은 두 벡터가 클수록, 같은 방향을 향할수록 큰 값을 갖기 때문에 두 벡터의 내적이 크다면 유사도 역시 크다고 볼 수 있다. 정점 임베딩은 1) 그래프에서의 정점 유사도를 정의하는 단계 2) 정의한 유사도를 보존하도록 정점 임베딩을 학습하는 단계 순으로 이루어진다.

• 인접성 기반 접근법
  두 정점이 인접해 있을 때 유사하다고 간주하는 방법이다. 두 정점 u와 v가 인접했다면 둘을 직접 연결하는 간선이 있다. 인접행렬 A에서 u행 v열의 원소는 두 정점 u,v가 인접했다면 1, 인접하지 않았다면 0이기 때문에 인접행렬의 원소 A_u,v를 두 정점의 유사도로 가정할 수 있다. 하지만 거리가 2인 정점과 거리가 6인 정점 모두 유사도가 0이 되어 인접성만으로 유사도를 판단하기에는 한계가 있다.

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

  • 거리 기반 접근법
    두 정점 사이의 거리가 충분히 가까운 경우 유사하다고 간주하는 방법이다. 충분히의 기준을 2로 잡았을 경우 거리가 2 이하인 정점들을 유사하다고 간주한다.

  • 경로 기반 접근법
    두 정점 사이의 경로가 많을수록 유사하다고 간주하는 방법이다. 두 정점 u,v 사이의 경로 중 거리가 k인 것의 수는 인접행렬 A의 k제곱의 u행 v열의 원소와 같다.

  • 중첩 기반 접근법
    두 정점이 많은 이웃을 공유할수록 유사하다고 간주하는 방법이다. 공통 이웃의 수 외에도 공통 이웃의 비율을 계산하는 자카드 유사도, 공통 이웃 각각에 가중치를 부여하여 가중합을 계산하는 Adamic Adar 점수를 통해 유사도를 측정하는 방법도 있다.

• 임의 보행 기반 접근법
  한 정점에서 시작하여 임의 보행을 할 때 다른 정점에 도달할 확률을 유사도로 간주하는 방법이다. (임의 보행 : 현재 정점의 이웃 중 하나를 균일한 확률로 선택해 이동하는 과정)
  임의 보행을 사용할 경우 시작 정점 주변의 지역적 정보와 그래프 전역 정보를 모두 고려할 수 있다는 장점이 있다. 임의 보행 기반 접근법은 다음과 같은 단계를 거쳐 수행된다.

1. 각 정점에서 시작하여 임의 보행을 반복 수행한다.
2. 출발한 각 정점별로 임의 보행 중 도달한 정점들의 리스트를 구성한다. 정점 u에서 출발해 임의 보행 중 도달한 정점들의 리스트를 N_R(u)라고 한다. 이 때 한 정점에 여러 번 도달한 경우 해당 정점은 N_R(u)에 여러 번 포함될 수 있다.
3. 손실함수를 최소화하는 방향으로 임베딩을 학습한다.

임의 보행 기반 접근법에는 DeepWalk와 Node2Vec이 있는데, 두 기법은 임의 보행을 하는 방법이 좀 다르다.

• DeepWalk
  기본적인 임의 보행 방식을 사용한다. 현재 정점의 이웃 중 하나를 균일한 확률로 선택하여 이동한다.
• Node2Vec
  2차 치우친 임의 보행 방식을 사용한다. 현재 정점과 직전에 머물렀던 정점을 모두 고려하여 다음 정점을 선택하는데, 직전 정점의 거리를 기준으로 방문할 다음 정점이 1. 이전 정점과 가까워지는 방향 2. 이전 정점과의 거리가 유지되는 방향 3. 이전 정점과 멀어지는 방향 3가지로 구분해 각 경우별로 차등적인 확률을 부여한다. 차등적인 확률은 사용자가 결정할 수 있으며, 부여하는 확률에 따라 다른 종류의 임베딩을 얻게 된다.
  멀어지는 방향에 높은 확률을 부여하는 경우 다리, 변두리 등 정점의 역할이 같은 경우에 임베딩이 유사해진다. 반면, 가까워지는 방향에 높은 확률을 부여할 때는 같은 군집에 속하는 경우에 임베딩이 유사해진다.

위의 방법들은 변환식 임베딩 방법으로, 학습을 통해 정점의 임베딩 자체를 얻을 수 있다. 이와 반대되는 방식으로는 귀납식 임베딩 방법이 있는데, 귀납식 임베딩은 정점을 임베딩으로 변환시키는 함수(인코더)를 얻는 방법이다. 변환식 임베딩 방법은 학습 이후 추가된 정점의 임베딩을 얻을 수 없고 모든 정점에 대한 임베딩을 미리 계산해 저장해 둬야 하며 정점의 속성 정보를 활용할 수 없다는 단점이 있다.