GCN 이해하기
이번 포스팅에서는 GCN에 관한 내용을 공유해보려고 합니다.
그래프
개념
2가지 구성 요소로 이루어진 데이터 구조로, 방향성이 있거나 없는 Edge로 연결된 Node들의 집합, 데이터 입니다.
그래프 분석 및 적용
ML 대부분(이미지, 텍스트 데이터 기준), 입력 데이터가 유클리드 공간(Euclidean space)에 존재함을 가정합니다.
한 점에서 좌표(x,y,z)까지의 거리 등을 유클리드 공간 데이터(이미지, 시계열 등)의 숨은 패턴을 효율적으로 학습하지만, 그래프는 비유클리드 공간에서 표현되는 데이터로 객체 간의 복잡한 관계와 상호의존성을 표현하며, 방향성이 없고 고정된 형태가 아니기에 해석하기 어렵습니다.
그래프 사용 이유
그럼에도 불구하고 그래프는 관계, 상호작용 등 추상적 개념을 다루기 적합하며, 새로운 관점에서 데이터를 표현할 수 있다는 장점이 있습니다.
그래서 소셜 네트워크, 미디어, 코로나 19 확산, 이동 경로 등 연구 및 모델링에 주로 사용할 수 있습니다.
그래프의 표현
데이터를 2가지 행렬을 이용하여 그래프 데이터로 표현합니다.
아래의 2가지 행렬은 가지고 GCN에 적용시키게 됩니다.
- 인접 행렬 (Adjacency Matrix, A)
- 그래프의 연결관계를 표현한 행렬
- 자기 자신의 노드의 정보를 반영하는 self-loop를 포함(현 그림에서는 self-loop 미포함)
- 그래프에 따라 단순 0,1 이 아닌 실수가 되기도 함
- 예시를 보면 1번 노드는 2와 3번 노드와 연결되어있기 때문에 1로 표현
- 노드 행렬 (Feature Matrix, X 혹은 H)
- 노드들의 특성 정보를 반영하는 행렬
GCN (Graph Convolution Network)
그래프의 이웃한 노드 값들이 반영되기에 Receptive Field와 같은 역할 수행한다고 보며, 한 레이어의 weight는 그래프에 있는 노드 전체에 대해 공유합니다. 이러한 Convolution 특징(혹은 개념)을 도입했기 때문에 GCN이라고 불리게 되었습니다. 즉, GCN은 Convolution 필터의 특징을 그래프에 적용했다고 볼 수 있습니다.
노드 정보 업데이트(학습)
어떻게 2가지 행렬을 합쳐서 Convolution을 수행할 것인가에 대한 내용입니다.
일반적으로, 연결관계와 이웃들의 상태를 이용하여 각 노드의 상태를 업데이트하고 마지막 상태를 통해 예측, 분류 등을 수행합니다.
- 기본 가정은 모든 노드들이 서로 연결되어 있다는 가정하에 진행이 됩니다.
- 즉, 한 레이어의 Weight는 그래프에 있는 노드 전체에 대해 가중치를 공유합니다.
수식
다음과 같이 행렬 곱의 형태로 표현이 가능합니다.
- HW() : 노드의 정보에 가중치까지 곱한 정보를 가진 행렬(단, 모든 노드 연결 가정)
- AHW() : 인접행렬을 곱함으로써, 원래의 그래프 정보까지 포함
모든 노드들을 일일이 업데이트하는 것이 아닌 인접행렬을 활용하여 이웃한 노드들(연결된)의 정보만 받게 됩니다. (+ 설정한 필터값)
Readout
GCN을 거친 후 마지막에 Readout Layer를 통해 최종적으로 Classification 혹은 Value를 Regression 합니다.
이러한 layer를 쓰는 이유는 아래 그림과 같이 그래프 데이터의 노드 간 연결정보가 같아도 노드의 위치나 행렬 표현순서가 바뀔 때, 같은 그래프 형태라도 다르게 표현되기 때문에 MLP를 통해 같은 그래프는 같은 피쳐값을 같게 해줍니다.
전반적인 구조
GCN의 전반적인 구조는 아래와 같습니다.
내용 정리
GCN은 그래프의 형태는 바뀌지 않으면서, 노드 피쳐의 값을 업데이트를 합니다.
노드 간 관계를 정의하고 임베딩하는 과정을 거치기 때문에, convolution 연산에서 인접한 노드간의 관계를 자연스럽게 고려하게 된다.
노드 간 엣지는 인접 행렬(혹은 degree Matrix, Laplacian Matrix)로 표현하며, 해당 인접행렬을 직접적으로 모델에 넣어주게 된다.
추가
그래프라는 이미지, 텍스트와 같이 격자 구조가 아닌 자유로운 형태의 데이터에 대해서 convolution 개념을 도입했다는 점에서 새로운 접근방법이였다고 생각합니다.
또한, T-GCN, ST-GCN 등 시계열 관련 GCN도 연구되고 있으며, 그 외에도 여러 연구가 진행되고 있다는 점에서 주의깊게 봐야할 것 같습니다.
참고 논문 및 자료
- Semi-Supervised Classification With Graph Convolutional Networks
- T-GCN: A Temporal Graph Convolutional Network for Traffic Prediction
- 그림 출처 (전체)