https://dl.acm.org/doi/10.1145/3626772.3657723
EditKG: Editing Knowledge Graph for Recommendation | Proceedings of the 47th International ACM SIGIR Conference on Research and
Knowledge Graphs (KGs) have been utilized as useful side information to improve recommendation quality. In those recommender systems, knowledge graph information often contains fruitful facts and inherent semantic relatedness among items. However, the ...
dl.acm.org
이번에 리뷰할 논문은 SIGIR 2024에 게재된 EditKG: Editing Knowledge Graph for Recommendation 입니다.
Abstract
본 논문은 추천시스템에서 지식그래프(KG)를 사용함에도 불구하고 KG의 불완정성으로 인해 발생하는 long-tail 현상을 다룹니다.
이를 해결하기 위해 본 논문에선 EditKG라는 추천 태스크를 위한 지식 그래프를 편집하는 방법을 제안합니다.
EditKG는 크게 Knowledge Generator와 Knowledge Deleter 두 가지로 구성됩니다.
Knowledge Generator의 경우, 아이템의 mutual information correlation과 semantic correlation을 사용하여 지식을 연결하고
Knowledge Deleter는 태스트의 관련성 점수를 통해 추천 태스트와 무관한 아이템의 지식을 제거하는 동시에, 속성 점수를 활용해 거짓 속성을 삭제하는 과정을 거칩니다.
Introduction
1. Background
추천시스템에서는 사용자와 항목 간의 복잡한 상호 작용 관계를 모델링을 하기 위해 그래프 신경망(GNN)이 많이 사용됩니다.
그러나, GNN 기반의 추천시스템은 cold-start 문제를 겪고 있으며, 이를 위해 다양한 기법들이 등장하였고 그중에서도 지식 그래프(KG)를 사용하는 기법이 등장했습니다.
지식 그래프는 아이템에 대한 외부 정보를 제공하고, 데이터 관점에서의 cold-start 문제를 완화할 수 있습니다.
2. Challenge
그러나, 현재 KG-aware 추천시스템은 지식 불균형 문제를 갖고있으며, 인기가 없는 아이템의 잠재적인 속성을 발견하는 것은 도메인 전문가의 지식에 의존하기 때문에 자동화가 어렵다는 특징을 가지고 있습니다.
이러한 불균형 현상은 아이템의 long-tail 현상으로 나타나게 됩니다. 또한, 아이템이 여러 속성을 가지고 있어도 이는 태스크(추천)과 관련이 없는 데이터가 존재하기에 불필요한 속성을 제거하는 것, 허위 정보를 가지고 있는 경우 이를 제거하기 위한 판단을 하는 것 또한 어렵습니다.
3. Contribution
본 논문에서는 지식 불균형 문제를 해결하기 위해 EditKG를 제안하며 이는 두 가지 모듈로 구성됩니다.
먼저 Knowledge Generator는 아이템 간 mutual information correlation과 semantic correlation을 학습하여 잠재적인 속성을 생성합니다.
이후, Knowledge Deleter를 통해 태스트 관련성 점수를 통해 task-irrelevant, suprious 속성을 제거합니다.
Method
0. Problem Definition
- $\mathcal{U}$: 사용자의 집합
- $\mathcal{V}$: 아이템의 집합
사용자가 $u_i $ 가 아이템 $ v_i $ 와 상호작용한 경우, 이진 값 $ y_{u_i,v_i} = 1 $ 이 됩니다.
구조화된 heterogeneous graph $\mathcal{G}_k$는 다음과 같습니다.
- $\mathcal{E}$: 엔티티의 집합
- $\mathcal{R}$: 관계의 집합
1. Knowledge Generator
Knowledge Generator는 크게 두 파트로 나뉩니다.
1.1. Attribute Correlation Calculation
이는 NPMI에서 영감을 받아 correlation을 계산하는 방식으로, 모든 유저에 대해 아이템 간 information의 correlation을 계산합니다.
먼저, $ C(v_i, v_j) $는아이템 $v_i$, $v_j$가 동시에 등장한 빈도를 의미하며, $C(v_i)$는 동시에 등장한 빈도 중에서도 $v_i$의 등장 횟수를 의미합니다.
이를 PMI를 통해 계산한 다음, 값이 너무 커지거나 작아지는 것을 막기 위해 nomalize 과정을 진행하여 값의 범위를 [-1, 1]로 조절합니다.
뿐만아니라, semantic correlation을 반영하기 위해 cosine similarity를 사용하여 두 아이템 간 의미적인 유사도를 더해 두 아이템 간의 유사도 $s$를 계산합니다.
cosine similarity를 통해 나온 값 또한 [-1,1] 사이의 값을 가지게 됩니다.
1.2. Attribute Transfer
앞서 구한 $s$ 값이 파라미터 $\eta$를 넘게 될 경우, 두 아이템은 유사하다고 판단을 합니다.
이때 $K_i={(r,t)|(v_i, r, t) \in \mathcal{G}_k}$이며, 즉 아이템 $v_i$가 가지고 있는 아이템과 연결된 속성들(e.g., genre, director 등)과의 (edge, node) 쌍을 의미합니다.
따라서 아이템 $v_i$ 가 $v_j$와 유사하다고 판단되었을 경우, $\tilde{K_i} $는 아이템 $v_j$의 속성 중 $v_i$가 가지고 있지 않은 속성 정보를 의미하며, 이는 $v_i$의 잠재적인 속성을 의미하게 됩니다.
잠재적인 지식그래프인 $\mathcal{G_k^+}$는 아래의 수식을 만족하게 되며 Knowledge Generator 과정이 끝나게 됩니다.
2. Knowledge Deleter
2.0. Background
Knowledge Deleter는 잠재적인 지식그래프 $\mathcal{G_k^+}$는 아이템의 속성을 많이 가지고 있지만, 이는 사실관계가 파악되지 않았기에 task-irrelevant한 속성이거나 suprious 속성을 가지고 있을 것입니다.
또한, 초기의 KG $\mathcal{G_k}$는 거짓 정보 없이 잘 구축된 KG이지만, 이는 일반적인 상황에서 동작하는 지식 그래프이기에, task-irrelevant한 속성들을 포함하고 있습니다.
이를 해결하기 위해 Knowledge Deleter는 두 가지 스텝으로 수행됩니다.
2.1. Attribute Purification Layer (APL)
APL($f_{APL}^{\mathcal{G}_k}$)은 $\mathcal{G}_k $에서 추천 태스크와 관련이 없는 속성들을 제거하는 과정이며 간단한 MLP로 구성되어 있습니다.
여기서 $\mathcal{G}_k^i$는 $\mathcal{G}_k$의 $i$번째 triplet을 의미하며, $\theta_{\mathcal{G}_k}$는 학습이 가능한 파라미터를 의미합니다.
이 APL은 직접적으로 추천 태스크를 수행하여 추천 task relevance score를 학습하게 됩니다.
이렇게 구해진 $p_k^i$는 $i$번째 triplet이 추천 태스크와 관련이 있는가에 대한 점수를 의미합니다.
위에서 구해진 점수는 Gumbel Max reparameterization trick을 사용하여 chararcteristic score vector를 얻게 됩니다.
이때 $\epsilon$은 gumbel(0, 1) 분포를 따르는 랜덤 값으로 $log(\epsilon)- log(1-\epsilon))$의 gumbel noise를 $p_k^i$에 더해 이를 sigmoid function에 넣어 (-1, 1) 사이의 값으로 변환합니다.
여기서 $\mathbb{I}[\cdot]$은 indicator function으로 $\mathbb{I}[x > \mu] = x$ and $\mathbb{I}[x <= \mu] = 0$ 을 만족하며 이를 통해 $m_k^i$는 [0, 1] 범위의 값을 갖게 되는데, $m_k^i=0$일 경우 이 $i$번째 triplet은 추천 task와 관련없는 triplet이라고 판단합니다.
이렇게 $m_k^i$가 (0, 1] 사이의 값을 갖는 triplet을 모아둔 unbiased KG를 $\mathcal{G}_k^-$이라 정의합니다.
동시에, 각 triplet의 task relevance score를 함께 담은 KG를 purified primary KG $\tilde{\mathcal{G}}_k$라고 정의합니다.
2.2. Knowledge Deletion of Potential KG
2.2.0. Previous studies
두 번째로 진행할 과정은 Knowledge Generator 과정에서 생성된 잠재적인 KG $\mathcal{G}_k^+$는 앞서 설명했듯이 추가된 triplet이 ① 속성의 진위 여부를 판단하기 힘들며 (spurious triplet), ② 추천 task와 관련된 triplet이 아닐 가능성이 있기에 이 두 가지 noise를 제거하는 것은 추천 성능을 위해선 필수적입니다.
먼저, spurious 속성과 task-irrelevant 속성을 잠재적인 KG에서 제거하기 위해선 두 가지 과정을 사용할 수 있습니다.
1) Sequential Mathod
: well-trained Knowledge Graph Completion(KGC) 모델을 사용하여 spurious 속성을 제거한 뒤, 그 후 APL을 사용해 task와 무관한 속성을 제거하는 방법
2) Joint Method
: $\mathcal{G}_k^-$를 APK의 보조적인 task로 활용해 APL이 spurious 속성을 제거할 수 있도록 학습하는 방법
그러나, 첫 번째 방법은 KGC 모델이 sprious 속성을 완벽하게 제거하지 못할 경우 그 다음 단계인 APL의 task-irrelevant 속성 제거 과정에서 잘못된 정보를 학습하여 오류가 누적이 될 수 있고, KGC 모델은 추천 task를 위해 학습된 모델이 아니기에 추천에서 중요한 정보가 실제 추천에서 중요한 속성일 가능성이 있기에 이를 수행하는 것은 오류 누적으로 이루어집니다.
두 번째 방법의 경우, Domain shift 문제가 발생하게 되는데, 이는 KG가 가지고 있는 데이터는 지식 기반의 구조화된 데이터(e.g., (Titanic, directed by, James Cameron))이고, 추천 시스템의 데이터는 user-item interaction data이기 때문에 이러한 KG를 추천에 직접 적용할 경우 비효율적으로 작동할 가능성이 있습니다. 또한, 추천에서는 특성 속성만이 유용하고, 나머지는 노이즈로 작동할 수 있기에 추천에 KG를 직접적으로 활용할 경우 추천시스템이 불필요한 속성까지 학습을 하게 됩니다.
이러한 문제점을 극복하기 위해 본 논문에서는 Expertise Transfer Mechanism을 제안합니다.
2.2.1. Expertise Transfer Mechanism
먼저, 이 과정은 unbiased KG $\mathcal{G}_k^-$를 KGC model을 사용하여 반복적으로 학습하게 됩니다.
이 $\mathcal{L_{kgc}}$를 학습하기 위한 과정은 아래와 같습니다.
먼저, $\mathcal{\tilde{G}}_k^-$ 는 unbiased KG와 unbiased KG에 negative sampling을 추가한 KG를 concat하여 정의됩니다.
이를 통해 간단한 MLP로 구성된 KGC 모델을 학습해 $\hat{y_i}$를 구하게 됩니다.
이 $\hat{y_i}$과, ground truth $y_i$를 통해 BCE Loss를 사용해 $\mathcal{L} _{kgc}$를 학습하게 됩니다.
이후, well-trained KGC 모델은 potential KG $\mathcal{G}_k^+$의 attribute score를 계산하게 되며, 이 점수들은 $\mathcal{Q}_k^+$로 정의합니다.
이는 spurious 속성과 관련된 점수를 의미하며, 앞서 task와 관련된 정도를 나타내는 점수 $\mathcal{P}_k^+$와 결합하여 학습을 진행하게 됩니다.
본 논문에선 $\mathcal{Q}_k^+$와 $\mathcal{P}_k^+$를 Maximum Mean Discrepancy(MMD) loss를 통해 학습을 진행하게 됩니다.
함수 $g(x)$는 두 확률 분포의 차이를 측정할 때 쓰는 함수로, sprious 속성과 관련된 점수의 확률분포와 task와 과련된 정도를 나타내는 점수의 확률분포의 가장 큰 차이를 찾아 이를 최소화 하도록 학습을 진행하게 됩니다.
이는 이후 추천에 대한 Loss인 $\mathcal{L}_{rec}$과 함께 사용됩니다.
이렇게 학습된 $f_{\mathcal{G}_k^+}^{APL}$은 추천과 관련성이 있는지, triplet이 진위성을 가지고 있는지에 대해 모두 평가가 가능해집니다.
다시 Gumbel-Max reparameterization trick을 통해 정제된 속성 점수 벡터 $\mathcal{M}_k^+$를 구할 수 있으며, 이를 담고 있는 purified potential KG $\tilde{\mathcal{G}_k^+}$를 구할 수 있습니다.
앞서 구한 unbiased KG인 $\tilde{\mathcal{G}_k}$과 purified potential KG $\tilde{\mathcal{G}_k^+}$를 concat하여 balanced KG $\mathcal{G}_k^b$를 구하게 됩니다.
3. Aggregator and Prediction
먼저, balanced KG를 LightGCN을 사용하여 knoweldge representaiton을 학습하게 되는데, $\mathcal{T}_1 \cup \mathcal{T}_2 \cup \mathcal{T} = \mathcal{G}_k^b $를 만족할 때, $\mathcal{G}_k^{b, *} =\{ \mathcal{T}_1 , \mathcal{T} \}$, $\mathcal{G}_k^{b, +} =\{ \mathcal{T}_2 , \mathcal{T} \}$ 로 정의합니다.
이때, $ \mathcal{T}_1 , \mathcal{T}_2 $는 item의 one-hop attribute들로 직접적인 정보를 포함하며, $ \mathcal{T} $는 multi-hop attribute들로 보조적인 역할을 수행하게 됩니다.
각 entity에 대한 embedding 값들은 위의 과정을 통해 학습을 진행하게 됩니다.
이후, 이는 아이템 $v_j$의 주변 entity 정보까지 포함하고 있는 $e_i$와 아이템의 embedding 값인 $h_j^v$를 concat하여 $\hat{h_j^v}$ 값을 구하게 됩니다.
최종적으로, 사용자 $u_i$가 아이템 $v_j$을 interact할 확률 $y_i^j$를 구하게 됩니다.
여기서 $\bar{h_i^u}$는 사용자 $u_i$가 상호작용한 아이템들에 대한 평균 임베딩을 의미하며,
$\bar{h_i^v}$는 아이템 $v_i$가 상호작용한 유저들에 대한 평균 임베딩을 의미합니다.
또한, $\mathcal{N}_u^i$는 user $u_i$와 상호작용이 있는 아이템들을 의미하며, 이때 $\bar{h_i^v}$와 다르게 아이템의 임베딩을 합할 때, $h_j^u$를 더하는 것이 아닌, 아이템 뿐만 아니라 그 주변 entity의 정보까지 담고 있는 $\hat{h_v^j}$을 더하게 되는데 아이템의 경우에만 주변 정보까지 담고 있는 embedding을 반영하는 이유는 본 논문에서는 user-item interaction 외에 item과 관련있는 지식 정보를 추가하였기 때문에 user의 부가 정보는 존재하지 않아 user의 주변 정보가 없기 때문입니다.
4. Model Optimization
본 논문은 cross-entropy를 loss function으로 사용하여 추천에 대한 loss를 구하게 됩니다.
앞서 잠깐 언급했듯이, mmd loss와 rec loss는 함께 학습을 수행하게 됩니다.
이 학습 방법은 PCGrad로부터 영감을 받았으며, mmd loss의 gradient와 rec loss의 gradient를 통해 학습을 진행하게 됩니다.
그러나, 위의 방법으로 학습을 진행하게 되면, loss의 충돌이 일어나게 됩니다.
예를 들어, $\mathcal{L}_{rec}$은 특정 triplet이 추천과 관련이 없다고 판단하여 이를 없애는 방향(-)으로 학습이 되는 반면, $\mathcal{L}_{mmd}$는 해당 triplet이 진실된 속성으로 판단하여 유지하는 방향(+)으로 학습하게 될 경우 이는 학습에 오류가 생기게 됩니다.
즉, 이렇게 loss의 gradient 방향이 반대일 경우 학습에 좋지 않은 영향을 끼치지 때문에 이를 해결하기 위해 본 논문에선 Gradient Match Strategy를 제안하며 이를 통해 학습을 진행합니다.
이는 둘의 gradient를 곱했을 때 음수가 나올 경우 mmd loss를 $\triangledown\tilde{\mathcal{L}}_{mmd}(\theta_{\mathcal{G}_k^+})$로 변경하여 $ \triangledown \mathcal{L}_{rec}$과 $ \triangledown \mathcal{L}_{rec}$을 더해 학습을 진행하게 됩니다.
위의 그림은 이해를 돕기 위해 제작된 자료입니다.
Experiments
1. Experimental Settings
1.1. Datasets.
1.2. Evaluation Metrics
1.3. Baselines
2. Research Questions
RQ1: How does EditKG perform compared with different types of recommendation methods?
EditKG는 Knowledge Generator, Knowledge Deleter를 통해 잠재적인 지식을 생성한 뒤, 추천과 관련없고 진실된 정보만 뽑아내서 Balanced KG를 구축함으로써 추천의 성능을 높였습니다.
또한, Yelp2018에 비해 Last-FM과 Amazon-Book의 데이터셋이 더 spase한 것을 볼 수 있는데 이 두 데이터셋에서 실험했을 때 성능이 더욱 우수하게 나타나 cold-start 문제를 보완했습니다.
또한, KG-aware method에서 GNN 기반의 추천이 embedding 기반의 추천보다 더욱 우수한 성능을 보였습니다.
RQ2: How do different key designs of EditKG impact its overall performance?
먼저 Knowledge Generator와 Knowledge Deleter를 없앴을 때, 큰 성능 하락을 보였고 이는 이 두 방법의 중요성을 의미합니다.
두 번째로, KG Compleation과 APL 과정을 없앰으로써 task-irrelevant attribute와 sprious 속성을 없애는 것에 대한 중요성을 강조하며
KTM 과정을 없앰으로써 전문성을 APL로 효과적으로 전달하여 negative한 속성을 더 정확히 제거할 수 있음에 대한 점을 강조합니다.
마지막으로 MIC와 SMC를 없앰으로써 negative 특성을 더 정확히 없애는 것에 대한 중요성을 강조합니다.
RQ3: What is the result of knowledge balancing of EditKG?
이 분포는 기존의 KG와 Balanced KG의 아이템의 속성 개수를 보여줍니다.
(근데 이거 개인적인 의견인데 빨간색이랑 초록색이 반대가 아닌가 하는 생각이 듭니다,,,)
(그림에서 빨간색과 초록색을 반대로 설명해보자면)
기존 KG에 비해 Balanced KG가 아이템의 속성 개수를 더 많이 포함하고 있으며, long-tail 아이템의 경우 balanced KG에서 더 많은 수의 속성을 가지고 있었습니다. 이를 통해 아이템의 부족한 속성을 효과적으로 보완하였다고 말할 수 있습니다.
또한, 인기있는 아이템의 특성 수는 감소하기도 했는데 이는 task와 관련없는 속성을 삭제하여 나타난 결과라고 볼 수 있습니다.
RQ4: What is the efficacy of EditKG in mitigating the cold-start problem?
이 표는 Group의 수가 커질수록 cold-start 현상이 큰 그룹을 의미하는데 cold start가 클 경우에도 EditKG가 우수한 성능을 보였고 이를 통해 Cold-start도 효과적으로 해결할 수 있다고 볼 수 있습니다.
RQ5: How does the Gradient Match Strategy impact EditKG? Besides, can EditKG provide an intuitive impression of explainability?
이 그림에서는 실제로 Item 3565와 3566가 함께 상호작용되어 $\eta$를 넘을 경우 비 인기 아이템 3566의 속성을 보완하게 되고 동시에 두 아이템의 속성 중 추천과 관련없는 속성이 제거된 모습을 볼 수 있습니다.
Conclusion
본 논문은 KG-aware 추천에서 지식 불균형 문제를 해결하기 위해 EditKG라는 프레임워크를 제안합니다.
이는 i) 잠재적인 속성 생성 ii) 작업과 관련 없는 속성 및 거짓 속성을 제거하는 두 단계로 구성됩니다.
본 논문은 이 방법을 사용하여 state-of-the-art를 달성했고 향후 연구에서는 high-order 속성을 파악해 동적인 user-item interaction을 위해 EditKG를 조정할 것이라 언급합니다.
My opinion
이 논문을 읽기 전까진 KG의 지식을 효과적으로 생성하는 방법을 찾고 관련된 논문을 작성하였는데, Knowledge Deleter 과정으로 task와 관련없는 지식을 삭제하는 방식을 내 논문에도 적용시킬 수 있으면 좋을 것 같다는 생각이 들었다.
그리고 이 논문을 읽으면서 수식이 많아 이해하기 힘들었는데 이해하고 나니 공부가 많이 된 느낌이다!
