Year: 2019

Abstract:
We address the problem of reconstructing a matrix from a subset of its entries. Current methods, branded as geometric matrix completion, augment classical rank regularization techniques by incorporating geometric information into the solution. This information is usually provided as graphs encoding relations between rows/columns. In this work we propose a simple spectral approach for solving the matrix completion problem, via the framework of functional maps. We introduce the zoomout loss, a multiresolution spectral geometric loss inspired by recent advances in shape correspondence, whose minimization leads to state-of-the-art results on various recommender systems datasets. Surprisingly, for some datasets we were able to achieve comparable results even without incorporating geometric information. This puts into question both the quality of such information and current methods’ ability to use it in a meaningful and efficient way.

heading: 1 INTRODUCTION
text: Matrix completion deals with the recovery of missing values of a matrix from a subset of its entries,
Find X s.t. X S = M S. (1)
HereX stands for the unknown matrix,M ∈ Rm×n for the ground truth matrix, S is a binary mask representing the input support, and denotes the Hadamard product. Since problem (1) is ill-posed, it is common to assume thatM belongs to some low dimensional subspace. Under this assumption, the matrix completion problem can be cast via the least-squares variant,
min X
rank (X) + µ
2 ‖(X −M) S‖2F . (2)
Relaxing the intractable rank penalty to its convex envelope, namely the nuclear norm, leads to a convex problem whose solution coincides with (2) under some technical conditions (Candès & Recht, 2009). Another way to enforce low rank is by explicitly parametrizingX in factorized form, X = Y Z>. The rank is upper-bounded by the inner dimensions of Y ,Z>. Recent studies by Arora et al. (2019); Gunasekar et al. (2017), suggest that overparametrizing X as a product of several matrices results in a low rank matrix due to an implicit regularization induced by the gradient descent trajectories. According to (Gunasekar et al., 2017; Arora et al., 2019), given enough entries and independent of the depth, overparametrized deep matrix factorization (DMF) models are equivalent1 to nuclear norm minimization. However, in the data poor regime these methods differ, and an implicit regularization brought forward by the dynamics of the gradient descent algorithm provides a stronger rank regularization. The deeper the network - the stronger the regularization.
Optimization approaches as described above can be thought of as instances of self-supervised learning, an informal name given to a machine learning paradigm with the goal of "predicting any part of the input from any other part" (LeCun, 2019). Adopting the machine learning nomenclature, we shall henceforth refer to the given entries ofM as training set or training samples, and denote by test set a subset of the (unknown) entries ofM which we shall use for evaluation.
The advent of deep learning platforms equipped with efficient automatic differentiation tools allows the exploration of more sophisticated models that incorporate intricate regularizations, both explicit
1Under some technical conditions. See (Arora et al., 2019).
and implicit. Some contemporary approaches for matrix completion fall under the umbrella of geometric deep learning. These approaches generalize standard (Euclidean) deep learning to domains such as general graphs and manifolds. For example, graph convolutional neural networks (GCNNs) follow the architecture of standard CNNs, but replace the Euclidean convolution operator with linear filters constructed using the graph Laplacian. We distinguish between graph based approaches which make use of the bi-partite graph structure of the rating matrix (e.g., Berg et al. (2017)), and geometric matrix completion techniques which make use of side information in the form of graphs encoding relations between rows/columns (Kalofolias et al., 2014; Monti et al., 2017). While these techniques achieve state-of-the-art results, their design is arguably cumbersome and non-intuitive. It has recently been demonstrated that some graph CNN architectures can be greatly simplified, and still perform competitively on several graph analysis tasks (Wu et al., 2019). Such simple techniques have the advantage of being easier to analyze and reproduce. Motivated by these results, our intent is to construct a simple architecture for matrix completion that follows from geometric considerations rather than ad-hoc ones.
The inspiration for our paper stems from techniques for finding shape correspondence. In particular, the functional maps framework and its variants (Ovsjanikov et al., 2012; 2016). Most notably the work of (Litany et al., 2017) who combined functional maps with joint diagonalization to solve partial shape matching problems, and the product manifold filter (PMF) (Vestner et al., 2017b;a) and zoomout (Melzi et al., 2019) – two greedy algorithms for correspondence refinement by gradual introduction of high frequencies. This last method lent its name to the loss we define in Section 3. To that end, we propose a simple spectral method for geometric matrix completion that combines the fully linear network structure of DMF with the geometric framework of functional maps.
Contribution. Our contributions are as follows:
• We propose a geometric interpretation for deep matrix factorization (Arora et al., 2019) by embedding it as part of the functional maps framework. • We introduce the zoomout loss, a multiresolution spectral geometric loss inspired by recent
advances in shape correspondence. • We show that via a simple shallow and fully linear network, it is possible to obtain state-of-
the-art results on various recommendation systems datasets. • We demonstrate that in some cases the effect of the geometry is only marginal, and results
on par with state-of-the-art can be achieved even without it.

