1 of 43

2. Reasoning For Graph-based Recommendation

2 of 43

Outline

1 Introduction
2 Preliminary of Graph-based Explainable Recommendation
3 Literature Review of Graph-based Explainable Recommendation
4 Conclusion

3 of 43

1 Introduction

The application scenario of recommendation:

E-commerce recommendation (Amazon, Taobao, etc.)
Micro-video recommendation (Tiktok, etc.)
Post recommendation (Twitter, etc.)
Point-of-interest recommendation (Yelp, etc.)

4 of 43

1 Introduction

Why is the recommendation systems important?

For the customers:

Saving time to choose needed products

For the merchant:

Bring more earnings through ads
Always catch customer’s attention

5 of 43

1 Introduction

Currently, the recommender systems can obtain high performance thanks to the development of graph neural networks, more and more researchers bring the attention to the explainability of the models. [1]

Why is the explainable recommendation important? [2]

Avoid black box
Facilitate system designers to diagnose, debug and refine the recommendation algorithm.
Give more persuasive, transparent, trustworthy recommendations

[1] Gao, Chen, et al. "Graph Neural Networks for Recommender Systems: Challenges, Methods, and Directions." arXiv preprint arXiv:2109.12843 (2021).

[2] Zhang Y, Chen X. Explainable recommendation: A survey and new perspectives[J]. arXiv preprint arXiv:1804.11192, 2018.

Currently, the recommender systems can already obtain high performance thanks to the development of graph neural networks as mentioned in the first part of the tutorial, more and more researchers bring the attention to the explainability of the models.

Why are the explainable recommendations catch more attention these years? The first reason is to avoid black box. Due to the high performance of neural networks, many recommendations use them to learn user’s interest to improve the effectiveness of recommendation. However, the shortcoming of the neural network also brings to recommender systems, including the black box nature. The second reason is that giving reasons for recommendation could facilitate system designers to diagnose, debug and refine the recommendation algorithm. Last, providing explanation can also give more persuasive, transparent, trustworthy recommendations. People are more likely to choose recommendations with explanations instead of those without explanations because it seems the recommendation more persuasive, and explanations will increase the user stickiness for the application.

6 of 43

Outline

1 Introduction
2 Preliminary of Graph-based Explainable Recommendation
3 Literature Review of Graph-based Explainable Recommendation
4 Conclusion

7 of 43

1 Introduction

Explainable recommender system: [1]

They not only provide users or system designers with recommendation results, but also explanations to clarify why such items are recommended.

[1] Zhang Y, Chen X. Explainable recommendation: A survey and new perspectives[J]. arXiv preprint arXiv:1804.11192, 2018.

8 of 43

2 Preliminary

Graph-based explainable recommendation

Graph-based Explainable

Recommender Systems

Input:

Users
Each user’s historical items
(Each item’s attributes)
(Each user’s attributes)

Output:

Predicted item(s) for each user
Explanation of each predicted item

9 of 43

2 Preliminary

Evaluation of Graph-based explainable recommendation

Performance of recommendation results
Quality of explanation

10 of 43

2 Preliminary

Evaluation of Graph-based explainable recommendation

Performance of recommendation results

Hit Ratio (HR) @ K
Normalized Discounted Cumulative Gain (NDCG) @ K
Precision @ K
Recall @ K

11 of 43

2 Preliminary

12 of 43

2 Preliminary

13 of 43

2 Preliminary

14 of 43

2 Preliminary

15 of 43

2 Preliminary

Evaluation of Graph-based explainable recommendation [1]

Performance of recommendation results
Quality of explanation

User study
Online evaluation
Offline evaluation
Case study

[1] Zhang Y, Chen X. Explainable recommendation: A survey and new perspectives[J]. arXiv preprint arXiv:1804.11192, 2018.

16 of 43

2 Preliminary

Evaluation of Graph-based explainable recommendation [1]

Quality of explanation

User study

The study will design some questions or tasks for the subjects to answer or complete, and conclusions will be derived from the responses of the subjects.

[1] Zhang Y, Chen X. Explainable recommendation: A survey and new perspectives[J]. arXiv preprint arXiv:1804.11192, 2018.

[2] Vig, J., S. Sen, and J. Riedl. 2009. “Tagsplanations: explaining recom- mendations using tags”. In: Proceedings of the 14th international conference on Intelligent user interfaces. ACM. 47–56.

[2]

17 of 43

2 Preliminary

Evaluation of Graph-based explainable recommendation [1]

Quality of explanation

Online evaluation

See if the explanations can help to make users accept the recommendations. It usually tests online. [2]
E.g.: On a commercial web browser, the experimental group receives testing explanations, the comparison group receives the baseline ‘People also viewed’ explanations, and a control group that receives no explanation. The click-through rate of each group is calculated to evaluate the effect of providing personalized explanations.

