[그래프 AI]Graph Convolution Network(GCN)

Date: 2024.08.05 Updated: 2024.08.05

카테고리: Graph

Graph Convolution Network(GCN)

1. GCN의 구조 (with Asymmetric Norm)

이미지, 텍스트, 정형 데이터는 격자 형태로 표현이 가능하다. 즉, 유클리디언 공간에 함수 좌표로 표현할 수 있다(좌표 평면상에서 벡터로 표현 가능). 반면, 소셜 네트워크나 분자 데이터 등은 유클리디언 공간 상에 표현하는 것이 어렵다. 유클리디언 공간이 아니므로 거리는 중요하지 않으며 ‘연결 여부’와 ‘연결 강도’가 중요하다.

GCN은 Semi Supervised Learning을 하며, 가장 기본적인 형태는 비대칭 정규화(Asymmetric Normalization)를 사용하여 각 노드의 이웃 정보를 집계한다.

$$h_v = f \left( \frac{1}{|\mathcal{N}(v)|} \sum_{u \in \mathcal{N}(v)} \mathbf{W} \mathbf{x}_u + b \right), \quad \forall v \in \mathcal{V}$$

Notation
- $\mathcal{N}(v)$는 노드 $v$의 이웃 노드 집합이다.
- $\mathbf{W}$는 학습 가능한 파라미터인 필터 행렬로, CNN에서 사용되는 필터와 유사한 역할을 한다.
- $\mathbf{x}_u$는 노드 $u$의 초기 노드 특징이다.
- $\mathbf{b}$는 학습 가능한 파라미터인 바이어스이다.
- $f$는 비선형 활성화 함수로, 일반적으로 ReLU가 사용된다.

이 수식은 다음과 같은 구성 요소로 나뉜다:

정규화(Normalization): $\frac{1}{\vert \mathcal{N}(v) \vert}$
이웃 집계(Neighborhood Aggregation): $\sum_{u \in \mathcal{N}(v)}$
필터 행렬(Filter matrix): $\mathbf{W}$
바이어스(Bias): $b$
초기 노드 특징(Initial Node Features): $\mathbf{x}_u$

필터 행렬은 학습 가능한 파라미터로, 노드 특징을 변환하는 역할을 한다. 이 행렬은 CNN에서 필터와 유사한 역할을 하며, 노드 특징을 새로운 공간으로 매핑하여 임베딩을 생성한다. GCN은 결론적으로 필터 행렬 $\mathbf{W}$와 바이어스 $b$를 학습한다. CNN에서 사용되는 합성곱 연산은 커널을 움직여가며 커널 크기에 해당하는 정보를 한 곳으로 모으는 과정을 의미한다. 그래프에서는 타겟 노드와 연결된 이웃 정보를 가중합 평균(Weighted Sum Average)하여 합성곱 효과를 만들어 낸다.

GCN은 이웃 노드로부터 정보를 받고 취합하는 여러 개의 레이어(layer)로 구성되어 있다. 레이어의 수가 많을수록 타겟 노드로부터 더 멀리 있는 노드들의 정보를 취합할 수 있다. 즉, 레이어의 수가 3이라면 타겟 노드로부터 3-hop 거리에 있는 노드들의 메시지까지 받을 수 있다. 위의 식은 1-hop 이웃의 정보를 취합하는 경우이며, 이를 $k$-hop의 정보를 받는 것으로 일반화하면 다음과 같다.

$$h_v^{k+1} = f \left( \frac{1}{|\mathcal{N}(v)|} \sum_{u \in \mathcal{N}(v)} \mathbf{W}^k h_u^k + \mathbf{b}^k \right), \quad \forall v \in \mathcal{V}$$

2. GCN에서의 비대칭 정규화(Asymmetric Normalization)

GCN에서 비대칭 정규화(asymmetric normalization)는 이웃 노드로부터 정보를 받아오는 중요한 과정이다. GCN의 각 레이어는 이웃 노드들의 정보를 취합하여 타겟 노드의 임베딩을 업데이트한다. 이를 통해 타겟 노드는 자신의 이웃 노드들의 특징을 반영하여 더 나은 임베딩을 학습하게 된다.

GCN의 핵심 아이디어는 타겟 노드의 이웃 노드들이 제공하는 정보를 균등하게 반영하기 위해 노드의 차수(degree)로 정규화(normalization)하는 것이다. 노드 $v$의 임베딩은 다음과 같은 수식을 통해 업데이트된다.

