Sequence aware Reinforcement Learning over Knowledge Graphs

Ashish Gupta Rishabh Mehrotra

Sr Statistical Analyst, Walmart Labs Sr Research Scientist, Spotify Research

Bangalore, India London, UK

Let’s first contextualize!

Last day

Last session

Last talk

Knowledge Graphs are useful

Knowledge represented as entities, edges and attributes

1. Nodes are entities
2. Nodes are labeled with attributes (e.g., types)
3. Edges between nodes capture a relationship between entities

Knowledge Graphs are useful

Knowledge represented as entities, edges and attributes

• Nodes are entities
• Nodes are labeled with attributes (e.g., types)
• Edges between nodes capture a relationship between entities

KGs are flexible

easy to integrate heterogeneous information

Large scale KGs in industry!

Recommendations over a KG

• Embedding models
1. Learn some kind of user and item representations from KG
2. Recommendation based on the similarity between user-item entity:
1. Translational KG Embedding for Rec and Explanation [Ai et al. Alg’2018]
2. Propagating User Preferences on the Knowledge Graph [Wang et al. CIKM’2018]�

​

WWW, SIGIR tutorial: ExplainAble Recommendation and Search (EARS)�https://sites.google.com/view/ears-tutorial/

Recommendations over a KG

• Embedding models
• Learn some kind of user and item representations from KG
• Recommendation based on the similarity between user-item entity:
• Translational KG Embedding for Rec and Explanation [Ai et al. Alg’2018]
• Propagating User Preferences on the Knowledge Graph [Wang et al. CIKM’2018]�

​

WWW, SIGIR tutorial: ExplainAble Recommendation and Search (EARS)�https://sites.google.com/view/ears-tutorial/

Recommendations over a KG

• Embedding models
• Path based recommendations
• Learning Path Embedding for Recommendation [Wang et al. AAAI’2019]
• Jointly Learning Explainable Rules for Recommendation [Ma et al. WWW’2019]
• Path reasoning beginning from user entity:
• Reinforcement KG Reasoning for Explainable Recommendation [Xian et al. SIGIR’2019]

WWW, SIGIR tutorial: ExplainAble Recommendation and Search (EARS)�https://sites.google.com/view/ears-tutorial/

Recommendations over a KG

• Embedding models
• Path based recommendations
• Learning Path Embedding for Recommendation [Wang et al. AAAI’2019]
• Jointly Learning Explainable Rules for Recommendation [Ma et al. WWW’2019]
• Path reasoning beginning from user entity:
• Reinforcement KG Reasoning for Explainable Recommendation [Xian et al. SIGIR’2019]

WWW, SIGIR tutorial: ExplainAble Recommendation and Search (EARS)�https://sites.google.com/view/ears-tutorial/

Recommendations over a KG

• Embedding models
• Path based recommendations
• Learning Path Embedding for Recommendation [Wang et al. AAAI’2019]
• Jointly Learning Explainable Rules for Recommendation [Ma et al. WWW’2019]
• Path reasoning beginning from user entity:
• Reinforcement KG Reasoning for Explainable Recommendation [Xian et al. SIGIR’2019]

WWW, SIGIR tutorial: ExplainAble Recommendation and Search (EARS)�https://sites.google.com/view/ears-tutorial/

SeqReLG: Sequence-aware RL over Graphs

Outline

• Introduction to Knowledge Graphs
• Product knowledge graphs
• Background research: Graph Reasoning PGPR (SIGIR 2019)
• SeqReLG: Sequence aware RL over KG
• Results
• Ongoing Work

Product Knowledge Graphs

Product Knowledge Graphs

Paths in a Knowledge Graph

Reasoning path = how the agent reached the item from the user

Xian, Yikun, et al. "Reinforcement Knowledge Graph Reasoning for Explainable Recommendation." SIGIR 2019

Outline

• Introduction to Knowledge Graphs
• Product knowledge graphs
• Background research: Graph Reasoning PGPR (SIGIR 2019)
• SeqReLG: Sequence aware RL over KG
• Results
• Ongoing Work

Knowledge Graph Reasoning (PGPR)

Step 1: Build Knowledge Graph

​

Xian, Yikun, et al. "Reinforcement Knowledge Graph Reasoning for Explainable Recommendation." SIGIR 2019

Knowledge Graph Reasoning (PGPR)

Step 1: Build Knowledge Graph

Step 2: Learn embeddings

• train embeddings for each entity & relation
• For entities pairs (e, e′) with relations r_k,j , maximize conditional probability:

​

Xian, Yikun, et al. "Reinforcement Knowledge Graph Reasoning for Explainable Recommendation." SIGIR 2019

Knowledge Graph Reasoning (PGPR)

Step 1: Build Knowledge Graph

Step 2: Learn embeddings

• train embeddings for each entity & relation
• For entities pairs (e, e′) with relations r_k,j , maximize conditional probability:
• Huge size of the entity set → adopt a negative sampling to approximate log P(e′ | e,r_k,j ):

​

