InstantEmbedding: Efficient Local Node Representations
Authors: Stefan Postavaru
Anton Tsitsulin
Filipe Miguel Goncalves de Almeida
Yingtao Tian
Silvio Lattanzi
Bryan Perozzi
Venue:  (2021)
Keywords: Node Embedding
Structural Graph Representations
Graph Embedding
Local Algorithms

Abstract: In this paper, we introduce InstantEmbedding, an efficient method for generating single-node representations using local PageRank computations.  We prove that our approach produces globally consistent representations in sublinear time. We demonstrate this empirically by conducting extensive experiments on real-world datasets with over a billion edges. Our experiments confirm that InstantEmbedding requires drastically less computation time (over 9,000 times faster) and less memory (by over 8,000 times) to produce a single node’s embedding than traditional methods including DeepWalk, node2vec, VERSE, and FastRP. We also show that our method produces high quality representations, demonstrating results that meet or exceed the state of the art for unsupervised representation learning on tasks like node classification and link prediction.

Under review as a conference paper at ICLR 2021
INSTANTEMBEDDING:
EFFICIENT LOCAL NODE REPRESENTATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, introduce InstantEmbedding, efficient method for generating single-node representations using local PageRank computations. We theoretically prove that our approach produces globally consistent representations in sublinear time. We demonstrate this empirically by conducting extensive experiments on real-world datasets with over billion edges. Our experiments confirm that Instant- Embedding requires drastically less computation time (over 9,000 times faster) and less memory (by over 8,000 times) to produce single node's 's embedding than traditional methods including DeepWalk, node2vec, VERSE, and FastRP. We also show that our method produces high quality representations, demonstrating results that meet or exceed the state of the art for unsupervised representation learning on tasks like node classification and link prediction.
INTRODUCTION
Graphs are widely used represent data when are objects connected to each other, such social networks, chemical molecules, and knowledge graphs. A widely used approach in dealing with graphs is learning compact representations of graphs (Perozzi et al. 20144, Grover & Leskoved 2016 Abu-El-Haija et al. 2018), which learns a d-dimensional embedding vector for each node in a given graph. Unsupervised embeddings in particular have shown improvements in many downstream machine learning tasks, such as visualization (Maaten & Hinton 2008), node classification (Perozzi al. 2014) and link prediction (Abu-El-Haija et al.] 2018). Importantly, since such embeddings are learned solely from the structure of the graph, they can be used across multiple tasks and applications.
Typically, graph embedding models often assume that graph data fits in memory (Perozzi al. 2014 4) and require representations for all nodes to be generated. However, in many real-world applications, often the case that graph data is large but also scarcely annotated. For example, the Friendster social graph (Yang & Leskovee 2015) has only 30% nodes assigned to community, from its total 65M entries. At the same time, many applications of graph embeddings such as classifying a data item only require one current representation for the item itself, and eventually representations of labeled nodes. Therefore, computing a full graph embedding is at worst infeasible and at best inefficient.
These observations motivate the problem which we study in this paper- the Local Node Embedding problem. In this setting, the embedding for a node is restricted to using only local structural infor- mation, and can not access the representations of other nodes in the graph or rely on trained global model state. In addition, we require that a local method needs to produce embeddings which are consistent with all other node's 's representations, so that the final representations can be used in the same downstream tasks that graph embeddings have proved adapt at in the past.
In this work, we introduce InstantEmbedding, an efficient method to generate local node embeddings on the fly in sublinear time which are globally consistent. Considering previous work that links embedding learning methods to matrix factorization (Tsitsulin et al. 2018 Qiu et al.) 2018), our method leverages high-order similarity matrix based on Personalized PageRank (PPR) as foundations on which local node embeddings are computed via hashing. We offer theoretical guarantees on the locality of the computation, as well as the proof of the global consistency of the generated embeddings. We show empirically that our method is able to produce high-quality representations on par with state of the art methods, with efficiency several orders of magnitude better in clock time and memory consumption: running 9,000 times faster and using 8,000 times less memory on the largest graphs that contenders can process.

---

