Fast Graph Learning
with Unique Optimal Solutions

SVD of $\mathbf{M}$ yields its left and right singular orthonormal (basis) vectors, respectively, in columns of $\mathbf{U}$ and $\mathbf{V}$. Since $\mathbf{U}$ and $\mathbf{V}$, respectively, are the eigenvectors of $\mathbf{M}\mathbf{M}^{\top}$ and $\mathbf{M}^{\top}\mathbf{M}$, then perhaps the most intuitive algorithms for SVD are variants of the power iteration, including Arnoldi iteration (Arnoldi, 1951) and Lanczos algorithm (Lanczos, 1950). In practice, randomized algorithms for estimating SVD run faster than these variants, including the algorithm of Halko et al. (2009) which is implemented in scikit-learn. None of these methods require individual access to $\mathbf{M}$’s entries, but rather, require two operations: ability to multiply any vector with $\mathbf{M}$ and with $\mathbf{M}^{\top}$. Therefore, it is only a practical gap that we fill in this section: we open-source a TensorFlow implementation that accept product and transpose operators.

Since we do not explicitly calculate the $\widehat{\mathbf{M}}$ matrices displayed in Equations 6 and 10, as doing so consumes quadratic memory $\mathcal{O}(n^{2})$, we implement a functional form SVD of the celebrated randomized SVD algorithm of Halko et al. (2009). To run our Algorithm 1, one must specify $k\in\mathbb{N}_{+}$ (rank of decomposition), as well as functions $f,l,s$ that the program provider promises they operate as:

1. 1.

   Product function $f$ that exactly computes $f(\mathbf{v})=\langle\mathbf{M},\mathbf{v}\rangle$ for any $\mathbf{v}\in\mathbb{R}^{c}$ (recall: $\mathbf{M}\in\mathbb{R}^{r\times c}$)

2. 2.

   Transpose¹¹1An alternative to $t$ can be a left-multiply function $l(\mathbf{u})=\langle\mathbf{u},\mathbf{M}\rangle$, however, in practice, TensorFlow is optimized for CSR matrices and computationally favors sparse-times-dense function $t$. $\forall\mathbf{v}\in\mathbb{R}^{r}$, $(t\circ f)(\mathbf{v})=\langle\mathbf{M}^{\top},\mathbf{v}\rangle$

3. 3.

   Shape (constant) function $s$ that knows and returns $(r,c)$. Once transposes, should return $(c,r)$.

We apply our functional SVD on popular datasets that can be trained using our simplified (i.e., convexified) models. Specifically either (1) semi-supervised node-classification datasets, where features are present, or (2) link-prediction datasets where features are absent. It is possible to convexify other setups, e.g., link prediction when node features are present, but we leave this as future work. We run experiments on seven graph datasets:

• •

  Protein-Protein Interactions (PPI): a large graph where every node is a protein and an edge between two nodes indicate that the two proteins interact. Processed version of PPI was downloaded from (Grover & Leskovec, 2016).

• •

  Three citation networks that are extremely popular: Cora, Citeseer, Pubmed. Each node is an article and each (directed) edge implies that an article cites another. Additionally, each article is accompanied with a feature vector (containing NLP-extracted features of the article’s abstract), as well as a label (article type).

• •

  Two collaboration datasets: ca-AstroPh and ca-HepTh, where nodes are researchers and an edge between two nodes indicate that the researchers co-published together at least one article, in the areas Astro-Physics and High Energy Physics.

• •

  ego-Facebook: an ego-centered social network.

For citation networks, we processed node features and labels. For all other datasets, we did not process features during training nor inference. For train/validation/test partitions: we used the splits of Yang et al. (2016) for Citeseer, Cora, Pubmed; we used the splits of Abu-El-Haija et al. (2018) for PPI, Facebook, ca-AstroPh and ca-HepTh; we used the splits of OGB (Hu et al., 2020) for ogbl-ddi. All datasets and statistics are summarized in Table 2. In §B.2 and §B.3, unless otherwise noted, we download authors’ source code from github, modify⁴⁴4Modified files are in our code repo it to record wall-clock run-time, and run on GPU NVidia Tesla k80. Thankfully, downloaded code has one script to run each dataset, or hyperparameters are clearly stated in the source paper.

We consider a transductive setting where a graph is entirely visible (all nodes and edges). Additionally, some of the nodes are labeled. The goal is to recover the labels of unlabeled nodes. All nodes have feature vectors.

