[그래프 AI]Graph Neural Network의 일반적인 학습 매커니즘

GNN의 학습 메커니즘

1. CNN vs GNN

GNN의 개념을 이해하기 위해서는 CNN의 개념을 제대로 알고 있어야한다. CNN은 정규적이고 유클리드(Euclidean) 구조의 데이터들을 임베딩하는 반면, GNN은 CNN을 보다 형식적으로 일반화한 버전이다. CNN은 2D 이미지와 같은 구조화된 격자 데이터에서 효과적으로 작동한다. 예를 들어, 위의 그림은 3x3 필터를 사용한 단일 CNN 계층을 보여준다. 여기서 각 픽셀은 주변 픽셀의 정보를 통합하여 업데이트된다. 구체적으로, 각 픽셀은 이웃 픽셀로부터 메시지를 개별적으로 변환하고, 이 메시지들을 합산하여 업데이트된다. 이 과정은 다음 수식으로 표현된다:

$$ \mathbf{h}_4^{(l+1)} = \sigma \left( \mathbf{W}_0^{(l)} \mathbf{h}_0^{(l)} + \mathbf{W}_1^{(l)} \mathbf{h}_1^{(l)} + \cdots + \mathbf{W}_8^{(l)} \mathbf{h}_8^{(l)} \right) $$

여기서 (\(\mathbf{h}_i\))는 픽셀 혹은 노드의 은닉층 활성화값을 나타내고, (\(\mathbf{W}_i\))는 각 메시지에 대한 가중치 행렬을 나타낸다.

반면, GNN은 정규적이지 않고 비유클리드(Non-Euclidean) 구조의 데이터를 처리한다. 이는 그래프 구조의 데이터를 다루는 데 특화되어 있으며, 소셜 네트워크, 화합물 구조, 지식 그래프 등과 같은 복잡한 데이터 간의 관계를 분석하고 예측하는 데 사용된다. GNN은 각 정점이 이웃 정점의 정보를 집계하여 자신의 상태를 업데이트하는 방식으로 작동하며, CNN과 유사하게 이웃 정점으로부터 메시지를 수집(Message Passing)하고 이를 통합(Aggregation)하여 업데이트한다. 따라서 GNN은 CNN의 개념을 보다 일반화하여 다양한 데이터 구조에 적용할 수 있게 하며, 이는 다양한 도메인에서 복잡한 데이터 간의 관계를 효과적으로 학습할 수 있게 한다.

2. GNN의 기본 구조

GNN은 입력으로 특성 행렬(Feature Matrix)과 인접 행렬(Adjacency matrix)을 받는다. 구조 정보와 노드들의 특징을 활용하여 그래프 내의 노드(=정점)들의 임베딩을 학습하게 된다.

GNN의 주요 아이디어는 노드 쌍 간에 메시지를 전달하고 이를 집계하는 것이다. 이를 통해 노드(그리고 필요 시 간선)의 표현을 세밀하게 다듬는다. GNN의 구조는 여러 개의 은닉층을 포함하며, 각 은닉층에서는 노드 간의 정보를 전달하여 임베딩을 반복적으로 계산한다. 구체적으로, 각 단계에서 타겟 노드의 임베딩을 1-hop 단위로 이웃 노드들의 정보를 취합하여 업데이트한다. 각 스텝에서 이웃 노드의 정보를 통합하고, 이를 통해 타겟 노드의 임베딩을 점진적으로 구체화한다.

이 과정은 다음과 같이 요약할 수 있다:

• 인접 행렬(Adjacency matrix) = \(\mathbf{A} \in \mathbb{R}^{N \times N}\)
• 특성 행렬(Feature matrix) = \(\mathbf{X} \in \mathbb{R}^{N \times F}\)