Under review as a conference paper at ICLR 2021
Table 1: Related work in terms of desirable properties and the computational complexity necessary to generate a single node embedding. Note that all existing methods must generate full graph embedding, and thus are directly dependent on the total graph size, while our method can directly solve this task in sublinear time. Analysis in Section 3.2.
Properties
Complexities
method
Local Inference
Global Training
Unsupervised Embedding
Attribute- Free
Time ?
Memory
DeepWalk
dn log n dbn. dbn
dn + m n
node2vec
X
x
VERSE
X
X
V
dn
FastRP
dm on/n
dn + m
GCN
X
X
X
dm
dn
DGI
dm
dn + m
InstantEmbedding
d
a m(I-a) +
of m(l-
PRELIMINARIES & RELATED WORK
2.1 GRAPH EMBEDDING
n. and edges Let = (V, represent an unweighted graph, which contains set nodes V, |V| A graph can also be represented as adjacency matrix A E (0, | where Au, iff v) E F. The task of graph embedding then, learn d-dimensional node embedding matrix X Raxd where X, serves as the embedding for any node v E V. We note that d < i.e. the learned representations are low-dimensional, and the challenge of graph embedding is to best preserve graph properties (such as node similarities) in this space. Following the formalization in Abu-EEl et al. (018). many graph embedding can be thought of minimizing objective in the general form: minx ((f(X)g(( (A)), where f RR x + pa*x" a pairwise distance function the (possibly transformed)
EC (V V). E
on the embedding space, g nx Rax is distance function adjacency matrix, and I a loss function over all (u, v) E (V x V) pairs.
A number of graph embedding methods have been proposed. One family of these methods simply
learn X as lookup dictionary of embeddings and calculate the loss via distance (Kruskal 1964). or
matrix factorization (either implicit (Perozzi al. 2014 Grover Leskoved (016) or explicit (Oul
et al. 2016)). Another line of work focuses on leveraging the graph structure using neighborhood
aggregation (Battaglia et al.) 2016 Scarselli al. 2008). or the Laplacian matrix of the graph (Kipf
& Welling 2016). On attributed structured data, Graph Convolutional Networks (Kipf & Welling 2016) have been successfully applied both supervised and unsupervised tasks (Veličković et al.
2018). However, in the absence of node-level features, Duong et al. (2019) demonstrated that these methods do not produce meaningful representations.
Graph Embedding via Random Projection The computational efficiency brought by advances random projection (Achlioptas) 2003 Dasgupta et al., 2010) paved the way for its adaptation in graph embedding allow direct construction of the embedding matrix X. Two recent works, RandÑE (Zhang et al.||2018) and FastRP (Chen et al. 2019) iteratively project the adjacency matrix to simulate the higher-order interactions between nodes. As show the experiments, these methods suffer from high memory requirements and are not always competitive with other methods.
2.2 LOCAL ALGORITHMS ON GRAPHS
Local algorithms on graphs (Suomela 2013) solve graph without using the full graph. A well- studied problem in this space is personalized recommendation (Jeh Widom, 2003) where users are represented nodes in graph and the goal is to recommend items to specific users leveraging the graph structure. Classic solutions to this problem are Personalized PageRank (Gupta et al., (2013) and Collaborative Filtering (Schafer et al. 2007; He al. 2017). Interestingly, these methods have been recently applied to graph neural networks (Klicpera et al. (2199] He et al.) 2020). We now recall the definition of Personalized PageRank that one of the main ingredients in embedding algorithm.
2

---

Under review as a conference paper at ICLR 2021
Definition (Personalized PageRank (PPR, variation)). Given R" (s, o. a distribution of the starting node of random walks, and a E (0, 1), a decay factor, the Personalized PageRank vector T(s) E Iº is defined recursively
((s) as + +1- ( (1+D-1A)
where ) +L++D-AA is the lazy random-walk matrix.
PPR takes as input a distribution of starting nodes s, which is typically a dimensional one-hot vector e, with 1 in the i-th coordinate, enforcing a local random walks starting from node i. Following this practice, we denote म. E RR", the PPR vector starting from a single node i, and PPR E RR*". the full PPR matrix for all nodes in the graph, where PPR,, x (c.). VERSE (Tsitsulin et al. 2018) proposes to learn node embeddings by implicitly factorizing PPR. Its stochastic approach can perform well, but lacks guarantees of stability and convergence. The idea of learning embeddings based on local random walks has also been used in the property testing framework, a direction in graph algorithm aiming at analyzing the clustering structure of a graph (Kale & Seshadhri 20088 Czumaj & Sohler 2010; Czumaj et al. 2015 Chiplunkar et al. 2018).
2.3 PROBLEM STATEMENT
In this work, we consider the problem of embedding single node in graph quickly. More formally, we consider what we term the Local Node Embedding problem: given graph G and any node return a globally consistent structural representation for using only local information around v, in time sublinear to the size of the graph.
solution to the local node embedding problem should possess the following properties:
1. Locality. The embeddings for node are computed locally, i.e. the embedding for node can be produced using only local information and in time independent of the total graph size.
2. Global Consistency. A local method must produce embeddings that are globally consistent
(i.e. able to relate each embedding to each other, s.t. distances the space preserve proximity).
While many node embedding approaches have been proposed (Chen et al. 2018), to the best of our knowledge we are the first to examine the local embedding problem. Furthermore, no existing methods for positional representations of nodes meet these requirements. We briefly discuss these requirements in detail below, and put the related work in terms of these propertics in Table [
Locality. While classic node embedding methods, such as DeepWalk (Perozzi et al., 2014). node2vec (Grover & Leskovec 2016), or VERSE (Tsitsulin et al., 2018) rely on information ag- gregated from local subgraphs (e.g. sampled by random walk), they do not meet our locality requirement. Specifically, they also require the representations of all the nodes around them, resulting in dependency on information from all nodes in the graph (in addition to space complexity (nd) where d is the embedding dimension) to compute a single representation. Classical random- projecciin based methods also require access the full adjacency matrix in order to compute the higher-order ranking matrix. We briefly remark that even methods capable of local attributed subgraph embedding (such as GCN or DGI) also do not meet this definition of locality, as they require global training phase to calibrate their graph pooling functions.
Global Consistency. This property allows embeddings produced by local node embedding to be used together, perhaps as features in model. While existing methods for node embeddings are global ones which implicitly have global consistency, this property is not trivial for a local method to achieve. Specifically, a local method must produce node representation that resides in space, preserving proximities to all other node embeddings that may be generated, without relying on global state. One exciting implication of local method which is globally consistent is that it can wait compute a representation until it is actually required for a task. For example, in production system, one might only produce representations for immediate classification when they are requested.
We propose our approach satisfying these properties in Section 3 and experimentally validate it in Section 4 followed by conclusions in Section 5
3

---

Under review as a conference paper at ICLR 2021
3 METHOD
Here we outline our proposed approach for local node embedding. We begin by discussing the connection between recent embedding approach and matrix factorization. Then using this analysis, we propose an embedding method based on randomly hashing the PPR matrix. We note that this approach has a tantalizing property - can be decomposed into entirely local operations per node. With this observation in hand, we present our solution, InstantEmbedding. Finally, we analyze the algorithmic complexity of our approach, showing that is both a local algorithm (which runs time sublinear to the size of G) and that the local representations are globally consistent.
3.1 GLOBAL EMBEDDING USING PPR
A recently proposed method for node embedding, VERSE T'itsulin et al. 2018). learns node em- beddings using neural network which encodes Personalized PageRank similarities. Their objective function, in the form of Noise Contrastive Estimation (NCE) (Gutmann & Hyvärinen, 2010). is:
T1
PPR., log a (x|x,) + DE log (-x, x,))]
where PPR is the Personalized PageRank matrix, a is the sigmoid function, b is the number of negative samples, and 2/ is a uniform noise distribution from which negative samples are drawn. Like many SkipGram-style methods (Mikolov et al., 2013), this learning process can be linked to matrix factorization by the following lemma:
Lemma 3.1 (Tsitsulin et al. (2020)) VERSE implicitly factorizes the matrix log(
(PPR) +lgg) n- n- b into XX T where n is the number of nodes in the graph and b is the number of negative samples.
3.1.1
HASHING FOR GRAPH EMBEDDING
Lemma 3.1 provides an incentive to find an efficient alternative to factorizing the dense similarity matrix M log (oPR) +lg nog b. Our choice of the algorithm requires important properties: a) providing an unbiased estimator for the inner product, and b) requiring less than ((n) memory. The first property is essential ensure we have good sketch of M for the embedding, while the second one keeps our complexity per node sublinear.
In order meet both requirements we propose to use hashing (Weinberger et al. 2009) to pre- serve the essential similarities of PPR in expectation. We leverage two global hash functions ha: N {O...., d 1} and hagn N - 1- sampled from universal hash families Ua and U U-1,1 respectively, to define the hashing kernel Hha.heen IR" - Rd Applied to an input vector x, it yields h = H Auge (x), where h, = Σkeh (i) X4haan((k)
We note that although Hhg Argn is proposed for vectors, it can be trivially extended to matrix M when applied to each row vector that matrix, e.g. by defining H Ha,,. (M);, = Hha. (M.)). In the appendix we prove the next lemma that follows from (Weinberger et 2009) and highlights both the aforementioned properties:
Lemma 3.2. The space complexity of Haa.dign is (1) and:
Eng Uugnn 111 [Hag Rugg (M) H Hag (M) MM
This matrix sketching technique is strongly related to the factorization proposed in Lemma 3.1 To better understand this, we consider the approximation M UEUT, the (asymptotic) solution of VERSE is U. then our method aims to directly approximate US. We show that this rescaled solution is more computationally tractable, while still preserving critical information for high-quality node representations.
Our algorithm for global node embedding is presented in Algorithm I First, we compute the PPR matrix PPR (Line 2) with a generic approach (Create P.M.P..MMM.r atriz), which takes a graph and e, the desired precision of the approximation. We remark that any of the many proposed approaches for computing such a matrix (c.g. from Jeh & Widom (2003;; Andersen et al. (2007); Lofgrrn et al. (2014)) can be used for this calculation. As the PPR could be dense, the same could be said about the
4

---

Under review as a conference paper at ICLR 2021
implicit matrix M. Thus, we filter the signal from non-significant PPR values by applying the max operator. We remove the constant log from the implicit target matrix. In lines (4-6), the provided hash function accumulates each value in the corresponding embedding dimension.
Algorithm 1 Global Node Embedding using Personalized PageRank
Input: graph G, embedding dimension d, PPR precision e, hash functions has hagn
Output: emhedding matrix W
I: function GRAPHEMBEDDINGGG d, ha, Ragu)
2: PPR + CreatePPRMatrraal
3: W Onxd
4: for PPR. do
for Ty in m. do
6:
W (.A += hago (i) x max([og(r; * v))
7:
return W
Interestingly, the projection operation only uses information from each node's ' individual PPR vector to compute its representation. In the following section, we will show that local calculation of the PPR can be utilized to develop an entirely local algorithm for node embedding.
3.2 LOCAL NODE EMBEDDING VIA INSTANTEMBEDDING
Having local projection method, all that require is procedure that calculate the PPR vector for a node time sublinear to size of the graph. Specifically, for InstannEneedding we propose that the Create PP P.P.R. RMM atrix operation consists of invoking the Sparse PPR routine from Andersen et al. (Andersen et al. (007) once for each node This routine an entirely local algorithm for efficiently constructing m, the PPR vector for node i, which offers strong guarantees. The next lemma follows from (Andersen et al. 2007) and formalizes the result (proof in Appendix (A.4).
Lemma 3.3. The INSTANT ENTTANTEMBEDDINGCC G, d, e) algorithm computes the local embedding of a node e by exploring most the (V()))))) nodes the neighborkood of v.
We present InstantEmbedding, our algorithm for local node embedding, in Algorithm 2 will show, it is self-contained solution for the local node embedding problem that can generate embeddings for individual nodes extremely efficiently. Notably, per Lemma (3.3 the local area around explored by InstantEmbedding is independent of n. Therefore the algorithm is strictly local.
As we
Algorithm 2 InstantEmbedding
Input: node v, graph G, embedding dimension d, PPR precision e, hash functions hag hagn.
Output: embedding vector w
1: function INSTANTRMBEDDINGG;; G, e,,, hagn)
2: TTo < Sporse G,
3: w f 02
4: for ry n. do
Wha(s) += hega(j) (j) max(log(r) * v))
return w
3.2.1 ANALYSIS
We now prove some basic properties of our proposed approach. First, we show that the runtime of our algorithm is local and independent of n, the number of nodes in the graph. Then, we show that our local computations are globally consistent, i.e., the embedding of node e the same independently if we compute it locally or if we recompute the embeddings for all nodes in the graph at the same time. Note that we focus on bounding the running time to compute the embedding for a single node in the graph. Nonetheless, the global complexity to compute all the embeddings can be obtained by multiplying our bound by n, although it is not the focus of this work. We state the following theorem and prove it in Appendix A.5
Theorem 3.4. The Instant Embedding( G, d, c) algorithm has running time O (d + 1/(11o0)
5

---

Under review as a conference paper at ICLR 2021
Besides the embedding size d, both the time and and space complexity of our algorithm depend only on the approximation factor e and the decay factor a. Both are independent of n, the size of the graph, and m, the size of the edge set. Notably, if O (Va(1-a)e) E o(n), as commonly happen in real world applications, our algorithm has sublinear time w.r.t. the graph size. Lastly, we note that the space complexity is also sublinear (due to Lemma 3.3). which we show in the appendix.
Now we turn our attention to the consistency of our algorithm, by showing that for a node e the embeddings computed by Instant Embedding and GraphEmbeddinn are identical. In the fol- lowing we denote the graph embedding computed by Graph Embeddingg d, for node v by GraphEEmeadding(G. d, e)y, and we prove the following theorem (Appendix
Theorem 3.5 (Global Consistency). Inslant Beleddninne G, G, oulput equals one of GraphhEmedddigg. G, d, 6) at position
Complexity Comparison. Table I compares the complexity of InstantEmbedding with that of previ- ous works: d, n, m stands for embedding dimension, size of graph and number of edges respectively. Specifically, b stands for the number of samples used in node2vec and VERSE. It is noteworthy that all the previous works have time complexity depending on n, and perform at least linear w.r.t. size of the graph. In contrast, our algorithm depends only on e and a, and has sublinear time w.r.t. n, the graph size. In Section we experimentally verify the advantages of our principled method.
4 EXPERIMENTS
In the light of the theoretical guarantees about the proposed method, we perform extended experiments in order verify our two main hypotheses:
1. H1. Computing local node-embedding is more efficient than generating a global embedding.
2. H2. The local representations are consistent and of high-quality, being competitive with and even surpassing state-of-the-ee methods on several tasks.
We assess H1 in Section 4.2 in which we measure the efficiency of generating a single node embedding for each method. Then in Section 4.3 we validate H2 by comparing our method against the baselines on multiple datasets using tasks of node classification, link prediction and visualization.
4.1 DATASETS AND EXPERIMENTI SETTINGS
Table 2: Dataset attributes: size of ver- tices [V], edges [E], labeled vertices |S].
To ensure relevant and fair evaluation, we compare our method against multiple strong baselines, including Deep- Walk (Perozzi et al. (2014), node2vec (Grover & Leskovee
Dataset
[V]
E
|S|
2016). VERSE (Tsitsulin et al. 2018). and FastRP (Chen al. 2019). Each method was run a virtual machine hosted on the Google Cloud Platform, with a 2.3GHz 16- core CPU and 128GB of RAM. All reported results use dimensionality d = 512 for every method. We provide ex- tended results for additional baselines: RandNE: (Zhang et al.] (0118), NodeSketch (Yang et al.] [2019), LouvainNE [Bhowmick et al. 2020) and FREDE (Tsitsulin et al. 2020)
PPI
3.8k
38k
3.8k
BlogCatalog
10k
334k
10k
CoCit
44k
195k
44k
CoAuthor
52k
356k
Flickr
81k
5.9M
81k
YouTube
1.1M
3.0M
32k
Amazon2M
2.4M
62M
Orkut
3.0M
117M
110k
on a subset of tasks, along with full details regarding each
Friendster
66M
1806M
method and its parameterization in the Appendix B.I For reproducibility, we release an implementa-
tion of our method
InstantEmbedding Instantiation. As presented in Section 3 our implementation of the presented method relies on the choice of PPR approximation used. For instant single-node embeddings, the highly efficient PushFlow (Andersen et al. 2007) approximation that enables us to dynamically load into memory at most 2/(1-a), nodes from the full graph compute single PPR vector This is achieved by storing graphs in binarized compressed sparse row format that allows selective reads for nodes of interest. In the special case when full graph embedding is requested, have the freedom to approximate the PPR in a distributed manner (we omit this from runtime analysis, as
Software available for reviewers and ACs in the OpenReview forum.

---

Under review as a conference paper at ICLR 2021
DeepWalk
node2vec
VERSE
FastRP
InstantEmbedding (ours)
107
logisccom))
(ug(MB
104
108
10a
9000
108
109
10a
6000
10-2
10
1110
10a
10
107
10
10
10
10
107
10
10P
[e) (a) Running Time
logtl BI)
(b) Memory Usage
Figure 1: Required (a) running time and (b) memory consumption to generate a node embedding (d=512) based on the edge count of each graph (E)). with the best line fit drawn. Our method is over 9,000 times faster than FastRP and uses over 8,000 times less memory than VERSE, the next most efficient baselines respectively, in the largest graph that these baseline methods can process.
we had no distributed implementations for the baselines, but note our local method is trivially parallelizable). We refer to Appendix B.3 for the study of the influence of e on runtime and quality.
Datasets. We perform our evaluations on 10 datasets as presented in Table 2 Detailed descriptions, scale-free and smrld-world measurements for these datasets are available in the supplementary material. Note that YouTube and Orkut the number of labeled nodes is much smaller than the total. We observe this behavior in several real-world application scenarios, where our method shines the most.
4.2 PERFORMANCE CHARACTERISTICS
We report the mean wall time and total memory consumption (Wolif) required to generate an embedding (d=512) for single node in the given dataset. Note that due to the nature of all considered baselines, they implicitly have to generate full graph embedding in order to get a node representation. We repeat the experiment 1,000 times for InstantEmbedding due to its locality property; for the baselines, average the running time from 5 experiments, and measure the memory usage once. For reference, we also provide the performance of InstantEmbedding producing a full graph embedding in Appendix B.3
Running Time. As Figure I a) shows, InstantEmbedding is the most scalable method, drastically outperforming all the other methods, the task of producing single node embedding. We are over 9,000 times faster than the next fastest baseline in the largest graph both methods can process, and scale graphs of any size.
Memory Consumption.Ar As Figure [b) shows, InbeannEnb is the most efficient method having been able run in all datasets using negligible memory compared to the other methods. Compared to the next most memory-efficient baseline (VERSE) we are over 8,000 times more efficient in the largest graph both methods can process.
The results of running time and memory analysis confirm hypothesis H1 and show that Instant- Embedding has a significant speed and space advantage versus the baselines. The relative speedup continues to grow as the size of the datasets increase. On dataset with over billion edges (Friend- ster), we can compute node embedding in 80ms fast enough for real-time application!
4.3 EMBEDDING QUALITY
Node Classification. This task measures the semantic information preserved by the embeddings by training a simple classifier on a small fraction of labeled representations. For each method, we perform three different random splits of the data. More details available in the Appendix [B.4
In Table 3 we report the mean Micro Fl scores with their respective confidence intervals (corre- sponding Macro-F1 scores in the supplementary material). For each dataset, perform Welch's
7

---

Under review as a conference paper at ICLR 2021
Table
Average Micro-F1 classification scores and confidence intervals. Our method is marked as follows: above baselines; bold no other method is statistically significant better.
Method \ Dataset
PPI
BlogCatalog
CoCit
Flickr
YouTube
Orkut
DeepWalk
16.08 +: 0.64
32.48 + 0.35
37.44
0.67
31.22 +: 0.38
38.69
1.17
87.67 = 0.23
node2vec
15.03 +: 3.18
33.67
= 0,93
38.35
+:2 1.75
29.80
+ 0.67
36.02
+: 2.01
DNC
VERSE
12.59 + 2.54
24.64
+ 0,85
38.22
+:2 1.34
25.22
+ 0.20
36.74
1.05
81.52 = 1.I1
FastRP
15.74 + 2.19
33.54
0.96
26.03
2.10
29.85
+ 0.26
22.83
0.41
DNC
InstamLEmbedding 17.67* 1.22
33.36
0.67
39.95
0.67
30.43 + 0.79
40.04*
0.97
76.83 1.16
Table 4: Average ROC-AUC scores and confidence intervals for the link prediction task. Our method marked as follows: * above baselines; bold no other method statistically significant better.
Method \
Dataset
CoAuthor
Blogcatalog
Youtube
Amazon2M
DeepWalk
88.43 i: 1.08
91.41 067
82.17 1: 1.02
98.79 1 0.41 DNC 99.67 1 0.18
node2vec
86.09 0.85
92.18
0.12
81.27 1.58
VERSE
92.75 1 0.73
93.42 0.35
80.03 1: 0.99
FastRP
82.19 + 2.22
88.68 = 0,70
76.30 + 1.45
92.12 + 0.61
InstantEmhecdding
90.44 1: 0.48
92.74 0.60
82.89 1:: 0.83
99.15 1: 0.18
I-test between our method and the best performing contender. We observe that Instantmbeddding remarkably good on these node classification, despite its several approximations and locality restriction. Specifically, on four out of five datasets, no other method is statistically significant above ours, and three of these (PPI, CoCit and YouTube) we achieve the best classification results.
In Figure 2 we study how our hyperparameter, the PPR approximation error e, influences both the classification performance, running time, and memory consumption. There is general sweet spot (around c 10-5) across datasets where InstantEmbedding outperforms competing methods while being orders of magnitude faster. Data on the other datasets is available in Section B.5
InstantEmbedding (ours)
DeepWalk
node2vec
VERSE
FastRP
10
10a
Micn-FI
Log (
Log (MTB)
10a
10a
30
20
10
10
111
10
10
3
10
10
10
10
3
10
10
10
10
10
10
logle)
Togre)
Miem Seore
Running
Memory (MB)
Figure 2: The impact of the choice of the quality of the resulting embedding (through the Micro-F1 score), average running time and peak memory increase for the YouTube dataset.
Link prediction. We conduct link prediction experiments to assess the capability of the produced representations to model hidden connections in the graph. For the dataset which has temporal information (CoAuthor), we select data until 2014 as training data, and split co-authorship links between 2015-2016 in two balanced partitions that we use as validation and test. For the other datasets, we uniformly sample 80% of the available edges as training (to learn embeddings on), and use the rest for validation (10%) and testing (10%). Over repeated runs, vary the splits. More details about the experimental design are available the supplementary material. We report results for each method in in Table which shows average ROC-AUC and confidence intervals for each method. Across the datasets, our proposed method beats all baselines except VERSE, however we do achieve the best performance on YouTube by statistically significant margin.
Visualization. Figure 3
presents UMAP (Melnnes et al. 2018) projections on the CoCit dataset, where we grouped together similar conferences. We note that sublinear approach is especially
8