$$h_v^{(l)} = f \left( \sum_{u \in \mathcal{N}(v)} \frac{1}{|\mathcal{N}(v)|} \mathbf{W}^{(l)} h_u^{(l-1)} \right)$$

이 때, 합성곱을 해준 부분에 $\vert \mathcal{N} \vert$로 나눠주는 것을 볼 수 있다. 죽, 이웃의 차수(Degree)수로 정규화(Normalization)를 한다. 차수로 정규화를 하는 이유는, 각 노드가 가지는 이웃의 수가 다르기 때문이다. 차수가 큰 노드는 많은 정보를 모으기 때문에, 결과적으로 패널티를 받는다. 정규화를 통해 각 노드의 이웃 정보가 고르게 반영되도록 하여 과도한 정보 집중이나 희석을 방지할 수 있다. 구체적으로, 차수가 큰 노드는 더 많은 이웃으로부터 정보를 받기 때문에, 이러한 정보가 타겟 노드의 정보를 희석시킬 수 있다. 따라서 차수로 정규화하여 각 이웃 노드의 영향력을 동일하게 만들어, 정보의 균형을 맞추는 것이다.

이를 통해 타겟 노드를 정의하는 데 있어서 범용적인 정보의 영향력을 줄이고, 특징적인 정보를 강조하여 확실하게 구분할 수 있게 된다. 또한, GCN에서는 이웃 집합에 자기 자신(self-loop)을 추가하기 위해 별도로 결합(combine)하지 않는다. 이렇게 함으로써 이웃 노드의 메시지를 집계(aggregation)할 때 자신의 정보도 포함되도록 한다. 이를 통해 타겟 노드의 정보를 보존하면서 이웃 노드의 정보를 균형 있게 반영할 수 있다.

3. GCN의 일반화 (with Symmetric Norm)

최종적으로 타겟 노드가 메세지를 전달하고 취합할 때, 자기 자신의 정보까지 함께 처리하기 위해서 Self-Loop를 추가했을 때 수식은 위와 같이 변한다. 정규화를 해주는 부분 또한, 이웃 노드의 차수뿐만아니라 타겟 노드 자신의 차수까지 함께 고려하는 것을 볼 수 있다. 이를 Per-Neighbor 정규화라고 한다. 이를 통해, 이웃 노드들의 정보 불균형으로 인한 정보 희석뿐만 아니라 자기 정보의 희석이 되는 것을 방지할 수 있다. ($\tilde{A}$ = $A + I$)

$$h_v^{(k)} = \sigma \left( \mathbf{W}_{k-1} \cdot \text{MEAN} \left( \left\{ h_u^{(k-1)} \mid \forall u \in \mathcal{N}(v) \cup \{v\} \right\} \right) \right)$$ $$h_v^{(k)} = \sigma \left( \mathbf{W}_{k-1} \cdot \left( \sum_{u \in \mathcal{N}(v) \cup \{v\}} \frac{h_u^{(k-1)}}{\sqrt{|\mathcal{N}(u)|} \sqrt{|\mathcal{N}(v)|}} \right) \right)$$ $$H^{(k)} = \sigma \left( \hat{D}^{-\frac{1}{2}} \hat{A} \hat{D}^{-\frac{1}{2}} H^{(k-1)} W_{k-1} \right)$$

중요한 점은 GCN은 자기 정보를 취합하기 위해 Self-Loop를 추가했기 때문에, 상호작용이 없는 노드에 대해서는 임베딩 자체를 생성해내지 못한다. 왜냐하면 Self-loop는 학습 시 그래프의 모든 노드가 고정되어 있다는 가정을 기반으로 하기 때문이다. 또한, 정규화 과정에서 인접 행렬 $\hat{A}$와 차수 행렬 $\hat{D}$을 활용한다. 이 과정에서 그래프 전체의 구조 정보가 반영되기 때문에, 새로운 노드나 그래프 구조가 변할 경우 정규화 과정에 필요한 정보를 미리 알 수 없다. 즉, GCN은 Transductive하다. 따라서 한 번도 보지 못한 새로운 노드가 등장하면 노드 임베딩과 마찬가지로 전체 그래프를 다시 학습해야 한다.