Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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.

While 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.

(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.

(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.

(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.

Yuanzhi Li, Tengyu Ma, and Hongyang Zhang, Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations.

(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.
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: 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. 

The 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.

1.	Why 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.
2.	What is the sample complexity of the proposed matrix completion algorithm? 
The 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.

There 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. 

---------------------------------------------------
Thank 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.

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: 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 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.

Overall, 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.

Main concerns:

1. 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? 

2. 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?

For experiments:

1. 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.

2. 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.

3. What are the training times of the proposed method and other competitors?

4. Why results of FM are not reported under other datasets?

Minor comments:

1. In page 4, please edit “We explore The” -> “We explore the”.

2. In equation (15), writing “\odot S” twice seems to be unnecessary.

review_title: Official Blind Review #2

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