---

Under review as a conference paper at ICLR 2021
well suited to visualizing graph data, as visualization algorithms only require small subset of points (typically downsampling to only thousands) to generate a visualization for datasets.
The experimental analysis of node classification, link prediction, and visualization show that despite relying on two different approximations (PPR random projection), InstantEmeedding to very quickly produce representations which meet or exceed the state of the art in unsupervised representation learning for graph structure, confirming hypothesis H2. We remark that interestingly InstantEmbedding seems slightl better node classifications than link prediction. We suspect that the randomization may effectively act as a regularization which is more useful on classification.
able
(a) DeepWalk
(b) VERSE
(c) FastRP
(d) InstantEmbedding
Figure 3: UMAP visualization of CoCit (d=512). Research areas
ML,
DM,
DB, IR).
CONCLUSION
The present work has two main contribution: a) introducing and formally defining the Local Node Embedding problem and b) presenting InstantEmbedding, highly efficient method that selectively embeds nodes using only local information, effectively solving the aforementioned problem. As existing graph embedding methods require accessing the global graph structure at least once during the representation generating process, the novelty brought by Imbedingg is especially impactful in real-world scenarios where graphs outgrow the capabilities of single machine, and annotated data is scarce or expensive to produce. Embedding selectively only the critical subset of nodes for a task makes many more applications feasible in practice, while reducing the costs for others.
Furthermore, we show theoretically that our method embeds single node in space and time sublinear the size of the graph. We also empirically prove that EmbtdnnEmeedding capable of surpassing late--of-the-art methods, while being many orders of magnitude faster than them our experiments show that we are over 9,000 times faster on large datasets and on a graph over billion edges we can compute representation in 80ms.
REFERENCES
Microsoft academic graph (mag) kkd cup 2016. attps::/www.cdd.or///kkkko
Std--cup-206/Dattt 2016.
Sami Abu-El-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, pp. 9180-9190, 2018
Dimitris Achlioptas. Databsse-friendly random projections: Johnson--lindenstrauss with binary coins. Journal of computer and System Sciences, 66(4):671-687, 2003.
Reid Andersen, Fan Chung, and Kevin Lang. Using pagerank to locally partition a graph. Internet Mathematics, 4(1):35-64 2007.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. Advances neural information processing systems, pp. 4502-44 4510, 2016.
Ayan Kumar Bhowmick, Koushik Meneni, Maximilien Danisch, Jean-Loup Guillaume, and Bivas Mitra. Louvainne: Hierarchical louvain method for high quality and scalable network embedding. In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 43-51, 2020.

---

Under review as a conference paper at ICLR 2021
Haochen Chen, Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. A tutorial network embeddings. arXiv preprint arXiv: 180..02888002900 2018.
Haochen Chen, Syed Fahad Sultan, Yingtao Tian, Muhao Chen, and Steven Skiena. Fast and accu- rate network embeddings via very sparse random projection. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 399-409,999 2019.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2019. URL ROLLhttp:// htttp://web.cm
e data/ AmmaoonM. tar.aarr.. gz
Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres. Testing graph clusterability: Algorithms and lower bounds. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp- 497-508. IEEE, 2018.
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009.
Artur Czumaj and Christian Sohler. Testing expansion in bounded-degree graphs. Combinatorics, Probability and Computing, 19(5-6):693-709, 2010.
Artur Czumaj, Pan Peng, and Christian Sohler. Testing cluster structure of graphs. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pp. 723-732, 2015.
Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós. A sparse johnson: Lindenstrauss transform. In Proceedings of the forty-second ACM symposium Theory of computing, pp. 341-350, 2010.
Chi Thang Duong, Thanh Dat Hoang, Ha The Hien Dang, Quoc Viet Hung Nguyen, and Karl Aberer.
On node features for graph neural networks. arXiv preprint arXiv:1911.088 2019.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pp. 855- 864, 2016.
Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Zadeh. Wtf: The who follow service at twitter. In Proceedings of the 22nd international conference on World Wide Web, pp. 505-514, 2013.
Michael Gutmann and Aapo Hyvärinen. soise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 297-304, 2010.
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural col- laborative filtering. In Proceedings of the 26th international conference on world wide web, pp. 173-182, 2017.
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. arXiv preprint arXiv:2002.02126, 2020.
Glen Jeh and Jennifer Widom. Scaling personalized web search. In www, 2003.
Satyen Kale and C Seshadhri. Testing expansion in bounded degree graphs. 35th ICALP, 527-538, 2008
Thomas N Kipf and Max Welling, Semi- supervised classification with graph convolutional networks. arXiv preprint weo.:.290999 2016.
Johannes Klicpera, Alcksandar Bojchevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for classification on graphs. In International Conference Learning Representations, 2019.
Joseph B Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29(1):1-27, 1964.
10

---

