E-commerce Graph-Based Recommendation System

Luận văn thạc sĩ về hệ thống gợi ý sản phẩm thương mại điện tử dựa trên đồ thị. Nghiên cứu ứng dụng graph embedding và Node2Vec để cá nhân hóa trải nghiệm mua sắm.

• Tác giả: Vo Thi Kim Nguyet
• Người hướng dẫn: Le Thanh Van, Ph.D
• Trường học: Ho Chi Minh City University of Technology
• Chuyên ngành: Computer Science
• Đề tài: E-commerce Graph-Based Recommendation System
• Loại tài liệu: Master’s Thesis
• Năm xuất bản: 2023
• Địa điểm: Ho Chi Minh City

Tóm tắt

I. Tìm Hiểu Hệ Thống Gợi Ý Thương Mại Điện Tử Tổng Quan Quan Trọng

Nghiên cứu này tập trung vào việc nâng cao hệ thống gợi ý thương mại điện tử bằng cách khám phá các thuật toán tiên tiến và thực hiện thử nghiệm A/B để thu thập thông tin chi tiết thực tế. Sử dụng một tập dữ liệu quy mô lớn, nghiên cứu này đề xuất một thuật toán hiện đại nhằm cải thiện độ chính xác và hiệu quả. Mục tiêu là thu hẹp khoảng cách giữa lý thuyết và thực hành, cách mạng hóa hệ thống gợi ý và tối đa hóa sự hài lòng của người dùng trong thương mại điện tử. Nghiên cứu tận dụng một tập dữ liệu lớn từ REES46 để đạt được những mục tiêu này. Hệ thống recommender system ecommerce cá nhân hóa ngày càng trở nên quan trọng với sự bùng nổ về số lượng sản phẩm.

1.1. Tầm Quan Trọng Của Cá Nhân Hóa Trong Thương Mại Điện Tử

Luận văn này tập trung vào hệ thống gợi ý thương mại điện tử, nơi cá nhân hóa thương mại điện tử là rất quan trọng do số lượng lớn sản phẩm có sẵn trên nhiều trang web. Các hệ thống gợi ý truyền thống như Content-Based Filtering và Collaborative Filtering gặp phải các vấn đề về khả năng mở rộng, tính thưa thớt và vấn đề cold start, làm giảm hiệu quả của chúng trong việc xử lý các bản ghi giao dịch quy mô lớn và thưa thớt. Để giải quyết những thách thức này, dự án đề xuất sử dụng các kỹ thuật nhúng đồ thị (graph embedding), đặc biệt là Random Walks, để nắm bắt chuỗi hành vi của người dùng và tạo ra các nhúng đồ thị (graph embedding) cho các sản phẩm.

1.2. Câu Hỏi Nghiên Cứu và Phương Pháp Tiếp Cận

Luận văn này nhằm mục đích giải quyết tính hiệu quả của các kỹ thuật dựa trên đồ thị, cụ thể là Random Walks và FAISS, trong việc nắm bắt chuỗi hành vi của người dùng và tạo ra các nhúng đồ thị (graph embedding) cho các sản phẩm được cải thiện trong gợi ý sản phẩm so với các phương pháp truyền thống. Để điều tra kỹ lưỡng các câu hỏi nghiên cứu này, phương pháp luận sau sẽ được sử dụng: Thu thập dữ liệu từ nền tảng thương mại điện tử thông qua tương tác của người dùng, bản ghi giao dịch và siêu dữ liệu của sản phẩm. Triển khai và tinh chỉnh hệ thống graph-based recommender system đề xuất.

II. Vấn Đề Của Hệ Thống Gợi Ý Giải Quyết Thách Thức

Hệ thống gợi ý sản phẩm đối mặt với nhiều thách thức, đặc biệt trong môi trường thương mại điện tử. Vấn đề cold start xảy ra khi hệ thống không có đủ thông tin về người dùng hoặc sản phẩm mới, dẫn đến việc gợi ý không chính xác. Tính thưa thớt dữ liệu cũng là một vấn đề lớn, khi hầu hết người dùng chỉ tương tác với một phần nhỏ của tổng số sản phẩm. Khả năng mở rộng là một thách thức khác, vì hệ thống cần xử lý lượng lớn dữ liệu và tương tác của người dùng một cách hiệu quả. Các phương pháp truyền thống thường gặp khó khăn trong việc giải quyết đồng thời các thách thức này, làm giảm hiệu suất hệ thống gợi ý.

