Fast Graph Learning with Unique Optimal Solutions
This work addresses efficiency issues for practitioners in graph learning, though it is incremental as it builds on existing methods with simplifications.
The paper tackles the problem of slow training in graph representation learning by linearizing popular models and using Frobenius norm minimization to enable closed-form solutions, achieving competitive performance with orders of magnitude speedup.
We consider two popular Graph Representation Learning (GRL) methods: message passing for node classification and network embedding for link prediction. For each, we pick a popular model that we: (i) linearize and (ii) and switch its training objective to Frobenius norm error minimization. These simplifications can cast the training into finding the optimal parameters in closed-form. We program in TensorFlow a functional form of Truncated Singular Value Decomposition (SVD), such that, we could decompose a dense matrix $\mathbf{M}$, without explicitly computing $\mathbf{M}$. We achieve competitive performance on popular GRL tasks while providing orders of magnitude speedup. We open-source our code at http://github.com/samihaija/tf-fsvd