Under review as a conference paper at ICLR 2021
Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. In Advances in neural information processing systems, pp. 2177-2185, 2014.
Peter A Lofgren, Siddhartha Banerjee, Ashish Goel, and C Seshadhri. Fast-ppr: Scaling personalized pagerank estimation for large graphs. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1436-1445, 2014.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(Nov):2579-2665) 2008
Leland McInnes, John Healy, Nathaniel Saul, and Lukas Großherger. Umap: Uniform manifold approximation and projection. Journal of Open Source Software, 2018.
Tomas Mikolov, llya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In C. J. C. Burges, L.. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26, pp. 3111-3119. 2013.
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserv- ing graph embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1105-1144 11,, 2016.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830. 2011.
Bryan Perozzi, Rami A1-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vee. In Proceedings of the Eleventh ACM International Conference on Web Seurch and Data Mining, pp. 459-467, 2018.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-88) 2008
J Ben Schafer, Dan Frankowski, Jon Herlocker, and Shilad Sen. Collaborative filtering recommender systems. In The adaptive web, pp. 291-324. Springer, 2007.
Chris Stark, Bobby-Joe Breitkreutz, Teresa Reguly, Lorrie Boucher, Ashton Breitkreutz, and Mike Tyers. Biogrid: a general repository for interaction datasets. Nucleic acids research, 34(suppL_); DS35-D539, 2006. https: //snap.////ppp.. st stanford.d.o.ooooo http://nodvveeeeeone wacpimoos_pppiiieee sapiens mat
Jukka Suomela. Survey of local algorithms. ACM Computing Surveys (CSUR), 45(2): 2013.
Lei Tang and Huan Liu. Social dimension approach to classification in large-scale networks. 2010. URL http://eeetaanneeeeesii..... dimens html
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller. Verse: Versatile graph embeddings from similarity measures. In Proceedings of the 2018 World Wide Web Conference, pp. 539-548, 2018.
Anton Tsitsulin, Marina Munkhoeva, Davide Mottin, Panagiotis Karras, Ivan Oseledets, and Em- manuel Müller. Frede: Linear-space anytime graph embeddings. arXiv preprint arXiv:2006.04746, 2020.
Petar Veličković, William Fedus, William I. Hamilton, Pietro Liò, Yoshua Bengio, and Devon Hjelm. Deep graph infomax. arXiv preprint 1t0i:::800.113411 2018.
Kilian Weinberger, Anirban Dasgupta. John Langford, Alex Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. In Proceedings of the 26th anmual international conference on machine learning, pp. 1113-1120, 2009.

---

Under review as a conference paper at ICLR 2021
Milian Wolff. heaptrack
A heap memory profiler for linux, 2018.
bttp:://github.comm/ httphhu...om//DDD
KDE/
Dingqi Yang, Paolo Rosso, Bin Li, and Philippe Cudre-Mauroux Nodesketch: Highly-efficient graph embeddings via recursive sketching. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1162-1172, 2019.
Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 42(1):181-21) 2015. https:/ snap
Orkut html
Ziwei Zhang, Peng Cui, Haoyang Li, Xiao Wang, and Wenwu Zhu. Billion-scale network embedding with iterative random projection. In 2018 IEEE International Conference Data Mining (ICDM), pp. 787-796. IEEE, 2018.
12

---

Under review as a conference paper at ICLR 2021
APPENDIX
A PROOFS
A. VERSE AS MATRIX FACTORIZATION
Lemma A.I. (restated from Tsitsulin al. (2020), (ref. Lemma 3.1)) VERSE implicitly factorizes the matrix log(PPR) + log n log b into XX where n is the number of nodes in the graph and b the number of negative samples.
Proof. (from Tsitsulin et al. 2020), following Levy & Goldberg 2014); Qiu et al. (2018) Since PPR is rtght-stochastic and the noise distribution does not depend on j we can decompose the positive and negative terms from the objective of VERSE:
, log (x!xx) b
C
log (-x, x²))
Isolating the loss for pair of vertices i,j:
b Lij PPR;; log (x] xy) log (-x, x,)
We substitute Pij x, Xj, j. use our independence assumption, and solve for 8L:; PPR.,
(0(2)) =0 to get žij log n-PPR.; hence log (PPR) +log n llo XXT.
h
A.2 HASH KERNEL
Lemma A.2. (restated from Weinberger et al. (2009)) The hash kernel is unbiased:
Enawu U1, ha (x) daggo (x)] = x xTx x
Corollary A.2.1. (ref. Lemma 3.2) The space complexity of Ha (1) and:
E haggoa U11,1
Hha Jeego (M) (M) MM
Proof. We note that the space complexity required to store hash function from an universal family is (1). Indeed, one choose universal hash family such that its elements are uniquely determined by fixed choice of keys. As an example, the multiplication hash function (Cormen et al. (2009))
A (x) = (2A mod 1))1 requires constant memory store the key A E (0, 1).
In order to prove the projection provides unbiased dot-products, considering the expectation per each entry, we have:
Nennn ~ (Haarhogo (M) Har (M)
Ua - [Hhag (M;) M H Roga (M;)
-M,M
From Lemma A.2
= -(MMJ) )ay
which holds for all i, pairs.
A.3 SPARSPPERSNAAIZEDPAGRRE PROPERTIES
Theorem A.3. (restated from Andersen et al. 2007 Properties of the WALIZEEDAGGEAAKKO G,c) (3) algorithm are as follows. For any starting vector and any constant e E (0, the algorithm computes an e-approximate Personal- RzedPageRank vector p. Furthermore the support of p satisfies vol( Supp(r)) (1((-o))) and the running time of the algorithm is (1/oc).
We note here that Andersen et al. 2007 prove their results for the lazy transition matrix and not the standard transition matrix that we consider here. Nevertheless as discussed in Appendix A.7 switching between the definitions does not change the asymptotic of their results.
13

---

Under review as a conference paper at ICLR 2021
Algorithm SPARS SPARSSTPERSONALLZDDRRGEEEE cf. Andersen et al. (2007)
Input: node graph G. precision retun probability Output: PPR vector
1: function J.A.EPIRSOOALLEEDAGAAAAKCKC
On (sparse)
π f- On (sparse)
4:
r|o] =1
5:
while 7 G,r(w) > x deg(w) do
6:
f r[w]
f- T|u] + of r(w] (1-aff
T T|w]
8:
r[u] r|u] + (اما V(w, u) EC
10: return
A.4 INSTANTEMBEDDE LOCALITY
Lemma A... (ref. Lemma 3.3) The INSTANTEMBEDDINGI G,,,,,,,G,,,,, G,d,C, algorithu computes the local embedding of a node by exploring at most the O (1/(1a)e) nodes in the neighborhood of
Proof. First recall that the only operation that explores the graph in INSTANTEMBEDDING is SPARSEPER SON A AALIZEEPAGER.AO
K, which explores node w in the graph if and only if neighbor of has positive score (i.e. r[w') > deg(w') was true and thus r[w') > 0), and so is part of the support of æ. Furthermore at the beginning the algorithm only v is active, So follows that every node explored by the algorithm is connected to via path composed only by the nodes with π score strictly larger than 0. So its distance from v is bounded by the support of the m vector that is O (3/(1-)e) ef. Theorem A.3
A.5 INSTANTEMBEDDING COMPLEXITY
Theorem A.S. (ref. Theorem 3.4) The INSTANTEMBEDDING/? G,d,e) algorithm has running time O (d + 1/a(1-a)c).
Proof. The first step of the INSTANTEMBEDDIN is computing the approximate Personalized PageRank vector. noted in Theorem A.3 this can be done in time O (1/ac).
We now focus our attention to the second part of our algorithm, projecting the sparse PPR vector into the embedding space. For each non-zero entry rj the PPR vector æ, we compute hash functions ha(i), hagn (j) and max(log(7)) * n), 0) in ((1) time. The total number of iterations is equal to the support size of म. i.c. O (1)(1a))))
Finally, we note that our algorithm always generates dense embedding, handling this variable in (dd) time complexity. However, in practice this term is negligible as 1/e >> d. Summing up the aforementioned bounds get the total running time of our algorithm:
O (d 1/ac + 1/(1-a))) = O (d + 1/a(1-a)e)
A.6 GLOBAL CONSISTENCY
Theorem A.6. (ref. Theorem 3.5) INSTANTEMBEDDINGUS G, d, E) output equals GRAPHEMBEDDINGGC e,
begin by noting that for fixed parameterization, the PAGERANK routine will compute an unique vector for given node. Analyzing the W... W.y entry of the embedding matrix generated by GR GRAPHEMBEDDINGIC. d, we have:
Proof. We
W W.,j Σ
(kgm()) x max(log(ra * n), ()) = F
14

---

Under review as a conference paper at ICLR 2021
The entire computation is deterministic and directly dependent only on the hash functions of choice and the indexing of the graph. By fixing the two hash functions ha and hagn, we also have that W j.j
W where w" INSTANTEMBEDDINGG C,d, Vu E [0.. - 1..n-1,j- E [0.d 11. M
A.7 REPARAMETERIZATTON
We note that Andersen et al. (2007) in their paper use a lazy random walk transition matrix. Further- more in their analysis they also consider lazy random walk. Nevertheless, this does affect the asymptotic of their results, in fact in Proposition 8.1 in Andersen et al. (2007) they show that the two definition are equivalent up to small change a. More precisely, a standard personalized PageRank with decay factor a is equivalent to lazy random walk with decay factor 2-o So all the asymptotic of the bounds in Andersen et al. (2007) apply also to the classic random walk setting that we study in this paper.
B EXPERIMENTS
B. METHODS DESCRIPTIONS
We ran all baselines on 128 and 512 embedding dimensions. As we expect our method to perform better as increase the projection size, performed an auxiliary test with embedding size 2048 for InstantEmbeddding We also make the observation that learning-bar scale well with an increase of the embedding space. The following are the description and individual parameterization for each method.
methods generally do not
Deep Walk (Perozzi et al., 2014): Constructs node-contexts from random- walks and learns representations by increasing the nodes co-occurrence likelihood by modeling the posterior distribution with hierarchical softmax. We set the number of walks per node and their length to 80, and context windows size to 10.
Node2Vee (Grover & Leskovee 2016): Samples random paths in the graph similar to WeepWalk, while adding two parameters, p and q, controlling the behaviour of the walk. Estimates the likelihood through negative sampling. We set again the number of walks per node and their length to 80 and windows size 10, number of negative samples to 5 per node 1.
and
Verse (Titssulin et al., 2018): Minimizes objective through gradient descent, by sampling nodes from PPR random walks and negatives samples from noise distribution. We train over 10a epochs and set the stopping probability to 0.15.
FastRP (Chen al. 2019]: Computes a high-order similarity matrix linear combination of multiple-steps transitions matrices and projects it into an embedding space through a sparse random matrix. We fix the linear coefficients [0, 0, 1, 6] and the normalization parameter-OA. -0.65.
InstantEmbedding (this work): Approximate per-node PPR vectors with return probability a and precision which are projected into the embedding space using two fixed hash functions. In all our experiments, we set a 0.15 and L. where n is the number of nodes in the graph.
Four additional baselines were considered for extending a subset of our experiments, as follows:
RandNE (Zhang al. 2018): Linearnly combine transition matrices of multiple orders,
randomly projected through an orthogonal Gaussian matrix. We used transitions up to order
3, with coefficients [1, 100, 10a 10%].
NodeSketch (Yang et al. 2019): Employs a recursive sketching process using hash function that preserves hamming distances. Where provided, we use the recommended default parameters, and on all other datasets we choose the best performing ( ('order', a) parameters from {(2, 0.0001), (5, 0.001))-
LouvainNE [Bhowmick et al. 2020): Aggregates node representations from successive sub-graph hierarchy. We use the recommended defaults across all datasets, with Louvain partition strategy and damping parameter a 0.01.
15

---

Under review as a conference paper at ICLR 2021
Table Analysis of employed networks in terms of scale-free and small-world measures. The scale- free degree is reported as Kolmogorov-Smen Sorrrroov--m test between power-law and exponential/lo-nonnt normall distributions candidates (R mean log- likelihood ratio, = degree of confidence).
Exponential Distribution
Log-normal Distribution
Pseudo- diameter
Transitivity
12.49
0.02
-0.56
0.45
0.09
Blogcatalog
63.39
-1.9
0.16
0,09
CoCit
354.09
-2.61
0.19
25
0,08
CoAut
502
-102
30
0.28
Flickr
-61.31
0.28
-504
0.18
YouTube
60175
-142
24
0.006
Amazon2M
41233
-190
29
0.13
Orkut
33757
-737
10
0.04
FREDE Tsitsulin et al. 2020): Sketches matrix by iteratively computing per-node PPR vectors and using frequent directions. We use the provided default parameters for all datasets in order to measure running times.
B.2 DATASET DESCRIPTIONS
The graph datasets we used in our experiments are as follows:
PPI (Stark al. 2006): Subgraph of the protein-protein interaction for Homo Sapiens species and ground-truth labels represented by biological states. Data originally processed by Grover & Leskoved (2016).
Blogcatalog (Tang & Liu 2010); Network of social interactions between bloggers. Authors specify categories for their blog, which we use as labels.
Collection of scientific papers, authors. journals and conferences. Two distinct subgraphs were originally processed by Tsitsulin et al. (2018), based on co-authorship (CoAuthor) and co-citations (CoCit) relations. For the latter one, labels are represented by the unique conference where the paper was published.
Microsoft Academic Graph (MAG) (mag 2016):
Flickr (Tang & Liu 2010 Contact network of users within 195 randomly sampled interest groups.
YouTube Tang & Liu 2010) Social network of users on the video-sharing platform. Labels are represented by group of interests with least 500 subscribers.
Amazon2M (Chiang et al. 2019): : Network of products where edges are represented by
co-purchased relations.
Orkut (Yang Leskovec 2015 Social network where users can create and join groups,
used at ground-truth labels. We followed the approach of Tsitsulin et al. (2018) and selected only the top 50 largest groups.
Friendster YYang & Leskoved 2015): Social network where users can form friendship edge each other. also allows users form a group which other members can then join.
To better understand the variety of our chosen datasets, we report the scale-free and small-works characteristics of the networks in Table 5 fitting a power-law distribution to node degrees, and comparing it to other 2 distributions (exponential and log-normal) through the Kolmogorov-Smimm test (R = mean log-likelihood ratio, = degree of confidence). We note that on the Co Flickr, YouTube, Amazon2M and Orkut networks, the h0 hypothesis can be rejected (p < 0.05) and thus conclude that the log-none normall distribution is better fit (graphs are not scale-free). Additionally, report two smold-world related measures: the pseudo-diameter of the graphs and their global clustering coefficient (transitivity). We observe that that graphs we use in the study are diverse, covering the spectrum of mall-woord and lirge-di networks.
16

