Title
Tripartite Heterogeneous Graph Propagation for Large-scale Social Recommendation
1. Problem Definition
Please write the problem definition on here
2. Motivation
Please write the motivation of paper. The paper would tackle the limitations or challenges in each fields.
After writing the motivation, please write the discriminative idea compared to existing works briefly.
3. Method
Please write the methodology author have proposed.
We recommend you to provide example for understanding it more easily.
4. Experiment
In this section, please write the overall experiment results.
At first, write experiment setup that should be composed of contents.
Experiment setup
•
Dataset
•
baseline
•
Evaluation Metric
Result
Then, show the experiment results which demonstrate the proposed method.
You can attach the tables or figures, but you don't have to cover all the results.
5. Conclusion
Please summarize the paper.
It is free to write all you want. e.g, your opinion, take home message(오늘의 교훈), key idea, and etc.
Author Information
•
Author name
◦
Affiliation
◦
Research Topic
6. Reference & Additional materials
Please write the reference. If paper provides the public code or other materials, refer them.
•
Github Implementation
•
Reference
Title
Tripartite Heterogeneous Graph Propagation for Large-scale Social Recommendation
1. Problem Definition
•
*사회 추천 시스템(social recommendation)**은 사용자-사용자, 사용자-아이템 간의 복잡한 관계를 학습하여 개인화된 추천을 제공합니다.
•
기존의 Graph Neural Network(GNN) 기반 추천 시스템은 이웃 노드의 정보를 집계하여 추천 성능을 향상시키지만, 다음과 같은 문제에 직면합니다:
1.
사용자 간 연결이 기하급수적으로 증가해 그래프 규모가 매우 커지는 문제.
2.
*이질적인 그래프(heterogeneous graph)**에서 서로 다른 노드와 엣지 유형을 효과적으로 처리하기 어려움.
3.
GNN 모델의 과도한 스무딩(oversmoothing) 문제로, 층이 깊어질수록 국소적인 정보가 소실됨.
2. Motivation
•
이질적인 그래프 구조와 과도한 스무딩 문제는 대규모 소셜 그래프에서의 GNN 사용을 어렵게 만듭니다.
•
이 논문은 세 가지 노드 유형(사용자, 그룹, 아이템) 간 관계를 학습하는 세부 구조를 가진 그래프를 제안합니다.
◦
기존 연구와의 차별점:
▪
Tripartite Graph로 사용자-그룹-아이템 관계를 모델링해 연결 수를 줄이고 계산 효율성을 개선합니다.
▪
Personalized PageRank 기반 전파 방식을 통해 과도한 스무딩 문제를 해결합니다.
▪
Attention 메커니즘을 사용해 여러 유형의 노드 임베딩을 결합합니다.
3. Method
이 논문에서는 **Heterogeneous Graph Propagation (HGP)**라는 방법을 제안합니다.
•
HGP는 사용자-그룹 및 사용자-아이템 그래프의 이웃 정보 전파를 각각 수행한 후, Attention 메커니즘을 통해 노드 임베딩을 결합합니다.
구체적 과정
1.
그래프 구성:
•
사용자-그룹-아이템의 3자(graph tripartite) 구조를 사용해 사용자-사용자 간 직접 연결을 제거하고, 노드 간 경로 복잡성을 줄입니다.
•
그룹 노드는 **사회적 속성(예: 공통 관심사)**을 나타내며, 사용자와 아이템 간의 연결 고리로 작용합니다.
2.
Personalized PageRank 기반 전파:
•
PageRank 알고리즘을 응용해, 노드가 항상 자기 자신으로 돌아올 확률을 부여합니다. 이 방식은 스무딩을 방지하고 국소 정보를 유지합니다.
•
전파 방식:
Z(k+1)=(1−α)ReLU(A^Z(k)W(k))+αH
Z(k+1)=(1−α) ReLU(A^Z(k)W(k))+αHZ^{(k+1)} = (1 - \alpha) \, \text{ReLU}(\hat{A} Z^{(k)} W^{(k)}) + \alpha H
◦
α\alphaα: PageRank에서의 텔레포트 확률
◦
A^\hat{A}A^: 정규화된 인접 행렬
◦
HHH: 초기 임베딩 행렬
3.
Attention을 통한 임베딩 결합:
•
서로 다른 엣지 유형에 대해 학습된 노드 임베딩을 Attention 메커니즘으로 결합합니다:
Y′=softmax(dkQK⊤)V
Y′=softmax(QK⊤dk)VY' = \text{softmax}\left(\frac{Q K^\top}{\sqrt{d_k}}\right) V
◦
Q, K, V는 각각 Query, Key, Value 행렬입니다.
4.
CTR 예측:
•
사용자와 아이템 임베딩 간 내적을 통해 클릭 확률(CTR)을 예측합니다:
pi,j=sigmoid(zi⊤zj+xi⊤xj)
pi,j=sigmoid(zi⊤zj+xi⊤xj)p_{i,j} = \text{sigmoid}(z_i^\top z_j + x_i^\top x_j)
4. Experiment
Experiment Setup
•
Dataset:
◦
1.1M 사용자, 456K 그룹, 82K 아이템으로 구성된 소셜 네트워크 데이터셋.
◦
총 1.6M 노드와 4.7M 엣지로 구성됩니다.
◦
그룹 노드는 주제 정보를, 사용자 노드는 인구 통계 속성, 아이템은 언어-시각 정보를 포함합니다.
•
Baseline Models:
1.
metapath2vec: 메타 경로 기반 임베딩.
2.
FastGCN: 대규모 그래프를 위한 샘플링 기반 GCN.
3.
MNE+EGES: 이질 그래프 임베딩 모델.
•
Evaluation Metrics:
◦
ROC-AUC: 예측의 정확도 평가.
◦
PR-AUC: Precision-Recall 곡선의 면적.
◦
F1-Score: Precision과 Recall의 조화 평균.
Result
•
HGP 모델은 ROC-AUC: 0.6365, PR-AUC: 0.6378, F1: 0.5967로 기존 모델을 능가하는 성능을 보였습니다.
•
샘플링 전략을 사용한 경우 학습 시간이 45시간에서 1.1시간으로 단축되었습니다.
•
Propagation step 수가 증가할수록 성능이 향상되었으며, 과도한 스무딩 문제가 발생하지 않았습니다.
5. Conclusion
•
HGP는 사용자-그룹-아이템의 3자 구조를 사용해 복잡한 소셜 네트워크의 효율적인 추천을 수행합니다.
•
Personalized PageRank 기반 전파와 Attention 메커니즘을 사용해 이질적인 그래프와 과도한 스무딩 문제를 해결했습니다.
•
실험 결과, HGP는 대규모 데이터셋에서도 높은 성능을 기록하며, 산업용 추천 시스템에 적합함을 보였습니다.
Author Information
•
Authors: Kyung-Min Kim, Donghyun Kwak, Hanock Kwak, Young-Jin Park
◦
Affiliations: NAVER Corp., LINE Plus Corp., Search Solution Inc.
◦
Research Topics: Graph Neural Networks, Social Recommendation, Heterogeneous Networks
6. Reference & Additional Materials
•
Reference:
◦
Cen et al. (2019), “Representation Learning for Attributed Multiplex Heterogeneous Network”
◦
Kipf & Welling (2017), “Semi-supervised classification with graph convolutional networks”
•
Github Implementation: Not mentioned.
Key Idea
•
이 논문은 사용자-그룹-아이템 간의 관계를 학습하여, 기존 GNN 기반 소셜 추천 모델의 스케일링 문제와 과도한 스무딩 문제를 해결합니다.
•
Tripartite Graph를 활용해 연결 복잡성을 줄이고 효율적인 전파를 가능하게 합니다.