Xian, Yikun, et al. "Reinforcement Knowledge Graph Reasoning for Explainable Recommendation." SIGIR 2019

Knowledge Graph Reasoning (PGPR)

Step 1: Build Knowledge Graph

Step 2: Learn embeddings

• train embeddings for each entity & relation
• For entities pairs (e, e′) with relations r_k,j , maximize conditional probability:
• Huge size of the entity set → adopt a negative sampling to approximate log P(e′ | e,r_k,j )
• Goal: maximize the objective function:

Xian, Yikun, et al. "Reinforcement Knowledge Graph Reasoning for Explainable Recommendation." SIGIR 2019

Knowledge Graph Reasoning (PGPR)

Step 1: Build Knowledge Graph

Step 2: Learn embeddings

Step 3: Train RL model: policy/value network

• Train an agent:
• starts from a user and walks over the graph
• reach a “good” item node with high probability
• High reward: reach positive item�Low reward: reach negative item

​

Xian, Yikun, et al. "Reinforcement Knowledge Graph Reasoning for Explainable Recommendation." SIGIR 2019

Knowledge Graph Reasoning (PGPR)

Step 1: Build Knowledge Graph

Step 2: Learn embeddings

Step 3: Train RL model: policy/value network

Step 4: Serve recommendations using trained policy network

• For each user:
• employ beam search guided by the action probability reward
• explore the candidate paths as well as the recommended items
• Multiple paths between u & i → select path with highest generative probability
• Rank paths based on path rewards
• recommend corresponding items

​

Xian, Yikun, et al. "Reinforcement Knowledge Graph Reasoning for Explainable Recommendation." SIGIR 2019

Outline

• Introduction to Knowledge Graphs
• Product knowledge graphs
• Background research: Graph Reasoning PGPR (SIGIR 2019)
• SeqReLG: Sequence aware RL over KG
• Results
• Ongoing Work

SeqReLG: Sequence-aware RL over Graphs

SeqReLG: Advancements

RQ1: Can we train better embeddings?

RQ2: How important is considering item sequences in policy/value network?

RQ3: Can we incorporate look-ahead items while evaluating actions?

SeqReLG: Advancements

RQ1: Train better embeddings

• Obtaining positive and negative example is important to get good embeddings
• Can we get better negatives?
• Large no of entities → large vocab size�

​

SeqReLG: Advancements

RQ1: Train better embeddings

• Obtaining positive and negative example is important to get good embeddings
• Can we get better negatives?
• Large no of entities → large vocab size�
• Hierarchical softmax:
• Instead of randomly sampling out-of-context negatives → tree like traversal
• Eliminates the preference towards frequent categories

SeqReLG: Advancements

RQ2: Sequence-aware policy/value network

Reinforcement Learning setup:

• State:
• <u,i,t> user, item, time tuple
• Action:
• outgoing edges of entity e_t
• user-conditional action pruning strategy
• keeps the promising edges conditioned on the starting user based on a scoring function
• Reward:
• a “good” path → one that leads to an item a user will interact with with high probability

​

SeqReLG: Advancements

Policy / value network

SeqReLG: Advancements

Sequence of states

SeqReLG: Advancements

Sequence of states

Sequence important for Multi-Objective modeling

SeqReLG: Advancements

RQ3: Incorporating look-ahead items

SeqReLG: Advancements

RQ3: Incorporating look-ahead items

SeqReLG: Advancements

RQ3: Incorporating look-ahead items

Outline

• Introduction to Knowledge Graphs
• Product knowledge graphs
• Background research: Graph Reasoning PGPR (SIGIR 2019)
• SeqReLG: Sequence aware RL over KG
• Results
• Ongoing Work

Results - I

No change in RL model� → Only embedding training� phase changed

~2% improvement across all metrics

Results - I

No change in RL model� → Only embedding training� phase changed

~2% improvement across all metrics

Better trained embeddings are useful!

Results - II

Added sequence of items

~4% improvement in hit rate

Improvements across all metrics

Results - II

Added sequence of items

~4% improvement in hit rate

Improvements across all metrics

Sequence information of items in the path is helpful!

Results - III

RL model with look-ahead

~9% improvement in precision

Improvements across all metrics

Knowing where the path is headed helps!

Ongoing Work

Ongoing Work

Ongoing Work

Ongoing Work

Multi-objective RL:

• Stakeholders & objectives?
• Diversity
• Exposure of items
• Promotions

​

Ongoing Work

Multi-objective RL:

• Stakeholders & objectives?
• via multi-objective rewards?

​

Ongoing Work

Multi-objective RL:

• Stakeholders & objectives?
• via multi-objective rewards?
• via multi-task policy network?

Ongoing Work

Multi-objective RL:

• Stakeholders & objectives?
• via multi-objective rewards?
• via multi-task policy network?
• pareto-optimal methods?

Thank You!

Summary:

1. Train better embeddings via hierarchical softmax�
2. Sequence information is helpful in policy/value network�
3. Look-ahead helps!

Ashish Gupta

Rishabh Mehrotra

On-going work: