그래프 머신러닝: (3-2) 이웃재구성: 랜덤워크 임베딩

(GRL) Neighborhood Reconstruction Methods: Random Walk Embeddings

graph
network
encoder-decoder
Author

Cheonghyo Cho

Hamilton,W.L. Graph Representation Learning. 2020

랜덤워크 임베딩

Random Walk Embeddings

DeepWalk and node2vec

DeepWalk와 node2vec은 전에서 소개한 방법들과 마찬가지로 shallow 임베딩 방법과 내적 디코더를 사용한다. 단, 노드 유사성과 이웃 재구성의 개념을 정의하는 방법에서 차이를 가진다.

인접행렬 \(A\)를 직접 재구성하는 대신 랜덤워크 통계량을 인코딩하는 최적화 임베딩을 구한다. 수학적으로 말하면 아래가 성립하도록 임베딩을 학습하는 것이다:

\[\text{DEC}(\mathbf{z}_u,\mathbf{z}_v) = \frac{e^{\mathbf{z}_u^{\top}\mathbf{z}_v}}{\sum_{v_k \in \mathcal{V}} e^{\mathbf{z}_u^{\top}\mathbf{z}_k}} \approx p_{\mathcal{G},T}(v|u).\]

\(p_{\mathcal{G},T}(v|u)\)는 \(u\)에서 시작해서 길이 \(T(\in \{2, \dots, 10 \})\)의 랜덤워크로 \(v\)에 도착하는 확률을 말한다. factorization-based approach와 다른 가장 중요한 점은 유사도 측정이 stochastic, asymmetric하다는 것이다.

랜덤워크 임베딩을 훈련시키기 위해서 가장 일반적인 방법은 위의 디코더를 이용하여 다음의 cross-entropy loss를 최소화하는 것이다:

\[\mathcal{L} = \sum_{(u,v)\in \mathcal{D}} -\log (\text{DEC}(\mathbf{z}_u,\mathbf{z}_v))\]

  • 여기서 \(\mathcal{D}\)는 랜덤워크의 훈련 집합을 지칭하며, 각 노드에서 시작하는 표본 랜덤워크로 생성된다.

  • 하지만 위 방법은 계산적으로 expensive하다. 손실 함수를 추정하는데 \(O(|\mathcal{D}||\mathcal{V}|)\)의 시간 복잡성을 가진다. DeepWalk와 node2vec은 이 문제를 극복하기 위한 각기 다른 방법이다.

DeepWalk는 위 식을 추정하기 위해 hierarchical softmax를 사용한다. 이 방법은 계산 가속화를 위해 이진-트리(binary-tree)를 레버리징한다.

node2vec은 noise contrastive 방법을 사용한다. 이 방법은 아래의 식으로 negative sample을 이용해 정규화 팩터를 추정한다.

\[\mathcal{L} = \sum_{(u,v) \in \mathcal{D}} -\log(\sigma(\mathbf{z}_u^\top\mathbf{z}_v)) - \gamma \mathbb{E}_{v_n\sim P_n(\mathcal{V})}[\log(-\sigma(\mathbf{z}_u^\top\mathbf{z}_{v_n}))]\]

  • 여기서 \(\sigma\)는 로지스틱 함수를 나타내고, \(P_n(\mathcal{V})\)는 노드 집합 \(\mathcal{V}\)의 분포를 나타내며, \(\gamma >0\)은 하이퍼파라미터로 가정한다. \(P_n(\mathcal{V})\)는 보통 uniform distribution으로 정의하고, 기대값는 몬테 카를로 샘플링을 이용하여 추정한다.

  • node2vec는 초기 DeepWalk 알고리즘과 달리 하이퍼파라미터를 사용해 랜덤워크 확률을 조정한다.

Large-scale information network embeddings (LINE)

LINE은 두 개의 인코더-디코더를 합친다. 첫번째로 일차(first-oreder) 인접 정보를 인코딩하고 다음 식과 같은 디코더를 사용한다: \(\text{DEC}(\mathbf{z}_u,\mathbf{z}_v) = \frac{1}{1+e^{-\mathbf{z}_u^{\top} \mathbf{z}_v}}\). 두번째는 랜덤워크 방식과 비슷하다.

LINE은 node2vec이나 DeepWalk와 개념적인 면에서 비슷하다. 확률적 디코더와 확률적 손실함수(KL-divergence기반)를 사용한다. 하지만 랜덤워크를 샘플링하는 대신 first-order, second-order 이웃 정보를 재구성한다.

Random Walk Methods And Matrix Factorization

랜덤워크 방법은 행렬 facotrization과 밀접하게 연결되어 있다.

\[S_{DW} = \log (\frac{\text{vol}(\mathcal{V})}{T}(\sum^{T}_{t=1}P^t)D^{-1}) - \log(b)\]

Shallow 임베딩의 한계

  1. 인코더가 각 노드에 대해 고유한 임베딩 벡터를 직접 최적화하기 때문에 섈로우 임베딩 방법은 인코더의 노드 간에 어떤 파라미터도 공유하지 않는다. 이러한 파라미터 공유의 부족은 통계적으로나 계산적으로 비효율적이다. 통계적 관점에서 매개변수 공유는 학습의 효율성을 향상시킬 수 있으며, 정규화의 강력한 형태로 작용하기도 한다. 계산적 관점에서 파라미터 공유가 부족하다는 것은 파라미터의 수가 \(O(V)\)로 증가한다는 것이며, 이는 방대한 그래프에서 다루기 어려울 수 있다.

  2. 섈로우 임베딩 접근법들은 인코더에서의 노드 피처(feature)들을 활용하지 않는다. 많은 그래프 데이터 세트들은 풍부한 피처 정보를 가지며, 이는 인코딩 프로세스에서 잠재적으로 정보가 될 수 있다.

  3. 섈로우 임베딩 방법은 본질적으로 transductive하다. 훈련 단계 동안 존재했던 노드에 대한 임베딩만 생성할 수 있으며, 훈련 단계 이후 관찰되는 새로운 노드에 대한 임베딩을 생성하는 것은 추가 최적화를 수행하지 않는 한 불가능하다.

이러한 한계점들을 보완하기 위해서 그래프의 구조와 특성에 의존한 조금 더 정교한 인코더로 대체하고는 한다. 이러한 인코더를 정의하는 유명한 패러다임(ie.GNN)을 다음 포스트에서 살펴보기로 하자.

참고자료

[1] Hamilton, W. L. (2020). Graph Representation Learning. Morgan & Claypool Publishers.

[2] https://velog.io/@minjung-s/GNN-Graph-Representation-Learning-Deep-Walk-node2vec