Summarizing user-item matrix by group utility maximization

A user-item utility matrix represents the utility (or preference) associated with each (user, item) pair, such as citation counts, rating/vote on items or locations, and clicks on items. A high utility value indicates a strong association of the pair. In this work, we consider the problem of summari...

Full description

Saved in:
Bibliographic Details
Main Authors: Wang, Yongjie, Wang, Ke, Long, Cheng, Miao, Chunyan
Other Authors: School of Computer Science and Engineering
Format: Article
Language:English
Published: 2023
Subjects:
Online Access:https://hdl.handle.net/10356/166437
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary:A user-item utility matrix represents the utility (or preference) associated with each (user, item) pair, such as citation counts, rating/vote on items or locations, and clicks on items. A high utility value indicates a strong association of the pair. In this work, we consider the problem of summarizing strong association for a large user-item matrix using a small summary size. Traditional techniques fail to distinguish user groups associated with different items (such as top-$l$ item selection) or fail to focus on high utility (such as similarity based subspace clustering and biclustering). We formulate a new problem, called Group Utility Maximization, to summarize the entire user population through $k$ user groups and $l$ items for each group; the goal is to maximize the total utility of selected items over all groups collectively. We show this problem is NP-hard even for $l=1$. We present two algorithms. One greedily finds the next group, called Greedy algorithm, and the other iteratively refines existing $k$ groups, called $k$-max algorithm. Greedy algorithm provides the $(1-\frac{1}{e})$ approximation guarantee for a nonnegative utility matrix, whereas $k$-max algorithm is more efficient for large datasets. We evaluate these algorithms on real-life datasets.