[Graph Neural Networks] Node Embedding

 

2025.06.08 - [Data & Research] - [Graph Neural Networks] Table of Contents

---

오랜만에 Graph Neural Networks의 포스팅을 이어가보려 합니다. 우리가 다루어야할 것은 추상적인 개념의 Graph인데 딥러닝 등의 정량적인 방식으로 다루기위해서는 어떻게든 수치화하는 것이 필요할 것입니다. 그런 관점에서 Graph의 node를 수치화(embedding)하겠다는 것이 node embedding입니다. node를 embedding한 결과물은 latent vector가 됩니다. 수치화하는 것도 중요하지만 그 과정에서 원래 graph에서 가까운 node들은 embedding 후에도 여전히 높은 유사도를 갖도록 해야 적절한 embedding이라고 할 수 있을 겁니다. 

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

 

1. Shallow Encoding

가장 간단한 방법입니다. 일종의 lookup table을 통해 embedding한다고 보시면 될 것 같습니다. 

\[\text{ENC}(v) = z_v = Z \cdot v\]

embedding vector의 차원이 \(d\)라고 하면, \(v \in \mathbf{I}^{|V|}\),  \(Z \in \mathbf{R}^{d \times |V|}\) 입니다. 여기서 \(v\)는 indicator vector입니다. 

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

 

2. Deepwalk (Random walk 접근법)

말그대로 Short fixed-length random walk의 관점에서 embedding을 접근하는 방식입니다. 그래프에서 랜덤 워크를 수행하여 노드 시퀀스를 생성하고, 이 시퀀스를 자연어 처리(NLP)의 단어 시퀀스처럼 취급하여 Word2Vec과 같은 언어 모델 기법(주로 Skip-Gram)을 적용해 노드 임베딩을 학습합니다. 핵심 아이디어는 랜덤 워크 상에서 함께 등장하는 노드들은 유사할 것이라는 가정입니다. DeepWalk (Perozzi et al., 2014)는 그래프의 노드 임베딩을 위해 랜덤 워크와 Word2Vec (Skip-Gram 모델)을 결합한 방법입니다.

 

\(z_u^T z_v\) ≈ probability that u and v cooccur on a random walk over the graph

\(z_u \): The embedding of node \( u \)
\(P(v|z_u)\): The (predicted) probability of visiting node v on random walks starting from node \(u\).

 

1) 그래프의 각 노드에서 시작하여 정해진 길이 \(l\)의 random walk를 여러 번 수행합니다. 각 워크는 노드의 시퀀스로 표현됩니다. 예를 들어, 노드 \(v_i\)​에서 시작하는 random walk는 \(W_{vi}\)​​=(\(vi​,v_{i1}​​,v_{i2}​​,...,v_{il}​​\))와 같이 나타납니다.

2) 생성된 random walk 시퀀스를 텍스트 코퍼스처럼 처리합니다. 각 노드를 "단어"로, random walk 시퀀스를 "문장"으로 취급합니다. Skip-Gram 모델을 사용하여 중심 노드 \(u\)가 주어졌을 때, random walk 상에서 \(u\)의 주변 노드(context nodes) \(v\)가 나타날 확률을 최대화하도록 노드 임베딩 \(Φ:V→\mathbf{R}^{d}\) 를 학습합니다. 이를 위한 목적 함수는 아래와 같이 쓸 수 있습니다. 제가 위에서 적었던 \(z_u\)를 \(\Phi(u)\)라고 보시면 됩니다. (저는 CS224W의 표기와 맞추었습니다)

$$ \max_{\Phi} \sum_{u \in V} \sum_{v \in N_R(u)} \log P(v | \Phi(u)) $$

여기서 \(N_R(u)\)는 random walk에서 노드 \(u\)의 context(주변)에 나타나는 이웃노드들의 집합입니다. \(P(v| \Phi(u))\) 는 중심 노드 \(u\)의 임베딩 \(Φ(u)\)가 주어졌을 때 context node \(v\)가 나타날 확률을 의미하고 주로 softmax와 같은 함수들을 사용합니다. 

$$ P(v | \Phi(u)) = \frac{\exp(\Phi(v)' \cdot \Phi(u))}{\sum_{v_k \in V} \exp(\Phi(v_k)' \cdot \Phi(u))} $$

그런데, 수식에서 알수 있듯 계산복잡도가 node의 개수의 제곱에 비례해서 높아집니다. 이것을 해결하기 위한 솔루션이 negative sampling이 됩니다. \(k\)개의 "negative" node \(n_{i}\)를 (그 node의 degree에 비례하는 확률로 sampling해서) softmax 연산에 넣는 것입니다. 모든 negative sample을 softmax 안에 넣기에는 ... 계산복잡도가 너무 높기 때문이죠. 이런 방법론은 우리가 추천시스템에서도 확인한 바 있습니다. 

 

3. Node2Vec

이름부터가 word2vec이랑 굉장히 비슷하죠? node2vec (Grover and Leskovec, 2016)은 DeepWalk의 아이디어를 확장하여, random walk 생성 과정에 유연성을 부여함으로써 다양한 종류의 노드 유사성을 포착할 수 있도록 설계되었습니다. node2vec은 BFS(Breadth-First Search, 너비 우선 탐색)와 DFS(Depth-First Search, 깊이 우선 탐색)의 특징을 모두 반영할 수 있는 biased random walk)를 도입합니다. 이 개념이 익숙하지 않으신 분들은 이전 BFS/DFS 포스팅을 참고하시기 바랍니다. 

 

2025.02.11 - [프로그래밍/Python 관련 정보] - [Algorithm] Depth/Breadth First Search

[Algorithm] Depth/Breadth First Search

 

 

 

• BFS-like exploration: 현재 노드 주변의 로컬 이웃들을 탐색하며, 이는 미시적인 관점에서 노드의 구조적 역할(structural equivalence)을 파악하는 데 유리합니다.
• DFS-like exploration: 현재 노드에서 멀리 떨어진 노드들을 탐색하며, 이는 거시적인 관점에서 노드가 속한 커뮤니티(homophily)를 파악하는 데 유리합니다.

 

node2vec은 두 가지 파라미터 p와 q를 사용하여 랜덤 워크의 다음 방문 노드를 결정합니다:

• Return parameter p (복귀 파라미터): 이전 노드로 되돌아갈 확률을 조절합니다. \(p\)가 높으면 이전 노드로 되돌아갈 확률이 낮아져 (즉, 1/p가 작아져) 이미 방문한 노드를 다시 탐색할 가능성이 줄어듭니다 (더 탐험적).
• In-out parameter q (입출력 파라미터): 현재 노드에서 멀리 떨어진 노드(DFS 방식)와 가까운 노드(BFS 방식) 중 어느 쪽을 우선적으로 탐색할지 조절합니다.
  • q>1 이면, 랜덤 워크는 이전 노드 t와 가까운 노드들(즉, t에 인접한 노드들)을 선호하게 되어 BFS와 유사한 탐색을 합니다 (로컬 구조 탐색).
  • q<1 이면, 랜덤 워크는 이전 노드 t에서 더 멀리 떨어진 노드들을 선호하게 되어 DFS와 유사한 탐색을 합니다 (글로벌 구조 탐색).

 

 

이런 방식으로 biased random walk을 생성한 이후에는 Deepwalk와 마찬가지로 Skip-Gram모델을 사용하여 동일하게 진행합니다.  $$ \max_{\Phi} \sum_{u \in V} \sum_{v \in N_S(u)} \log P(v | \Phi(u)) $$