Deep geometric matrix completion:  Are we doing it right?
Authors: Amit Boyarski
Sanketh Vedula
Alex Bronstein
Venue:  (2020)
Keywords: Geometric Matrix Completion
Spectral Graph Theory
Functional Maps
Deep Linear Networks

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.

Under review as a conference paper at ICLR 2020
DEEP GEOMETRIC MATRIX COMPLETION: ARE WE DOING IT RIGHT?
Anonymous authors Paper under double-blind review
ABSTRACT
We address the problem of reconstructing 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, 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.
INTRODUCTION
Matrix completion deals with the recovery of missing values matrix from a subset of its entries,
(1) Here X stands for the unknown matrix, M E RRxx for the ground truth matrix, S is binary mask representing the input support, and @ denotes the Hadamard product. Since problem (T) is ill-posed, it is common assume that M belongs to some low dimensional subspace. Under this assumption. the matrix completion problem can be cast via the least-squares variant,
Find X
X o M e S.
min rank (X) + / |(X M) c S X
(2)
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 parametrizing X in factorized form.
X The rank is upper-bounded by the inner dimensions of Y Z Recent studies by Arora ct al. 12019) Gunasckar et al. (2017), suggest that overparametrizing X product of several matrices results in a low rank matrix due to an implicit regularization induced by the gradient descent trajectories. According (Gunasekar et al. 2017| AAooa al., 2019), given enough entries and independent of the depth, overparametrized deep matrix factorization (DMF) models are equivalen nuclear norm minimization. However, in the data poor regime these methods differ, and 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 M as training set or training samples, and denote by test set a subset of the (unknown) entries of M 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
Under some technical conditions, See Arora et al. 2019

---

Under review as a conference paper at ICLR 2020
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 general graphs and manifolds. For example, graph convolutional neural networks (GCNNs) follow the architecture of standard CNNs, but replace the Fuclidean 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 (c.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-ther of-tth-art results, their design is arguably cumbersome and non-intuitive. has recently been demonstrated that some graph CNN architectures can be greatly simplified, and still perform competitively on several graph analysis tasks (Wu 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 (Ovjjanikov et al. 2012 (016). 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. 201 a) and zoomoul (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 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, multiresolution spectral geometric loss inspired by recent advances in shape correspondence.
We show that via simple shallow and fully linear network, is possible 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 of-te-----h--rrtt- can be achieved even without
BACKGROUND
Spectral graph theory. Let G
F.) be (weighted) graph specified by its vertex set V and edge set E, and let Z be its adjacency matrix. Given a function RI on the vertices, define the following quadratic form (also known as Dirichlet energy) measuring the variability of the function & the graph,
x Lx
Σ (a,D)E
Wab (I(a) - =x())²
The matrix L is called the (combinatorial) graph Laplacian, and is given by L D Ω where D = diag(S?1) is the degree matrix. L is symmetric and positive semi-definite and therefore admits a spectral decomposition
& The graph Laplacian is a discrete generalization of the continuous -eltace operator, and therefore has similar properties. One can think of the eigenpairs (Φ); Ax) as the graph analogues of "harmonic" and "frequency". A function == E. a on the vertices of the graph whose coefficients a; 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 regularize some loss term. For example, this approach gives rise to the popular bilateral and local means filters (Gadde al. 2013).
E,, 22) G2 = (V2, E2, 12) be two graphs, and let Φ v, be two orthonormal bases for functions defined on the vertices of these graphs. Given two such functions,
Functional maps. Let G = E,
2

---

