Source-linked AI summary
Reinforcement Knowledge Graph Reasoning for Explainable Recommendation
Yikun Xian, Zuohui Fu, S. Muthukrishnan, Gerard de Melo, Yongfeng Zhang
TL;DR
Recommendation research has often used knowledge graphs for accuracy, while leaving explicit decision reasoning and its interpretability limited. The paper proposes PGPR, an RL framework that navigates from users to items, prunes actions conditionally, uses soft rewards and multi-hop scoring, and samples reasoning paths with policy-guided search. Experiments report strong recommendation results together with explainable paths on Amazon domains.
Problem
The paper addresses the gap between using knowledge graphs for recommendation and performing explicit, interpretable reasoning that connects each recommended item to a graph path.
Method
PGPR formulates recommendation as reinforcement-learning navigation over a knowledge graph using soft rewards, user-conditional action pruning, multi-hop scoring, and policy-guided path search.
Results
PGPR achieves outstanding recommendation results while exposing reasoning procedures for explainability, with extensive experiments reporting strong results and explainable paths on Amazon domains.
Takeaways & Limitations
The framework couples recommendation with interpretable evidence by using actual knowledge-graph reasoning paths to support recommended items.
Takeaways & Limitations
Using identical learning-rate and training-step settings across action-space choices may produce suboptimal solutions for larger action spaces.
Abstract
from arXiv · showhide
Recent advances in personalized recommendation have sparked great interest in the exploitation of rich structured information provided by knowledge graphs. Unlike most existing approaches that only focus on leveraging knowledge graphs for more accurate recommendation, we perform explicit reasoning with knowledge for decision making so that the recommendations are generated and supported by an interpretable causal inference procedure. To this end, we propose a method called Policy-Guided Path Reasoning (PGPR), which couples recommendation and interpretability by providing actual paths in a knowledge graph. Our contributions include four aspects. We first highlight the significance of incorporating knowledge graphs into recommendation to formally define and interpret the reasoning process. Second, we propose a reinforcement learning (RL) approach featuring an innovative soft reward strategy, user-conditional action pruning and a multi-hop scoring function. Third, we design a policy-guided graph search algorithm to efficiently and effectively sample reasoning paths for recommendation. Finally, we extensively evaluate our method on several large-scale real-world benchmark datasets, obtaining favorable results compared with state-of-the-art methods.
1 INTRODUCTION
The paper frames explainable recommendation as explicit multi-step reasoning over knowledge graphs, using reinforcement learning to navigate from users to items while retaining reasoning paths as evidence. PGPR combines soft rewards, user-conditional action pruning, multi-hop scoring, and policy-guided search, achieving strong results and explainable paths on Amazon domains.
- Motivation: Knowledge graphs provide structured relationships that can improve recommendation performance and support more interpretable reasoning.The paper contrasts this with approaches that use graph embeddings primarily for similarity matching.
- Problem and approach: PGPR treats recommendation as explicit multi-step path reasoning from a user to suitable items, with paths serving as interpretable evidence for each recommendation.The method casts the task as a deterministic MDP and trains an RL agent to navigate the graph.
- Method: The RL approach addresses terminal rewards and large action spaces through soft rewards, a multi-hop scoring function, and user-conditional action pruning.Action pruning retains promising edges conditioned on the starting user.
- Method: A policy-guided beam-search algorithm efficiently samples diverse reasoning paths and candidate item sets for recommendation.The search is guided by the learned policy network.
- Evaluation: The paper evaluates PGPR extensively on Amazon e-commerce domains, reporting strong recommendation results and explainable reasoning paths.The introduction identifies both effectiveness and path explainability as evaluation outcomes.
2 RELATED WORK
Prior recommendation research includes collaborative filtering, knowledge-graph embeddings, path-based methods, and reinforcement learning. Existing KG path approaches face scalability or coverage limitations, motivating a method that reasons over large graphs more flexibly.
- Collaborative filtering: Collaborative filtering evolved from user–item rating matrices toward latent factor models such as matrix factorization.Examples include singular value decomposition, non-negative matrix factorization, and probabilistic matrix factorization.
- Knowledge-graph methods: Knowledge-graph embedding methods use graph information as content or representation features to enhance recommendation.Examples include knowledge-base embeddings for user and item representations and memory networks over entity embeddings.
- Path-based recommendation: An RNN path-embedding method requires enumerating all possible paths between every user–item pair, which can be impractical for large-scale knowledge graphs.The computational burden arises during both model training and prediction.
- Reinforcement learning: Reinforcement learning has been applied to recommendation in non-knowledge-graph settings and explored for reasoning in knowledge-graph settings.The cited non-KG applications include ads, news, and post-hoc explainable recommendation.
3 METHODOLOGY
PGPR formulates explainable recommendation as path reasoning over a knowledge graph, using reinforcement learning to navigate from users toward items while jointly producing reasoning paths. Its design combines user-conditioned action pruning, soft terminal rewards, shared policy/value networks, and beam search for diverse candidate paths.
- 3.1 Problem Formulation: The KGRE-Rec problem finds recommended items for each user and associates every recommendation with a 2- to K-hop reasoning path.The formulation explicitly couples item recommendation with path finding over the recommendation knowledge graph.
- 3.1 Problem Formulation: Post-hoc recommendation is limited because it separates similarity-based item selection from path finding and leaves the decision process uninterpretable.It also fails to exploit the knowledge graph’s heterogeneous metadata during recommendation.
- 3.2 Formulation as Markov Decision Process: PGPR casts recommendation as a deterministic MDP in which an RL agent starts at a user and navigates toward potential items, using the path history as an explanation.Reverse edges preserve connectivity, while NOOP self-loops allow the agent to remain at an entity.
- 3.2 Formulation as Markov Decision Process: Each state records the starting user, current entity, and prior path history; the initial state is (u,u, ) and the terminal state is (u,eT,hT) at fixed horizon T.The k-step history contains entities and relations from the preceding k steps.
- 3.2 Formulation as Markov Decision Process: User-conditional action pruning retains at most α high-scoring outgoing edges, reducing exploration over nodes with large out-degrees.The pruned action space is defined by ranking the edge score f((r,e) | u) and keeping ranks no greater than α.
- 3.2 Formulation as Markov Decision Process: Because target items are unknown, PGPR assigns a normalized soft reward only at the terminal state using the user–item score f(u,i).The reward encourages paths leading to items a user is likely to interact with, with RT normalized to [0, 1].
- 3.2 Formulation as Markov Decision Process: REINFORCE trains shared-feature policy and value networks, while entropy regularization encourages exploration of more diverse paths.The policy masks pruned actions, and the value network supplies the REINFORCE baseline.
- 3.4 Policy-Guided Path Reasoning: Beam search guided by policy probabilities and path rewards samples diverse T-hop reasoning paths with associated generation probabilities and rewards.The procedure takes the user, policy network, horizon T, and per-step sampling sizes K1, …, KT as inputs.
4 EXPERIMENTS
The experiments evaluate PGPR on Amazon e-commerce knowledge graphs, comparing recommendation quality, path discovery, pruning, scoring, and state-history choices. PGPR consistently outperforms baselines while producing interpretable reasoning paths, though larger action spaces may be harder to optimize under fixed training settings.
- Experimental Setup: Experiments use four Amazon e-commerce benchmarks, each represented as a knowledge graph with 5 entity types and 7 relation types.The categories are CDs and Vinyl, Clothing, Cell Phones, and Beauty.
- Recommendation Effectiveness: PGPR consistently outperforms all baselines across NDCG, Hit Rate, Recall, and Precision on all four datasets.The metrics are computed from each user's top-10 test predictions.
- Recommendation Effectiveness: PGPR improves NDCG over the best baseline by 3.94% on CDs & Vinyl, 64.73% on Clothing, 15.53% on Cell Phone, and 23.95% on Beauty.Similar trends are reported for Recall, Hit Rate, and Precision.
- Path Analysis: The method finds valid user-to-item paths within three hops with an approximately 50% success rate, and multiple supportive paths can exist for each recommendation.The authors suggest providing more than one path when users request further details.
- Action Pruning: On Clothing, PGPR outperforms JRL across NDCG, Recall, Hit Rate, and Precision for pruned action spaces ranging from 100 to 500.Across the evaluated figures, smaller pruned action spaces generally yield better performance.
- Action Pruning: Larger action spaces may produce suboptimal solutions because identical learning rates and training steps provide insufficient exploration for those settings.This is a fairness-preserving experimental choice rather than a claimed inherent failure of larger action spaces.
- Multi-Hop Scoring: The 2-hop PGPR variant further outperforms the default model because multi-hop scoring captures interactions between entities at longer distances.The paper illustrates this with the {Purchase, Belong_to} pattern connecting a user to a category.
- State History: State representations without history perform worst, indicating that history provides information needed by the recommendation policy.The comparison includes 0-step, 1-step, and 2-step history alternatives.
5 CASE STUDY ON PATH REASONING
PGPR discovers diverse multi-hop reasoning paths and uses them to make recommendations interpretable through concrete user–item connections.
- Path patterns: For a fixed path length of 3, PGPR discovers 15 different path patterns.
- Case study: The case studies show recommendations supported by shared features, purchase histories, co-purchase behavior, and category membership.
- Case study: In the Beauty example, shared “nourish” and “lightening” features connect a purchased shampoo to a recommended conditioner.
- Case study: Other examples use overlapping review features to transfer a running-shoes purchase, co-purchase behavior to recommend an iPhone case, and category membership to recommend a key chain.
- Conclusion: The authors conclude that PGPR achieves promising recommendation results while efficiently finding diverse reasoning paths.
6 CONCLUSIONS AND FUTURE WORK
The paper presents PGPR as an RL-based framework for recommendation with interpretable reasoning paths. It reports strong recommendation results and identifies extensions to other graph tasks and time-evolving graphs.
- PGPR combines soft rewards, user-conditional action pruning, and multi-hop scoring to expose its reasoning procedure for explainability.
- The authors report outstanding recommendation results supported by extensive comparisons with state-of-the-art baselines.
- PGPR could be extended to product search, social recommendation, and time-evolving graphs for dynamic decision support.