Chapter19. Applications of Graph Neural Networks

투빅스 13기 이예지

마지막 강의는 지금까지 다뤘던 GNN이 다양한 도메인에서 어떻게 활용되고 있는지 살펴본다.

크게 3가지에 대해 다룬다.

추천시스템에서 GNN의 활용
Heterogeneous Graph에 GNN의 활용
분자구조에서 부작용(side-effect)을 찾기 위한 GNN의 활용

PinSAGE: GNN for Recommender System

핀터레스트(Pinterest)의 데이터를 활용한 graph-based recommendation이다. 우버이츠에서도 사용되고 있다고 한다. 즉, 실제 산업에서도 추천시스템에 graph-based rec을 활용하는 경우는 생각보다 많다.

우리는 set of users가 어떤 set of item과 interaction을 하고 있는지 알 수 있다. ex) 어떤 영화를 봤는가 , 어떤 상품을 샀는가, 어떤 음악을 들었는가

이 데이터를 활용하여 우리는 개인화된 추천을 하고싶다. 즉, 유저가 볼만한 영화, 살만한 음식, 들을만한 음악을 찾고싶다.

간단히 생각하면, 고객 X가 Metallica와 Megadeth CD를 샀다면, Metallica를 산 Y 사용자에게 Megadeth를 추천해줄 수 있을 것이다.

Figure 2에 있는 아래 그림을 보자. set of users와 set of items이 있을 때, 새로운 user가 지고 어떻게 interaction을 하는지에 따라 new item을 추천해줄 수 줄것이다.

우리가 하려고 하는 것. Q를 했을 때 RECOMMENDATION을 해주는 것.

결국, 우리는 Query를 했을 때 set of items을 추천해주는 것이다. (유저가 선택한 item을 알려줬을 경우(q) set of items(rec)을 내뱉는 것.)

Define

이 때 item이 아니라 items가 주어졌을 경우, set of relative items(rec)을 해주는 것이 최종 목표이다. (given a set of query items, retrieve relative items )

Figure 4를 보면, 실제로 굉장히 비슷한 아이템들이 추천되고 있음을 알 수 있다.

그렇다면 서로 다른 아이템에 대해 "비슷하다"는 정의를 어떻게 할까?

일반적으로 다음과 같이 두가지로 정의된다.

content-based item의 feature를 사용하여 가장 유사한 아이템을 추천해줌. ex) 이미지, 텍스
graph-based (collaborative filtering) user와 item 간의 interaction을 bipartite graph(이분 그래프)로 나타냄. user가 주어졌을 때, 나와 비슷한 items을 좋아하는 유저를 찾고, 그것을 based로 하여 추천해줌. 여기서 item의 feature 자체가 중요한 것이 아님. 나와 비슷한 것을 좋아하는 user가 중요함

Recommendation을 하기위해 3가지가 필요하다.

Collect data 유저가 어떤 노래를 좋아하는지 어떤 노래를 싫어하는지 알아야 함.
Prediction problem user가 unknown item에 대해 얼마나 좋아할지를 predict해야 함.
Evaluating methods 내 method가 얼마나 성공적인지를 평가해야 함.

따라서, 위의 3가지를 어떻게 하는지 살펴보자.

우리는 두가지를 얻을 수 있다.

features: 각각의 pin(node)에 대한 이미지와 텍스트 정보 등등

graph: user와 item의 interaction. 그리고 이 interaction은 dynamic하게 changing 됨.

이제 이 데이터로부터 predict를 하기 위해 우리는 item을 임베딩한다. 임베딩을 하면 고차원 공간에 각각의 item이 point로 존재할 것이고, relative item들은 이 공간에서 매우 가깝게 맵핑되어 있을 것이다.

즉, 고차원에 item들이 point로 존재하고, 내가 collect한 아이템과 가까운 point를 추천해주면 되는 것이다. 다음의 예시를 살펴보자.

Query로 어떤 케이크가 주어졌다. 우리는 스웨터보다, 또 다른 케이크를 추전하는 것이 더 올바른 추천일 것을 알고 있다. 그렇다면 오른쪽의 식이 이해될 것이다. 여기서 $d$ 는 distance를 의미한다.

임베딩 공간에서 (cake1과 cake2)의 거리보다 (cake1과 sweater)의 거리가 더 커야할 것이다.

우리의 가정에 맞게 임베딩을 하기 위해 GNN을 써보자.

bipartite graph가 주어지고, 이 때 input으로 item(circle)들은 이미지만 사용하는 것이 아니라 관련 feature들을 사용한다. (오른쪽의 circle은 이분 그래프에서 item을 의미함.)

이제 cake1과 cake2를 임베딩해보자. 우리는 cake1과 cake2의 거리 $d(z_1, z_2)$ 가 매우 작기를 바란다. 이때, 오른쪽 그림을 보면 cake1을 임베딩하기 위해 자기 자신만 사용하는 것이 아니라 이웃들까지 같이 활용하고 있는 것을 볼 수 있다.