[1] Zhang Y, Chen X. Explainable recommendation: A survey and new perspectives[J]. arXiv preprint arXiv:1804.11192, 2018.

[2] Zhang, Y., G. Lai, M. Zhang, Y. Zhang, Y. Liu, and S. Ma. “Explicit factor models for explainable recommendation based on phrase-level sentiment analysis”. SIGIR. ACM. 83–92. 2014.

18 of 43

2 Preliminary

Evaluation of Graph-based explainable recommendation [1]

Quality of explanation

Offline evaluation

Model Fidelity (MF)

[1] Zhang Y, Chen X. Explainable recommendation: A survey and new perspectives[J]. arXiv preprint arXiv:1804.11192, 2018.

19 of 43

2 Preliminary

Evaluation of Graph-based explainable recommendation [1]

Quality of explanation

Offline evaluation

Bilingual Evaluation Understudy (BLEU) [2], if sentence

[1] Zhang Y, Chen X. Explainable recommendation: A survey and new perspectives[J]. arXiv preprint arXiv:1804.11192, 2018.

[2] Papineni K, Roukos S, Ward T, et al. Bleu: a method for automatic evaluation of machine translation[C]//ACL. 2002: 311-318.

c is the length of the generated sentence and r is the ground-truth sentence length.

20 of 43

2 Preliminary

Evaluation of Graph-based explainable recommendation [1]

Quality of explanation

Offline evaluation

Recall-oriented Understudy for Gisting Evaluation (ROUGE), if sentence

[1] Zhang Y, Chen X. Explainable recommendation: A survey and new perspectives[J]. arXiv preprint arXiv:1804.11192, 2018.

[2] Lin C Y. Rouge: A package for automatic evaluation of summaries[C]//Text summarization branches out. 2004: 74-81.

21 of 43

2 Preliminary

Evaluation of Graph-based explainable recommendation [1]

Quality of explanation

Case study

Providing case studies can help to understand the intuition behind the explainable recommendation model and the effectiveness of explanations.

[1] Zhang Y, Chen X. Explainable recommendation: A survey and new perspectives[J]. arXiv preprint arXiv:1804.11192, 2018.

[2] Chen H, Li Y, Sun X, et al. Temporal meta-path guided explainable recommendation[C]//WSDM. 2021: 1056-1064.

[2]

22 of 43

Outline

1 Introduction
2 Preliminary of Graph-based Explainable Recommendation
3 Literature Review of Graph-based Explainable Recommendation
4 Conclusion

23 of 43

3 Literature Review

Classification of graph-based explainable recommendation

Homogeneous graph

Use collaborative information as reasoning

Heterogeneous graph

Regard path as reasoning
Generate sentences as reasoning
Extract sentences as reasoning
Consider visualized relation as reasoning
…

24 of 43

3 Literature Review

Classification of graph-based explainable recommendation

On homogeneous graph

A bipartite graph is constructed on the recommendation data (only including users and items).
Feature: The explanation is mostly based on the collaborative information.
Related work: [1]

Shortcoming: It does not involve the external information.

[1] Heckel R, Vlachos M, Parnell T, et al. Scalable and interpretable product recommendations via overlapping co-clustering[C]//ICDE. IEEE, 2017: 1033-1044.

This kind of method always constructs a bipartite graph on the recommendation data, which only include users and items. So, they usually use collaborative information to explain the recommendation. No matter how they provide the explanation, including use user or item to explain, use the textual sentence to explain, and so on. The core of the explanation are all based on collaborative information. For example, here is a work use collaborative information and a sentence template to provide explanation. The explanation is the item is recommened to client 4 because he is similar to client 5 and client 6 in the first cluster who also bought this item. However, this kind of explanation only involves collaborative information, and ignore some external information, like the attributes of the items. Therefore, the explanation tends to be improper and one-sided.

25 of 43

3 Literature Review

Classification of graph-based explainable recommendation

Homogeneous graph

Use collaborative information as reasoning

Heterogeneous graph

Regard words as reasoning
Regard sentences as reasoning
Regard path as reasoning
Regard visual graph as reasoning
…

26 of 43

3 Literature Review

Classification of graph-based explainable recommendation

On heterogeneous graph

A heterogenous graph is constructed on the recommendation data (including users, items and other external information).
Feature: It involves the external information compared with the homogeneous graph-based explainable recommendation. Moreover, the explanation tends to be more kinds.

27 of 43

3 Literature Review

Classification of graph-based explainable recommendation

On heterogeneous graph - Regard words as reasoning
Related work [1]

