We study a matrix completion problem which leverages a hierarchical structure of social similarity graphs as side information in the context of recommender systems. We assume that users are categorized into clusters, each of which comprises sub-clusters (or what we call “groups”). We consider a hierarchical stochastic block model that well respects practically-relevant social graphs and follows a low-rank rating matrix model. Under this setting, we characterize the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) as a function of the quality of graph side information (to be detailed) by proving sharp upper and lower bounds on the sample complexity. One important consequence of this result is that leveraging the hierarchical structure of similarity graphs yields a substantial gain in sample complexity relative to the one that simply identifies different groups without resorting to the relational structure across them. Another implication of the result is when the graph information is rich, the optimal sample complexity is proportional to the number of clusters, while it nearly stays constant as the number of groups in a cluster increases. We empirically demonstrate through extensive experiments that the proposed algorithm achieves the optimal sample complexity.

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. For the matrix completion problem which possesses additional block structures in its rows and columns, we derive the expected number of sampled entries required for MC2G to succeed, and further show that it matches an information-theoretic lower bound up to a constant factor for a wide range of parameters. We perform extensive experiments on both synthetic datasets and a semi-real dataset inspired by real graphs. The experimental results show that MC2G outperforms other state-of-the-art matrix completion algorithms.

We study a matrix completion problem which leverages a hierarchical structure of social similarity graphs as side information in the context of recommender systems. We assume that users are categorized into clusters, each of which comprises sub-clusters (or what we call “groups”). We consider a hierarchical stochastic block model that well respects practically-relevant social graphs and follows a low-rank rating matrix model. Under this setting, we characterize the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) as a function of the quality of graph side information (to be detailed) by proving sharp upper and lower bounds on the sample complexity. One important consequence of this result is that leveraging the hierarchical structure of similarity graphs yields a substantial gain in sample complexity relative to the one that simply identifies different groups without resorting to the relational structure across them. Another implication of the result is when the graph information is rich, the optimal sample complexity is proportional to the number of clusters, while it nearly stays constant as the number of groups in a cluster increases. We empirically demonstrate through extensive experiments that the proposed algorithm achieves the optimal sample complexity.

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. For the matrix completion problem which possesses additional block structures in its rows and columns, we derive the expected number of sampled entries required for MC2G to succeed, and further show that it matches an information-theoretic lower bound up to a constant factor for a wide range of parameters. We perform extensive experiments on both synthetic datasets and a semi-real dataset inspired by real graphs. The experimental results show that MC2G outperforms other state-of-the-art matrix completion algorithms.

Welcome to the ninth (June 2022) issue of the IEEE Journal on Selected Areas in Information Theory (JSAIT), dedicated to “Distributed Coding and Computation”.

In future complex and diverse battlefield situations, the existing command system faces the challenge of delayed human judgement of strategy and low objectivity. This paper proposes an artificial intelligence model that takes situation information and course of action simulation results as input and automatically assigns scores to various evaluation elements and a comprehensive score. This tool is expected to assist the commander in making decisions, reduce the time required for making judgments, and promote impartial decision-making.

We explore a fairness-related challenge that arises in generative models. The challenge is that biased training data with imbalanced demographics may yield a high asymmetry in size of generated samples across distinct groups. We focus on practically-relevant scenarios wherein demographic labels are not available and therefore the design of a fair generative model is non-straightforward. In this paper, we propose an optimization framework that regulates the unfairness under such practical settings via one statistical measure, LeCam (LC)-divergence. Specifically to quantify the degree of unfairness, we employ a balanced-yet-small reference dataset and then measure its distance with generated samples using the LC-divergence, which is shown to be particularly instrumental to a small size of the reference dataset. We take a variational optimization approach to implement the LC-based measure. Experiments on benchmark real datasets demonstrate that the proposed framework can significantly improve the fairness performance while maintaining realistic sample quality for a wide range of the reference set size all the way down to 1% relative to training set.

본 연구에서는 사용자 유사도 그래프를 동시에 부가 정보로 활용할 수 있는 추천 시스템에서, 적은 양의 관측정보에도 잘 작동하는 행렬 채움(Matrix Completion) 알고리즘을 제안한다. 제안하는 알고리즘은 클러스터링 단계에서 평점행렬, 소셜그래프 정보 중 하나를 적절하게 선택하는 메커니즘을 기반으로 한다. 제안한 알고리즘이 하나의 유사도 그래프를 사용하는 기존의 알고리즘 대비 높은 성능을 보임을 실제 데이터를 사용한 실험을 통해 검증한다.