Implicit SVD for Graph Representation Learning
Authors: Sami Abu-El-Haija
Hesham Mostafa
Marcel Nassar
Valentino Crespi
Greg Ver Steeg
Aram Galstyan
Venue: NeurIPS 2021 Poster (2021)
Keywords: SVD
symbolic matrix
fast
graph
GRL
gradient-free
embedding
splitrelu
convex-nonconvex
resource efficient training
semi-supervised node classification

Abstract: Recent improvements in the performance of state-of-the-art (SOTA) methods for Graph Representational Learning (GRL) have come at the cost of significant computational resource requirements for training, e.g., for calculating gradients via backprop over many data epochs. Meanwhile, Singular Value Decomposition (SVD) can find closed-form solutions to convex problems, using merely a handful of epochs. In this paper, we make GRL more computationally tractable for those with modest hardware. We design a framework that computes SVD of *implicitly* defined matrices, and apply this framework to several GRL tasks. For each task, we derive first-order approximation of a SOTA model, where we design (expensive-to-store) matrix $\mathbf{M}$ and train the model, in closed-form, via SVD of $\mathbf{M}$, without calculating entries of $\mathbf{M}$. By converging to a unique point in one step, and without calculating gradients, our models show competitive empirical test performance over various graphs such as article citation and biological interaction networks. More importantly, SVD can initialize a deeper model, that is architected to be non-linear almost everywhere, though behaves linearly when its parameters reside on a hyperplane, onto which SVD initializes. The deeper model can then be fine-tuned within only a few epochs. Overall, our algorithm trains hundreds of times faster than state-of-the-art methods, while competing on test empirical performance. We open-source our implementation at: https://github.com/samihaija/isvd


Implicit SVD for Graph Representation Learning
Sami Abu-El-Haija USC Information Sciences Institute sami @haija. org
Hesham Mostafa, Marcel Nassar
Intel Labs
Valentino Crespi, Greg Ver Steeg, Aram Galstyan
USC Information Sciences Institute {vcrespi, oragapp.ggrrggggglssttannloiiii
galstyan edu
Abstract
Recent improvements in the performance of state-of-the-art (SOTA) methods for Graph Representational Learning (GRL) have come at the cost of significant computational resource requirements for training, e.g., for calculating gradients via backprop over many data epochs. Meanwhile, Singular Value Decomposition (SVD) find closed-form solutions to convex problems, using merely handful of epochs. In this paper, we make GRL more computationally tractable for those with modest hardware. We design framework that computes SVD of implicitly defined matrices, and apply this framework to several GRL tasks. For each task, we derive linear approximation of SOTA model, where we design (expensive- to-store) matrix M and train the model, in closed-form, via SVD of M, without calculating entries of M. By converging calculating gradients, our models show competitive empirical test performance over various graphs such as article citation and biological interaction networks. More importantly, SVD can initialize a deeper model, that is architected to be non- linear almost everywherg though behaves linearly when its parameters reside on a hyperplane, onto which SVD initializes. The deeper model can then be fine-tuned within only few epochs. Overall, our procedure trains hundreds of times faster than state-of- thite--f-thhattt the-art methods, while competing on empirical test performance. We open-source our implementation at: https: hattps://gitaii //g.tubb...t...t. com/ commsamihaii ja isvd
unique point one step, and without
1 Introduction
Truncated Singular Value Decomposition (SVD) provides solutions to a variety mathematical problems, including computing matrix rank, its pseudo-inverse, or mapping its rows and columns onto the orthonormal singular bases for low-rank approximations. Machine Learning (ML) software frameworks (such as TensorFlow) offer efficient SVD implementationn,, as SVD can estimate solutions for a variaty of tasks, c.g., in computer vision Turk and Pentland, 1991], weather prediction [Molteni
al. 1996], recommendation [Koren al. 2009 language (Deerwester al.) 1990 Levy and
Goldberg 2014), and more-relevantly. graph representation learning (GRL) QQu et al.) 2018
SVD's benefits include training models, without calculating gradients, to arrive at globally-unqqu solutions, optimizing Frobenius-nomn objectives ($2.3), without requiring hyperparameters for the learning process, such the choice of the learning algorithm. step-size, regularization coefficient, etc. Typically, one constructs a design matrix M, such that, its decomposition provides solution to task of interest. Unfortunately, cxisting popular ML frameworks (Abadi et al.) 2016 Paszke ct al. 2019 cannot calculate the SVD of an arbitrary linear matrix given its computation graph: they
Parr of this work was done during internship at Intel Labs.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

