[그래프 AI]Graph Neural Network(GNN)

그래프(Graph)

그래프를 분석하기 어려운 이유

그래프는 정점(Node, Vertex) 간선(Edge)으로 이루어진 자료 구조이다. 간선의 방향성 유무에 따라 방향성 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 구분된다. 특히 인접, 차수 등의 용어는 그래프의 특성을 나타내는데 중요하다. 일반적인 그래프는 모든 연결성을 보여주는 행렬을 인접 행렬(Adjacent Matrix)이라고 한다. 인접 행렬을 통해 정점과 정점 사이의 연결 유무를 쉽게 판단할 수 있다.

그래프를 분석하기 어려운 이유 중 첫번째는, 그래프는 유클리드 공간에 있지 않다. 즉, 좌표평면 상에 그래프의 모든 정보를 표시하는 것은 거의 불가능하다. 이와 달리, 주가 예측을 위한 시계열 데이터나, 음성, 이미지 같은 데이터는 2차워, 3차원 유클리드 공간에 쉽게 맵핑할 수 있다. 따라서 일반적인 해석 방식으로 그래프를 분석하기에는 무리가 있다.

둘째, 그래프는 고정된 형태가 아니다. 그래프를 시각화 했을때, 서로 다른 것처럼 보이지만 실제로는 동일한 경우가 존재한다. 다시 말해, 두 그래프가 본질적으로 동일한 구조를 가지는 경우가 존재하며 이러한 경우를 그래프 동형(Graph Isomorphism)이라고 한다. 위의 그림과 같이, 서로 달라보이지만 각 정점의 연결관계를 따져봤을 때 두 그래프는 동일한 것을 알 수 있다.

셋째, 그래프의 분석을 위해 시각화하는 것은 어렵다. 예를 들어, 초거대 지식 그래프(Large-Scale Knowledge Graph)의 밴치마크인 Wikidata5M의 경우 정점의 수가 5백만 개에 달한다. 이를 2차원 혹은 3차원 공간에 맵핑하여 적절하게 분류하는 것은 거의 불가능에 가깝다.

그래프를 사용하는 이유

그럼에도 불구하고 여러 머신러닝/딥러닝 문제를 해결하는데 그래프를 사용하는 이유는 바로 관계, 상호작용과 같은 추상적인 개념을 다루기에 적합하다. 그래프는 어떤 두 개체 간의 상호작용을 정점과 간선으로 표현할 수 있으며, 이들의 상호작용이 무엇인지 간선에 레이블링을 함으로써 효과적으로 표현할 수 있다.

기존의 그래프 분석 방법은 주로 알고리즘에 기반하였다.

• 검색 알고리즘(BFS, DFS)
• 최단 경로 알고리즘(Dijkstra 알고리즘, A*알고리즘)
• 신장 트리 알고리즘(Prim 알고리즘, Kruskal 알고리즘)
• 클러스터링 방법(연결 성분, 클러스터링 계수)

이런 알고리즘의 한계는 알고리즘을 적용하기 전에 입력 그래프에 대한 사전 지식이 필요하다는 점이다. 그렇기 때문에 그래프 자체를 연구하는 것이 불가능하고, 그래프 단위에서의 예측이 불가능하다. 그래프 단위라는 것은 쉽게 말해 단백질 구조 그래프와 같이 여러 가지의 그래프를 비교하는 것을 말한다.

Graph Neural Network(GNN)

1. GNN의 개요

그래프 신경망(GNN, Graph Neural Network, GNN)은 그래프 구조 데이터를 처리하고 분석하는 데 특화되어있다. GNN은 정점(=노드)와 간선(=엣지)으로 구성된 그래프 데이터를 입력받아 정점의 특성이나 그래프 전체의 특성을 학습한다. GNN의 기본 아이디어는 각 정점이 이웃 정점으로부터 정보를 받아 자신의 정보(정점의 특징, 속성)를 업데이트하는 것이다. 이를 통해 GNN은 그래프의 구조적 패턴을 학습하고, 정점 간의 복잡한 관계를 이해할 수 있다. 이 과정은 여러 계층을 통해 반복되며, 각 계층에서는 정점의 임베딩(embedding)을 점진적으로 업데이트한다.

GNN은 소셜 네트워크 분석, 화합물 구조 예측, 추천 시스템, 자연어 처리 등 다양한 분야에서 활용된다. 그래프 데이터를 효율적으로 처리할 수 있어 복잡한 데이터 간의 관계를 분석하고 예측하는 데 강력한 도구가 된다. 참고로 GNN은 하나의 모델이 아닌, 하나의 방법론이다.

GNN을 통해 풀 수 있는 문제는 크게 세 Level로 나뉘어진다. 먼저 Graph-level에서는 그래프 임베딩(Graph Embedding)과 그래프 생성(Graph Generation)이 있다. 그래프 임베딩은 그래프 전체를 고정된 크기의 벡터로 표현하는 과정이다. 예를 들어, 화합물의 구조를 벡터로 변환하여 분자 특성을 예측하는 데 사용된다. 그래프 생성은 새로운 그래프 구조를 생성하는 과정이다. 예를 들어, 신약 개발에서 새로운 화합물 구조를 생성하여 잠재적인 약물 후보를 찾는 데 사용된다.