이 예시에서, 입력은 특성 행렬과 인접행렬로 구성되며, 각 노드는 이웃 노드와의 메시지 교환을 통해 자신의 임베딩을 갱신한다. 그림에서처럼 은닉층을 거칠 때마다 ReLU와 같은 활성화 함수가 적용되어 각 단계의 임베딩이 더욱 정교해진다. 이와 같은 과정을 통해 GNN은 그래프 내의 구조적 패턴과 노드 간의 복잡한 관계를 효과적으로 학습할 수 있다.

이 때, 이웃 노드들의 정보(=메세지)를 타겟 노드로 전달해주는 것을 메세지 패싱(Message Passing), 타겟 노드가 이 정보들을 취합하는 것을 집계(Aggregation)이라고 한다. 그리고 경우에 따라 추가적인 정보를 이 메세지와 함께 합치는 과정을 결합(Combine)이라고 한다.

3. Inductive Capability

그래프 신경망(GNN)은 그래프 데이터의 노드와 엣지 정보를 이용하여 노드 임베딩을 생성한다. GNN의 중요한 특징 중 하나는 동일한 파라미터를 모든 노드가 공유한다는 점이다. 즉, 노드마다 임베딩 파라미터를 정의하는 노드 임베딩과는 달리, GNN은 파라미터를 공유(Parameter Sharing)한다. 이는 모델 파라미터의 수가 그래프의 노드 수(\(\vert V \vert\))에 비례하지 않고 서브리니어(sublinear)하게 유지된다는 것을 의미한다. 결과적으로, GNN은 학습되지 않은 새로운 노드에 대해서도 일반화(Generalization)할 수 있는 능력을 갖추게 된다.

위 그림에서 볼 수 있듯이, 특정 노드(A 또는 B)에 대해 그래프를 구성할 때, 동일한 집계 파라미터를 사용하여 임베딩을 계산한다. 이는 노드 수와 파라미터 수가 무관하게 만들며, 새로운 노드에 대해서도 모델이 일반화할 수 있게 한다.

GNN의 레이어는 크게 세 가지 단계로 구성된다: 메시지 전달(Message Passing), 집계(Aggregation), 그리고 선택적으로 자기 정보 결합(Combine[Self Information])이다. 이 과정에서 각 노드는 이웃 노드의 정보를 받아 집계하고, 필요한 경우 자기 정보와 결합하여 최종 임베딩을 생성한다.

그러나 모든 GNN 모델이 Inductive한 것은 아니다. 일부 모델은 Transductive한 성격을 가지며, 학습된 그래프의 구조에만 적용될 수 있다. 예를 들어, GCN(Graph Convolutional Network)은 Transductive한 반면, GraphSAGE는 Inductive한 특성을 가진다.

4. GNN Operation

4-1. 메세지 전달(Message Passing)

메시지 전달(Message Passing) 과정은 그래프 신경망(GNN)에서 중요한 단계 중 하나이다. 이 과정에서는 각 노드가 이웃 노드로부터 메시지를 받아 이를 전달할 메시지로 변환한다. 메시지 함수(MSG 함수)는 이전 레이어의 노드 특징 (\(h_u^{(l-1)}\))을 입력으로 받아 새로운 메시지 (\(m_u^{(l)}\))를 생성한다. 하나의 이웃 노드는 하나의 메시지를 생성하며, 이 메시지들은 집계 과정에서 사용된다.

메시지 전달 과정은 다음과 같은 세부 단계로 구성된다:

1. 메시지 함수
   • 식: \(m_u^{(l)} = \text{MSG}^{(l)} \left( h_u^{(l-1)} \right)\)
2. 각 노드가 메시지를 만듦
   • 식: \(m_u^{(l)} = W^{(l)} h_u^{(l-1)}\)

4-2. 메세지 집계(Aggregation)

집계(Aggregation) 과정은 그래프 신경망(GNN)에서 중요한 단계 중 하나이다. 이 과정은 여러 이웃 노드로부터 받은 메시지들을 하나로 합치는 과정을 포함한다. 이웃 노드의 메시지를 하나로 합치는 방법은 다양한 방식이 있으며, 이를 집계 함수(aggregator)라고 한다.