heading: 2 BACKGROUND
text: Spectral graph theory. Let G = (V,E,Ω) be a (weighted) graph specified by its vertex set V and edge set E, and let Ω be its adjacency matrix. Given a function x ∈ R|V | on the vertices, we define the following quadratic form (also known as Dirichlet energy) measuring the variability of the function x on the graph,
x>Lx = ∑
(a,b)∈E
ωa,b (x(a)− x(b))2 . (3)
The matrix L is called the (combinatorial) graph Laplacian, and is given by L = D −Ω, where D = diag(Ω1) is the degree matrix. L is symmetric and positive semi-definite and therefore admits a spectral decomposition L = ΦΛΦ>. The graph Laplacian is a discrete generalization of the continuous Laplace-Beltrami operator, and therefore has similar properties. One can think of the eigenpairs (φi, λi) as the graph analogues of "harmonic" and "frequency". A function x = ∑|V | i=1 αiφi on the vertices of the graph whose coefficients αi are small for large i, demonstrates a "smooth" behaviour on the graph in the sense that the function values on nearby nodes will be similar. A standard approach to promoting such smooth functions on graphs is by using the Dirichlet energy (3) to regularize some loss term. For example, this approach gives rise to the popular bilateral and non-local means filters (Gadde et al., 2013).
Functional maps. Let G1 = (V1, E1,Ω1), G2 = (V2, E2,Ω2) be two graphs, and let Φ,Ψ, be two orthonormal bases for functions defined on the vertices of these graphs. Given two such functions,
x = Φα on G1 and y = Ψβ on G2, one can define a map C between their representations α and β, i.e., α = Φ>x = CΨ>y = Cβ. The matrix C represents a linear map between the functional spaces on G1 and G2, known as a functional map. Let us denote the Cartesian product of G1 and G2 by G1 G2. G1 G2 is a graph with vertex set V1 × V2, on which two nodes (u, u′), (v, v′) are adjacent if either u = v and (u′, v′) ∈ E2 or u′ = v′ and (u, v) ∈ E1. LetX be a function defined on G1 G2, then the functional map is given by projecting X onto the corresponding bases Φ,Ψ, C = Φ>XΨ. Using the SVD, one can decompose X = UΣV > to interpret C as a mapping between UΣ, a function on one graph, and V , a function on the other. To get X back from the functional map, one can useX = ΦCΨ>. For computational reasons, it is common to use truncated bases Φ,Ψ, in which case the last equality holds only approximately.
The structure of the functional map depends on the properties of the chosen bases and the functions it maps. A common choice for a basis is the aforementioned Laplacian eigenbasis, building on the assumption that the signals involved are smooth with respect to the graphs. While this is a useful model, it assumes that the given graphs encode the geometry in an adequate way. In real world problems these graphs are only approximate, constructed from heuristic features associated with the row and the column spaces. Given better graphs, a simpler structure of the functional map emerges. For example, by introducing two orthonormal matrices P andQ, one can make the functional map C = (ΦP ) > X (ΨQ) diagonal. These orthonormal matrices can be thought of as a way of aligning the bases Φ,Ψ, with the principal axes ofX .

