[Graph Convolutional Neural Networks for Web-Scale Recommender Systems] 번역 & 리뷰
원문 보기 : https://arxiv.org/abs/1806.01973
Graph Convolutional Neural Networks for Web-Scale Recommender Systems
Recent advancements in deep neural networks for graph-structured data have led to state-of-the-art performance on recommender system benchmarks. However, making these methods practical and scalable to web-scale recommendation tasks with billions of items a
arxiv.org
0. Abstract
최근 추천시스템에서는 기존의 CF, W2V 기반의 방법에서 발전한 그래프 자료구조에 기반한 뉴럴 네트워크가 state-of-the-art 로 자리잡아가고 있는 추세이다. 본 논문에서는 Pinterest에 적용된 추천 엔진의 large-scale 기술을 소개할 것이며, PinSage 라고 부르는 random walk, graph convolutions 기반의 임베딩 방법을 소개한다. PinSage는 노드 단위와 그래프 단위의 vector 표현 모두에 좋은 효과를 보였다. 기존의 GCN과 다른 점은 앞서 말한대로 random walk를 적용한 부분인데, 이의 성능에 대해서도 언급하고자 한다. 그리고 PinSage는 무려 3억개의 Node와 18억개의 Edge를 가진 7.5억개의 학습데이터를 만들어 학습하였다.
1. Introduction
그래프 기반의 딥러닝 임베딩 모델, GCN은 기존의 추천시스템에서 가장 널리 사용되는 CF(collaborative filtering) 방식을 아주 훌륭하게 대체할 수 있었다. 이를테면 item 임베딩을 통해 item to item 추천에 사용할 수 있으며(Similarity), 기존의 Latent Factor 보다 더 좋은 성능을 보였다. 그리고 GCN의 핵심 아이디어는 local graph의 neighborhood를 Convolutional NN 구조로 aggregate 하는 것이다.
GCN은 위와 같은 구조를 가지는데, 여기에서 'convolution' 한다는 것은 one-hop 거리에 있는 neighborhood 노드들의 정보를 aggregate 한다는 것이다. 그리고 이러한 구조의 depth가 여러 개가 되면 stacked convolutions가 되는 것이다. 이러한 구조는 추천시스템에서 새로운 standard가 되어가고 있지만, real-world 에서 extra ordinary한 적용사례를 완성시키지는 못했다(논문을 쓸 때 기준으로, Pinterest가 GCN을 Lage-scale에서 제대로 적용한 첫 사례인 것으로 이야기하고 있음). 문제는 3억개의 nodes와 18억개의 edges를 어떻게 GCN 구조로 학습시키고 서비스하느냐이다.
- On-the-fly convolutions
일반적인 GCN은 Laplacian Matrix를 활용하여 convolution을 수행한다. 이에 반해 PinSage는 localized convolution을 수행하는데, 인접 노드 중 일부만을 샘플링하여 computation 그래프를 다이나믹하게 생성한다는 것이 다르다.
- Producer-consumer minibatch construction
stochastic 하게 학습하기 위한 미니배치 구조를 디자인했다고 한다. 당연한 부분이지만, 워낙에 Large scale이니 이 부분을 다시 한 번 강조한 듯 하다.
- Efficient MapReduce inference
모델 학습 자체를 분산으로 했다는 것은 아닌 듯 하고, 학습된 GCN 모델로부터 embedding을 생성하는 파이프라인을 분산 구조로 처리한다는 것 같다.
- Constructing convolutions via random walks
Laplacian Matrix로 Global하게 계산하지 않고 Localized를 사용한다고 해도, 여전히 인접 노드에 대한 샘플링은 필요하다. 여기서 서두에 언급한 Random walks 방법으로 샘플링을 한다. 단순 랜덤 샘플링보다 좋다는 점에 더해, 이 방법으로 샘플링을 하면 pooling/aggregation 단계에서 사용할 수 있는 Importance score를 얻을 수 있다는 장점이 하나 더 생긴다고 한다.
- Importance pooling
Graph convolution 구조에서 가장 중요한 요소는 인접 노드의 피처를 aggregation 하는 것이다. 본 논문에서는 aggregation 과정에서 노드 피쳐의 Importance를 더 잘 캐치하는 방법으로 random walk similarity measure를 사용했다고 한다.
- Curriculum training
curriculum training 방법으로 학습해 더 나은 학습 결과를 얻었다고 한다.
2. Related Work
그래프 기반의 DNN은 꽤 오래 전부터 연구된 주제이고, 최초의 접근법은 'message-passing' 방법이다. (이와 관련된 내용은 이전의 논문 리뷰에 설명해 두었다) 그러나 이 방법은 Large scale 에서는 별로 좋지 못한 방법이다. 하나의 shared parameter로 수억 개의 노드와 엣지를 순차적으로 돌아다닐 순 없기 때문이다. 그 후에 Convolutional 개념이 도입되면서 많은 단점이 개선되고, state-of-the-art 알고리즘이 무수히 만들어졌다. 그러나 연구 결과와는 별개로, product 레벨에서 성공적인 그래프 기반 알고리즘은 사용된 적이 없었다고 한다. 그 한계점은 기존 알고리즘들이 공통적으로 Graph Laplacian 방식으로 학습했기 때문이다. 본 논문은 그 문제를 해결하려고 애썼으며, 가장 가까운 연구 결과로 GraphSAGE(2017)을 꼽았다. GraphSAGE 역시 Graph Laplacian 구조를 탈피하는 것이 가장 큰 목적이었기 때문이다. 그러나 GraphSAGE 역시 모든 전체 그래프의 정보가 GPU memory에 올라간다는 단점을 가지고 있었기 때문에, random walks로 이마저도 보완하는 것이 목표였다고 한다. 참고로 node2vec이나 DeepWalk 와 같은 논문의 방법은 이곳에 적용될 수 없다고 하는데, 그 이유는 그 논문들은 Unsupervised를 가정했을 뿐만 아니라, 노드의 피처를 포함하지도 않았으며(단순히 노드간의 관계성과 관련된 피쳐만으로 임베딩한 알고리즘), 임베딩에 필요한 파라미터가 노드 수에 따라 linear하게 증가하기 때문이다.
3. Method
전체 과정 중에서 가장 중요한 키워드를 하나 꼽자면, "notion of localized graph convolution"이라고 한다. 특히나 이러한 지역화된 convolution에서 사용하는 파라미터는 모든 노드에 공통적으로 적용되는 방식으로 설계되었기 때문에 그래프의 크기와 상관없이 독립적으로 파라미터의 complexity를 조절할 수 있게 되었다.
3.1 Problem Step
문제 정의는 명확하다. 질 높은 embedding representation을 pin 단위로 만들어내는 것이 목표였고, 이를 위해 bipartite graph에 I, C라는 두 개의 개념을 생성했다. I는 pin의 집합이고 C는 board의 집합이다. I는 일종의 item set으로 간주할 수 있고, C는 User-defined collection으로 간주할 수 있다. 여기서 그래프 내의 전체 노드 V는 I와 C의 합집합으로 간주할 수 있다. pinterest 에서는 핀과 보드를 그다지 엄격하게 분리하지 않았다고 한다. 마치 배달앱에서 레스토랑도 추천하고, 메뉴도 추천하는데 그 성격이 유사한 것과 비슷한 느낌인 것 같다.
3.2 Model Architecture
기본적으로 Forward propagation algorithm의 형태이며, 위의 알고리즘과 같이 표현할 수 있다. 앞서 살펴본 그림 1에서 이 구조를 그대로 찾아볼 수 있다. 이 과정에서 몇 가지 특이할 사항은, concat 함수를 쓰는 부분에서 average 같은 함수도 써봤지만 concat이 경험적으로 더 좋았다는 것과, output으로 나온 임베딩 벡터를 한번 더 normalize 하면 더 좋은 성능을 냈다는 것이다.
모델 구조의 또 하나의 특징은 Importance-based neighborhoods 이다. 위에서 여러 차례 이야기했지만, GCN 구조는 노드 u의 k-hop 위치에 있는 모든 인접 노드를 활용하는 구조이다. 이 노드들을 효과적으로 샘플링하기 위해, 노드 u에서 random walk를 통해 인접 노드로 visit count를 만들고 L1-norm을 적용했다고 한다. 이렇게 만든 스코어를 importance score로 활용한다. 즉, 노드 u의 이웃은 노드 u에 가장 큰 영향을 미치는 T 노드로 정의된다는 것이고 영향을 미치는 기준을 정렬하는 것이 importance score이다.
이런 구조는 크게 두 가지 장점을 가지는데, T에서 정해진 숫자의 인접 노드만 가져옴으로써 노드가 너무 많아지는 경우에 생기는 메모리 문제를 해결할 수 있게 된다. 두 번째는 importance score를 aggregating에 활용할 수 있다는 것인데, 위 그림의 알고리즘에서 symmetric vector function의 역할을 하는 함수에 weighted-mean을 사용함으로써 importance pooling 이라는 새로운 개념을 만들어낼수 있다는 것이다.
모델 구조에서 언급하는 마지막 특징은 Stacking convolutions로, 요약된 단어만 보고도 내용에 대한 유추가 가능하니 생략하도록 하겠다.
3.3 Model Training
모델 학습 알고리즘은 아래와 같다.
Loss function은 max-margin ranking loss를 활용했다고 하는데, 아래의 수식을 보면 쉽게 이해할 수 있다. 수식에서 q에 해당하는 것이 similarity 대상이 되는 query vector이고, i가 이에 연관된 벡터, 그리고 Pn(q)로 되어있는 것이 negative sample이다. 따라서 연관 샘플의 inner product 값이 negative 샘플의 inner product 값보다 클 수록 loss가 감소하는 모양이 된다.
논문에서 언급하는 related items는 supervised인 것으로 보이며, 즉 pinterest에서 유저가 한 보드에 모아놓은 핀들은 '연관성이 있다' 라는 label true=1 로 보인다. negative example은 어떻게 샘플링 한 건지는 모르겠지만, 역시 서비스 구조에 기인하는 것 같다. 앞선 장에서 언급했던 내용(unsupervised한 임베딩을 하지 않는다)과 일치하는 부분이다.
그리고 Large-scale 상황에서 학습하는 몇 가지 포인트에 대해 언급하였는데, 첫 번째는 Multi-GPU training이다. mini-batch를 활용해서 아래와 같은 구조로 전체 데이터를 학습한다.
여기에 Producer-consumer mini-batch 라는 구조를 활용한다.
adjacency list와 수억개 노드의 각 피처들은 어마어마한 메모리를 필요로 하기 때문에, 모두 CPU에 올라가 있다. 반면 convolution 이후의 스텝은 각 GPU에서 수행하기 때문에 GPU는 CPU에 있는 메모리에 접근해야만 한다. 그러나 이런 방식은 비효율적이기 때문에 re-indexing이라는 방법을 사용한다. re-indexing은 노드와 인접노드를 포함하는 sub-graph를 생성하는 기법인데, 여기에서 말하는 re-indexing이란 GPU로 전달된 미니 배치 그래프를 의미한다. 즉, 원래는 CPU에서 global하게 사용하는 adjacency list와 feature matrix을 각 GPU에서 수시로 가져가는 대신, 미니배치를 만들어낼 당시에 local adjacency list와 mini feature matrix를 생성하여 GPU로 전달한다는 것이다. 이는 CPU와 GPU간의 overhead를 방지하여 GPU의 utilization을 극대화 할 수 있다고 한다.
정리하자면 GPU는 모델 구조에 정의된 내용을 학습하고, CPU는 feature extract, re-indexing, negative sampling (with mini batch) 등의 일을 수행한다. (또한, OpenMP를 사용하여 CPU가 일을 분배하는 방식까지 최적화한다)
이제 마지막으로 Negative Sampling 방법에 대해 알아보자. 우선 large batch size에서 학습할 때 효율적으로 활용하기 위해 각 미니배치마다 500개의 negative 샘플을 뽑았고, 해당 500개는 미니배치 안의 모든 학습 데이터에 공통적으로 활용되는 샘플이다. 이렇게 하면 효율은 극대화되지만 성능은 아무런 차이가 없다고 한다.
하지만 이렇게 학습시키는 것은 "너무 쉬운 학습"이라는 단점이 있다. 수 억 개의 노드 중 500개의 노드만 negative로 선정하고, 이를 미니배치 내의 모든 학습셋에 적용하는 것은 타당하다고 보기는 힘들다. pair of item (q,i)로 다시 돌아가 보았을 때, 고작 500개를 뽑았다고 할 때 q와 negative sample인 i가 조금이라도 연관이 있을 확률은 매우 낮다. 즉, 대부분의 negative 샘플이 q와 아무런 연관이 없을 확률이 높기 때문에 너무 쉬운 학습이라는 것이다. 이는 추후에 similarity를 계산할 때, 아주 유사한 항목과 대강 유사한 항목을 구분하지 못하게 될 가능성이 높아지게 된다.
그래서 학습 시에 "hard negative" 샘플을 추가한다(이하 hn). hn을 추가하는 방법은 입력 쿼리 q와 유사한 샘플이지만 positive i 만큼 유사하지는 않은 샘플을 의미한다. 이를 뽑는 방법은, 그래프 데이터의 PageRank 스코어(item q의 스코어)를 이용하는 것이다. 이를 기준으로 약 2000~5000등 정도 되는 랜덤한 샘플을 뽑으면 hn 샘플이 된다.
hn 샘플링을 통해 학습하면 수렴에 필요한 epoch가 두배가 된다. 더 어려운 학습이기 때문이다. 따라서 이를 줄이기 위해 curriculum training scheme라는 것을 사용했다. curriculum training은 첫 epoch때는 hn을 사용하지 않아서 대략적인 parameter를 빠르게 찾은 후에 이어지는 epoch에는 hn을 추가하여 더 정밀하게 학습하는 것이다. 비유하자면 문제집을 풀 때 쉬운문제는 몇 개만 풀어서 빠르게 넘기고, 어려운 문제만 공략하는 것이다.
3.4 Node Embeddings via MapReduce
모델이 학습된 후에는, 몇 억 개의 노드마다 embedding을 generate 하는 문제가 남아있다. 앞서 살펴본 알고리즘을 그대로 구현한다면, 하나의 노드의 embedding을 generate 하기 위해 k-hop neighborhoods를 iteration 하면서 반복적으로 무언가를 계산해야 한다. 그래서 이를 효율적으로 계산하기 위해서 MapReduce를 활용하고자 했고, 내용은 다음과 같다.
4. Experiments
실험에 대한 내용은 이 글에서는 생략하도록 하겠다 (3.5에 Approximate Nearest Neighbor looksup에 관한 내용도 나오지만, 이 역시 생략한다)