[Stanford/CS224W] 3. node embeddings(3) : 전체 그래프 임베딩

스탠포드 강의를 듣고 정리한 내용입니다.

 

지난 포스팅에서는 랜덤 워크에 대해서 알아봤습니다. 

이번 포스팅에서는 전체 그래프 임베딩에 대해 알아보겠습니다. 

 

Embedding Entire Graphs

전체 그래프를 임베딩 하는 것은 무엇일까요? 

단순 노드 임베딩에서는 노드들을 임베딩 공간으로 맵핑시켰습니다. 

전체 그래프 임베딩은 하나의 노드를 임베딩 공간으로 맵핑시키는 것이 아니라 전체 그래프를 임베딩 공간으로 맵핑시키는 것을 뜻합니다. 

즉, 마치 하나의 파일을 압축하듯 노드들의 정보를 압축시켜 임베딩 공간으로 맵핑해줍니다. 

 

전체 그래프 임베딩은 분자가 독성이 있는지 탐지(분자 구조는 그래프 형태), 또는 이상 탐지 등에 사용될 수 있습니다. 

 

Approach1 : 노드 임베딩 값의 평균 또는 총합 이용

첫 번째 접근 방법은 매우 간단한 방법입니다. 

앞의 포스팅에서 배웠던 노드 임베딩 방식들 중 하나를 이용해서 각 노드들을 임베딩해주고, 그 임베딩된 노드 값들의 평균 또는 총합을 그래프 임베딩 값으로 사용하는 방법입니다. 

따라서 수식도 굉장히 간단합니다. 

 

이게 과연 제대로 임베딩이 될까?라는 생각이 들었는데, 실제로 구조물을 기반으로 분자를 분류하는데 사용한 결과 효과가 굉장히 좋았다고 하네요!

 

Approach2 : 하위 그래프(subgraph)를 대표하는 가상 노드(virtual node) 이용

그래프는 여러 개의 하위 노드로 구성될 수 있습니다. 따라서 이 하위 그래프를 표현할 수 있는 하나의 가상노드 S를 설정합니다.

위의 그림처럼 전체 그래프가 아닌 일부 하위 그래프를 하나의 가상 노드 S로 벡터 공간에 임베딩 해줍니다. 

이 방법도 일반적으로 많이 사용한다고 합니다. 

 

Approach3 : Anonymous Walk Embedding

anonymous walk embedding은 이름에서도 알 수 있지만, random walk에서 출발된 임베딩 방법입니다. 

기존 random walk는 방문한 노드가 어떤 노드인지 알 수 있었습니다. 하지만 anonymous walk에서는 말 그대로 익명입니다. 어떤 노드를 방문했는지 모르게 임베딩 됩니다. 

 

이게 무슨뜻이냐면!

위의 random walk 1을 예로 들어보겠습니다. 

random walk 에서는 위의 경로대로 방문을 한다면 A-B-C-B-C와 같이 임베딩 될 것입니다. 

따라서 random walk 2인 C-D-B-D-B와는 다른 값을 가지게 됩니다. 

 

하지만! anonymous walk는 "방문한 노드"가 아닌 "방문한 노드 순서"에 더 집중합니다. 

이게 무슨 소리냐! random walk 1을 봅시다. 여기서 A는 첫 번째로 방문했기 때문에 1이 됩니다. 그리고 B, C는 각각 두 번째, 세 번째 방문했기 때문에 2, 3이됩니다. 그런데 다시 B를 방문한다면 B는 이미 두 번째로 방문했던 노드기 때문에 다시 2가 되고, C는 세 번째로 방문했던 노드기 때문에 3이 됩니다. 

 

조금 정리해서 보자면 아래와 같습니다. 

결국 "방문한 시간의 시퀀스"를 중심으로 임베딩 하게 됩니다. 

 

그렇게 되면 random walk 2와 random walk 1의 임베딩 값이 같아지게됩니다. 

 

굉장히 간단하죠?

 

하지만 이 방법은 치명적인 단점이 존재합니다. 

anonymous walk 길이에 따라 가능한 임베딩 차원의 수가 기하급수적으로 들어나게 되는데요. 

예를 들어서 anonymous walk 길이를 3으로 설정할 경우 아래와 같이 서로 다른 5가지의 경우 수가 존재합니다.

• (1,1,1) : 시작 노드에 계속 머무르는 경우
• (1,1,2) : 시작 노드에 두번 머무르고 새로운 노드로 넘어갈 경우
• (1,2,1) : 새로운 노드로 넘어갔다가 다시 시작 노드로 돌아올 경우
• (1,2,2) : 새로운 노드로 넘어갔다가 그대로 있는 경우
• (1,2,3) : 새로운 노드로만 넘어간 경우 

 

anoymous walk sampling

이를 가장 간단하게 해결할 수 있는 방법은 샘플링을 하는 방법인데요. 바로 m개의 독립적인 랜덤워크 세트를 생성하는 방법입니다. 

m은 위와 같이 수식을 나타낼 수 있습니다. 위의 식에서는 error가 𝜀(오차의 하한)보다 크고 𝛿(오차의 상한)보다 작아야 합니다. 

 

new idea : learn walk embedding

여기서 새로운 아이디어가 하나 등장합니다. walk 가 발생할 때마다 나타내는 표현방식이 아닌 anonymous walk w_i로부터 z_i를 배우자는 것입니다.

 

그래서 어떻게 학습하자는 것일까요?

바로 다음 walk를 예측함으로써 임베딩을 학습한다고 합니다. 

 

 

위에 보시는 것 처럼 전체 그래프 Z_G를 의미하는 그래프 d를 입력으로 넣어주고, 동일한 노드에서 출발한 random walk를 이용하여 최종적으로 w_t를 예측합니다. 

 

목적함수는 아래와 같습니다. (Δ는 윈도우 사이즈, T는 walk의 총 수를 의미합니다.)

이제 전체 학습 과정을 간단하게 살펴볼까요?

1. 길이 l에 대해 u로부터 출발한 random walks를 T번 실행합니다. 

2. 아래와 같이 랜덤워클 예측하는 작업을 수행합니다. 

anonymous walk w_i로부터 임베딩 z_i를 추정합니다. 여기서 𝜂는 모든 가능한 임베딩 수 입니다. (즉 윈도우 사이즈라고 생각하시면 됩니다.)

P 함수는 이전과 동일하기 sofmax를 이용하고, 최종 벡터를 예측하기 전에 그래프 벡터와 함께 concatenate하여 사용합니다.

너무 수식으로만 봐서 이해가 잘 안가실 수도 있는데요. 그림으로 한번 확인해 보겠습니다. 

먼저 그래프 수치 + anonymous walk들을 concatenate하여 하나의 벡터로 만들어 준 뒤, 최종적으로 예측을 해줍니다. 

 

여기서 최종적으로 만들어지는 임베딩된 그래프 Z_G는 아래와 같이 두 가지 방법으로 사용될 수 있습니다.