[1] Huang, J., W. X. Zhao, H. Dou, J.-R. Wen, and E. Y. Chang (2018). “Improving sequential recommendation with knowledge-enhanced memory networks”. In: ACM SIGIR. ACM. 505–514.

One of the type of explanation is to use words to explain. Here is an example work to use the attributes of music as the explanation, including singer, album and so on. In the figure, the left squares are the attentions of each attribute. The second line squares are the singer attention and the third line square are the album attentions. The darker the square is, the more weight of the attention. So the reason for user listening to the pecan tree is more because of the same album as the vertigo.

(This work firstly construct the whole data as a knowledge graph, and then to explain the recommendations, the model detects the attributes that are taking effect when predicting the recommended music. For a particular music recommendation as an example, it can detect whether the album attribute is more important or the singer attribute is more important, where the attributes come from an external knowledge graph. )

28 of 43

3 Literature Review

Classification of graph-based explainable recommendation

On heterogeneous graph - Regard sentences as reasoning
Related work [1]

[1] Ai, Q., V. Azizi, X. Chen, and Y. Zhang (2018). “Learning heterogeneous knowledge base embeddings for explainable recommendation”. Algorithms. 11(9): 137.

Textual sentence:

B9C is recommended because the user often purchases items that are bought with BTU together, and B9C is also frequently bought with BTU together.
B9C is recommended because the user often purchases items that are bought with BYS together, and B9C is also frequently bought with BYS together.

Another type of explanation is to use sentence. here is an example to use sentence to explain the recommendation. This work construct a knowledge graph with entities, including, users, items, and items’ attributes. It uses a naïve Breadth-first search ( which is BFS) to explore the shortest path. And then, generate the textual sentences according to templates. In this box, it is the explanation. B9C is recommended because the user often purchases items that are bought with BTU together, and B9C is also frequently bought with BTU together. However, this kind of explanation is sometimes not fluent because of the bottleneck of natural language processing method. and use the template to express sentence is always too boring and stock.

(For example, a typical relation in the knowledge graph is “User A purchased Item B belonging to Category C”. Moreover, they embed each entity for recommendation and adopt the shortest relation path between a user and an item in the knowledge graph to indicate the recommendation explanations. This work )

29 of 43

3 Literature Review

Classification of graph-based explainable recommendation

On heterogeneous graph - Regard path as reasoning

Intuitively, paths with lengths 2 on the graph represents the relation between two nodes and paths with more than lengths 2 represent compositional relations.

Meta-path [1]
Meta-path instance [2] / specific path

[1] Sun Y, Han J. Mining heterogeneous information networks: principles and methodologies[J]. Synthesis Lectures on Data Mining and Knowledge Discovery, 2012, 3(2): 1-159.

[2] Sun Y, Han J. Meta-path-based search and mining in heterogeneous information networks[J]. Tsinghua Science and Technology, 2013, 18(4): 329-338.

30 of 43

3 Literature Review

Classification of graph-based explainable recommendation

On heterogeneous graph - Regard path as reasoning

Meta-path [1]

A meta path is an ordered sequence of node types and edge types defined on the network schema, which describes a composite relation between the nodes' types involved.
e.g., Author-Paper-Author (APA) → co-authors;
Author-Paper-Venue-Paper-Author (APVPA) →two authors who published papers in the same venue.

[1] Sun Y, Han J. Mining heterogeneous information networks: principles and methodologies[J]. Synthesis Lectures on Data Mining and Knowledge Discovery, 2012, 3(2): 1-159.

31 of 43

3 Literature Review

Classification of graph-based explainable recommendation

On heterogeneous graph - Regard path as reasoning

Meta-path
Related work [1]

Each meta-path represents a semantic meaning in the model.

[1] Shi C, Zhang Z, Luo P, et al. Semantic path based personalized recommendation on weighted heterogeneous information networks[C]//CIKM. 2015: 453-462.

Shortcoming: Meta-path schema can only provide general and high-level explanations, because each node in the meta-path represents a type.

32 of 43

3 Literature Review

Classification of graph-based explainable recommendation

On heterogeneous graph - Regard path as reasoning

Meta-path instance

A meta path instance context is the general information of several instances from the same start node to the same end node.
e.g., All meta path instances from Alice to I see Fire : [1]
𝜙_1: Alice →Shape of You →Ed Sheeran → I see Fire
𝜙_2 : Alice → Shape of You → Tony → I see Fire
A meta path instance context from Alice to I see Fire : 𝜙=𝛼_1 𝜙_1+𝛼_2 𝜙_2

[1] Hu B, et al. Leveraging meta-path based context for top-n recommendation with a neural co-attention model[C]//KDD. 2018: 1531-1540.

33 of 43

3 Literature Review

Classification of graph-based explainable recommendation

On heterogeneous graph - Regard path as reasoning

