Matrix Data Deep Decoder - Geometric Learning for Structured Data Completion
Authors: Maria Schmidt
Alexander Bronstein
Venue:  (2021)
Keywords: Deep learning
Non-Euclidean data completion
Sparse matrices
Recommender systems
Recommendation systems
Sparse representations

Abstract: In this work, we present a fully convolutional end to end method to reconstruct corrupted sparse matrices of Non-Euclidean data. The classic example for such matrices is recommender systems matrices where the rows/columns represent items/users and the entries are ratings. The method we present is inspired by the surprising and spectacular success of methods like$"$  deep image prior$"$  and $``$deep decoder$"$  for corrupted image completion. In sharp contrast to previous Matrix Completion methods wherein the latent matrix or its factors directly serve as the optimization variable, in the method we present, the matrix is parameterized as the weights of a graph neural network acting on a random noisy input. Then we are tuning the network parameters to get a result as close as possible to the initial sparse matrix (using its factors) getting that way state of the art matrix completion result. In addition to the conceptual simplicity of our method, which is just Non-Euclidean generalization of deep image priors, it holds fewer parameters than previously presented methods which makes the parameters more trackable and the method more computationally efficient and more applicable for the real-world tasks. The method also achieves state-of-the-art results for the matrix completion task on the classical benchmarks in the field. The method also surprisingly shows that untrained convolutional neural network can use a good prior not only for image completion but also for Matrix Completion when redefined for graphs.