2.1. Giới Thiệu Các Phương Pháp Gợi Ý Dựa Trên Đồ Thị

Dự án sử dụng một đồ thị vô hướng cho hệ thống gợi ý sản phẩm dựa trên dữ liệu clickstream. Không giống như đồ thị có hướng, nắm bắt các mối quan hệ một chiều, đồ thị vô hướng thể hiện các mối quan hệ hai chiều giữa các sản phẩm và người dùng. Các đề xuất được đưa ra dựa trên sự tương đồng giữa các nút, được tính toán bằng cách sử dụng các biện pháp như cosine similarity hoặc Jaccard similarity. Dữ liệu clickstream được tiền xử lý và chuyển đổi thành ba loại đồ thị đồng xuất hiện, thể hiện các mối quan hệ sản phẩm khác nhau dựa trên hành động của người dùng.

2.2. Phân Tích Dữ Liệu và Xây Dựng Đồ Thị Đồng Xuất Hiện

Phương pháp luận của dự án liên quan đến việc sử dụng một đồ thị vô hướng cho một hệ thống gợi ý sản phẩm dựa trên dữ liệu clickstream. Không giống như đồ thị có hướng, nắm bắt các mối quan hệ một chiều, đồ thị vô hướng thể hiện các mối quan hệ hai chiều giữa các sản phẩm và người dùng. Các đề xuất được đưa ra dựa trên sự tương đồng giữa các nút, được tính toán bằng cách sử dụng các biện pháp như cosine similarity hoặc Jaccard similarity. Dữ liệu clickstream được tiền xử lý và chuyển đổi thành ba loại đồ thị đồng xuất hiện, thể hiện các mối quan hệ sản phẩm khác nhau dựa trên hành động của người dùng.

III. Node2Vec và FAISS Giải Pháp Tối Ưu Gợi Ý Sản Phẩm E Commerce

Nghiên cứu này tập trung vào việc sử dụng Node2Vec và FAISS để xây dựng hệ thống gợi ý sản phẩm hiệu quả trong thương mại điện tử. Node2Vec giúp biểu diễn các nút trong đồ thị thành các vector, từ đó nắm bắt được mối quan hệ giữa các sản phẩm và người dùng. FAISS được sử dụng để tìm kiếm các sản phẩm tương tự một cách nhanh chóng và hiệu quả, giúp hệ thống đưa ra gợi ý kịp thời và chính xác. Việc kết hợp hai công nghệ này giúp giải quyết các vấn đề về khả năng mở rộng và tính thưa thớt dữ liệu, đồng thời cải thiện tối ưu hóa gợi ý cho người dùng.

3.1. Kỹ Thuật Nhúng Đồ Thị Với Random Walks và Node2Vec

Để xử lý hiệu quả kích thước đồ thị lớn, thuật toán Random Walks, kết hợp các kỹ thuật DeepWalk và Node2Vec, được áp dụng. DeepWalk nắm bắt chuỗi hành vi của người dùng và tạo ra các nhúng đồ thị (graph embedding), trong khi Node2Vec nắm bắt thông tin cấu trúc cục bộ và toàn cục để nâng cao các nhúng đồ thị (graph embedding). Các kỹ thuật này chuyển đổi đồ thị thành các vector embedding chiều thấp có ý nghĩa, nắm bắt sự tương đồng và mối quan hệ giữa các sản phẩm.

3.2. Sử Dụng FAISS Để Tìm Kiếm Tương Tự Hiệu Quả Trong Gợi Ý

FAISS (Facebook AI Similarity Search) được sử dụng để tìm kiếm hiệu quả các láng giềng gần nhất trong quy trình gợi ý sản phẩm. Nó lập chỉ mục và sắp xếp các vector embedding, cho phép truy xuất nhanh chóng và chính xác các sản phẩm tương tự. FAISS giúp tối ưu hóa gợi ý và cải thiện đáng kể tốc độ gợi ý sản phẩm.

IV. Ứng Dụng Thực Tế Hệ Thống Gợi Ý Kết Quả Thử Nghiệm

