[머신러닝 공부] Graph Representation learning 1

 

Graph 에서의 Representation learning

 

representation learning : 표현학습 으로 쉽게 말하면 딥러닝 그 자체이다. 복잡한 데이터의 구조를 layer화 한다.

 

Graph 에서의 representation learning 은 우리가 알고있는 딥러닝 layer 와 다르게 동작할까?

 

''같은 의미로 동작한다''

 

graph의 node를 function을 통해 Latent space(embedding space)로 embedding 할 수 있다.

 

graph의 embedding을 통해 다양한 임무를 효과적으로 수행할 수 있다.

 

 

그래프를 왜 Embedding 할까?

 

graph는 node로 이루어져있고 각 노드는 인접한 node가 있다.

 

그 정보들로 인접행렬 (Adjacency Matrix)를 구성할 수 있다.

 

위는 인턴때 정리한 자료 중 하나이다. 연결된 node로 Adjacency Matrix를 보인 것을 알 수 있다.

 

graph의 인접행렬은 각 column이 node를 의미하기 때문에 크기가 매우 크다.

 

인접행렬을 그대로 다루기에는 연산쪽에서의 문제가 있을 것이다.

 

따라서 graph의 각 node를 low-dimension으로 mapping 할 필요가 있다.

 

Adjacency Matrix 의 dimension -> (embedding) -> Latent dimension  = computation 효과

DeepWalk 이외에도 다른 embedding 방법이 존재한다. 뒤에 계속..

 

node별로 representation이 가능하게 된다.

 

대신, Adjacency matrix의 각 column은 node를 나타내지만 latent demension에서 나타낼 수 있는 embedding matrix의 column은 각 node를 나타내지는 않는다.

 

latent demension의 column들은 node가 아닌 node간의 상관관계와 같은 graph 정보를 의미하는 feature가 된다.

 

Adjacency matrix의 그래프 정보를 latent dimension으로 encoding하고, node representation을 만들어 내는 것

 

그래프 정보를 담았으니 latent 에서 나타내지는 node간의 similarity는 실제 graph에서의 node간의 similarity라고 볼 수 있다.

 

 

 

 

---

 

 

 

Embedding Nodes

graph의 node들을 어떻게 embedding 할까?

우선, embedding의 목적은

 

위 그림의 embedding 공간 상의 similarity와 원본 graph의 similarity를 최대한 동일하게 만드는 것이다.

 

embedding 공간상의 두 벡터의 similarity는 dot product (Zv^T​)*(Zu)​로 측정할 수 있다.

 

embedding을 시키는 것은 encoder의 역할이다. (같은 의미이기도 하지만)

---

Encoder

shallow encoding, Deep Walk, node2vec, TransE 등의 encoder 로 Embedding 할 수 있다.

---

Similarity Function

두 벡터의 similarity를 어떤 기준으로 정의할까?

 

- 두 노드의 연결관계

- 공유하는 neighbor node

- structural role의 유사성

 

등이 있을 것이다.

---

Optimization

www.researchgate.net/publication/336602725_Deep_Reinforcement_Learning_meets_Graph_Neural_Networks_An_optical_network_routing_use_case

위의 논문을 참고

 

 

 

---

 

 

 

Node embedding 방법

Random Walk Approaches to Node Embeddings

Random Walk 를 직역하면 node위를 랜덤하게 걸어다니는 것을 뜻한다.

 

그래프의 특정한 점에서 랜덤하게 주변 노드들을 선택해 나가는데 그 point들의 시퀀스들을 ramdom walk라고 한다.

 

이를 sampling 한다고 표현한다.

 

왜 Random Walk 를 사용할까?

Expressivity(표현력) : local과 higher-order neighborhood정보를 함께 고려하는 node similarity에 유연한 확률적 정의를 내릴 수 있다.

 

Efficiency(효율성) : 모든 node쌍으로 학습할 필요 없이 random walk와 함께 발견될 쌍들만을 고려

 

 

Ramdom walk Embedding (Deep walk로 encoding)

Zu^T * Zv = network 전체 random wolk 에서 u 와 v 가 co-occur(함께 발생) 할 확률

 

Zu와 Zv 의 Similarity가 높다는 것은 latent space 상에 가깝게 위치할 것

=> node u와 v의 similarity가 높다는 의미

=> random walk에서 동시에 발견될 확률이 높다

 

과정

1. Random walk strategy R을 사용하여 u에서 출발해 v에 방문할 확률을 추정한다.

2. 이 확률을 encoding 하기 위해 embedding을 최적화 시킨다.

 

 

 

다음엔 Random Walk Optimization 에 대해 포스팅 할 예정이다.

 

 

---

 

 

Reference

아래는 공부하고 포스팅을 하는데 참고한 유튜브 채널과 블로그이다

 

www.youtube.com/watch?v=zCEYiCxrL_0

www.youtube.com/watch?v=4PTOhI8IWTo&t=293s

velog.io/@minjung-s/GNN-Graph-Representation-Learning-Deep-Walk-node2vec