그래프기반분석

그래프를 사용하여 데이터를 표현하는 방법은 다음과 같다.
1. 추상적인 개념을 다루기에 적합하다.
1) 관계 데이터
2) 상호작용 데이터
그래프를 그려보면 이러한 추상적인 개념을 시각화할 때 도움이 된다.

2. 복잡한 문제의 표현
복잡한 문제를 더 간단한 표현으로 단순화할 수 있다.

3. 실생활에 적용할 분야가 많다.
소셜네트워크, 미디어의 영향, 바이러스 확산 등을 연구하고 모델링할 때 사용할 수 있다. 소셜 네트워크 분석은 데이터 과학에서 그래프 이론을 사용하는 가장 잘 알려진 분야이다. 최근 뉴스에서 코로나 19확산, 이동경로를 나타내고 분석할 때 자주 등장한다.

4. 기존 그래프 분석의 문제점
기존의 그래프 분석방법은 알고리즘을 적용하기 전에 입력 그래프에 대한 사전 지식이 필요하다. 따라서 그래프 자체를 연구하는 것이 불가능하고 그래프 레벨에서의 예측이 불가능하다.
1) 검색알고리즘(BFS, DFS 등)
2) 최단 경로 알고리즘(Dijkstra 알고리즘, A+알고리즘 등)
3) 신장 트리 알고리즘(PRIM알고리즘, Kruskal알고리즘 등)
4) 클러스터링 방법(연결성분, 클러스터링 개수)

5. Graph Neural Network
GNN은 이름에서 알 수 있듯이 그래프에 직접 적용할 수 있는 신경망이다.
점, 선, 그래프 Level에서의 예측 작업에 사용된다.
논문으로 살펴볼 수 있는 방법은 3가지가 있다.
1) Recurrent Graph Nueral Network
2) Spatial Convolutional Network
3) Spectral Convolutional Network

6. GNN의 핵심
점이 이웃과의 연결에 의해 정의된다는 점이다.
어떤 점이 이웃과 연결이 없다면 해당 점은 고립된 상태로 아무런 의미를 갖지 못한다는 것을 의미한다.

7. GNN의 예측업무
1) 학습
GNN은 주로 연결관계와 이웃들의 상태를 이용하여 각 점의 상태를 업데이트하며 이를 학습한다고 정의한다. 또한 마지막 상태를 통해 예측 업물 수행한다.
2) 마지막 상태
일반적으로 마지막 상태를 node embedding이라고 한다.

 

 

 

아래내용은 정리가 필요한 부분입니다.
Shanon Hong의 An Introduction to Graph Neural Network(GNN) For Analysing Structured Data의 글을 Jeong Jisu님이 정리한 글입니다.

 

 

 

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이 해결할 수 있는 문제는 크게 세 가지로 나눌 수 있다.

1. Node Classification
2. Link Prediction
3. 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을 한번 적용해볼까?’라는 생각을 들게 해주길 바란다.

참고자료

1. F. Scarselli, M. Gori, “The graph neural network model,” IEEE Transactions on Neural Networks, 2009
2. Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, Philip S. Yu, “A Comprehensive Survey on Graph Neural Networks”, arXiv:1901.00596
3. T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in Proc. of ICLR, 2017
4. 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
5. D. Xu, Y. Zhu, C. B. Choy, and L. Fei-Fei, “Scene graph generation by iterative message passing,” in Proc. of CVPR, 2017
6. J. Johnson, A. Gupta, and L. Fei-Fei, “Image generation from scene graphs,” in Proc. of CVPR, 2018
7. D. Teney, L. Liu and A. van den Hengel, “Graph-Structured Representations for Visual Question Answering”, in Proc. of CVPR, 2017
8. 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
9. R. van den Berg, T. N. Kipf, and M. Welling, “Graph Convolutional Matrix Completion”, arXiv:1706.02263