Social trust prediction addresses the significant problem of exploring interactions among users in social networks. Naturally, this problem can be formulated in the matrix completion framework, with each entry indicating the trustness or distrustness. However, there are two challenges for the social trust problem: 1) the observed data are with sign (1-bit) measurements; 2) they are typically sampled non-uniformly. Most of the previous matrix completion methods do not well handle the two issues. Motivated by the recent progress of max-norm, we propose to solve the problem with a 1-bit max-norm constrained formulation. Since max-norm is not easy to optimize, we utilize a reformulation of max-norm which facilitates an efficient projected gradient decent algorithm. We demonstrate the superiority of our formulation on two benchmark datasets.
@cite_18: 
@cite_22: The max-norm was proposed as a convex matrix regularizer in [1] and was shown to be empirically superior to the trace-norm for collaborative filtering problems. Although the max-norm can be computed in polynomial time, there are currently no practical algorithms for solving large-scale optimization problems that incorporate the max-norm. The present work uses a factorization technique of Burer and Monteiro [2] to devise scalable first-order algorithms for convex programs involving the max-norm. These algorithms are applied to solve huge collaborative filtering, graph cut, and clustering problems. Empirically, the new methods outperform mature techniques from all three areas.
@cite_8: We consider in this paper the problem of noisy 1-bit matrix completion under a general non-uniform sampling distribution using the max-norm as a convex relaxation for the rank. A max-norm constrained maximum likelihood estimate is introduced and studied. The rate of convergence for the estimate is obtained. Information-theoretical methods are used to establish a minimax lower bound under the general sampling model. The minimax upper and lower bounds together yield the optimal rate of convergence for the Frobenius norm loss. Computational algorithms and numerical performance are also discussed.
@cite_31: We show that matrix completion with trace-norm regularization can be significantly hurt when entries of the matrix are sampled non-uniformly, but that a properly weighted version of the trace-norm regularizer works well with non-uniform sampling. We show that the weighted trace-norm regularization indeed yields significant gains on the highly non-uniformly sampled Netflix dataset.
@cite_20: We study the rank, trace-norm and max-norm as complexity measures of matrices, focusing on the problem of fitting a matrix with matrices having low complexity. We present generalization error bounds for predicting unobserved entries that are based on these measures. We also consider the possible relations between these measures. We show gaps between them, and bounds on the extent of such gaps.
@cite_12: 
However, all the methods mentioned above use the nuclear norm as the surrogate to the rank, whose exact recovery can be guaranteed only when the data are sampled uniformly, which is not practical in real world applications. On the other hand, recent empirical on max-norm @cite_18 shows promising results for non-uniform data if one utilize the max-norm as a surrogate @cite_31 . Notably, for some specific problems, such as collaborative filtering, @cite_20 proved that the generalization error bound for max-norm is better than the nuclear norm. More recently, @cite_12 reported encouraging results on the subspace recovery task (which is closely relevant to matrix completion). Since the social trust data is non-uniformly sampled, we believe that a max-norm regularized formulation can better handle the challenge than the nuclear norm. Our formulation is also inspired by a recent theoretical study on matrix completion with 1-bit measurement @cite_8 , which established a minimax lower bound on the general sampling model and derived the optimal convergence rate in terms of Frobenius norm loss. Furthermore, there are several practical algorithms to solve max-norm regularized or max-norm constrained problems, see @cite_22 and @cite_12 for example.