Để đánh giá hiệu quả của hệ thống gợi ý sản phẩm, các thử nghiệm đã được thực hiện trên một tập dữ liệu lớn từ thương mại điện tử. Các kết quả cho thấy rằng hệ thống graph-based recommender system sử dụng Node2Vec và FAISS vượt trội so với các phương pháp truyền thống về độ chính xác và tốc độ. Hệ thống có khả năng gợi ý các sản phẩm phù hợp với sở thích của người dùng, đồng thời giải quyết được vấn đề cold start và tính thưa thớt dữ liệu. Các kết quả này chứng minh tiềm năng của việc sử dụng đồ thị trong cá nhân hóa thương mại điện tử.

4.1. Đánh Giá Hiệu Quả Với Các Metric Hàng Đầu

Hiệu suất của hệ thống gợi ý sản phẩm được đánh giá bằng cách sử dụng các metric top-N nhận biết thứ hạng, chẳng hạn như Precision at N, Recall at N, Mean Average Precision (MAP) và Normalized Discounted Cumulative Gain (NDCG). Các metric này đánh giá một cách toàn diện độ chính xác, mức độ liên quan, sự đa dạng và vị trí xếp hạng của các đề xuất của hệ thống. Các thử nghiệm này cho thấy khả năng đánh giá hiệu quả gợi ý của hệ thống.

4.2. So Sánh Với Các Phương Pháp Gợi Ý Truyền Thống

Các mô hình truyền thống sẽ được phát triển và cấu hình như một đường cơ sở để so sánh với phương pháp dựa trên đồ thị. Độ chính xác và hiệu quả của các hệ thống dựa trên đồ thị và lọc cộng tác sẽ được đánh giá bằng cách sử dụng các metric đề xuất tiêu chuẩn như Mean Average Precision (MAP), Recall, Precision và Normalized Discounted Cumulative Gain (NDCG). Các kết quả cho thấy hệ thống gợi ý thương mại điện tử dựa trên đồ thị vượt trội hơn hẳn.

V. Kết Luận và Hướng Phát Triển Hệ Thống Gợi Ý Tương Lai

Nghiên cứu này đã chứng minh tiềm năng của việc sử dụng Node2Vec và FAISS trong việc xây dựng hệ thống gợi ý sản phẩm hiệu quả cho thương mại điện tử. Hệ thống có khả năng cá nhân hóa thương mại điện tử, giải quyết các vấn đề về khả năng mở rộng và tính thưa thớt dữ liệu. Trong tương lai, nghiên cứu có thể tập trung vào việc tích hợp thêm thông tin về người dùng và sản phẩm, sử dụng các thuật toán học máy trên đồ thị (graph machine learning) phức tạp hơn, và triển khai hệ thống trên quy mô lớn. Các hướng phát triển này hứa hẹn sẽ mang lại những cải tiến đáng kể cho hệ thống gợi ý sản phẩm.

5.1. Tóm Tắt Các Đóng Góp Chính Của Nghiên Cứu

Luận văn này trình bày một hệ thống đề xuất dựa trên đồ thị được thiết kế riêng để đưa ra các gợi ý nội dung được cá nhân hóa trong thương mại điện tử. Sử dụng các phương pháp nhúng đồ thị như DeepWalk và Node2Vec như một phần của kỹ thuật Random Walks, hệ thống nắm bắt các chuỗi hành vi của người dùng và tạo ra các nhúng đồ thị (graph embedding) cho các sản phẩm. Những nhúng đồ thị (graph embedding) này tạo điều kiện thuận lợi cho việc tính toán độ tương đồng theo cặp giữa các sản phẩm, tạo thành cơ sở cho các đề xuất nội dung bắt nguồn từ các metric tương đồng.

5.2. Hướng Nghiên Cứu Mở Rộng và Phát Triển Hệ Thống

Để giải quyết các thách thức như tính thưa thớt và cold start, thông tin bổ sung được tích hợp liền mạch vào framework nhúng đồ thị (graph embedding). Đánh giá thực nghiệm bằng dữ liệu clickstream chứng minh tính ưu việt của phương pháp được đề xuất so với các kỹ thuật lọc cộng tác truyền thống về cả độ chính xác và hiệu quả. Nghiên cứu đóng góp một hệ thống đề xuất dựa trên đồ thị mới giải quyết các vấn đề về khả năng mở rộng, tính thưa thớt và cold start, đồng thời được làm phong phú hơn nữa bằng cách kết hợp dữ liệu bổ sung để nâng cao hiệu quả của hệ thống đề xuất.

