Review _ Food Discovery with Uber Eats: Using Graph Learning to Power Recommendations
https://eng.uber.com/uber-eats-graph-learning/
' recommender system + graph neural network ' 기업 사례 _ Uber
Graph learning in a nutshell
The representations that we learn from graphs can encode properties of the structure of the graph and be easily used for the above-mentioned machine learning tasks.
i.e.) to represent an eater in our Uber Eats model we don’t only use order history to inform order suggestions, but also information about what food items are connected to past Uber Eats orders and insights about similar users.
--> feature 내의 다양한 관계를 연결하여 모델링 해보고자 함. 모든 representation learning 의 필연적인 과제이지 않을까 싶은데 Graph data 에서는 RDB 와 다르게 데이터간의 관계를 유동적으로 연결하여 edge내에 정보(weight 형식으로 )를 전달 하는 개념이라 좀 더 효율적이라 생각하는 거 같다. ( meta-path etc...)
meta-path 내에서도 manually 하게 path 를 지정해줘야 하는 문제가 있었는데 그 한계점을 GTN 이 해결해보고자 하였음. 이 것에 관해서는 향후 다뤄보겠습니당.
overall graph properties divide into 2 things , one is undirected the other is directed graph and so this is 'undirected graph'
* including self-loop architecture
Layer 1 ; 1 hop
Layer 2 ; 2 hop
1. A node's feature extraction 을 하기 위해 breadth-first search 를 시행함. 대략 1, 2 hop 으로 나누어 진행하는데 본 포스팅에서는 2 hop 으로 진행함.
2. 그렇게 모인 feature 을 토대로 aggregation 하여야 하는데 이때 aggregation / pooling function 을 사용함.
+ Layer 1 에서는 A 의 neighboor 인 D C B 그리고 자기 자신 A ( 자기 자신을 하는 이유는 over-smoothing 방지 )
The main advantage of obtaining a representation in this manner is that it captures both the properties of node A and the structural information about its neighborhood, aggregating information about the nodes that node A connects to, as depicted in Figure 2, below:
앞선 과정을 통해 우리는 node A 의 고유 feature 그리고 연결된 주변 노드들로부터 structural information ( 즉 그 주변 노드들의 고유의 특성 ) 을 전달 받았다.
* Graph 데이터 구조와 기존 데이터 구조는 어떠한 차이점이 있으며 그에 따른 장ㆍ단점이 무엇인가에 대한 고민.
computation procedure 이 후 h^k_v(node representation) 를 통해 우리는 probability 를 예측하게 됩니다. 이 때 그 예측은 대략적으로 '두 노드 가 존재할 확률 ' 그리고
학습하면서 최대 / 최소화 해야할 loss function 으로는 대체적으로
' 두 노드가 실제로 그래프 내에서 연결 될 확률 '을 앞서 node representation을 통해 최대화
' 연결되지 않을 확률 ' 을 최소화 하는게 above notation의 목표 입니다.
GNN은 graph의 사이즈에 연연하지 않고 scalable 한 graph 에 대해서도 학습하기 위해서는 고정된 파라미터가 필요합니다. 여기서 말한 고정된 파라미터는 어떻게 보면 1-hop , 2-hop으로 진행하여 fixed parameter 이라 하지 않을까 조심스레 추측해봅니다.
더불어 저자가 말하기를 특정 노드의 표현을 얻을 때 인접 노드가 일정한 경우 그 '특정 노드'의 주변 이웃의 feature 로만 특정 노드를 inference 해가기에 neighboring 으로 new node 가 addation 할 때 inductive learning 할 수 있다 합니다. ( 구체적으로는 basic features 와 connection 을 통해서)
Graph learning for dish and restaurant recommendation at Uber
* 회전목마 형식으로 UI를 구축하여 유저의 선호를 토대로 recommendation list 를 제공합니다.
* 여기에서 추천시스템은 이전 주문과 유저 선호 데이터를 토대로 진행됩니다.
앞서 언급드린 추천시스템은 2가지 단계로 진행되며
1. candidate generation
2. personalized ranking
1. The candidate generation componet
scalable issue happen this stage -> 수 많은 자료들을 filtering 을 해야하며 더불어 음식점 내의 다양한 옵션들도 포함하여야 하기 때문에 그래서 pre-filtering 을 진행하는데 이때 주 factors 는 정확히 말하지 않았으며 포스팅에서는 간단하게 공간적인 정보로 진행한다고 함.
결론적으로 공간적인 정보인 (delivery range out etc..) 들을 토대로 filtering 함.
2. personalized ranker
이 때 ranking 은 추가적인 contextual informaiton 에 기반하여 하는데 이 때 말하는 info 예시로는 current day time location etc ... 우버 앱을 접속하였을 시 발생되는 기본적인 정보들 입니다.
예로 들자면 , 계속 반복되는 주문 패턴을 모델이 학습하여 user가 특정 날짜 특정 시간에 OO을 먹는다 등과 같은 예시입니다.
앞 선 전략을 토대로 모델 자체적인 (GNN) 의 추천성능을 높이고자 2개의 bipartite graph를 만들었습니다.
1. 유저와 음식을 노드로 표현합니다. 노드간에 연결되는 edge는 특정 음식에 대한 주문 여부 및 빈도를 함축함.
2. 유저와 음식점을 노드로 표현하여 엣지는 유저가 특정 음식점에 얼마나 주문했는지에 대한 정보를 함축하였음.
이렇게 raw 데이터를 graph 화 한 후 이러한 graph 구조 데이터를 representing 즉 embedding 을 어떤 모델로 할것인지 에 대해서는 GraphSAGE 모델을 사용하였음. 그러한 이유로는 scalability 에 대해 robust 하며 강력하다는 것에 초점을 두었기 때문 이다. 이 GNN 은 노드 정보와 유저 정보를 concatenation을 통하여 결합한다. 추가적으로 GraphSAGE 는 간단한 sampling 전략을 활용하여 node의 이웃 즉 정보를 aggregating 할 이웃을 1, 2 distance 로 한정지었다. 이러한 연유로는 앞서 언급한것과 같이 billions of nodes 분포에서 효율적으로 모델링을 하기 위함이다 ( scalability) 이는 최종적으로 better suggestion 을 가져온다고 함.
bipartite graph 를 GraphSAGE에 적용하기 위해 몇 일의 시간과 인내의 숲에서 머물렀다고 한다.
리뷰포스팅을 작성하는 저도 지금 이 과정을 거치는 중입니다 /......
1. 각각의 노드타입은 다른 features을 가질 수 있기에 우리는 추가적으로 projection layer 가 필요합니다 . (다양한 features를 aggregation 을 하기 위해) 구체적으로 다시 말씀드리자면 layer 에서 추출한 feature은 결론적으로 하나의 vector 가 될텐데 이 vector를 각각의 노드 타입( 위에서 bipartite 그래프를 만들 시 저희는 유저 - 음식 , 유저 - 음식점 을 설계하기로 했었죠?) 이 노드에 각각 함축하기 위해 size depending 을 해주는 layer 입니다.
예를 들자면 , dishes 는 그 음식의 description 혹은 associated image 와 같은 feature(그 음식에 대해 잘 표현할 수 있는) 에서 embedding 될 것이며, 음식점은 그 내의 여러 feature ( menu , cusine offerings ) 가 있을 텐데 이 representation 은 dishes 와restaurants는 각각 다른 요소로부터 feature을 도출하기 때문입니다. 즉 feature size가 다 다르죠. 하지만 이러한 size 를 unified 해주기 위해 projection layer가 존재합니다.
게다가 GraphSAGE는 edge의 feature을 [0,1] 즉 binary 로만 간주하기에 이것 또한 앞서 설계한 각 노드간의 관계를 잘 반영하기 위해 저희는 또 modify process를 진행해야합니다. 이러한 edge 를 잘 반영하기위해 본 포스팅에서는 new concepts를 제안하는데요. 바로 hinge loss를 활용하는 것입니다 .
--> a type of loss that fits the ranking of items with respect to the user better than using binary edges.
유저 u 가 음식 v를 적어도 한 번 주문 했을 때 , 유저 u 와 음식 v 간의 edge는 존재한다.
만약 우리가 이 노드 쌍의 스코어를 예측하고자 할 땐 동일한 유저 u 그리고 randomly selected node n 이 연결 되지 않았다 할 때 발생하는 그 스코어를 토대로 higher or lower 로 예측을 한다고 함.
* 0,1 binary 라 하였는데 어떻게 score를 예측하고자 하는지가 궁금함. 0.1 , 0.5 이렇게 formating 하여 주려나...?
이 loss의 문제점으로는 edges with a high weight , low weight 가 1번 구매 , 10번 구매한 weight에 대해 명확히 반영이 어렵다는 것이다. 단순히 구매 / 비구매 로만 나뉘어지기 때문에 . 이러한 한계점을 극복하고자 앞선 hinge loss에 아래와 같이 장치를 추가하고자함.
윗 그림은 어떻게 이 시스템이 low-rank positive 를 보완하였는지에 대해 나타낸다.
주어진 positive edge <u , v> , low rank positive <u , l> 여기서 u는 동일하나 각각의 Dish 에 대해 5 , 1 이라는 점수를 줌 .
기존 Loss 에 equation 을 하나 추가하는데 자세히 들여다 보면 higher rank , lower rank 간에 대해서도 margin constrain 을 줘서 앞서 언급한 빈도에 대한 difference를 추가하여 보다 weight 를 정밀하게 반영하고자 한다. 이 loss에는 또한 알파 값의 하이퍼파라미터가 있는데 이 것은 각 multiplier로 사용하여 relative importance 를 조정하는 역할로 쓰임.
마침내 , 이렇게 weight를 aggregation 하고 sampling 한 후에 얻어진 representation을 활용하여 각 노드간의 거리를 활용하여 그들 간의 거리를 근사화 , 유사도를 활용할 때 사용할 수 있따. 특별히 우리는 dot product 내적을 통해 유사도 거리 측정을 사용할 때 활용되는 코사인 유사도로 이 거리를 측정한다. 그리고 그들을 오프라인 , 온라인에서 테스트하여 그들의 accuracy를 결정한다.
우리의 recommending task에 지금까지 과정을 진행하며 도출된 embedding 값이 과연 유용한가? 를 측정하기 위해 우리는 4개월간의 historical data 를 특정 기간동안 나누어 훈련 하였다. test 시에는 특정 기간 이후 +10 day 에 주문한 내역을 예측하는 것으로 task를 잡았음. 특히 , 우리는 유저와 모든 음식 그리고 그 도시내에 있는 레스토랑의 유사도를 계산 , 유저가 주문한 음식 및 레스토랑에서 랭킹을 계산함.
To evaluate how useful the embeddings are for our recommending task, we trained the model on four months of historical data up to a specific split date. We then tested the model performance on recommending dishes and restaurants using order data from the ten days following the split date. Specifically, we computed the cosine similarity between a user and all the dish and restaurant embeddings in the city and computed the rank of the dish and restaurant that the user ordered. During the experiment we observed a performance boost of over ~20 percent compared to the existing production model on metrics like Mean Reciprocal Rank, Precision@K, and NDCG.
--> 해석이 번잡하여 원문 글을 가져왔습니다... 특히 computed 부분은 유의하여 읽으시면 좋을거라 생각됩니다! task !
* 여기에서 high low rank 의 기준은 ...?
personalized ranking model을 훈련할 때 그래프 임베딩 내의 유사도 feature을 토대로 진행하였는데 baseline 보다 AUC metric 토대로 측정하였을 때 12% 가량 boost 되었다고 합니다.
게다가 feature importance를 통해 나타난 결과는 다음과 같다고 합니다.
Data and training pipeline
/divider