4. 노드 임베딩 CS224W: Machine Learning with Graphs 정리

https://web.stanford.edu/class/cs224w

목차

- 노드임베딩

• 전통적인 머신러닝
• 표현학습

- 노드 임베딩 인코더와 디코더

- 노드의 유사성을 측정하는 방법 : Random Walks

 

👉 Node embedding

 

• 노드 임베딩은 각 노드를 저차원 벡터로 표현하는 것
• 노드 임베딩은 노드 분류, 링크 예측, 그래프 분류 등 다양한 태스크에 활용 가능

1. 기존 전통적인 방식의 노드임베딩

기존 전통적인 방식에서는 다른 머신러닝과 마찬가지로 Feaure engineering에 신경을 많이 썼다.

 

2. 그래프의 표현학습

 

 

표현 학습의 목표 : 그래프 머신러닝에서 효율적인 특성을 학습하는 것!

 

 

 

👉 Node embedding : Encoder And Decoder

Encoder : 원본 그래프에 있는 노드를 임베딩 공간 Z로 맵핑하는 것!

단순히 Z공간으로 맵핑시키는게 중요한것이 아닌 실제 그래프에 있는 U와 V의 유사도와 Z공간으로 맵핑된 U, V 노드의 유사도가 최대한 비슷하게 하는것이 목표이다.

순서 

1. 인코더 : 노드를 임베딩 공간으로 맵핑

- 실제 그래프의 유사도를 측정할 함수 정의

2. 디코더 : 임베딩 벡터의 노드의 유사도 점수를 맵핑(유사도 점수는 내적을 사용)

3. 실제 네트워크에서의 유사도와 임베딩 공간에서의 유사도를 최대한 비슷하게 하도록 파라메터를 최적화

 

위 순서를 보면 인코더는 단순히 네트워크안에 있는 노드를 Z공간으로 맵핑을 하는 것이고 핵심부분은 실제 네트워크에 있는 노드의 유사도를 측정하는 similarity(u,v)라는걸 알 수 있다. (디코더는 Z공간에서의 내적으로 유사도를 계산) 그렇다면 실제 네트워크에 있는 노드의 유사도를 어떻게 계산할까?

- 엣지로 연결되어 있는가?

- 이웃을 공유하고 있는가?

- 네트워크 구조가 비슷한가?

이를 Random Walks를 사용해 유사도를 측정하는 방법을 알아보자!!

 

👉 Random Walks

랜덤 워크는 노드임베딩을 하는 비지도 / 셀프 지도 학습 방법이다.

- 노드의 특징을 활용하지 않는다.

- 노드의 라벨을 활용하지 않는다.

기본적인 아이디어는 다음과 같다. 노드 u에서 시작하는 랜덤 워크가 노드 v를 높은 확률로 방문하면 u와 v가 유사하다고 간주

 

 

랜덤 워크 시뮬레이션:
1. 사용자 A에서 시작하는 랜덤 워크를 수행합니다.
- 이 랜덤 워크가 사용자 B를 자주 방문한다면, 사용자 A와 B는 유사하다고 볼 수 있다.
- 반면 사용자 C는 A에서 시작한 랜덤 워크에서 거의 방문되지 않았다면, A와 C는 유사도가 낮다고 판단할 수 있다.

 

2. 방문 확률 모델링:
사용자 u의 임베딩을 𝐳u라 하고, 사용자 v를 방문할 확률을 P(v|𝐳u)로 모델링한다.
소프트맥스 함수를 사용해 이 확률 값을 계산한다.
예를 들어, P(B|𝐳A) = 0.7, P(C|𝐳A) = 0.01 이라면, 사용자 A와 B가 더 유사하다는 것을 의미한다.

 

3. 노드 임베딩 최적화:
위에서 정의한 유사도를 바탕으로, 노드 임베딩을 학습한다.
목적 함수는 각 노드 u에 대해, u에서 시작한 랜덤 워크의 이웃 노드들을 잘 예측하는 것이다.
사용자 A의 경우, 목적 함수는 log P(B|𝐳A)와 log P(C|𝐳A) 등의 항을 최대화하는 방향으로 임베딩 𝐳A를 업데이트하게 된다.

이렇게 학습된 노드 임베딩은 원본 그래프의 이웃 구조를 반영하게 되고, 이를 다운스트림 태스크에 활용할 수 있다. 예를 들면 유저 임베딩 간 유사도를 기반으로 친구 추천을 하거나, 노드 임베딩을 입력으로 받아 노드 분류를 수행할 수 있다.

랜덤 워크 기반 노드 임베딩의 장점은 로컬과 글로벌 정보를 모두 고려하며, 모든 노드 쌍이 아닌 랜덤 워크에서 co-occur한 노드 쌍만 사용하기에 효율적이라는 점이다.

📝 정리

1. 그래프의 각 노드에서 시작하여 짧은 고정 길이의 무작위 보행을 실행

2. 각 노드 u에 대해 랜덤워크 샘플링을 시작하여 u의 랜덤한 이웃들에 대한 집합 NR(u)을 생성

3. 확률적 경사하강법을 이용하여 임베딩을 최적화

 

랜덤워크를 하는 방법

- node2vec

- deepwork

1. DeepWalk:
DeepWalk는 그래프 임베딩을 위한 대표적인 알고리즘 중 하나이다. 이 알고리즘은 그래프에서 랜덤 워크(Random Walk)를 수행하여 노드 시퀀스를 생성하고, 이를 자연어 처리에서 사용되는 Skip-gram 모델을 이용하여 노드의 임베딩 벡터를 학습다.

예시:
- 소셜 네트워크 그래프에서 DeepWalk를 적용하면, 사용자(노드)의 임베딩 벡터를 얻을 수 있다. 이 벡터는 사용자 간의 연결 관계와 유사도를 반영하므로, 이를 활용하여 추천 시스템이나 링크 예측 등의 작업을 수행할 수 있다.

2. node2vec:
node2vec은 DeepWalk를 확장한 알고리즘이다. DeepWalk에서는 랜덤 워크가 완전히 무작위로 이루어지는 반면, node2vec에서는 두 개의 파라미터(p와 q)를 도입하여 랜덤 워크의 전략을 조절한다. 이를 통해 그래프의 구조적 정보를 더 잘 반영할 수 있다.

- p (Return Parameter): 이전에 방문한 노드로 돌아갈 확률을 조절한다. p값이 높을수록 이전에 방문한 노드로 돌아갈 가능성이 낮아진다.
- q (In-out Parameter): 현재 노드와의 거리에 따라 다음 노드를 선택할 확률을 조절한다. q값이 높을수록 현재 노드와 가까운 노드를 선택할 가능성이 높아진다.

예시:
- 학술 논문 인용 네트워크에 node2vec을 적용하면, 논문(노드)의 임베딩 벡터를 얻을 수 있다. 이 벡터는 논문 간의 인용 관계와 주제적 유사도를 반영하므로, 이를 활용하여 논문 분류, 논문 추천, 인용 관계 예측 등의 작업을 수행할 수 있다.

 

다음은 그래프 머신러닝 딥 그래프를 이용해서 임베딩 벡터를 학습하는 방법에 대해서 알아보겠다!

2024.03.26 - [GNN/CS224] - 5. Graph Neural Networks CS224W: Machine Learning with Graphs 정리

5. Graph Neural Networks CS224W: Machine Learning with Graphs 정리