PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforced Negative Sampling over Knowledge Graph for Recommendation

Xiang Wang, Yaokun Xu, Xiangnan He, Yixin Cao, Meng Wang, Tat-Seng Chua

arXiv:2003.05753v1cs.IRcs.LG

TL;DR

Recommendation models trained on positive-only implicit feedback need informative and factual negative samples. KGPolicy uses reinforcement learning to navigate item knowledge graphs for knowledge-aware negative sampling, and experiments show improvements across three datasets, while false-negative issues remain only partly alleviated.

  • Problem

    Positive-only implicit feedback makes it difficult to distill negative signals, while high-quality negatives should be both informative and factual.

  • Method

    KGPolicy uses a reinforcement learning agent and adaptive two-hop exploration over knowledge graphs to discover potential negative items for positive interactions.

  • Results

    KGPolicy significantly improves recommendation performance across three benchmark datasets, including ndcg@20 gains over KAGT of 6.22% on Yelp2018, 11.09% on Last-FM, and 8.25% on Amazon-book.

  • Takeaways & Limitations

    Knowledge-aware negative signals can improve recommender representations and help interpret user intents from unobserved data.

  • Takeaways & Limitations

    False negatives remain difficult for stochastic samplers, and KGPolicy empirically alleviates this issue only to some extent.

Abstract

from arXiv · show

Properly handling missing data is a fundamental challenge in recommendation. Most present works perform negative sampling from unobserved data to supply the training of recommender models with negative signals. Nevertheless, existing negative sampling strategies, either static or adaptive ones, are insufficient to yield high-quality negative samples --- both informative to model training and reflective of user real needs. In this work, we hypothesize that item knowledge graph (KG), which provides rich relations among items and KG entities, could be useful to infer informative and factual negative samples. Towards this end, we develop a new negative sampling model, Knowledge Graph Policy Network (KGPolicy), which works as a reinforcement learning agent to explore high-quality negatives. Specifically, by conducting our designed exploration operations, it navigates from the target positive interaction, adaptively receives knowledge-aware negative signals, and ultimately yields a potential negative item to train the recommender. We tested on a matrix factorization (MF) model equipped with KGPolicy, and it achieves significant improvements over both state-of-the-art sampling methods like DNS and IRGAN, and KG-enhanced recommender models like KGAT. Further analyses from different angles provide insights of knowledge-aware sampling. We release the codes and datasets at https://github.com/xiangwang1223/kgpolicy.

1 INTRODUCTION

The paper addresses the one-class problem of deriving negative feedback from positive-only interactions. It proposes using knowledge graphs and reinforcement learning to find negative samples that are both informative and factual.

  • Motivation: Implicit feedback records positive signals such as clicks and purchases, leaving recommender models without direct negative feedback.This creates the one-class problem: distilling negative signals from positive-only data.
  • Limitations of Existing Sampling: Existing negative samplers include static, adaptive hard-negative, and extra-behavior approaches, but each has limitations.Static sampling may be inefficient, hard negatives may be future positives, and extra behaviors are limited in scale.
  • Design Requirements: High-quality negatives should be informative to model training and factual as true negatives rather than merely unobserved items.The paper identifies factual-negative discovery as the key unresolved challenge because missing data lacks ground truth.
  • Knowledge-Aware Sampling: Knowledge graphs may help infer factual negatives by exposing relations among items and real-world entities, including items a user may know but choose not to consume.Prior KG-enhanced recommenders use knowledge for prediction, whereas this work applies it to negative sampling.
  • Challenges: KG-guided sampling must intelligently traverse rapidly expanding paths and distinguish the confidence of entities and candidate items being exposed or negative.The absence of ground truth makes both navigation and signal interpretation difficult.
  • Proposed Approach: KGPolicy uses a reinforcement learning agent and adaptive exploration from positive items to discover high-quality negative examples.Its neighbor attention module conditions path selection on the positive user-item pair and personal tastes.
  • Contributions: Across three benchmark datasets, KGPolicy improves sampling effectiveness and knowledge usage, while remaining plug-and-play for arbitrary recommenders.The work reports extensive experiments and emphasizes that the sampler is recommender-agnostic.

