Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: The authors suggest to express large matrices as operations over given manageable leaf matrices. They keep track of the resulting abstract syntax tree (AST) and offer a specialised SVD decomposition implementation that can perform the computation on the final expression by traversing the AST and operating on the individual leaf matrices. They then show how using the SVD operation they can perform learning in various inductive and transductive tasks. The advantage of their proposal is that the process is computationally efficient and they can in practice match SOTA results with speedups reaching several orders of magnitude.
main_review: The work presented warrants dissemination as it is an original approach to tackle ML problems on large datasets. 
The paper is filled with ideas and examples on how to model various problems and it may therefore cram too much in too little space. This is likely inevitable and not something that can be helped much. 
Further improvements would include a more systematic empirical investigation of the scaling behaviour of the method (i.e. tackling a defined set of problems on ever increasing inputs)  and offering a more structured conceptual framework to describe general classes of problems and how they can be addressed/converted with the new approach.

### After the authors' responses
Many thanks to the authors for the their response. I maintain my positive evaluation. I understand that due to the space constraints the authors cannot further develop general guiding principles or offer a more systematic treatment of their proposed approach, but I am confident that they will use other media (blogs, websites, GitHub, etc) and further publications to expand on the ideas they have introduced.  
limitations_and_societal_impact: The authors do address the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The goal of this paper is to speed-up graph representational learning by removing 
nonlinearities between layers and replacing them with linear models while also 
replacing cross entropy by Frobenius norm minimization. In turn, this allows the 
application of SVD, and the authors suggest modifications of randomized SVD 
which execute faster and in a matrix-free manner. The above approach is reported 
to be much faster than previous state-of-the-art, even though it is required to post-process 
the obtained model by feeding it as an initial guess to a more expensive, but also 
more accurate, approach. 
main_review: 
-) The paper is fairly well-written.

-) For most part, the concepts presented are in a clear manner although the paper is 
crowded with equations and side-information. 

-) I am not sure about whether the authors claim that the their orthonormalization approach 
is new or they just use it to speed-up the QR part in randomized SVD. If the former is the 
case, then it is not a new idea. In fact, it is a well-known "trick", see for example

https://www.sciencedirect.com/science/article/pii/S0010465510000524

Do the authors use a different approach? If so, can they elaborate more on how exactly they 
replace standard QR?

-) In addition to the above remark, using the Cholesky factorization squares the condition 
number of the matrix whose columns are orthonormalized (i.e., normal equations). In fact, 
I am actually surprised that the authors didn't mention this, since my understanding is that 
they use the "subspace iteration" version of randomized SVD. 

-) Moreover, matrix-free SVD is not a new thing -- in fact several approaches exist, see for example

https://academic.oup.com/bioinformatics/article/35/19/3679/5430929?login=true

I understand that the authors refer to their own approach of doing this, but some citations 
on the topic need be provided. 

-) The experiments paint a nice picture, and they indeed show that the suggested hybrid 
approach is a good alternative. Nonetheless, my impression is that the proposed hybrid 
approach is more costly in terms of memory. Is this the case? If so, then I wonder 
whether the proposed approach is useful for large graphs with millions/tens of millions of 
nodes. Note that using less nodes with more edges is not as important as very large and very 
sparse graphs. What is the execution time then? Can the authors provide experiments on 
graphs with millions of nodes? Alongside memory costs for each method? This would be 
very helpful.

-) How do you set the number of leaf nodes?

-) A '.' is missing at the end of line 285.

-) "decompose exactly M without calculating it" -> "decompose M exactly without explicitly calculating it."

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this work, authors design a software framework which allows symbolically representing matrices and computing their SVD implicitly. This paper also derives linear first-order approximations of popular Graph Representation Learning (GRL) models, and they can be trained via SVD. Further, SVD initializations can be used to fine-tune deeper neural networks via cross-entropy on many GRL tasks. Experimental results demonstrate that the proposed model trains orders-of-magnitudes faster than state-of-art methods, while having comparable performance.
main_review: \textbf{Strength}: 
Authors open-source a software library that allows symbolic definition of matrices and computing their SVD efficiently without explicitly calculating them. \\
Authors derive the convexification of popular GRL models (i.e., network embedding models and message passing graph networks), and presents how to leverage SVD of designed matrices to train them without computing gradients.\\
Convexified model parameters from SVD can initialize deeper models which can be fine-tuned via cross-entropy over GRL tasks.


\textbf{Weakness}:
First, it would be great if the authors could discuss about the proposed method's computational complexity when dealing with huge graphs.\\
Next, it seems that the experiments are conducted on simple graphs. I wonder if it is possible to extend the proposed model to more complex graphs (e.g., knowledge graphs)?

limitations_and_societal_impact: Authors have discussed the limitations and societal impacts in the Conclusion Section.
review_title: null

Meta-review: The reviewers were generally positive about this paper -- they liked the SVD based approach to simplifying or initializing deep neural networks for graph representation learning, and appreciated the positive empirical results. Thus, the paper is recommended for acceptance. Connections to prior work should be clarified in the revise submission -- the abstract of the paper seems to imply that the idea of computing a partial SVD of an implicit matrix is new. There is significant work in the numerical linear algebra community on matrix-free SVD methods -- in fact this is a critically important feature of nearly all Krylov based and sketching methods for partial SVD. See this link for a number of references to background literature: https://stats.stackexchange.com/questions/159325/what-fast-algorithms-exist-for-computing-truncated-svd
Decision: Accept (Poster)