[논문 요악 4일차] Graph neural networks: A review of methods and applications (1)

논문요약

[논문 요악 4일차] Graph neural networks: A review of methods and applications (1)

wony-wony 2024. 10. 2. 15:26

1. Introduction

그래프는 객체(노드)와 그 관계(엣지)를 모델링하는 데이터 구조로, 최근 다양한 분야에서 그래프 데이터를 머신러닝으로 분석하는 연구가 활발히 진행되고 있다. 그래프의 표현력은 매우 뛰어나서 소셜 네트워크, 물리 시스템, 단백질 상호작용 네트워크, 지식 그래프 등 다양한 분야에서 활용되고 있다. 머신러닝에서는 주로 노드 분류, 링크 예측, 클러스터링 등의 과제가 다뤄진다.

그래프 신경망(GNN)은 그래프 상의 의존성을 캡처하여 노드 간의 정보를 교환하는 딥러닝 기반의 모델이다. GNN은 최근 몇 년간 뛰어난 성능을 보여주었으며, 특히 그래프 합성곱 네트워크(GCN), 그래프 어텐션 네트워크(GAT), 그래프 순환 네트워크(GRN) 등의 변형 모델이 많은 연구 과제에서 성과를 거두고 있다.

GNN의 첫 번째 동기는 1990년대의 그래프를 위한 신경망 역사에 기반한다. 초기에는 순환 신경망과 Feedforward 신경망이 사용되었으나, 확장성과 표현력에 한계가 있었다. 최근 합성곱 신경망(CNN)의 발전과 함께 GNN이 다시 주목받게 되었으며, CNN의 핵심 개념인 로컬 연결(local connection), 가중치 공유(shared weights), 다중 레이어 사용(use of multiple layers)이 그래프 문제를 해결하는 데에도 중요한 역할을 한다.

또한, GNN은 그래프 임베딩을 활용하여 노드나 엣지, 서브그래프를 저차원 벡터로 표현하는 능력을 가지고 있으며, 이를 통해 기존 머신러닝의 한계를 극복하고 더욱 유연하고 효율적인 그래프 분석이 가능해졌다.

따라서 GNN은 다양한 그래프 구조를 모델링하는 데 사용되며, 최근에는 그래프의 유형에 맞는 다양한 변형 모델들이 개발되고 있다.

2. General design pipeline of GNNs (GNN 설계 일반 파이프라인)

GNN 모델을 설계하는 과정은 기본적으로 네 가지 주요 단계로 이루어진다.

2-1. Find graph structure (그래프 구조 찾기)

먼저, 사용될 그래프 구조를 파악해야 한다. 이는 두 가지 경우로 나뉜다:

구조적 시나리오 (Structural scenarios): 여기서 그래프 구조는 명확하게 주어진다. 예를 들어, 분자 구조, 물리 시스템, 지식 그래프 등은 이미 그래프 구조로 표현된다.
비구조적 시나리오 (Non-structural scenarios): 이 경우 그래프 구조가 명시적으로 주어지지 않으며, 먼저 그래프를 만들어야 한다. 예를 들어, 텍스트에서 단어 간 관계를 기반으로 그래프를 만들거나, 이미지에서 장면 그래프(scene graph)를 생성하는 방식이다. 이 과정을 통해 적절한 그래프 구조를 얻은 후, 그 그래프에 맞는 GNN 모델을 설계한다.

2-2. Specify graph type and scale (그래프 유형 및 규모 지정)

그래프를 정의한 후에는 그 그래프의 유형과 규모를 결정해야 한다. 주요 그래프 유형은 다음과 같다:

방향성/비방향성 그래프 (Directed/Undirected Graphs): 방향성 그래프는 노드 간의 연결 방향이 있는 반면, 비방향성 그래프는 방향성이 없다. 비방향성 그래프는 하나의 엣지를 양방향 엣지로 볼 수 있다.
동질/이질 그래프 (Homogeneous/Heterogeneous Graphs): 동질 그래프는 모든 노드와 엣지가 같은 유형을 가지지만, 이질 그래프에서는 노드와 엣지가 서로 다른 유형을 가진다. 이질 그래프에서는 이러한 유형 정보를 모델에서 고려해야 한다.
정적/동적 그래프 (Static/Dynamic Graphs): 정적 그래프는 시간이 지나도 노드나 엣지의 변화가 없지만, 동적 그래프는 시간이 지남에 따라 노드, 엣지 또는 그 특성이 변화한다.

