이 글은 Shanon Hong의 An Introduction to Graph Neural Network(GNN) For Analysing Structured Data를 저자에게 허락받고 번역, 각색한 글이다.
Image from Manuchi, via pixabay (CC0).
Graph Neural Network(GNN)은 그래프 데이터를 직접 분석할 수 있어서 최근에 많은 관심을 받고 있다. 이번 글에서는 쉬우면서도 너무 쉽진 않게, 자세하면서도 너무 자세하진 않게, 넓으면서도 너무 넓진 않게 GNN에 대해 소개해보겠다. 그래프에 대한 이해를 돕기 위해 약간의 그래프 이론과 GNN 없이 기존 방법으로 그래프를 분석할 때 한계로 시작할 것이다. 그리고 GNN의 여러가지 형태와 그 원리를 살펴본다. 마지막으로 GNN으로 할 수 있는 것들과 실제로 어떻게 활용될 수 있는지를 다룬다.
그래프
그래프의 정의 및 표현 방법
먼저, 그래프가 무엇인지 알아보자. 그래프는 점들과 그 점들을 잇는 선으로 이루어진 데이터 구조이다. 관계나 상호작용을 나타내는 데이터를 분석할 때 주로 쓰인다. 대표적인 예로는 페이스북 친구관계, 왓챠플레이(유튜브, 넷플릭스) 유저-영상 감상여부 등이 있다.
Graph of Social Network. Image from GDJ, via Pixabay.
일반적으로 그래프는 G=(V,E)로 정의하며 여기서 V는 점 집합이고 E는 두 점을 잇는 선 집합이다. 아래 그래프는 G=({1,2,3},{{1,2},{2,3},{1,3}})으로 정의할 수 있다.
A simple graph. Figure by the original author.
그래프는 주로 인접행렬(adjacency matrix)로 표현된다. 점의 개수가 n개일 때 인접행렬의 크기는 n×n이다. 머신러닝에서 그래프를 다룰 땐 점들의 특징을 묘사한 feature matrix로 표현하기도 하는데 feature의 개수가 f 일 때 feature matrix의 차원은 n×f 이다. 관련된 예는 뒤에 다시 등장한다.
그래프를 분석하기 어려운 이유
첫째, 그래프는 유클리드 공간에 있지 않다. 이는 우리에게 익숙한 좌표계로 표현할 수 없다는 것을 의미한다. 시계열 데이터, 음성, 이미지 같은 데이터는 2차원, 3차원 유클리드 공간에 쉽게 매핑할 수 있는데 그래프 데이터의 해석은 비교적 어렵다.
둘째, 그래프는 고정된 형태가 아니다. 아래 예시를 보자. 아래 두 그래프는 다르게 생겼다. 하지만 두 그래프의 인접행렬을 같다. 이 경우에 두 그래프를 다르게 볼 것인가, 같게 볼 것인가?
Figure by the original author.
마지막으로, 그래프는 사람이 해석할 수 있도록 시각화 하는 것이 어렵다. 위의 예시에 있는 작은 그래프를 얘기하는게 아니다. 아래 그림 같이 점의 개수가 수백, 수천개 이상인 그래프를 얘기하는 것이다. 점과 선들이 다닥다닥 붙어있어서 눈으로 보고 그래프를 이해하기 어렵다. 이것만을 위한 연구도 따로 있을 정도이다.
Example of a giant graph: circuit netlist. Figure from “Machine Learning and Structural Characteristics of Reverse Engineering”.
그래프를 사용하는 이유
그래프를 사용하는 이유는 다음과 같이 요약할 수 있다.
관계, 상호작용과 같은 추상적인 개념을 다루기에 적합하다. 그래프를 그려보면 이런 추상적인 개념을 시각화 할 때 도움이 된다. 사회적 관계를 분석할 때 기초가 되기도 한다.
복잡한 문제를 더 간단한 표현으로 단순화하기도 하고 다른 관점으로 표현하여 해결할 수도 있다.
소셜 네트워크, 미디어의 영향, 바이러스 확산 등을 연구하고 모델링 할 때 사용할 수 있다. 소셜 네트워크 분석은 데이터 과학에서 그래프 이론을 사용하는 가장 잘 알려진 분야일 것이다. 최근 뉴스에서 코로나19 확산, 이동경로를 나타내고 분석할 때 자주 등장한다. 아래 이미지도 그 중 하나이다.
Image from this link.
기존 그래프 분석 방법
전통적인 방법은 주로 다음과 같은 알고리즘 기반 방법이다.
검색 알고리즘 (BFS, DFS 등)
최단 경로 알고리즘 (Dijkstra 알고리즘, A* 알고리즘 등)
신장 트리 알고리즘 (Prim 알고리즘, Kruskal 알고리즘 등)
클러스터링 방법 (연결 성분, 클러스터링 계수 등)
이런 알고리즘의 한계는 알고리즘을 적용하기 전에 입력 그래프에 대한 사전 지식이 필요하다는 점이다. 그렇기 때문에 그래프 자체를 연구하는 것이 불가능하고, 그래프 레벨에서의 예측이 불가능하다. 여기에서 말하는 ‘그래프 레벨’은 그래프에 속하는 점이나 선에 대한 정보를 다루는 것이 아니라 그래프가 여러개 있을 때 그래프의 정보를 다루는 것을 말한다.
Graph Neural Network
GNN은 이름에서도 알 수 있듯이 그래프에 직접 적용할 수 있는 신경망이다. 점 레벨에서, 선 레벨에서, 그래프 레벨에서의 예측 작업에 쓰인다.
발표된 논문들을 보면 크게 세 가지로 나눌 수 있다.
Recurrent Graph Neural Network
Spatial Convolutional Network
Spectral Convolutional Network
GNN의 핵심은 점이 이웃과의 연결에 의해 정의된다는 것이다. 만약 어떤 점의 이웃과 연결을 다 끊으면 그 점은 고립되고 아무 의미를 갖지 않게 된다. 이름을 불러주었을 때 꽃이 된다면, 연결될 때 점이 된다.
이를 염두하고, 모든 점이 각각의 특징을 설명하는 어떤 상태로 표현되어 있다고 생각해보자. 예를 들어, 점이 영화고 이 영화는 로맨스,범죄,공포 중에 로맨스,범죄에 해당한다면 (1,1,0)의 상태를 가지고 있다고 생각할 수 있다. GNN은 주로 연결관계와 이웃들의 상태를 이용하여 각 점의 상태를 업데이트(학습)하고 마지막 상태를 통해 예측 업무를 수행한다. 일반적으로 마지막 상태를 ‘node embedding’이라고 부른다.
Recurrent Graph Neural Network
오리지날 GNN 논문 ‘The Graph Neural Network Model’에서 소개되었듯이 Recurrent GNN은 Banach Fixed-Point Theorem을 기초로 만들어졌다. Banach Fixed-Point Theorem은 다음과 같다.
k가 크면, x에 매핑 T를 k번 적용한 값과 k+1번 적용한 값이 거의 같다는 의미로 이해하면 된다.
Recurrent GNN은 입력과 출력이 아래와 같은 함수 f_w를 정의하여 점의 상태를 업데이트 한다.
여기에서, l_{n}는 점 n의 feature, l_{co[n]}은 점 n과 연결된 선들의 feature, l_{ne[n]}은 점 n과 연결된 점들의 feature, x_{ne[n]}은 점 n과 연결된 점들의 상태를 의미한다.
An illustration of node state update based on the information in its neighbors. Figure from “The Graph Neural Network Model”.
k번 반복을 통한 업데이트 후 마지막 상태(x_n)와 특징(l_n)을 사용하여 결과값(o_n)을 출력한다. 즉, o_n = g_w(x_n, l_n)이 된다.
함수 f_w, g_w에 대한 자세한 내용은 논문에서 확인할 수 있다.
Spatial Convolutional Network
Spatial Convolutional Network의 아이디어는 이미지 분류와 이미지 영역 구분에 많이 쓰이는 Convolutional Neural Network(CNN)의 아이디어와 비슷하다. 간단히 말하면, 이미지에서 convolution의 아이디어는 학습 가능한 필터를 통해 중심 픽셀의 주변 픽셀을 합치는 것이다. Spatial Convolution Network의 핵심 아이디어는 이 아이디어에서 주변 픽셀 대신 연결된 점의 특징을 적용한 것이다.
Figure from “A Comprehensive Survey on Graph Neural Networks”
Spectral Convolutional Network
Spectral Convolutional Network는 그래프 신호 처리 이론을 기반으로 고안됐으며 위에 설명한 것들보다 더 수학적 기반을 가지고 있다. 이 글에서는 최대한 쉽고 간략하게 느낌적인 느낌을 설명하도록 하겠다.
‘Semi-Supervised Classification with Graph Convolutional Networks’(논문링크, 블로그링크)에서 두 층으로 된 신경망을 제안하는데 아래 식으로 정리할 수 있다.
여기에서 Â는 인접행렬 A를 약간 변형한 것이라고 생각하면 된다. (물론, Â의 정의는 중요하고 ‘spectral’을 붙인 이유이긴 한데 논문에서 각자 읽도록 하자.) 위 식의 형태는 머신러닝에 익숙하다면 본적이 있을 것이다. fully-connected layer 두 개를 연결한 식에선 학습 가능한 행렬 W만 있는데 위 식엔 Â이 붙어있다. 자세한 내용은 논문을 보면 알 수 있고, 여기에선 인접행렬의 변형과 feature matrix를 곱하는 것이 어떤 의미일지만 가볍게 맛보자.
Example of a graph with a feature assigned to each node. Figured by the original author.
점이 4개인 그래프를 생각해보자. 위의 그림처럼 연결되어있고 점 옆에 있는 수들은 그래프의 feature를 나타낸다. 아래처럼 대각선을 1로 채운 인접행렬과 feature matrix를 쉽게 얻을 수 있다.
Example of the adjacency matrix and feature matrix. Figured by the original author.
이제 두 행렬을 곱할 것이다.
Example of graph convolution by matrix multiplication. Figured by the original author.
가장 오른쪽에 있는 행렬이 곱한 결과이다. 곱한 후 [점 1]의 feature를 보자. [점 1] 자신과 이웃인 [점 2], [점 3]의 feature를 합한 값임을 알 수 있다. [점 4]는 [점 1]의 이웃이 아니므로 [점 4]의 feature는 더해지지 않았다. 인접행렬의 성질에 의해 곱한 결과가 자신과 이웃의 feature 합이 되었다.
따라서, Spectral Convolutional Network와 Spatial Convolutional Network는 다른 내용을 기초로 하고 있지만 비슷한 연산 과정을 거친다. 현재 대부분의 Convolutional GNN이 이런 식이다. 점의 정보를 공유하고 업데이트를 하는데 어떻게 전달할 것인지에 대한 연구가 많이 진행되고 있다. 어떻게 전달할지 정의하는 함수를 message-passing 함수라고 한다. ‘Neural Message Passing for Quantum Chemistry’에서 아래 세 가지 함수를 정의하여 GNN을 Quantum Chemistry에 적용하는 연구를 했다. 자세한 정의는 생략하지만 첨자와 기호를 보면 대략 어떤 식인지 추측할 수 있다.
GNN은 무엇을 할 수 있는가?
GNN이 해결할 수 있는 문제는 크게 세 가지로 나눌 수 있다.
Node Classification
Link Prediction
Graph Classification
Node Classification
Node embedding을 통해 점들을 분류하는 문제다. 일반적으로 그래프의 일부만 레이블 된 상황에서 semi-supervised learning을 한다. 대표적인 응용 영역으로는 인용 네트워크, Reddit 게시물, Youtube 동영상이 있다.
Link Prediction
그래프의 점들 사이의 관계를 파악하고 두 점 사이에 얼마나 연관성이 있을지 예측하는 문제다. 대표적인 예로 페이스북 친구 추천, 왓챠플레이(유튜브, 넷플릭스) 영상 추천 등이 있다. 물론 저들이 GNN을 실제로 쓰는지는 모르고 우리도 쓰는지 안 쓰는지 비밀이다. 궁금해요? 궁금하면 클릭. 영화와 유저가 점이고 유저가 영화를 봤으면 선으로 연결을 해준 그래프를 생각할 수 있다. 선으로 연결되지 않은 영화, 유저 쌍 중에 연결될 가능성이 높은 쌍을 찾아서 유저가 영화를 감상할 가능성이 높다고 예측할 수 있다.
Graph Classification
그래프 전체를 여러가지 카테고리로 분류하는 문제이다. 이미지 분류와 비슷하지만 대상이 그래프라고 생각하면 된다. 분자 구조가 그래프의 형태로 제공되어 그걸 분류하는 산업 문제에 광범위하게 적용할 수 있으며 따라서 화학, 생의학, 물리학 연구자들과 활발히 협업을 하고 있다.
실제 응용 사례
GNN으로 어떤 일을 할 수 있는지 위 내용을 대략 이해했다면 실제로 어떤 일이 일어났는지 궁금할 것이다. 아래 논문들을 통해 각자의 분야에서 GNN 어떻게 사용할지 조금 더 감 잡을 수 있길 바란다.
Scene graph generation by iterative message passing
CNN에 기반을 둔 많은 방법들이 이미지에서 물체를 탐지하는데 최첨단 성능을 달성했지만 그 물체들 사이의 관계까지는 알지 못한다. CNN으로 탐지된 물체들을 아래 그림의 방법을 통해 scene graph를 만들어서 관계를 파악할 수 있다.
Image generation from scene graphs
위에서 언급한 작업의 반대되는 작업도 할 수 있다. 기존 이미지 생성 방법은 Generative Adversarial Network이나 Autoencoder를 사용하였다. 아래 그림의 방법을 사용하면 scene graph로부터 이미지를 생성할 수 있다.
Graph-Structured Representations for Visual Question Answering
Visual Question Answering 문제에도 그래프를 도입하여 성능을 끌어올릴 수 있다. 아래 그림에 간략히 요약되어 있는데, 장면과 질문으로부터 각각 scene graph와 question graph를 만든 후 pooling과 GRU를 적용한다.
Machine Learning for Scent: Learning Generalizable Perceptual Representations of Small Molecules
머신러닝이 시각, 청각을 넘어서 후각에 진출하고 있다. 분자 구조를 그래프로 변환하고 GNN을 거치면 138개의 향기를 예측할 수 있다고 한다. 기존에는 분자 구조를 분석할 때 Mordred나 fingerprint 방법을 사용했는데 요즘엔 graph neural network를 사용해서 분자 주고를 분석할 수 있다.
Graph Convolutional Matrix Completion
유저-영화 평점 행렬이 있을 때 기존 평점을 기반으로 message passing function을 사용해서 아직 평가가 없는 유저-영화 쌍의 예상 평점을 계산한다.
마무리
사람들은 항상 머신러닝을 ‘블랙박스'로 본다. 대부분 머신러닝 알고리즘은 훈련 데이터의 feature를 통해서만 학습하지만 그 과정의 이유는 모른다. 그래프를 사용하면 학습을 하는 흐름에 논리를 조금 뒷받침할 수 있고 더 자연스러운 과정이라고 생각할 수 있다.
GNN은 여전히 비교적 새로운 분야이며 더 많은 주목을 받을 가치가 있다. 그래프 데이터를 분석할 때 뛰어날 뿐만 아니라 다른 도메인에도 영향을 주고 있다. 이 글이 독자들의 전공 분야, 관심 있는 분야에 ‘GNN을 한번 적용해볼까?’라는 생각을 들게 해주길 바란다.
참고자료
F. Scarselli, M. Gori, “The graph neural network model,” IEEE Transactions on Neural Networks, 2009
Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, Philip S. Yu, “A Comprehensive Survey on Graph Neural Networks”, arXiv:1901.00596
T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in Proc. of ICLR, 2017
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Neural Message Passing for Quantum Chemistry”, in Proc. of ICML, 2017
D. Xu, Y. Zhu, C. B. Choy, and L. Fei-Fei, “Scene graph generation by iterative message passing,” in Proc. of CVPR, 2017
J. Johnson, A. Gupta, and L. Fei-Fei, “Image generation from scene graphs,” in Proc. of CVPR, 2018
D. Teney, L. Liu and A. van den Hengel, “Graph-Structured Representations for Visual Question Answering”, in Proc. of CVPR, 2017
B. Sanchez-Lengeling, J. N. Wei, B. K. Lee, R. C. Gerkin, A. Aspuru-Guzik, and A. B. Wiltschko, “Machine Learning for Scent: Learning Generalizable Perceptual Representations of Small Molecules”, arXiv: 1910.10685
R. van den Berg, T. N. Kipf, and M. Welling, “Graph Convolutional Matrix Completion”, arXiv:1706.02263
가입하기