Meta-path instance
Related work (TMER) [1]

[1] Chen H, Li Y, Sun X, et al. Temporal meta-path guided explainable recommendation[C]//WSDM. 2021: 1056-1064.

Meta-path instance as explanation

34 of 43

3 Literature Review

Classification of graph-based explainable recommendation

On heterogeneous graph - Regard path as reasoning

Meta-path instance
Related work (TMER) [1]

Evaluation of explainability:

[1] Chen H, Li Y, Sun X, et al. Temporal meta-path guided explainable recommendation[C]//WSDM. 2021: 1056-1064.

35 of 43

3 Literature Review

Classification of graph-based explainable recommendation

On heterogeneous graph - Regard visual graph as reasoning
Related work [1]

The predictions are based on a collaborative analysis of preference data from a user’s direct peer group on a social network. Users also learn a wealth of information about the preferences of their peers through interaction with the visualization.

[1] Gretarsson B, O'Donovan J, Bostandjiev S, et al. Smallworlds: visualizing social recommendations[C]//Computer graphics forum. Oxford, UK: Blackwell Publishing Ltd, 2010, 29(3): 833-842.

36 of 43

3 Literature Review

Classification of graph-based explainable recommendation

On heterogeneous graph - Regard visual graph as reasoning
Related work [1]

The predictions are based on a collaborative analysis of preference data from a user’s direct peer group on a social network. Users also learn a wealth of information about the preferences of their peers through interaction with the visualization.

[1] Gretarsson B, O'Donovan J, Bostandjiev S, et al. Smallworlds: visualizing social recommendations[C]//Computer graphics forum. Oxford, UK: Blackwell Publishing Ltd, 2010, 29(3): 833-842.

37 of 43

Outline

1 Introduction
2 Preliminary of Graph-based Explainable Recommendation
3 Literature Review of Graph-based Explainable Recommendation
4 Conclusion

38 of 43

4 Conclusion

Introduce the recommendation system and its explainability
Classify the explainable recommendation

Homogeneous graph

Use collaborative information as reasoning

Heterogeneous graph

Regard words as reasoning
Regard sentences as reasoning
Regard path as reasoning
Regard visual graph as reasoning
…

explainability

Performance of recommendation

Trade-off of explainability and performance

We introduce the recommednation system and its expalinablility. And we classify the explainable recommedantion into the following types. In the homogeneous graph, they usually use collaborative information as reasoning, and in the heterogeneous graph, they usually use words, sentences, paths and visual graph as reasoning. And roughly, the explainability and the performance of the recommendaion are of this relation. When the performance is low, the explaiablity is good. And otherwise, the explainability is low. That is because the deep learing-based explianbility always could get better performance but the black-box nature also makes the recommendation less explainability. However, methods without the deep learning methods, always could get better explianbiliyt, but their performance cannot outperform the deep learning recommendations. The goal of the explainble recommedation is to keep high performace of the recommendation and also provide better explainability .

39 of 43

4 Conclusion

Future direction of graph-based explainable recommendation

Dynamic graph explainable recommendation

Sequential feature is an important information in recommendation and explanation. However, the existing graph-based explainable recommendation are almost based on static graphs.
Challenge:

How to design an effective and efficient dynamic graph model to do explainable recommendation?

[1]

[1] Time Matters: Sequential Recommendation with Complex Temporal Information. SIGIR 2020.

Here I lists several future direction of the graph-based explainable recommendation. The first one is dynamic graph explainable recommendation.

Sequential feature is an important information in recommendation and explanation. For example, in this figure, it is unlikely for the user to firstly buy a guitar string and then buy a guitar. This sequential information is not only necessary for the recommender system, but also important information when giving explanations. Because this temporal information can also be an explanation to buy a guitar string.

Howedver, the exisint graph-based explainable recommendation are almost based on static graphs. In this way, it is hard to model the dynamic evolution of the recommendation graph. The challenge is how to design an effective and efficient dynamic graph model to do explainable recommendation.

40 of 43

4 Conclusion

Future direction of graph-based explainable recommendation

Causality-based explainable recommendation

It has been adopted in machine learning to provide causal relation for better explainability in model.
Challenge:

How to combine the causal learning in graph to do recommendation?

41 of 43

4 Conclusion

Future direction of graph-based explainable recommendation

Sentence-based explainable recommendation

Providing high quality, fluent sentences for explanation is always a hot topic.
Challenge:

Bottleneck of natural language processing

42 of 43

4 Conclusion

Future direction of graph-based explainable recommendation

Evaluation for the quality of explainability

The evaluation is not sufficient currently. Most of the papers use case study or user study to test the quality of explainability.
Challenge:

How to define the good quality of explanation?
How to use metric to evaluate?

43 of 43

Thanks for your listening.