Trích đoạn nội dung tài liệu

VIETNAM NATIONAL UNIVERSITY HO CHI MINH CITY HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY VO THI KIM NGUYET ECOMMERCE GRAPH-BASED RECOMMENDATION SYSTEM Major: COMPUTER SCIENCE Major code: 8480101 MASTER’S THESIS HO CHI MINH CITY, July 2023 THIS THESIS IS COMPLETED AT HO CHI MINH UNIVERSITY OF TECHNOLOGY – VNU-HCM Supervisor: Le Thanh Van, Ph. Huynh Tuong Nguyen, Ph.D Examiner 2: Ton Long Phuoc, Ph.D This master’s thesis is defended at Ho Chi Minh City University of Technology (HCMUT) – VNU-HCM on 11th July 2023 Master’s Thesis Committee: 1. Tran Ngoc Thinh, Ph. Huynh Tuong Nguyen, Ph.

Ton Long Phuoc, Ph. Le Thanh Van, Ph. Nguyen Tien Thinh, Ph.D Secretary Approval of the Chairman of the Master’s Thesis Committee and Dean of Faculty of Computer Science and Engineering after the thesis being corrected (If any). CHAIRMAN OF THESIS COMMITTEE DEAN OF FACULTY OF COMPUTER SCIENCE AND ENGINEERING i VIETNAM NATIONAL UNIVERSITY - HO CHI MINH CITY SOCIALIST REPUBLIC OF VIETNAM HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY Independence – Freedom - Happiness THE TASK SHEET OF MASTER’S THESIS Full name: Vo Thi Kim Nguyet Student code: 2270346 Date of birth: Oct 10th 1995 Place of birth: Ho Chi Minh City Major: Computer Science Major code: 8480101 I.

THESIS TITLE: E-commerce graph-based recommendation system (Hệ thống gợi ý dựa trên phương pháp đồ thị trong thương mại điện tử) II. TASKS AND CONTENTS: 1. Introduction: • Introduce the research topic and its significance. • Provide an overview of the structure of the thesis.

Literature Review: • Conduct a comprehensive review of existing product recommendation techniques. • Analyze strengths and weaknesses of different approaches. • Identify gaps in the literature that the research aims to address. Problem Statement: • Clearly state the problem being addressed in the research.

• Highlight the need for improved recommendation approaches in the context of e-commerce. Methodology: • Design the research approach for developing and evaluating the recommendation system. • Define the criteria and metrics for evaluating the effectiveness of the system. Graph-Based Recommendation System Implementation: • Develop the recommendation system using graph embedding techniques.

• Implement graph construction methods based on user behavior data. • Incorporate Node2Vec and FAISS for graph embedding and indexing. Experimental Evaluation: • Conduct experiments to evaluate the performance of the developed system. • Compare the results with other existing recommendation models.

• Collect and analyze data on key evaluation metrics. Discussion of Findings: • Analyze and interpret the results of the experimental evaluation. • Discuss the implications of the findings in relation to the research objectives. Conclusion: • Summarize the key findings and contributions of the research.

• Discuss the practical implications of the research outcomes. Future Research Directions: • Suggest avenues for further research and improvements in the recommendation system. • Highlight areas where the proposed approach could be extended or refined. References: • List all the sources and references cited throughout the thesis.

Appendices: • Include any supplementary material, code snippets, graphs, or diagrams that enhance understanding. THESIS START DAY: Feb-06-2023 IV. THESIS COMPLETION DAY: Jun-09-2023 V. SUPERVISOR: Le Thanh Van, Ph.D Ho Chi Minh City, Jun-09-2023 SUPERVISOR CHAIR OF PROGRAM COMMITTEE (Full name and signature) (Full name and signature) DEAN OF FACULTY OF COMPUTER SCIENCE AND ENGINEERING (Full name and signature) Note: Student must pin this task sheet as the first page of the Master’s Thesis booklet iii ACKNOWLEDGEMENT This thesis marks the culmination of my research journey into graph-based modeling and its applications in data analysis and machine learning.

