[Stanford/CS224W] 3. node embeddings(2) : 노드 임베딩을 위한 랜덤 워크 접근 방식

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

 

지난 포스팅에서는 노드 임베딩이 어떤 과정을 거쳐 진행되는지 간단하게 알아봤습니다.

오늘은 노드 임베딩의 접근 방식 중 하나인 랜덤 워크(random walk)에 대해서 알아보겠습니다.

 

본격적인 설명에 앞서 몇가지 개념을 정의하고 가도록 하겠습니다. 

• z_u는 노드 u가 임베딩된 벡터입니다.
• P(v|z_u)는 u노드로 부터 시작한 랜덤 워크가 v를 지나갈 확률을 뜻합니다. 
• softmax
  • 모델이 예측한 K벡터를 합이 1인 확률로 변환해줍니다.

• sigmoid
  • S모양의 함수로 예측 값을 0~1사이의 값으로 변환시켜줍니다.

 

Random Walk

랜덤워크는 시작점 u에서 무작위로 다음 노드를 선택하여 그래프를 돌아다닐 때, 특정 노드 v를 들릴 확률을 유사도로 두고 학습하는 방법을 뜻합니다. 여기서 시작점 다음 노드는 당연히 시작점과 연결된 노드여야합니다. 

위와같이 하나의 그래프가 있다고 가정합시다. 위의 시작점은 노드 4입니다. 노드 4는 노드 1, 3, 5에 갈 수 있습니다. 여기서는 랜덤하게 5를 선택했습니다. 노드 5에서는 다시 이전에 있었던 노드 4와 노드 6, 7, 8으로 갈 수 있는데, 여기서는 8을 선택해서 갔습니다. 이런식으로 그래프 위를 정말 랜덤하게 돌아다닙니다. 

 

여기서 왔다갔다한 노드 경로 즉, 4-5-8-9-11 이 표현은 z₄라고 할 수 있습니다.(실제로는 다르게 임베딩 될 수 있습니다)

또한 만약 노드 8이 z₄에 속해있을 확률은 P(v|z₄)가 됩니다. 

 

이제 우리는 임베딩이 어떻게 진행되는지 간략하게 알게 되었습니다. 

그런데!! 랜덤 워크는 어떤 방식으로 최적화가 진행될까요?

 

한번 알아보겠습니다. 

노드를 최적화 하기 위해서는 간단하게 두 가지 과정으로 표현이 됩니다.

1. 랜덤 워크 노드 임베딩

위에 말씀드렸던 다음 노드를 선택하는 랜덤한 방법을 랜덤워크 전략 R이라고 하겠습니다. 시작노드 u로부터 랜덤워크 전략 R을 통해 v를 방문할 확률은 P_R(v|u)라고 정의합니다. 

 

2. 유사도를 통해 최적화

z_u, z_v 는 각각 u, v에서 부터 시작해서 랜덤 워크 전략 R에 의해 임베딩된 벡터들입니다. 이 두 벡터가 이루는 각 θ는 두 벡터가 얼마나 닮아있는지와 같죠.(코사인 유사도) 따라서 앞에서 정의한 u 노드에서 시작하여 v노드를 방문하는 확률과, 위의 두 벡터 사이의 각도와 비례하도록 최적화 시켜주시면 됩니다.

 

왜 랜덤워크를 사용할까요?

크게 두 가지 이유가 있는데요. 

• Expressivity(표현력) : 랜덤 워크는 local, higher-order 이웃 정보를 모두 포함 할 수 있기 때문에 표현력이 매우 좋습니다. 
  • u에서 v를 랜덤 워크로 방문할 확률이 높다면, u와 v가 닮아있다는 것을 뜻합니다. 즉, 그들 사이에 여러 경로가 있을 수 있습니다.  
• Efficiency(효율성) : 모든 노드 쌍을 고려하지 않고, 랜덤 워크가 발생한 노드만 고려하면 되기 때문에 효율성이 좋습니다.

 

Unsupervised Feature Learning

오잉? 갑자기 unsupervised feature learning이요? 하실 수 있는데, 현재까지 랜덤 워크의 과정을 보셨다면, 라벨이 존재하지 않는 unsupervised learning과 굉장히 닮아있다는 것을 알 수 있습니다. 

 

네! unsupervised learning이 맞습니다!

 

결론적으로 random walk의 학습 목표는 d차원 공간에서의 노드간의 유사도를 보존하는 임베딩을 찾는 것입니다. 

이를 위해서는 네트워크 내에 가까이 있는 노드를 고려하여 임베딩을 진행해야합니다. 

 

여기서 의문이 드는 점이 있죠. 