heading: 3 SPECTRAL GEOMETRIC MATRIX COMPLETION
text: We assume that we are given a set of samples from the unknown matrix M ∈ Rm×n, encoded by a binary mask S, and two graphs Gr, Gc, encoding relations between the rows and the columns, respectively. Denote the Laplacians of these graphs and their spectral decompositions by Lr = ΦΛrΦ >, Lc = ΨΛcΨ>. Our approach relies on a minimization problem of the form
min X
Ez(X) + µrtrace ( X>LrX ) + µctrace ( XLcX >) , (4) with Ez denoting the data term that we discuss in the sequel. The other two terms in (4) are the Dirichlet energies of X computed on Gr, Gc, as defined in (3). These energies measure the variability of X along neighbouring nodes on these graphs. Using X = ΦCΨ> and the spectral decompositions of Lr,Lc, we can equivalently write them in terms of C,
trace ( X>LrX ) = trace ( ΨC>Φ>LrΦCΨ >) = trace (C>ΛrC) , trace ( XLcX
>) = trace (ΦCΨ>LcΨC>Φ>) = trace (CΛcC>) . (5) As mentioned above, the input graphs are typically constructed from a set of heuristically gathered features which may provide a poor representation of the latent geometry. One way to account for this inaccuracy could be to include the features in our optimization. This will induce, through a complicated nonlinear dependence, a different metric (i.e., adjacency matrix) and a different graph Laplacian. This approach lies at the heart of smoothing models based on conditional random fields (CRFs) used in image segmentation (see for example Krähenbühl & Koltun (2011)). We adopt a different approach by working in the spectral domain. Switching to the spectral domain allows us to modify the metric indirectly by applying orthogonal transformations, P andQ, to the bases Ψ,Φ. The purpose of these transformations is to rotate Ψ,Φ, in a way that will simplify the structure of C. For example, it is possible to diagonalize C by an appropriate choice of P ,Q via the SVD decomposition.
Since our method relies on the premise that the matrix M is smooth with respect to some graphs, our interest is in modified bases ΦP ,ΨQ, which arise from the eigendecomposition of a graph Laplacian. To that end, we shall use Lr,Lc, as proxies for the latent graph Laplacians, and promote bases that approximately diagonalize them by introducing two energy terms,
Erdiag ≡ ∥∥off (P>Φ>LrΦP )∥∥2F = ∥∥off (P>ΛrP )∥∥2F ,
Ecdiag ≡ ∥∥off (Q>Ψ>LcΨQ)∥∥2F = ∥∥off (Q>ΛcQ)∥∥2F , (6)
where off(·) denotes the off-diagonal elements. Under these modifications, the Dirichlet energy terms (5) become,
Erdir ≡ trace ( QC>P>ΛrPCQ >) , Ecdir ≡ trace ( PCQ>ΛcQC >P> ) .
(7)
Finally, we introduce the following energy terms to promote the (approximate) orthonormality of P ,Q:
Erorth(P ) ≡ ∥∥P>P − I∥∥2 F ,
Ecorth(Q) ≡ ∥∥Q>Q− I∥∥2 F .
(8)
Zoomout loss. Let us denote the training error achieved by a matrixXp,q ≡ ΦpCp,qΨ>q composed from the first p vectors in Φ and the first q vectors in Ψ as Zp,q ≡ ‖ ( ΦpCp,qΨ > q −M ) S‖2F . We define the zoomout loss as follows:
Ez = m,n∑ p=1,q=1 wp,qZp,q, (9)
with the weights wp,q ≥ 0. It can be shown that it is enough to use each value of p or q only once and therefore most of the wp,q shall be set to 0 (see Appendix A). The zoomout loss (9) is inspired by the greedy approaches for shape correspondence proposed by Vestner et al. (2017a) and Melzi et al. (2019). These methods approximate the point-to-point map between the shapes (i.e., the correspondence) by a smoothed map obtained through the application of spectral filters, and proceed by projecting the smoothed map onto the set of point-to-point maps. By gradually increasing the filters’ bandwidth, or resolution, the correspondence becomes more refined in each step. In contrast, we advocate minimizing the training error using all resolutions at once. This simultaneous multi-resolution approach incurs a penalty on the rank of the reconstructed matrix by implicitly giving more weight to the low frequency terms. For example, the sub-matrix C2,2 appears in all the terms Zp,q with p ≥ 2, q ≥ 2, emphasizing its importance. This allows us to be sloppy in the estimation of the rank ofM without compromising the results by much. We explore the effect of overparameterization in Section 4. Following the discussion above, we replace Φ,Ψ with ΦP ,ΨQ, obtaining Zp,q ≡ ‖ ( ΦPpCp,qQ > q Ψ > −M ) S‖2F . With this modification, the zoomout loss (9) should favor bases ΦP ,ΨQ, in which most of the energy of C is concentrated in the low frequencies, i.e., the top-left part. An interesting observation is that by setting p = m, q = n, we get the deep matrix factorization (DMF) method from Arora et al. (2019) (up to initialization). As we show in Section 4, this model alone, without any additional geometric priors, is sufficient to obtain results on par with the state-of-the-art on some datasets. This puts in question the quality of the geometric information in those cases. The complete minimization objective combines all the described terms weighed with the appropriate weights and minimized with respect toC, P andQ by gradient descent,
min C,P ,Q
Ez + µrE r dir + µcE c dir + ρrE r diag + ρcE c diag + orE r orth + ocE c orth. (10)

