[Graph Neural Networks] Graph Convolutional Networks (GCN)
2025.06.08 - [Data & Research] - [Graph Neural Networks] Table of Contents
이번 포스팅에서는 대표적인 GNN 모델인 GCN에 대해서 알아보도록 하겠습니다. GCN은 Spatial 관점과 Spectral 관점에서 접근해 볼 수 있는데, 일단 Spatial 관점에서 접근해서 알아보고 이후 Spectral 관점과 어떻게 연결되는지 살펴보는 방식으로 진행하겠습니다.
1. CNN과 GNN
이름에서 알 수 있듯이 Convolution의 개념이 들어간 Graph Neural Network입니다. CNN에 대해서 예~전에 포스팅한 적이 있었죠? 벌써 5년 가까이 오래된 일이네요.. 소름..
2021.11.16 - [Data & Research] - [Deep Learning] Convolutional Neural Network (CNN)
[Deep Learning] Convolutional Neural Network (CNN)
이번 포스팅에서는 기초 딥러닝 구조 중 하나인 CNN에 대해서 정리하겠습니다. 저도 간단한 conference paper만 한번 써봤을 뿐 딥러닝 분야 전문가는 아니기에 제가 확실히 아는 부분 중심으로만 정
trillionver2.tistory.com
어쨌든 CNN이라는 것은 Convolution의 개념을 가져와서 이미지픽셀의 주변 지형적(geometrical) 정보를 충분히 뽑아내는 방식이었습니다. 유사하게 (spatial 관점에서의) GCN는 CNN처럼 Convolution의 개념을 가져와서 주변의 위상(topological) 정보를 뽑아내려는 구조입니다. 그러니까 CNN이 특정 픽셀을 기준으로 동,서,남,북, ... 의 상대적인 위치의 정보를 뽑아내는 건데 그래프에서는 왼쪽에 있냐 오른쪽에 있냐 이런것은 중요하지 않죠. 고등학교 때 자연계 전공을 하셨다면 화학에서의 이성질체를 떠올려보시면 뭔가 이해가 되실 것 같습니다. 위상관계(연결이 되어 있느냐 아니냐)가 중요하고 그 정보를 뽑아내기 위한 방법이 GCN입니다.
2. GNN의 구조
일단 먼저 scaler 형태의 식부터 살펴볼까요?
일단 0번째 layer는 아직 Convolution layer를 통과하지 않은 것이니 embedding값이 그냥 node feature 입니다.
GNN에서 layer는 해당 노드에서 연결관계에 있는 node로 한 번 넘어갈 때마다 바뀌는 개념이라고 보시면 됩니다(hop이라고 표현하기도 합니다). 예를들어 위 그림에서 관심대상 노드를 가운데 파란색 노드라고 가정해 봅시다. 그럼 이 노드 입장에서 1번째 layer는 첫번째 hop(빨간색 노드)들로부터 들어오는 신호들의 convolution layer가 됩니다. 다시 2번째 layer는 두번째 hop(보라색 노드)들로부터 들어오는 신호들의 convolution layer가 되는 식입니다.
그리고 layer를 통과할 때마다 embedding(혹은 hidden representation)값이 위의 점화식을 통해서 업데이트 되는데요. \(k+1\)번째 layer의 embedding은 \(k\)번째 layer에서 이웃의 embedding 평균을 \(W_{k}\) 만큼 weight을 주고 거기에 자기자신의 \(k\) layer의 embedding값도 \(B_{k}\)만큼 weight을 줍니다. 그리고 activation function을 가해서 나온 것이 \(k+1\)번째 layer에서의 새로운 embedding값이 되는 겁니다. \(W_{k}\) 가 클수록 neighbor 정보를 많이 가져오게 되고, \(B_{k}\)가 클수록 이전 layer에서의 자신의 정보를 많이 가져오게 됩니다.
지난 포스팅에서 다루었듯이 message passing 패러다임을 따르는 녀석들은 "Message"와 "Aggregation" 을 가지고 있다고 했죠? 그런 관점에서 GCN은 Message와 Aggregation이 아래와 같은 방식으로 이루어진다고 볼 수 있습니다.
이걸 Matrix Formation으로 바꿔주면
일단 CS224W의 표기에 대응되는 Matrix formation입니다. CNN에서는 옆에 있는 픽셀이면 다 같이 filter의 적용을 받아서 weight이 곱해지지만 graph에서는 edge로 연결된 이웃노드에만 weight를 가해주어야 하기에 Adjacent matrix를 활용해서 연결된 것만 취합합니다. 이웃노드 외에 전 layer에서의 자신의 정보도 가져오려한다면 두번째 항도 있어야 합니다. 좀 더 간단하게 표기하기위해 Adjacent matrix에 단위행렬을 더해서 \(\hat{A}\) 으로 쓰고 weight은 한꺼번에 통으로 \(W_{k}\) 써서 표기하기도 합니다.
여기서 Adjacent matrix의 "정규화(Normalization)"에 대해서 체크해볼 포인트가 있는데요
1) Adjacent matrix normalization의 필요성
원래 Adjacent matrix를 그대로 갖다 사용하면 연결이 많이 되어 있는 노드는 feature representation에서 큰 값을 가지고, 연결이 적은 노드는 값이 작아지게 되어 최적화 과정에서 exploding/vanishing gradient 문제가 발생할 수 있습니다. 그래서 node의 degree에 따라 이렇게 발산하지 않도록 normalization이 필요하고 이 normalized adjacent matrix를 \(\tilde{A}\)라고 표기했습니다.
2) Normalization 방법
지금 여기 표기(CS224W)에서는 직관적인 정규화 방식을 사용했습니다. 각 노드가 자신의 이웃 노드들의 feature vector를 평균내어 집계하겠다는 의미입니다. 이런 방식으로 정규화(normalization)할 때는 \[\tilde{A} = D^{-1}A\] 와 같이 사용합니다.
그런데, 일반적으로 GCN이라 함은 Kipf & Welling (2017) 논문에서의 구조를 지칭하는 경우가 많고 이 때는 정규화를 조금 다른 방식으로 진행합니다(이 방식은 뒤에서 말씀드리겠지만 Spectral GCN의 개념과 연결됩니다). 정보를 보내는 노드와 받는 노드 양쪽의 차수를 모두 고려하는 방식으로 symmetric matrix형태가 되는데요. 그 형태는 아래와 같습니다.
$$ \tilde{A} = D^{-\frac{1}{2}} A D^{-\frac{1}{2}} $$
3. GCN의 Training
GCN의 objective function도 기존 딥러닝의 방법론과 크게 다르진 않습니다(e.g. cross-entropy). 목적에 맞게 유연하게 조절해서 사용하게 됩니다.
1) Supervised Learning
2) Un-supervised Learning (AutoEncoder와 유사한 발상)
link prediction(그래프 구조 복원)이 목적이라면 아래와 같이 목적함수를 만들어볼 수도 있을 겁니다.
4. Spectral GCN과 Spatial GCN의 관계
마지막으로 서두에 말씀드렸던 Spectral 관점과 Spatial 관점의 GCN을 연결지어 보겠습니다. 일단 두 관점의 시작점은 아래와 같이 다릅니다.
- Spatial Convolution : Central Node를 주위 Neighbor Node의 Feature로 Update
- Spectral Convolution : Graph convolution을 Graph Signal Processing의 일환으로 보며, graph signal에 대한 noise 제거 과정으로 간주
(1) Graph에서의 신호(Signal)
지금까지 살펴본 것은 Spatial Convolution의 관점이었으니, Spectral Convolution을 살펴보아야겠군요. 먼저 그래프에서의 "신호"를 정의해야 합니다. 그래프 신호(graph signal) \(\mathbf{x} \in \mathbb{R}^N \)는 각 그래프의 노드 \(v_i\)에 할당된 스칼라 값입니다. \[ \mathbf{x} = [x_1, x_2, \dots, x_N]^T \]
여기서 \(N\)은 노드의 총 개수입니다. 시간 영역이나 공간 영역의 일반적인 신호(예: 음성, 이미지)는 푸리에 변환을 통해 주파수 영역에서 분석할 수 있습니다. 푸리에 변환은 신호를 서로 다른 주파수를 가진 기저 함수(basis functions, 예: sin, cos)들의 합으로 분해합니다. 그래프 신호에 대해서도 유사한 변환을 정의하여 "주파수" 개념을 도입하고, 이를 통해 그래프 컨볼루션을 정의하고자 하는 것이 Spectral GCN의 출발점입니다.
(2) Laplacian Matrix
이 작업을 위해서는 먼저 Laplacian matrix를 알아야 합니다. 라플라시안.. 개인적으로 저는 전자기학이나 수리물리, 고전역학 등에서 먼저 벡터 미적분으로 배웠던 개념인데요. Graph에서도 라플라시안은 비슷한 맥락에서 생각해볼 수 있습니다. $$ L = D - A $$
라플라시안 operator \(L\)을 신호 \( \mathbf{x} \)에 적용한 결과 \( (L\mathbf{x})_i \)는 노드 \(i\)에서의 신호 값 \(x_i\)와 그 이웃 노드들의 신호 값 \(x_j\)들의 차이(발산)를 반영합니다. (undirected graph라는 전제하에서)
\[ (L\mathbf{x})_i = (D\mathbf{x})_i - (A\mathbf{x})_i = d_i x_i - \sum_{j \in \mathcal{N}(i)} A_{ij} x_j \]
만약 adjacent matrix 가 0 또는 1로 표기된다면 \[ (L\mathbf{x})_i = d_i x_i - \sum_{j \in \mathcal{N}(i)} x_j = \sum_{j \in \mathcal{N}(i)} (x_i - x_j) \] 와 같이 쓸 수 있겠죠.
이 식을 들여다보면, 노드 \(i\)의 신호가 이웃들의 신호들과 얼마나 다른지를 나타내는 값이라고 할 수 있습니다.
만약 \( (L\mathbf{x})_i \approx 0 \)이라면 노드 \(i\)의 신호는 이웃 신호값들의 평균과 유사한 값이라는 뜻이고
\( (L\mathbf{x})_i \)의 절대값이 크다면 이웃 신호값들과 크게 다르다는 것을 나타냅니다. (전기장, 중력장에서 potential함수의 gradient에 divergence가 Laplacian이었는데 potential함수의 값이 급격하게 변하는 곳에서 더 강한 보존력이 작용하지요?)
예를 들어서 3개의 노드가 연결된 그래프를 한번 생각해보면
\( A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \), \( D = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix} \), \( L = D-A = \begin{pmatrix} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \end{pmatrix} \) 이 되는데
신호 \( \mathbf{x} = [x_1, x_2, x_3]^T \)에 대해 \( L\mathbf{x} \)를 계산하면
\[ (L\mathbf{x})_1 = x_1 - x_2 \] \[ (L\mathbf{x})_2 = 2x_2 - x_1 - x_3 = (x_2 - x_1) + (x_2 - x_3) \] \[ (L\mathbf{x})_3 = x_3 - x_2 \] 가 되어 각 노드에서 이웃과의 차이를 반영하는 것을 확인할 수 있습니다.
참고로 Normalized된 꼴의 라플라시안을 쓰기도 합니다(이 경우 고유값(eigenvalue)이 [0,2] 범위로 정규화됩니다).
\[ L_{sym} = I - D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \]
(3) Laplacian Matrix의 고유값분해와 Graph의 Fourier 변환
자 이렇게 graph 신호의 발산을 의미하는 Laplacian matrix를 정의했는데... 이걸 전체적으로 그냥 더한다면 부호가 상쇄되어 의미있는 결과를 끌어내기가 어렵겠죠? Quadratic form에서 생각해봅시다. \[ \mathbf{x}^T L \mathbf{x} = \sum_{(i,j) \in E} w_{ij}(x_i - x_j)^2 \] 위 식의 값이 작을수록 "연결된 node와 유사하다"고 볼 수 있고 다르게 표현하면 식을 최소화하는 극점을 찾아냄으로써 노드 특성이 유사한 집단을 찾아낼 수 있습니다.(즉, 다르게 표현하면 Graph의 smoothness를 나타내는 식이라고 볼 수 있습니다)
\( \mathbf{x}^T L \mathbf{x} \) 를 제약조건 \( \lVert \mathbf{x} \rVert_2=1 \) 하에서 최소화하는 것은
\[ \min_{\mathbf{x} \in \mathbb{R}^N, \lVert \mathbf{x} \rVert_2=1} \mathbf{x}^T L \mathbf{x} \] 와 같이 쓸 수 있으며
정리하면 \[ \frac{\partial \mathcal{L}}{\partial \mathbf{x}} = 2L\mathbf{x} - 2\lambda \mathbf{x} = 0 \]
이 최적화 식의 해는 Laplacian matrix의 eigenvector라는 걸 알 수 있습니다. 작은 값의 eigenvalue(낮은주파수)에 대응하는 eigenvector일수록 graph 전체에 걸쳐 smooth하게 변화하는 패턴을 보이고, 큰 값의 eigenvalue(높은 주파수)에 대응하는 eigenvector일수록 이웃한 노드들 사이에서 급격하게 변하는 패턴을 보입니다(PCA에서도 첫번째 주성분 벡터가 데이터 분포의 분산이 가장 큰 방향을 나타내는 것을 떠올려보시면 좋을 것 같습니다).
이 과정이 graph에서의 Foruier 변환이라고 할 수 있으며 Laplacian의 eigenvector가 Fourier변환의 basis가 됩니다: Graph의 signal을 Frequency별로 분해하는 과정
(4) Spectral GCN 에서 Spatial GCN으로
Graph Theory가 아니더라도 Fourier Transformation과 Convolution은 밀접한 관계가 있습니다.
Convolution Theorem: 시간/공간 영역에서의 컨볼루션은 주파수 영역에서의 곱셈과 같다.
그럼 (Spectral Convolution을 이야기한다면서...? 왜 라플라시안의 고유벡터니 푸리에변환이니 하는거냐 생각하셨을수도 있는데) 지금까지 주저리주저리 설명드린 이유를 알 수 있습니다.
Spectral Convolution을 Fourier 변환 후에 연산하면 단순 "곱셈"으로 할수 있기에 푸리에 변환 후에 convolution을 (수치근사적 방법으로) 연산해볼 수 있습니다. 그런데 이 과정에서 몇 가지 근사와 수치적인 방법론을 적용하고 식을 잘 정리해보면 Spectral convolution의 special case(first-order approximation of localized spectral filters on graph)가 바로 spatial GCN이라는 것입니다. 이 유도 과정은 꽤나 길고 복잡하기에 궁금하신 분들은 위 논문을 찾아보시면 될 것 같습니다.
정리하면 이렇습니다.
초기 GCN 연구는 사실 가장 나중에 소개한 Graph Signal Processing 관점에서 시작되었습니다. 그런데 이 방식은 Laplacian matrix의 eigen decompoision이 필수적이기 때문에 이 과정에서 높은 수준의 연산량이 필요하고 filter가 그래프 구조에 의존적이라 새로운 그래프에 적용하기도 어려운 단점이 있었습니다.
이러한 한계를 극복하고자 학습가능한 필터를 체비셰프(Chebyshev) 다항식으로 근사하여 연산량을 줄이고 몇가지 근사를 적용하였더니(ChebNet; Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering -NeurIPS'16) 우리가 처음 살펴보았던 Spatial Convolution의 형태가 Spectral GCN으로부터 짠하고 유도된다는 것이었습니다.