그렇다면 가까운 노드는 어떻게 정의해야할까요? 

 

그래프 G = (V, E)가 주어졌을 때, 우리는 아래와 같이 노드 u가 d차원의 어떠한 임베딩 벡터로 맵핑되는 것을 원합니다.

이는 위와 같이 f(u)라고도 표현 할 수 있습니다. 

 

여기서 목적 함수는 아래와 같습니다.

N_R(u)은 랜덤워크 전략 R 내에서 u 노드의 이웃 노드들 입니다. 

 

자 이제 구체적인 랜덤워크 노드 임베딩 학습 과정을 살펴볼까요?!

1. 길이를 고정시키고 그래프 내에 u로부터 랜덤워크 전략 R을 실행합니다. 

2. 각 노드 u에서 시작한 랜덤 워크 내에 방문된 노드의 멀티셋인 N_R(u)를 모두 수집합니다.

3. u가 주어지면, 그것의 이웃 노드인 N_R(u)를 예측하며 최적화를 진행합니다.

이를 그래프 내에 있는 모든 노드 V에 대하여 구하면 최종 Loss값을 알 수 있습니다.

위의 식을 천천히 살펴볼까요? 우리는 두 노드가 닮을 확률이 최대가 되도록 학습합니다. 즉, 최대가 되게 학습되면 앞에 -부호가 붙기 때문에 값은 작아지겠죠? 그럼 이 모든 값들을 더하면 값이 점점 작아질것입니다. 따라서 loss값은 작아집니다! 잘 학습하고 있다는 거겠죠!

반면 값이 작게 학습된다면 부호가 -이기 때문에 값은 점점 커질것입니다. 따라서 loss값이 점점 커지게됩니다!

 

여기서 P함수는 우리가 앞에서 잠깐 이야기하였던 softmax함수로 정의합니다. 

따라서 다음과 같은 수식을 얻을 수 있습니다. 

여기서 softmax를 사용하는 이유는, 노드 u와 가장 유사한 노드 v를 찾기 위해서입니다. 

그래서 결론적으로 위와 같은 식을 얻을 수 있습니다. 

 

그런데 자세히 보시면 뭔가 비슷한 식이 보입니다!!

softmax안에서도 전체 노드의 합을 구하고, 밖에서도 노드 합을 구하기 때문에 이는 시간 복잡도가 O(V²)이 됩니다. 

비용이 너무 커서 실제로 사용하기가 힘들겠죠?

 

Negative sampling

위의 한계점을 극복하기 위해 나온 개념입니다. 

바로 softmax함수를 조금 다르게 수정하는 방법입니다. 

 

※ negative sampling이 뭐죠?(참고)

보통 자연어 처리에서 나온 용어인데요. 

일반적으로 word2vec의 출력층에서 softmax함수를 이용하면 단어 집합 크기의 벡터와 실제값인 원-핫 벡터의 오차를 구하고, 이것으로 부터 임베딩 테이블에 있는 벡터 값을 업데이트시킵니다. 단어 집합 크기가 작다면 괜찮겠지만, 10만개, 20만개씩 엄청 커진다면 비용이 점점 커지겠죠. 

 

따라서 학습 과정에서 단어 전체 집합이 아니라 일부 단어 집합에만 집중할 수 있도록 하는 방법을 이용합니다. 

문장 내에 어느 한부분을 선택하고, 그 단어를 무작위로 대체시킵니다. 그리고 주변 단어와 맥락을 파악해서 그 단어가 대체된 단어인지, 아니면 기존 단어인지 체크를 하여 이진 분류 문제로 바꿔줍니다. 

 

즉, 전체 다를 고려하느냐 주변만을 고려하느냐에 차이입니다. 

이는 실제로 연산량에서 훨씬 효율적이라고합니다.

 

 

따라서 softmax수식을 sigmoid로 바꿔줍니다.

 

 

여기서 n_i ~ P_V는 노드의 랜덤 분포를 뜻합니다. 

즉, softmax함수처럼 그래프에 있는 모든 노드를 고려하는 것이 아니라, 그 노드들 중 특정 k개만을 랜덤하게 선택하고, 그 노드에 대해서만 위의 식을 구하겠다는 것입니다. 

 

따라서 시간 복잡도는 O(V*k)로 비용이 많이 줄어들었습니다. 

여기서 k는 클수록 더 robust하지만, negative events에 더 편향될 수 있기 때문에 5~20으로 설정하는 것이 적절하다고 합니다. 

 

Stochastic Gradient Descent

위의 함수를 최적화하기 위한 방법이죠. SGD가 뭔지 모르시는 분들은 이 포스팅을 참고해주세요.

 