heading: 3.1 THEORETICAL DISCUSSION
text: In this section we discuss some physical interpretations of our approach.
Forward/Backward diffusion. The backbone of the zoomout loss are the terms Zp,q, which measure the disparity (restricted to the training set) betweenM and its smoothed version,Xp,q ≡ ΦpCp,qΨ > q . While we rely on the full spectral decomposition of Lr,Lc in order to constructXp,q at different resolutions, one can also construct them gradually. The process of zooming out, i.e., switching fromXp,q toXp+1,q+1, consists of two steps: smoothing or filtering - applying spectral filters Fp,Gq , to the functional map C = Φ>XΨ,
Cp,q = Fp ( Φ>XΨ ) G>q , (11)
and sharpening - forming Cp+1,q+1 from Cp,q by adding the missing frequencies, and composing Xp+1,q+1 via
Xp+1,q+1 = ΦCp+1,q+1Ψ >. (12)
In the algorithm described above we chose Fp,Gq to be diagonal matrices with p or q 1’s on the diagonal, i.e., step filters. One can think about different kind of filters that, at least conceptually, will have a similar effect. For example, smoothing can be done with filters of the following form,
Fp = I − τfLr, Gq = I − τfLc, (13) which correspond to a short time (forward) diffusion process, followed by a sharpening stage
(I + τbLr)(I − τfLr)X(I − τfLc)(I + τbLc), (14) which corresponds to backward diffusion. Forward-and-Backward (FAB) diffusion has been used for image denoising either as a nonlinear process on the original image grid (Gilboa et al., 2002), or via a linear process on a graph (Singer et al., 2009), and in shape processing for finding correspondence between non-rigid shapes (Vestner et al., 2017a). Despite backward diffusion being notoriously unstable, our algorithm exhibits a stable behaviour. In light of our experiments, we conjecture that it is possible to perform a stable backward diffusion on the product graph Gr × Gc via a controlled forward-and-backward diffusion process on each of the graphsGr andGc. Notice that (14) is no more than a second degree polynomial of the Laplacian applied to the signalX on both sides. Concurrent application of such polynomials result in a deep linear graph neural network. Our results and analysis support recent works such as Arora et al. (2019) and Wu et al. (2019) that argue in favor of such fully linear deep networks. Multirate filtering. Let us look at the gradient of Zp,q = ∥∥(ΦpCΨ>q −M) S∥∥2F ,
∂Zp,q ∂C
= Φ>p (( ΦpCΨ > q −M ) S S ) Ψq = Φ > p (R S) Ψq. (15)
In (15) we denoted byR ≡Xp,q −M the residual, and used the fact that S S = S for a binary mask. Ideally, the gradient should be the filtered version of the full residualR, but we only have its sampled versionR S. Is (15) a good approximation to Φ>p RΨq? From a signal processing perspective, it is sometimes possible to exchange the order of filtering and decimation (down-sampling). The conditions under which it is possible are known as the Noble identity for down sampling. Informally, if the down-sampler comes before the filter, the order between the filter and the down-sampler can be exchanged, but the filter has to be modified by interleaving it with zeros between adjacent samples. However, if the filter comes first, the order can only be exchanged if it has this special "interleaved with zeros" sparse form. Effectively, if the filter is a low-pass filter, it is possible to perform the down-sampling before the filtering. Since, by virtue of (5), ourX is driven towards having mostly low-frequencies, we can expect that the functional map obtained by the gradient descent iteration will be a good approximation of the true functional map2.

