Data & Research

[Graph Neural Networks] Concepts of GNN

물박사의 저장공간 2025. 6. 3. 22:22

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

저번 시간까지의 내용은 주로 Neural Network의 개념을 Graph로 도입하기 전의 작업들이었습니다. 그렇다면 앞으로 진행될 Graph Neural Network의 컨셉은 앞 서 살펴본 내용과는 어떤 점에서 차이가 있을까요? 본격적인 GNN의 첫 포스팅에서는 GNN의 일반적인 컨셉부터 알아보겠습니다. 

 

Deep Graph Encoders : 사실 기본적인 얼개 자체는 이전 내용과 통하는 부분이 있습니다. 추상적인 개념인 Graph라는 것을 정량화해서 embedding(encoding) 한다. 그리고 이 과정에서 여러 층의 심층신경망 구조를 동원한다는 건데요

사실 GNN이 어려운 이유는 Graph의 node는 canonical order가 없다는 것 때문입니다. 

 

이 사실을 유념하면서 GNN이 그래프 데이터를 효과적으로 처리하기 위한 핵심 요건을 알아봅시다. 

 

1. Mapping 함수의 속성

1) 순열 불변성(Permutation Invariance)

입력의 순서가 바뀌어도 함수의 출력이 동일하게 유지되는 특성을 의미합니다. 그래프의 맥락에서, 노드들은 특정 순서로 정렬되어 있지 않습니다. 예를 들어, 3개의 노드 A, B, C로 구성된 그래프는 [A, B, C] 순서로 표현될 수도 있고, [C, A, B] 순서로 표현될 수도 있지만, 이들은 동일한 그래프입니다. GNN이 그래프 전체에 대한 예측(예: 그래프 분류, 그래프 속성 예측)을 수행할 때, 입력 노드의 순서가 어떻게 바뀌든 동일한 예측 결과를 내놓아야 합니다. 이것이 바로 순열 불변성입니다.

 

그래프 \(G=(A,X)\) (여기서 \(A\)는 Adjancency Matrix, \(X\)는 node feature matrix)에 대해 GNN 함수를 \(f\)라고 할 때, 임의의 순열 행렬(Permutation Matrix) \(P\)에 대해 다음이 하면 순열 불변이라고 한다. \[f(A, X) = f(PAP^T, PX)\]

 

GNN에서는 주로 마지막 단계에서 노드별 embedding들을 집계(aggregate)하여 그래프 전체의 표현(graph representation)을 얻을 때 순열 불변성을 확보합니다.

 

2) 순열 공변성(Permutation Equivariance)

Permutation Equivariance는 입력의 순서가 바뀌면 함수의 출력도 동일한 방식으로 순서가 바뀌는 특성을 의미합니다.

 

GNN의 한 layer (또는 전체 노드 embedding 함수)을 \(f\)라고 하고, 입력이 \((A,X)\)일 때 출력 노드 embedding 행렬이 \(Z=f(A,X)\)라고 할 때(여기서 \(Z\)의 각 행 \(z_i\)​는 노드 \(i\)의 embedding, 임의의 순열 행렬 P에 대해 다음이 성립하면 순열 공변이라 한다

\[Pf(A, X) = f(PAP^T, PX)\]

 

2. GNN의 작동 방식

Graph Neural Network(GNN)의 일반적인 작동 방식의 핵심에는 메시지(Message) 전달과 집계(Aggregation) step이 있습니다. 이 과정을 통해 각 노드는 자신의 이웃 노드들로부터 정보를 수집하고, 이를 바탕으로 자신의 embedding(혹은 representation)을 업데이트합니다. 이를 흔히 Message Passing 패러다임이라고 부릅니다.

1) Message

메시지(Message)는 그래프 내의 한 노드가 다른 노드(주로 자신의 이웃 노드)에게 전달하는 정보 조각입니다. 각 GNN layer에서, 노드들은 자신의 현재 상태(embedding)와 연결된 edge의 정보를 바탕으로 메시지를 생성하여 이웃에게 전달합니다. 이웃 노드의 정보를 현재 노드에게 전달하여, 현재 노드가 자신의 local neighborhood context를 이해하고 표현을 풍부하게 만들도록 돕습니다.

 

메시지는 일반적으로 다음 요소들을 입력으로 하는 함수에 의해 생성됩니다

  • 송신 노드(또는 수신 노드의 이웃 노드 j)의 현재 layer(\(l\))에서의 feature vector(embedding) \(h_{j}^{(l)}\)​
  • (optional) 수신 노드 \(i\)의 현재 layer(\(l\))에서의 feature vector(embedding) \(h_{i}^{(l)}\) ​
  • (optional) 노드 \(j\)와 \(i\)를 연결하는 edge의 feature vector \(e_{ji}\)

일반적인 메시지 함수에서 노드 \(j\)에서 노드 \(i\)로 전달되는 메시지는 다음과 같습니다

$$ \mathbf{m}_{j \to i}^{(l+1)} = M^{(l)}(\mathbf{h}_i^{(l)}, \mathbf{h}_j^{(l)}, \mathbf{e}_{ji}) $$

 

2) Aggregation

집계(Aggregation) 단계에서는 각 노드가 자신에게 도달한 모든 이웃 노드들의 메시지들을 하나로 통합합니다. 특정 노드가 자신의 이웃들로부터 받은 다양한 정보(메시지들)를 요약하여 단일 벡터로 만듭니다. 이 단일 벡터는 해당 노드의 "이웃 정보 요약"이라고 볼 수 있습니다. 집계 함수는 입력 메시지들의 순서에 영향을 받지 않아야 합니다(Permutation Invariant). 왜냐하면 그래프에서 이웃 노드들은 자연적인 순서를 가지고 있지 않기 때문입니다. 집계된 메시지는 다음과 같이 표현됩니다. 

$$ \mathbf{a}_i^{(l+1)} = \text{AGGREGATE}^{(l)} ( \{\mathbf{m}_{j \to i}^{(l+1)} : j \in \mathcal{N}(i)\} ) $$

 

참고) GNN모델에 따라서는 message 생성과 aggregation이 한 단계로 통합된 형태를 띠기도 합니다. 

$$ \mathbf{a}_i^{(l+1)} = \text{AGGREGATE}_{j \in \mathcal{N}(i)} ( \phi^{(l)}(\mathbf{h}_j^{(l)}, \mathbf{e}_{ji}) ) $$

 

3) Update

이 단계에서 각 노드 \(i\)는 집계된 이웃 정보 \(\mathbf{a}_i^{(l+1)}\)와 자기 자신의 이전 layer(\(l\))에서의 embedding \( \mathbf{h}_i^{(l)} \) 을 결합하여 현재 layer(\(l+1\))에서의 새로운 embedding \(\mathbf{h}_i^{(l+1)}\)을 계산합니다. 업데이트 함수는 다음과 같이 표현할 수 있습니다. 

$$ \mathbf{h}_i^{(l+1)} = U^{(l)}(\mathbf{h}_i^{(l)}, \mathbf{a}_i^{(l+1)}) $$

 

이 업데이트 함수는 일반적으로 신경망 layer(예: GRU, LSTM cell과 유사한 gating mechanism, 단순한 MLP)와 activation 함수(예: ReLU, Sigmoid)를 활용합니다.

 

이러한 일반론을 파이썬에서 포괄할 수 있도록 되어있는 대표적인 패키지가 Pytorch Geometric입니다.