그래프의 정점 벡터화

정점 표현 학습

---

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

✔️ 정점 표현 학습은 간단하게 정점 임베딩(Node Embedding)이라고도 부른다.

✔️ 정점 임베딩은 벡터 형태의 표현 그 자체를 의미하기도 하며 정점이 표현되는 벡터 공간을 임베딩 공간이라고 부른다.

출처: Naver BoostCamp AI Tech - edwith 강의

✔️ 정점 표현 학습의 입력은 그래프이고 주어진 그래프의 각 정점 $u$에 대한 임베딩(벡터 표현 $z_u$)이 정점 임베딩의 출력이다.

출처: Naver BoostCamp AI Tech - edwith 강의

⭐️ 임베딩의 결과가 벡터가 되기 때문에, 벡터 형태의 데이터를 위한 도구들을 그래프에 적용이 가능하다.
예시
➡️ 대부분의 분류기(로지스틱 회귀분석, 다층 퍼셉트론 등)
➡️ 군집 분석 알고리즘(K-Means, DNSCAN 등)
➡️ 이 외에도 최신의 기계 학습도구들을 정점 분류(Node Classification), 군집 분석(Community Detection)등에 활용할 수 있다.

✔️ 정점을 벡터로 변환할 때의 기준 아이디어
👉 그래프에서의 정점간 유사도를 임베딩 공간에서도 보존하는 것을 목표로 임베딩을 한다.

출처: Naver BoostCamp AI Tech - edwith 강의

✔️ 임베딩 공간에서의 유사도로는 내적을 이용한다.
👉 임베딩 공산에서 $u$와 $v$의 유사도는 둘의 임베딩의 내적$z_u^Tz_u = ||z_u|| \cdot ||z_v|| \cdot cos(\theta )$이다.(내적은 두 벡터가 클 수록, 같은 방향을 향할 수록 큰 값을 가지게 된다.)
➡️ $similarity(u,v) \approx z_u^T \cdot z_u$
❗️이때, $similarity$(유사도)는 두 벡터를 연산하여 어떠한 기준에 가깝게 할 것인가를 판단하기 위해 나타낸 식으로(임베딩 공간에서의 유사도) 기준은 인접성 기반 접근법, 저리 기반 접근 기반법 등(그래프에서의 유사도) 다양한 기준을 삼을 수 있다.

👉 이에 따라 정점 임베딩은 두 단계로 이루워 지게 된다.
1️⃣ 그래프에서의 정점 유사도를 정의하는 단계
2️⃣ 정의한 유사도를 보존하도록 정점 임베딩을 학습하는 단계

인접성 기반 접근법

---

✔️ 인접성 기반 접근법에서는 두 정점이 인접할 때 유사하다고 간주

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

✔️ 인접행렬(Adjacency Matrix)A의 $u$행 $v$열 원소 $A_{u,v}$는 $u$와 $v$가 인접한 경우 1 아닌 경우 0이다.
👉 인접행렬의 원소 $A_{u,v}$를 두 정점 $u$와 $v$의 유사도로 가정한다.

✔️ 인접성 기반 접근법의 손실 함수(Loss Function)
➡️ $L = \sum_{(u,v) \in V\times V}||z_u^Tz_v - A_{u,v}||^2$

✔️ 인접성 기반 접근법의 한계

출처: Naver BoostCamp AI Tech - edwith 강의

👉 빨간색 정점과 파란색 정점의 거리는 3
👉 초록색 정점과 파란색 정점의 거리는 2
❗️ 인접성만을 고려 할 시 두 경우 유사도는 0으로 같다.
⭐️ 거리에 대한 정보를 파악하는데 한계점이 있다.

👉 빨간색 정점과 파란색 정점은 다른 군집에 속해있다.
👉 초록색 정점과 파란색 정점은 다른 군집에 속해있다.(같은 군집에 속해야 하지만)
⭐️ 군집관계 표현에 한계가 있다.

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

---

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

출처: Naver BoostCamp AI Tech - edwith 강의

👉 예를 들어, 충분히 가까운 경우의 기준을 2라고 가정
👉 빨간색 정점과 초록색, 파란색 정점들와는 유사함으로 유사도가 1이다.
👉 빨간색 정점은 보라색 정점과 유사하지 않음으로 유사도가 0이다.