집계 과정은 다음과 같은 세부 단계로 구성된다:

1. 이웃 정보를 취함
   • 식: \(a_v^{(l)} = \text{AGG}^{(l)} \left(\left\{m_u^{(l-1)} \mid u \in N(v)\right\}\right)\)
2. 집계를 하는 Aggregator의 예
   • 합계(Sum)
   • 평균(Mean)
   • 최대값(MAX)

집계 함수는 이웃 노드로부터 받은 메시지들을 특정 방식으로 결합하여 하나의 값으로 변환한다. 예를 들어, 합계(Sum), 평균(Mean), 최대값(MAX) 등이 일반적으로 사용되는 집계 함수이다. 이러한 집계 과정을 통해 노드는 주변 이웃들의 정보를 효과적으로 통합할 수 있다.

4-3. 결합(Combine)

결합(Combine) 과정은 그래프 신경망(GNN)에서 타겟 노드의 자체 정보를 유실하지 않도록 포함시키기 위한 단계이다. 결합 과정에서는 이웃 노드들의 집계된 정보와 타겟 노드의 자체 정보를 결합하여 최종 노드 임베딩을 생성한다.

결합 과정은 다음과 같은 세부 단계로 구성된다:

1. 목적: 타겟 노드 (\(v\))의 자체 정보가 유실되지 않도록 포함시키기 위함.
2. 포함: 따라서, (\(h_v^{(l)}\))를 계산할 때 (\(h_v^{(l-1)}\))도 포함시켜야 함.
3. 결합 과정:
   • 식 1. \(h_v^{(l)} = \text{Combine}^{(l)} \left(a_v^{(l)}, m_v^{(l-1)}\right)\)
   • 식 2. \(a_v^{(l)} = \text{AGG}^{(l)}\left(\left\{m_u^{(l)} \mid u \in N(v)\right\}\right)\)
   • 식 3. \(m_u^{(l)} = W^{(l)} h_u^{(l-1)}\)
   • 식 4. \(m_v^{(l-1)} = B^{(l)} h_v^{(l-1)}\)
4. 결합이 필요 없을 경우: 만약 결합이 필요 없다면 (\(h_v^{(l)} = a_v^{(l)}\))로 둠.

결합 과정을 통해 타겟 노드의 자체 정보와 이웃 노드의 집계된 정보를 모두 포함한 최종 임베딩을 생성할 수 있다. 이는 타겟 노드의 자체 정보가 유실되지 않도록 보장한다.

GNN이 해결하는 문제(Task)

1. 문제 종류

• Input: 특징 행렬(Feature Matrix) + 인접 행렬(Adjacent Matrix)
• Output: 노드 임베딩(Node Embedding)

그래프 신경망(GNN)은 입력으로 특징 행렬(\(\mathbf{X}\))과 인접 행렬(\(\hat{\mathbf{A}}\))를 받는다. 이를 통해 각 노드의 임베딩을 학습하고, 다양한 그래프 기반 예측 문제를 해결할 수 있다. GNN의 출력은 노드 임베딩이다.

입력 단계에서는 \(\mathbf{X} = \mathbf{H}^{(0)}\)로 초기화된다. 이후, 은닉 표현(hidden representation)을 입력받아 가중치 행렬 \(\mathbf{W}^{(l)}\)를 곱하고 비선형 함수 \(\sigma\)를 적용하여 다음 레이어의 은닉 표현을 얻는다. 이 과정은 다음과 같은 수식으로 표현된다. \(\hat{\mathbf{A}} = \mathbf{A} + I\)은 인접 행렬 + Self-loop를 나타댄다:

$$\mathbf{H}^{(l+1)} = \sigma \left( \hat{\mathbf{A}} \mathbf{H}^{(l)} \mathbf{W}^{(l)} \right)$$

