1월 1주차 그래프 오마카세
Scalable Graph Transformers for Million Nodes
• 글 서두부터 graph transformer 와 graph neural network 의 차이점인 “whether is the resorting function the message or not” 을 언급하면서 이야기가 진행됩니다.
• message passing 을 hopbyhop으로 진행하며 information resort 가 필요한 gnn 대비(local feature aggregation), all feature aggregation 이 가능한 graph transformer 는 local + global feature aggregation 이 모두 가능하단거죠. 이를 통해, over-squashing 문제와 graph task flexibility 에서 강력하다라고 말합니다.
• 허나, 간단하게 생각해보면 모든 노드들로부터 정보들을 가져와야하기에 연산량 문제(query , key , value 계산을 위한 O(N^2) )에 부딪히게 됩니다. 그 문제를 해결하기 위해 random freature map 과 Gumble-softmax 의 장점을 활용한 NodeFormer 라는 아이디어를 제시합니다.
• 구체적으로는, Performer [논문원문] 라는 아이디어에 Gumble-softmax 를 활용했다고 보시면 될 것 같습니다. 자세한 설명은 Performer[설명] 에 있습니다. 커널 트릭을 RFM 에 접목해서 공간 복잡도를 줄인 아이디어가 핵심인 아키텍쳐입니다.
• 또한 , Global adapative 방식으로 정보를 추출하는만큼 중요한 요소들을 쏙쏙 골라보기 위해(informativeness) Relational Bias 와 Edge regularization loss를 활용합니다. 요약해보자면 , attention score 를 잘 활용해보겠다. 라는 아이디어입니다.
• 논문을 구체적으로 이해하기 위해서는 Transformer, Performer , gumble-softmax , etc.. 수학적인 테크닉이 많이 반영되어있기에 , 이런 아키텍쳐가 있구나~ 그래프의 global feature 를 반영하기 위해 다양한 시도들이 있구나 라는 측면으로 가볍게 보시는걸 추천드립니다.
BGL: GPU-Efficient GNN Training by Optimizing Graph Data I/O and Preprocessing
• GPU-efficient 를 위해 feature retrieving 과 subgraph sampling(neighborhood sampling)을 어떻게 할것인가에 대해 기술한 논문입니다. 구체적으로는 data I/O size (batch 마다 subgraph 를 가져오고 , 그 subgraph 의 node feature를 가져와야함)는 굉장히 큰 반면에, 모델 (GraphSAGE는 node sampling 이후 mean 등 parameter 가 적음.)은 가볍다. 그렇기에 huge gap 이 발생하면서 효율적으로 연산하지 못한다 라는 것을 문제로 정의하고, 그것을 해결하기 위한 방식을 제안합니다.
• feature 를 효율적으로 다루기 위해 cache engine(policy) 을 tunning 했습니다. 기존 모델(pinterest , PaGraph) 들은 hottest node feature 를 Cache 에 저장하고 활용하곤 합니다. 이 때, static 방식으로 적용하기에 ,cache hit ratio 의 효율이 저조하다는 것을 문제로 지적하며, dynamic 방식으로 튜닝해서 적용합니다. 결과를 비교하기위해, amortized analysis 를 진행합니다. 그리고 그에 대한 결과를 해석하며 cache engineering 이 어떻게 왜 중요한가에 대해서 언급합니다.
• graph partitioning 알고리즘을 제안합니다. 심플하게는 , cpu & gpu 를 cross-partitioning efficient 해주기위해, 1. multi-level coarsening (HDFS 에서 random sampling , generation ) 2. assignment(sampling 된 node in block 들을 assign) 3. uncoarsening(assignment 과정이 끝난 generated node를 실 original node와 맵핑) 의 과정으로 이루어집니다. 심플하게는 학습을 위한 random sampling 을 HDFS 에서 진행한다 라고 보시면 될 것 같습니다.
• 마지막으로는 , 데이터간의 송수신을 효율적으로 하기위해, network PCIe cpu gpu resource allocation에 대해서도 언급하고 개선 아이디어에 대해 이야기합니다.• baseline 으로 Euler , DGL , PyG 3가지 프레임워크 설정하여 실험했습니다. 내용이 워낙 방대하고, 컴퓨터 공학에 대한 사전지식이 많이 필요하여 읽으실 때 다소 지루하시고 어렵다고 생각하실수도 있겠습니다. 허나, 그만큼 최적화에 대한 지식을 잘 나타낸 아이디어로써 충분한 가치가 있기에 graph , scalability 등에 관심 있으신 분들은 읽어보시는걸 추천드립니다.
Using Graph Learning for Personalization
• Graph 를 Recommender system 에 적용하면 어떤 점이 유리한지 그리고 해외 유수 기업들은 어떻게 적용을 하고 있는지에 대해 친절하게 설명되어 있습니다.
• why GNN 에 대해 다음 3가지 이유를 들어 주장합니다.
1. Models require fixed data input, which ignores the underlying relational structure in the data
2. Models are extremely sensitive to new data
3. Models are rigid, with limited adaptability to new predictions or use cases
• GNN 이 많은 관심을 받고 있는데 왜 유독 추천시스템에서 많이 언급되는가? 라는 호기심이 있으신 분들에게 추천드립니다. 수식같은 수학적 요소를 최대한 배제하여 글로 잘 풀어낸 포스팅이기에, 읽는데 큰 불편함은 없을거라 생각됩니다.
Chartalist: Labeled Graph Datasets for UTXO and Account-based Blockchains
• Blockchain , cryptocurrency analysis 의 관심이 커져가며 graph application 한 축에 블록체인이 자리매김하고 있습니다. 블록체인의 transparency database 의 형태가 결국 linked list 이기에, 연결로써 자산들의 흐름들을 분석할 수 있다는거죠. 그리하여, graph 의 장점인 노드-노드 를 지갑-지갑 등으로 맵핑해서 활용하면 효율적이기에 주로 graph 측면으로 접근하곤 합니다.
• 주로 연결은 UTXO , Account-based 2가지로 나뉘어서 발생합니다. 자세한 내용은 논문에 설명이 되어있습니다. Account-based 개념은 저희가 주로 이용하고 있는 송금 이벤트랑 동일한 형태이나, UTXO는 다소 새롭습니다. 그렇기에 약간의 공부?가 필요할수도 있습니다.
• blockchain industry 에서는 모든 정보가 투명하게 웹에 공개되어있습니다. 허나 어떤식으로 접근할지 , 어떤 task를 적용해야할지 , 어느 feature를 활용해야하는지 , 학습 추론을 위한 labeling , large dataset , api limitations 등을 많이들 고민하시곤 하는데요. 그 고민에 대한 해답들이 본 논문에 잘 나와 있습니다.
• blockchain 또한 financial network 와 money send, receive 하는 행위를 다룬다는 점에서 비슷한 성격을 띄기 때문에, financial network analysis 를 해보고싶었으나 여러 한계들 때문에 보루하셨던 분들에게 좋을것 같습니다.
ItemSage: Learning Product Embeddings for Shopping Recommendations at Pinterest
• 산업에서 적용하고 있는 gnn 의 대표적 사례인 ‘PINSAGE’에 대해 다들 알고 계실텐데요. 그 모델을 좀 더 향상시키기 위해 트랜스포머 구조를 차용한 아이디어입니다.
• 간단하게 기존에는 image embedding 만을 활용했다면 , 본 아이디어에서는 SearchSage라는 구조를 활용해서 text 를 추가적으로 임베딩해줍니다. 그래서 PINSAGE output + SearchSage output 을 결합해서 [CLS] token에 context를 반영해주고, 그 context들 간의 similarity 를 통해 추천을 해준다는 아키텍쳐입니다.
• 주의깊게 보시면 좋을 부분은 1. multi-task learning (각기 Task들을 결합하여 추천성능 향상시키는 기법) , 2. 고차원의 text 를 다루기 위해 적용한 Hash embedding , 3. user engagement 를 어떻게 capture 하는지에 대해서 ( 구체적으로는 , 주로 heterogeneous context 를 반영하기 위해 주로 Knowledge graph embedding 방법을 사용하곤 했는데, 여기에서는 어떻게하였는가? ) 들이 될 것 같습니다.
• 앞선 결과들로부터 실험결과 unified (모든 feature들을 모두 결합한것) 모델이 뛰어난가? 만약 그렇지않다면, 어떤 이유에서 그럴까? 하는 논문의 해석을 유심히 보신다면 좋은 인사이트를 도출하실수 있을거라 생각됩니다 🙂
Next-item Recommendation with Sequential Hypergraphs
• 오랜만의 하이퍼그래프 관련 논문입니다. 추천 영역에서 하이퍼그래프가 어떤식으로 활용이 되는지를 기술하고 있습니다. 다양한 적용방식이 있겠으나, 본 논문에서는 유저의 행동 발생 전/후에 대해서의 중요성에 대해 언급하며, 그 전/후(window , Time Granularity) 를 파악하는게 핵심이며, 그 context를 하이퍼그래프를 통해 추출하는것이 좋다 라고 주장합니다.
• 그 이유로는 그래프는 1:1 pair-wise 인 측면으로 접근한다면 그 순간의 맥락만을 sequential 하게 임베딩함으로써 내부의 전후맥락 반영하기엔 부족하다. 반면, 하이퍼그래프는 1:N 을 관찰할 수 있는 hyperedge를 통해 해당 시점에서 발생한 모든 행동들을 co-occurrence 측면으로 볼 수 있기에 반영하기에 유리하다. 라는 식으로 논리를 풀어가고 있습니다.
• 요즘, sequential recommender 이 많이 보이고 있는데요. 최근 wsdm , www challenge 에서도 Task 의 한 축으로 자리매김할 정도로 산업에서의 니즈가 많아보입니다. 상식적으로 그 유저의 맥락이 시시각각 변동되기에 dynamic embedding이 static embedding 보다 유리해보이겠으나, 실상 리더보드를 보면 상위권에 속해있는 방법론들은 모두 static embedding(LINE , graph transformer 등) 인 결과를 보면, 이 역시도 아직까지는 개선의 여지가 많이 있어보입니다. 여러분들이 개척해보시면 어떨까요?!