그래프 신경망(GNN)은 그래프 구조 데이터를 처리하도록 설계된 인공 신경망의 한 부류로, 입력이 정규적인 순서가 없는 노드(정점)와 엣지(연결)로 구성된다. 고정된 크기와 순서가 있는 입력을 가정하는 표준 신경망과 달리, GNN은 다양한 크기와 위상을 가진 그래프를 처리하도록 설계되어 분자 화학, 소셜 네트워크 분석, 조합 최적화와 같은 분야에 적합하다. GNN의 핵심 혁신은 쌍별 메시지 전달(pairwise message passing)에 있으며, 각 노드는 이웃으로부터 정보를 집계하여 표현을 반복적으로 갱신함으로써 네트워크가 지역적 구조 패턴과 의존성을 포착할 수 있게 한다.
GNN은 일반적으로 순열 등변성(permutation equivariant)을 갖도록 설계되는데, 이는 입력 그래프의 노드 순서를 바꾸면 네트워크가 생성하는 노드 표현도 그에 따라 재배열된다는 것을 의미한다. 분자 전체의 속성 예측과 같은 그래프 수준 예측 작업의 경우, GNN은 순열 불변성(permutation-invariant) 읽기 함수를 사용하여 노드 표현을 단일 고정 크기 출력으로 집계하며, 이를 통해 결과가 노드 순서에 영향을 받지 않도록 보장한다. 이 속성은 그래프에 자연스러운 노드 순서가 없고, 네트워크 출력이 그래프가 어떻게 표현되든 일관되어야 하기 때문에 필수적이다.
역사적 발전
GNN의 개념은 구조화 데이터를 위한 신경망에 대한 초기 연구에서 비롯되었으며, 기본 아이디어는 1990년대로 거슬러 올라간다. 방향성 비순환 그래프에 적용된 순환 신경망과 같은 초기 접근 방식은 그래프 유사 구조를 처리하는 기반을 마련했다. 그러나 메시지 전달과 순열 등변성에 기반한 현대적 GNN의 공식화는 2010년대 딥러닝의 부상과 함께 두각을 나타냈다. MIT CSAIL과 스탠포드 AI 연구소와 같은 기관의 연구자들은 임의의 그래프를 처리할 수 있는 아키텍처 개발에 기여했으며, 이는 GNN이 머신 러닝 내에서 별개의 하위 분야로 자리 잡는 계기가 되었다.
2010년대 후반까지 GNN은 딥러닝의 표준 도구가 되었으며, 표현력과 확장성을 개선하기 위해 수많은 변형이 제안되었다. 2022년 포지션 페이퍼 "Weisfeiler and Leman Go Neural"과 유사한 연구들은 GNN과 그래프 동형성 테스트 간의 관계를 공식화하여 이론적 한계를 명확히 하고 더 강력한 아키텍처에 대한 연구를 촉진했다.
아키텍처
일반적인 GNN의 아키텍처는 그래프 구조 입력을 처리하기 위해 함께 작동하는 여러 기본 레이어를 구현한다. 이러한 레이어에는 순열 등변성 레이어, 지역 풀링 레이어, 전역 풀링 레이어가 포함되며, 각각은 그래프 표현을 변환하는 데 서로 다른 목적을 수행한다.
순열 등변성 레이어는 GNN의 핵심으로, 그래프 노드 간 쌍별 메시지 전달을 통해 구현된다. 메시지 전달 레이어에서 각 노드는 인접 이웃으로부터 수신한 메시지를 집계하여 표현을 갱신한다. 이 과정은 레이어당 GNN의 수용 영역을 한 홉씩 증가시켜 네트워크가 점진적으로 더 큰 이웃의 정보를 통합할 수 있게 한다. 메시지 전달 연산은 노드 특징, 이웃 특징, 엣지 특징을 입력으로 받아 갱신된 노드 표현을 생성하는 함수로 공식적으로 표현될 수 있다.
지역 풀링 레이어는 다운샘플링을 통해 그래프를 조밀하게 만들어 노드 수를 줄이면서 중요한 구조 정보를 보존한다. 이는 합성곱 신경망(CNN)의 풀링 레이어와 유사하며 GNN의 수용 영역을 늘리는 데 도움이 된다. 일반적인 예로는 k-최근접 이웃 풀링, top-k 풀링, 자기 주의 풀링이 있으며, 각각 다른 기준에 따라 유지할 노드 하위 집합을 선택한다.
전역 풀링 레이어는 읽기 레이어라고도 하며 그래프 전체의 고정 크기 표현을 제공한다. 이러한 레이어는 순열 불변성이어야 하며, 즉 그래프의 노드와 엣지의 어떤 순열도 최종 출력을 변경하지 않아야 한다. 요소별 합, 평균, 최대 연산은 전역 풀링의 일반적인 선택으로, 노드 표현을 그래프 수준 예측에 사용할 수 있는 단일 벡터로 집계한다.
메시지 전달 레이어
메시지 전달 레이어는 GNN을 정의하는 구성 요소로, 메시지 전달 신경망(MPNN)으로 알려진 과정을 통해 순열 등변성 변환을 구현한다. 노드 집합 V와 엣지 집합 E를 가진 그래프 G = (V, E)가 주어지면, V의 각 노드 u는 관련 특징 x_u를 가지며, E의 각 엣지 (u, v)는 특징 e_uv를 가진다. 노드 u의 이웃 N_u는 (u, v)가 E의 엣지인 모든 노드 v로 구성된다.
MPNN 레이어는 메시지 전달 함수를 사용하여 각 노드 u의 표현을 갱신한다. 레이어는 각 이웃 v에서 u로의 메시지를 계산하며, 메시지는 소스 노드 특징, 대상 노드 특징, 엣지 특징의 함수이다. 이러한 메시지는 합, 평균, 최대와 같은 순열 불변 연산을 사용하여 집계된 다음, 일반적으로 신경망인 미분 가능한 갱신 함수를 통해 노드 자체의 특징과 결합된다. 이 과정은 여러 레이어에 걸쳐 반복될 수 있어 정보가 그래프 전체에 전파될 수 있다.
메시지 전달 함수의 설계는 GNN 아키텍처에 따라 다양하다. 일부는 단순한 선형 변환을 사용하는 반면, 다른 일부는 더 복잡한 주의 메커니즘이나 게이트 순환 유닛을 사용한다. 집계 연산의 선택도 네트워크의 표현력과 다양한 유형의 구조 정보를 포착하는 능력에 영향을 미친다.
표현력과 한계
표준 메시지 전달 GNN(Message-Passing GNN)은 두 그래프가 동형인지 판별하는 고전적 알고리즘인 Weisfeiler-Lehman 그래프 동형 테스트보다 더 강력한 표현력을 가질 수 없다. 이는 표준 GNN이 동형이 아닌 그래프에 대해 동일한 표현을 생성할 수 있어, 서로 다른 그래프 구조를 구별하지 못하는 경우가 존재함을 의미한다. 이러한 한계는 메시지 전달의 국소적 특성에서 비롯되며, 이는 인접 이웃으로부터 정보를 집계하는 데 의존하여 전역적 구조 패턴을 포착하지 못할 수 있다.
이러한 한계를 극복하기 위해 연구자들은 단순 복합체(simplicial complex)나 하이퍼그래프(hypergraph)와 같은 고차원 기하 구조에서 작동하는 더 강력한 GNN을 제안했다. 이러한 구조는 쌍별 엣지 너머의 고차 상호작용을 인코딩할 수 있다. 2022년 현재, 미래 아키텍처가 메시지 전달 프리미티브를 완전히 극복할 수 있을지는 여전히 열린 연구 질문으로 남아 있으며, 그래프 트랜스포머와 등변 신경망(equivariant neural network)과 같은 대안적 패러다임을 탐구하는 지속적인 작업이 진행 중이다.
응용 분야
GNN은 그래프 구조 데이터를 처리하는 능력을 활용하여 다양한 분야에서 응용되고 있다. 분자 생물학과 화학에서 분자는 원자를 노드로, 화학 결합을 엣지로 하는 그래프로 표현되며, 종종 알려진 화학적 특성을 특징으로 포함한다. 그래프 수준 작업에는 특정 의학적 응용(예: 대장균 제거)을 위한 분자의 효능 예측이나 용해도 및 독성과 같은 물리적·화학적 특성 추정이 포함된다.这使得 GNN은 약물 설계와 재료 과학에서 중요한 도구가 된다.
자연어 처리에서 GNN은 구문 의존 트리나 의미 역할 그래프에 적용되어 문장 내 단어 간 관계를 포착할 수 있다. 또한 소셜 네트워크 분석에서 사용자 상호작용을 모델링하고, 커뮤니티를 탐지하며, 링크를 예측하는 데 사용된다. 노드가 논문을 나타내고 엣지가 인용을 나타내는 인용 네트워크는 또 다른 일반적인 응용 분야로, 논문 분류 및 추천과 같은 작업을 가능하게 한다.
GNN은 입자 상호작용을 모델링하거나 동적 시스템을 시뮬레이션할 수 있는 물리학, 그리고 그래프 색칠이나 외판원 문제와 같은 작업에 대한 휴리스틱을 학습할 수 있는 NP-난해 조합 최적화 문제에도 관련이 있다. GNN의 다재다능함은 학술 연구와 산업 응용 모두에서 채택으로 이어졌다.
다른 신경망 아키텍처와의 관계
기하학적 딥러닝의 더 넓은 맥락에서, 특정 기존 신경망 아키텍처는 적절히 정의된 그래프에서 작동하는 GNN으로 해석될 수 있다. 컴퓨터 비전에서 일반적으로 사용되는 합성곱 신경망(CNN) 레이어는 노드가 픽셀이고 엣지가 인접 픽셀만 연결하는 그래프에 적용된 GNN으로 간주될 수 있다. 이러한 관점은 CNN과 GNN 간의 국소 연결성과 특징 집계의 공유 원리를 강조한다.
유사하게, 자연어 처리와 대규모 언어 모델에서 널리 사용되는 트랜스포머 레이어는 노드가 텍스트 구절의 단어 또는 토큰인 완전 그래프에 적용된 GNN으로 볼 수 있다. 이 해석에서 트랜스포머의 어텐션 메커니즘은 각 토큰이 다른 모든 토큰으로부터 정보를 집계하는 메시지 전달의 한 형태로 작동한다. 이러한 연결은 이러한 아키텍처를 통합하고 GNN의 통찰력을 트랜스포머 기반 모델 개선에 적용하는 연구에 영감을 주었다.
소프트웨어 라이브러리 및 도구
GNN의 구현과 배포를 용이하게 하기 위해 여러 오픈소스 라이브러리가 개발되었다. PyTorch 프레임워크 기반의 PyTorch Geometric은 그래프 데이터 처리와 메시지 전달 레이어를 위한 포괄적인 도구 세트를 제공한다. TensorFlow GNN은 TensorFlow 생태계 내에서 유사한 기능을 제공한다. Deep Graph Library(DGL)는 PyTorch, TensorFlow, Apache MXNet을 포함한 여러 백엔드를 지원하는 프레임워크 비종속 라이브러리이다. Google JAX 사용자를 위해 jraph는 그래프 신경망을 위한 경량 라이브러리를 제공한다. Julia 프로그래밍 언어에서는 GraphNeuralNetworks.jl과 GeometricFlux.jl이 Flux 머신러닝 프레임워크 기반의 GNN 구현을 제공한다.
이러한 라이브러리는 연구자와 실무자에게 진입 장벽을 낮추어 다양한 GNN 아키텍처의 빠른 프로토타이핑과 실험을 가능하게 한다. 여기에는 표준 메시지 전달 레이어, 풀링 연산, 그래프 데이터셋 로드 및 처리를 위한 유틸리티 구현이 포함되어 GNN을 광범위한 사용자에게 접근 가능하게 만든다.
미래 방향
GNN에 대한 연구는 계속 진화하고 있으며, 표현력 향상, 대규모 그래프로의 확장성, 노이즈가 있거나 불완전한 데이터에 대한 견고성과 같은 활발한 연구 영역이 포함된다. 어텐션 메커니즘과 그래프 구조를 결합한 그래프 트랜스포머의 개발은 장거리 의존성을 포착하기 위한 유망한 방향을 나타낸다. 또한 노드와 엣지가 시간에 따라 변하는 동적 그래프와 여러 유형의 노드와 엣지를 가진 이종 그래프에 GNN을 적용하는 데 대한 관심이 증가하고 있다.
2020년대 초반 현재, GNN은 머신러닝 도구 키트의 표준 구성 요소가 되었으며, 학술 기관과 산업 연구소의 지속적인 기여가 이루어지고 있다. 그들의 능력과 한계에 대한 이론적 이해는 계속 심화되어, 점점 더 복잡한 그래프 기반 문제를 해결할 수 있는 차세대 아키텍처 설계를 안내하고 있다.