heading: 4 RESULTS
text: We demonstrate the effectiveness of our approach on the following datasets: Synthetic Netflix, Flixster, Douban, Movielens (ML-100K) and Movielens-1M (ML-1M) as referenced in Table 1.
The datasets include user ratings for items (such as movies) and additional features. For all the datasets we use the users and items graphs taken from Monti et al. (2017). The ML-1M dataset was taken from Berg et al. (2017). We constructed 10 nearest neighbor graphs for users/items from the features, and used a Gaussian kernel with σ = 1 for edge weights. See Table 4 in the Appendix for a summary of the dataset statistics. For all the datasets, we report the results for the same test splits as that of (Monti et al., 2017) and (Berg et al., 2017). The compared methods are referenced in Table 1.
Synthetic Netflix is a small synthetic dataset constructed by Kalofolias et al. (2014) and Monti et al. (2017), in which the user and item graphs have strong communities structure. See Figure 6 in Appendix for a visualization of the user/item graphs, the full matrix and its singular values. It is useful in conducting controlled experiments to understand the behavior of geometry-exploiting algorithms.
2This does not say that this model is correct, just that if M has the structure we assume, this iteration will capture it faithfully.
Proposed baselines. We report the results obtained using the following methods:
• SGMC and SGMC-Z (spectral geometric matrix completion): These are two variants of our method, differing from each other by the weights wp,q in (9). For these methods we chose a maximal resolution pmax, qmax (which can be larger than m,n) and a skip determining the spectral resolution, denoted by pskip, qskip. SGMC uses only wpmax,qmax = 1, with the rest set to zero, while SGMC-Z uses w1+kpskip,1+kqskip = 1, k ∈ N. • DMF (deep matrix factorization): This method, which coincides with the one suggested by
Arora et al. (2019), minimizes the loss ∥∥(PCQ> −M) S∥∥2
F , i.e., it does not incorporate
any geometric side information.
• FM (functional map): this method optimizes (10) only for C.
The optimization is carried out using gradient descent with fixed step size (i.e., fixed learning rate), which is provided for each experiment alongside all the other hyper-parameters in Table 5.
Initialization. All our methods are deterministic and need not require multiple runs to account for initialization. We always initialize the rotation matrices P ,Q with αI, α > 0. In Figure 7 we reported results on synthetic Netflix and ML-100K datasets for different values of α. We noticed that for SGMC and SGMC-Z it is best to use α = 1. According to (Arora et al., 2019), DMF requires a small α to decrease the generalization error (provided there are enough samples). We used DMF with α = 0.01 for Synthetic Netflix and α = 1 for the real world datasets, in accordance with Figure 7 and our experimentation. In the cases where only one of the bases was available, such as in Douban and Flixster-user only benchmarks, we set the basis corresponding to the absent graph to identity. The initialization of C is given by the projection ofM S on the first pinit eigenvectors of Lr and first qinit eigenvectors of Lc, i.e., C0 = Φ>pinit (M S) Ψqinit
3. We use pinit = qinit = 1 in all SGMC experiments.
Stopping condition. Our stopping condition for the gradient descent iterations is based on a validation set. We use 95% of the available entries for training (i.e., in the data term (9)) and the rest 5% for validation. The 95/5 split was chosen at random. We stop the iterations when the RMSE (16), evaluated on the validation set, does not change by more than tol = 0.000001 between two consecutive iterations, |RMSEk −RMSEk−1| < tol. Since we did not apply any optimization into the choice of the validation set, we also report the best RMSE achieved on the training set via early stopping. In this regard, the number of iterations is yet another hyper parameter that has to be tuned for best performance.
Test error. To evaluate the performance of the algorithms, we report the root mean squared error,
RMSE(X,S) = √ ‖(X −M) S‖2F∑
i,j Si,j (16)
computed on the test set provided with each dataset. Here X is the recovered matrix and S is the binary mask representing the support of the set on which the RMSE is computed.

