[Graph Neural Networks] Node Similarity

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

---

Graph라는 추상적인 개념을 정량화하는 컨셉이 Node Embedding(Encoder)이었다면, 이렇게 Emebedding된 결과물들이 원래 original network에서의 특성을 잘 반영하도록(original network에서 similarity가 높았던 node는 embedding 후에도 similarity가 높도록) 하는 "Decoder"의 역할도 고찰해보아야겠죠. 기본적인 schema는 아래와 같습니다.

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

 

그러니까 embedding된 것들의 similarity가 원래 original network에서의 '유사성'을 잘 반영할 수 있도록 optimize를 해야한다는 건데.. 그럼 original network에서 노드의 유사성을 먼저 정의해야겠네요. 추상적인 개념인 graph에서 노드 간 유사성을 어떻게 생각해 볼 수 있을까요?

 

1. Node Similarity - Adjacency Matrix

가장 간단하게 생각해볼 수 있는 node similarity는 node끼리 edge로 연결되면 유사하고 그렇지 아니면 유사하지 않다고 간주하는 것입니다. 그런 관점에서 node의 original network에서의 node의 유사도는 graph의 adjacency matrix(\(A\))가 되는 셈이죠. 그럼 우리가 optimize해야하는 식은 아래와 생각해볼 수 있습니다. 

어디서 많이 봤던 꼴이죠? 추천시스템에서 "Matrix Factorization"에서 봤던 식입니다. 사실 일반적으로 embedding의 차원 \(d\)는 node의 개수 \(n\)보다 매우 작기 때문에 이 식을 정확히 만족시키는 해를 찾는 것은 불가능합니다. 다만 \[\underset{Z}{\min} \lVert \mathbf{A} - \mathbf{Z}^\top \mathbf{Z} \rVert_2\] 의 최적화 식을 푸는 방법으로 근사시킬 수는 있습니다. 

결론은 edge connectivity를 유사도로 설정했을 때 node embedding의 최적화 식은 Adjacency Matrix \(A\)의 matrix factorization이다. 

 

 

2. Node Similarity - Deep Walk

Deep walk이나 node2vec 같은 경우에는 node간 유사도를 random walk기반으로 정의한 것이죠. Deep walk의 경우에는 node embedding의 최적화 식이 아래 식을 matrix factorization하는 것이라 보시면 됩니다. 

 

3. Node Similarity - Node2Vec 외

그 밖에 다른 방법론들도 similarity의 구체적인 정의는 다르지만 아래 식을 matrix factorization하여 embedding 시킨다는 관점에서는 동일합니다. 

 

Qiu, Jiezhong, et al. "Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec." Proceedings of the eleventh ACM international conference on web search and data mining. 2018.

 

지금까지 소개한 Matrix Factorization의 확장으로 볼 수 있는 방법론(Adjacent matrix, Deep Walk, Node2Vec..)들은 본격적으로 neural network의 개념을 Graph에 가져오기 전에 기존의 개념들을 최대한 활용해서 node의 정보를 embedding하려는 노력이었다 보시면 될 것 같습니다. 그런데, 이러한 방식에는 아래와 같은 몇 가지 문제점이 존재하는데요

1) Training Dataset에 존재하지 않는 node에 대해서는 Embedding할 수 없다
(원할 경우 전체 데이터셋에 대한 재계산 필요)

 

2) 구조적 유사성(Structural Similarity)를 포착하기 어렵다

1과 11은 유사한 역할을 하고 있는데 1에서 11에 random walk으로 도닳하기는 어렵다

3) Node의 Feature는 활용할 수 없다

 

이러한 한계점을 극복하기 위해서 이제 Graph Neural Network의 개념이 본격적으로 도입되었다고 보시면 될 것 같은데요. 이 내용은 이어지는 포스팅들에서 다루도록 하겠습니다.