Baselines: We download code of GAT (Veličković et al., 2018), MixHop (Abu-El-Haija et al., 2019), GCNII (Chen et al., 2020) and re-ran them, with slight modifications to record training time. However, for baselines Planetoid (Yang et al., 2016) and GCN (Kipf & Welling, 2017), we copied them from the GCN paper (Kipf & Welling, 2017).

In these experiments, to train our method, we run our functional SVD twice per graph. We take the feature matrix $\mathbf{X}$ bundled with the datasets, and concatenate to it two matrices, $\widehat{\mathbf{L}}$ and $\widehat{\mathbf{R}}$, calculated per Equation 8: the calculation itself invokes our functional SVD (the first time) on $f_{\widehat{\mathbf{M}}^{\textrm{(WYS)}}}$ with rank $=32$. Hyperparameters of $f_{\widehat{\mathbf{M}}^{\textrm{(WYS)}}}$ are $\lambda$ (negative coefficient) and $C$ (context window-size). After concatenating $\widehat{\mathbf{L}}$ and $\widehat{\mathbf{R}}$ into $\mathbf{X}$, we PCA the resulting matrix to 1000 dimensions, which forms our new $\mathbf{X}$. Finally, we express our model as the linear $L$-layer messaging passing network (Eq. 10) and learn its parameters via rank $k$ SVD on $f_{\widehat{\mathbf{M}}^{\textrm{(JKN)}}}$ (the second time), as explained in §3.2. We use the validation partition to tune $L$, $k$, $\lambda$, and $C$.

Table 1 (left) summarizes the performance of our approach ($f_{\widehat{\mathbf{M}}^{\textrm{(JKN)}}}$) against aforementioned baselines, showing both test accuracy and training time. While our method is competitive with state-of-the-art, it trains much faster.

Given a partial graph: only of a subset of edges are observed. The goal is to recover unobserved edges. This has applications in recommender systems: when a user expresses interest in products, the system wants to predict other products the user is interested in. The task is usually setup by partitioning the edges of the input graph into train and test edges. Further, it is common to sample negative test edges e.g. uniformly from the graph compliment. Lastly, a GRL method for link prediction can be trained on the train edges partition, then can be asked to score the test partition edges versus the negative test edges. The quality of the scoring can be quantified by a ranking metric, e.g., ROC-AUC.

Baselines: We download code of WYS (Abu-El-Haija et al., 2018) and update it to for TensorFlow-2.0. We download code of Qiu et al. (2018) and denote their methods as NetMF and $\widetilde{\textrm{NetMF}}$, where the first computes complete matrix $\mathbf{M}$ before SVD decomposition and the second sample $\mathbf{M}$ entry-wise – the second is faster for larger graphs but sacrifices on estimation error and performance. For node2vec (n2v), we use its PyG implementation (Fey & Lenssen, 2019).

Table 1 (right) summarizes results test ROC-AUC. For our method (denoted $f_{\widehat{\mathbf{M}}^{\textrm{(WYS)}}}$), we call our functional SVD (Alg. 1) and pass it $f_{\widehat{\mathbf{M}}^{\textrm{(WYS)}}}$ as defined in Eq. 14. Embeddings are set to the SVD basis (as in, §3.1) and edge score of nodes $(u,v)$ is $\propto$ dot-product of embeddings. The last row of the table shows results when svd rank $=$100. Lastly, we set the context window hyperparameter (a.k.a, length of walk) as follows. For WYS, we trained with their default context (as WYS learns the context), but for all others (NetMF, n2v, ours) we used context window of length $C$=5 for datasets Facebook and PPI (for us, this sets $\mathbf{c}=[5,4,3,2,1]$) and $C$=20 for AstroPh and HepTh.

While in §B.2 we tune the number of layers ($L$) using the performance on the validation partition, in this section, we show impact of varying $L$ on test accuracy. According to the summary in Figure 2 (left), accuracy of classifying a node improves when incorporating information from further nodes. We see little gains beyond $L>6$. Note that $L=0$ corresponds to ignoring the adjacency matrix altogether when running $f_{\widehat{\mathbf{M}}^{\textrm{(JKN)}}}$. Here, we fixed $\lambda=C=1$ and averaged 5 runs. The (tiny) error bars show the standard deviation.

Further, while in §B.3 we do SVD on $f_{\widehat{\mathbf{M}}^{\textrm{(WYS)}}}$ with rank $k=32$ or $k=100$, Figure 2 (right) shows test accuracy while sweeping $k\leq 32$. In general, increasing the rank improves estimation accuracy and test performance. However, if $k$ is larger than the inherit dimensionality of the data, then this could cause overfitting (though perfect memorization of training edges). The Norm Regularization note (§A.3.1) applies only to pseudoinversion i.e. our classification models.