Implicit SVD for Graph Representation Learning
  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 \textit{implicitly} defined matrices, and apply this framework to
several GRL tasks. For each task, we derive linear 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 procedure
trains hundreds of times faster than state-of-the-art methods, while competing
on empirical test performance. We open-source our implementation at:
https://github.com/samihaija/isvd