또한, 그래프의 규모를 평가해야 한다. 특정 크기 이상으로 커지면 메모리나 계산 복잡도 문제가 발생할 수 있으므로, 큰 그래프에서는 샘플링 기법을 도입하는 것이 필요하다.

2-3. Design loss function (손실 함수 설계)

그래프 학습 작업의 목표와 훈련 설정에 따라 손실 함수를 설계해야 한다. 주요 작업은 다음과 같다:

노드 수준 작업 (Node-level tasks): 노드 분류, 노드 회귀, 노드 클러스터링 등이 있다. 예를 들어, 노드 분류는 주어진 노드를 여러 클래스 중 하나로 분류하는 작업이다.
엣지 수준 작업 (Edge-level tasks): 엣지 분류 및 링크 예측 작업이 있다. 예를 들어, 두 노드 간의 엣지가 존재하는지 또는 엣지 유형을 예측한다.
그래프 수준 작업 (Graph-level tasks): 그래프 전체를 분류하거나 회귀 작업을 수행하며, 그래프 간의 유사성을 측정하는 작업도 포함된다.

훈련 설정에 따라 작업을 세 가지로 나눌 수 있다:

지도 학습 (Supervised learning): 모든 학습 데이터에 레이블이 있는 경우이다.
준지도 학습 (Semi-supervised learning): 일부 레이블이 있는 노드와 많은 양의 레이블 없는 노드가 제공된다. 모델은 주어진 레이블 없는 노드에 대해 추론하거나, 새로운 노드에 대해 일반화할 수 있어야 한다.
비지도 학습 (Unsupervised learning): 레이블 없이 패턴을 찾는 작업이다. 노드 클러스터링이 대표적인 비지도 학습 과제이다.

2-4. Build model using computational modules (계산 모듈을 사용한 모델 구축)

마지막으로, 계산 모듈을 사용하여 GNN 모델을 구축한다. 주요 모듈은 다음과 같다:

전파 모듈 (Propagation Module): 노드 간 정보를 전파해 이웃 노드의 정보를 수집한다. 합성곱 연산자(convolution operator)와 순환 연산자(recurrent operator)가 자주 사용되며, 스킵 연결(skip connection)은 과도한 smoothing을 방지하는 데 도움이 된다.
샘플링 모듈 (Sampling Module): 대규모 그래프의 경우 이웃 노드들에 대해 샘플링하여 계산을 효율적으로 만든다.
풀링 모듈 (Pooling Module): 그래프나 서브그래프의 고수준 표현을 학습할 때 사용된다. 풀링 모듈은 노드 수준에서 더 추상적인 표현을 얻도록 도와준다.

일반적으로 GNN 모델은 이러한 모듈들을 결합하여 구성되며, 이를 통해 다양한 그래프 작업을 처리할 수 있다.

3. Instantiations of computational modules (계산 모듈의 구체적 구현)

이 섹션에서는 GNN 모델에서 사용되는 세 가지 주요 계산 모듈인 전파 모듈(Propagation modules), 샘플링 모듈(Sampling modules), 풀링 모듈(Pooling modules)에 대해 설명하고, 이들의 구체적 구현에 대해 다룬다.

3.1. 전파 모듈 (Propagation modules)

전파 모듈은 노드 간의 정보를 전파하여 이웃 노드의 특징과 그래프의 구조적 정보를 통합하는 역할을 한다. 주로 합성곱 연산자(convolution operator)와 순환 연산자(recurrent operator)를 통해 구현된다. 전파 모듈의 세부적인 구현은 다음과 같다.

3.1.1. Spectral approaches (스펙트럴 방법)

스펙트럴 방법은 그래프의 스펙트럼 표현을 사용해 합성곱 연산을 정의한다. 이 방법은 그래프 신호 처리를 기반으로 하며, 주로 그래프 푸리에 변환을 통해 그래프 신호를 변환한 후, 합성곱을 수행하고 다시 역변환을 적용한다. 주요 스펙트럴 방법은 다음과 같다:

ChebNet: Chebyshev 다항식을 사용해 합성곱 필터를 효율적으로 계산한다. 이는 그래프 라플라시안의 고유값 분해를 피하면서도 스펙트럴 방법을 빠르게 수행할 수 있도록 돕는다.
GCN (Graph Convolutional Network): GCN은 ChebNet의 K=1 버전으로, 과적합 문제를 해결하기 위해 더 단순한 합성곱 연산을 사용한다.
AGCN (Adaptive Graph Convolutional Network): AGCN은 기본 그래프 라플라시안에 '잔여(residual)' 그래프 라플라시안을 학습해 추가하여, 노드 간 숨겨진 관계를 모델링한다.

