AI, 그래프를 배우다 (Mastering GNN)

이전 포스팅에서 BDL을 푸는 방법을 간략히 정리했는데, 사실 이직 후에 처음 공부한 것은 Graph Neural Network (GNN)이었다. GNN도 카카오에서 마지막까지 남겨놨던 주제인데 운명의 장난처럼 이직하자마자 공부하기 시작했다. BDL과는 달리 GNN은 이미 많은 Survey 논문들이 있어서 체계를 잡는 데는 다소 쉬웠으나 처음 GNN이 어떻게 구성, 학습되는지를 이해하기까진 시간이 필요했다. 다행히 오래전에 배웠던 Message Passing 메커니즘으로 현재의 대부분 GNN을 설명할 수 있다는 걸 익힌 후론 진도가 빨라졌다. Signal processing의 filter 개념으로 시작해서 여러 수식들이 나올 때는 방황했는데 MP로 정리된 후로는 다소 쉬워졌다. 물론 지금도 필터로 설명한 논문은 잘 이해하기 어렵다. 그냥 익숙해질 뿐이다. 다른 분들이 나와 같은 우여곡절을 겪지 않도록 어떤 순서로 GNN을 익히면 개념을 쉽게 — 쉽지 않을 수 있음 — 익힐 수 있는지를 대략적인 테크트리를 설명하려 한다. 참고했던 모든 자료나 논문들을 리스트업 하지는 못한다는 점은 이해 바란다.
자세한 설명에 앞서 그래프가 뭔지 그리고 GNN이 필요한 이유부터 짧게 적는다. 그래프는 보통 노드 (vertex)와 링크 (edge)로 이뤄진 자료 구조로, G = {V, E}로 표현한다. 엣지 E도 정보를 갖고 있지만 보통 노드 V가 부가 정보를 갖는 경우가 대부분이어서 G = {V, E, X}로 표현하기도 하는데, 여기서 X는 V의 속성 정보를 나타내는 벡터다. GNN을 이해하는데 필요한 몇 가지 속성이 있는데, 엣지로 연결된 노드를 Adjacency (이웃)라 하고, 노드에 연결된 이웃의 개수 (즉, 엣지의 개수)를 Degree라 한다. 또 중요한 개념으로 Laplace Matrix가 있는데, L = D - A (L 라플라스, D diagonal 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은 아니지만 본격적으로 그래프 (노드) 이베딩을 가능하게 했던 DeepWalkn (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 그래픽으로 설명해놨기 때문에 직접 수치를 바꿔가면서 임베딩 값이 변하는 걸 본다면 책과 논문의 설명과 수식으로 이해하기 어려웠던 부분을 많이 해결할 수 있다.
6. 다시 책으로…
GNN을 향한 먼 길을 왔는데, 이제 다시 책으로 돌아가서 앞서 남겨놨던 부분을 읽어보길 권한다. DLonG을 처음부터 또는 5장부터 다시 읽고, GRL의 7장을 읽으면 이젠 조금 익숙해졌을 거다. 컨볼루션 방식과 MP가 처음에는 전혀 다른 방식처럼 보였지만 이젠
(특히 위의 Distill의 그래픽을 봤다면) 같은 개념을 다르게 표현한 것을 알았을 거다. Convolution과 Sum/Aggregation이 같은 말이기 때문에 둘의 시작이 달랐을 뿐 같은 지점에 이르렀다. 저는 MP가 더 편해서 GNN을 MP의 틀로 이해했지만 시그널 프로세싱이나 컨볼루션에 더 익숙한 분은 컨볼루션으로 GNN을 이해하면 된다. 시각적으로 상상이 가능한 MP가 이해하는데 더 쉬울 것 같아서 저는 이런 식으로 공부하면 된다고 한 것이지, 이것이 유일한 방식은 아니다. 각자 편한 방식과 순서로 GNN을 마스터하기 바란다.
7. 필드로…
노드 임베딩을 위주로 글을 적었지만 엣지 임베딩이나 그래프 임베딩은 바로 확장 가능하다고 믿는다. 혹시 자신의 문제가 엣지나 그래프 임베딩이라면 위에 적은 참고 자료들 외에도 이를 다룬 많은 자료들이 있으니 직접 찾아보기 바란다. 이제 직접 구현하고 자신의 문제에 적용해서 좋은 성과를 얻길 바란다. 이미 오픈소스도 많으니 있는 걸 그냥 잘 활용해도 좋고, 자신의 문제에 맞게 조금씩 수정할 수도 있다. GNN이 아직은 연구 초기라서 개선할 포인트들이 많기 때문에 연구자(대학원생)라면 GNN을 좀 더 깊게 파보는 것도 쉽게 논문 주제를 찾을 수 있다.