Hypergraph structure and truncation method that reduces computer processor execution time in predicting product returns based on large scale data

Patent metadata

Field	Value
Publication number	US-11164229-B2
Application number	US-201816194970-A
Country	US
Kind code	B2
Filing date	Nov 19, 2018
Priority date	Nov 19, 2018
Publication date	Nov 2, 2021
Grant date	Nov 2, 2021

Abstract

A hypergraph is constructed based on historical shopping cart data. A node of the hypergraph corresponds to a shopping basket, and a hyperedge of the hypergraph corresponds to a unique product, the hyperedge connecting all nodes of the hypergraph representing baskets containing the unique product. A hypergraph partition algorithm identifies a cluster of shopping baskets represented in the hypergraph and determined to be similar to a given basket. Based on the cluster of shopping baskets a dual-level return prediction is performed. The dual-level return prediction includes predicting whether the given basket will be returned, and based on predicting that the given basket will be returned, predicting a probability that a product in the given basket will be returned. Based on predicting that the given basket will be returned, an ameliorative action is performed to reduce the probability.

First claim

What is claimed is:

1. A computer-implemented method comprising:
constructing a hypergraph data structure in computer memory based on historical shopping cart data, a node of the hypergraph data structure corresponding to a shopping basket, and a hyperedge of the hypergraph data structure corresponding to a unique product, the hyperedge connecting all nodes of the hypergraph data structure representing baskets containing the unique product, the hypergraph data structure representing historical purchase and return records;
executing a hypergraph partition algorithm, the hypergraph partition algorithm identifying a cluster of shopping baskets represented in the hypergraph data structure and determined to be similar to a given basket, the given basket being an online shopping basket;
based on the cluster of shopping baskets identified by the hypergraph partition algorithm, performing a dual-level return prediction, the dual-level return prediction comprising predicting whether the given basket will be returned, and based on predicting that the given basket will be returned, predicting a probability that a product in the given basket will be returned; and
based on predicting that the given basket will be returned, performing an ameliorative action to reduce the probability,
the ameliorative action including at least initiating a chatbot to interact with a user in real time, the chatbot interacting with the user and providing guidance regarding the product placed in the online shopping basket.

2. The method of claim 1 , wherein the dual-level return prediction is performed before a purchase associated with the given basket is made.

3. The method of claim 1 , wherein the ameliorative action comprises providing a discount coupon on the product.

4. The method of claim 1 , wherein the ameliorative action comprises providing a return affinity aware search result responsive to a user associated with the given basket performing a product search.

5. The method of claim 1 , wherein the hypergraph partition algorithm comprises a local graph cut algorithm using truncated random walk on the hypergraph data structure, the truncated random walk starting from an input seed node and exploring a neighborhood of the seed node on the hypergraph data structure.

6. The method of claim 1 , wherein the guidance regarding the product includes guidance with respect to at least one of the product's style, the product's shade, the product's size and the product's fit.

7. A computer readable storage medium storing a program of instructions executable by a machine to perform a method comprising:
constructing a hypergraph data structure in computer memory based on historical shopping cart data, a node of the hypergraph data structure corresponding to a shopping basket, and a hyperedge of the hypergraph data structure corresponding to a unique product, the hyperedge connecting all nodes of the hypergraph data structure representing baskets containing the unique product, the hypergraph data structure representing historical purchase and return records;
executing a hypergraph partition algorithm, the hypergraph partition algorithm identifying a cluster of shopping baskets represented in the hypergraph data structure and determined to be similar to a given basket, the given basket being an online shopping basket;
based on the cluster of shopping baskets identified by the hypergraph partition algorithm, performing a dual-level return prediction, the dual-level return prediction comprising predicting whether the given basket will be returned, and based on predicting that the given basket will be returned, predicting a probability that a product in the given basket will be returned; and
based on predicting that the given basket will be returned, performing an ameliorative action to reduce the probability,
the ameliorative action including at least initiating a chatbot to interact with a user in real time, the chatbot interacting with the user and providing guidance regarding the product placed in the online shopping basket.

8. The computer readable storage medium of claim 7 , wherein the dual-level return prediction is performed before a purchase associated with the given basket is made.

9. The computer readable storage medium of claim 7 , wherein the ameliorative action comprises providing a discount coupon on the product.

10. The computer readable storage medium of claim 7 , wherein the ameliorative action comprises providing a return affinity aware search result responsive to a user associated with the given basket performing a product search.

11. The computer readable storage medium of claim 7 , wherein the hypergraph partition algorithm comprises a local graph cut algorithm using truncated random walk on the hypergraph data structure, the truncated random walk starting from an input seed node and exploring a neighborhood of the seed node on the hypergraph data structure.

12. A system comprising:
at least one hardware processor;
a memory device coupled with the at least one hardware processor, the at least one hardware processor operable to:
construct a hypergraph data structure in the memory device based on historical shopping cart data, a node of the hypergraph data structure corresponding to a shopping basket, and a hyperedge of the hypergraph data structure corresponding to a unique product, the hyperedge connecting all nodes of the hypergraph data structure representing baskets containing the unique product, the hypergraph data structure representing historical purchase and return records;
execute a hypergraph partition algorithm, the hypergraph partition algorithm identifying a cluster of shopping baskets represented in the hypergraph data structure and determined to be similar to a given basket, the given basket being an online shopping basket;
based on the cluster of shopping baskets identified by the hypergraph partition algorithm, perform a dual-level return prediction, the dual-level return prediction comprising predicting whether the given basket will be returned, and based on predicting that the given basket will be returned, predicting a probability that a product in the given basket will be returned; and

based on predicting that the given basket will be returned, perform an ameliorative action to reduce the probability,
the ameliorative action including at least initiating a chatbot to interact with a user in real time, the chatbot interacting with the user and providing guidance regarding the product placed in the online shopping basket.

13. The system of claim 12 , wherein the dual-level return prediction is performed before a purchase associated with the given basket is made.

14. The system of claim 12 , wherein the ameliorative action comprises providing a discount coupon on the product.

15. The system of claim 12 , wherein the ameliorative action comprises providing a return affinity aware search result responsive to a user associated with the given basket performing a product search.

16. The system of claim 12 , wherein the hypergraph partition algorithm comprises a local graph cut algorithm using truncated random walk on the hypergraph data structure, the truncated random walk starting from an input seed node and exploring a neighborhood of the seed node on the hypergraph data structure.

Assignees

• IBM

Inventors

• Zhu Yada
• Deshpande Ajay Ashok
• Park Jae-Eun
• Topol Anna Wanda
• Liu Xuan

Classifications

• G06Q30/0202 Primary

  Market predictions or forecasting for commercial activities · CPC title

• G06Q30/0222

  During e-commerce, i.e. online transactions · CPC title

• G06Q30/0617 Primary

  Representative agent · CPC title