Under review as a conference paper at ICLR 2020
& G1 and y 3 on G2, one can define map C' between their representations and G. i.e. a = ① 2 = C y = CB. The matrix represents a linear map between the functional spaces on Gj and G2. known a functional map. Let us denote the Cartesian product of G1 and G2 by G,D DzD is graph with vertex set V1 x V2, on which two nodes (u, u') n'), (v, u') are adjacent if either u v and (u', v'), ) E2 u' v' and (u, v) E Fj. Let X be function defined on G2 then the functional map is given by projecting X onto the corresponding bases Q. V, C' = Φ X Using the SVD, one can decompose X = UEV between UΣ, function on one graph, and V. function on the other. To get X back from the functional map, one can use X $C For computational reasons, it is common to use truncated bases 4 V, in which case the last equality holds only approximately.
interpret C as a mapping
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, simpler structure of the functional map emerges. For example, by introducing two orthonormal matrices P and Q, one can make the functional map C' = (&P) P) X (IQQ) diagonal. These orthonormal matrices can be thought of as a way of aligning the bases 4, V with the principal axes of X.
SPECTRAL GEOMETRIC MATRIX COMPLETION
We assume that we are given a of samples from the unknown matrix M Rmxn, encoded by a binary mask S, and two graphs Gr, Ge. encoding relations between the rows and the columns, respectively. Denote the Laplacians of these graphs and their spectral decompositions by L. AA. L. = A Our approach relies on a minimization problem of the form
min (x) + p,trrae (x X, + patrace (XL.X X
(4)
with Eg denoting the data term that we discuss in the sequel. The other two terms in (4) are the Dirichlet energies of X computed on G,, Ge. defined in (3). These energies measure the variability of X along neighbouring nodes on these graphs. Using X = &C and the spectral
decompositions of L,, Le, we can equivalently write them in terms of C,
= trace (VC T L,, = trace (CTA.C). trace (XL.X trace (&CV L. WC trace (CA.C
trace
(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 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 (201T). 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 and Q, to the bases V d. The purpose of these transformations is to rotate V Φ in 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, interest is in modified bases & P. T QQ which arise from the eigendecomposition of graph Laplacian. To that end, we shall use L., Le, as proxies for the latent graph Laplacians, and promote bases that approximately diagonalize them by introducing two energy terms.
Eling = off (PT ①T L. L)) = ||off (PT (TA,P) F
(6)
Ee ding = off (Q v
T L. & 1] Ifff (QTAQQ) (.
3

---

Under review as a conference paper at ICLR 2020
where o- denotes the off diagonal elements. Under these modifications, the Dirichlet energy terms (5) become,
Edr trace (QC PT PTA, A,PC)) E trace (PCQTAQQC) A P.).
Finally, introduce the following energy terms to promote the (approximate) orthonormality of P,Q:
ti (P) = | P || r
(8)
Forth (Q) = Q Q - / 1F
Zoomout loss. Let us denote the training error achieved by matrix X Bp V composed from the first vectors in & and the first q vectors in V as Zp.g = ( p. We define the zoomout loss as follows:
p.q
ppppppp L
M @ S
E2
Σ
Wp.9 Wp.g2pp.r
1
with the weights "p.. 2 0. can be shown that it is enough to use each value of p or q only once and therefore most of the Wp.a shall be set to 0 (see Appendix [A). The zoomout loss ( is inspired by the greedy approaches for shape correspondence proposed by Vestner et al. (2
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- toint maps. By gradually increasing the filters' bandwidth, or resolution, the correspondence becomes more refined in each step. In contrast, advocate minimizing the training error using all resolutions once. This simultancous 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 2, q 2 2, emphasizing its importance. This allows us to be sloppy in the estimation of the rank of M without compromising the results by much. We explore the effect of overparameterrization in Section 4 Following the discussion above, we replace &, v with P, VQ, obtaining Zp.g = ④ P, C... P, Q T M) @ $ With this modification, the zoomout loss ( should favor bases P., Q. in which most of the energy of C is concentrated in the low frequencies, i.c., the top-left part. An interesting observation is that by setting p = m, q = n, get the deep matrix factorization (DMF) method from Arora et al. (2019) (up initialization). As we show in Section this model alone, without any additional geometric priors, is sufficient to obtain results par with the state-of-fe of-tth-art 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 C, P and Q by gradient descent,
min E, + M4 Edir + Eā + Pr Eriagi + Pe + Forth + Eo C,P.Q
(10)
3.1 THEORETICAL DISCUSSION
In this section we discuss some physical interpretations of our approach.
Forward/Backwarr diffusion. The backbone of the zoomout loss the terms Zp.q. which measure the disparity (restricted to the training set) between M and its smoothed version, Xp.9 L, V While we rely on the full spectral decomposition of Ly, Le in order to construct Xp.a at different resolutions, switching from X, to Xp+1.g+1. consists of two steps: smoothing or filtering applying spectral filters Fp, Gg. to the functional map C = V
also construct them gradually. The process of zooming out, ie..,
Cp. F, (Φ X G.T
(11)
4

---

Under review as a conference paper at ICLR 2020
and sharpening forming Cp+1.t+1 from Cp.9 by adding the missing frequencies, and composing X xp+1.91 via
X x+11 = &Cp+1.0+1
(12)
In the algorithm described above we chose Fp. Gg to be diagonal matrices with or q I'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,
F, = T,L,, G, which correspond to a short time (forward) diffusion process, followed by a sharpening stage (g - Ty L, X Ty L.) + tbLe).
TT
(13)
(14)
which corresponds to backward diffusion. Forward-and- aaa-udd-nd-BBawwwan Backward (FAB) diffusion has been used for image denoising either as a nonlinear process on the original image grid (Gilboa et al.) 22002), or via a linear process on graph (Singer al.) 22009). and in shape processing for finding correspondence between non-rigid shapes (Vestner et al., 2017a). Despite backward diffusion being notoriously conjecture that it
unstable, our algorithm exhibits stable behaviour. In light of experiments, is possible to perform a stable backward diffusion on the product graph G, X G. via controlled arrwardanddbackwarte diffusion process on each of the graphs G, and G.. Notice that (14) is no more than second degree polynomial of the Laplacian applied to the signal X on both sides. Concurrent application of such polynomials result 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.0 = = CV. - M) @ S
8Zp.g - ( ( M) e s S) 12 = Φ R (OS)) Lg.
(15)
ac
In (15) we denoted by R = Xp.q M the residual, and used the fact that o S = for a binary mask. Ideally, the gradient should be the filtered version of the full residual R, but only have its sampled version R @ S. Is 15) good approximation to $ RV,,"
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 low-pass filter, is possible to perform the down-sampling before the filtering. Since, by virtue of (5), our X 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 mar
RESULTS
We demonstrate the effectiveness of our approach the following datasets: Synthetic Netflix, Flixster, Douban, Moviclens (ML-100K) and Movielens- 1M (ML-IM) as referenced in Table
The datasets include user ratings for items (such movies) and additional features. For all the datasets we use the users and items graphs taken from Monti et al. (2017) The ML-IM 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 o = 1 for edge weights. See Table the Appendix for a summary of the dataset statistics. For all the datasets,
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
Synthetic Netflix is small synthetic dataset constructed by Kalofolias et al. (2014) and Monti jet all..,2200 (2017), in which the user and item graphs have strong communities structure. See Figure Appendix for visualization of the user/item graphs, the full matrix and its singular values. is useful in conducting controlled experiments to understand the behavior of geometry-exploiting algorithms.
This does not say that this model is correct, just that if M has the structure we assume, this iteration will capture faithfully.
5

---

Under review as a conference paper at ICLR 2020
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 Up,4 in ② For these methods we chose a maximal resolution Pmnax; fmax (which can be larger than m, n) and skip determining the spectral resolution, denoted by Pskip: (skip- SGMC uses only "Pmax = with the rest set to zero, while SGMC-Z uses 4kpkpppp 1- 1+ kquaip 1, A N.
DMF (deep matrix factorization): This method, which coincides with the one suggested by Arora et al. 2019), minimizes the loss any geometric side information.
(PCQQ M) S||pp i.e. does incorporate
FM (functional map): this method optimizes (TO) only for C.
The optimization 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-parametens 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 aI, a 0. In Figure 7 we reported results on synthetic Netflix and ML-100K datasets for different values of a. We noticed that for SGMC and SGMC-Z is best use 1. According (Arora et al. 2019), DMF requires small a to decrease the generalization eπгоr (provided there are enough samples). We used DMF with 0.01 for Synthetic Netfix and a for the real world datasets, accordance with Figure 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 identity. The initialization of C' is given by the projection of M @ S on the first Pinit eigenvectors of L, and first We use Pinit
Pnit eigenvectors of Le, i.e., Co = & T (M S) Timit experiments.
Pinit = 1 in all SGMC
Pintt
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., the data term ( 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, [RMSE, - RMSE,-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, report the root mean squared error,
RMSE( X, S) = (x M) 3 SI
(16)
Σi Sij
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.
4.1 DISCUSSION
few remarkable observations can be extracted from Table I 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 obscured by their cunbersome architecture. Third, while some of the experiments reported in [T 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 presents the
3 PiPisi X Xquit is the top-left submatrix of the full size Pimaa X Gmax, The rest of the entries are initialized
with 0.

---

Under review as a conference paper at ICLR 2020
Model
Synthetic Neflix
Flixster
Douban
ML-100K
MC (Candès & Recht 2009
1.533
0.845
0.973
GMC (Kalooola et al. 4
0.3693
0.996
GRALS
Rao et al. 2015)
0.0114
1.313/ / 1.24
0.833
0.945
RGCNN Monti et al.
2017
0.0053
1.179/0..0 00.926
0.801
0.929
GC-MC Berg et al. 2017)
0.941 0.941/0.917
/0.917
0.734
0.910
FM (ours)
0.0064
3.32
3.15
1.10
DMF (Arora et al.
2019), (ours)
0.0468d
1.06
0.732
0.91 8% 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.907% 0.913
8 This number corresponds to the inseparable version of MGCNN.
This number corresponds GC-MC.
Early stopping.
d Initialization with 0.011.
Table 1: RMSE
for on Synthetic Netflix (Monti 2017). Flixster (Jamali & Ester 2010), Douban (Ma et al. 2011), and Moviclens- 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 al. 2017 Berg et al. 2017).
results of Movielens- M. First, performance of complex alternatives. Furthermore, using graphs produces slight improvements over the DMF baseline and overall provides competitive performance compared heavily engineered methods.
deduce that simple linear DMF model is able match the
Comparing DMF and SGMC. Arora al. (2019) reports that for low rank matrix, above certain number of samples DMF converges to the minimum nuclear norm solution (see Figure in their paper). Below that number it induces better regularization 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 T indicate that in this extremely data poor regime the performance of DMF drops, and the extra information present the graphs is crucial. We further confirmed this observation through study conducted on a synthetic example, constructed from the synthetic Netflix graphs: Figure left compares reconstruction errors on synthetic matrices when increasing the rank, using 15% of the samples for training. Figure [ right compares reconstruction errors on synthetic rank-10 matrix with increasing the density the training set. Further details appear in the caption. The results can be summarized 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 I and the discussion below).
the rank of the matrix than
4.2 SYNTHETIC DATASETS
While the experiments reported in T showed slight margins in favor of methods using geometry, further experimented with 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 L,, Le. and then matching the ratings histogram with that of the original ML-100K dataset. This nonlinear operation increased the rank the matrix from 50 to about 400. See Figure 5 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 and those on the Synthetic Netflix column in Table 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., (017)) 7 by a significant margin, reducing the test RMSE by half. Furthermore, it can be observed that DMF performs poorly both the synthetic datasets compared to SGMCISGMC-Z, raising question as to the quality of the graphs provided with those datasets on which DMF performed comparably.
7

---

Under review as a conference paper at ICLR 2020
Model
ML-1M
PMF (Salakhutdinov & Mnih
2007
0.883
I-RBM (Salakhutdinov et al.
2007)
0.854
BiasMF (Koren et al. 2009)
0.845
Model
Synthetic ML-100K
NNMF (Dzuugaite & Roy 2015
0.843
DMF
0.9147
LLORMA-Local [Lee et al.
201
0.833
SGMC
0.5006
LAUTOREC (Sehhan et al.
2013
0,831
SGMC-Z
0.4777
CF-NADE (Zheng et al. 2016)
0.829
GC-MC (Berg et al. 2017
0.832
Table 3: Comparison of average RMSE of
DMF (Arora et al. 2019)
(ours)
0.843
DMF, SGMC and SGMC-Z baselines cal- culated on randomly generated Synthetic Movielens- 100K datasets.
CGMC(ours)
0.839
Table 2: Comparison of test RMSE scores on Movielens IM
dataset, Baseline scores are taken from Zhengg et al. 2016 Berg
al. 2017)
4.3 COLD START ANALYSIS
particularly interesting scenario in the context of recommender systems the presence of cold-start users. referring to the users who have not rated enough movies yet. We perform analysis of the performance of our method in the presence of such cold start users on the ML-100K dataset. sort the users according to
In order to generate dataset consisting of N₂ cold start users, the number of ratings provided by each user, and retain at most N, ratings (chosen randomly) of the bottom No users (i.e., the users who provided the least ratings). We choose the values No = (50. 100, 150, 200, 300, 400, 500) and N, = [1, 5, 10), and run our algorithms: DMF, SGMC and SGMC-Z, with the same hyperparameter settings used for obtaining Table T 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 Figure 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 small margin. We note that SGMC-Z, even the presence of N, 500 cold start users with N, ratings, is still able to outperform the full data performance of (Monti ct al. 2017). demonstrating the strength of geometry and implicit low-rank induced by SGMC-Z.
0.96
--SGMC
Ablation study. We study the ef- feets of different hyper-parameters of the algorithms on the final recon- struction of the matrix. We perform an ablation study on the effects of p. Pmaxx Umax DMF, SGMC and SGMC-Z. The results are summa- It is in- teresting to note that in the case of DMF and SGMC, overparametrizing C,Q.P consistently improves the performance (see Figure but only holds to a certain point, beyond which the overparametrization does not seem to effect the reconstruction error.
0.945
DMF
Nr rating
0.94
Nr 5 rating
RMSE
0.935
0.93
0.925
rized in Figures 2 3
0.92
0.916
50
100
100
200
250
300
350
400
450
300
Number
Figure 1: Comparison of test RMSE in the presence of cold start users on the ML-100K dataset. The x-axis corresponds to the num- ber of the cold start users N. 50, 100, 500. Red, blue and green correspond to DMF, SGMC and SGMC-Z Z methods respec- tively as also shown in the legend. Different shapes of the markers indicate different number of maximum ratings (N, = (1,5, 10)) available per cold-start user.
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 this report, it is nonetheless a drawback. We intend to address this issue in future work.
8

---

Under review as a conference paper at ICLR 2020
5 CONCLUSION
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 full multiresolution spectral loss with (implicit) metric learning. Under suitable change of basis, we obtain a fully linear network that gives rise to useful interpretation via the framework functional maps. We have demonstrated state-of-thee obtained by much more complicated architectures. In addition, we have demonstrated that some results which are usually attributed clever use of 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 new line of research in transferring the theory and algorithms across these fields.
results few recommendation systems datasets, surpassing results
be obtained without any geometry
REFERENCES
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. arXiv preprint arXiv:1905. 2019.
Rianne van den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. 2017.
arXiv preprint arXiv:1706.000
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational mathematics, 9(6):717, 2009.
Gintare Karolina Dziugaite and Daniel M. Roy. Neural network matrix factorization. abs/1511. 151144644,, 2015. /tt/ht:pp//arxxiv.oo httg:/abs/111111
CoRR,
Akshay Gadde, Sunil K Narang, and Antonio Ortega. Bilateral filter: Graph spectral interpretation and extensions. In 2013 IEEE International Conference on Image Processing, pp. 1222-1226. IEEE, 2013.
Guy Gilboa, Nir Sochen, and Yehoshua Y Zeevi. Forward-and-ber anwaadd-nd--backward diffusion processes for adaptive image enhancement and denoising. IEEE transactions on image processing, 11(7): 689-703, 2002.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pp. 5191-6 2017.
Maxwell Harper and Joseph Konstan. The movielens datasets: History and context. Acm Iransactions interactive intelligent systems (tās), 5(4):19, 2016. URR.https::///rou org/datases www.eoviiieeeoooee elens
Mohsen Jamali and Martin Ester. A matrix factorization technique with trust propagation for recommendation in social networks. In Proceedings of the fourth ACM conference on Recommender systems, pp. 135-142, ACM, 2010.
Vassilis Kalofolias, Xavier Bresson, Michael Bronstein, and Pierre Vandergheynst. Matrix completion on graphs. arXiv preprint 1rXiv: 1717, 2014.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-33) 37, August 2009. ISSN 0018-9162, doi: 10. 19/0M..00220........... URL http:httt// doi www.ddo...oooooooooo 11..://.1111111CCC..
Philipp Krähenbühl and Vladlen Koltun. Efficient inference in fully connected crfs with gaussian edge potentials. Advances in neural information processing systems, pp. 109-117, 201
Yann LeCun. self supervised learning, 2019.
24C2| ICML Workshop on Generative Modeling and Mased Reasoning for Robotics and AI 2019-099 2019-06-14.

---

Under review as a conference paper at ICLR 2020
Joonseok Lee, Seungyeon Kim, Guy Lebanon, Yoram Singer, and Samy Bengio. Llorma: Local low-rank matrix approximation. Journal of Machine Learning Research, 17(15):1-24, 2016. URL
/ttt::/jmixx org.or////oooo.oo
1001300.50 html
Or Litany, Emanuele Rodolå, Alexander M Bronstein, and Michael M Bronstein. Fully spectral partial shape matching. In Computer Graphics Forum, volume 36, pp. 247-258. Wiley Online Library, 2017.
Hao Ma, Dengyong Zhou, Chao Liu, Michael R Lyu, and Irwin King. Recommender systems with social regularization. In Proceedings of the fourth ACM international conference on Web search and data mining, pp. 287-296. ACM, 2011.
Simone Melzi, Jing Ren, Emanuele Rodola, Maks Ovsjanikov, and Peter Wonka. Zoomout: Spectral upsampling for efficient shape correspondence. arXiv preprint 1eXiv::904.78800 2019.
Federico Monti, Michael Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi-graph neural networks. In Advances in Neural Information Processing Systems, pp. 3697- 2707,2017
Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. Func- tional maps: flexible representation of maps between shapes. ACM Transactions on Graphics (TOG), 31())330 2012.
Maks Ovsjanikov, Etienne Corman, Michael Bronstein, Emanuele Rodolå, Mirela Ben-Chen, Leonidas Guibas, Frederic Chazal, and Alex Bronstein. Computing and processing correspon- dences with functional maps. In SIGGRAPH ASIA 2016 Courses, pp. 9, ACM, 2016.
Nikhil Rao, Hsiang-Fu Yu, Pradeep K Ravikumar, and Inderjit S Dhillon. Collaborative filtering with graph information: Consistency and scalable methods. Advances neural information processing systems, pp. 2107-2115, 2015.
Ruslan Salakhutdinov and Andriy Mnih. Probabilistic matrix factorization. In Proceedings of the 20th International Conference on Neural Information Processing Systems, NIPS 07, pp. 1257-1264 USA, 2007. Curran Associates Inc. ISBN 978-1-60560-352-0, URL http:://dd... acm. org/
ci www.:on...cm...........e... 2981720
Ruslan Salakhutdinov, Andriy Mnih, and Geoffrey Hinton. Restricted boltzmann machines for collaborative filtering. In Proceedings of the 24th International Conference on Machine Learning, ICMI. '07, pp. 791-798, New York, NY, USA, 2007. ACM. ISBN 978- 1 5955999939333333 doi: 1273596
0tt15//222749..2233599 URL WtRLhttp://ddr acm. org 11..101..111131 1et.:1151127345555 wwwpo//..1////111111
Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998.
Suvash Sedhain, Aditya Krishna Menon, Scott Sanner, and Lexing Xie. Autoree: Autoencoders meet collaborative filtering. In Proceedings of the 24th International Conference on World Wide Web, WWW '15 Companion, pp. 111-112, New York, NY, USA, 2015. ACM. ISBN 978-1- 4503-3473-0. doi: 10. /5/1144472740008.7777222
URL hhtpp://dos acm. org//o../g1oo.....ooo 1145/
2740908 2742726
Amit Singer, Yoel Shkolnisky, and Boaz Nadler. Diffusion interpretation of nonlocal neighborhood filters for signal denoising. SIAM Journal on Imaging Sciences, 2(1):118-139) 2009.
Matthias Vestner, Zorah Lähner, Amit Boyarski, Or Litany, Ron Slossherg, Tal Remez, Emanuele Rodola, Alex Bronstein, Michael Bronstein, Ron Kimmel, et al. Efficient deformable shape correspondence via kernel matching. In 2017 International Conference on 3D Vision (3DV), pp. 517-526. IEEE, 2017a.
Matthias Vestner, Roee Litman, Emanuele Rodolà, Alex Bronstein, and Daniel Cremers. Product manifold filter: Non-rigid shape correspondence via kernel density estimation in the product space. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp- 3327-3336, 2017b.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv: 190e. 07 2019.
10

---

Under review as a conference paper at ICLR 2020
Dataset
Users
Items
Features
Ratings
Density
Rating levels
Flixster
3, 000
3, 000
Users/Items
26, 173
0.0029
0.5, 1
Douban
3, 000
3, 000
Users
136, 891
0.0152
1,2, ..2.....
MovieLens-100K
943
1, 682
Users/Items
100, 000
0.0630
1, ,,..
MovieLLens-MM
6, 040
3, 706
Users/Items
1, 0000 209
0.0447
Synthetic Netflix
150
200
Users/Items
4500
0.15
1...5
Synthetic ML-100K
943
1, 682
Users/Items
100, 000
0.0630
1,2,...,
Table 4: Number users, items and ratings for Flixster, Douban, Movielens- 100K, Movielens- 1M, Synthetic Netflix and Synthetic Movielens- Novielens-100K datasets used in our experiments and their respective rating density and rating levels.
TTee ratings valued.
Yin Zheng, Bangsheng Tang, Wenkui Ding, and Hanning Zhou. A neural autoregressive approach collaborative filtering. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 764-773, New York, New York, USA, 20-22 Jun 2016. PMLR. URL http://proceeddings wrwss v48/ zheng
A APPENDIX
A.I
SPECTRAL SELECTION
Here we shall prove that is enough to choose the weights wp.g in such that each p or q appears only once. For simplicity shall assume Pmax Imax and that Pskip Qakip (see Section 4
Proposition 1. Let W denote the matrix of weights used in p
and assume that they satisfy
Wp.a Σ
1,
Σ Wp. = 1, Wp. 2 0.
(17)
p=1
Then it is always possible choose weights ap.q 1) achieving, for the same optimal variables, a value of (0) 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 1T with some weights W.
Then for the same optimal variables, one can find weights A achieving value of (9) (and conse- quently, of (T0)) which is at least as low as the one obtained with W, by solving
A1
=1
A" = arg min
Σ CP" C", Q*) s.t.
A
= 1 1
(18)
A
2 0.
Problem 18 is a linear assignment problem and therefore has an integral solution dp.9 (Schrijver 1998).
{0,
11

---

Under review as a conference paper at ICLR 2020
kaming rate
5 10 5
5 10
5X 10
5 10
1x 10 10-4
1x 10-4
5x 10
5x 10
5X 10
6x 10-6
2 10
5X 10
5X 10-5
3x 10 10-7
3/- P.C,Q 1x 10-5
8x 10-5
9x 10
2x 10
5 10 10
2
Table 5: Hyper-parameter settings for the algorithms: DMF, SGMC and SGMC-Z, reported in Tables 2
Triinabee varrables
P,C,Q
C
P.C
P,C
P.C.Q
P,C,Q
P,C
P.C,Q
P.C,Q
P.C,Q
P.C.Q.
P.C,Q
P.C.Q
P.C.Q
P,C,Q
P.C
P,C,Q
-/- P,C,Q
P.C
0r/0c
-/-
-/-
-/-
-/-
-/-
1/-
-/-
-/-
0.001/
0.001/0
-/-
-/-
0.09/0.09
-/-
-/-
Pr Pr/Pe
-/2
0.1/
-/- 0.1/0.1
/0.0001
-/- 0.0001
0.0001/
0.001/
0.0011
0.004/0
-/- /0.0001
0.0001/0.000)
0.2/0.2
3/C
-/-
00.009
0.009/0 00.009
0.009 0.009/0.000
0.0001
pr. Me
-/-
0.4/0.4
0.001/0.001
0.4/0.4
-/-
0.0001 /0. 0000
00.0225
0.011 1/
-/-
00.0003
0..3/0.03
-/-
/0.0001
-/-
0.001/0.001
0.0001/
0.0025
0.001
0.0003 1.0003/0.0000
/0.00000000
0.001/0.000
0.0025 0.0025/0.000
0.0001
Pakip Uskip
7
1/1
-/-
3/1
-/-
/
2/2
20/20 22
50 50/100 1000
-/-
30, 30/35 35
-
-/-
-/-
3/1
20
Pmax /qmax
200 200
200 /200
20 /2
500 500/500 500
3000
3000/300 3000
200 /20
3000/ /3000
200 200 200
DMF 3000 /300
2500/ 2500
1000/ 1000/1000 1000
DMF 2000/ 2000
4000/ /4000
3200/ /3000
DMF 7000 77000
7000/ 7000
/8000
600 /60
500 500
3000
8000
Method
DMF
FM
SGMC
SGMC-Z
DMF
SGMC
SGMC-Z
SGMC
SGMC-Z
SGMC
SGMC-Z
SGMC
SGMC-Z
SGMC
DMF
SGMC
SGMC-Z
(users only)
Synthetic Netflix
ML-100K
Synthetic ML-100K
Dataset
Flixster
Flixster
Douban
ML-1M
12

---

Under review as a conference paper at ICLR 2020
RMSE vs P/Pe
RMSE vs 1 11/l4c
0.9128
0.98
0.91275
RMSE
0.96
RMSE
0.9127
0.94
0.91265
0.92
0.9126
0.91255
0.9
0.002
0.004
0.006
0.008
0.01
0.9125
0.2
0.4
0.8
0.8
1/11/
9/9
x10
Ablating = Pe and 14, = of SGMC on the MI.100K dataset. The rest of the parameters were to the ones reported in Table|5 Green denotes the baseline from Table [
Figure 2:
RMSE n/PP
RMSE vs p.Pe
0.9175
0.91456
0.917
0.91454
RMSE
0.9165
RMSE
0.91452
0.916
0.9145
0.955
0.91448
0.9150
0.01
0.02
0.08
0.04
0.05
0.01
0.02
0.03
0.04
0.05
4/4
0/0c
Figure 3: Ablating Pr. Pe and Hy He of SGMC-Z on the ML-100K dataset. The rest of the parameters were set to the ones reported in Table 5
RMSE P Pmax's maxx
RMSE vs p /q
0.95
max max
0.94
0.94
RMSE
RMSE
0.93
0.93
0.92
0
2000
4000
6000
8000
10000
0.92
max / max
Pmxx m
Figure 4: Effect of overparametrizatton: SGMC (left) and DMF (right). x-axis indicates the values of Pmaa Jmaxx and y-axis presents the RMSE. Green X denotes the baseline from Table [
13

---

Under review as a conference paper at ICLR 2020
Synth ML-100K
(M
200
100
Users
400
(M))
600
800
500
1000
1500
10
10
102
10
Items
index
Figure 5: Synthetic Movielens- 100k. Top-left: Full matrix. Top-right: singular values of the full matrix. Bottom left & right: items & users graph. Both graphs are constructed using 10 nearest. neighbors.
(M)
Synth Netflix
100
Users
50
a(M)
100
150
100 Items
150
200
10
10 index
102
Figure 6: Synthetic Netflix. Top-left: Full matrix. Top-right: singular values of the full matrix.
Bottom left & right: items & users graph. Taken from (Monti al. 2017)
14

---

Under review as a conference paper at ICLR 2020
synthetic Netflix
ML100K
reconstruction error
reconstruction error
0.94
0.2
*DMF @SGMC
SGMC
0.93
0.1
0.92
00
0.91
10
10.0.5
10-1
10
10
10.2.5
10
10.9.5
10
10
10
10.25
Figure 7: Reconstruction error (on the test set) scale of initialization. For each method initialized P. Q with al. SGMC consistently outperforms DMF for any initialization.
synthetic Netflix (variant)
synthetic Netflix (variant)
reconstruction error
reconstruction error
*DDMF
DMF
@SGM
1
SGMC
1
1
10-43
10
5
5%
10%
15%
20%
30%
rank
training set density
Figure 8: In these experiments we generated matrices using the synthetic Netflix graphs to test the dependence of SGMC and DMF on the rank and on the number of training samples. Left: Reconstruction error (on the test set) rank. As the rank increases, the reconstruction error increases, but it increases slower for SGMC than for DMF. For the training set we used 15% of the points chosen random (same training for all experiments). Right: Reconstruction error (on the test set) vs. size of the sampling set, for a random rank 10 matrix. As we increase the number of samples, the gap between DMF and SGMC reduces. Still, even when using 30% of the samples, SGMC performs better for the same number of iterations. In all experiments we used the following hyperparameters: /4 = He 0.001, Pr = Pc 0.001, maxiter 106.
15


Reviews:
[{"review_id": "SyxRPVxfqB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nWhile the geometric approach looks interesting and the experimental results seem promising, it is unclear why the proposed approach works, and the comparison with [Arora et al. (2019)] is not fair. Below are the specific comments.\n\n(1) The proposed approach (formulation (10)) involves too many parameters (including the weights w in (9)) that need to be tuned. The authors should discuss how to select the parameters after (10). This also raises the question of how practical the proposed approach is.\n\n(2) The authors claim the first contribution is to provide the geometric interpretation of deep matrix factorization via the functional maps framework. However, I didn't see clearly the interpretation. If it refers to the parametrization of X by \\Phi P C Q^T \\Psi^T, then it is just a special case of deep matrix factorization since both \\Phi and \\Psi are fixed, and P and Q are optimized to be approximately orthonormal.\n\n(3) Due to over-parameterization, in general deep matrix factorization would suffer from overfitting. That being said [Gunasekar et al. (2017), Arora et al. (2019)] prove that gradient descent induces implicit regularization if the algorithm is initialized with factors that are very \"small\". However, in the experiments, both P and Q are initialized as the identity, which is not close to zero. Indeed, it was proved in the following paper that the generalization gap will be proportional to the energy of the initialization, even for matrix factorization.\n\nYuanzhi Li, Tengyu Ma, and Hongyang Zhang, Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations.\n\n(4) As a followup question, without such implicit regularization, it is unclear why the proposed approach does not suffer from overfitting. A discussion along this line is required. Though the authors include the connection between [Arora et al. (2019)], this is not convincing enough since as explained above, the implicit regularization there depends on the smallness of the initialization.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlk4jujYB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThis work can be a significant contribution as it is a simple linear model but practically performs better than other deep nonlinear networks (e.g., RGCNN). Additionally, the proposed loss functions utilize only the spectral information of graph structure with novel approaches. However, there are some drawbacks to this work. First, it requires a good quality of geometric model which is hard to obtain in practical datasets. Second, the proposed method has a scalability issue since it requires eigendecompositions of graph Laplacians (as discussed in the paper). This can be a problem for real and large-scale datasets.\n\nOverall, this paper presents a novel approach utilizing graph spectral information with empirical improvements. But, I vote for weak acceptance due to its drawbacks as mentioned above.\n\nMain concerns:\n\n1. It is not clear why minimizing Dirichlet energy can improve the performance of matrix completion. In the paper, the authors mention that it promotes smooth functions on the graph nodes, but not fully clear why smooth functions are good. And how much does the accuracy increase (or decrease) when using the Dirichlet regularization? \n\n2. Authors argue that the re-parameterizing of the basis (emerging P and Q) can find a better geometric model (section 2). So, it is expected that the proposed method shows a better result when the given geometric model is not accurate. However, the empirical results are reported poor improvements for inaccurate geometric models. Does this make sense?\n\nFor experiments:\n\n1. What is the number of trainable parameters for each method? Since the proposed method is overparameterized, it is not clear that the empirical improvements come from the overparameterizing or the proposed loss function. It would be great to report the number of parameters of all other methods by setting similar numbers.\n\n2. It is not clear how to generate the synthetic dataset, i.e., projecting a random matrix on te the first few eigenvectors of L_r and L_c. It would be better to give more details.\n\n3. What are the training times of the proposed method and other competitors?\n\n4. Why results of FM are not reported under other datasets?\n\nMinor comments:\n\n1. In page 4, please edit “We explore The” -> “We explore the”.\n\n2. In equation (15), writing “\\odot S” twice seems to be unnecessary.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HJgg1pKRtB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new method for geometric matrix completion based on functional maps. The proposed algorithm is a simple shallow and fully linear network. Experimental results demonstrate the effectiveness of the proposed method. \n\nThe proposed method is new and has been shown good empirical results. The paper also points out a new way to interpret matrix completion. On the other hand, the proposed method seems ad hoc and there is no clear evidence why it is better than other baselines except the empirical results. The paper also has some clearance issues, making it hard to understand. I vote for a weak reject of the paper at the current pace and would like to increase my score if the following questions can be clearly answered.\n\n1.\tWhy do we need to propose the algorithm? Is it because we have the functional maps technique motivated from shape correspondence, and we can see some connection of such technique with matric completion? If it is true, we surely can have a new algorithm based on such a new technique. But I can still not understand why the method work, at least, in an intuitive way.\n2.\tWhat is the sample complexity of the proposed matrix completion algorithm? \nThe introduction of the paper is poorly written. The first paragraph and the third one both contain some introduction to matric completion, which results in a lot of redundant information. The second paragraph and the fourth one are redundant in the same way since they both focus on geometric matrix completion. I think besides introducing what is matrix completion and what is geometric completion, the introduction part should focus more on the motivation to propose the algorithm. However, I can only see from the end of the second paragraph (some simple models need to be proposed) and the fifth paragraph (“The inspiration of our paper”) some motivation information. The introduction part needs to be re-organized to provide more useful information about the paper rather than a literature review.\n\nThere is some unclear/inaccurate/subjective statement in the introduction part. For example, “Self-supervised learning” needs a reference. Why geometric matrix completion generalizes the standard deep learning approaches is not clear. What does it mean by “their design is … cumbersome and non-intuitive”? The shape correspondence is never explained until very later in the paper.  Also, there are some unclear issues besides the Introduction part. For example, what does it mean by “the product graph”? All these issues need to be clarified before the paper can be accepted. \n\n---------------------------------------------------\nThank you for the detailed rebuttal. For Q1, it clearly explains how does the method work. However, it is still not clear why does the method work. I also have another concern after reading the rebuttal, if the shape correspondence is not that important, why make it an important motivation in the paper? For Q2, it is interesting to see some theoretical results on the sample complexity, rather than an experimental one. The paper would also be much better if the clearance issues can be addressed. Even if I would not vote for an accept this time, I am looking forward to a revised version in the future.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a multiresolution spectral geometric loss called the zoomout loss to help with matrix completion, and show state-of-the-art results on several recommendation benchmarks, although experiments also show that the result improvements are not always dependent upon the geometric loss itself.
Reviewers find the idea interesting and the results promising but also have important concerns about the experiments not establishing how the approach truly works. Authors have clarified their explanations in the revisions and provided requested experiments (e.g., on the importance of the initialization size), however important reservations re. why the approach works are still not sufficiently addressed, and would require more iterations to fulfill the potential of this paper.
Therefore, we recommend rejection.
Decision: Reject