12월 4주차 그래프 오마카세

TGL: A General Framework for Temporal GNN Training on Billion-Scale Graphs

• 현업에 계신분들께서 좋아하실만한 논문입니다. billion-scale 을 가진 그래프들을 어떻게 학습하고 추론할지에 대해 많이 고민하실텐데요. 그 가이드라인 , 레퍼런스로써 좋은 참고서가 될 논문입니다.

• temporal graph inference 는 시간의 흐름에 따라 바뀌는 정보들을 edge 에 timestamp 형식으로 담아두며 message passing 을 통해 업데이트해주는게 핵심이라고 볼 수 있습니다. 이 때, node-edge 간의 정보교환을 통해 새로이 업데이트된 new information 을 historical 하게 잘 보관하는것 또한 중요한데요. 그 솔루션을 본 논문에서 random chunk scheduling 이라 표현하며 제안했습니다.

• node memory , attention aggregator , temporal sampler 그리고 multi-gpu (parallel-sampling) 을 어떻게 하는지등 현업에서 마주하실 많은 고민들을 본 논문에서 명쾌하게 풀어내고 있습니다.

논문을 읽다보시면, binary search , pointer 등의 데이터 자료구조 측면에서 접근하는 섹션이 간간이 있기에 디테일한 이해를 원하신다면 잠시 데이터 자료구조를 복습하고 오시는걸 추천드립니다.

• 또한 , DGL 프레임워크를 사용합니다. 그 중 MFG(Message Flow Graph) 라는 개념이 포함되어 있습니다. 다소 생소하실분들 계실텐데요. 심플하게 message passing 으로 부터 받은 정보들을 어떻게 sampling 할지에 대한 개념이라고 보시면 될 것 같습니다. (디테일한 내용이 궁금하신분들은 DGL 을 보시는걸 추천드립니다.

혹은 추가적인 설명이 필요하시면 주방장에게 메일 혹은 링크드인 메세지 주세요! 환영합니다 🙂)** 이어서) Tutorial: Scaling GNNs in Production: A Tale of Challenges and OpportunitiesLoG 컨퍼런스에서 발표된 영상입니다.

production 에서 gnn 을 활용할 때 한계점을 영상에 담아놓았는데요. 시간되실때 꼭 보시는걸 추천드립니다. 양질의 콘텐츠 , 팁들이 한가득 담겨있습니다.

APAN: Asynchronous Propagation Attention Network for Real-time Temporal Graph Embedding

• MLops 관련 lecture 인 cs329S 공부 중 발견한 논문입니다. 저도 내년 사이드 프로젝트로 gnn with web deployment 해보는게 목표라 되게 반가웠고, 독자분들 절반가까이 현업에 계신분들이시기에 도움되실거라 생각되어 준비해보았습니다.

실 gnn 의 inference 때, high latency 가 가장 큰 문제점으로 꼽히곤 하거든요. 잡설이 길었습니다. ‘since users cannot tolerate the high latency of neighbor query in a giant graph database, deploying a synchronous CTDG model in online payment platform is almost worthless’ 라는 어절을 논문에 명시해놓은만큼 산업 관점에서 잘 풀어낸 논문입니다.

• message passing 에 치중하여 어떻게 node 가 update 시키는지가 핵심인 논문입니다. gnn 을 처음 접할 때 주로 노드의 정보를 담는 공간을 mailbox(우체통)으로 비유하는데요. 그 mailbox 의 mechanism 을 변형한 아이디어입니다.

• 구체적으로는 , 기존 temporal embedding 시 이전 event , message 들을 querying(가져올 때) timestamp sorting 그리고 reading out 등의 과정이 발생하는데요. 이 때 cost 가 상당합니다. 이를 가장 최근의 이웃들의 history message 만을 가져오기 , aggregation 시 mean으로 정보 가공하기 , update 시 summarized , message decay 하기(FIFO queue 개념) 등으로 풀어놓았습니다.

• online deployment 를 위해 최적의 mailbox 청사진이지 않을까 싶습니다. 실험 섹션 결과 그리고 해석이 굉장히 흥미롭습니다. 그래프 정보를 모두 잘 반영하기 위해 설계된 타 모델들 대비 성능이 떨어지지 않으며, speed 또한 빠른걸 보니 되게 신기합니다.

Residual Network and Embedding Usage: New Tricks of Node Classification with Graph Convolutional Networks

• node-classification 에서의 Efficiency trick들을 모아놓은 논문입니다. baseline 을 구현 후 성능이 마음에 들지 않는다? 하실 때 참고하시면 좋을 논문입니다. 실제로 주방장도 주로 성능이 마음에 들지 않을 때 간단하게 correct & smooth 를 시작으로 성능향상을 시도하곤하는데 대부분 만족했습니다. 🙂

