Implicit SVD for Graph Representation Learning

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 \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

References in corpus (10)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
• Fast Graph Representation Learning with PyTorch Geometric
• Representation Learning on Graphs with Jumping Knowledge Networks
• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• Simple and Deep Graph Convolutional Networks
• Watch Your Step: Learning Node Embeddings via Graph Attention
• Combining Label Propagation and Simple Models Out-performs Graph Neural Networks
• Unifying Graph Convolutional Neural Networks and Label Propagation
• Global Attention Improves Graph Networks Generalization