2 TASK FORMULATION

The task is to use user interactions and item knowledge in a KG to generate unobserved items that are informative and reflective of personal tastes. Multi-hop paths provide candidate negative signals, while their differing confidence motivates adaptive exploration.

  • Data and Knowledge Graph: The framework represents historical user-item interactions as implicit feedback between users and positive items.The interaction set contains user-item pairs indicating historical interactions.
  • Data and Knowledge Graph: The knowledge graph unifies users, items, and auxiliary entities, representing item attributes or external knowledge as graph connections.Entity-relation-entity triples are simplified into edges between conceptualized entities.
  • Task Description: The sampler generates a distribution over unobserved items to select a knowledge-aware negative item expected to reflect personal tastes and inform training.Exclusive KG entities of the positive and negative items can explain why the user is less interested in the negative item.
  • Negative Signals in Multi-hop Paths: Multi-hop paths rooted at a positive item connect it to unobserved candidate items, but different paths carry different confidence levels as negative evidence.The formulation therefore treats path structure as informative but not uniformly reliable.
  • Negative Signals in Multi-hop Paths: A shared KG entity can make a candidate informative through similar representations and factual through possible prior exposure without consumption.Longer paths can be explored when a discovered candidate has lower confidence as a negative.

3 METHODOLOGY

KGPolicy learns to navigate the knowledge graph toward informative negatives using reinforcement learning. Its exploration combines graph representations, attention-based neighbor selection, and neighbor pruning.

  • KGPolicy Architecture: KGPolicy comprises graph learning, neighbor attention, and neighbor pruning components for conducting exploration operations.Graph learning prepares node representations, attention selects the next node, and pruning limits candidate neighbors.

3.1 Recommender

The recommender uses matrix factorization with user and item embeddings and optimizes pairwise preferences between historical and unobserved items. Negative-sample informativeness is tied to the resulting gradient magnitude.

  • Matrix Factorization: Matrix factorization represents each user and item with an embedding and predicts consumption likelihood through their inner product.The model is used as a simple linear recommender for evaluating the sampler.
  • Optimization: The pairwise BPR objective trains the recommender to score a user’s historical items above unobserved items.The recommender acts as a critic of the sampled positive-negative pair.
  • Negative Informativeness: Negative-sample informativeness is measured by gradient magnitude because it reflects a pairwise preference’s contribution to updating recommender parameters.Negatives with prediction scores close to the positive produce more useful optimization signals.

3.2 Knowledge-aware Sampler

KGPolicy treats negative sampling as an RL navigation problem over the knowledge graph, starting from a positive item and producing candidate negatives through multi-hop exploration. Its rewards combine informativeness from recommender predictions with similarity to the positive item.

  • Sampling as Reinforcement Learning: KGPolicy uses the knowledge graph as an environment for an RL agent to navigate from a positive item toward potential negative items.The approach avoids enumerating all paths to unobserved items and instead learns automatic exploration over the KG.
  • Sampling as Reinforcement Learning: Sampling is formulated as an MDP with actions from exploration operations, states representing exploration paths, transition dynamics, and rewards.The state captures the user and currently visited item, while the initial state is the user-positive-item pair.
  • Exploration Operation: Each exploration operation follows a two-hop path from the current item through a KG entity to a proposal item.The operation evaluates both the likelihood that the intermediate entity was exposed to the user and that the proposal item is negative.
  • Exploration Operation: After T operations, the terminal item eT becomes the final negative, while varying T adjusts the search space and negative diversity.The method sets T to 2 by default.
  • Reward: The reward combines prediction and similarity signals because high predicted scores indicate informative negatives and similarity indicates likely exposure.The two components are fR(u,et) = ru^Tret and дR(i,et) = ri^Tret, with their combination controlled by a hyper-parameter.
  • Objective Function: KGPolicy learns a stochastic policy by maximizing expected cumulative discounted reward, producing action probabilities for proposal items.The policy probability represents the confidence that a proposal item is negative at each exploration step.

3.3 Knowledge Graph Policy Network.