---

Under review as a conference paper at ICLR 2021
B.3 RUNTIME ANALYSIS
B.3.1 GENERAL SETUP
For the runtime analysis we use the same parameterization as described in B.1 for all methods. In the special case of InstantEmbedding, we dynamically load into memory just the required subgraph in order to approximate the PPR vector for single node. We individually ran each method virtual machine hosted on the Google Cloud Platform, with a 2.3GHz 16-core CPU and 128GB of RAM.
B.3.2 RUNTIME: SPEED
All methods, except the single-threadee FastRP, leveraged the 16 cores of our machines. Some methods did not complete all the tasks: none ran Friendster; node2vec was unable to run on Amazon2M and Orkut; FastRP did not rum Orkut specifically for 512-dimension embedding. We note that all reported numbers are real execution times, taking into account also loading the data in memory. The detailed results are shown Table
For reference, we also provide the total running time for producing full graph embedding. We note that when computing the PPR matrix (of an entire graph) local measure may be suboptimal, and we leave optimizing global run time future work. Nevertheless, here report the total running time of our local method successively applied to all nodes in graph in Table with an additional recent baselines. All methods ran the same machine and produced 512-dimensions embedding for the node classification task. From the additional baselines, only RandNE and LouvainNE could scale to Orkut, while FREDE could only produce an embedding on half of the datasets.
B.3.3 TASK: MEMORY USAGE
The methods that failed to complete in the Running Times section also marked here accordingly. We note that due to the local nature of our method, we can consistently keep the average memory usage under MB for all datasets. This observation reinforces the sublinear guarantees of algorithm when being within good e-regime, as stated in Lemma A.4 The detailed results are shown in Table g
Table Total approximate running time for producing a 5512-dimmnsio full graph embedding, with 4 additional recent baselines. In this scenario, InstandEmbedding produced full graph embedding, as opposed to the originally proposed single node representation task.
PPI
BlogCatalog
CoCit
Flickr
YouTube
Orkut
DeepWalk
254
711
2,767
6,035
81,168
219,003
node2vec
24.82
67.8
280
802
7,600
DNC
VERSE
87.5
198
904
1,863
31,101
84,468
RandNE
2.05
3.93
3.86
39.4
32.1
773
FasIRP
1.81
5.62
7.21
79.8
85.5
DNC
NodeSketch
19.9
609
496
3,350
2,798
DNC
LouvainNE
0.62
2.47
17.7
196
FREDE
150
1.194
10,954
DNC
DNC
DNC
InstantFmhedddnn
0.27
3.98
5.32
53.6
1,254
58,070
17

---