Graphs offer a unique perspective to understand complex relationships within vast datasets. Throughout this work, I explore fundamental concepts of graph-based modeling, delve into graph embedding techniques, and evaluate their efficacy in solving real- world problems. I extend my gratitude to my advisors, mentors, colleagues, and family for their unwavering support and encouragement. My hope is that this thesis inspires further research and innovative applications of graph-based models in various domains.

Thank you for joining me on this journey. Sincerely, Nguyet Vo Ho Chi Minh City, June 2023 iv ABSTRACT This thesis presents a graph-based recommendation system tailored for personalized content suggestions in ecommerce. Utilizing graph embedding methods such as DeepWalk and Node2Vec as part of Random Walks technique, the system captures users’ behavioural sequences and generates embeddings for items. These embeddings facilitate pairwise similarity calculations among items, forming the basis for content recommendations rooted in similarity metrics.

To tackle challenges like sparsity and cold start, additional information is seamlessly integrated into the graph embedding framework. Empirical evaluation using clickstream data demonstrates the superiority of the proposed approach over traditional collaborative filtering techniques in terms of both accuracy and efficiency. The study contributes a novel graph-based recommendation system addressing scalability, sparsity, and cold start issues, further enriched by the incorporation of supplementary data to enhance recommendation system efficacy. The results suggest that graph-based techniques hold potential for enhancing personalized recommendation systems across diverse domains, including ecommerce.

v TÓM TẮT LUẬN VĂN THẠC SĨ Luận văn đề xuất một hệ thống gợi ý dựa trên đồ thị cho việc cá nhân hóa gợi ý nội dung trong thương mại điện tử. Dự án sử dụng các kỹ thuật đồ thị như DeepWalk và Node2Vec của kỹ thuật Random Walks để nắm bắt chuỗi hành vi của người dùng và đề xuất các danh sách sản phẩm phù hợp. Những kỹ thuật này giúp tính toán độ xác suất giữa các cặp/ danh sách sản phẩm, từ đó tạo nền tảng cho gợi ý cho người dùng dựa trên hành vi của họ. Để giải quyết các thách thức như người dùng/ sản phẩm mới và khả năng mở rộng hoặc sự thưa thớt, thuật toán sẽ được bổ sung và tích hợp hệ thống nhằm đưa ra những gợi ý thông minh, phù hợp với sở thích của từng khách hàng.

Đánh giá thực nghiệm bằng dữ liệu lớn của hành vi khách hàng cho thấy phương pháp đề xuất vượt trội so với các phương pháp lọc cộng tác truyền thống về cả độ chính xác và hiệu suất. Nghiên cứu đóng góp một hệ thống gợi ý dựa trên đồ thị nhằm giúp khách hàng nhanh chóng định vị được những sản phẩm họ quan tâm để từ đó đưa ra quyết định đúng đắn khi mua sắm online cũng như khả năng cải thiện hiệu suất của hệ thống gợi ý cá nhân hoá. vi DECLARATION OF AUTHORSHIP I hereby declare that this thesis was carried out by myself under the guidance and supervision of Le Thanh Van, Ph.D; and that the work contained and the results in it are true by author and have not violated research ethics. The data and figures presented in this thesis are for analysis, comments, and evaluations from various resources by my own work and have been duly acknowledged in the reference part.

In addition, other comments, reviews and data used by other authors, and organizations have been acknowledged, and explicitly cited. I will take full responsibility for any fraud detected in my thesis. Ho Chi Minh City University of Technology (HCMUT) – VNU-HCM is unrelated to any copyright infringement caused on my work (if any). Ho Chi Minh City, June 2023 Author Vo Thi Kim Nguyet vii TABLE OF CONTENTS LIST OF FIGURES.

ix LIST OF TABLES. xi CHAPTER 1: INTRODUCTION. Background on recommendation systems and the importance of personalization. Scope of the research.

Novelty of the topic. 7 CHAPTER 2: OVERVIEW OF RECOMMENDATION SYSTEM. Recommendation System methods. Overview of existing literature on graph-based recommendation systems 16 2.

