Summarizing user-item matrix by group utility maximization

• 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: Engineering::Computer science and engineering; Data Summarization; Greedy Algorithm
• Online Access: https://hdl.handle.net/10356/166437
• Institution: Nanyang Technological University

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.