Node Embedding

Contents

 

 

노드를 임베딩(Embedding)하는 이유는 노드의 정보를 vector로 표현할 수 있다면 Classification, Cluster 등 다양한 기법을 사용할 수 있는 것 뿐만 아니라 Node Classification, Community Detection 등에도 활용이 가능하다. 그렇다면 어떻게 노드를 벡터로 변환할 수 있을까? 이에 대한 내용은 Leskobec 교수님의 Node2Vec을 살펴보거나 DeepWalk를 보면 자세히 알 수 있으며 본 강의에서는 Random Walk, Node2Vec 이전에 제안된 노드 임베딩 기법의 개략적인 내용에 대해서만 다룬다. Random Walk,  Node2Vec 등의 모델은 여기를 참고하면 된다.

 

그래프에서의 노드 간의 유사도를 최대한 보존하면서 임베딩 공간으로 전달하는 것을 기준으로 노드 임베딩을 진행한다. 임베딩 공간에서 내적(Inner Product)을 사용해 유사도를 계산하고, 노드들이 같은 방향일수록 값이 크고, 반대 방향일수록 값이 작아지는 형태를 띈다. 

 

 

Adjacency Based Approach

노드를 임베딩하는 가장 간단한 방법은 바로 Adjacency 기반 접근법이다. 두 노드가 인접할 때 유사하다고 가정하는 것이다. 이때 인접하다는 것은 노드가 서로 연결되어 있다는 것을 의미하며, 인접행렬 $A_{u,v}$를 유사도로 가정하고 아래와 같은 손실 함수를 최적화하는 형태로 학습한다. 

\[ \mathcal{L} = \sum_{(u,v) \in V \times V} || Z^{\text{T}}_u z_v - A_{u,v}||^2 \]

이때 $z^{\text{T}}_u z_v$는 임베딩 공간에서의 유사도를 의미한다. 이때는 경사하강법 등의 기법을 사용할 수 있다. 그러나 Adjacency 만으로 유사도를 판단하는 경우 노드의 거리를 고려하지 않기 때문에 정확한 유사도를 계산하는 것이 어렵다.

 

 

Distance Based Approach

위 문제를 해결하기 위해 거리 기반, 경로 기반, 중첩 기반 등 다양한 접근법이 제안되었으며, 이 중 거리 기반 접근법 먼저 알아보자. 거리 기반 접근법은 두 노드 사이의 거리가 충분히 가까운 경우 유사하다고 간주한다. 예를 들어, 이때의 충분한 정도를 2로 설정한 경우 빨간색 노드는 초록색, 파란색 노드와는 유사하지만, 보라색 노드와는 유사하지 않다고 판단한다. 

Path Based Approach

경로 기반 접근법은 두 노드 사이의 경로가 많을수록 유사하다고 간주한다. 노드 $u$와 $v$ 사이의 경로는 순열을 의미하며, 두 사이의 경로 중 거리가 k인 것은 $A^k_{u,v}$로 표현한다. 이때의 손실함수는 아래와 같이 정의할 수 있다.

\[ \mathcal{L} = \sum_{(u,v) \in V \times V} || z^{\text{T}}_u z_v - A^k_{u,v} ||^2 \] 

 

Overlap Based Approach

중첩 기반 접근법은 두 노드가 서로 많은 이웃을 공유할 경우 유사하다고 간주한다. 아래의 그림처럼 빨간색 노드와 파란색 노드는 서로 두 명의 이웃 노드를 공유하기 때문에 유사도를 2로 판단한다.

이때 노드 $u$의 이웃 집합을 $N(u)$, 노드 $v$의 이웃 집합을 $N(v)$로 한다면 두 노드의 공통된 이웃 수 $S_{u,v,}$는 아래와 같이 정의할 수 있으며, 손실 함수도 아래와 같이 정의할 수 있다.

\[ S_{u,v} = |N(u) \cap N(v)| = \sum_{w \in N(u) \cap N(v)} 1 \]

\[ \mathcal{L} = \sum_{(u,v) \in V \times V} || z^{\text{T}}_u z_v - S_{u, v} ||^2 \]