[24] 정점 임베딩 (Node Embedding)

1️⃣ 정점 표현 학습

 

정점 표현 학습이란 그래프의 정점들을 벡터의 형태로 표현하는 것입니다.

 

정점 표현 학습은 간단히 정점 임베딩(Node Embedding)이라고도 부릅니다.

정점 임베딩은 벡터 형태의 표현 그 자체를 의미하기도 합니다.

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

 

http://snap.stanford.edu/proj/embeddings-www/

 

정점 표현 학습의 입력은 그래프입니다.

주어진 그래프의 각 정점 𝑢에 대한 임베딩, 즉 벡터 표현 $𝒛_{𝑢}$가 정점 임베딩의 출력입니다.

 

http://snap.stanford.edu/proj/embeddings-www/

 

정점 임베딩의 결과로, 벡터 형태의 데이터를 위한 도구들을 그래프에도 적용할 수 있습니다.

군집 분석 알고리즘(K-Means, DBSCAN 등), 정점 분류(Node Classification), 군집 분석(Community Detection) 등등..

 

그렇다면 어떤 기준으로 정점을 벡터로 변환해야 할까요?

 

그래프에서의 정점 간 유사도를 임베딩 공간에서도 “보존”하는 것을 목표로 합니다.

정점과 정점 간의 유사도를 보존하면서 임베딩 공간에 옮겨와야 합니다.

 

따라서 임베딩 공간에서의 유사도로는 내적(Inner Product)을 사용합니다.

임베딩 공간에서의 𝑢와 𝑣의 유사도는 둘의 임베딩의 내적 $Z^{T}_{v}Z_{u} = ||Z_u||\cdot ||Z_v|| \cdot cos(\theta)$ 입니다. 내적은 두 벡터가 클수록, 그리고 같은 방향을 향할수록 큰 값을 갖습니다.

 

http://snap.stanford.edu/proj/embeddings-www/

 

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

 

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

 

 

2️⃣ 인접성 기반 접근법과 Loss

 

인접성(Adjacency) 기반 접근법에서는 두 정점이 인접할 때 유사하다고 간주합니다.

두 정점 𝑢와 𝑣가 인접하다는 것은 둘을 직접 연결하는 간선 (𝑢, 𝑣)가 있음을 의미합니다.

 

인접 행렬(Adjacency Matrix) 𝐀의 𝑢행 𝑣열 원소 $𝐀_{𝑢,𝑣}$는 𝑢와 𝑣가 인접한 경우 1 아닌 경우 0입니다.

 

https://www.edwith.org/bcaitech1

 

인접성 기반 접근법의 손실 함수(Loss Function)는 아래와 같습니다.

 

즉, 이 손실 함수가 최소가 되는 정점 임베딩을 찾는 것을 목표로 합니다.

손실 함수 최소화를 위해서는 (확률적) 경사하강법 등이 사용됩니다.

 

https://www.edwith.org/bcaitech1

 

그렇지만 인접성만으로 유사도를 판단하는 것은 한계가 있습니다.

 

빨간색 정점과 파란색 정점은 거리가 3인 반면

초록색 정점과 파란색 정점은 거리가 2입니다.

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

 

http://snap.stanford.edu/proj/embeddings-www/

 

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

1) 거리 기반 접근법

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

 

http://snap.stanford.edu/proj/embeddings-www/

 

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

빨간색 정점은 초록색 그리고 파란색 정점들과 유사합니다. 즉, 유사도가 1입니다.

반면, 빨간색 정점은 보라색 정점과는 유사하지 않습니다. 즉 유사도가 0입니다

 

 

2) 경로 기반 접근법

 

경로 기반 접근법에서는 두 정점 사이의 경로가 많을수록 유사하다고 간주합니다.

 

여기서 경로(Path)는 다음과 같은 조건을 가진 정점들의 순열(Sequence)입니다.

 

(1) 𝑢에서 시작해서 𝑣에서 끝나야 합니다.

(2) 순열에서 연속된 정점은 간선으로 연결되어 있어야 합니다.

 

https://www.edwith.org/bcaitech1

 

경로 기반 접근법에서 손실함수 Loss는 다음과 같습니다.

 

• $A^{k}_{u,v}$ : 두 정점 𝑢와 𝑣의 사이의 경로 중 거리가 𝑘인 것

 