The KG policy network combines graph-based node representations, user-conditioned neighbor attention, and neighbor pruning to select knowledge-aware exploration paths. These components reduce the search space while modeling which entities and items are promising negative proposals.

  • Knowledge Graph Policy Network: KGPolicy contains graph learning, neighbor attention, and neighbor pruning modules for generating a policy and action confidences.The modules respectively represent graph nodes, select suitable neighbors, and reduce the exploration space.
  • Graph Learning Module: GraphSage propagates information over the KG and user-item graph to embed users, items, and KG entities.Stacked layers produce final node representations that inject graph structure into exploration.
  • Neighbor Attention Module: The attention module decomposes each exploration operation into selecting an outgoing KG entity and then selecting an item proposal.The resulting operation probability is the product of the probabilities assigned to these two exploration steps.
  • Attentive KG Neighbors: Different users and items may emphasize different KG entities, such as a movie’s director or writer, motivating adaptive neighbor attention.The paper describes user interests as potentially changing across consumed items.
  • Attentive KG Neighbors: Entity attention conditions neighbor importance on the user, current item, and candidate KG entity before normalizing selection probabilities.The score uses the element-wise interaction between the current-item and entity representations together with the user representation.
  • Neighbor Pruning: Neighbor pruning first samples n1 neighbors and then scores n2 candidates, adding random whole-space nodes to preserve diversity.The pruned sets replace the original neighbor sets and reduce the time complexity of neighbor attention.

3.4 Model Optimization

Training alternates between optimizing the matrix-factorization recommender and the KGPolicy sampler. Because sampling is discrete, the sampler uses policy-gradient reinforcement learning, while neighbor attention and graph learning determine the computational cost.

  • Alternating Optimization: The recommender parameters ΘR and sampler parameters ΘS are optimized iteratively rather than jointly in a single update.The recommender is MF, while the sampler is KGPolicy.
  • Recommender Optimization: With ΘS frozen, KGPolicy samples a negative item, and SGD updates the recommender using the positive-negative interaction.The sampled terminal item j = eT is paired with a positive interaction and passed to MF.
  • Sampler Optimization: With ΘR frozen, the sampler is updated using REINFORCE because discrete sampling blocks direct gradient-based optimization.A baseline equal to the average reward of recently generated negative interactions reduces policy-gradient variance.
  • Limitation: Stochastic samplers cannot fully avoid false negatives, although KGPolicy empirically alleviates the issue to some extent through item knowledge.False negatives are sampled training items that are positive during later inference testing.
  • Complexity: KGPolicy costs about 232s per training epoch on Yelp2018, compared with 22s for RNS and 116s for DNS.The paper characterizes KGPolicy as having complexity comparable to adaptive samplers, especially adversarial methods.

4 EXPERIMENT

Experiments on three public datasets compare KGPolicy with negative samplers and KG-based recommenders. KGPolicy consistently performs best across evaluation measures, with larger gains over both sampler and KG-recommender baselines.

  • 4.1 Dataset Description: Experiments use Amazon-book, Last-FM, and Yelp2018 with user-item interactions and knowledge graphs from Freebase or local business information.Each user’s history is split 80%/20% for training and testing, and sampled negatives are paired with observed positives during training.
  • 4.2 Baselines and Metrics: The evaluation compares KGPolicy against static, adaptive, and KG-based negative samplers, plus supervised, regularization-based, path-based, and GNN-based KG recommenders.Recall@20 and ndcg@20 are reported over the whole item space.
  • 4.4.1 Empirical Results w.r.t. Negative Sampling: KGPolicy consistently outperforms all negative-sampling baselines across three datasets and all measures.The comparison includes RNS, PNS, DNS, IRGAN, AdvIR, NMRN, and RWS.

4.5 Study of KGPolicy (RQ2)