간단하게 요약하자면, 전체 데이터에 대해서가 아니라 하나의 데이터에 대해 최적화를 진행합니다. 

즉, 노드 하나씩 최적화를 진행한다는 것이죠. 

 

과정을 정의하면 아래와 같습니다. 

1. 모든 i에 대한 zi를 초기화

2. 샘플링한 노드 i에 대한 모든 j에 대해 아래의 식을 계산

3. 모든 j에 대해 다음과 같이 업데이트

4. loss가 수렴할 때까지 반복

 

지금까지 랜덤 워크에 대해서 배워보았는데요. 랜덤 워크의 대표적인 예로는 DeepWalk가 있습니다. 

Deepwalk는 고정된 길이에 대해서만 편향되지 않게 랜덤 워크를 수행할 수 있는 방법을 제안했습니다. 

하지만 유사성에 대한 개념이 너무 제한적이라는 문제가 있습니다. 

같은 말로 하면 랜덤 워크는 임의로 만들기 때문에 그래프 이웃노드의 파악이 잘 되지 않을 수도 있습니다. 

 

Node2Vec

위의 한계점을 극복하고자 나온 모델입니다. 

Node2vec에서도 마찬가지로 목표는 유사도를 잘 보존할 수 있는 노드의 임베딩을 벡터 공간에 잘 표현하는 것이죠.

이 방법에서는 기존 방법보다 더 flexible한 벡터를 만들려고 했습니다.

flexible한 벡터를 만들기 위해서는 많은 정보를 담고있어야겠죠? 

따라서 아래 두 가지 방법을 고려하기 시작합니다. 

• BFS(너비 우선) : local한 정보를 담기 좋은 방법
• DFS(깊이 우선) : global한 정보를 담기 좋은 방법 

위의 두 정보를 담으면 정말 너무 좋을 것 같습니다만, 두 방법은 이웃 노드 정의하는 방법이 다릅니다.

 

왜 다른지 길이를 3으로 설정하고 한번 살펴보겠습니다.

너비 우선 탐색은 너비를 우선적으로 탐색하기 때문에, 길이를 3으로 주면 넓게(가장 근처로 연결된) 노드를 먼저 살펴봅니다. 따라서 이웃 노드는 S₁,S₂,S₃가 되겠죠. 

 

하지만 깊이 우선 탐색은 깊이를 우선적으로 탐색하기 때문에, 깊이를 3으로 주면 깊게 살펴봅니다. 따라서 이웃 노드는 S₄, S₅, S₆가 되겠죠. 

 

아래의 그림을 참고하시면 더 쉽게 이해하실 수 있습니다. 

 

따라서 local, global한 특징을 하나의 벡터로 임베딩하는 것은 매우 어렵습니다. Node2vec에서는 이 방법을 대체하여 p, q라는 두 가지 파라미터를 정의합니다. 

• p : 자신이 방문했던 노드로 돌아갈 확률이며, 높을수록 새로운 노드로 가는 경향이 있습니다. (=BFS)
• q : 새로운 노드로 갈 확률을 뜻합니다. q가 낮을수록 더 새로운 노드를 많이 탐색합니다. (=DFS)

이를 실제로 보면 위와 같습니다. 

상황은 S₁에서 W로 노드가 넘어온 상황입니다.

이 때, p가 낮을 수록 출처 노드로 갈 확률이 커집니다. 즉, 얕은 탐색을 할 확률이 높아지죠. 

반대로 p가 높아질수록 출처 노드로 갈 확률이 낮아지기 때문에, 더 깊은 탐색을 할 확률이 높아집니다. 

 

S₂는 기존 출처 노드와 동일한 길이의 노드이기 때문에 1로 표현이 됩니다. 

 

S₃, S₄는 출처 노드와 같은 거리에 있지도 않고, 출처 노드도 아닌 새로운 노드들입니다. 

여기서 q가 높을수록 새로운 노드로 갈 확률이 낮아집니다. 얕은 탐색을 할 확률이 높아지죠. 

반대로 q가 낮을 수록 새로운 노드로 갈 확률이 높아집니다. 따라서 깊은 탐색을 할 확률이 높아집니다. 

Node2vec는 아래의 과정으로 진행됩니다. 

1. random walk의 확률을 계산(p, q를 이용하여 각 노드로 갈 확률을 계산)

2. 시작 노드 u로 부터 길이가 l인 랜덤워크 시뮬레이션 진행

3. SGD를 이용한 최적화

 

또한 Node2vec는 다음과 같은 두 가지 특징을 가집니다. 

• 병렬 실행이 가능하다. (모든 노드에 대해 고정된 랜덤 워크가 있기 때문)
• 선형적인 시간 복잡도를 가진다.