https://www.edwith.org/bcaitech1

 

마지막에 제곱이 붙었기 때문에 만약 식 안의 값이 커지게 되면, Loss 값도 많이 커지게 됩니다.

 

 

3) 중첩 기반 접근법

중첩 기반 접근법에서는 두 정점이 많은 이웃을 공유할수록 유사하다고 간주합니다.

 

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

 

http://snap.stanford.edu/proj/embeddings-www/

 

중첩 기반 접근법에서 손실함수 Loss는 다음과 같습니다.

 

• $N(u)$ : 정점 𝑢의 이웃 집합
• $N(v)$ : 정점 𝑣의 이웃 집합
• $S_{u,v}$ : 두 정점의 공통 이웃 수

https://www.edwith.org/bcaitech1

 

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

 

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

 

• $N(u) \cap N(v)$ : $u$와 $v$의 공통 이웃
• $N(u) \cup N(v)$ : $u$ 혹은 $v$와 인접한 정점들의 수

자카드 유사도는 항상 0부터 1 사이의 값이 나옵니다.

자카드 유사도가 1을 갖는 경우는 $N(u) = N(v)$가 완벽하게 같은 경우입니다.

즉, 두 정점의 이웃들의 집합이 완벽하게 동일할 때 자카드 유사도는 1을 가집니다.

 

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

 

• $w$ : $u$와 $v$이 공통 이웃
• $d_w$ : $w$의 연결성

즉, $w$의 연결성 $d_w$가 크면 클수록 가중치는 낮아지게 됩니다.

이 뜻은 연결성이 매우 큰 (1000만 인플루언서 같은) 이웃을 가지고 있는 것은 자신이 팔로우(이웃) 해봤자 의미가 없으므로 가중치가 크지 않습니다.

 

 

4️⃣ 임의보행 기반 접근법

 

임의보행 기반 접근법에서는 한 정점에서 시작하여 임의보행을 할 때 다른 정점에 도달할 확률을 유사도로 간주합니다.

 

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

 

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

(그래프 전역 정보를 고려한다는 의미 : 임의보행 기반 접근법은 거리(k)를 제한하지 않기 때문에 그래프의 전체 정보를 고려할 수 있음)

 

http://snap.stanford.edu/proj/embeddings-www/

 

임의보행 기반 접근법은 세 단계를 거칩니다.

 

1. 각 정점에서 시작하여 임의보행을 반복 수행합니다.
2. 각 정점에서 시작한 임의보행 중 도달한 정점들의 리스트를 구성합니다.
   
   이때, 정점 𝑢에서 시작한 임의보행 중 도달한 정점들의 리스트를 $𝑁_{𝑅}(𝑢)$라고 합시다.
   
   한 정점을 여러 번 도달한 경우, 해당 정점은 $𝑁_{𝑅}(𝑢)$에 여러 번 포함될 수 있습니다.
3. 다음 손실함수를 최소화하는 임베딩을 학습합니다.

https://www.edwith.org/bcaitech1

 

위 식에서 $P(v|z_{u})$는 𝑢에서 시작한 임의보행이 𝑣에 도달할 확률을 의미합니다.

즉, 출력에 해당하는 embedding으로부터 추정한 $u$에서부터 $v$에 도달할 확률값을 의미합니다.

이 확률값이 크면 클수록 추정을 잘된 것을 의미합니다.

이후, $-log$를 씌어서 확률 $P(v|z_{u})$가 1에 가까워질수록 $-log(P(v|z_{u})$값이 감소하게 만들어 궁극적으로 Loss값을 최소화하게 됩니다. (확률은 0~1 사이의 값, 아래 그림과 같이 $-log$값은 1에 도달할수록 값이 감소)

 

 

http://www.sosmath.com/algebra/logs/log4/log42/log422/log422.html

 

즉, 최소화해야 하는 손실함수 $L$은 $-log$들의 합으로 정의되게 됩니다.

 

$P(v|z_{u})$는 다음과 같이 계산합니다.

분자는 $z_u$, $z_v$의 내적값의 exp를 해주고,

분모는 모든 정점의 내적값에 exp한, 즉, 정규화를 나타냅니다.

즉 유사도 $𝒛_{𝒗}^{\top} 𝒛_{𝒖}$가 높을수록 $P(v|z_{u})$ 확률이 높습니다.

 

 

추정한 $P(v|z_{u})$ 확률을 사용하여 손실함수를 완성하고 이를 최소화하는 임베딩을 학습합니다.

(여기서 $N_{R}(u)$는 임의보행 중 "실제로" 마주친 모든 정점)

 

https://www.edwith.org/bcaitech1

 

5️⃣ DeepWalk와 Node2Vec

 

임의보행의 방법에 따라 DeepWalk와 Node2Vec이 구분됩니다.

1) DeepWalk