heading: 4.1 DISCUSSION
text: A few remarkable observations can be extracted from Table 1: First, on the Douban and ML-100K dataesets, the simple DMF shows competitive performance with all the other methods. This suggests that the geometry information is not very useful for these datasets. Second, the proposed algorithm outperforms the other methods, despite its simple and fully linear architecture. This suggests that the other methods do not exploit the geometry properly, and this fact is obscured by their cumbersome architecture. Third, while some of the experiments reported in Table 1 showed only slight margins in favor of SGMC/SGMC-Z compared to DMF, the results in the Synthetic Netflix column, the ones reported on Synthetic Movielens-100K (Table 3) and the ones reported in Figure 8, suggest that when the geometric model is accurate our methods demonstrate superior results. Table 2 presents the
3Cpinit×qinit0 is the top-left submatrix of the full size C pmax×qmax . The rest of the entries are initialized
with 0.
Model SyntheticNeflix Flixster Douban ML-100K MC (Candès & Recht, 2009) – 1.533 0.845 0.973 GMC (Kalofolias et al., 2014) 0.3693 – – 0.996 GRALS (Rao et al., 2015) 0.0114 1.313/1.245 0.833 0.945 RGCNN (Monti et al., 2017) 0.0053a 1.179/0.926 0.801 0.929 GC-MC (Berg et al., 2017) – 0.941/0.917 0.734 0.910b FM (ours) 0.0064 3.32 3.15 1.10 DMF (Arora et al., 2019), (ours) 0.0468d 1.06 0.732 0.918c/ 0.922 SGMC (ours) 0.0021 0.971 / 0.900 0.731 0.912 SGMC-Z (ours) 0.0036 0.957 / 0.888 0.733 0.907c/ 0.913
a This number corresponds to the inseparable version of MGCNN. b This number corresponds to GC-MC. c Early stopping. d Initialization with 0.01I.
Table 1: RMSE test set scores for runs on Synthetic Netflix (Monti et al., 2017), Flixster (Jamali & Ester, 2010), Douban (Ma et al., 2011), and Movielens-100K (Harper & Konstan, 2016). For Flixster, we show results for both user/item graphs (right number) and user graph only (left number). Baseline numbers are taken from (Monti et al., 2017; Berg et al., 2017).
results of Movielens-1M. First, we can deduce that a simple linear DMF model is able to match the performance of complex alternatives. Furthermore, using graphs produces slight improvements over the DMF baseline and overall provides competitive performance compared to heavily engineered methods.
Comparing DMF and SGMC. Arora et al. (2019) reports that for a low rank matrix, above a certain number of samples - DMF converges to the minimum nuclear norm solution (see Figure 2 in their paper). Below that number it induces a better regularization on the rank of the matrix than the nuclear norm, which still allows to recover the matrix. However, in the real datasets we tested on, the number of available samples is way below that threshold (see Table 4). The results reported in Table 1 indicate that in this extremely data poor regime the performance of DMF drops, and the extra information present in the graphs is crucial. We further confirmed this observation through a study conducted on a synthetic example, constructed from the synthetic Netflix graphs: Figure 8-left compares reconstruction errors on synthetic matrices when increasing the rank, using 15% of the samples for training. Figure 8-right compares reconstruction errors on a synthetic rank-10 matrix with increasing the density of the training set. Further details appear in the caption. The results can be summarized as follows: SGMC consistently outperforms DMF, in particular in the data poor regime. The gap between them decreases as we increase the number of samples. Similar behavior was observed in the cold-start analysis of the ML-100K dataset (see Figure 1 and the discussion below).

heading: 4.2 SYNTHETIC DATASETS
text: While the experiments reported in Table 1 showed slight margins in favor of methods using geometry, we further experimented with a synthetic model generated from the ML-100K dataset. The purpose of this experiment is to investigate whether the results are due to the DMF model or due to the geometry as incorporated by SGMC/SGMC-Z. The synthetic model was generated by projecting M on the first 50 eigenvectors of Lr,Lc, and then matching the ratings histogram with that of the original ML-100K dataset. This nonlinear operation increased the rank of the matrix from 50 to about 400. See Figure 5 in the Appendix for a visualization of the full matrix, singular value distribution and the users/items graphs. The test set and training set were generated randomly and are the same size as those of the original dataset. The results reported in Table 3 and those on the Synthetic Netflix column in Table 1 clearly indicate that SGMC/SGMC-Z outperforms DMF, suggesting that when the geometric model is accurate it is possible to use it to improve the results. On Synthetic Netflix, we notice that by using SGMC, we outperform (Monti et al., 2017) by a significant margin, reducing the test RMSE by half. Furthermore, it can be observed that DMF performs poorly on both the synthetic datasets compared to SGMC/SGMC-Z, raising a question as to the quality of the graphs provided with those datasets on which DMF performed comparably.
Model ML-1M PMF (Salakhutdinov & Mnih, 2007) 0.883 I-RBM (Salakhutdinov et al., 2007) 0.854 BiasMF (Koren et al., 2009) 0.845 NNMF (Dziugaite & Roy, 2015) 0.843 LLORMA-Local (Lee et al., 2016) 0.833 I-AUTOREC (Sedhain et al., 2015) 0.831 CF-NADE (Zheng et al., 2016) 0.829 GC-MC (Berg et al., 2017) 0.832 DMF (Arora et al., 2019), (ours) 0.843 SGMC (ours) 0.839
Table 2: Comparison of test RMSE scores on Movielens-1M dataset. Baseline scores are taken from (Zheng et al., 2016; Berg et al., 2017)
Model Synthetic ML-100K DMF 0.9147 SGMC 0.5006 SGMC-Z 0.4777
Table 3: Comparison of average RMSE of DMF, SGMC and SGMC-Z baselines calculated on 5 randomly generated Synthetic Movielens-100K datasets.

