[RecSys] GNN(Graph Neural Network) (1)

최근 Recsys 분야의 추천은 전통적인 CF(협업 필터링), MF(행렬 분해) 알고리즘을 넘어 딥러닝으로 확장되고 있는 추세이다. 최근 많은 기업에서 GNN(Graph Neural Network) 알고리즘을 사용하고 있으며, 사용자의 선호도를 그래프 구조로 파악하고자 하는 연구의 흐름을 보이고 있다.

 

본인도 RecSys 관련 프로젝트를 하나 기획하고 있는데, 관계나 상호작용과 같은 추상적인 개념을 다루기에 적합한 GNN 알고리즘을 사용해볼 계획이기에 정리해보고자 한다.

 

(Project 관련 자료는 나중에 한번에 정리해보겠다!)

 

GNN((Graph Neural Network)) 정리에 앞서 해당 알고리즘은 이름에서 볼 수 있듯 Graph 자료구조를 활용하는데, 우선적으로 Graph에 대한 정리를 한번 제대로 하고 가는 것이 이해에 도움이 될 듯하여 Graph 자료구조와 장점에 대해 우선적으로 살펴보겠다.

 

What is Graph?

 

그래프(Graph)는 정점(Node)들과 그 노드들을 잇는 간선(Edge)들을 집합으로 모아 구성한 자료 구조라고 볼 수 있다. Graph를 일반적인 수식으로 정리하면 아래와 같이 정리된다.

$$ G=(V,E) $$

여기서 V는 그래프를 구성하는 정점(node)의 집합, E는 두 정점(node)를 잇는 간선의 집합으로 보면 된다.

 

예를 들어 아래와 같은 이미지가 있을 때 수식을 다음과 같이 정의할 수 있다.

출처: 지그시 Tistory

 

$$G = (V, E)$$

$$V = (A, B, C, D, E)$$

$$E=(A, B), (C, D), (D, E)$$

 

정점(node)의 경우 한 시스템의 구성 요소(ex. 고객)을 의미한다고 볼 수 있고 간선(edge)의 경우 이러한 정점들 사이의 관계 또는 상호작용을 의미한다고 볼 수 있다.

 

Graph Type

출처: 지그시 Tistory

 

그래프 종류는 위와 같이 크게 6개로 분류된다. 우선적으로 언급하자면, GNN에 관해서는 방향 존재 유무에 따른 그래프 종류와 간선의 가중치 여부에 따른 그래프 종류, 그리고 이분 그래프 정도만 알고 있으면 된다.

 

정점들 사이의 관계를 어떻게 정의하는지에 따라 간선의 방향이 존재하는 방향 그래프(directed graph)와 방향이 존재하지 않는 무향 그래프(undirected graph)로 나눌 수 있고 간선에 가중치에 있느냐 없느냐에 따라 weighted와 unweighted graph로 나눌 수 있으며 형태에 따라서도 그래프를 단순 그래프와 다중 그래프, 이분 그래프, 루트 없는 트리로 구분할 수 있다.

 

위 사진에 DAG라고 하는 트리의 유형이 존재하는데, 한 정점((node))에 관해 간선을 한 번만 거쳐서 자기 자신으로 돌아오는 path가 존재하는 cycle이 그래프에서 있을 수 있고 없을 수도 있는데,그러한 cycle이 존재하지 않는 그래프를 DAG라고 한다.

 

Why Graph?

 

그렇다면 굳이 왜 Graph 자료구조를 가지고 추천 시스템에 적용하는 것일까, 그리고 어떻게 추천 시스템에 Graph를 적용시킬 수 있을까.

 

그래프도 Representation Learning 학습 방법과 유사한 성능을 가지고 있다.

 

CNN의 경우, 유클리디안 공간에서 행과 열로 배열된 픽셀들로 이루어진 이미지에서 특징을 추출한다. LSTM의 경우는 자기 자신으로 돌아오는 recurrent 구조를 통해 input으로 주어지는 시계열 데이터인 sequence의 특징을 추출한다. Transformer의 경우는 self-attention 구조를 통해 어떤 한 부분에서 주의를 기울여야 할 여러 부분들을 병렬적으로 처리함으로써 input의 특징을 추출한다.

 

위와 같은 방식들은 나름의 자료구조를 통해 Data Representation을 Learning하는 알고리즘이라고 볼 수 있다. GNN도 위 방식들과 마찬가지로 그래프의 구조를 통해 데이터의 특징을 추출한다. (= Representation Learning) 때문에 학습하려는 데이터를 그래프 구조로 표현할 수 있게 되면 그래프로 표현된 데이터의 특징을 모델에 학습시킬 수 있다.

 

GNN은 관계적 특성과 우리의 생각으로 표현할 수 없는 데이터 공간(Non-Euclidean Space)을 학습하는 것에 장점을 가지고 있는 알고리즘이다. 이러한 특성 덕분에, 관계적 task을 잘 Representation해야하는 추천 시스템 문제에서 GNN 알고리즘이 잘 활용되는 것 같다.

 

---

Reference

 

https://ysg2997.tistory.com/24

그래프 기반 추천시스템의 이해

https://velog.io/@hmym7308/%EB%85%BC%EB%AC%B8-%EB%A6%AC%EB%B7%B0-How-Powerful-Are-Graph-Neural-Networks-ICLR-2019

논문 리뷰 : How Powerful Are Graph Neural Networks? (ICLR, 2019)

https://peaceatlast.tistory.com/4

추천시스템과 GNN(Graph Neural Network)

https://www.youtube.com/watch?v=9eMbvfRM9_8

https://techblog.yogiyo.co.kr/%EC%95%8C%EC%9E%98%EB%94%B1%EA%B9%94%EC%84%BC-%EC%B6%94%EC%B2%9C-%EB%AA%A8%EB%8D%B8-%EB%A7%8C%EB%93%A4%EA%B8%B0-gnn%EC%9D%84-%ED%99%9C%EC%9A%A9%ED%95%9C-%EC%9A%94%EA%B8%B0%EC%9A%94%EC%9D%98-%EC%B6%94%EC%B2%9C-%EB%AA%A8%EB%8D%B8-yosemite-33b0600d2464

[알잘딱깔센 추천 모델 만들기] — GNN을 활용한 요기요의 추천 모델 YoSEMITE