다음으로는, Node-level이다. 노드 레벨의 문제는 노드 임베딩(Node Embedding)과 노드 분류(Node Classification)이 있다. 노드 임베딩은 각 정점을 고정된 크기의 벡터로 표현하는 과정이다. 예를 들어, 소셜 네트워크에서 각 사용자를 벡터로 변환하여 사용자의 속성이나 관계를 분석하는 데 사용된다. 노드 분류는 정점의 속성을 기반으로 정점을 특정 클래스에 할당하는 작업이다. 예를 들어, 네트워크 내에서 스팸 계정과 정상 계정을 분류하는 데 사용된다.

마지막은 Edge-level이다. 엣지 레벨의 문제는 링크 예측(Link Prediction)이 있다. 링크 예측은 그래프 내에서 두 정점 간의 연결 가능성을 예측하는 작업이다. 예를 들어, 소셜 네트워크에서 두 사용자가 친구가 될 가능성을 예측하는 데 사용된다. 링크 예측은 아주 중요한 문제이다. 지식 그래프(Knowledge Graph)에서는 이 링크 예측과 유사한 문제로 지식 그래프 완성(Knowledge Graph Completion)이 있으며, 이 두 문제는 다중 홉 추론(Multi-hop reasoning)으로 확장될 수 있다. 결론적으로, 지식 그래프 완성이나 링크 예측은 질의 응답(QA) 시스템으로 확장될 수 있다. 다중 홉 추론을 통해 복잡한 질문에 대한 답을 찾고, 서로 관련된 정보를 연결하여 보다 정확한 답변을 제공할 수 있다.

2. GNN 연구의 동향

GNN은 크게 세 가지 방향으로 연구가 진행되고 있다.

• Recurrent Graph Neural Network
• Spatial Convolutional Network
• Spectral Convolutional Network

1) Recurrent Graph Neural Network Recurrent Graph Neural Network (RGNN)는 순환 신경망(RNN)의 개념을 그래프 데이터에 적용한 모델이다. RGNN에서는 그래프의 각 정점이 시간의 흐름에 따라 순차적으로 업데이트되며, 각 정점의 상태는 이웃 정점과 자신의 이전 상태를 결합하여 반복적으로 갱신된다. 예를 들어 Graph Recurrent Neural Network (GRNN)은 노드 상태가 반복적으로 업데이트되며, 상태 갱신 함수로 RNN을 사용한다. Gated Graph Neural Network (GGNN)은 GRNN의 변형으로, GRU(Gated Recurrent Unit) 구조를 사용하여 노드 상태를 업데이트한다.

2) Spatial Convolutional Network Spatial Convolutional Network는 그래프 구조를 직접 활용하여 이웃 정점의 정보를 집계하고 이를 통해 정점 상태를 업데이트하는 모델이다. Spatial 방법은 계산 효율성이 높고, 다양한 크기의 그래프에 쉽게 적용할 수 있다는 장점이 있다. 예를 들어 GraphSAGE는 이웃 정점의 특징을 집계하여 노드 임베딩을 업데이트하는 모델이다. Graph Attention Network (GAT)는 노드 간의 중요도를 학습하여 가중치를 부여하고, 이를 통해 노드 상태를 업데이트한다.

3) Spectral Convolutional Network Spectral Convolutional Network는 그래프의 라플라시안(Laplacian) 행렬의 고유벡터를 이용해 그래프 컨볼루션을 정의하는 모델이다. Spectral 방법은 계산 복잡도가 높고, 다른 크기의 그래프에 일반화하기 어렵다는 단점이 있다. 예를 들어 Graph Convolutional Network (GCN)은 라플라시안 행렬을 사용하여 노드 상태를 업데이트하는 대표적인 모델이다. ChebNet은 라플라시안 행렬의 다항식 근사를 사용하여 계산 효율성을 개선한 모델이다. 노드 \(v\)의 상태 업데이트 수식은 다음과 같다:

$$H^{(t+1)} = \sigma \left( \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(t)} W^{(t)} \right)$$

여기서 \(\tilde{A} = A + I\)는 정규화된 인접 행렬, \(\tilde{D}\)는 \(\tilde{A}\)의 대각 행렬, \(H\)는 노드 특성 행렬, \(W\)는 학습 가능한 가중치 행렬을 나타낸다.

이 세 가지 유형의 Graph Neural Network는 각각의 특성과 응용 사례가 다르며, 다양한 그래프 기반 문제를 해결하는 데 사용된다. Recurrent Graph Neural Network는 순차적 데이터와의 상호작용이 많은 그래프에, Spatial Convolutional Network는 효율적인 계산이 요구되는 다양한 크기의 그래프에, 그리고 Spectral Convolutional Network는 라플라시안 행렬의 고유벡터를 활용한 그래프 컨볼루션을 필요로 하는 경우에 적합하다.

다음 포스팅에서는 Graph Convolution Network(GCN)에 대해서 다뤄보도록 하겠다.

Graph 카테고리 내 다른 글 보러가기