Under review as a conference paper at ICLR 2021
MATRIX DATA DEEP DECODER GEOMETRIC LEARN- ING FOR STRUCTURED DATA COMPLETION
Anonymous authors Paper under double-blind review
ABSTRACT
In this work we present a fully convolutional end to end method to reconstruct corrupted sparse matrices of Non-Euclidean data.The classic example for such matrices is recommender systems matrices where the rows/columns represent items/users and the entries are ratings. The method we present is inspired by the surprising and spectacular success of methods like" deep image prior" and "deep decoder" for corrupted image completion. In sharp contrast to previous Matrix Completion methods wherein the latent matrix or its factors directly serve as the optimization variable, in the method we present, the matrix is parametrized as the weights of graph neural network acting on random noisy input. Then we are tuning the network parameters to get a result as close as possible to the initial sparse matrix (using it's factors) getting that way state of the art matrix completion result. In addition to the conceptual simplicity of our method, which is just -un-Euclddean generalization of deep image priors. it holds less parameters then previously presented methods which makes the parameters more trackable and the method more computationally efficient and more applicable for the real world tasks. The method also achieves state-of-the-arr results for the matrix com- pletion task on the classical benchmarks in the field, The method also surprisingly shows that untrained convolutional neural network can use a good prior not only for image completion but also for Matrix Completion when redefined for graphs.
INTRODUCTION
Matrix completion (MC) consists of estimating the missing entries of an n x m matrix X (usually, of very big dimensions) given its measurements M on (usually, very sparse) support Q. An example of such matrices are signals on graphs/manifolds which are Non-Euclidean domains. The classical example of such data are recommender (recommendation) systems, where the ratings signals on (user item) couple. The most known Matrix Completion problem is the Netflix problem, where a IM $ prize was offered for the algorithm that can best predict user ratings in a dataset that contained 480k movies x 18k users (8.5B entries), with 0.01 1111% % known entries (Bell et al. 2009).
Many works focused on solutions for the MC problem. In brief, one wishes obtain the matrix X given matrix M as the specified input on the support Q. Then, formally the completion task amounts to the minimization problem
X argmin Al (X -
where Ag is the observation mask matrix (filled with where data exists in the original problem), is the Hadamard product and ||- is the Frobenius norms (Rennie & Srebro 2005). Different approaches where presented in order to fill in matrix X. Those approached included imposing different regularization (priors) on the matrix and its factors. The most prominent approach consists of imposing a low rank (Candès & Recht 20099; Recht (009) on the matrix. Then, priors based
on collaborative filtering (users/items rating patterns), content based filtering (user/items profile) (Ghassemi et al. 20188) 1018.Jain Jain & Dhillon 2013 Xu et al.) 2013 Si et al. (016) and their combinations.
Then Geometric Matrix Completion approaches appeared (Li & Yeung) 2009 Rao et al. 2015 Cai
al. (011)) and proposed describing rows/column graphs which represent similarity. then encoding the structural (geometric) information of those graphs via graph Laplacian regularization (Belkin
& Parthal 2002. Belkin & Niyogi 2003) and imposing smoothness of the data in those graphs

---

Under review as a conference paper at ICLR 2021
Kalofolias et al. 2014 Rao al. 2015: Ma et al. 2011 Mardani et al. 2012). Those approaches where generally related to the field of signal processing as entries signals on the rows/columns graphs (Shuman et al. 2012). Then Geometric Deep Learning Methods where introduced to learn the domains of geometric data structures (e.g. single graphs or (Brofssstn)nnnnnteiii et al. 2016]
Lefkimmiatis 2016, Defferrard al.] 2016; Niepert
al. [2066] Gilmer 2017; Hamilton
et a [017]] Velickovic et al. 2017; Chen et al. 2018 W. Huang et al. 2018 Klicpera et al.) 2018
AAb--El-Hajj et 2019 Ying al. 2018 Gao et al. 2018 Hammond et al. 2011). The current
state of the art solution for Matrix completion problem, relies on an extending classical harmonic analysis methods to non- non-Euelidean domains. When, the geometry of the column/row spaces and their graphs is utilised to provide Geometric Deep Learning mechanism called the RMGCNN (Monti al. 2017) that includes complex combined CNN and RNN(Hochreiter Schmidhuber 1997 networks.
In this work we present simplified method for the MC problem: the Matrix Data Deep Decoder that contains a classical end end GRAPH convolutional neural network and inspired by the leading methods from the field of image completion the Deep Image Prior (Ulyanov et al. 2020) and the Deep Decoder (Heckel & Hand 2018). In our method, random noisy input matrix is acted upon by the weights neural network (parametrization). By tuning the parameters of the network and minimising the error between its output to the initial corrupted matrix, find the best candidate for the complete matrix. This method yields state of art results for the MC task. The contributions of our work are:
A novel approach for solving the MC Problem, using deep learning with end-to-end pure convolutional network for graphs
State-of-the-art performance for the MC problem in both prediction error (RMSE) and solution running time Our method significantly outperforms the previous state of art method the RMGCNN.
We show that a pure graph convolutional neural network is a good prior for the MC prob- lem. This provides correspondence of convolutionial neural networks methods to MC problems.
PRELIMINARIES
2.1 MATRIX COMPLETION NOTATION
The most prominent prior for the MC problem is assuming the matrix X of low rank. Low rank is obtained by rank regularization using its nuclear (trace) norm || sum of the singular values of X. The canonical optimization problem with parameter X,, is stated as:
X min | o
(X (X MI + 1XII.
2.1.1 MATRIX FACTORIZATION
To alleviate the computational burden for big datasets, we factorize X = W H", where W e Rmxk H R kxn Here, k < and n is the upper bound the rank of X. With this factorization, the nuclear norm term can be replaced by the sum of the Frobenius norms leading to the following non-convex (but still very well-behaved) problem (Rao et al. 2015):
X
min W. W.
| (WH" (OTT-M)IE 2
MI
d (IWI || 11
2.2 GEOMETRIC MATRIX COMPLETION
We introduce the geometric matrix completion framework, using notations as RMGCNN (Monti
al. 2017).
"vvlluated the existing classical benehmark for MC Problems
2

---

Under review as a conference paper at ICLR 2021
2.2.1 THE Row/COLUMN GRAPHS
The matrix X is comprised from signals non-euclidean domains of rows and columns. We rep- resent those domains by undirected weighted graphs 9, (c.g. items) and ge (c.g users) respectively, where: Gr/c (V, E, W). Gr/c built either directly from the ratings matrix X, based on additional data about the rows/columns (if given). Their structure is encoded Laplacian matri- which built from the adjacency matrices W r/cc (definitions are below). This procedure is sketched in figure below.
Figure 1: Example for matrix X and rows/columns graphs structures
2.2.2 THE ADJACENCY MATRIX:
For graph G = (V,E,W) the elements of its adjacency matrix (W);, = Waj obey: wi Wye, Wij 0 if (i,j) & E and wiy if (i,j) E E. The Adjacency Matrix represents the weights of the proximity between every two vertices and can be built based on the signal patterns external features about the rows/columns in methods like euclidean distance of normalized features, Chi square, Gaussian Kernel, K-nn clustering K-means clustering and etc.
2.2.3 THE GRAPH LAPLCIANS
The Laplacian matrices L, and Le are based on the adjacency matrices W and are holding inside the internal Graph Structure. The most common constructions of Laplacian matrix is an n matrix defined as L = D W. where D is degree matrix, n x n diagonal matrix (D)s = Ejfs Waj-
We adopt the Normalized Graph Laplacian definition as L D LD
D D
2.2.4 THE OPTIMIZATION PROBLEM
We use the graph laplacians in the optimization function as an additional prior regularizing the matrix completion problem. We'd like more similar items/users get more similar predictions. Math- ematically, regarding the columns æi...., for example as vector-valued function defined on the vertices Va, the smoothness assumption implies that æy As xy if (j.j') E E.- Stated differ- ently, we want the following entity (Trace norm Dirichlet semi-norm (Kalofolias et al., 2014)):
Ens wf, || =x,122 = tr (XL.x²) to be as small possible, leading to the following optimiza- tion problem:
x = argmin Pa (X
|X + X, (XT L, X) + No 1r L. xT).
which, if will look at the factorized model will equivalent to,
X
argmin WeRexk HT ERAMn
| (WHT- M) WH Il, +A, (W L.W) +he (HLL.H)
From this perspective, the estimation of the left and the right factors of X is considered diffusion of the input fields on the row and column graphs, respectively. This separable form allows no accommodation for the low rank constraint (which pertains the product of the graphs).
3

---

Under review as a conference paper at ICLR 2021
2.3 DEEP NEURAL NETWORKS
In the recent years, deep neural networks and, in particular, convolutional neural networks (CNNs) (Lecun al. 1998) based methods have been applied with great success to Image completion tasks. Such methods are based on one of the key properties of CNN architectures the ability to extract the important local stationary patterns of Euclidean data. Image completion with untrained networks (when only the corrupted image is the input with no other training examples) can be seen as parallel the "Matrix Completion" task. Two recent works, applying un-trained deep neural networks on corrupted images, showed state-of the art results for this task. We were inspired by those methods and our goal was generalize them to the Non-Euclides Domain.
2.3.1 DIP DEEP IMAGE PRIOR
The method suggests to feed the network with random input Z, forward pass the random input through the network and check how close the output to the corrupted image, while tuning the network parameters weights. This operation surprisingly reconstructs the clean image (see Ulyanov et al. 2020)).
2.3.2 DEEP DECODER
The Deep Decoder method showed results even better then the DIP (see Heckel & Hand (0118) The method proposed to take a small sample noise, and pass it through a network, while making some non-linear operations on it and up-sample, then check how far the result is from the corrupted image while fixing the network parameters. This method showed that a deep decoder network is a very concise image prior. The number of parameters it needs to completely specify that image is very small, providing a barrier for over-fittin fittifiting (catching only the most important image features (natural structures) and ignore noise) and allowing the network to be amenable to theoretical analysis.
2.4 GEOMETRIC DEEP LEARNING OR DEEP LEARNING ON GRAPHS
In contrast to image matrices, the notion of convolution and pooling for Non-Euclidean matrices needs to be re-defined to give the Non-Euclidean stracture the special meaning that convolutional networks are based When those operations redefined, we build "graph convolutional neural network" which is parallel to some classical neural network and find the estimate for X.
2.4.1 CONVOLUTION FOR GRAPHI
To perform meaningful convolution operation keeping the operation translation invariant, we perform spectral graph convolution with spectral graph filters. The spectral graph theory suggest that spectral filters on matrix Z can be well approximated by smooth filters in form of truncated expansion in terms of Chebyshev polynomials T3 upon the rows/columns graph Laplacians (Á) up to some pre-defined order K (Defferrard et al. 2016). The coefficients of those polynomials 9 are the network parameters that we learn. Using that filter approximation, we can define the Single Graph Convolution operation of a signal matrix Z with filter y:
SINGLE GRAPH CONVOLUTION:
K Σ
+
T
P Z
FULL MULTI GRAPH CONVOLUTION: In RMGCNN the authors propose that when Matrix in- cludes signals on product of two graphs (rows/columns graph) Multi-Graph convolution is used. Full Multi Graph convolution is suitable for small matrices. When we pass signal matrix Z through a graph convolutional network layers, the output matrix after the convolution operation of matrix Z layer I with each filter q and after adding the bios parameters 3q (j, j' are the degree of the Chebyshev polynomials of the rows and columns on filters of layer l):
0 O3 II (Am) Zi T. (Aci) + :9q
Ż1, = Zi Bq =
Σ 3.8
4

---

Under review as a conference paper at ICLR 2021
FACTORIZED MULTI GRAPH CONVOLUTION: Factorized Graph convolution is used to alleviate the computational burden for big signal matrices, using matrix factorization and then performing each of the factors (proposed in Bruna et al. (0144); Monti et al. (2177; : Kipf & Welling (2016); Henaff et al. (213)). It can be done in different Matrix Factoriza- tion techniques (Cabral et al. 2013] Chi al. 20188 Zhu al.; 2018). In this model, the matrix decomposed to it's factors with SVD: Zq W WqHqg After factorizing, to get the full Multi- dimensional signal we pass each factor through the network separately and only then multiply back to get the full cialiiddieesionall signal. The convolution for each factor is a Single-Graph convo- lution each of the W and H matrices:
Single Graph convolutions
P
P Ar Wa + -Ba). H H₂ - Σ (0,TT f0m
W
q
Σ J=0
O,T,
(O, (Ac) Ha Bcq
2.4.2 POOLING FOR GRAPHS
When we talk about graph pooling we talk about reducing the graph resolution grid (zoom-out operation). In our work the graph pooling is done in two steps, those steps are described below:
STEP 1: GRAPH COARSENING PROCESS (DIILLON ET AL. 2007; KARYPIS & KUMAR 1999:
SHI & MALIK 2000)- We do bi- birpattition of the Graph G, to form clusters of couples. At each coarsening level, pick an unmarked vertex and match it with one of its unmarked neighbors that maximizes the local normalized cut Way Ag Asg (A is graph adjacency matrix and D is Da + Dajj
graph degree matrix). Then we mark the clasters as the vertices of the next level coarsened graph. The edge weight on this coarsened graph are set as the sum of the weights of the edges that connect the vertices between the clusters as described in figure 2
0
2
2
2
3
2
12
12
Figure Graph coarsening and edge weighs assignment for the coarsened Graph
STEP 2: GRAPH POOLING / DOWN SAMPLING STRUCTURES SAVING- Defferrard et al. (2016) suggest save the coarsening structure of the previous step in balanced binary tree for both row/column graphs. Practically, for each row/column graph, on each layer I, we save in matrices Uni Ua which vertices where down sampled from which parent vertices in the previous layer. We rearrange the vertices of each adjacency matrix on each level according to this tree order, and use those matrices to constract the graph Laplacians i.e År, and Åc, for each network level.
2.5 UP-SAMPLING FOR GRAPHS
The up-sampling operation is done by multiplying the signal matrices 2, by the parent indicators matrices UnL Ual resulting in a Z level matrix where the row/column parents of a specific "child" get linear combination of its children values. We will denote this operation as:
2
Upsample
(1)
UniZU
In the factorized case, matrices H and W are up sampled separately in the same method W H and then multiplied to get Z W44 H
Upsample (i)). Hit1 Upsample
THE MATRIX DATA DEEP DECODER METHOD
In this section present method, the Matrix Data Deep Decoder. The core idea of our approach was to take the state of the art untrained learning model for image completion "deep decoder" and "translate" its network it would feet for Matrix completion.
5

---

Under review as a conference paper at ICLR 2021
3.1 NETWORK PREPERATION
1. Input corrupted m x n rating matrix M and Ag observation mask.
2. Input the hyper parameters: Ir learning rates, L number of layers (1 the smallest down sampled År,, Act), Prl/Pel- the degree of row/column Chebyshev polynomials on layer (i.e: the number of neighbours we' d like to consider on each layer) and finally qi = 91....:92 -9. number of neurons each layer 1. Each nueron learns Prl Pel coefficients of the Chebyshev polynoomials of the row/column Laplacians.
3. Build Initial row/cols graph adjecency matrices (Ar Act., based on: M, row/columns properties and selected distance function (we used the threshold clustering: for every cou- ple of rows/columns, saving the Euclidean distance between their attributes only if it is smaller then threshold R. otherwise O. Alternatively, for specific data combinations of rating patters and user/item attributes can taken as featurs.)
4. Build Initial row/cols normalized graph Laplacians (ÅrI, Δci) based on (Arl, ACL)
5. For each = I,...I for each rows/col graph adjacency matrices do:
(A:), (Ai) 5.1. Build the rows/cols coarsed edge weights matrix (Wi);s = (D:). (D)),s
A; is the graph adjacency matrix and D; is the graph degree matrix.
5.2. Cluster couple of every two closest vertices to Wi distance and enumerate the clusters the
new graph vertices in pooling matrices Ur, Uc:
5.3. Build reduced adjacency matrices Art, Aci when the matrix instances (edges weights) are the sum if the distances between the clusters members in matrix W: as described in figure and rearrange in the order of Ur., Uc.
5.4. Build row/cols normalized graph Laplacians (Arr, de)) based on Art. Ae
6. Take matrix Z in the size of (Ar Aci) and input (infuse) random noise in it.
3.2 NETWORK LEARNING PROCESS ALGORITHMS
Algorithm (MDDD)
Algorithon 2 (sMDDD)
For 1 T do:
For 0 T: do:
Nenwork Learning process Forward pass:
Network Learning process Forward pass:
1. For è 1: L 1 (las layer with the smallest årG, Acg) doc
1. for 1: da
perjorm for matrix Ze Full Graph convolution:
Zz SVD W. (rows) Hy (cols.)
1.2 perform Hactorined Multi- comvouutin::
2,
Σ 0 B..' T3 (āre) žeTTy (des) Bh
W. Ed By.TT (āre) We + BE, E7L E 0g,22 (Ber) He 8x
Vet
Pet
Apply ReLu non- mon- lincarity: W, + (W.). H, + (H.)
1.2 Apply ReLu non linearit:: + (2:)
We11 - Lipsample (We). Weil Upocmple (Hc)
1.3 Zo45 Upsample ssc. 2.5)
End for
End
Pas through Fully Comnected Layer (Bwte Onso have Wr. Hy, stages) 9wro H, OntoH,, Baso 4. Nommalaa:: 2r, Sigmoid (W.H.)
Normalize: Z2 Sigmoid (22)
W, + Owro
Nenwork Back ward Pass:
4. Update the parameters and B for all layers with gradient descent, minimiie the loss between Lg and the obsrrved M:
Network Backward ward Pass:
Update parameters (8, layers gradient to minamize
8. argmin || Aa (2I-.)ll? R
8.
argmin
|| (Ze (0-M) M) I1-- (2z)
e cigm
R (2:) A. 12.ll. + t (2. 2c) + Noto (2, 27.
12 (2:)
2 || + 2.1r (W år,,
Wr. Wt) 2nte (H Se,, H.))
T (X, M)
To o (X, M)
S. RMRE, =\
Test ubes vationationnnoomm unsk)
Eng Fi.
6. RMSE,
Exs Tei &, where RMSE, is smallest
iTe-iest observation mask)
End For Retum matrix X X, where RMSEE is smallest
End For. Return matrix
3.3 STOPPING CRITERIA
In this work we run the algorithm for each set for T=10000 iterations in RMGCNN. We the Iteration weights on which we' 'e obtained the best RMSE for the test set. Thus, the number of iterations is another hyper parameter that should be tuned for best performance.

---

Under review as a conference paper at ICLR 2021
fiiters Py Size
91 Pr P, Size
Convolve
1.Convolve
W
2. Upppsmppee
3. UpSample
fitees
Tu P: P. Size
Signoodd (2.)
P. P.
FC(
Stggmnnd (R,R,
1.Corvolve
Convolve
ReLu
3. UpSample
3. UpSample
Figure 3: Network Structure Illustration - MDDD algorithm flow scatch
4 EXPERIMENTAL RESULTS
Up to date, the state of art results for Matrix Completion where obtained by the RMGCNN method, hence, in the experimental results we compare our results to are the results of the RMGCNN. The information about the other methods was taken from the RMGCNN work and can be found in the work of [30]. Our tested datasets started with a small simple synthetic dataset Synthetic Netflix. Then we have continued by evaluating our method on real banchmark datasets: MovieLens 100k, Flixster, Douban and YahooMusic following Monti et al. (2017). The tested datasets statistics described in table below:
Table I: Datasets Statistics.
"Graphs" cropphssroows/oolmms availability for graphs construction
Dalaset
#Users
#ltems
Graphe
ARadings
Donsity
Rating levels
ML-100K
1682
Users/Ttems
100,000
0.0630
2,
Douban
3000
3000
Users
136,891
0.0152
1, 2, "
Plixster
3000
Users/Items
26,173
0.0029
0.5, 1, "
YahooMusic
3000
3000
Items
5,335
0,0006
1, "", 100
4.1 BENCHMARK RESULTS ON THE TESTED DATASETS
In this section we describe the data preparation parameters of the MDDD method for all tested datasets and then present summerizing tables the Results compared other known methods.
THE NETFLIX CHALLANGE- On the Synthetic Netflix dataset we tested both, the Non- Non-Factorised and the factosised algorithms. In MDDD we used row degree 1,column degree 5. The graphs where constructed using 10 nearest neighbours. Our Non-Fuctorised MDDD model achieved the best accuracy, followed by our Factorised MDDD model as described in table3 (a) below.
THE MOVIELENS, FLIXTER, DOUBAN AND YAHOOMUSIC CHALLENGE- For the real datasets, Movielens 100k, Flixter, Douban and YahooMusic the network was prepared as following: For all datasets only the MDDD Factorised model was used, due to the big datasets size. In all settings learning rate was set to 0.01. and fully connected layer was used to translate the rows and columns embedding to the Ratings space. For all datasets the training and tests where taken exactly as in Monti et al. (2017). For the Movielens_100 100k Dataset (the most familiar benchmark dataset), the rows/column graphs where built using the threshold method described in section 3.2.2. The network had 2-layers with 32 filters on each layer and filter size of 3x3. For all other datasets, we have used the same graphs that were used in the RMGCNN work [30]. As for the YahooMusic/Douban datasets only columns or rows features were available respectively (tracks fatures or users features), to build the missing Graphs for those databasets we used the training set of the corrupted matrix with 10-nn neighbors. For example for Douban, we have used 7.5% of the ratings that we' ve marked as the training set. In the Douban dataset, we used a 2-layer network, with 64 filters on each layer, of size 2x2. In the Flixter dataset, used deeper network of layers (64.64.32,32) filters each with filter sizes of 1x1,x00,1xx,,xxx on each layer. Table 2 summarizes the performance of different methods compared to MDDD.

---

Under review as a conference paper at ICLR 2021
Table 2: Performance (RMS error) comperisson
(a) Comparison of different matrix completion meth- ods on Synthetic Netfilix in terms of number of pa- rameters (optimization variables) and computational complexity order (operations per iteration). Right- most column shows the RMS error on Synthetic dataset.
(b) Performance (RMSE) of different matrix comple- tion methods on the MovieLens 100k dataset. We got the best results with a 2-layer network when each layer had 64 parameters; the 1st layer had 1xl filters and the 2nd 40x40.
METIOD
RMSE
PAUARELL
CONTIDIIY
RMSE
MEAN
1:154
0.3593
USEN MEAN
1.063
GRALS
in n
/1 1
0.0114
Movs Mav
MC (CaMrEN R. Remm, 2012)
0.973
1.033
RGCNN
0.0053
IMC (JAIN & DIILON, 2013; Xu IT Al., 2013)
1.653
SRGCNN
0.0106
GMC
2014)
0.996
MDDD (Factorized)
0.0017
GRALS (RACEE AL., 2015)
0.945
0.929
MDDD (Multi-Graph)
0.0004
MDDD
0.922
(c) Performance (RMSE) Douban, Flixster/Fliter-UU (when only users Graph Ex- ists) and YahooMusic with only ratings Graph. Other baselines are taken from 32
METaOn
DOUMNN
Fuxster/Fllyter U
YManoMusic
ME
0.845
1.533/ 1.534
52.0
GRALS
0.833
1.313/ 1.243
38.0
GC-MC
0.734
0.917/ 0,941
20.5
SRMGCNN
0,801
1.179/ 0.926
22.4
MDDD
0.733
0.893
20.2
4.2 RESULTS DISCUSSION
For the Synthetic Netflix dataset our Non-Fuctorised MDDD model achieves the best accuracy, followed by our Factorised MDDD model (table 2 (a)) For the real datasets (Movielens, Flixter, Douban and YahooMusic). MDDD (the Factorized Model) outperforms the competitors (Monti et al. 2017 Rao et al. 2015 Yao & Li 2018) in all the experiments (table 2 (b).(c) Our algorithm also gets the result much less running For example On the Movielens dataset our algorithm converges after 1800 Iterations, compared to 25, 25,000 in RMGCNN algorithm ( minutes compared to 30 minutes- (table 2 (b))). The algorithm has shown an improvement in state of the art result in 7%, and can be farther improved (appendix A and B) but most importantly, we got the results very quickly. We consider the reason for that the model simplicity and the small amount of parameters that make it easier for the algorithm to first re-construct the natural graph structures, then the noise.
CONCLUSIONS
In this work addressed the problem of Matrix Completion Non-Euclident domains, where sparse signal, which lies on a grid of two non- Euclidean domains (Graphs or manifolds), should be completed. We introduced a new method for the Matrix Completion Problem solution: The Ma- trix Data Deep Decoder- a simple, intuitive under-parametrized yet powerful method for Matrix Completion inspired by the Deep Decoder method for Image Completion. As far as we know this is the 1st method for non-Euclidean matrix data completion that is end to end based on fully con- volutional network. Despite it's simplicity the method shows state of art results on current known benchmarks in both predictions error ( 77% improvement) and runnig time in 6 times faster). Be- cause of the method simplicity, it can be applicable in variety of fields and real life problems like recommendations systems (the Netflix Problem), pattern recognition, community detection Biologi- cal consequences on gene data or DNA structure, Chemical reactions, Physical applications, Events prediction, traffic detection, stocks prediction and many more. It also be expended to higher dimensional spaces like tensors instead of matrices and new research directions (appendix A and B).
Our method can suggest that when we are looking at the problem of Matrix Completion from the ge- ometric point of view (as sparse signal that lies on underlying rows/columns or their product graphs structures), convolutional neural networks future research and applications it means a continuous improvement in the field of Non-Euclic Euclidean learning networks, in parallel to the improvement in the field of the classical learning networks.
very strong prior for that problem solution. For
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sami -bu-aa-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyumyan. Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolu- tional architectures via sparsified neighborhood mixing. CoRR, abs/1905.00067, 2019. URL
httt:://arxiv.org//bbb. 00077
M. Belkin and Niyogi. Laplacian eigenmmps for dimensionality reduction and data representation. Neural Computation, 15(6):1333-1366 2003.
Mikhail Belkin and Niyogi Partha. niques for embedding and clustering. In T. G. Dietterich, S. Becker, and
Laplacian eigenmaps and spectral tech-
Z. Ghahramani (eds.). Advances in Neural Information Processing Systems
pp. 585-591. MIT Press, 2002. URL http::/ . nips. cct cctppppppe
pdf
R. M. Bell, Bennett, Y. Koren, and C. Volinsky. The million dollar programming prize. IEEE Spectrum, 46(5):28-33, 2009.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Ge- ometric deep learning: going beyond euclidean data. CoRR, abs/1611.08097, 2016. URL
hittp://arxle www.or///aa....... hat//bb//// /wtes//6l.... 1611.08097
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. international conference learning representations, 2014.
R. Cabral, De la Torre, Costeira, and A. Bernardino. Unifying nuclear norm and bilinear fac- torization approaches for low-rank matrix decomposition. In 2013 IEEE International Conference on Computer Vision, pp. 2488-24993 2013.
D. Cai, X. He, J. Han, and T. S. Huang. Graph regularized nonnegative matrix factorization for data representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(8); 1548-1560, 2011.
Emmanuel J. Candès and Benjamin Recht. Exact maact via convex optimization. CoRR, abs/0805.4471, 2009. httpppp//aaaxt....rraaaa//......
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. ICML., pp. 941-949 2018.
Yuejie Chi, Yue M. Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factoriza- tion: An overview. CoRR, hts/1809.09573. 2018. URL BtKLLattpp///x...oo/////b///
09573
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. CoRR, abs/1606.09375, 2016. URL http:
09375
Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvectors: A multilevel approach. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 29(0), nov 2007.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Lcrge-scale learnable graph convolutional networks. CORR, abs/1808. 03965,
03965
M. Ghassemi, A. Sarwate, and N. Goela. Global optimality in inductive matrix completion. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp- 2226-2230, 2018
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley. Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. CoRR, abs/ 100.00124..21,, 2017. URL httl:://p///xx org/abs/ 01212

---

Under review as a conference paper at ICLR 2021
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. CoRR, htss/1066002166. 2017.
02216
David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2): March 2011. 1. doi: 10. 10.1016/j.ach..222 www.jaacaa.220.0...m.m 2010.04.005. https:/ itaraaiiiiiieiiiieeeeaa
Reinhard Heckel and Paul Hand. Deep decoder: Concise image representations from untrained non- convolutional networks. CoRR, abs/1810.03392,, 2018. URL http: org/ abs/
1810.03980
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. CoRR,
2015. URL http:://aar.....rr/////////66660
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Wilffiid Imrich and S Klavzar. Product Graphs, Structure and Recognition. 01 2000.
Prateek Jain and Inderjit S. Dhillon. Provable inductive matrix complction. CoRR, abs/ abs//130.0066, 2013.
1306. C626
Vassilis Kalofolias, Xavier Bresson, Michael M. Bronstein, and Pierr Vandergheynst. Matrix com- pletion graphs. CoRR, abs/1408. 1717, 2014. URL http:::/aarxww.orr//bbbsaa
1717
G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partition- ing irregular graphs SIAM Journal on Scientific Computing, 20(1):359, 1999. URL
com ottp.e....c..co.........aeei..o. 2a0
scholar.goog com/ ottp:///www..oooo..a.a.aaaaoaaaa _dt=0,, 54as_
lact=citationscde
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. CoRR, abs/1609.02207,, 2016.
abs 1609.6699.00 wttp:///aa//10.0022220
Johannes Kliepera, Aleksandar Bojehevski, and Stephan Günnemann. Personalized embed- ding propagation: Combining neural networks on graphs with personalized pagerank. CoRR, abs/1810.05997, 2018. htt.fitpp://axl..orgg//////
05997]
Y. Lecun, I.. Bottou, Bengio, and P. Haffner. Gradient-based learning applied to document recog- nition. Proceedings of the IEEE, 86 36(11):2778-2344 1998.
Stamatios Lefkimmiatis. Non-local color image denoising with convolutional neural networks. CoRR, abs/1611.06757, 2016. / wttp://///......111111111
Wu-Jun Li and Dit- Ran Yeung. Relation regularized matrix factorization. pp. 1126 1131, 01 2009.
Hsueh-Ti Ti Derek Liu, Alec Jacobson, and Maks Ovsjanikov. Spectral coarsening of geometric oper-
ators. CoRR, 0ts/1995.05161 2019. http::///////iii..otmm http://axxxi..oorra///////////// 05161
Hao Ma. Denny Zhou, Chao Liu, Michael R. Lyu, and Irwin King. Recommender systems with social regularization. In WSDM '1I Proceedings of the fourth ACM international conference on Web search and data mining, WSDM 11, pp. 287-299 296. ACM Press, 2011. ISBN 978- 1-450-- 0493-1. URL https: www mi wrosoft cot.ttt.cco/eeeee.ee recommender- sws-emstteessss
M. Mardani, G. Mateos, and G. B. Giannakis. Distributed nuclear norm minimization for matrix completion. In 2012 IEEE 13th International Workshop Signal Processing Advances in Wire- less Communications (SPAWC), pp. 354-358, 2012.
Federico Monti, Michael M. Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi graph neural networks. CoRR, Abs/1704,,,803, 2017. URL /tttp://aaaat prg/abs//77m 06803
10

---

Under review as a conference paper at ICLR 2021
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. CoRR, abs/1660500527,, 2016. URL http::/aaxiv.ooo///aaaaaaa
05273
Guillermo Ortiz-Jiménez, Mario Coutino, Sundeep Prabhakar Chepuri, and Geert Leus. Sampling and reconstruction of signals on product graphs, 2018.
Nikhil Rao, Hsiang-Fu Yu, Pradeep K Ravikumar, and Inderjit S Dhillon. Collaborative filtering with graph information: Consistency and scalable methods. In C. Cortes, N. D. Lawrence, D. D.
Lee, M. Sugiyama, and Garnett (eds.), Advances in Neural Information Processing Systems 28, nips oag.op/..ocouoo.........aaaaaaar
pp. 2107-2115. Curran Associates, Inc., 2015. URL http: pttppppppss.nissscppppppprperrre
pdf
Benjamin Recht. A simpler approach to matrix completion. CoRR, abs/0910.0651, 2009. URL
http://arxiva http:://rx.w.orr//abbbb///// wtt.:ogggabb///110 0910.0661
Jasson D. M. Rennie and Nathan Srebro. Fast maximum margin matrix factorization for collab- orative prediction. In ICML '05: Proceedings of the 22nd international conference on Ma-
chine learning, pp. 713-719, New York. NY, USA, 2005. ACM. ISBN 1-59593-180-5. doi:
Jianbo Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 22(8):888-900 2000. ISSN 0162-8828. doi: 00.100933.8666888
David I. Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. Signal processing graphs: Extending digh-dimensional data analysis to networks and other ir- regular data domains. CoRR, abs/1211.008 2012. URL http:httt:/xxttt wwtp://wwrrg/bb//////e/
0053
Si Si, Kai-Yang Chiang, Cho-Jui Hsieh, Nikhil Rao, and Inderjit S. Dhillon. Goal-directed induc- tive matrix completion. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 16, pp. 1165-1174, New York, NY, USA. 2016. Association for Computing Machinery, ISBN 978 4781450342322. doi: 10.11457293967222999699
URL httpp::///o...rg//11.... htt.:///....11/9999111 2tt.55222233772229998333
Dmitry Ulyanov, Andrea Vedaldi, and Victor S. Lempitsky. Deep image prior. International Journal of Computer Vision (IJCV), 128(7):1867-1888 2020.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li, and Yoshua Bengio. Graph attention networks, 2017.
Tong Zhang W. Huang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph rep- resentation learning. CoRR, 0bs//880905..3 2018. URL htl.:ttp://aarii.or//aa///////
05343
Miao Xu, Rong Jin, and Zhi-Hua Zhou. Speedup matrix completion with side information: Appli- cation to multi-label learning. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q Weinberger (eds.). ), NIPS, pp. 2301 -3099 2013. /tR. ba//bb/cc http://onn//ppssmmps//.....
html #XuJø13
Kai-Lang Yao and Wu-Jun Li. Convolutional geometric matrix completion. CoRR, abs/ 1803.00754, 2018.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. CoRR, abs/ 806.01996.. 2018. URL httphhtt::/aaae org abtp//bbs/188 180..019733331331
Z. Zhu, Q. Li, G. Tang, and M. B. Wakin. Global optimality in low-rank matrix optimization. 1EEE Transactions on Signal Processing, (6(13)366443666 2018.

---

Under review as a conference paper at ICLR 2021
A APPENDIX A
FUTURE WORK In this work we have presented the results of the described method that was the basis for in order to get new state of the art results. But, do believe that the results can be farther improved by the following future research tuning he hyper parameters, using novel methods for Graph Convolution on the convolutional layers for example different graph coarsening (Liu et al., 2019), using methods for learning the best Metric for the initial Adjacency Matrices and the Laplacians in the same separate network, using Multi-Graph convolution for the smaller network layers and factorized convolution on the bigger levels, using other different methods for matrix factorization and using Product Graph Laplacians instead of the row/columns (Imrich & Klavzar 2000; Ortéz-Jiménez et al., 2018).
In future work we also believe that there can be an expansion of the results to higher dimentional space (from matrix to tensor completion). One of our side experiments was testing the method on real live mobile adds platform that shared Terabytes of information with us, and included a tensor of User(gamer),
(aame) and Context(page appearance and details in which the game adver- tised), and got prediction results for the content downloading much better and faster then RMGCNN and better then every company algorithm.
The data included: The shared data included the following files: Apps 183, 199 Applications and Host Applications. They included different properties of the application like genre, developer details, price, OS and etc.
Hosts like Apps the same 183, 199 Applications and Host Applications. They included differ- ent properties of the application like genre, developer details, price, OS and etc.
c. Users 12, 12,,008 Users that included users' properties like their origin, country, locale, interests and other user specific properties.
Events 632,849,288 Events that included the user, application, context (application host), and the specific event that occurred by the user (impression, click, install and etc.).
We have predicted the Clicks of users on the apps but could work with any other kind of event.
The results were as following:
Table 3: Results comparison on a real live Adds Dataset.
METHOD
RMSE
Time to best result
sRMGCNN
0.0172
~30 min
MDDD
0.0160
~5 min
In addition, Dynamic inference (in which the matrix itself describes a time process and the geometry of the row/column spaces has some non-trivial dynamics) can be great extension to the algorithm applications but requires a separate future research in different settings and benchmarks.
Finally, in future work we intend and strongly recommend to other scientists explore if new Learning methods that are state of art in the field of single image completion problem (in the 2-D Euclidean domain) may yield new state of art results also for the solution of the Parallel Non- Euclidean Matrix Completion problem the way we have translated the Deep Decoder network in this article, for Non-Euclides Domains.
12

---

Under review as a conference paper at ICLR 2021
B APPENDIX B
SIDE RESEARCH- SMALL MATRICES COMPLETION IN PRODUCT SPACE One of the experi- ments that we did as part of work was to test the idea of matrix completion when input not only the ratings matrix, but the whole product space. To test this, we took the Movielens 100k database and created random cuts from the matrix X of 100x100 size. We took 30% of the data as the observed data and 7.5% of the observed data as the training data. Our goal was to complete the whole 100x 100 ratings matrix (see example run in figure 5). First we ran the RMGCNN algo- rithm as described in Monti et al. 2017). Then we ran the same algorithm on the product space instead, meaning, that our input was the full product space matrix (as described in figure 4). In all experiments we constructed the Laplacian matrices using only the features of users/movies and partial rating column. When we compared the RMSE in all cuts,the result was a higher RMSE of 20-40 % in case we inputted the whole product space (see table 4 for all cuts). In addition, not only the ratings where completed but also all other features (like age, gender etc.). The drawback of this method was that the learning took a long time and the time grows exponentially with every user/item couple. The advantage of this method is that it can be applicable for real life instances when small sparse matrices with important data should be completed (like small businesses or detective purpose etc.). It also worthwhile to test different estimators for the product space. Future research this direction might yield astonishing results.
Product Space Row Graph
Product Space Column Graph
Product Matrix
Pais
Age
Gender
Genre
Length
Pair Roting
Gender
Novis LJber1
Novie Wiber
08
Movie (User)
08
Length
Figure 4: The full product space matrix input illustration
Example Run Movielens [600:700,600:700]
Methed
Full Ground truth Matrix
Support (30% of the Ful! matrixi
Dato and Training (random support for learning)
Best Result (Compared only for entries Full Ground truth Matrux
RMSE/MSE
RMOCNN en
Min
0.06075277470
169958
Min
0.00E52101052
Lie max
2016990
volenvers
RMSCNN on Product Matrix
Min RINS::
0.05712308805
MIn MM:
85137506
Figure 5: Example run illustration The cut of users 600:700 and movies 600:700
13

---

Under review as a conference paper at ICLR 2021
Table 4: All 10 cuts RMSE comparison
Run1
Run2
Run3
Run4
Rurb
Run6
Run7
Run8
Run9
Run10
RMSE Averoge
RMSE Variance
Matrix X input
0.1333
0.10558
0.13624
0.097113
0.09006
0.07926
0.08075
0.06518
0.05351
0.12977
0.097958577
0.000931
Product space Input
0.10715
0,08996
0.10705
0.07225
0.07756
0.06015
0.05712
0,04864
0,04448
0.10247
0.075571776
0.000573632
Average Improvement
24.41%
18.82%
27.27%
34.44%
27.47%
31.78%
41.37%
34.00%
20.31%
26.65%
28.65%
14


Reviews:
[{"review_id": "_iqwmjgFff4", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Topic: Matrix Completion for Recommender Systems\n\n\nmain contribution\n\nusing the idea of `deep prior for matrix completion.\n\n\nStrength\n\n-  performance: It seems that the method outperforms a number of baselines on different recommender system tasks. This suggests the usefulness of the proposed method.\n\n\n\nWeakness\n\n- Contribution Limited: The problem is formulated as graph Laplacian regularized matrix completion problem. This has been a long-existing technique. The contribution of this work lies in modeling the complete matrix within the range of a deep generative model and learns the deep generative model on the fly. GNN based link prediction is not a new technique. The work puts GNN based link prediction together with low-rank regularization, which is perhaps the reason why some practical benefits were observed, but the contribution is limited.\n\nIn fact, it is very hard to see how much new contribution is there on top of the main reference \n\nFederico Monti, Michael M. Bronstein, and Xavier Bresson. Geometric matrix completion with\nrecurrent multi-graph neural networks. CoRR, abs/1704.06803, 2017. URL http://arxiv.\norg/abs/1704.06803.\n\nThere may have been some regularization and network modifications, but the new contributions seem to be marginal.\n\nIs it possible to clarify what are the new contributions on top of the framework from the above reference?\n\n\n- Clarity and Soundness:\n -- Most of the effort was invested onto constructing the graph CNN that is claimed tailored for non-Euclidean matrices. But this part looks a bit theoretically (or even intuitively) ungrounded --- particularly, it is not easy to follow the rationale behind sec. 2.4. It is also unclear how is this construction suitable for handling non-Euclidean cases. This part may need some more explanations. \n\n-- the writing of the work is a bit convoluted or at least misleading. It tries to connect with deep prior based approaches, but the actual method is not really related. In a nutshell, the approach is a regression approach that maps embeddings of the row and column entities of the matrix to be completed to the ratings. The embeddings are constructed from graph Laplacians, and the mapping (regression model) is a particularly constructed neural network. It is suggested that these points to be clearly articulated.\n\n\n- Technical Depth: The regression formulation with the regularization and constraints are not outright unreasonable, but it seems that there is no further justification of the approach beyond intuition. The reason why the regression model/network should be constructed this way other than other ways is unclear and unjustified, even on an intuition level. The technical depth of this work may have large room to improve.\n\n- Simulation validation: It is unclear if the proposed algorithm converges or not, even on simple simulated data. It is suggested to show the algorithms’ numerical behaviors so that the readers have some sense about its convergence characterizations. The current version does not have such information.\n\n- Questionable Mathematical Representation: The last equation in page 3 looks a bit strange: if X is approximated by WH’, then it is automatically rank limited (by the number of columns of W,H). Adding a nuclear norm on WH’ looks unnecessarily complicated.\n\n\n- writing: The writing seems to have been done in a hastily manner, with many typos (see “Minor”). \n\n\n\n\n\nMinor:\n\npage 2: ``non-convex (but still very well-behaved)’’: what does it mean?\npage 2: two equations, “min” should be “arg min”?\npage 4  sec 2.4 “stracture”\nsec 2.3.2 “better then” \nmost of the tables and figures seem to have very low resolution\nsec 3.1 is very hard to read through \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "VfcJ4UB9QSq", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "In this work,  the authors addressed the problem of Matrix Completion on Non-Euclidean domains.  They mainly adopt the method Matrix Data Deep Decoder, inspired by the Deep Decoder method for Image Completion. Here are my main concerns:\n\n1. The technical contributions of this paper is limited since it mainly adopts existing methods, like Matrix Completion + Deep Decoder + multi-graph convolution. It seems for me this paper is more like an engineering paper consist of lots of stuff. It is better to release the source code to understand this kind of composition stuffs.\n\n2. The motivation of this work is also not very sound. The authors spend lots of content on the related work. However, the main idea is only presented in a presuppose-code style in Page 6, which is not very clear.\n\n3. In the experimental parts. Why use different methods for different dataset in Table 2(a), (b), (c)?  Is it possible to conduct all of the baselines for all datasets? Also,  the matrix completion has been studied for many years with many solid theory results,  the baselines in the experiments are not SOAT.\n\nTypos:\nIn page 4: stracture -------> structure\nIn page 7:  can be found in the work of [30] -----> the cite form is not correct.\n\nIn summary, the paper show that a GCN network is a good prior for the Matrix completion problem. However,  the technical contributions of this paper is limited and the overall presentation can be further improved.", "extra_scores": {}, "extra_text": {}}, {"review_id": "FHx8gFyYfdu", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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 tackle the matrix completion problem by drawing connection from prior work in image completion domain. It seems to be a combination of prior work: Multi-graph convolution combined with Dirichlet energy on row and column graph laplacian where the input rating matrix is corrupted with noise. The writing and presentation is significantly below par Iclr acceptance in the current form. Also, considering some of the work mentioned below, SOTA results is an overclaim.\n\na) Clarity Issues- \nPage 6 is incomprehensible in current form where the main algorithm is described. There are too many font changes in the results and main algorithm section. There is a grammatical / spelling error or typo almost every 5 lines throughout the paper. Few examples below:\n\n-results for Matrix Completion *where* obtained \n-Figure 3: Network Structure Illustration – MDDD algorithm flow *scatch*\n-then present in a *summerizing* tables the Results compared to other known methods.\n-the Non-Factorised and the *factosised* algorithms.\n-*translate\" its network \n-so it would *feet* for Matrix completion\n\nb) State of the art on Matrix completion:\nWhile this work claims state of the art results, it is missing some recent work (Iclr 20) that have achieved better state of the art results than reported in this paper.\n\n1) Inductive Matrix completion with gnn iclr 20 https://openreview.net/forum?id=ByxxgCEYDS\n2) Deep Matrix Factorization with spectral regularizers (https://arxiv.org/abs/1911.07255)\n\nc) Related work :\nThis section is completely missing. While authors use 3 and half pages to describe the background needed,  it is not clear to me how this work uses multi graph convolution used in prior work or how does the authors make use of Dirichlet energy that is defined in preliminary section if it is differently used here than prior work.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2mfpuNwIXH8", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "It could be accepted with major changes in the structure of the paper and rewriting some parts. But I would prefer to vote for rejecting and ask them for upgrading the writing overall. \n\nPros:\nVery promising method and concept.\nExperimental results look great comparing to the two state-of-the-art methods (Referring to table 2 – performance comparison)\n\nCons:\n1.\tThe grammar and style of writing are not as high as expected. \nSeveral typos and lowercase/uppercase misuse throughout the whole paper. Numerous grammatical errors. \nUse of several run-on sentences. For example:\nIn abstract:\nUse of the adjectives “surprising” and “spectacular” for the state-of-the-art methods is uncustomary language for a technical literature. \nThe sentence starting with “In sharp contrast to previous …” is a run-on sentence. It can be broken to at least two sentences. \nThen the sentence containing “getting that way state of the art …” is vague. Do you mean “in that way we get?”\nThe sentence starting with “In addition to the conceptual simplicity of our method …” is a run-on sentence. Should be broken to at least two sentences. \n\nIn section 1 Introduction:\n“In this work, we present a simplified …” sentence is too long. \nAfter “a classical end to end graph convolutional neural network and is/was inspired…”, is/was is missing before inspired. \nThe sentence starting with “When, the geometry of the column/row …” is grammatically incorrect. It could be connected to the previous sentence with a phrase in which, instead of using “when”. \n\n2.\tThe structure of the paper is not completely standard. \n•\tContribution i and ii are technically one contribution and should be merged. \n•\tIn section 2.3 “two recent works” are mentioned with no immediate reference to the papers.\n•\tFuture work could be a section after a conclusion called future work, not as an appendix. The appendix is usually for detailed descriptions of methods. \n•\tToo many small subsections. \no\tToo many small subsections in section 2. Preliminaries.\no\tIn section 3.1, network preparation starts with bullet points right away. An explaining sentence or two is needed before starting the bullet point. The same issue at 3.2, only two figures are shown with no extra explanation. \no\t3.3 is not a necessary subsection. Should be merged with other explanations of this section. \n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The focus of this paper is to analyze an end to end network to reconstruct matrices originating from non-Euclidean data which are corrupted. The authors present an untrained network for this task. In the review period the reviewers raised a variety of concerns including concerns about novelty of the paper with respect to existing work, technical depth and clarity. The authors did not respond to these concerns. Therefore, I recommend rejection.
Decision: Reject