DeepWalk는 앞서 설명한 기본적인 임의보행을 사용합니다.

즉, 현재 정점의 이웃 중 하나를 균일한 확률로 선택하는 이동하는 과정을 반복합니다.

 

2) Node2Vec

Node2Vec은 2차 치우친 임의보행(Second-order Biased Random Walk)을 사용합니다.

2차 치우친 임의보행은 ($u$에서 $v$로 이동했을 때) 현재 정점(𝑣)과 직전에 머물렀던 정점(𝑢)을 모두 고려하여 다음 정점을 선택합니다.

 

직전 정점의 거리를 기준으로 경우를 구분하여 차등적인 확률을 부여합니다.

 

• (a) 가까워지는 방향은 다시 $u$로 가는 것 (거리 1)
• (b) 거리가 유지되는 방향은 $u$ -> $x$의 거리가 1 / $u$ -> $v$의 거리가 1이기 때문
• (c) 멀어지는 방향은 $u$ -> $y$의 거리가 2 / $u$ -> $v$의 거리가 1이기 때문

http://snap.stanford.edu/proj/embeddings-www/

 

Node2Vec에서는 부여하는 확률에 따라서 다른 종류의 임베딩을 얻습니다.

아래 그림은 Node2Vec으로 임베딩을 수행한 뒤, K-means 군집 분석을 수행한 결과입니다.

 

• 멀어지는 방향에 높은 확률을 부여한 경우

파란색 node : 다리 역할

노란색 node : 변두리 정점

빨간색 node : 군집에 속해있는 정점

 

멀어지는 방향에 높은 확률을 부여한 경우 비슷한 역할을 하는 node들이 embedding 공간에서 유사한 vector를 갖게 된 것을 알 수 있습니다.

 

http://snap.stanford.edu/proj/embeddings-www/

 

• 가까워지는 방향에 높은 확률을 부여한 경우

같은 색깔을 가진 정점들은 같은 군집(Commnuity)에 속한 것을 알 수 있습니다.

멀어지는 방향에 높은 확률을 부여한 경우 같은 군집(Commnuity)에 속한 node들이 embedding 공간에서 유사한 vector를 갖게 된 것을 알 수 있습니다.

 

http://snap.stanford.edu/proj/embeddings-www/

 

 

6️⃣ 손실 함수 근사

 

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

 

따라서 많은 경우 근사식을 사용합니다.

모든 정점에 대해서 정규화하는 대신 몇 개의 정점을 뽑아서 비교하는 형태입니다.

즉, 모든 정점 V를 정규화하는 대신 몇 개의 정점을 뽑아서 비교합니다. (V는 분모에만 들어가 있음)

이때 뽑힌 정점들을 네거티브 샘플이라고 부릅니다. (k개의 정점)

 

https://www.edwith.org/bcaitech1

 

연결성에 비례하는 확률로 네거티브 샘플을 뽑으며, 네거티브 샘플이 많을수록 학습이 더욱 안정적입니다.

즉, 연결성이 높을수록 네거티브 샘플로 뽑힐 확률이 많습니다.

 

 

7️⃣ 변환식(Transductive) 방법과 귀납식(Inductive) 방법

 

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

귀납식(Inductive) 방법은 정점을 임베딩으로 변화시키는 함수, 즉 인코더를 얻습니다.($ENC$)

 

 

변환식 임베딩 방법은 여러 한계를 갖습니다.

 

1) 학습이 진행된 이후에 추가된 정점에 대해서는 임베딩을 얻을 수 없습니다.

2) 모든 정점에 대한 임베딩을 미리 계산하여 저장해두어야 합니다.

3) 정점이 속성(Attribute) 정보를 가진 경우에 이를 활용할 수 없습니다.