Key idea 케이크1을 임베딩하기 위해 내 피쳐만 사용하는 것이 아니라, 내 이웃들의 피쳐까지 함께 사용해서 임베딩함.

그렇다면, 위의 그림처럼 그래프로 이 문제를 푸는 것이 잘 작동할까...?

전통적으로 비슷한 아이템을 추천하는 것(content-based), 어떤 아이템과 내가 산 아이템이 얼마나 유사한지에 대해 추천해주는 것은 한계가 있다. 예를 들어 울타리 사진이 Q로 주어졌을 때, 비슷하게 생긴 침대를 추천해줄 때가 있다. 그러나 그래프를 활용하면, 주변 이웃 정보에 따라 울타리의 임베딩 파트가 있고, 침대의 임베딩 파트가 따로 존재할 것이다. 이 때문에 전통적 추천 시스템에서 발생하는 실수의 확률이 적다.

PinSAGE의 pipeline

데이터 수집 가장 먼저 training data를 수집해야 한다. 이 때, positive pair와 negative pair를 수집해야 한다. - positive pair

매우 짧은 시간 안에 동시에 수집된 것을 related item이라고 정의한다. - negative pair random으로 수집한다.

trainset에 존재하는 노드(pin) 임베딩을 위해 GNN을 학습시킨다.
모든 pin에 대해 임베딩 값을 한다.
nearest neighbor search를 통해 추천해준다.

모델 학습을 위한 objective function은 다음과 같다.

positive data에 대해 가깝게 임베딩을 해야하며, negative data에 대해 멀리 떨어져 있어야하므로 cosine similarity(element-wise)를 구하여 objective function을 만들 수 있다.

따라서 다음과 같이 구성되어 있다.

positive pair: 우리가 현재 가깝게 하고자 하는 pair이고, negative example보다 크게 만들어야 .

negative example: 우리는 이것을 작게 만들어야 . (random set이므로 example이란 말이 붙는 것 같다.)

$\Delta$ : margin으로 불리며, positive pair과 negative example보다 최소한 이것보다 커야한다를 주기 위함. 즉, objective funition을 최소로 만드려면 max(0, something)이 0이 나와야하고, something부분이 0이 나오려면 $-z_u^{\intercal}z_v+z_u^{\intercal}z == \Delta$ 가 만족되어야 . 따라서 델타가 margin으로 불림.

four key innovations

on-the-fly graph convolutions 임베딩해야 하는 노드가 정해지면, dynamically small computation graph를 생성함(mini-batch). computation graph에 없는 노드들을 굳이 볼 필요가 없으므로, parallel하게 processing 될 수 있음.

2. selecting neighbors via random walks degree가 매우 높은 이웃이 있을 경우, 그 이웃의 모든 정보를 aggregate할 필요는 없음. 따라서 aggregate할 노드를 정하기 위해 page-rank를 사용할 수 있음. 따라서 most important pin의 정보가 aggregate 됨. 👉 나의 node로부터 random walk를 출발하여 등장하는 노드들에 대해 counting을 하게 됨. 여기서 top k nodes를 뽑고 normalize를 한 뒤 importance의 weight로 사용함.

3. efficient MapReduce inference 같은 계산을 여러 번 하는 computation redundancy를 줄이기 위해 값을 저장해놓고 참조함.

Negative examples

harder negative examples을 고르는게 핵심이다.

위의 그림처럼 positive pair가 주어졌다고 생각하자. 우리는 negative sample을 뽑아야 한다. 오른쪽의 아이템 중 어떤 것을 negative sample로 만들어주는 것이 좋을까?

모자를 negative sample로 할 수도 있겠지만, 이 경우는 모델이 너무 맞추기 쉬운 case라고 할 수 있다. 따라서 모델이 맞추기 어려운, postive sample과 유사하지만 그렇다고 너무 relative하지 않은 sample을 negative sample로 하면 어떨까? 이런 example을 보통 harder examples이라고 하는데, 이것을 negative sample로 활용함으로써 모델은 더 좋아질 것이다.

그렇다면 어떻게 이러한 negative sample을 만들 수 있을까? 단순히 생각하면 전체 item을 sorting한 후, rank를 구할 수 있을 것이다. 그러나 이건 computationally hard이다. 이를 해결하기 위해 우리는 random walk를 사용할 수 있다. random walk를 활용해서 완전히 관련없는 negative sample 대신, more related example을 뽑는 것이다.

Evaluation

평가 지표로 Hit-rate와 MRR이 사용된다.

Mean Reciprocal Rank(MRR): first relevant recommendation을 찾는다.

Hit-rate: prediction 값들 중 실제 relevant item이 몇 개 있는지 계산한다.