그래프 머신 러닝 소개

Graph Machine Learning (GraphML) 은 관계로 연결된 항목으로 구조화된 데이터를 분석할 수 있게 하며, 그래프, 노드, 엣지, 서브그래프 수준에서 예측을 가능하게 합니다. 이 분야는 신약 개발 및 분자 독성 예측부터 소셜 네트워크 커뮤니티 탐지, 일정 시스템의 교통량 추정에 이르는 다양한 응용 분야에 필수적입니다.

기본 그래프 개념

그래프는 노드(또는 정점)와 엣지(또는 링크)로 구성됩니다. 데이터의 특성에 따라 그래프는 여러 특성으로 구분됩니다:

동질 그래프 vs. 이질 그래프: 동질 그래프는 단일 유형의 노드와 엣지를 포함합니다. 이질 그래프는 유형이 지정된 노드 또는 엣지를 가지고(예: 저자와 논문이 모두 포함된 인용 네트워크) 토폴로지 외에 추가 정보를 필요로 합니다.
방향성 그래프 vs. 무방향 그래프: 방향성 그래프(예: 팔로워 네트워크)는 특정 방향을 가진 엣지를 가지고, 무방향 그래프(예: 분자)는 양방향 관계를 가집니다.
표현 방식: 그래프는 일반적으로 엣지 집합이나 인접 행렬로 표현되며, 인접 행렬은 두 노드 사이에 연결이 있으면 1 값을 갖는 정방 행렬입니다.

핵심적으로, 그래프는 순서가 있는 객체가 아니기 때문에 시퀀스(텍스트/오디오)나 격자(이미지)와 다릅니다. 엣지 리스트나 인접 행렬의 열을 섞어도 기본 그래프는 변하지 않으며, 이를 순열 불변성이라고 합니다.

그래프 학습 과제

그래프에 대한 머신 러닝은 네 가지 주요 수준에서 적용됩니다:

그래프 수준: 그래프 생성(예: 신약 개발), 그래프 진화 예측(예: 물리학) 및 그래프 수준 예측(예: 분자 독성 예측)을 포함합니다.
노드 수준: 노드 속성 예측에 초점을 맞추며, 예를 들어 AlphaFold가 노드 속성을 사용해 분자 내 원자의 3D 좌표를 예측합니다.
엣지 수준: 엣지 속성 예측(예: 약물 부작용 예측) 또는 누락된 엣지 예측(예: 추천 시스템)을 포함합니다.
서브그래프 수준: 소셜 네트워크에서 커뮤니티 탐지 또는 Google Maps와 같은 시스템에서 도착 시간 추정을 위한 서브그래프 속성 예측에 초점을 맞춥니다.

이러한 과제는 전이학습(transductive) 설정(단일 그래프에서 학습 및 테스트) 또는 귀납학습(inductive) 설정(학습, 검증, 테스트를 위해 별도의 그래프를 사용하는) 중 하나로 수행됩니다.

그래프 표현의 진화

신경망 이전 접근법

신경망이 등장하기 전, 그래프 표현은 설계된 특징에 의존했습니다:

노드 수준 특징: 중심성(중요도), 차수(이웃 수), 클러스터링 계수(이웃 연결성).
엣지 수준 특징: 노드 간 최단 거리, 공통 이웃, Katz 지수(특정 길이까지의 경로 수).
그래프 수준 특징: 전체 그래프릿 카운트와 “노드 가방” 접근법을 통한 유사도 측정 커널 방법.

워크 기반 접근법(예: Node2Vec)은 랜덤 워크를 사용해 유사도 메트릭을 정의하고 스킵그램 모델을 통해 임베딩을 계산합니다. 그러나 이러한 방법은 새로운 노드에 대한 임베딩을 생성할 수 없으며, 세밀한 구조적 유사성을 포착하거나 추가 노드 특징을 활용하지 못합니다.

그래프 신경망 (GNNs)

보지 못한 데이터에 일반화하기 위해, GNN은 순열 불변성(노드 순서와 무관하게 출력이 동일) 및 순열 동등성(노드를 순열하면 해당 표현도 동일하게 순열)으로 설계됩니다.

GNN 레이어는 메시지 전달과 집계를 통해 작동합니다: 노드의 표현은 이전 레이어에서 이웃 및 자신 자체의 표현을 집계함으로써 업데이트됩니다.

주요 GNN 아키텍처에는 다음이 포함됩니다:

그래프 컨볼루션 네트워크 (GCNs): 이웃의 정규화된 표현을 평균합니다.
그래프 어텐션 네트워크 (GATs): 중요도에 따라 이웃에 가중치를 부여하는 어텐션 메커니즘을 사용합니다.
GraphSAGE: 다양한 홉에서 이웃을 샘플링하고 최대 풀링을 사용해 정보를 집계합니다.
그래프 동형성 네트워크 (GINs): 이웃 표현의 합에 MLP를 적용합니다.

과도 평활화 문제

GNN에 레이어를 추가하면 각 노드의 표현은 더 넓은 반경의 정보를 집계합니다. 레이어 수가 그래프의 지름을 초과하면 노드 표현이 동일한 값으로 수렴할 수 있으며, 이를 과도 평활화(oversmoothing) 라고 합니다. 이는 레이어 깊이를 제한하거나, 레이어 복잡성을 높이거나, 비-메시지 전달 레이어(예: MLP)를 추가하거나, 스킵 연결을 구현함으로써 완화됩니다.

그래프 트랜스포머

트랜스포머는 본질적으로 순열 불변성을 가지고 효율적으로 확장되기 때문에, 과도 평활화와 밀집 그래프 확장과 같은 GNN의 한계를 극복하기 위해 그래프에 적용되고 있습니다. 주요 발전 사항은 다음과 같습니다:

Graphormer: 노드 특징을 어텐션의 query/key/value로 사용하고 중심성, 공간 및 엣지 인코딩을 통합합니다.
TokenGT: 그래프를 식별자가 추가된 노드 및 엣지 임베딩 시퀀스로 표현하여 위치 임베딩이 필요 없게 합니다.
GraphGPS: 메시지 전달 네트워크와 선형 장거리 트랜스포머를 결합한 하이브리드 네트워크 프레임워크입니다.
스펙트럴 어텐션 네트워크 (SANs): 라플라시안 고유벡터/값에서 파생된 학습된 위치 인코딩과 노드 특징을 결합합니다.

그 외 주목할 만한 방법으로는 그래프-시퀀스 학습을 위한 Graph Encoder와 GRPE(그래프 상대 위치 인코딩) 트랜스포머가 있습니다.