✔️ 경로 기반 접근법에서는 두 정점 사이의 경로가 많을 수록 유사하다고 간주
👉 두 정점 $u$와 $v$의 사이의 경로 중 거리가 $k$인 것의 수는 $A_{u,v}^k$와 같다.
(참고 링크 - https://m.blog.naver.com/PostView.nhn?blogId=gt7461&logNo=110151975370&proxyReferer=https:%2F%2Fwww.google.com%2F)

👉 위를 통해 손실함수의 접근법은 다음과 같다.
➡️ $L = \sum_{(u,v) \in V\times V}||z_u^Tz_v - A_{u,v}^k||^2$


❗️토의했던 점
$k$에 대하여 코드 접근 시 어떻게 접근을 하면 좋을까?
➡️ 사용자가 모델 구현 시 직접 지정을 하여 모델을 설계함으로써 $k$값에 따라 유사한 정도를 다르게 보는 것 같다. 이에 대하여 두가지 정도 어떻게 구현을 해 볼지 같은 팀원들과 토의를 해 보았는데 토의 결과는 다음과 같았다.
1️⃣ $k$값을 임의로 여러개를 지정하여 loss를 뽑아 낸 다음 평균 loss를 줄이는 방향으로 학습을 진행
2️⃣ model마다 $k$값을 다르게 주고 학습을 진행 후 loss가 가장 작은 모델을 선택한다.
➡️ 질문을 해 본 결과 임의의 수 k설정 후 그 이하의 값들을 고려하여 식을 진행
➡️ $L = \sum_{(u,v) \in V\times V}||z_u^Tz_v - \sum_{k=1}^KA_{u,v}^k||^2$
👉 최근에는 많이 사용하지 않는 embedding 방식

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

출처: Naver BoostCamp AI Tech - edwith 강의

👉 위의 예시에서는 빨간색 정점은 파란색 정점과 두 명의 이웃을 공유함으로 유사도는 2이다.

👉 정점 $u$의 이웃 집합을 $N(u)$ 그리고 정점 $v$의 이웃 집합을 $N(u)$라고 하면 두 정점의 공통 이웃 수$S_{u,v}$는 다음과 같다.
➡️ $S_{u,v} = |N(u) \bigcap N(v)| = \sum_{w \in N(u) \bigcap N(v)}1$

👉 손실함수의 접근법은 다음과 같다.
➡️$L = \sum_{(u,v) \in V\times V}||z_u^Tz_v - S_{u,v}||^2$

👉 공통 이웃 수를 자카드 유사도 혹은 Adamic Adar 점수를 사용할 수도 있다.
1️⃣ 자카드 유사도는 공통 이웃의 수 대신 비율을 계산하는 방식
➡️ $\frac{|N_u \bigcap N_v|}{|N_u \bigcup N_v|}\;$ 0~1사이의 값을 가지며 1의 값을 가질 때는 $N_u, N_v$가 동일할 때 이다.
2️⃣ Adamic Adar 점수는 공통 이웃 각각에 가중치를 부여하여 가중합을 계산하는 식이다.
➡️ $\sum_{w \in N_u \bigcap N_v}\frac{1}{d_w}\;$ 이때, $d_w$는 연결성을 나타내고 높으면 높을수록 가중치가 작다.(이미 많이 연결된 정점에 대해서는 가중치를 적게 둠 - 유명인과 일반인의 팔로워 예시를 생각해 보면 유명인을 공통 이웃으로 두는 경우는 가중치를 낮게 부여하고 일반인을 공통 이웃으로 두는 경우 가중치를 높게 둠)

임의보행 기반 접근법

---

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

출처: Naver BoostCamp AI Tech - edwith 강의

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

👉 정점 주변의 지역적 정보와 그래프 전역 정보를 모두 고려한다는 장점이 있다.

✔️ 임의보행 기반 접근법의 3 단계
1️⃣ 각 정점에서 시작하여 임의보행을 반복 수행
2️⃣ 각 정점에서 시작한 임의보행 중 도달한 정점들의 리스트 구성
정점 $u$에서 시작한 임의보행 중 도달한 정점들의 리스트를 $N_R(u)$라고 가정(이때, 한 정점을 여러번 도달한 경우, 해당 정점은 $N_R(u)$에 여러번 포함될 수 있다.)
3️⃣ 다음 손실함수를 최소화하는 임베딩을 학습
➡️ $L = \sum_{u \in V}\sum_{v \in N_R(u)}-log(P(v|z_u))\;$ (이때, $P(v|z_u)$는 $u$에서 시작한 임의보행이 $v$에 도달할 확률을 임베딩으로부터 추정한 결과를 의미 => 이 값이 클수록 손실함수 값이 작아진다.)
이때, 임베딩으로부터 추정한 도달 확률을 식으로써 풀어서 써 보게 되면 다음과 같다.
➡️ $L = \sum_{u \in V}\sum_{v \in N_R(u)} - log(\frac{exp(z_u^Tz_v)}{\sum_{n \in V}exp(z_u^Tz_n)})$

✔️ 임의보행의 방법의 따라 DeepWalk와 Node2Vec이 구분된다.
👉 DeepWalk는 위의 방법처럼 기본적인 임의보행을 사용한다.(현재 정점의 이웃 중 하나를 균일한 확률로 선택하고 이동하는 과정을 반복)

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

출처: Naver BoostCamp AI Tech - edwith 강의

위의 예시에서 현재 정점($v$)과 직전에 머물렀던 정점($u$)을 모두 고려하여 다음 정점을 선택(직전 정점의 거리를 기준으로 경우를 구분하여 차등적인 확률을 부여)

Node2Vec을 이용하여 K-Means 군집 분석을 수행한 결과

출처: Naver BoostCamp AI Tech - edwith 강의

➡️ 멀어지는 방향에 높은 확률을 부여한 경우, 정점의 역할(다리 역할, 변두리 정점 등)이 같은 경우 임베딩이 유사
➡️ 가까워지는 방향에 높은 확률을 부여한 경우, 같은 군집(community)에 속한 경우 임베딩이 유사

✔️ 임의보행 기법의 손실함수는 계산에 정점의 수의 제곱에 비례하는 시간이 소요
➡️ $L = \sum_{u \in V}\sum_{v \in N_R(u)} - log(\frac{exp(z_u^Tz_v)}{\sum_{n \in V}exp(z_u^Tz_n)})\;$($\sum_{u \in V}$부분의 중첩 합 때문이다.)
➡️ 이에 따라 근사식을 사용
모든 정점에 대하여 정규화를하는 대신 몇 개의 정점을 뽑아서 비교하는 형태
이 때, 뽑힌 정점들을 네거티브 샘플(연결성에 비례하여 뽑음 - 연결성이 높을수록 잘 뽑히도록)이라고 부른다.(이때, 샘플이 많을수록 정확도가 올라간다.)
$log(\frac{exp(z_u^Tz_v)}{\sum_{n \in V}exp(z_u^Tz_n)}) \approx log(\sigma(z_u^Tz_v)) - \sum_{i=1}^klog(\sigma(z_u^Tz_{n_i})), n_i \sim P_V$
(이때, $\sigma$는 sigmoid함수를 뜻하며 $\sum_{i=1}^klog(\sigma(z_u^Tz_{n_i})), n_i \sim P_V$이 식의 표현은 $k$개를 뽑고 그 뽑는 기준은 확률에 비례해서 뽑는다는 뜻이다.)
❗️ 추가적으로 이 식은 의미론적으로 위의 네거티브 샘플을 고려하지 않은 손실함수는 $V$에 있는 모든 노드들 중 $v$노드가 $u$노드와 가장 유사하도록 임베딩이 되는 것을 희망하는 것을 뜻하고 네거티브 샘플을 고려한 식은 $u$, $v$가 유사하게 임베딩 되었을 확률 - 노드 $u$와 negative sampled된 노드(u와 유사하지 않을 것이라 판단된 노드, random walk에서 $u$ 근처에 나타나지 않은 노드들)이 유사하게 임베딩되었을 확률로, 아래의 수식을 높게 학습시킨다는 것은 $u$와 $v$의 임베딩은 유사하도록, $u$와 negative sample된 다른 노드들의 임베딩은 유사하지 않도록 학습시킨다는 것을 뜻한다.

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

---

✔️ 위에서 설명한 임베딩 방법들은 변환식 방법이다.

✔️ 변환식 방법이란?
변환식 방법은 학습의 결과로 정점의 임베딩 자체를 얻는다는 특성이 있고 정점을 임베딩으로 변화시키는 함수, 즉 인코더를 얻는 귀납식(Inductive)방법과 대조된다.

✔️ 변환식 임베딩 방법의 한계점
1️⃣ 학습이 진행된 이후에 추가된 정점에 대하여는 임베딩을 얻을 수 없다.
2️⃣ 모든 정점에 대한 임베딩을 미리 게산하여 저장해두어야 한다.
3️⃣ 정점이 속성(Attribute)정보(부가정보)를 가진 경우 이를 활용할 수 없다.(한가지 속성을 기준으로 손실함수를 판단하여 사용)

Reference

Naver BoostCamp AI Tech - edwith 강의