The study examines how exploration depth and reward design affect KGPolicy. Three exploration operations generally improve results, whereas a fourth hurts performance, and combining reward components is preferable to using either alone.

  • 4.5 Study of KGPolicy: The ablation study varies user behaviors, item knowledge, exploration-operation count, and reward functions to analyze KGPolicy components.The exploration count is evaluated in Table 4, and reward-function variants in Table 5.
  • 4.5.1 Impact of Exploration Number: Three exploration operations generally outperform one or two by covering more diverse item neighbors.The paper connects this result to three-hop paths reaching exposed but less-interested items and potentially unobserved disliked negatives.
  • 4.5.1 Impact of Exploration Number: Four exploration operations worsen performance across the board, which the authors associate with less-relevant items and vanishing gradients.The authors report that KGPolicy-3 is the strongest setting among the tested exploration counts in most cases.
  • 4.5.2 Impact of Reward Functions: Using only S+Reward or only P+Reward degrades performance because the selected items become suboptimal negatives.Neither S-Reward nor P-Reward wins on every dataset; their relative performance varies by dataset.

4.6 In-depth Analysis (RQ3)

The analysis examines how KGPolicy affects training, sparsity, and interpretability. It finds stronger learning signals and performance gains for relatively active users, while extremely sparse behavior remains insufficient for sampler learning.

  • Training Process w.r.t. Gradient Magnitude.: KGPolicy produces larger gradient magnitudes than static and adaptive samplers throughout training, indicating more informative sampled negatives.The comparison uses average gradient magnitude on Yelp2018 and Last-FM.
  • Performance w.r.t. Sparsity Levels.: KGPolicy significantly improves over competing methods in the third and fourth user groups.On Last-FM, improvements over KGAT are 8.78% for the <135 group and 8.50% for the <297 group.
  • Performance w.r.t. Sparsity Levels.: Knowledge-aware negative sampling benefits relatively active users, whereas extremely sparse behaviors are insufficient to guide sampler learning.KGPolicy slightly outperforms KGAT in Yelp2018’s sparsest group, but the authors identify insufficient behavior as a limitation for learning the sampler.
  • Case Study.: The study suggests that jointly modeling informative KG propagation and knowledge-aware negative sampling may help address sparsity, but leaves this combination for future work.The authors also propose incorporating true negative signals to improve explanations of user behavior.
  • Case Study.: Exploring paths from positive interactions to negative items can reveal differences in item attributes associated with users’ choices.Examples connect restaurant preferences to attributes such as convenience, TakeOut, and Good for Dancing.

5 RELATED WORK

The related work covers negative sampling for implicit feedback and KG-based recommendation. The paper distinguishes its approach by using KG structure to discover informative and factual negative feedback rather than only improving positive-signal modeling.

  • Negative Sampling: Negative sampling addresses one-class implicit-feedback learning by selecting unobserved items as negatives under predefined distributions.Examples include random sampling based on a uniform distribution and popularity-biased sampling.
  • Knowledge Graph-based Recommendation: The paper hypothesizes that KG structure can infer informative and factual negative items from missing data.This distinguishes the proposed research direction from prior KG-enhanced recommendation methods.
  • Knowledge Graph-based Recommendation: KG-based recommenders use structural knowledge to enrich user and item representations or interaction modeling.Examples include KG embeddings, joint recommendation and KG completion, and higher-order connectivity modeling.
  • Knowledge Graph-based Recommendation: Existing recommenders primarily leverage KG to design more complex interaction functions and distill better positive signals, leaving negative signals unexplored.This motivates the paper’s focus on knowledge-aware negative sampling from missing data.

6 CONCLUSION AND FUTURE WORK

The paper introduces KGPolicy, an RL-based KG navigation framework for knowledge-aware negative sampling. Experiments and analyses support its effectiveness, including strong performance from MF equipped with KGPolicy and insights into sampled negatives.

  • Conclusion: KGPolicy uses an RL agent and adaptive exploration to navigate from a positive interaction toward potential negative items.Its exploration operation selects sequential neighbors while accounting for user behavior and item knowledge.
  • Conclusion: Experiments on three benchmark datasets demonstrate the rationality and effectiveness of knowledge-aware sampling.MF equipped with KGPolicy improves significantly over state-of-the-art samplers and KG-based recommender models.
  • Conclusion: Analysis indicates that high-quality negative signals help use positive-only data effectively and establish better user and item representations with limited data.The authors also state that these signals provide insights into user intents and sharper preference distributions.
Loading 2003.05753v1…