Graph-based learning Approaches for Recommender System (RS). Research results in application of Graph-based learning in Recommender System. Comparison of different graph-based algorithms. The advantages of using UMAP and FAISS in combination with Deep Walk and Node2Vec.

Session-based Recommendation System. Data collection and its characteristics. Data cleaning and preparation. Explanation of how the data was transformed into a graph-based representation.

Random Walks algorithm. Visualization with UMAP. Embedding Vector Search with FAISS. Evaluation of the Recommendation System.

67 CHAPTER 4: EXPERIMENTAL RESULTS. All Machine Learning (ML) Models. Traditional Recommendation Techniques. Sequence Models for Session-Level Data .86 CHAPTER 5: DISCUSSION AND CONCLUSION.102 ix LIST OF FIGURES Figure 1.

Example of PDP views in a session. Taxonomy of Recommendation System. The demonstration of graph learning based recommender systems. BFS and DFS search strategies from node 𝑢(𝑘 = 3).

Illustration of the random walk procedure in node2vec. The walk just transitioned from 𝑡 to 𝑣 and is now evaluating its next step out of node 𝑣. Edge labels indicate search biases 𝛼. Overview of graph embedding in Taobao: (a) Users’ behavior sequences: One session for user 𝑢1, two sessions for user 𝑢2 and 𝑢3; these sequences are used to construct the item graph; (b) The weighted directed item graph 𝒢 = (𝒱, ℰ); (c) The sequences generated by random walk in the item graph; (d) Embedding with Skip-Gram.

Attributes of raw dataset. Daily Visits summary. Flow of a user in a session. Example for view of all products of a user in a session.

Directed Graph with Weight. Undirected Graph with Weight. Middle and Remaining proportion. Final results of embedding vectors.

Node2Vec Embeddings Visualization. New dataset is generated from embedding vectors. Category-code in level 1 visualization. Cosine Similarity and L2 scores.

An imbalance in user interactions. List of results for a specific user. Correlation among categories. Each chunk in Association Rules algorithm.

Result in Association Rule algorithm. Traditional Recomendation System Models Results. Model and Result in NARM model. Co-occurrence matrix of items based on adjacency of items in same session.

Item & User Similarity matrix. Heterogenous Global Graph. Model Training and Evaluation. Results in HG-GNN model.92 xi LIST OF TABLES Table 2.

Comparison of different graph-based algorithms. Top-N Metrics Result. Comparison among dimensional reduction techniques. Comparisons among ML models and Graph-based approach.

Comparisons among traditional and graph-based models. Comparison among metrics in HG-GNN model. Comparison between Sequence Models and Graph-based model .94 1 CHAPTER 1: INTRODUCTION This chapter aims to enhance personalized recommendation systems in ecommerce by exploring advanced algorithms and conducting A/B testing for real- world insights. Using a large-scale dataset, we propose a state-of-the-art algorithm to improve accuracy and efficiency.

Our goal is to bridge theory and practice, revolutionizing recommender systems and maximizing user satisfaction in ecommerce. Leveraging a large-scale dataset from REES46 [1], we aim to revolutionize recommender systems, maximizing user satisfaction and platform diversity. Background on recommendation systems and the importance of personalization This thesis focuses on recommender systems in ecommerce, where personalized content recommendation is crucial due to the vast number of products available on numerous websites. Traditional recommender systems like Content-Based Filtering and Collaborative Filtering encounter issues with scalability, sparsity, and cold start problems, reducing their effectiveness in handling large-scale and sparse transaction records.

To address these challenges, the project proposes the use of graph embedding techniques, specifically Random Walks, to capture users’ behavioral sequences and generate item embeddings. These embeddings can then be utilized to recommend products to users, group similar products, and classify transactions based on meta-information about clusters, items, and users’ transaction use cases. The approach also employs Facebook AI Similarity Search (FAISS) for generating recommendations through embedding vector search. By leveraging graph-based learning, this thesis offers insights into enhancing recommender systems in ecommerce platforms while tackling the limitations faced by traditional methods.

Research Questions This thesis aims to address the effectiveness of graph-based techniques, namely Random Walks, and FAISS, in capturing users’ behaviour sequences and 2 generating item embeddings for improved product recommendations in ecommerce, compared to traditional methods. To investigate these research questions thoroughly, the following methodology will be employed: a.