Appendices ALow-Rank Matrix Factorization with Non-Uniform Sampling

In this section, we demonstrate the effectiveness of low-rank matrix factorization in recovering the label relationship matrix. We first present four important facts: f1: the rank of the matrix is equivalent to the number of classes. Specifically, this also means that if ˆZi,k = 1, then ˆZj,k = 1. We consider a toy example (without self-loops), ˆZ = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A = 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 (14) In a standard LRMF problem, it is not possible to recover ˆZ from A since no entries are observed for the third and fourth rows. However, we can demonstrate how LRMF effectively performs in this situation. Recovery: We begin by assuming v1 is in class 1, resulting in U1,: = [1, 1, 1] and V1,: = [1,0,0]. By observing A1,4, we know that v4 is also in class 1, resulting in U4,: = [1, 1, 1]and V4,: = [1,0,0](f2). By analyzing A1,2 and A1,3, we determine that v2 and v3 do not belong to class 1.