heading: 4.3 COLD START ANALYSIS
text: A particularly interesting scenario in the context of recommender systems is the presence of cold-start users, referring to the users who have not rated enough movies yet. We perform an analysis of the performance of our method in the presence of such cold start users on the ML-100K dataset. In order to generate a dataset consisting of Nc cold start users, we sort the users according to the number of ratings provided by each user, and retain at most Nr ratings (chosen randomly) of the bottom Nc users (i.e., the users who provided the least ratings). We choose the values Nc = {50, 100, 150, 200, 300, 400, 500} andNr = {1, 5, 10}, and run our algorithms: DMF, SGMC and SGMC-Z, with the same hyperparameter settings used for obtaining Table 1. We use the official ML-100K test set for evaluation. Similar to before, we use 5% of the training samples as a validation set used for determining the stopping condition. The results presented in Figure 1 suggest that the SGMC and SGMC-Z outperform DMF significantly, indicating the importance of the geometry as data becomes scarcer. As expected, we can see that the performance drops as the number of ratings per user decreases. Furthermore, we can observe that SGMC-Z consistently outperforms SGMC by a small margin. We note that SGMC-Z, even in the presence of Nc = 500 cold start users with Nr = 5 ratings, is still able to outperform the full data performance of (Monti et al., 2017), demonstrating the strength of geometry and implicit low-rank induced by SGMC-Z.
Ablation study. We study the effects of different hyper-parameters of the algorithms on the final reconstruction of the matrix. We perform an ablation study on the effects of ρ, µ, pmax, qmax on DMF, SGMC and SGMC-Z. The results are summarized in Figures 2, 3, 4. It is interesting to note that in the case of DMF and SGMC, overparametrizing C,Q,P consistently improves the performance (see Figure 4), but it only holds up to a certain point, beyond which the overparametrization does not seem to effect the reconstruction error.
Scalability. In this work we focused on the conceptual idea of solving ma-
trix completion via the framework of functional maps, paying little attention to the issue of scalability. The dependence of our method on eigenvalue decomposition renders it unscalable. While this did not pose a problem for the small data sets we used in this report, it is nonetheless a drawback. We intend to address this issue in our future work.

heading: 5 CONCLUSION
text: In this work we have proposed a simple spectral technique for matrix completion, extending ideas borrowed from the field of non-rigid shape analysis. Our approach combines a full multiresolution spectral loss with (implicit) metric learning. Under a suitable change of basis, we obtain a fully linear network that gives rise to a useful interpretation via the framework of functional maps. We have demonstrated state-of-the-art results on a few recommendation systems datasets, surpassing results obtained by much more complicated architectures. In addition, we have demonstrated that some results which are usually attributed to a clever use of geometry, can be obtained without any geometry altogether. We believe that this work bridges the gap between the communities of geometric deep learning, non-rigid shape analysis, deep linear networks and spectral graph theory; it allows for a new line of research in transferring the theory and algorithms across these fields.

