달고나 42. AI, 그래프를 배우다
Algorithm. Mastering GNN
이전 포스팅에서 BDL을 푸는 방법을 먼저 정리했지만, 이직 후에 처음 공부한 것은 Graph Neural Network (GNN)이었다. GNN도 카카오에서 마지막까지 남겨놨던 주제인데 운명의 장난처럼 이직하자마자 공부하기 시작했다. 파트장님의 ‘혹시 GNN도 알아요?’라는 물음에 바로 공부해야겠구나라는 무언의 압박을 느꼈다. BDL과는 달리 GNN은 이미 많은 Survey 논문들이 있어서 체계를 잡는 데는 다소 쉬웠으나 처음 GNN이 어떻게 구성, 학습되는지를 이해하기까진 시간이 필요했다. 다행히 오래전에 개념만 들었던 Message Passing 메커니즘으로 대부분 GNN을 설명할 수 있다는 걸 익힌 후론 진도가 빨라졌다. Signal processing의 filter 개념 또는 convolution으로 시작해서 여러 수식들이 나올 때는 방황했는데 MP로 정리된 후로는 다소 쉬워졌다. 물론 지금도 필터로 설명한 논문은 잘 이해하기 어렵다. 그냥 익숙해질 뿐이다. 다른 분들이 나와 같은 우여곡절을 겪지 않도록 어떤 순서로 GNN을 익히면 개념을 쉽게 — 쉽지 않을 수 있음 — 익힐 수 있는지를 대략적인 테크트리를 설명하려 한다. 참고했던 모든 자료나 논문들을 리스트업 하지는 못한다는 점은 이해 바란다.
자세한 설명에 앞서 그래프가 뭔지 그리고 GNN이 필요한 이유부터 짧게 적는다. 그래프는 모든 자료 구조의 모태가 되는 형태로 노드 (vertex)와 링크 (edge)로 이뤄졌고, G = {V, E}로 표현한다. 엣지 E도 정보를 갖을 수 있지만 보통 노드 V에 부가 정보가 있는 경우가 대부분이어서 G = {V, E, X}로 표현하기도 하는데, 여기서 X는 V의 속성 정보를 나타내는 벡터다. GNN을 설명하기에 앞서 몇 가지 속성을 익힐 필요가 있는데, 한 노드에서 (1-hop) 엣지로 연결된 노드를 Adjacency (이웃)라 하고, 노드에 연결된 이웃의 개수 (즉, 엣지의 개수)를 Degree라 한다. Laplace Matrix를 주로 이용하는데, L = D - A (L 라플라스, D diagonal degree matrix, A adjacency matrix)다. 더 자세한 내용은 아래에 소개할 자료들을 참고하기 바란다. 그리고 GNN으로 하려는 것은 기본적으로 노드 V를 수치 벡터로 표현하는 거다. 이를 이용해서 엣지와 (sub-) 그래프 전체도 수치 벡터로 표현할 수 있다. 이런 수치 벡터를 이용해서 unseen 노드를 분류한다거나 노드 간의 연결 가능성 (edge prediction)을 측정한다거나 또는 (서브) 그래프의 의미를 파악하는 등에 활용한다.
기술의 변화/발전이 워낙 빨라서 최신 기술은 논문에 많이 의존하지만 잘 정리된 책 (텍스트북)이 있다면 이보다 더 좋은 자료는 없다. 정식 출판본은 아니지만 GNN을 다룬 책을 가장 먼저 읽기 시작했다.
1. Deep Learning on Graphs (Book)
- https://cse.msu.edu/~mayao4/dlg_book/dlg_book.pdf
1~3장까지는 그래프와 딥러닝에 관한 일반적인 내용을 다루고 있어서 그래프나 딥러닝에 생소한 분들도 쉽게 개념을 파악할 수 있다. GNN을 이해하는데 필요한 시그널 프로세싱이나 Fourier 변환 등의 내용도 있지만 처음에는 가볍게 무시하고 읽어도 된다. 4장은 GNN은 아니지만 본격적으로 그래프 (노드) 임베딩을 가능하게 했던 DeepWalk (DW)라는 알고리즘을 소개하고 있다. DW를 처음 읽었을 때 나름 충격을 받았다. 완전히 새로운 분야를 개척하는 천재들도 존경하지만, 기존에 있던 익숙한 개념들을 엮어서 새로운 방식을 만들어낸 아이디어를 개인적으로 매우 높게 평가하는데 (전자는 경외, 후자는 자책), DW가 바로 그런 사례다. 이름에서 알 수 있듯이 DW는 Walk, 더 정확히 말하면 (이미 친숙한) Random Walk를 활용해서 임베딩 한다. 여러 노드들에서 시작해서 임의로 방문(traverse)한 node sequence들을 ‘문장 document’로 본다면 각 노드는 ‘단어 word’가 된다. 이쯤 되면 Word2Vec을 바로 떠올리는 분도 많을 텐데, DW는 랜덤워크로 생성된 노드 시퀀스에 skip-gram을 적용해서 노드 (워드)를 임베딩 한 거다. 이후에 Node2Vec이 등장했는데, 기본 방식은 같지만 노드 간 이동하는 방식에 제한을 둬서 조금 개선한 아이디어다. 4장까지는 쉽게 읽었겠지만 5장부터는 계속 읽어도 내가 뭘 읽고 있는지 이해하기가 조금 어렵다. 이쯤에서 그만 읽고 다음으로 넘어가자. (DW나 N2V는 GNN보다 성능이 낮음)
2. Graph Representation Learning (GRL, Book)
- https://www.cs.mcgill.ca/~wlh/grl_book/files/GRL_Book.pdf
두 번째 책은 6장까지만 일단 읽으면 된다. 6장까지 읽으면 GNN이 Message Passing (MP)으로 정의, 해석할 수 있다는 걸 배운다. 7장의 Theoretical Motivations는 아래의 다른 논문들을 좀 더 읽어서 개념에 익숙해진 후에 다시 읽으면 도움이 되지만 다시 읽는다고 해서 쉽게 이해되는 건 아니다 (ㅠㅠ). MP는 그래피컬 모델 (Graphical Model) 또는 Bayesian Network에서 사용하는 개념으로, BN에선 belief propagation이란 용어로 더 익숙하다. 자세한 건 생략하고, 한 노드의 정보는 이웃 노드들의 정보의 합으로 정의한다. 즉, 이웃 노드의 message (또는 belief)를 전달 (pass/progagate) 받는다는 걸 의미한다. 결국 GNN은 MP로 주변/이웃의 노드의 정보를 취합해서 현재 노드를 표현한다로 정리할 수 있다. MP 개념이 낯설고 아직 이해하기 어려운 분들은 구글의 페이지랭크 PageRank (PR) 알고리즘을 생각해보면 된다. GNN (벡터)의 스칼라 버전이 PR이다. PR은 각 노드의 중요도를 스칼라 값으로 취합하는데, 그건 하이퍼링크로 연결받은 이웃 문서들의 중요도의 — 조금 더 복잡한 연산이 있지만 — 합 (aggregation)으로 정의된다. Aggregation 후에 그래프 전체의 밸런스를 맞추도록 값을 재조정 (update)하는 과정을 여러 번 거치면 각 문서의 본연의 중요도가 측정된다. 비슷한 연산을 vector로 진행한 것이 GNN이다.
3. 많은 Survey 논문들 (검색하면 많이 나와서 링크 생략)
위의 책만으론 부족한 다양한 알고리즘이나 최신 연구 동향을 파악하기 위해서 이젠 여느 때와 같이 서베이 논문들을 쭉 읽어보면 감이 조금 잡힌다. 그런데 MP로 설명한 부분은 대강 이해는 되는데, 필터 (또는 convolution)로 설명한 부분은 여전히 긴가민가하다. 그래도 여러 논문들을 계속 읽어 가다 보면 용어나 개념, 표현이 익숙해지고 처음엔 이해하기 어려웠던 것들도 차츰 눈에 들어온다.
4. 주요 seminal 논문들 (몇 개만 가져옴)
- DeepWalk: https://arxiv.org/pdf/1403.6652.pdf
- Node2Vec: https://arxiv.org/pdf/1607.00653.pdf
- MPNN: https://arxiv.org/pdf/1704.01212.pdf
- GCN: https://arxiv.org/pdf/1609.02907.pdf
- GraphSAGE: https://arxiv.org/pdf/1706.02216.pdf
책과 서베이 논문을 읽으면서 반복해서 등장하는 알고리즘은 개별 논문을 찾아서 자세히 읽어보는 게 좋다. 특히 개념이 처음 등장한 논문과 그것의 메이저 업데이트 논문은 필히 읽어보면 좋다. 실제 문제에 적용하는 것에 관심이 더 크다면 기업체에서 나온 논문을 참조하면 학계 논문과는 다른 인사이트를 얻을 때도 많다.
5. 기타 자료
- Uber Eats: https://eng.uber.com/uber-eats-graph-learning/
- Distill: Understaning Colvolutions on Graphs (Interative Visualization)
- https://distill.pub/2021/gnn-intro/
- https://distill.pub/2021/understanding-gnns/
논문은 아니지만 GNN을 실제 문제에 적용한 사례를 찾아본다거나 좀 더 평이한 문장으로 적은 자료를 읽는 것이 논문을 보는 것보단 이해하는데 편하다. 정확한 수식과 메커니즘을 익히기 위해선 논문이 필수지만, 그냥 개념적 이해를 위해선 일반 블로그가 더 편하다. 하지만 전문가의 블로그가 아닌 경우에는 좀 더 주의하고 크로스 체크를 하면서 읽기를 바란다. 특히 학생들이 논문을 리뷰하며 적은 한글 포스팅은 가능하면 참조한 원래 논문을 함께 읽을 것을 권한다. 우버에서 GNN을 적용한 사례는 이론적으로 완전히 새롭지는 않지만 실제 문제에 적용할 때 발생/고려하는 다양한 practical issue를 다루기 때문에 도움이 많이 된다. Distill의 첫 번째 포스팅은 그래프가 무엇이고 GNN을 어떤 분야에 활용하는지에 관한 기초 지식을 습득하기에 좋고, 두 번째 포스팅은 중요 GNN인 GCN, GAT, GraphSAGE, GIN을 interactive 그래픽으로 설명해놨기 때문에 직접 수치를 바꿔가면서 임베딩 값이 변하는 걸 본다면 책과 논문의 설명과 수식으로 이해하기 어려웠던 부분을 많이 해결할 수 있다. 그냥 수식과 설명만 보면 앞의 4가지 (그 외 다른) 방식들이 모두 다른 듯하지만 distill의 그래픽을 보면 MP, 즉 모든 이웃 노드로부터의 MSG를 합(aggregation)하고 스케일을 조정(update)한다는 걸 알 수 있다. 합치는 방식이나 가중치만 다를 뿐이다. CNN에서 목적에 맞는 다양한 필터를 만들어내듯이 적당한 MSG 필터 또는 가중치 산정 방식만 새로 고안하면 다양한 그래프나 문제에 특화된 GNN을 구상할 수 있다.
** distill의 자료는 내가 GNN을 이해하는데 마지막 퍼즐이 됐다. 두 문서의 작성일이 공교롭게도 2021년 11월이다. 내가 딱 GNN을 공부할 시기를 예상하고 만들어졌나 싶을 정도다. 뭐든 시기가 중요하다. 예전에 공부했더라면 이런 자료가 있는지도 모르고 어설프게 이해했거나 어렵다며 그냥 포기했을 거다.
6. 다시 책으로…
GNN을 향한 먼 길을 왔는데, 이제 다시 책으로 돌아가서 앞서 남겨놨던 부분을 읽어보길 권한다. DLonG를 처음부터 또는 5장부터 다시 읽고, GRL의 7장을 읽으면 이젠 조금 익숙해졌을 거다. 컨볼루션 방식과 MP가 처음에는 전혀 다른 방식처럼 보였지만 이젠 (특히 위의 Distill의 그래픽을 봤다면) 같은 개념을 다르게 표현한 것을 알았을 거다. Convolution과 Sum/Aggregation이 같은 말이기 때문에 둘의 시작이 달랐을 뿐 같은 지점에 이르렀다. 저는 MP가 더 편해서 GNN을 MP의 틀로 이해했지만 시그널 프로세싱이나 컨볼루션에 더 익숙한 분은 컨볼루션으로 GNN을 이해하면 된다. 시각적으로 상상이 가능한 MP가 이해하는데 더 쉬울 것 같아서 저는 이런 식으로 공부하면 된다고 한 것이지, 이것이 유일한 방식은 아니다. 각자 편한 방식과 순서로 GNN을 마스터하기 바란다.
7. 필드로…
노드 임베딩을 위주로 글을 적었지만 엣지 임베딩이나 그래프 임베딩은 Concat이나 풀링 등으로 바로 확장 가능하다고 믿는다. 그래프의 종류가 다양하기 때문에 상황에 맞는 변경도 필요하다. 혹시 자신의 문제가 엣지나 그래프 임베딩이라면 위에 적은 참고 자료들 외에도 이를 다룬 많은 자료들이 있으니 직접 찾아보기 바란다. 이제 직접 구현하고 자신의 문제에 적용해서 좋은 성과를 얻길 바란다. 이미 오픈소스도 많으니 있는 걸 그냥 잘 활용해도 좋고, 자신의 문제에 맞게 조금씩 수정할 수도 있다. GNN이 아직은 연구 초기라서 개선할 포인트들이 많기 때문에 연구자(대학원생)라면 GNN을 좀 더 깊게 파보면 쉽게 논문 주제를 찾을 수 있다.