Under review as a conference paper at ICLR 2021
Table Average run time (in seconds) generate 128-size and 512-size node embedding for each method and each dataset with the respective standard deviation. Each experiment was run times for all the methods (given their global property) except for InstantEmbeodinn for which we ran the experiment 1000 times (given the method's locality property).
bold improvement over the baselines; DNC- Did Not Complete.
InstantEmeedding
DeepWalk
node2vec
VERSE
FastRP
0.00735
92.74
12.90
40.05
1.42
128
0.00130
+
0.26
0.08
= 0.02
PPI
0.00751
254.31
24.82
87.53
1.81
512
0.00137
+: 7.68
0.17
0.24
4 0.02
0.00627
349.66
37.10
109.15
3.03
128
0.00221
30.03
0.19
1.20
1 0.08
BlogCatalog
0.00826
711.76
67.86
198.75
5.62
512
0.00436
+ 17.81
0.17
+ 1.68
4 0.15
0.01993
1,015.44
149.53
427.06
3.51
128
0.01042
+ 3,23
1.14
+ 4.23
- 0.12
CoCit
0.02019
2.766.99
280.35
904.53
7.21
0.01048
+ 5.71
0.82
7.89
# 0.72
0.01612
1,334.55
189.30
468.47
2.71
128
0.00733
10.84
+ 11.78
1.88
#
CoAuthor
0.01630
3,561.27
339.01
1,029.88
5.50
512
0.0076/
+: 27.86
+ 1.04
1: 9.96
1 0.08
0.02042
2,519.22
564.71
1,038.87
38.41
128
0.01
1: 121.60
1: 5.01
1. 11.27
1 0.42
Flickr
0.02051
6,035.50
802.64
1,863.41
79.88
512
# 102.25
4.95
::
0.06065
27,249.93
4,301.05
16,618.20
30.44
128
0.04527
+ 1,383.18
+ 21.36
282.66
$
YouTube
0.06128
81,168.81
7,600.46
31,101.92
85.52
$12
0.04334
+ 2.752.42
+ 64.14
+ 121.03
+ 4.81
0.09746
63,525.32
38,627.77
450.84
128
DNC
+ 0.05306
+ 164.83
+ 4,058.04
+ 21.07
Amazon2M
0.09715
173,966.97
73,993.64
940.88
512
DNC
0.05187
1: 1,09.666
2,110.29
31.16
0.17192
94,217.21
50,516.07
843.46
128
DNC
0.04782
1. 1,121.94
4,082.24
17.69
Orkut
0.17231
219,003.92
84,468.50
DNC
DNC
0.04806
+ 781.12
3,407.44
0.07910
DNC
DNC
DNC
DNC
0.04084
Friendster
0.07930
512
DNC
DNC
DNC
DNC
0.04000
18

---

Under review as a conference paper at ICLR 2021
Table 8: Peak memory used (in MB) to generate 1 128-size and 512-size node embedding for each method and each dataset. Each experiment was run once for all the methods (given their global property) except for InstantEmeedding for which ran the experiment 1000 times (given the method's locality property) and report the mean peak memory consumption with the respective standard deviation. bold improvement over the baselines, DNC Did Not Complete.
InstantEmbedding
DeepWalk
node2vec
VERSE
FastRP
0.1692 1: 0,0144
4.80
54.02
2.40
68.17
PPI
512
0.1707 0.02/1
16.75
65.98
8.39
197.67
128
0.2040 0.0788
14.54
2,970.00
8.08
150.47
BlogCatalog
512
0.2140 + 0,0877
46.21
3,000.00
23.92
504.65
128
0.2697 + 0.0848
52.27
148.93
24.38
438.27
CoCit
0.2780
0.0692
187.54
284.20
92.01
1,660.00
128
0.1778
61.13
120.56
28.25
465.47
CoAuthor
512
0.1803
0.0642
220.32
279.75
107.85
1,770.00
128
0.4138 + 0,1525
140.33
69,860.00
88.83
1,080.00
Flickr
512
0.4451 +: 0.1729
387.67
70,110.00
212.50
3,830.00
128
0.5902
1,360.00
24,910.00
611.48
10,240.00
YouTube
512
0.5456
0.2642
4,860.00
28,410.00
2,360.00
40,610.00
128
0.6321
+ 0.3122
3,380.00
DNC
1,760.00
26,440.00
Amazon2M
512
0.6778
1: 0.2862
10,910.00
DNC
5,520.00
125,870.00
0.9124
1: 0,0672
4,560.00
DNC
2,520.00
35,940.00
Orkut
512
0.8884
14,000.00
DNC
7,240.00
DNC
128
0.6818
0.2476
DNC
DNC
DNC
DNC
Friendster
512
0.7892
0.1753
DNC
DNC
DNC
DNC
19

---

Under review as a conference paper at ICLR 2021
B.4 EMBEDDING QUALITY
B.4.1 QUALITY: NODE CLASSIFICATION
These tasks aim to measure the semantic information preserved by the embedddings, through the means of the generalization capacity of simple classifier, trained on small fraction of labeled representations. All methods use 512 embedding dimensions. For each methods, we perform three different splits of the data, and for our method we generate five embeddings, each time sampling different projection matrix. We use logistic regression (LR) classifier from using Scikit- [Pedregosa et al.) 2011) to train the classifiers. In the case of multi-class classification (we follow Perozzi et al. (2014) and use a one-vs-rest LR ensemble) known and select the top probabilities from the ensemble. To simulate the sparsity of labels in the real-wold, we train 10% of the available labels for PPI and Blogcatalog and only 1% for the rest of them, while testing on the rest.
assume the number of correct labels K
We treat CoCit multi-class problem as each paper associated unique conference were it was published. Also, for Orkut we follow the approach from Tsitsulin et al. (2018) and select only the top 50 largest communities, while further filtering nodes belonging more than one community. In these two cases, are fitting a simply logistic regression model on the available labeled nodes. The other datasets have multiple labels per node, and we are using a One-vs-The-Be evaluating, we assume the number of correct labels, K, is known and select the top K probabilities from the ensemble. For each methods, we are performing three different splits of the data, and for our method we generate five embeddings, sampling different projection matrices.
ensemble. When
We report the average and 90% confidence interval for micro and macro Fl-scores at different fractions of known labels. The following datasets are detailed for node classification: PPI (Table 9
BlogCatalog (Table 10.. CoCit (Table IT). Flickr (Table 12]. and YouTube (Table 13
We also report experiments with 4 additional baselines in Table 14 The classification task is the same, however for NodeSketch we used the recommended SVC classifier with hamming kernel, as the Logistic Regression could not infer separation boundary in this particular case. Additionally, for FREDE we are referencing the scores from the original paper, having a comparable evaluation framework. We note that although FREDE produces better scores, it does not scale past medium- sized graph, and its extremely high running times (Table 6 takes this approach out of the original scope of our paper.
Table 9: Classification miero and macro Fi-scores for PPI.
Lubeled Nodex
10.00%
50.00%
90.00%
Method
Micro-F1
Macro-FI
Micro-F1
Macro-F1
Micro-FI
Macro-F1
128
15.72 = 1.75
12.56 1.84
21.34 1.20
18.59 1.40
24.44 0.32
20.36 2.74
DeepWalk
512
16.08 = 0.64
12.89 + 1.66
19,90 + 1.02
18.08 1.11
21.51 + 5.75
20.36 + 5.05
node2vec
128
15.65
1.46
12.07 1.23
20.97 1.26
17.86 0.85
23.99 5.84
19.05 2.25
512
15.03 + 3.18
12.19 +: 2.34
21.04 + 1.90
18.11 2.13
22.02 1.14
18.18 3.47
128
14.41
11,56 1.37
19.63
16.95 1.67
22.01 2.66
18.71 0.67
VERSE
512
12.59 +:2 2.54
9.54 +: 2.22
13.62 + 0.88
11.67 + 0.85
16.00 +: 0.26
13.66 +: 0.53
FasIRP
128
11.73
2.37
7.24 + 1.49
16.76 0.70
11.03 1.05
19.45 3.10
11.70 2.98
512
15.74 + 2.19
11.11 + 1.20
21.19 + 2.25
15.72 + 1.37
21.52 + 5.37
16.63 = 1.87
128
15.88 + 1.36
11.67 1.09
20.51 0.70
16.89 0.93
21.82 2.47
17.49 2.36
Instant
Embedding
512
17.67
# 1.22
13.04 + 1.06
23.50
0.97
19.84 1.34
25.36 2.32
21.21 + 2.92
2048
18.77 # 1.22
13.76 1.41
24.30 0.67
20.44 0.85
25.85 2:9
22.03 3.84
B.4.2 TASK: LINK PREDICTION
For this task we create edge embeddings by combining node representations, and treat the problem as a binary classification. We observed that different strategies for aggregating embeddings could maximize the performance of different methods under evaluation, so we conducted an in-depth
20

---

Under review as a conference paper at ICLR 2021
Table 10: Classification micro and macro Fi-scores for Blogcatalog.
Labeled Nodes
10.00%
50.00%
90.00%
Method
Micro-Fl Fl
Macro-F1
Micro-F1
Macro-Fi Fl
Micro-F
Macro-Fi
DeepWalk
128
36.05 i 0.85
20.91 0.79
41.07
1. 1.05
26.85
0.96
42.69
1.49
28.87 1. 4.61
512
32.48
1: 0.35
18.69 1. 1.17
37.88
1. 0.61
25.38
0,85
40.14 1. 4.03
26.11 1: 6.42
node2vec
128
33.63
1: 0.96
15.28
1: 0.99
37.18
0.82
20.02
0.44
38.34
3.62
21.26 :: 1.37
512
33.67
= 0.93
16.24 + 1.11
37.42 + 1.40
21.43 + 0.73
38,98 + 4.70
21.94 = 1.49
VERSE
128
32.57
0.96
18.67
1.46
38.66
0.88
25.0
1.37
39.47 1.34
26.64 1.08
512
24.64
+ 0.85
12.33 + 1.58
29.27 + 0.41
18.48 0.88
33.18 + 2.51
21.11 + 2.60
FastRP
128
28.68
+: 0.35
12.74
1.23
31.22 + 1.34
14.78
0.53
31.61 1.90
15.34
3.27
512
33.54 +: 0.96
17.83 +: 1.90
36.94 +: 1.08
21.49
+: 0.38
37.62 +: 2.66
22.26
+: 2.98
128
27.99
1 1,20
13.72
1: 1.49
32.40
+: 1.23
18.77
1.40
33.40
1: 2.95
19.94
3.30
Instant
Embedding
512
33.36
1 1.11
17.37
1: 1.67
37.76
1.37
23.79
1.61
39.33
1: 3.45
26.14
=: 3.07
2048
36.05 1.66
19.01
1.93
41.42 1.49
27.16
1.96
42.46
4.35
29.00
3.94
Table 11: Classification micro and macro Fl-scores for CoCit.
Labeled Nodes
1.00%
5.00%
9.00%
Method
d
Micro-FI Fl
Macro-F1
Micro-F1
Macro-FI F1
Micro-Fi
Macro-F1
128
36.51 1 0,85
27.54 +: 1.26
41.52 +: 0.03
29.85 1.31
43.21 4: 0.63
30.31 +: 0.50
DeepWalk
512
37.44 + 0.67
26.57 +: 0.76
39.41 + 1.11
29.92
0.79
40.95 +: 0.82
31.48 +: 0.91
node2vec
128
37.55
+:2 0.99
26.38 +: 0.88
42.92
+ 0.55
31.12
0.41
43.94 + 0.63
32.03 +: 0.20
512
38.35 :: 1.75
27.71 + 1.17
42.53
+ 0.26
31.05 + 0.50
43.99 + 0.32
32.14 + 0.38
VERSE
128
38.52
:: 0.47
28.17
1.20
41.68
0.96
31.14
0.26
43.47
0.26
32,22
+: 0.53
512
38.22 :: 1.34
27.42 1: 0.91
38.03
+: 0.58
29.50
+: 0,88
38.88 4: 0.61
31.04 :: 0,82
FastRP
128
15.97
1: 0.55
4.18 1: 0.29
16.74
0.64
4.31
0.47
0.35
4.17 0.29
512
18.88 1: 1.28
6.63 1: 0.47
26.82
1: 1.23
9.17
1: 0.26
27.91 1: 0.99
8.79
0.38
128
38.19
1: 1.07
25.29
1: 1.14
41.23
0.49
27.92
0.63
42.48
0.42
28.44 1: 0.72
Instant
Embedding
512
39.95
1: 0.67
27.64
1: 1.22
43.01
1: 0.51
30.61
0,51
44.05
1: 0.35
31.50
1: 0.63
2048
40.49 1.06
28.86 0.81
43.79
0.46
31.69 0.55
44.85 0.46
32.76 0.41
Table 12: Classification micro and macro F1 Fi-scores for Flickr.
Labeled Nodes
1.00%
5.00%
9.00%
Method
d
Micro-F1
Macro-F1
Micro-F1
Macro-F1
Micro-F1
Macro-F1
128
32.55 : 0.91
13.81 + 1.72
37.44 +: 0.44
22.58 0.53
38.78 + 0.23
24.75 +: 0.58
DeepWalk
512
31.22 # 0.38
13.42 + 1.23
35.67 + 0.38
22.72
1.52
37.25 + 0.09
25.74 + 0.58
node2vec
128
29.27
+ 0.96
6.40 + 0.50
34.12
0.47
12.82
0.88
35.15 + 0.03
14.89 0.47
512
29.80 1: 0.67
7.14 1: 0.20
34.40
0.26
13.50 i: 0.20
35.39 1 0.06
15.58 +. 0.58
VERSE
128
28.04 + 1.84
10,52 + 2.37
33.52
+ 0.12
19.12 12 0.41
35.38 + 0.41
22.31 + 0.93
512
25.22 1: 0.20
7.20 1: 1.28
28.25
1: 0.29
14.17 1: 1.02
29.65 1 0.32
17.09 1. 0.29
FastRP
128
28.20
1: 0.53
9.39 1: 1.67
30.43
0.15
13.82 0.67
30.65 1: 0.29
14.51 +: 0.38
512
29.85 +: 0.26
12,28 1: 2.72
33.64
+: 0.58
1.28 18.94
34.88 4: 0.58
21.44 + 1.23
128
27.41
+: 0.90
9.14 1: 0.56
31.84 + 0.25
14.90 0.55
33.14 4: 0.33
17.27 +: 0.65
Instant
Embedding
512
30.43
4 0.79
10.78 +: 1.20
34.00 + 0.25
18.36
0.51
35.37
+: 0.25
21.26 + 0.48
2048
31.89
0.62
11.15 1.02
35.94 0.23
19.38 0.85
37.21 0.18
23.02 0.56
21

---

Under review as a conference paper at ICLR 2021
Table 13: Classification miero and macro Fi-scores for YouTube.
Labeled Nodes
1.00%
5.00%
9.00%
Method
Micro-FI Fl
Macro-F1
Micro-F1
Macro-Fi Fl
Micro-F
Macro-Fi
DeepWalk
37.53 i 1.40
29.04 1 3.77
41.64
0.15
34.45
0.70
42.97
0.29
35.62 1 0.93
512
38.69 1: 1.17
31.11 1. 1.08
40.26
0.38
35.09
1: 0.26
40.74 1. 0.06
36.14 1 0.23
VERSE
37.13 1: 0.41
28.54
2.39
39.74
0.32
33.87
0.67
41.70
0.38
35.04 1: 0.41
512
36.74 = 1.05
27.16 + 0.15
37.47 = 1.37
32.40 + 0.91
37.64 + 0.67
33.00 = 0.35
node2vee
128
34.64 + 2.63
25.35
3.83
40.62
1.02
33.26
0.20
42.65 0.70
35.73 0.32
512
36.02 = 2.01
25.03 + 2.89
39.64 + 0.44
33.78 0.38
40.47 + 0.83
35.01 = 1.08
FastRP
128
23.61 +: 1.61
6.24 +: 0.61
24.16
0.96
6.64 1.64
24.50 0.29
7.09 0.35
512
22.83 ::: 0.41
7.21
+: 0.20
23.43
+ 0.55
8.77 + 0.82
23.76 +: 0.64
9.56 : 0.91
Instant
37.89
1 1.02
26.27
1.36
40.90
0.53
31.57
0.86
41.78
0.37
32.73 1: 0.51
Embedding
512
40.04
1 0.97
27.52
1: 1.60
43.31
0.41
33.98
0.81
44,00
1: 0.42
35.56 1. 0.69
2048
40.91
0.86
28.34 1.43
44.82
0.49
35.16
1.02
45.67 0.32
36.90 0.69
investigation in order for the fairest possible evaluation. Specifically, for node embeddings w and V we adopt the following strategies for creating edge representations:
1. dot-product: w
2. cosine distance: || [|]
3. hadamard product: W
4. element-wise average: (w w))
5. L1 element-wise distance: |w w/
6. L2 element-wise distance (w W (w w)
While the first two strategies directly create ranking from two embeddings, for the other ones we train a logistic regression on examples from the validation set. all cases, a likelihood scalar value will be attributed to all edges, and we report their ROC-AUC score on the test set.
Taking into account that different embedding methods may determine a specific topology of the embedding space, that may in turn favour specific edge aggregation method, for each method consider only the strategy that consistently provides good results on all datasets. This ensures that all methods be objectively compared to another, independent of the particularities of induced embedding space geometry.
The following tables show detailed analysis of link prediction results for BlogCatalog (Table 15 and CoAuthor T6).
Table Approximate Micro-F1 scores with an additional baselines. methods produced 512- dimensional embeddings, with the exception of FREDE for which we refer the scores from the original paper.
PPI
BlogCatalog
CoCit
Flickr
YouTube
Orkut
DeepWalk
16.08
32.48
37.44
31.22
38.69
87.67
node2vec
15.03
33.67
38.35
29.80
36.02
DNC
VERSE
12.59
24.64
38.22
25.22
36.74
81.52
RandNE
15.77
32.79
16.23
29.19
24.57
59.01
FastRP
15.74
33.54
26.03
29.85
22.83
DNC
NodeSketch
12.03
29.65
16.67
23.07
32.02
DNC
LouvainNE
14.73
22.28
35.14
26.37
33.52
45,08
FREDE
19.56
35.69
42.46
DNC
DNC
DNC
InstannFmhedddng
17.67
33.36
39.95
30.43
40.04
76.83
22

---

Under review as a conference paper at ICLR 2021
Inbkkiniibeekinng
DeepWalk
node2vec
VERSE
FUIRP
1111
Metuory (mbb)
10
Micro
Logs Time
10
10
109
mm
10-1
111
11
11111
10
10
10
10
10
10
10
10 10
10
10
10
10
10
10
10
10
log(e)
logte)
lagle]
(e) Micro Fl Soore
Running Time
Peak Memory
Figure 4: Effect of the PPI dataset.
lostantFanheddding
DoepWalk
mode2vee
35
XUXC FOI PC
10
LogiMemory (mb))
30
10a
10a
Mico
LogiTTme
25
10
20
2
10
10
logte) (al Micro F1 Score
logie) (b) Running Time
logie) (3) Peak Memory
Figure 5: Effect of on the BlogCatalog dataset.
B.5 EPSILON INFLUENCE
In order to gain insight into the effect of on the behaviour of our method, we test values in the range of [10-1,... ..., 10 10-6) I]. We note that the decrease of is strongly correlated with better classification performance, but also to a larger computational overhead. The only apparent exception seems to be the Micro-F1 score on the Blogcatalog dataset, which drops suddenly when 10 We argue that this is due to the fact that more probability mass is dispersed further away from the central node, but the max operator cuts that information away (as the number of nodes is small), and thus the resulting embedding is actually less accurate.
B.5. TASK: VISUALIZATION
Figure 3 presents multiple UMAP (Melnnes et al. 2018) projections on the CoCit dataset, where we grouped together similar conferences. We note that our sublinear approach is especially well suited to
Table 15: iine-predittion ROC-AUC scores for Blogcatalog. For each method, highlight the aggregation function that consistently performs good on all datasets.
Aggregation Function
Method
d
hadamard
dot-product
cosine
L1
L2
average
DeepWalk
128
68.92
2.45
63.01 2,83
75.73
1.49
91.51
061
91.84
0.88
82.07
0.09
512
67.70 +
62.80
2.07
72.83
0.82
90.94
0.29
91.41
0.67
83.71 1.46
node2vee
128
0.20 92.18
93.12
1.37 90.96
91.85
22.52
= 0.41
89,90
0.70
90.28
1.28
94.41 0.53
512
12.49
1.20
93.89
0.38
93.50 0.76
93.72
VERSE
128
94.96
1: 0.38
95.10 0.67
85.21
0.88
75.74
0.85
75.92 0.73
94.07
0.47
512
93.42
93.40
61.48
0.88
91.52
0.26
92.17 0.61
93.14
FastRP
128
73.54
1: 0.23
68. 16
0.55
76.32
1.90 79.25
2.31 88.68
85.78
82.46
2.01
89.25
0,85
512
78.34
70.67
84.56
0.76
90.99
0.55
128
89.22
1.48
84.95 4.19
1.14 51.75
51.57
72.52
1.71 83.07
64.39
1.37
87.65 0.70
Instant
Embodding
512
92.74
90.77
70.39
1.11
90.63
2048
93.84
1:: 0.33
93.44
0.53
51.35 + 1.18
88.95
0.85
77.39 4: 1.02
92.40 +: 0.42
23

