04 GNN 기반 추천 알고리즘
Homofily : 동종 선호, 그래프 내에서 자신과 유사한 개체들이 서로 연결되는 특성
1. Graph Data의 이해
그래프의 종류
- 유방향 그래프(directed)
- 무방향 그래프(undirected)
- 가중 그래프(weighted)
- 동종 그래프(Homogeneous) : 모든 노드와 엣지가 같은 종류를 가짐(예:소셜 네트워크)
- 이종 그래프(Heterogeneous) : 노드와 엣지의 종류가 다양(예:이커머스 내 유저와 아이템 그래프)
- 이분형 그래프(bipartite) : 노드를 두 종류의 분리된 집합으로 나눌 수 있음. 집합 내 연결은 없고 집합 간 연결만 존재. 이종그래프의 일종.
그래프 관련 태스크
1. 그래프 분류
2. 링크 예측 ⭐️
3. 커뮤니티 감지
2. Graph 기반 추천 알고리즘
노드 표현 학습(Node Representation Learning)
1) 인코더 정의 : 각 노드를 저차원 벡터로 임베딩 하는 방법 결정.
2) 유사도 정의 : 의미상 비슷한 노드는 유사도가 높도록 유도하면서 학습. 유사도를 어떤 함수로 계산하는냐를 결정해야 함. 디코더기능.
3) 파라미터 최적화 : 파라미터를 최적화하면서 의미를 잘 보존한 벡터 표현을 생성
2-1. PageRank
- 그래프 구조를 활용해 웹 페이지의 중요도를 측정하는 알고리즘
- 랜덤워크(Random Walk) 기반 방법론
- 서퍼가 링크(하이퍼링크)를 떠돌아 다니다가 노드(웹페이지)에 머무를 확률(중요할 수록 높음)
- Power Iteration을 통해 스코어 계산
- 문제점 1. spider trap : 노드가 서로를 링크해서 반복. 진동발산.
- 문제점 2. dead end(막다른 정점) : 들어오는 엣지는 있고 나가는 엣지가 없는 상황. 값이 0으로 수렴.
- 해결책. Random Teleport : 매 스텝마다 특정 확률 alpha를 따라 아무 노드로 순간이동함.
- 추천을 위한 변형 : 이분형 그래프 내에서 teleportation vector를 관심 타겟 유저/아이템에게 원핫에 가깝게 셋팅.
- Non-GNN 추천에 적용될 수 있는 그래프 알고리즘으로, 그래프의 구조적 정보를 활용해 개인화된 추천을 제공하는 데 응용 가능
2-2. DeepWalk
2-3. GCN(Graph Convolution Network)
- MPNN(Message Passing Neural Network)
1) Message Passing & Aggregation: 연결된 이웃으로부터 정보를 전달받고, 이를 통합
2) Update: 통합된 값을 바탕으로 Node의 representation을 갱신
3) Read Out: Node representation을 종합해 전체 그래프에 대한 표현을 획득
2-4. GraphSAGE (Sampling and Aggregation)
2-5. GAT (Graph Attention Network)
- Inductive한 Graph Representation Learning 모델에 Attention을 적용하여 노드 임베딩 표현 성능을 높임
- Transductive, Inductive한 상황 모두에서 SOTA의 성능을 보임
2-6. PinSAGE
- Pinterest에서 실제 production에 적용한 GraphSAGE의 변형 알고리즘
- web-scale에서 적용 가능한 scalability를 확보하는 것이 주된 목적. 추가적으로 임베딩 표현력 향상을 위한 학습기법 도입.
- Scalability Improvements 1) 즉석(On-the-fly) Convolution: 기존의 GCN 알고리즘처럼 전체 그래프 행렬을 사용하지 않고 노드 주변 이웃을 샘플링 해 Localized Convolution을 적용
- Scalability Improvements 2) 생산자-소비자 미니배치 구성: CPU 기반 “생산자”는 노드 주변의 이웃을 추출 한 뒤 convolution 연산을 위한 준비를 수행. GPU 기반 TF 모델은 생산자가 미리 준비한 계산 그래프를 사용해 SGD 수행
- Scalability Improvements 3) 효율적인 맵리듀스 추론: 맵리듀스 파이프라인을 통해 학습된 모델을 분산처리해,
반복 연산을 최소화 하면서도 임베딩을 빠르게 생성
- Training Techniques 1) 랜덤워크를 통한 컨볼루션 생성: 랜덤워크 기반 스코어링을 통한 중요 이웃 샘플링
- Training Techniques 2) 중요도 풀링 (Importance Pooling): 랜덤워크 유사도 점수를 기반으로 Aggregation 과정에서 노드 피처에 가중치를 도입
- Training Techniques 3) 커리큘럼 학습 (Curriculum Training): 학습 과정에서 점점 더 어려운 예제를 학습하도록 유도하는 커리큘럼 학습 도입
3. 지식 그래프 기반 추천
지식 그래프 : 실제 세계를 구성하는 개체들과 그들의 관계를 나타낸 네트워크
지식 그래프 구성 요소 : 노드, 엣지, 라벨
지식 그래프 임베딩 방법론
- 대칭 관계 / symmetric (나의 친구의 친구는 나)
- 비대칭 관계 / Antisymmetric (상위어)
- 반의 관계 / Inverse (팔로우/팔로잉)
- 조합 관계 / composition (우리 엄마의 남편은 아내)
- 1대 다 관계 / 1-to-N (나는 A 교수의 제자 중 하나)
TransR이 협업지식그래프 학습에 널리 사용됨.
RippleNet
: 수면에 물방울이 떨어질 때 동그란 물결이 퍼지듯이, 유저와 아이템, 아이템의 특성(여기서는 ‘개체’, ‘entity’로 부름)으로 구성된 KG라는 수면 위에 " interaction'"이라는 물방울이 떨어졌을 때 고객의 선호라는 물결 파동이 어떻게 퍼져 나가는 지 잡아내는 모델.
KGAT(Knowledge Graph Attention Network)
Explainability와 Cold-Start Problem 개선
출처 : [패스트캠퍼스] 30개 프로젝트로 끝내는 추천시스템 구현 초격차 패키지