MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs

2020-06-08 · Qiaosheng Zhang, Geewon Suh, Changho Suh, Vincent Y. F. Tan

In this paper, we design and analyze MC2G (Matrix Completion with 2 Graphs), an algorithm that performs matrix completion in the presence of social and item similarity graphs. MC2G runs in quasilinear time and is parameter free. It is based on spectral clustering and local refinement steps. The expected number of sampled entries required for MC2G to succeed (i.e., recover the clusters in the graphs and complete the matrix) matches an information-theoretic lower bound up to a constant factor for a wide range of parameters. We show via extensive experiments on both synthetic and real datasets that MC2G outperforms other state-of-the-art matrix completion algorithms that leverage graph side information.

📄 PDF Abstract BibTeX arXiv:2006.04373

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringMatrix CompletionRecommendation Systems

Methods 이 논문이 사용한 방법론

Spectral Clustering Spectral clustering has attracted increasing attention due to the promising ability in dealing with nonlinearly separable datasets [15], [16]. In spectral clustering, the…

Community Detection and Matrix Completion with Social and Item Similarity Graphs

2019-12-06 · Qiaosheng Zhang, Vincent Y. F. Tan, Changho Suh

We consider the problem of recovering a binary rating matrix as well as clusters of users and items based on a partially observed matrix together with side-information in the form of social and item similarity graphs. Th…

Community Detection Matrix Completion Stochastic Block Model

Matrix Completion with Hierarchical Graph Side Information

2022-01-02 · NeurIPS 2020 12 · Adel Elmahdy, Junhyung Ahn, Changho Suh, Soheil Mohajer

We consider a matrix completion problem that exploits social or item similarity graphs as side information. We develop a universal, parameter-free, and computationally efficient algorithm that starts with hierarchical gr…

Clustering Graph Clustering Matrix Completion Stochastic Block Model

On the Fundamental Limits of Matrix Completion: Leveraging Hierarchical Similarity Graphs

2021-09-12 · Junhyung Ahn, Adel Elmahdy, Soheil Mohajer, Changho Suh

We study the matrix completion problem that leverages hierarchical similarity graphs as side information in the context of recommender systems. Under a hierarchical stochastic block model that well respects practically-r…

Matrix Completion Recommendation Systems Stochastic Block Model

A Soft Recommender System for Social Networks

2020-01-08 · Marzieh Pourhojjati-Sabet, Azam Rabiee

Recent social recommender systems benefit from friendship graph to make an accurate recommendation, believing that friends in a social network have exactly the same interests and preferences. Some studies have benefited …

Clustering Recommendation Systems TAG

Cluster Developing 1-Bit Matrix Completion

2019-04-07 · Chengkun Zhang. Junbin Gao, Stephen Lu

Matrix completion has a long-time history of usage as the core technique of recommender systems. In particular, 1-bit matrix completion, which considers the prediction as a ``Recommended'' or ``Not Recommended'' question…

Clustering Matrix Completion Recommendation Systems