---

Under review as a conference paper at ICLR 2021
DeepWalk
node2vee
VERSE
FaIRP
40
Memory (mb))
10a
Micro F1
30
10a
10
20
100
10-1
10
20
10
10
10
10
2
10
0
10
100
10
10
logte)
logte)
Iogle)
Micro E1 Store
Running Time
Peak Memory
Figure 6: Effect of on the CoCit dataset.
DoepWalk
node2vee
VERSE
FusRPP
FiIt 20111
pott
1R11 B!
1 MUTE
10a
LogoMenory (mbi)
10
Micio F1
25
10a
10a
10
20
109
10-1
1.5
m0
10
11
10
10 10
10
10
10
10
10
10
10
10 10
10
10
10
10
10-00
logte)
logic)
logle)
(a) Micro Fl Soore
(b) Running Time
(c) Peak Memury
Figure 7: Effect of on the Flickr dataset.
ImbtannEnbedding
DeepWalk
2ude2vec
VERSE
FastRP
40
10a
10a
LagiMenxry (mab))
MicooF
Logs (x))
30
103
30
10
10
25
10
10
2
10
8
2
10
10
8
Togle) (i) Micro Soore
Togie)
lngle]
Running Time
Pesk Memory
Figure 8: Effect of 6 on the YouTube dataset.
24

---

Under review as a conference paper at ICLR 2021
Table 16: Temporal link- prek-preiition ROC-AUC scores for CoAuthor, For each method, we highlight the aggregation function that consistently performs good on all datasets.
Aggregation Function
Method
hadamard
dot-product
cosine
L1
L2
average
DeepWalk
128
75.59
74.05
83.5
86.99
87.21
0.73
73.64
1.72
78.42
0.53
76.40
1.87
82.05
1.20
87.85
0.29
88.43
1.08
79.56 0.70
node2vec
128
80.18
45.00
54.59
0.88
70.14
70.32
79.07
86.09
0.85
45.19
0.20
42.99
1.66
72.41
1.84
72.70 1.43
84.00 0.38
128
93.16
92.74
90.85
79.24
80.27
86.50
VERSE
512
0.73 92.75
92.36
1.08
0.20 90.33
72.58 1.17
73.82 1.49
86.69 1.02
FastRP
128
60.23
59.97
1.61
65.08
0.93
78.51 0.64
77.66 0.23
57.69 1.90
512
61.16 1.75
61.92 0.85
70.12 0.38
2.22 82.19
78.51 1.99
63.87 1.49
128
89.41
88.88
89.15 0.63
66. 19 1.92
66.78
83.22
Instant
Embedding
90.44
0.48
90.10
0.69
0.55
76.50 1.44
75.76 1.41
85.64 0.67
2048
89.45 1 0.62
90.38 1: 0.60
90.84 0.44
88.42 0.48
84.83 +: 0.67
87.67 1.07
visualizing graph data, visualization algorithms (such as t-SNE or UMAP) only require small subset of points (typically downsampling to only thousands) to generate a visualization for datasets.
(a) DeepWalk
VERSE
(c) FastRP
(d) InstantEmbedding
Figure 9: UMAP visualization of CoCit (d=512). Research areas
ML. DM, DB, IR).
25