3.1.2. Spatial approaches (공간적 방법)

공간적 방법은 그래프의 이웃 구조를 직접 사용해 합성곱을 정의한다. 이 방법은 스펙트럴 방법과 달리 그래프 라플라시안의 고유값을 계산하지 않으며, 노드의 지역적 정보를 활용한다. 주요 공간적 방법은 다음과 같다:

Neural FPs: 노드의 차수에 따라 다른 가중치 행렬을 사용하는 방법이다.
GraphSAGE: 이웃 노드를 고정된 크기로 샘플링하여 정보를 집계하는 방법으로, 평균, LSTM, 풀링 집계자(aggregator)를 제공한다.
GAT (Graph Attention Network): GAT는 노드 간 주의(attention) 메커니즘을 적용해 이웃 노드에서 중요도가 높은 정보를 더 많이 반영한다.

3.1.3. Attention-based approaches (어텐션 기반 방법)

GAT와 같은 어텐션 기반 방법은 각 이웃 노드에 가중치를 달리하여, 노이즈를 줄이고 중요한 정보를 더 많이 반영한다. 대표적으로 GAT (Graph Attention Network)와 GaAN (Gated Attention Network)이 있다.

3.1.4. General frameworks for spatial approaches (공간적 방법을 위한 일반 프레임워크)

여러 공간적 방법을 통합하는 일반적인 프레임워크가 제안되었다. 예를 들어:

MPNN (Message Passing Neural Network): 메세지 전달(message passing)을 통해 노드 간 정보를 교환하는 방식으로, 여러 그래프 신경망 모델을 통합하는 프레임워크이다.
NLNN (Non-local Neural Network): 전통적인 '자기 주의(self-attention)' 메커니즘을 확장해 그래프에서도 사용할 수 있도록 설계되었다.

3.2. Recurrent operator (순환 연산자)

순환 연산자는 주로 순환 신경망(RNN)과 유사한 방식으로 작동하며, 그래프 구조에서 노드 간 정보를 반복적으로 업데이트한다. 대표적인 방법은 GNN (Graph Neural Network)과 GGNN (Gated Graph Neural Network)이 있으며, 후자는 GRU (Gated Recurrent Unit)를 사용해 학습을 효율적으로 만든다.

3.3. Skip connection (스킵 연결)

스킵 연결은 GNN 모델이 깊어질수록 발생할 수 있는 정보 손실이나 과적합 문제를 해결하기 위해 도입되었다. 대표적인 예로 Highway GCN과 Jump Knowledge Network (JKN), DeepGCN이 있으며, 이들은 각 레이어의 출력을 이전 레이어의 출력과 결합하여 정보 흐름을 개선한다.

3.4. 샘플링 모듈 (Sampling modules)

대규모 그래프에서 노드 수가 많아지면 이웃 노드의 정보 수집이 기하급수적으로 증가할 수 있다. 이를 해결하기 위해 샘플링 모듈을 사용해 이웃 노드의 일부만 선택하여 정보를 집계한다.

Node sampling (노드 샘플링): GraphSAGE처럼 각 노드의 이웃 중 일부만 샘플링해 정보를 집계한다.
Layer sampling (레이어 샘플링): FastGCN과 같은 방법은 각 레이어에서 수용 영역(receptive field)을 샘플링한다.
Subgraph sampling (서브그래프 샘플링): ClusterGCN처럼 서브그래프를 샘플링하여 계산 효율을 높인다.

3.5. 풀링 모듈 (Pooling modules)

풀링 모듈은 복잡한 그래프 구조에서 고수준의 그래프 표현을 얻기 위해 사용된다. 주로 다음과 같은 방법들이 있다:

Direct pooling (직접 풀링): 노드의 특징을 직접적으로 요약하여 그래프 전체의 표현을 얻는 방법이다. MPNN에서 사용된 Set2Set이나 SortPooling이 있다.
Hierarchical pooling (계층적 풀링): 그래프의 계층 구조를 활용해 서브그래프 단위로 풀링하는 방법이다. 대표적으로 DiffPool과 SAGPool이 있다. DiffPool은 학습된 할당 행렬을 사용해 노드를 클러스터링하고, SAGPool은 노드의 특징과 구조를 함께 고려한다.