이러한 과정을 여러 레이어에 걸쳐 반복하여 최종 출력 \(\mathbf{Z} = \mathbf{H}^{(N)}\)를 얻는다. 최종 출력은 다양한 그래프 기반 예측 문제에 활용될 수 있다.

• 노드 분류: 소프트맥스(Softmax)를 적용하여 각 노드의 클래스를 예측
  • Node Classification
  • 식: \(\text{softmax}(\mathbf{z}_n)\)
• 그래프 분류: 전체 그래프에 대한 클래스를 예측, 각 노드 임베딩의 합을 소프트맥스로 변환
  • Graph Classification
  • 식: \(\text{softmax}\left(\sum_{n} \mathbf{z}_n \right)\)
• 링크 예측: 두 노드 임베딩 간의 내적(dot product)을 통해 연결 가능성을 예측
  • Link Prediction
  • 식: \(p(\mathbf{A}_{ij}) = \sigma \left( \mathbf{z}_i^T \mathbf{z}_j \right)\)

2. 손실 함수

2-1. 노드 분류를 위한 손실 함수

노드 분류(Node Classification)를 위한 손실 함수는 Cross-Entropy를 사용한다. 이 과정에서 학습 가능한 파라미터인 가중치 벡터 (\(\mathbf{W}\))를 통해 노드 임베딩과 가중치의 곱이 타겟이 1인 경우 크게, 타겟이 0인 경우 작게 학습되도록 한다.

노드 분류는 반지도 학습(Semi-Supervised Learning)과 지도 학습(Supervised Learning) 방식이 모두 있다. 반지도 학습에서는 Transductive 접근법을 사용하고, 지도 학습에서는 Inductive 접근법을 사용한다.

1. Transductive 접근법:
   • Train Set에는 라벨이 있는 노드들이 존재하지만 Test Set에는 라벨이 없다.
   • Test Set에는 Train Set 그래프 내에 존재하기 때문에 Test Set의 속성들이 학습 시 메시지 전달과 집계에 영향을 미친다.
2. Inductive 접근법:
   • Test Set의 노드들이 Train Set로 만든 그래프 안에 존재하지 않는다.
   • 학습되지 않은 데이터에 대해 분류를 수행하는 방식이다.

다시 말해, Training set에는 노드들이 label이 존재하지만 Test set에는 label이 없다. 하지만, Test set이 Training set 그래프 안에 존재하기 때문에 Test set의 특징(attribute)들이 학습 시 메세지 전달과 메세지들을 취합하는데 영향을 끼치게 된다. 최종적으로 Cross-Entropy 함수는 다음과 같이 정의된다:

$$\mathcal{L} = \sum_{u \in V_{\text{train}}} -\log(\text{softmax}(\mathbf{z}_u, \mathbf{y}_u))$$

여기서 소프트맥스 함수는 다음과 같다. 여기서 \(\mathbf{z}_u\)는 노드 \(u\)의 임베딩, \(\mathbf{y}_u\)는 노드 \(u\)의 타겟 라벨, \(\mathbf{w}_i\)는 클래스 \(i\)에 대한 가중치 벡터이다:

$$\text{softmax}(\mathbf{z}_u, \mathbf{y}_u) = \sum_{i=1}^{c} \mathbf{y}_u[i] \frac{e^{\mathbf{z}_u^T \mathbf{w}_i}}{\sum_{j=1}^{c} e^{\mathbf{z}_u^T \mathbf{w}_j}}$$

2-2. 그래프 분류를 위한 손실 함수

그래프 수준 작업(Graph-Level Task)을 위한 손실 함수는 그래프 분류(Graph Classification)와 그래프 회귀(Graph Regression)로 나눌 수 있다. 그래프 풀링(Graph Pooling)을 거친 후 얻은 그래프 임베딩 \(\mathbf{z}_{G}\)를 사용하여 손실 함수를 정의한다.