Reviews:
[{"review_id": "xGKBj59tPR", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nContributions of this paper are twofold. First, it introduces the problem of Local Node Embedding, which means node embedding by using local information only while garanteeing global consistency. Second, it presents InstantEmbedding, an efficient implementation based on PPR and random projections. Extensive experiments on 10 datasets show that this new algorithm saves computer memory and is much faster than existing baselines.\n\n\n##########################################################################\n\nReasons for score: \n\nI vote for accepting the paper for I think we need such efficient approaches that are able to deal with huge graph (for industrial applications), or juste help when one uses a simple computer with limited capacities. I don't give a higher grade for I think it's a rather incremental proposal that is build on a pipeline combining two previous papers.\n\n \n##########################################################################\n\nPros: \n \n1. very well written paper\n2. approach well grounded on two previous interesting works\n3. new approach is proven to be more efficient, in term of runtime and memory usage\n\n \n##########################################################################\n\nCons: \n\n1. quite incremental, seems more like an application of existing methods\n2. way of comparing to previous work is not perfectly clear (see below)\n3. no discussion on the better performances in node classification (see below)\n \n##########################################################################\n\nQuestions during rebuttal period: \n\n- The way runtime is calculated in Section 4.2 is not perfectly clear. Is it calculated on the whole graph, and then divided by n (number of nodes), or is it directly at the node level? If this is the latter, how do you calculate the values for the competitors? For DeepWalk, in particular, complexity is proportional to the parameters defining the random walk, not n as shown in Table 1.\n\n- Can you explain why DeepWalk cannot be described as a local method since it is based on truncated random walks?\n\n- Do you have any explanation for the very good results in node classification? There is no clear reason why the proposed approach will be good for solving this task. The quick mention of regularization is not fully satisfying and further insight would be much welcome.\n\n#########################################################################\n\nSome typos: \n\n\"for its adaption\"\n\"should posses\"\n\"can choose and universal\"\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Xa_XJwFGTq9", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an efficient algorithm to obtain a given node's embedding based on its local PageRank scores. The proposed approach uses a hashing technique to hold similarities between nodes effectively. Besides, it exploits a local partition approach to compute PageRank scores. This paper performs the experiments by using several real datasets to show the approach’s efficiency and effectiveness. \n\nIn my opinion, the proposed approach lacks the originality; it is a combination of the existing hashing technique by Weinberger et al., and the PageRank computation approach by Andersen et al. Unlike the previous approaches such as DeepWalk, it exploits PageRank score to obtain similarities. However, this is the same idea proposed by Tsitsulin et al.\n\nI doubt the paper performed a fair comparison to the existing approaches in terms of running time. As shown in Algorithm 2, the proposed approach computes an embedding of a single node. On the other hand, the existing embedding approaches compute embeddings of all the nodes. Therefore, the proposed approach should be evaluated in computing embeddings of all the nodes. I do not think it takes only 80ms to compute embeddings of all the nodes for Friendster dataset of 66M nodes. The downstream applications, such as visualization, need embeddings of all the nodes, not a single node. Could you tell me whether the proposed approach is faster than the previous approaches if it computes all the nodes' embeddings?\n\nIn terms of running time, it is good to compare the proposed approach to the state-of-the-art approaches such as FastRP.\n\nSince the proposed approach removes non-significant PPR scores by using log b, it would impact the proposed approach’s running time and accuracy. Could you tell me the effects of log b?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Q2OD7b87ErJ", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "(Summary)\n\nUnsupervised learning of vector representations for a graph is an important problem for various downstream applications. The authors propose an InstantEmbedding approach that learns d-dimensional embedding for each node in sublinear time. As the paper claims that this approach is a local embedding but globally consistent, users can quickly learn vector representations of nodes based on the local structure, being free from possibly growing the rest of the graph.\n\nTwo properties are first defined as qualifications to be a useful local embedding. Locality requires learning algorithms to use only local information. If an approach requires an access to the embeddings of every node in local neighbors or to the entire adjacency matrix, locality is not qualified. Global consistency means that the locally-computed embeddings remain identical even if we compute the embeddings of the entire nodes simultaneously.\n\n\n\n(Originality and Contributions)\n\nThe proposed algorithm: InstantEmbedding is simple. Once we compute Personalized PageRank (PPR), the algorithm tries to decompose the dense similarity matrix log(PPR) + log(# of nodes) efficiently via two hash functions. The algorithm is designed in a way that global learning is equivalent to local update, automatically satisfying the global consistency. Thus most of the theoretical contributions are based on the idea of implicit factorization by Tsitsulin et al (2020) (which is essentially similar to Levy et al (2014)), the idea of hashing by Weinberger et al (2009), and the sparse computation of PPR by Andersen et al (2007). Instead, this paper conducts extensive study of empirical performance with increasing the error parameter $\\epsilon$. The experimental results demonstrate that InstantEmbedding produces competitive embeddings with other methods with a few thousand times better in time and space complexity.\n\n\n\n(Questions, Concerns, and Suggestions)\n\n1) Global consistency was expected to be a theoretical property, as given in Section 2.3, such as distance/geodesic preservation between the graph space and the vector space. However, it ended up being chosen more as an algorithmic property, which the proposed algorithm is uniquely achievable by the design. Have you actually measured distortion in various datasets, being able to claim low-distortion?\n\n\n2) As studied in GEMSEC by Rozemberczki et al (2018), quality embeddings should promote clustering of the nodes (i.e., underlying community structures) as well as preserving the proximities. Considering that one can easily acquire local clusters based only on the local structures of the graph, it will be useful for readers to know whether or not InstantEmbedding can also encode local community structures. And, that could be a significant part of the Locality.\n\n\n3) Note that Graph Convolutional Convolutional networks can also be trained as an unsupervised fashion and sometimes achieve great generalization without node features. See how synthetic graph is generated featurelessly in GAP by Nazi et al (2019). More importantly, the message passing scheme in GCN is scalable to multi-graph or even hyper-graph, which is not readily clear in the proposed method. Learning hierarchical representation is also questionable.\n\n\n4) Can you report the degree of scale-free and small-world for each of the graph in experiment? It is an important summary information for distinguishing individual graphs. Hope various graphs used in the experiment have explored a wide range of scale-free and small-world structures.\n\n\n5) If we carefully read Andersen et al (2007), they did not adopt standard transition matrix given in the proposed model. Asymptotically it would not cause much difference, but it is less clear what’s the impact on the F1-performance given $\\epsilon$ tolerance. Note again that InstantEmbedding becomes useful only if the tolerance parameter reaches at a certain level.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EpXQR8vU083", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "###### Summary ######\n\nThe paper proposes a node representation learning method for undirected networks based on the Personalized PageRank algorithm. The embedding vector for a node is obtained by applying a hashing algorithm on the approximated PageRank vector computed by using only the local region of the interested node. That way, the paper proposes a scalable algorithm that does not require the whole network while computing the embedding of a particular node. The performance of the algorithm is evaluated on the multi-label node classification and link prediction tasks.\n\n###### Reasons for score ######\n\nI vote for rejection. The structure and the main idea of the paper are good, but the experimental evaluation of the method is not sufficient and it should be enhanced. Although there are many recent scalable algorithms (as described below), the paper considers only FastRP and the classical models as baseline methods. \n\n###### Strengths ######\n\n--- The algorithm computes the embedding vector of a particular node by using only the local subregion of the network, without requiring the embedding vectors of the remaining nodes.\n\n--- The algorithm outperforms classical baseline methods on small training ratios in the classification task. \n\n###### Weaknesses ######\n\n--- The experimental evaluation is weak and does not allow us to draw meaningful conclusions about the proposed algorithm. The paper does not use most of the recent scalable algorithms, except one, in the empirical analysis. \n\n--- The proposed algorithm does not show significant performance improvement on the link prediction task.\n\n###### Detailed Comments ######\n\nOverall, the paper is well-written and has a well-organized structure. The proposed methodology is interesting, but I have concerns related to various parts of the paper. \n\nIn Section 3, the paper starts describing the methodology by firstly introducing the objective function of VERSE and then indicating that it implicitly performs a matrix factorization of the matrix M defined as “log(PPR) + log(n) + log(b)”. In Section 3.1.1, the paper describes the proposed approach as an efficient alternative to factorizing matrix M, preserving the similarities of PPR. Nevertheless, the hashing algorithm is applied to the rows of matrix M, so the approach mainly targets to preserve the similarities in MM^T instead of M as stated in Lemma 3.2. That’s why it seems that Lemma 3.1 does not contribute much to the presentation of the method. The paper also provides the proof of Lemma 3.1 in the Appendix, although this is somehow not relevant to the scope of the paper. \n\n# Theoretical background\n\n--- Lemma 3.2 is very similar to the first part of Lemma 2 in [Weinberger et al., 2009] and Lemma 3.3 relies highly on Theorem 3.2 of the paper [Andersen et al. (2007)]. Thus, it is preferable to provide references for these papers while presenting the lemmas. Similarly, for the proof of Theorem A.5 (ref Theorem 3.4) in the Appendix, the paper should give reference to Theorem 3.2 of Andersen et al. (2007).\n\n--- In the proof of Lemma A.4 (ref Lemma 3.3), I think the expression “... and only if a neighbor of w has positive score” should be replaced with “... and only if there is a node w in the graph such that r[w] greater than \\epsilon \\times deg(w).” In the proof, the “push” operation is also not defined.\n\n--- In the proof of Theorem 3.5, the symbol \\epsilon is used for the InstantEmbedding algorithm corresponding to the term defined for \\epsilon-approximate Pagerank vector. However, the \\epsilon used for GraphEmbedding indicates the desired precision of the approximation. I think it is not clear that the resulting vectors obtained by these two algorithms with the same epsilon value produce the same vectors. The authors should elaborate more on it in the proof of the theorem. For instance, [Andersen et al. (2007)] demonstrates that the total difference between the PageRank vector and the \\epsilon-approximate PageRank vector can be bounded in terms of \\epsilon and vol(S) for a given set S.\n\n--- Although the paper mentions that it applies the classic random walk settings in the paper, it actually uses the same updated rules (Algorithm 3 in Appendix) as in Andersen et al. (2007). Thus, the paper works on the PageRank vectors corresponding to the alpha values in the lazy random walk strategy. As the paper states in Section A.7, the alpha for the formulation given in Eq. 1 is different for the same vectors, so Eq. 1 needs to be reformulated.\n\n--- The authors remove the constant “b” but not “n” from the target objective matrix. Is there a particular reason for this choice? \n\n--- In Table 1, the complexity of the proposed approach is provided for learning the representation of a specific node, while the complexities of the baseline methods are given for the whole network structure. I believe that it might be better to introduce an additional parameter for the proposed approach to indicate the desired number of nodes to learn embeddings. For the complexities of the baseline methods, the paper should also provide references for them.\n\n\n# Experiments\n\n--- For the experiments shown in Figure 1, it seems that the scores for the baseline methods are given for the whole network, while for the proposed method they are stated for only one node. I think it might be better to follow the same strategy for the InstantEmbedding, in order to have a fair comparison -- since we need embeddings for the whole network structure, for instance, for the link prediction experiment in Table 4. The chosen \\epsilon values are not also described in the experiments in Figure 1, although \\epsilon has a significant influence on the running time.\n\n--- For the link prediction experiment, the paper should use all networks listed in Table 2 in order to have a more complete view of the experimental evaluation of the method.\n\n--- For the classification experiments, although the paper uses 1%, 5%, and 9% training ratios for all networks, it considers 10%, 50%, and 90% training ratios for the Blogcatalog dataset. Is there any particular reason for that? Besides, the VERSE algorithm mostly shows better performance for the link prediction task. How is this behavior explained? \n\n--- In Table 3, the performance of node2vec is better than InstantEmbedding on Blogcatalog network, so its score should be in bold. For the Flickr network, the score of Deepwalk should also be in bold.\n\n--- Another very important aspect has to do with the baselines used in the paper. In the related literature, there are many recently proposed scalable representation learning models that are not used in the experimental evaluation.  Although the paper provides references for some recent scalable algorithms such as RandNE [Zhang et al., 2018] and FREDE [Tsitsulin et al. (2020)], it does not consider them as baseline methods in the experiments. The paper uses solely FastRP [Chen et al., 2019] and the classical node embedding methods to compare the performance of the method, while other recent models are known to perform better than FastRP.  Why recent scalable methods such as NodeSketch [1] and LouvainNE [2], are not considered in the experiments? Besides, why is FREDE (matrix factorization formulation of VERSE)  not used as a baseline?\n\n[1] Dingqi Yang, Paolo Rosso, Bin Li and Philippe Cudre-Mauroux, NodeSketch: Highly-Efficient Graph Embeddings via Recursive Sketching, KDD 2019\n[2] Ayan Kumar Bhowmick, Koushik Meneni, Jean-Loup Guillaume, Maximilien Danisch, Bivas Mitra, LouvainNE: Hierarchical Louvain Method for High Quality and Scalable Network Embedding WSDM 2020\n\n# Typos\nIn Subsection 2.1, “v \\in G” should be “v \\in V”\nIn the second paragraph of Subsection B.4.1, “For each methods” should be “For each method”\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an efficient algorithm to obtain a node embedding based on its local PageRank scores. The proposed approach uses a hashing technique and a local partition approach to make the method more efficient and effective. However, the paper has significant drawback and can be further improved in the following aspects: 
1. The experimental evaluation is weak and does not allow us to draw meaningful conclusions about the proposed algorithm. 
2. The proposed algorithm does not show significant performance improvement on the link prediction task.
Decision: Reject