heading: A APPENDIX
text: A.1 SPECTRAL SELECTION
Here we shall prove that it is enough to choose the weights wp,q in (9) such that each p or q appears only once. For simplicity we shall assume pmax = qmax and that pskip = qskip = 1 (see Section 4). Proposition 1. LetW denote the matrix of weights used in (9) and assume that they satisfy
pmax∑ p=1 wp,q = 1, qmax∑ q=1 wp,q = 1, wp,q ≥ 0. (17)
Then it is always possible to choose weights ap,q ∈ {0, 1} achieving, for the same optimal variables, a value of (9) which is at least as low as the one obtained with wp,q .
Proof. Let P ∗,C∗,Q∗ be the optimal variables obtained by solving (10) with some weightsW .
Then for the same optimal variables, one can find weights A achieving a value of (9) (and consequently, of (10)) which is at least as low as the one obtained withW , by solving
A∗ = arg min A ∑ p,q ap,qZp,q(P ∗,C∗,Q∗) s.t.  A1 = 1 A>1 = 1 A ≥ 0. (18)
Problem (18) is a linear assignment problem and therefore has an integral solution ap,q ∈ {0, 1} (Schrijver, 1998).
D at
as et
M et
ho d
p m a x /q
m a x
p sk
ip / q s
k ip
µ r / µ c
ρ r / ρ c
o r / o c
Tr ai
na bl e va ri ab le s
le ar
ni ng
ra te
D M
F 20
0 /2
0 0
− /−
− /−
− / −
− /−
P ,C
,Q 5 ×
1 0 − 5
FM 20
0 /2
0 0
1/ 1
0 .4 / 0.
4 − / −
− /−
C 5 ×
1 0 − 4
Sy nt
he tic
N et
fli x
SG M
C 20 /2
0 − /−
0. 0 0 1 /0 .0
0 1
0 .1 / −
− /−
P ,C
5 ×
1 0 − 3
SG M
C -Z
50 0 /5
0 0
3/ 1
0. 4/
0. 4
0 .1 /0 .1
− /−
P ,C
5 ×
1 0 − 5
D M
F 30
00 / 30
0 0
− /−
− /−
− / −
− /−
P ,C
,Q 1 ×
1 0 − 4
Fl ix
st er
SG M
C 30
00 / 30
0 0
− /−
0. 0 0 0 1/
0. 0 0 0 1
0 .0
0 0 1/
0 .0
0 0 1
− /−
P ,C
,Q 1 ×
1 0 − 4
SG M
C -Z
20 0 /2
0 0
2/ 2
0. 0 0 2 5/
0. 0 0 2 5
− / −
− /−
P ,C
5 ×
1 0 − 6
Fl ix
st er
SG M
C 30
00 / 30
0 0
− /−
0 .0
0 0 1 /−
0 .0
0 0 1/ −
− /−
P ,C
,Q 5 ×
1 0 − 5
(u se
rs on
ly )
SG M
C -Z
20 0 /2
0 0
2 0/
2 0
0 .0
0 2 5 /−
0. 0 0 1 / −
− /−
P ,C
,Q 5 ×
1 0 − 7
D M
F 30
00 / 30
0 0
− /−
− /−
− / −
− /−
P ,C
,Q 6 ×
1 0 − 6
D ou
ba n
SG M
C 25
00 / 25
0 0
− /−
0. 0 0 1 /−
0. 0 0 1 / −
0. 0 0 1 /−
P ,C
,Q 2 ×
1 0 − 6
SG M
C -Z
10 00 / 10
0 0
5 0/
1 0 0 0
0. 0 1 1 /0
0. 0 0 4 /0
0. 0 0 1 /0
P ,C
,Q 2 ×
1 0 − 6
D M
F 20
00 / 20
0 0
− /−
− /−
− / −
− /−
P ,C
,Q 5 ×
1 0 − 5
M L
-1 00
K SG
M C
40 00 / 40
0 0
− /−
0. 0 0 0 3/
0. 0 0 0 3
0 .0
0 0 1/
0 .0
0 0 1
− /−
P ,C
,Q 5 ×
1 0 − 5
SG M
C -Z
32 00 / 32
0 0
3 0/
3 5
0 .0
3 /0 .0
3 0 .2 /0 .2
0 .0
9 /0 .0
9 P ,C
,Q 3 ×
1 0 − 7
D M
F 70
00 / 70
0 0
− /−
− /−
− / −
− /−
P ,C
,Q 1 ×
1 0 − 5
M L
-1 M
SG M
C 70
00 / 70
0 0
− /−
0. 0 0 0 1/
0. 0 0 0 1
− / −
− /−
P ,C
8 ×
1 0 − 5
D M
F 80
00 / 80
0 0
− /−
− /−
− / −
− /−
P ,C
,Q 9 ×
1 0 − 5
Sy nt
he tic
M L
-1 00
K SG
M C
60 0 /6
0 0
− /−
0. 0 0 1 /0 .0
0 1
0 .0
0 9 / 0.
0 0 9
− /−
P ,C
,Q 2 ×
1 0−
5
SG M
C -Z
50 0 /5
0 0
3/ 1
0. 0 0 1 /0 .0
0 1
0 .0
0 9 / 0.
0 0 9
− /−
P ,C
5 ×
1 0 − 6
Ta bl
e 5:
H yp
er -p
ar am
et er
se tti
ng s
fo rt
he al
go ri
th m
s: D
M F,
SG M
C an
d SG
M C
-Z ,r
ep or
te d
in Ta
bl es
1, 2,
3.

Review summaries:
This paper proposes a novel approach for the loss function of matrix completion when geometric information is available. The proposed method consists of two ideas: (1) spectral regularization (i.e., Dirichlet energy) with a re-parameterizing basis and (2) multiresolution of spectral loss (i.e., zoomout loss). In addition, the zoomout loss is motivated by the approach for shape correspondence and can be a generalization of the recent matrix completion method (deep matrix factorization). Empirical results show the best performance compared to other recent methods under small-scale datasets. Moreover, the proposed method outperforms when the geometric model is accurate (verified on the synthetic setting) and this can reflect that the proposed method is a good choice when the graph structures are given.

This paper aims to solve the matrix completion problem by incorporating geometric information. The proposed approach involves using graphs encoding relations between rows (and columns), applying spectral decomposition to these graphs, and using a multi-resolution spectral geometric loss to reconstruct the functional map which could then be used to directly recover the underlying matrix. The paper evaluates the proposed network on both synthetic and real datasets and shows improvements over the existing geometric methods and convex relaxations.