1. 그래프 분류 (Graph Classification):
   • 그래프 분류는 각 그래프를 특정 클래스에 할당하는 문제이다.
   • Cross-Entropy을 사용하여 각 그래프가 특정 클래스에 속할 확률을 최대화한다.
   • Cross-Entropy은 다음과 같이 정의된다:

$$\mathcal{L} = \sum_{u \in V_{\text{train}}} -\log(\text{softmax}(\mathbf{z}_u, \mathbf{y}_u))$$ $$\text{softmax}(\mathbf{z}_u, \mathbf{y}_u) = \sum_{i=1}^{c} \mathbf{y}_u[i] \frac{e^{\mathbf{z}_u^T \mathbf{w}_i}}{\sum_{j=1}^{c} e^{\mathbf{z}_u^T \mathbf{w}_j}}$$

1. 그래프 회귀 (Graph Regression):
   • 그래프 회귀는 각 그래프를 실수 값으로 예측하는 문제이다.
   • 평균 제곱 오차(MSE, Mean Squared Error) 손실 함수를 사용하여 예측값과 실제값 사이의 차이를 최소화한다.
   • MSE 손실 함수는 다음과 같이 정의된다:

$$\mathcal{L} = \sum_{G_i \in \mathcal{T}} \left\| \text{MLP}(\mathbf{z}_{G_i}) - \mathbf{y}_{G_i} \right\|^2_2$$

그래프 분류는 0이나 1과 같은 클래스로 구분하는 반면, 그래프 회귀는 실수 값을 예측한다. 예를 들어, 분자 구조 예측과 같은 작업에서 그래프 회귀를 사용하여 특정 분자의 속성을 예측할 수 있다.

2-3. 링크 예측을 위한 손실 함수

링크 예측(Link Prediction)에서 손실 함수는 두 노드 임베딩의 유사도를 계산하여 비교하는 방식이다. 두 노드의 벡터 거리가 가까워지면(L2-norm, MSE) 두 벡터의 각도가 줄어들어 코사인 유사도(Cosine Similarity)나 내적 값이 증가한다. 따라서, 노드 쌍 간의 유사도를 계산하고 이를 실제 값과 비교하여 손실을 최소화하는 것이 목표이다.

페어와이즈 노드 임베딩 손실 함수(Pairwise Node Embedding Loss Function)는 다음과 같이 정의된다:

$$\mathcal{L} = \sum_{(u,v) \in \mathcal{D}} \ell \left( \text{DEC}(\mathbf{z}_u, \mathbf{z}_v), \mathbf{S}[u, v] \right)$$

이 때, \(\text{DEC}(\mathbf{z}_u, \mathbf{z}_v)\)는 두 노드 임베딩 \(\mathbf{z}_u\)와 \(\mathbf{z}_v\) 간의 유사도를 나타낸다. \(\mathbf{S}[u, v]\)는 실제 노드 쌍 간의 관계를 나타내며, 예를 들어 인접 행렬 \(\mathbf{A}\)가 될 수 있다.

링크 예측에서는 두 노드 간의 벡터 거리가 가까워질수록 두 벡터의 각도가 줄어들어 코사인 유사도나 내적 값이 증가하게 된다. 이는 두 노드가 실제로 연결되어 있을 확률이 높아지는 것을 의미한다. 따라서, 손실 함수는 예측된 유사도와 실제 값을 비교하여 차이를 최소화하도록 학습된다.

2-4. Semi-Supervised Learning GNN을 위한 Setting

특징은, 몇몇 노드들만 Labeling이 되어있다. 나머지는 모두 Unlabeled이다.

• Task
• Labeled 노드들로 Unlabeled 노드들을 예측
• GCN with asymmetric normalization이 이에 해당

Reference

[강의]: CS224W

Graph 카테고리 내 다른 글 보러가기