데이터 과학 유망주의 매일 글쓰기 — 쉬어가는 시간 4–1
Graph Neural Network (GNN)
# GNN
오늘 한일:
드디어 마지막 섹션의 프로젝트가 끝났다. 벌써 이만큼 달려왔다는게 믿기지 않는다. 물론 조금 아쉬운 점도 있었지만, 어쨌든 내가 선택한 다른 문제를 해결하고, 그에 대한 발표를 성공적으로 할 수 있어서 다행이다.
이번 섹션을 공부하면서 특히 데이터 구조 중 그래프(Graph)라는 것에 많은 관심과 흥미를 가지게 되었다. 그래프를 보면서 가장 놀라웠던 것은 이 것이 이전 과정에서 배웠던 신경망(Neural Network)를 떠올리게 한다는 것이었다.
그래서 찾아보았더니 실제로 그래프 신경망(Graph Neural Network, GNN)이라는 것이 존재했다. 그렇다면 이 GNN은 어떤 구조로 이루어져 있으며, 어디서 활용될 수 있을까?
그래프(Graph)란?
컴퓨터 공학에서는 그래프가 노드(Vertice) 및 Edge라는 부분으로 구성되어있다. 그래서 그래프는 Edge를 통해 서로 연결된 네트워크(Network)의 개념으로 볼 수 있다.
그래프의 종류는 아래와 같이 방향성이 없는 Undirected Graph, 방향성이 있는 Directed Graph, 모든 노드가 서로 완전히 연결되어있는 Complete Graph로 나누어진다.
그래프의 노드는 다른 모든 노드들과 비슷한 구조를 가지고있거나, 서로 다른 노드들이 서로 다른 형태로 이어져 있다고도 볼 수 있다. Edge는 하나의 노드에서 다른 노드로 이어지는 관계를 말한다. Edge는 하나의 노드 “u”에서 다른 노드 “v”로 이어질 수 있으며, 그것이 양방향일 수도 있고 단방향일 수도 있다. Edge는 서로 다른 값을 가지는 Weighted 형태이거나, 연결 상태(“1”)로만 나타내는 Unweighted 일 수 있다.
예를 들어, 도시의 네트워크로 이루어진 그래프가 있다고 가정하자. 각각의 도시를 노드로, 각 도로를 Edge로 볼 수 있다. 만약, 도시들 사이에 가장 빠른 거리를 찾는다고 하면, 각 도로가 거리에 따라 특정한 가중치를 갖는다고 한다면, 가장 가중치가 낮은 거리를 위주로 검색을 할 수 있다.
그래프 신경망(Graph Neural Network)
그래프는 데이터를 효과적으로 표현할 수 있다는 장점 때문에, 머신 러닝 분야에서 특히 각광을 받고 있다. 모든 노드는 특정한 공간에서 정의될 수 있는 Embedding한 값을 가진다. 이러한 장점을 살려, 그래프 구조에 기반한 신경망인 GNN이 등장했다. GNN의 목적은 특정 노드의 주변 조건에 대한 정보가 담긴 Embedding값을 학습하는 것이다. 즉, 목적 노드와 Edge로 연결된 노드들의 정보를 학습하는 것이다. 노드 라벨링이나, 노드 예측, Edge 예측 등의 문제에 Embedding값들이 활용될 수 있다.
각 노드에 대한 Embedding 값이 있다면, Feed Forward 방식으로 네트워크의 레이어들을 더하는 방식으로 Edge를 변형하여 그래프와 신경망을 결합한다.
그래프 신경망의 등장 배경
그래프 신경망의 필요성이 대두된 것은, 특정한 구조로 정리되지 않은 데이터가 너무 많아졌기 때문이다. 구조화되지 않은 데이터는 아직 처리되지 않은 데이터이거나, 통상적으로 정의되지 않은 형태를 가지고 있어 분석이 어렵다는 단점이 있다. 예를 들어, 오디오, 이메일, 소셜미디어 포스팅 등이 있다. 이러한 데이터를 이해하고 인사이트를 추려내기 위해서는, 구조화되지 않은 데이터 사이에 존재하는 관계를 정의해야한다. 기존의 머신 러닝 구조와 알고리즘으로는 이러한 처리되지 않은 데이터를 바탕으로 학습하는 것에 한계가 있었다.
이에 대한 대안으로 나온 것이 GNN이며, 이는 아래와 같은 장점을 가지고 있다.
- 컴퓨터 공학에서 그래프 데이터 구조는 정리되지 않은 데이터를 처리하는데 있어 매우 높은 효율성을 가진다는 것이 증명되었다.
- 그래프는 도시들 사이의 관계 같은, 추상적인 개념을 정의하는데 매우 유용하다. 그래프의 각 노드가 다른 노드 사이의 연결로 정의될 수 있기 때문에, 노드들 사이에 존재하는 관계를 효율적으로 나타낼 수 있다.
그러므로, 소셜 네트워크의 데이터 같은 구조화되지 않은 데이터를 처리하기위해 그래프에 기반한 신경망을 만들 수 있다는 아이디어가 등장했다.
그래프 신경망의 실생활 활용
GNN은 2018년에 먼저 소개되어, 이후 많은 분야에서 활용되고 있다. 특히, 여러 다른 소스에서 추출한 구조가 없는 데이터를 처리하는데 있어 매우 큰 활약을 하고 있다.
먼저 소셜 네트워크 분석(Social Network Analysis) 목적에 많이 활용된다. 비슷한 포스팅을 예측하여 추천해 주거나, 사용자가 보는 포스팅의 태그(#)를 미리 예측하여 생성할 수 있다. 또한, 생명 공학에서 단백질 사이에서 일어나는 화학적 상호 작용을 예측하는데 있어 현재 많은 각광을 받고 있다.마지막으로, 사용자와 사용자가 구매한 상품들간의 관계를 잡아내 사용자가 관심 있을 법한 상품들을 추천하는데 활용할 수도 있다.
그래프 신경망의 작동 방법
그래프 신경망의 기본적인 구조를 파악했다면, 이번에는 그래프 신경망이 어떻게 작동하는지에 대해 궁금할 것이다. 기억해야할 것은, 노드의 Embedding과 Edge, 그리고 Feed Forward Layer등이 그래프 신경망을 이루는 주 요소들이라는 것이다.
단순하게 보자면, 신경망을 활용하여 “Edge의 누적”을 통해, 노드의 주변 조건들에 대한 정보를 담은 Embedding값을 학습하는 과정이다.
이웃 누적(Neighborhood Aggregation)/메시지 패싱(Message Passing)
메시지 패싱은 노드들 사이에 있는, 노드와 그 이웃들에 대한 정보를 주고 받는 과정을 말한다. 예를 들어 초기 Embedding값을 갖는 타깃 노드가 있다고 하자. 이는 그 이웃들로부터 Edge를 통해 전달된 정보라고 할 수 있다. 이 Edge들로부터 온 데이터는 max pooling, average pooling등을 통해 누적되고, 노드의 활성화 함수에 패스되어 노드에 대한 새로운 Embedding값들을 얻을 수 있다. 초기 설정에서 모든 노드는 x_v의 값을 가진다. 메시지를 패싱한 후에 얻을 수 있는 각 노드에 대한 Embedding값은 아래와 같이 정의될 수 있다.
- x_nev: 노드 “v”에 대한 이웃 feature를 말한다.
- x_cov: 노드 “v”에 연결된 edge들의 feature를 말한다.
- h_nev: 노드 “v”의 이웃에 대한 Embedding을 말한다.
위 그림을 보면, hA(1)은 노드의 최초 Embedding 값이며, hNA(1)은 그 이웃들의 Embedding 누적 값이다. 이들을 결합하여 노드의 활성화 함수에 전달하여 필터링하면, 노드 A에 대한 이웃 정보를 담은 새로운 Embedding값을 포함할 것이다. 이런 식으로 각 노드는 새로운 Embedding값들을 얻고, 그래프안에서 각 노드의 위치를 결정한다. 많은 반복 연산 또는, K 레이어들을 통과해 메시지를 전달하며, 각 노드는 그 주변 노드들과의 거리나 이웃 정보를 학습한다.
결국, 각 노드는 전체 그래프에 대해 얕은, 또는 부분적인 지식만을 가지고있다. 반복 횟수와 노드 사이의 거리나 길, 또는 레이어에 따라 다를 수 있다.
예를 들어, 소셜 미디어 포스트를 그래프의 노드로 가정하자. 만약 이 노드들이 Embedding값을 가지고 있고, “로맨스", “과학", “코미디" 등의 태그를 가지고 있다면, 새로운 포스트에 적절한 태그를 붙일 수 있다. 존재하는 네트워크 및 Embedding 값을 활용하여, 이웃 누적 정보는 라벨과 Embedding 값을 보이지않는 노드에 대해 예측할 수 있다.
장점: 전체 알고리즘을 다시 실행시킨다면, 이웃의 Embedding을 사용하여 새로운 포스트의 로컬성(locality)를 결정할 수 있다. 그러므로, GNN 기반 추천은 더 큰 규모의 데이터셋에 대해 기존의 머신 러닝 추천 알고리즘보다 더 효율적이면서도, 더 넓게 확장이 가능하다.
그래프 신경망의 종류
그래프는 이미 존재하는 다수의 신경망 구조를 활용하여 여러 머신 러닝 모델을 생성해 좋은 성능을 발휘할 수 있다. 여기서는 가장 널리 쓰이는 2가지의 신경망을 소개한다.
Graph Convolutional Network(GCN)
Convolutional neural networks(CNNs)은 이미지 분류 및 부분화(segmentation) 문제의 해결을 위해 널리 사용되고있다. Convolution과정이란, 입력 이미지에 대해 spatial filter라는 것을 사용하여 특정한 feature의 map을 얻어내는 과정을 말한다.
GCN은 그래프의 노드에 움직이는 spatial filter를 적용한다. 또한, 각 노드의 관련 Embedding 또는 데이터를 포함하기 때문에, 각 노드에 대한 feature를 얻을 수 있다. 일반적인 CNN 처럼 convolutional layer를 쌓는 기법이, 더 큰 이웃의 정보를 포함하는데에도 사용될 수 있다.
Graph Auto-Encoder Networks
Auto-encoder는 이미지의 사이즈를 압축하는 encoder라는 bottleneck layer와, encoder가 압축한 입력값을 활용해 다시 본래의 이미지를 구현하는 decoder로 이루어져있다.
그래프 Auto-encoder는 그래프의 압축된 형태를 학습하고 decoder를 통해 원본의 이미지를 구현해야한다. 그래프 Embedding 값을 학습하는데 활용될 수 있으며, 새로운 노드에 대한 Embedding값을 예측할 수 있다. 또한 새로운 노드를 그래프에 이미 존재하는 범주로 분류할 수 있다.
그래프 신경망의 대표적인 다른 예는 Spatial Graph Neural Network (SGNN)과 Temporal Graph Neural Network(TGNN), Recurrent Graph Neural Networks(RGNN) 등이 있다.
그래프 프로그래밍 예제
파이썬에는 NetworkX라는 복잡한 네트워크를 생성 및 수정하고, 네트워크의 구조, 유동성, 기능 등을 탐구할 수 있는 라이브러리를 제공한다. 아래는 이 라이브러리를 이용해 그래프 구조를 구현해 볼 수 있는 예제이다.
# NetworkX 설치
pip install networkx# 텅빈 그래프 생성
import networkx as nx
G = nx.Graph()# 그래프에 노드 추가
G.add_node(1)
G.add_node([2, 3]) # 리스트로 노드를 추가할 수도 있다.# 그래프에 Edge 추가
G.add_edge(1, 2) # 노드 1과 2 사이의 Edge
G.add_edges_from([(1, 2), (1, 3)]) # 리스트 형태로도 추가할 수 있다.
G.add_edge(1, 2, weight=4.5) # 가중치 있는 Edge 추가__________________________________________________________# 그래프 "G"에서 노드 "A"에서 노드 "D"로 가는 가장 빠른 길 찾기# 다시 그래프 생성하고, 노드들과 가중치 있는 Edge를 추가하기
G = nx.Graph()
G.add_edge('A', 'B', weight=5)
G.add_edge('B', 'D', weight=3)
G.add_edge('A', 'C', weight=4)
G.add_edge('C', 'D', weight=5)# NetworkX 라이브러리의 shortest_path 메소드 활용
nx.shortest_path(G, 'A', 'D', weight='weight')>> ['A', 'B', 'D']
그 밖에도 igraph라는 그래프를 구현할 수 있는 파이썬 라이브러리가 있다.
그래프 신경망을 구현하려면 아래와 같은 라이브러리를 활용해 볼 수 있다.
앞으로 할일:
그래프 신경망은 구조가 확실하게 잡히지 않은 데이터를 학습할 수 있다는 장점이 있다. 그러므로, 실시간으로 다양한 소스에서 데이터를 처리해야 하는 소설 네트워크 분석 등의 용도로 널리 쓰인다. 즉, 상대적으로 여러 데이터를 전처리해 주어야할 수고를 덜 수 있다는 매우 큰 장점이있다. 그래프를 적절하게 구성한다면, 그래프 신경망은 그 어떤 다른 신경망보다도 더 강력한 기술이 될 수 있다.
생각해보니, 그래프 역시 점과 점을 이은 구조이기 때문에, 시각화로써의 그래프도 이러한 그래프 데이터 구조를 닮은 것이 아닌가하는 생각이든다. x-y 평면에 그려지는 그래프도 결국 점과 점의 연결이니, 노드와 노드 사이를 연결하는 것이 바로 선이 되는 것이니까. 그래프란 네트워크의 역할도 하고, 시각화 도구로써도 매우 의미가 있으며, 신경망으로써도 구성을 할 수 있으니, 컴퓨터 공학에서 가장 기본적이면서도 중요한 데이터 구조라는 사실이 더욱 더 잘 와닿는 것 같다.
더 많은 것들을 공부하면서, 많은 개념들이 서로 이어져있다는 것을 깨닫게 된다. 마치 그래프에서 노드에서 다른 노드가 연결되고, 그러한 노드들의 연결이 커다란 하나의 형태를 갖는 것처럼, 지식도 작은 부분 부분이 또 다른 지식으로 이루어져 있는 것이다. 거미줄 같이 엮여있으며, 서로 연결된 지식들의 Edge를 계속 이리 저리 따라가다보면, 새로운 지식의 노드를 발견하게 되는 과정이 반복되는 느낌이다. 마치 나의 삶도, 그래프 처럼 새로운 길을 따라가다가 새로운 곳, 새로운 세계를 발견하게 되는 것 같다.
앞으로 나는 어떤 Edge를 따라 어떤 노드(세계)를 발견하게 될까? 또한 그렇게 해서 탐험한 전체 그래프는 어떤 모습일까? 내가 앞으로 살면서 탐험하게될 새로운 Edge와 발견하게될 새로운 노드들이 기대된다. 이제 신비롭고 재미있는 컴퓨터의 세계에 입문했으니, 앞으로 이 세계에서 더 많은 노드를 순회하면서 가슴 뛰는 여행을 이어가야겠다는 생각이든다. 앞으로도 컴퓨터에 대해 더 많은 것을 배우고, 향유하며, 느끼고 싶다. 그리고 그 안에서 더 겸손해지고, 더 논리적인 사고를 가진 인간으로 매번 다시 태어나고 싶다. 나를 포함한 모든 컴퓨터 과학 유망주이자 데이터 과학 유망주들도, 드넓은 논리의 세상속에서 계속 성장하고 발전할 수 있기를.
참조:
(1) https://algorist.com/images/figures/graph-data-structures-L.png
(2) https://medium.com/data-structures-and-algorithms/graph-dd2b72c32f1f
(3) https://blogs.cornell.edu/info2040/files/2011/09/econ2040_blog_graph1.png
(4) http://snap.stanford.edu/proj/embeddings-www/files/nrltutorial-part2-gnns.pdf
(5) https://arxiv.org/pdf/1812.08434.pdf
(6) http://snap.stanford.edu/proj/embeddings-www/files/nrltutorial-part2-gnns.pdf
(7) https://www.experoinc.com/post/node-classification-by-graph-convolutional-network
(8) https://www.frontiersin.org/articles/10.3389/fdata.2019.00002/full
Image Source: http://snap.stanford.edu/proj/embeddings-www/files/nrltutorial-part2-gnns.pdf