compute the matrix (entry-wise) then its decomposition. This limits the scalability of these libraries in several cases of interest, such as in GRL, when explicit calculation of the matrix is prohibitive due to memory constraints. These limitations render SVD as impractical for achieving state-of-the-art (SOTA) for tasks at hand. This has been circumvented by QQu et al. 2018 by sampling M entry- wise, but this produces sub-optimal estimation error and experimentally degrades the empirical test performance ($7 Experiments).
We design a software library that allows symbolic definition of M. via composition of matrix opera- tions, and we implement an SVD algorithm that can decompose M from said symbolic representation, without need to compute M. This is valuable for many GRL tasks, where the design matrix M is too large, e.g., quadratic in the imput size. With our implementation, we show that SVD can perform learning, orders of magnitudes faster than current alternatives.
Currently, SOTA GRL models are generally graph neural networks trained to optimize cross-entropy objectives. Their inter-layer non-linearities place their (many) parameters onto a non-convex objective surface where convergence rarely verified Nonetheless, these models can be convexified ($3 and trained via SVD, if we remove nonlinearities between layers and swap the cross-entropy objective with Frobenius norm minimization. Undoubtedly, such linearization incurs drop of accuracy on empirical test performance. Nonetheless, we show that the (convexified) model's parameters learned by SVD can provide initialization to deeper (non-linee) models, which then can be fine-tuned on cross-entrope objectives. The non-linear models are endowed with our novel Split-ReLu layer, which has twice as many parameters as a ReLu fully-connected layer, and behaves as a linear layer when its parameters reside on some hyperplane ($5.2) Training on modest hardware (e.g., laptop) is sufficient for this learning pipeline (convexify SVD - fine-tune) yet trains much faster than current approaches, that are commonly trained on expensive hardware. We summarize our contributions as:
We open-source a flexible python software library that allows symbolic definition of matrices and computes their SVD without explicitly calculating them.
2. We linearize popular GRL models, and train them via SVD of design matrices.
3. We show that fine-tuning few parameters on-top of the SVD initialization sets state-of-the-art on many GRL tasks while, overall, training urders-of-magnitudee faster.
2 Preliminaries & notation
We denote a graph with n nodes and m edges with an adjacency matrix A E Ruxa and additionally, if nodes have (d-dimensional) features, with a feature matrix X E R2xd If nodes i.j [ni] are connected then A.j is set to their edge weight and otherwise Ao = 0. Further, denote the (row-wise normalized) transition matrix as T D-1 A and denote the symmetrically normalized adjacency with coffeconnettion as A = (D + I) IID +I- where I is identity matrix.
We review model classes: (1) network embedding and (2) message passing that we define as follows. The first inputs a graph (A, X) and outputs node embedding matrix Z E R with z-dimensions per node, Z is then used for an upstream task, e.g., link prediction. The second class utilizes a function H x Raxd - x where the function H(A, X) usually directly trained on the upstream task, e.g. node classification. In general, the first class is transductive while the second is inductive.
2.1 Network embedding models based on Deep & node2vec
The seminal work of DeepWalk Perozzi al. 2014] embeds nodes of a network using two-step process: (i) simulate random walks on the graph each walk generating a sequence of node IDs then (ii) pass the walks (node IDs) to language word embedding algorithm, e.g. word2vec [Mikolov et al. 2013), as each walk is a sentence. This work was extended by node2vec [Grover and Leskovec 2016 among others. has been shown by AAuu-El-Haiaa et al. (0188 that the learning outcome of
FeensoFFlow can caluclate matrix-free SVD one implements Linear0perator, as such, our code could he re-implemented as a routine that can convert TensorGraph to LinearOperator. Prractitioners rarely verify that Vo. = 0, where J is mean train objective and 0 are model parameters.

---

the two-step process of WeepWalk is equivalent, in expectation, to optimizing single objectivo
min 2- (L (1
E [ logo(LR") A(1 - lo -ooR q~
(I)
where L, R E RTx are named by word2vec as the input and outpur embedding matrices, is Hadamard product, and the log(.) and the standard logistic a(.) element-wise. The objective above weighted cross-entropy where the (left) positive term weighs the dot-product L R, by the (expected) number of random walks simulated from and passing through J. and the (right) negative term weighs non-edges (1 (1) ) by scalar À E R.,. The context distribution Q stems from step (ii) of the process. In particular, word2vec accepts hyperparameter context window size C for its stochasatic sampling: when it samples a center token (node ID), then samples its context tokens that up-to distance from the center. The integer sampled from a coin flip uniform on the integers [1, ..., CJ -ass detailed by Sec.3.1 of (Levy et al. 2015
+ exp(.)) are applied
Therefore, Pq C) & C-gt2. Since has support on [C], then Po(a C) = [C+1CC
2.2 Message passing graph networks for (semi-) node classification
We are also interested in class of (message passing) graph network models taking the general form:
for -o 0,.,,.... ......... L: H(++) = (w( H = X; H H(
where L is the number of layers, W is are trainable parameters, oi 's denote element-wise activations (e.g. logistic or ReLu), and y is some (possibly trainable) transformation of adjacency matrix. GCN KKip and Welling, 2017 set (AA)
A, GAT Veličković et al. 2018 set (A)
with 0. For node H I where y is number of classes, and optimize cross-entropy objective:
MultiHeeaedAAttenioon and GIN [Xu et al. 2019 as =
classification, it is common to set σg = softmax (applied row-wise), specifyy the size of Wt s.t.
where Y is a binary matrix with one- hot rows indicating node labels. In semi-supervised settings where not all nodes labeled, before measuring the objective, subset of rows can be kept in Y and H that correspond to labeled nodes.
[w, 1 [-Y o log H - (1 - Y) log(1 - H)),
2.3 Truncated Singular Value Decomposition (SVD)
SVD is an algorithm that approximates any matrix M E Rrxx as product of three matrices:
SVD arg min [M- - USV T || subject to UTU-VTV Is; S
8k).
U.S.V
The orthonormal matrices U E grxk and V E Rexk respectively, are known as the left- and right-singular bases. The values along diagonal matrix S E R are known the singular values. Due to theorem of Eckart and Young 1936). SVD recovers the best rank-k approximation of input M. as measured by the Frobenius norm Further, if A rank(M) = ||-1|p 0.
2209)] The prototype algorithm starts with random matrix and repeatedly multiplies it by M and by M interleaving these multiplications with orthonormalization. Our SVD implementation (in Appendix) also follows the prototype of [Halko et al.) 2009], but with two modifications: (i) we replace the recommended orthonormalization step from QR decomposition to Cholesky decomposition, giving us significant computational speedups and (ii) our implementation accepts symbolic representation of M (S4). in lieu of its explicit value (constrast to TensorFlow and PyTorch, requiring explicit M).
Popular SVD implementations follow Random Matrix Theory algorithm Halko
In 3 we derive linear first-order approximations of models reviewed in 221 & $2.2 and explain how SVD can train them. In |5 we show how they can be used as initializations of non-linear models.
'Derivation is in Abu-El-Haipp et al. 2018 Unfortunately, matrix in Eq. iis dense with O(n²) nonzeros.
3

---

3 Convex first-order approximations of GRL models
3.1 Convexification of Network Embedding Models
We can interpret objective as self-supervised learning, since node labels are absent. Specifically, given a node E [ni] the task is to predict its neighborhood as weighted by the row vector I [7%,, representing the subgrapt around Another interpretation is that Eq. [ is decomposition objective: multiplying the tall-and- thin matrices, as LR E I=**" should give a larger value at (LR )i = I R, when nodes i and j are well-connected but a lower value when (i,j) is not an edge. We propose a matrix such that its decomposition can incorporate the above interpretations:
( = EylccTT - X(1 A)
(C (1C+1)
2
Σ
(
C C
T X(1 A)
(3)
1JC
If nodes i are nearby, share a lot of connections, and/or in the same community, then entry M NE) should be positive. If they are far apart, then M = -X To embed the nodes onto a low-rank space that approximates this information, one can decompose M into two thin matrices R):
LR M - (LR - R,) Mi for all i,j [n].
SVD gives low-rank approximations that minimize the Frobenius norm of error 23.3 The remaining challenge is computational burden: the right term (1 - A), a.k.a, graph compliment, has s n² non- zero entries and the left term has non-zero entry (i. if nodes i, within distance C away, has support on [C] for reference Facebook network has an average distance [Backstrom et al. 2012) i.e. yielding T with (n²)) nonzero entries Nonetheless, Section presents a tramework for decomposing M from its symbolic representation, without explicitly computing its entries. Before moving forward, we note that one can replace T in Eq. by its symmetrically normalized counterpart A, recovering basis where L R. This symmetric modeling might be emperically preferred for undirected graphs. Learning can be performed via SVD. Specifically, the node at the 7th row and the node at the th column will be embedded, respectively, in L, and R. computed as:
U.S. V < SVD, (M
+ L
R+ VS
(5)
In this k-dim space of rows and columns, Euclidean measures are plausible: Inference of nodes' similarity at row i and column j can be modeled as f(i,j) = (L, R,) = U.S.V, & (U,, Vi)s-
3.2
Convexification of message passing graph networks
Removing all ot's from Eq. 2 and setting g(A) = A gives outputs of layers 1,2, and L, respectively, ( (2) and
A
w()) w(1) (6)
Without -oneaiinas,,ies, adjacent parameter matrices can be absorbed into one another. Further, the model output can concatenate all layers, like JKNets [Xu al. 2018), giving final model output
(CC
x
Äx
A
A W
MOOW
linearized
where the linearized model implicitly constructs design matrix M RF and multiplies it with parameter W R.. Fxy here, d + dL. Crafting design matrices is a creative process 5$5.)
Learning can be performed by minimizing the Frohenius norm: | - Y|II = |
MNOW Y
Moore-Penron Inverse (a.k.a, the psuedoinverse) provides one such minimizer:
W argmin MW Y -M VS+UYY
(8)
with U. V SVD& MM). Notation S reciprocates non-zero entries of diagonal $ Golub and Multiplications in the right-most term should, for efficiency, be executed light-tollltt
Loan 1996
E, [T is distribution [n]: entry j equals prob. of walk starting ending j if walk length U[C].

---

a we..y..ppree.dlagssa......o sam(ixs=)))
csr aaaeeessssmmttte mmtarii(....)
t (1/d).dot(a)
t, a F.leaf(t), F.leaf(a)
row1 = F.leea (tf.onne(()) ([1, a. a.shape [0]1))
q1, q2, q3 = np.array ([3, 2, 1]) 6.0
3
q1
q2 têt q3 tōt@t
lamda (row1. 0 rowl A)
Figure I: Symbolic Matrix Representation. Left: code using our framework to implicitly construct the design matrix M M(NE) with framework. Center: DAG corresponding to the code. Right: An equivalent uutomatiially--ptimiizz
DAG (via lazy-cache, Fig. 2 requiring fewer floating point operations. The first 3 lines of code create explicit input matrices (that fit in memory): adjacency A, diagonal degree D, and transition T. Matrices are imported into our framework with F. Plla (depicted on computation DAGS in blue). Our classes overloads standard methods (t, -. +, **) to construct computation nodes (intermediate in grey). The output node (in red) needs not be exactly calculated yet can be efficiently multiplied by any matrix by recursive downward traversal.
The pseudoinverse M VS+UT recovers the W with least norm ($6 Theorem becomes = when 2 ran.
1_ The x
In semi-supervised settings, one can take rows subset of either (i) Y and U, or of (ii) Y and M, keeping only rows that correspond to labeled nodes. Option (i) is supported by existing frameworks (e.g., tf gather ()) and our symbolic framework ($4) supports (ii) by implicit row (or column) gather - i.e. calculating SVD of submatrix M without explicitly computing M nor the submatrix. Inference over (possibly new) graph (A,X) can be calculated by (i) (implicitly) creating the design matrix M corresponding to (A, X) then (ii) multiplying by the explicitly calculated W As explained in $4 M need not to be explicitly calculated for computing multiplications.
Symbolic matrix representation
To compute the SVD of any matrix M using algorithm prototypes presented by Halko et al. [2009] it suffices to provide functions that can multiply arbitrary vectors with M and M and explicit calculation of M is not required. Our software framework can symbolically represent M directed acyelic graph (DAG) of computations. On this DAG, each node can be one of two kinds:
1. Leaf node (no incoming edges) that explicitly holds matrix. Multiplications against leaf nodes are directly executed via an underlying math framework (we utilize TensorFlow).
2. Symbolic node that only implicitly represents a matrix as as a function of other DAG nodes. Multiplications recursively computed, traversing incoming edges, until leaf nodes.
For instance, suppose leaf DAG nodes M, and M2, respectively, explicitly contain row vector E IR. 1x and column vector E Raxx1 Then, their (symbolic) product DAG node M M2æM, is <Rax,, Although storing M explicitly requires (O space, multiplications against M can remain within (n) space if efficiently implemented as (M,.) = (M2, (M) Figure | shows code snippet for composing DAG represent symbolic node (EE) (Eq. 3. from leaf nodes initialized with in-memory matrices. Appendex lists symbolic nodes and their implementations.
5
SVD initialization for deeper models fine-tuned via cross-entropy
5.1 Edge function for network embedding as (1-dimensional) Gaussian kernel
SVD provides decent solutions to link prediction tasks. Computing U,S, V + SVD(M is much faster than training SOTA models for link prediction, yet, simple edge-scoring function f(i,j) = (U,, Vi)s yields competitive empirical (test) performance. We propose ʃ with 0 = 8},
V = U. (/, (/Ss((z (u,,),,)))))) (1,s)dr) V,, (9)
(i. B.-N(.s (U; Vi
U Ex S
5

---

where N is the truncated normal distribution (we truncate to f = [0.5, 2)). The integral can be approximated by discretization and applying softmax (see $A.4). The parameters μ E R, Ryo can be optimized on cross-entropy objective for link-prediction:
min,,. ((ij)e [log (o(ff..(t (i,ne [lo (1 off..(tt))))
(10)
where the left- and right-terms, respectively, encourage f to score high for edges, and the low for non-edges. kuy E N controls the ratio of negatives to positives per batch (we use hm 10). If the optimization sets μ = and 8 Rs O, then f reduces no-op. In fact, we initialize as such, and we observe that f converges within one epoch, on graphs we experimented on. If it converges as l < 1, VS y > 1, respectively, then f would effectively squash, VS enlarge, the spectral gap.
5.2 Split-ReLu (deep) graph network for node classification (NC)
W from SVD (Eq can initialize an L-layer graph network with input: H()) X, with: (0)
message passing (MP)
H (1+1)
Ah
w
- w
(11)
(P)
output
W
!1)
w (1) (on)
(12)
[op
W (1)
(1)
initialize MP
(p) I: W
(13)
(n)
initialize output
w())
W d(L+1)
(((
W [dt: d(+1))
(14)
(op)
(on)
Wiement-wise [[+ = max(0..). Further, Wi: denotes rows from (f)th until (i-1)th th of W.
The deep network layers (Eq. 12 use our Split-ReLu layer which we formalize as:
SplitReLu(X; W (),) W() [ mp [W
(15)
where the subtraction is calculated entry-wise. The layer has twice as many parameters as standard fully-connected (FC) ReLu layer. In fact, learning algorithms can recover FC ReLu from SplitReLu by assigning Was = O. More importantly, the layer behaves as linear in X when W = W mm- On this hyperplane, this linear behavior allows to establish the equivalency: the (non-linear) model H is equivalent to the linear Hineaiized at initialization (Eq, & due to Theorem 2 Following the initialization, model can be fine-tuned cross-entropy objective in $2.2
5.3 Creative Add-ons for node classification (NC) models
Label re-use (LR): Let (IN))
M NCC
-
(A
(D - (usik)
(A (D 1-+++I--11
Itsial
This follows the motivation of Wang and Leskovee 22200]
Huang et al.
[202] Wang [222] I and
their empirical results on ogbn-arxiv dataset, where [train] E gx*0
contains one-hot vectors at rows vectors for unlabeled (test) nodes. Our scheme is
corresponding labeled nodes but contain similar to concatenating Y |iain into X, but with care to prevent label leakage from row i of Y to row
i of M, as zero-out the diagonal of the adjacency multiplied by Y [train].
Seeudo-Dropout (PD): Dropout [Srivastava al. 2014) reduces overfitting of models. It can be related to data augmentation, as each example is presented multiple times. At each time, it appears with different set of dropped-on out features input or latent feature values, chosen random, get replaced with zeros. As such, we can replicate the design matrix as: M
M
PD(M) This
row-wise concatenation maintains the width of M and therefore the number model parameters.
In the above add-ons, concatenations, as well as PD, can be implicit or explicit (see $A.3).

---

Table 1: Dataset Statistics
Dataset
Nodes
Edges
Source
Task
X
PPI
3,852 proteins
20,881
chem. interactions
node2vec
LP
K
X
FB
4,039 users
88,234
friendships
SNAP
LP
AstroPh
17,903 researchers
197.031
co-authorships
SNAP
LP
Hep'Th
8,638 researchers
24,827
co-authorships
SNAP
LP
X
Cora
2,708
articles
5,429
citations
Planetoid
SSC
Citeseer
3,327 articles
4,732 citations
Planetoid
SSC
Pubmed
19,717 articles
44,338 citations
Planctoid
SSC
ogbn-Art ArXiv
169,343 papers
1,166,243
citations
OGB
SSC
ogbl-DDI
4,267 drugs
1,334,889
interactions
OGB LP
Analysis & Discussion
Theorem 1. (Min. Norm) If system MW
Y is underdetermined with rows of M being linearly MW Y has infinitely many solutions. Then, for
independent, then solution space W
rank (M), matrix W", recovered by Eq satisfies: W argmin ||
Theorem implies that, even though one can design wide M (Eq 7 iee, with many layers, the
recovered parameters with least norm should be less prone to overfitting. Recall that this is the goal of L.2 regularization. Analysis and proofs are in the Appendix.
Theorem 2. (Non-linear init) The initialization Eq. 13 14 wields (NC) linarrized
H
Eq
Theorem 2 implies that the deep (nonlinear) model is the same as the linear model, at the initialization
of (per Eq. 13 14
using W as Eq. 8). Cross-entropy objective can then fine-tune 8.
This end-to-end process, of (i) computing SVD bases and (ii) training the network So on singular values, advances SOTA on competitve benchmarks, with (i) converging (quickly) unique solution and (ii) containing merely few parameters 0 see 7
7 Applications & Experiments
We download and experiment on 9 datasets summarized in Table
We attempt link prediction (LP) tasks on smaller graph datasets (< million edges) of: Protein-Prote Protein Interactions (PPI) graph from Grover and Leskovec [2016]; as well as ego-Facebook (FB), AstroPh, HepTh from Stanford SNAP [eekovee and Krevl, 2014]. these datasets, we use the train-test splits of Hajja et al. 2018). We also attempt semi-supervised node classification (SSC) tasks on smaller graphs of Cora, Citeseer, Pubmed, all obtained from Planetoid [Yang et al. 2016). For these smaller datasets, only train and test using the SVD basis (without finetuning)
million edges) from Stanford's Open Graph Benchmark [OGB, Hu et al., 2020]. We use the official train-test-validation splits and evaluator of OGB. We attempt LP and SSC, respectively, on Drug Drug Interactions (ogbl-DDI) and ArXiv citation network (ogbn-ArXiv), For these larger datasets, we use the SVD basis as initialization that we finetune, as described
Further, we attempt on Slightly-larger datasets
$ For time comparisons, we train all models on Tesla K80.
7.1 Test performance & runtime on smaller datasets from: Planetoid & Stanford SNAP
For SSC over Planetoid's datasets, both A and X are given. Additionally, only handful of nodes are labeled. The goal is to classify the unlabeled test nodes. Table summarizes the results. For baselines, download code of GAT (Veličković et 2018), MixHop (Abu-El-Haija et al. 2019) GCNII [Chen et al.) 2020 and re-ran them with instrumentation to record training time. However, for baselines Planetoid Yang al. 2016) and GCN [Kipf and Welling 2017). we copied numbers
EE.g., if the number of labeled examples iee. height of M and Y is smaller than the width of M.

---

Table 2: Test accuracy (& train time) on citation graphs for task: semi-supervised node classification.
Graph dataset:
Cora
Citeseer
Pubmed
Baselines:
acc
tr.tmme
tr.time
acc
tr.time
Planetoid
75.7
(13s)
64.7
(26s)
77.2
(25s)
GCN
81.5
(4s)
70.3
(7s)
79.0
(838)
GAT
83.2
(Im)
72.4
(3m)
77.7
(6m)
Mix GCNII
81.9
(26s)
71.4
(31s)
80.8
(Im)
85.5
(2m)
73.4
(3m)
80.3
(2m)
Our models:
acc
tr.time
acc
tr.time
acc
tr.tmme
iSVD oo (M
82.0 #0.13 (0.1s)
71.4 #0.22 (0.1s)
78.9 +0.31 (0.3s)
+ dropout (.3)
82.5 +0.46 (0.1s)
71.5 +0.53 (0.1s)
78.9 +0.59 (0.2s)
Table 3: Test ROC-AUC (& train time) on Stanford SNAP graphs for task: link prediction.
Graph dataset:
FB
AstroPh
HepTh
PPI
Baselines:
AUC
tr.time
AUC
tr.ime
AUC
tr.time
AUC
tr.time
WYS
99.4
(54s)
97.9
(32m)
93.6
(4m)
89.8
(46s)
n2v
99.0
(30s)
97.8
(2m)
92.3
(55s)
83.1
(27s)
NetMF
97.6
(5s)
96.8
(9m)
90.5
(72s)
73.6
(7s)
NetMF
97.0
(4s)
81.9
(4m)
85.0
(48s)
63.6
(10s)
Our models:
AUC
tr.time
AUC
tr.time
AUC
tr.time
AUC
tr.time
iSVD32 M ((NE)
99.1 11c6(()2s))
94.4 +:c-44 (0.5s)
90.5 +0.1
(0.1s)
89.3
+0.01
(0.1s)
iSVD256 256
M M
99.3 9
(2s)
98.0 #0.01
(7s)
90.1
#0.54
(2s)
89.3 #0.48
(Is)
from Kipf and Welling 2017]. For our models, the row labeled iSVD 100 (M we run implicit SVD twice per graph. The first run incorporates structural information: we (implicitly) construct (NN)) with À = 0.05 and C' = 3, then obtain L, R + SVDsa (M)))),, per Eq. Then, we concatenate L and into X. Then, PCA the resulting matrix to 1000 dimensions, which forms our new X. The second SVD run is to train the classification model parameters W From the PCA-ed X, we construct the implicit matrix ( with L = 15 layers and obtain W VS+ U Y [tain] with U,S.V V SVD (MD (M (imin)) per in RHS of Eq. 8 For second "+ dropout" model variant, we (implicit) augment the data by M
(D(M update indices W VS+UTY Y [tmin] Discussion: Our method is competitive yet trains faster than SOTA. In fact, the only method that
M
[rain] < [train train] then similarly learn as: SVD (MIN))
(train)
reliably beats ours all dataset is GCNII, but its training time is about one-thousand-timg -imes longer.
For LP over SNAP and node2vec datasets, the training adjacency is given but not X. The split includes test positive and negative edges, which are used to measure a ranking metric: ROC-AUR where the metric increases when test positive edges are ranked above than negatives. Table summarizes the results. For baselines, we download code of WYS [Abu- El- El-Haija et al. [201]]: we use the efficient implementation of Py WoToch-GGeometri [Fey and Lenssen 2019] for 2ode2vec (n2v) and we download code of Qiu et al. [2018) and run it with their two variants, denoting their first variant as NetMF (for exact, explicitly computing the design matrix) as and their second variant as NetMF (for approximate, sampling matrix entry-wise) - their code runs SVD after computing either variant. For the first of our models, we compute U, U.S. V < SVD (NF) and score every test edge as T SV,, j. For the second, we first run SVD256 on half of the training edges, determine the "best" rank E (8, 16, 32, 128, 256] by measuring the AUC on the remaining half of training edges, then using this best rank, recompute the SVD on the entire training set, then finally score the test edges. Discussion: Our method is competitive on SOTA while training much faster. Both NetMF and WYS explicitly calculate dense matrix before factorization. approximates the matrix entry-wise, trading accuracy for training time. In our case, we have the best
the other hand, NetMF

---

Table 4: Test Hits 20 for link prediction over Drug-Drug Interactions Network (ogbl-ddi).
Graph dataset:
ogbI-DDI
Baselines:
HITS@20
tr.time
DKA+JKNet
Yang et al. 2021
76.72 126655
(60m)
LRGA+n2v
Hsu and Chen
2021
73.85 18.71
(41m)
MAD
Luo et al. 202
67.81 12.94
(2.6h)
LRGA+GCN
Puny et a.
2020
62.30 19.12
(10m)
GCN+JKNet
Xu et al.
2018
60.56 +8.69
(21m)
Our models:
HITS@20
tr.time
(a) iSVD 100 (MNE)
3.1 Eq. 5
67.86 +0.09
(6s)
(b) + finetune (S)
5.1 Eq 9 & 10
sets =
1.15)
79.09 10.18
(24s)
(c) + update U,S.V
(on validation, keeps fuss fixed)
84.09 #0.03
(30s)
of both worlds: using our symbolic representation and SVD implementation, we can decompose the design matrix while only implicitly representing it, as good as if we had explicitly calculated it.
7.2 Experiments on Stanford's s OGB datasets
We summarize experiments ogbI-DDI and ogbn-ArXiv, respectively, in Tables F and 5 For baselines. copy numbers from the public leaderboard where the competition is fierce. We then follow links on the leaderboard to download author's code, that we re-run, to measure the training time. For
our models on oghI-DDI, we (a) first calculate U, S, V <- SVDioo(MME)) built only from training edges and score test edge (i.j) using U. SV Then, we (b) then finetune fu.. (per $5.1 Eq. 9 & 10h) for only a single epoch and score using (i. Then, we (c) update the SVD basis to include edges from the validation partition and also score using (t. We report the results for the three steps. For the last step, the rules of OGB allows using the validation set for training, but only after the hyperparameters are finalized. The SVD has no hyperparameters (except the rank, which was already determined by the first step). More importantly, this simulates a realistic situation: it is cheaper to obtain SVD (of an implicit matrix) than propaaae through model. For a time-evolving graph, one could run the SVD more often than doing gradient-descent epochs on model. For our models on ogbn-ArXiv, we (a) compute U.S.V V < SVD250 (M where the implicit matrix is defined in $53 We (b) repeat this process where replicate M(NC) once: in the second replica, replace the [trii]] matrix with zeros (as-if, we drop-out the label with 50% probability). We (c) repeat the process where concatenate two replicas of M into the design matrix, each with different dropout seed. We (d) fine-tune the last model over 15 epochs using stochastic GTTF [Markowitz] et al. 2.21]. Discussion: Our method competes sets SOTA, while training much faster.
Time improvements: We replaced the recommended orthonormalization of (Halko et al. 2009 from QR decomposition, to Cholesky decomposition ($A.2). Further, we implemented caching to avoid computing sub-expressions if already calculated ($A...44). Speed-ups are shown in Fig.
Table 5: Test classification accuracy over ogbn-arxiv.
DC DRIRR
Cholesly)
Graph dataset:
og
001
Baselines:
accuracy
tr.time
GAT+LR+KD
Ren
2020
74.16 10.08
(6h)
FB
GAT+LR
Nuu
2020
73.99
+0.12
(3h)
AGDN
Sun and Wu
2020
73.98
+0.09
(50m)
GAT+C&S
Huang et a..
2021
73.86
10.14
(2h)
GCNII
Chen et al.
2020
72.74 10.16
(3h)
P01
Our models:
accuracy
tr.time
1.00
(a) 2500 M LR
3.2
Eq. 8
68.90 10.02
(1s) Figure 2: SVD runtime configs of
(b) + dropout(LR (LR)
($5.3
69.34 +0.02
(3s) (lazy caching; orthonormalization
(c) + dropout( M (CC)
($5.3)
71.95 10.03
(6s) ratio of SVD's common de-
(d) + finetune H 5.2 Eq.
11
11
74.14 +0.05
(2m) fault (QR decomposition)

---

8
Related work
Applications: SVD was used to project rows & columns of matrix M onto an embedding space. M can be the Laplacian of a homogenous graph [Belkin and Niyogi 2003]. Adjacency of user-item bipartite graph (Koren et al.] 2009]] or stats DDeerwester et al. 1990 Levy and Goldberg 2014] for word-to-document. We differ: our M a function of (leaf) matrices useful when M is expensive to store (e.g.. quadratic). While Qiu et al. [2018] circumvents this by entry-wise sampling the (otherwise n² n M, our SVD implementation could decompose exactly M without calculating it.
Symbolic Software Frameworks: including Theano [AI-Rfou et al., 2016]. TensorFlow (Abadi al. [0166] and PyTorch (Paszke et al.,, 2019], allow chaining operations to compose a computation (directed acyclic) graph (DAG). They can efficiently run the DAG upwards by evaluating (all entries of) matrix M 1r any DAG node. Our DAG differs: instead of calculating M, provides product function (M) = M x
The graph is run downwards (reverse direction of edges).
Matrix-free SVD: For many matrices of interest, multiplying against M is computationally cheaper than explicitly storing M entry-wise. As such, many researchers implement SVD(uM)). e.g. Calvetti al. [994]. Wu and Simon (2000), [ose al. [2019]. We differ in the programming flexibility: the earlier methods expect the practitioner to directly implement UM. On the other hand, our framework allows composition of M via operations native the practitioner (e.g., @ +, concat), and uM is automatically defined.
We have applied our framework for fast graph learning, but as sampling- based approaches including [Chen et al.) 2018 Chiang et al. 2019 Zeng et al.] 2020 Markowitz et al. 2021]. We differ in that ours can be used obtain initial closed- solution (very quickly) and can be fine-tuned afterwards using any of the aforementioned approaches. Additionally, Graphs shows one general application. Our framework might be useful in other areas utilizing SVD.
Fast Graph Learning:
9 Conclusion, our limitations & possible negative societal impact
We develop software framework for symbolically representing matrices and compute their SVD. Without computing gradients. this trains convexified models over GRL tasks, showing empirical metrics competitive with SOTA while training significantly faster. Further, convexified model param- eters can initialize (deeper) neural networks that can be fine-tuned with cross entropy. Practitioners adopting our framework would now spend more effort in crafting design matrices instead of running experiments or tuning hyperparameters of the learning algorithm. We hope our framework makes high performance graph modeling more accessible by reducing reliance on energy-intensive computation.
Limitations of our work: From a representational prospective, our space of functions is smaller than TensorFlow's ss as our DAG must be a linear transformation of its input matrices, e.g., unable to encode demment-wise transformations and hence demanding first-order linear approximation of models. As result, our gradient-free learning can be performed using SVD. Further, our framework only works when the leaf nodes (e.g., sparse adjacency matrix) fit in memory of one machine.
Possible societal impacts: First, our convexified models directly learn parameters in the feature space i.e. they are more explainable than deeper counterparts. Explainability a double-edged sword: it gives better ability interpret the model's behavior, but also allows for malicious users, e.g., to craft attacks on the system (if they can replicate the model parameters). Further, we apply our method on graphs. It is possible train our models detect sensitive attributes of social networks (e.g.. ethnicity). However, such ethical concerns exists with any modeling technique over graphs.
Acknowledgments and Disclosure of Funding
This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) and the Army Contracting Command- Aberdeen Proving Grounds (ACC-APG) under
Contract Number W911NF-188 18-N--18--00000
10

---

References
Martín Abadi, Ashish Agarwal, et TensorFlow: Large-scale machine learning on heterogeneous systems. In USENIX Symposium on Operating Systems Design and Implementation, OSDI, pages 265-283, 2016.
Sami Abu-aa-Haija, Bryan Perozzi, Rami AI-Rfou, and Alexander A Alemi. Watch your step: Learning node embeddings via graph attention. In Advances in Neural Information Processing Systems, NeurIPS, 2018.
Sami Abujal-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional archi- tectures via sparsified neighborhood mixing. In International Conference Machine Learning. ICML, 2019.
Rami AI-Rfou, Guillaume Alain, and others. Theano: A Python framework for fast computation of mathematical expressions. arXiv e-prints, org/abs/1605. 0001//668000088888
May 2016. /tttt/////arxx
L. Backstrom, Boldi, M. Rosa, Ugander, and S Vigna. Four degrees of separation. In ACM Web Science Conference, pages 33 33-42, 2012.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. In Neural Computation, pages 1373-1396, 2003.
Aritra Bose, Vassilis Kalantzis, Eugenia-Maria Kontopoulou, Mai Elkady, Peristera Paschou, and Petros Drineas. Terapea: a fast and scalable software package to study genetic variation in tera-scale genotypes, 2019.
D. Calvetti, L. Reichel, and D.C. Sorensen. An implicitly restarted lanczos method for large symmetric eigenvalue problems. In Electronic Transactions on Numerical Analysis, pages 1-21, 1994.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representation, 2018.
Ming Chen. Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, (CML,22000
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer, and Richard Harshman. Indexing by latent semantic analysis. In Journal of the American Society for Information Science, pages 391 397,407, 1990.
C. Eckart and G. Young. The approximation of one matrix by another of lower rank. In Psychometrika, pages 21 211-218, 1936.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Gene H. Golub and Charles F. Van Loan. Mairix Computations, pages 257-258. John Hopkins University Press, Baltimore, 3rd edition, 1996.
Aditya Grover and Jure Leskovec. Node2vec: Scalable feature learning for networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, pages 855 864,864,22 2016.
N Halko, Martinsson P. G., and A Tropp. Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions. In ACM Technical Reports, 2009.
Olivia Hsu and Chuanqi Chen. Cs224w project: The study drug-drug interaction learning through
various graph learning methods, 2021. URL https:///tttttbbbbbb homphhu..ooooocoeooooaaaa....eoe http:/chuaqqiiiccc chen httpeiiittttettt___eeeeeeee blob/main/ ttee study_uduaa. of _drug_uuruuuu wtw.://www...ggg...atraaoooooooo
wtw.ogg.tttooooo......... various.
graph_learne www.eeennnneeeoodssseseeeeesseee

---

Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv, 2020.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models out-performs graph neural networks. In International Conference on Learning Representations, 2021. URL https::/ http://pppeaeeeeeeeeeeeeeeeenodd
T. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, ICLR, 2017.
Y. Koren, R. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. In IEEE Computer, page 30-37, 2009.
Chris Lattner, Mehdi Amini, Uday Bondhugula, Albert Cohen, Andy Davis, Jacques Arnaud Pienaar, River Riddle, Tatiana Shpeisman, Nicolas Vasilache, and Oleksandr Zinenko. Mlir: Scaling compiler infrastructure for domain specific computation. In CGO 2021, 2021.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http
7/ //snap. stanford. edu/data, June 2014.
Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. In Advances in Neural Information Processing Systems, NeurIPS, pages 2177-2185, 2014.
Omer Levy, Yoav Goldberg, and Ido Dagan. Improving distributional similarity with lessons learned from word embeddings. In TACL., 2015.
Yi Luo, Aiguo Chen, Bei Hui, and Ke Yan. demory-associaae differential learning, 2021.
Elan Sopher Markowitz, Keshav Balasubramanian, Mchrnoosh Mirtaheri, Sami Abu-El-Haija, Bryan Perozzi, Greg Ver Steeg, and Aram Galstyan. Graph traversal with tensor functionals: A meta- algorithm for scalable learning. International Conference on Learning Representations, ICLR, 2021.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems, NeurIPS, pages 311 1-3119, 2013.
F. Molteni, R. Buizza, T.N. Palmer, and T. Petroliagis. The ecmwf ensemble prediction system: Methodology and validation. Quarterly Journal of the Royal Meteorological Society, pages 73-119, 1996.
Mengyang Niu. Gat+llabel-reuse+ttopp loss ogb submission. In Gitflub, 2020. URL https http:///wwrgaaaaaa//////eeeeraaa
Adam Paszke, Sam Gross, Francisco Massa, and Others. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems, 2019.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In ACM SIGKDD international conference on Knowledge discovery and data mining, KDD, pages 701-710, 2014.
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. Global attention improves graph networks general- ization, 2020.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang. and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In International Conference Web Search and Data Mining, WSDM, pages 459-467, 2018.
Shunli Ren. Gat(norm.adj.) label reuse + self kd for orbi-arxiv. GitHuh, 2020. URLptttp wtatbbcco//hhnneeeinn
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, pages 1958, 2014.
12

---

Chuxiong Sun and Guoshi Wu. Adaptive graph diffusion networks with hop-wise attention, 2020.
M. Turk and A. Pentland. Eigenfaces for recognition. In Journal of Cognitive Neuroscience, pages 71-86, 1991.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, ICLR, 2018.
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propaga- tion, 2020.
Yangkun Wang. Bag of tricks of sumi-suue classification with graph neural networks, 2021.
Kesheng Wu and Horst Simon. Thick-restart lanczos method for large symmetric eigenvalue problems. In SIAM Journal on Matrix Analysis and Applications, pages 602-616, 2000.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference Machine Learning, ICML,, pages 5453 5453-5462, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, ICLR, 2019.
Yichen Yang, Lingjue Xie, and Fangchen Li. Global and local -ooomeett-wwrr graph convolution networks, 2021. URL /tt/sttt::///iiuuuu.
www.//o////eef////eeeeee wwtp///efeleeetty//224400--- OGB DEA- JK/ JK/blob/main/
CS224a_ final, weail_reportppp. pdf
Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. International Conference on Machine Learning, 2016.
Hanqing Zeng. Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. In International Conference Learning Representations, 2020.
13


Reviews:
[{"review_id": "erIHnstFqgh", "reviewer": "Reviewer_bCFd", "summary": "The goal of this paper is to speed-up graph representational learning by removing \nnonlinearities between layers and replacing them with linear models while also \nreplacing cross entropy by Frobenius norm minimization. In turn, this allows the \napplication of SVD, and the authors suggest modifications of randomized SVD \nwhich execute faster and in a matrix-free manner. The above approach is reported \nto be much faster than previous state-of-the-art, even though it is required to post-process \nthe obtained model by feeding it as an initial guess to a more expensive, but also \nmore accurate, approach. ", "questions": "", "limitations": "", "rating": 6, "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": "\n-) The paper is fairly well-written.\n\n-) For most part, the concepts presented are in a clear manner although the paper is \ncrowded with equations and side-information. \n\n-) I am not sure about whether the authors claim that the their orthonormalization approach \nis new or they just use it to speed-up the QR part in randomized SVD. If the former is the \ncase, then it is not a new idea. In fact, it is a well-known \"trick\", see for example\n\nhttps://www.sciencedirect.com/science/article/pii/S0010465510000524\n\nDo the authors use a different approach? If so, can they elaborate more on how exactly they \nreplace standard QR?\n\n-) In addition to the above remark, using the Cholesky factorization squares the condition \nnumber of the matrix whose columns are orthonormalized (i.e., normal equations). In fact, \nI am actually surprised that the authors didn't mention this, since my understanding is that \nthey use the \"subspace iteration\" version of randomized SVD. \n\n-) Moreover, matrix-free SVD is not a new thing -- in fact several approaches exist, see for example\n\nhttps://academic.oup.com/bioinformatics/article/35/19/3679/5430929?login=true\n\nI understand that the authors refer to their own approach of doing this, but some citations \non the topic need be provided. \n\n-) The experiments paint a nice picture, and they indeed show that the suggested hybrid \napproach is a good alternative. Nonetheless, my impression is that the proposed hybrid \napproach is more costly in terms of memory. Is this the case? If so, then I wonder \nwhether the proposed approach is useful for large graphs with millions/tens of millions of \nnodes. Note that using less nodes with more edges is not as important as very large and very \nsparse graphs. What is the execution time then? Can the authors provide experiments on \ngraphs with millions of nodes? Alongside memory costs for each method? This would be \nvery helpful.\n\n-) How do you set the number of leaf nodes?\n\n-) A '.' is missing at the end of line 285.\n\n-) \"decompose exactly M without calculating it\" -> \"decompose M exactly without explicitly calculating it.\"\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "M8hmKePEq3w", "reviewer": "Reviewer_NLBE", "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.", "questions": "", "limitations": "", "rating": 9, "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": "The work presented warrants dissemination as it is an original approach to tackle ML problems on large datasets. \nThe 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. \nFurther 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.\n\n### After the authors' responses\nMany 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.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do address the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "1xTzdpgt8BY", "reviewer": "Reviewer_L58o", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "\\textbf{Strength}: \nAuthors open-source a software library that allows symbolic definition of matrices and computing their SVD efficiently without explicitly calculating them. \\\\\nAuthors 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.\\\\\nConvexified model parameters from SVD can initialize deeper models which can be fine-tuned via cross-entropy over GRL tasks.\n\n\n\\textbf{Weakness}:\nFirst, it would be great if the authors could discuss about the proposed method's computational complexity when dealing with huge graphs.\\\\\nNext, 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)?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors have discussed the limitations and societal impacts in the Conclusion Section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

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)