• Mini batch training , normalization and drop out , Adversarial training , Label propagation 등 이해하기 쉬우며 , 코드 구현도 간단한 methodology 들입니다. 이 방법론들을 조합하며 어떤 결과가 나오는지에 대해 유심히 지켜보며 실험결과와 독자분들이 기대했던 결과와 어떻게 다른지 비교해보신것 또한 본 논문의 묘미라 생각되네요.

Pay Attention to MLPs

• transformer 구조가 딥러닝 model에서 hegemony 를 가지고 있다.라고 표현해도 과언이 아닐만큼, 많은 산업에서 활용되고 있습니다.

• transformer 의 핵심 정보인 positional encoding 을 spatial gating unit 이라는 개념으로 대체한다는 아이디어가 주인 논문입니다. transformer 요소 중 하나인 self-attention 개념과 ‘연산량’,’projection’ 등 여러 부분에서 대조하며 아이디어를 흥미롭게 풀어나갑니다.

• spatial gating unit 은 gated linear unit 에서 파생된 개념입니다. 간단히 말씀드리면, gate 를 통해 도출된 정보가 유용한 정보인지 아닌지를 판단하는 개념이라고 보시면 되겠습니다. 여기에 spatial 정보를 반영하기 위해 tensor contraction (double inner dot operation) 을 활용해주는 개념이라고 보시면 되겠습니다.

Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods

• 복잡계 네트워크에서 네트워크 데이터 분석할 때, 주로 활용되는 지표 중 하나인 homophily 를 large scale gnn 에 차용한 논문입니다. homophily 를 간단하게 말씀드리면, ‘유유상종’ 이라고 보시면 되겠습니다. 이를 네트워크 데이터에서 생각해보면 ‘비슷한 사람(노드)들 끼리는 연결(link)되어 있을것이다.’ 라고 가정하며 측정하는 지표입니다.

• 그럼 이 개념이 어떻게 임베딩이 활용되는지 궁금하실텐데요. 그래프 임베딩시 주로 연결된 노드들로부터 받은 정보를 활용하여 추론하곤 합니다. 추론할 시 해당 노드 혹은 링크의 고유 label을 잘 맞추는 weight를 학습할텐데요. 이 때, 연결된 노드들 즉 이웃들로부터 받는 정보들이 유사할수록 고유 label 을 더욱 잘 맞춘다는 가정을 기반으로 임베딩이 진행되곤 합니다(homophily) .

• 허나 반대로, 연결된 노드들이 ego node (해당 노드)와 비슷하지 않다면? 다시 말해, non-homophily 하다면 어떨까요? 다들 예상할 수 있듯이, degrade performance 현상을 겪게됩니다. 이는 곧, 노드 주변 이웃들이 어떤 이웃인가에 따라 성능이 좌지우지된다고도 볼 수 있습니다.

그렇다면 최종적으로 학습된 모델이 특정 상황에서만 잘 맞추고 특정 상황이 아닌 경우에는 성능이 많이 떨어진다면, 이 모델은 결국 가치가 매우 떨어지는 모델이라고 볼 수 있죠. (experiment setup 측면에서 이를 체크하기 위해 , transductive , inductive learning 으로 나누어 진행하곤 합니다.)

• 앞선 현상을 극복하기 위해, 본 논문에서는 LINKX 라는 모델을 제안합니다. 모델 구조는 굉장히 심플한데요. (micro) 노드 정보인 node feature 는 multi layer perception , (macro) 그래프 구조 정보인 graph topology 정보는 logistic regression 으로 학습해줍니다. 이 후, 두 결과물들을 concat 해주고 다시 한 번 multi layer perception 에 태워줍니다.

• 위의 과정인 2 sub-layer(MLP , logistic regression) 으로 나누어 준 이유에 대해 의아하신 분들이 계실텐데요. 논문의 핵심입니다. 쉽게 말해보면 , 동일한 데이터셋이긴 하나 MLP, logistic regression 으로 부터 도출된 값들이 각각 다른 context 를 지녔을거라는 이야기죠. 멀티모달 러닝의 핵심과도 비슷한 맥락입니다.

• 정리해서 말씀드려보자면, homophily 에 의존적인 데이터들은 주변 이웃의 정보로부터 많은 영향을 받는다는 문제를 해결하기위해, 노드의 정보와 그래프 구조적 정보를 각각 독립 적용한다는게 본 아이디어의 핵심이라고 보시면 될 것 같습니다.

• 참고로, 제안한 모델이 non-homophily 에서 효과적임을 증명하기 위해 데이터셋이 homophily 인지 아닌지를 판단해야 할 텐데요. 그 과정에서 기존 homophily measurement 의 방식인 null-model의 randomly wired을 활용한 방식이 아닌 degree 를 활용합니다. ‘The sensitivity of edge homophily to the number of classes and size of each class limits its utility.’ 를 극복하기 위해서 변형했다고 하네요.