# Ultra-fast and efficient network embedding for gigascale biological datasets

Jianshu Zhao, Jean Pierre Both, Rob Knight

► To cite this version:

Jianshu Zhao, Jean Pierre Both, Rob Knight. Ultra-fast and efficient network embedding for gigascale biological datasets. 2025, 10.1101/2025.06.18.660497. cea-05137956

HAL Id: cea-05137956

https://cea.hal.science/cea-05137956v1

Submitted on 1 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
1 Ultra-fast and Efficient Network Embedding for Gigascale Biological

2 Datasets

3 Jianshu Zhao¹, †, Jean Pierre Both², †, Rob Knight¹,³,⁴,⁵,⁶,*

4

5 ¹Department of Pediatrics, School of Medicine, University of California, San Diego, California,

6 USA

7 ²Independent Researcher, Palaiseau, France

8 ³Department of Computer Science & Engineering, University of California, San Diego, California,

9 USA

10 ⁴Halıcıoğlu Data Science Institute, University of California, San Diego, California, USA

11 ⁵Shu Chien-Gene Lay Department of Bioengineering, University of California, San Diego,

12 California, USA

13 ⁶Center for Microbiome Innovation, Jacobs School of Engineering, University of California San

14 Diego, La Jolla, CA, USA

15 †Those Authors contributed equally

16 *Corresponding author: (rknight@ucsd.edu).

17 Running title: Large-scale Biological Network Embedding

18

19

20

21
22 Abstract

23 Graph/network representation learning (or graph/network embedding) is a widely used machine
24 learning technique in industry recommending systems and has recently been applied in
25 computational biology. Popular network representation learning algorithms include random walk
26 and matrix factorization methods, but they do not scale well to large networks. To accommodate
27 the fast growth of real-world network datasets, especially biological datasets, we engineered and
28 improved several network embedding algorithms via intensive computational optimization (e.g.,
29 randomized-generalized singular value decomposition/SVD, efficient sketching via ProbMinHash
30 including edge weights) and parallelization to allow ultra-fast and accurate embedding of large-
31 scale networks. We present GraphEmbed, a computer program for scalable, memory-efficient
32 network embedding. GraphEmbed can perform embedding for large-scale networks with several
33 billion nodes in less than 2 hours on a commodity computing cluster. We benchmark it against
34 standard datasets and demonstrate consistent speed and accuracy advantages over state-of-the-
35 art techniques. We also propose centric AUC, a new metric for evaluating link-prediction accuracy
36 in network embedding. It corrects the bias in conventional AUC caused by the highly skewed node
37 degree distributions, which are typically found in real-world networks, especially biological
38 networks. Taken together, GraphEmbed solves a major challenge in large-scale network
39 representation learning for networks in general and biological networks in particular.

40

41

42

43 **Keywords:** Graph embedding, Sketching, MinHash, hashing, biological network, link prediction,
44 node classification, Generalized SVD
45 **Introduction**

46 Networks or graphs (we use graph and network interchangeably here) are a powerful way to
47 represent data, especially biological data, where data points are connected. A standard approach
48 to computing on networks or graphs is to transform such data into vectorial data—known as graph
49 or network embeddings—to facilitate similarity search, clustering, visualization and community
50 detection¹, ². In a network embedding problem, one is given a directed or undirected network and
51 an induced similarity (or distance) function between its nodes; the goal is to find a low dimensional
52 representation of the network nodes in some metric space so that the given similarity (or distance)
53 function is preserved as much as possible². Embedding approaches have several potential
54 advantages. Algorithms using embeddings are frequently faster than their counterparts which
55 operate on the original graphs. The learned embeddings are often applicable for downstream
56 analysis, either by direct interpretation of the embedding space or by applying machine learning
57 techniques that operate on vectors. Traditional unsupervised methods, including matrix
58 factorization and random walk are based on either singular value decomposition (SVD) or
59 SkipGram, which can be computationally inefficient due to memory and run time constraint.

60 Graph-sampling based techniques design specific models to learn node embeddings from pairs
61 of nodes sampled from an input graph. DeepWalk³ and Node2vec⁴ first sample pairs of nodes
62 from an input graph using random walks, and then feed them into a SkipGram-alike model⁵ to
63 output node embeddings. LINE directly samples node pairs from an input graph considering
64 specifically the 1st- and 2nd-order node proximity⁶. VERSE was recently proposed as a
65 generalized graph-sampling based embedding learning framework that preserves a pre-selected
66 node similarity measure⁷. However, because the embedding learning process of the techniques
67 from this category usually relies on Stochastic Gradient Descent (SGD), a large number of node
68 pairs are often sampled and used to ensure the quality of the learned node embeddings
(convergence of the SGD algorithms). This requires significant computational resources, CPU in particular.

In addition to graph-sampling-based techniques, factorization-based techniques apply matrix factorization to a high-order proximity/adjacency matrix of an input graph to output node embeddings. GraRep preserves the top k-order node proximity by factorizing the top k-order transition matrices⁸; HOPE investigates several different node proximity measures and uses a generalized SVD to factorize the corresponding high-order node proximity matrices⁹; NetMF was recently proposed as a generalized matrix factorization framework unifying DeepWalk, Node2vec and LINE¹⁰. Due to expensive matrix factorization operations, the techniques from this category suffer from computational challenges, especially memory. These computational challenges hinder the application of many of those techniques on large-scale networks. In this paper, we focus on unsupervised network embedding, where graphs have no additional node information. We will not discuss graph neural network-based network embedding systems include GCN, GAT and GraphSAGE¹¹, ¹², ¹³ because these algorithms usually rely on node attributes/labels, as well as other supervised information.

Real-world networks often have edge attributes, such as positive edge weights, that can reflect the strength of interactions between nodes. Most current network embedding schemes ignore edge weights but ideally network embedding methods should not only be able to capture the (binary) information representing links between nodes, but also relative importance of those links¹⁴. Taking social networks and protein-protein interaction networks as examples, the edge weights can carry more information on friendship importance and protein-protein interaction strength, respectively. Computational methods for large and sparse networks have received considerable attention in recent years, e.g., random projection-based methods and randomized
92 SVD-based methods have been applied in large-scale network embedding¹⁵, ¹⁶. However, those
93 methods only support binary information between nodes (or simply unweighted edges).
94 The embeddings learned from the above techniques also face computational challenges when
95 being used in downstream tasks, especially tasks that require similarity computation between
96 embedded node vectors. A typical example is the link prediction problem, in which we try to predict
97 potential missing links between pairs of nodes in a graph to infer possible connections between
98 nodes (e.g., Protein-Protein interactions). Similarity must be computed between all pairs of
99 disconnected nodes in the embedding vector space, then node pairs must be ranked according
100 to their similarity. In the current literature, most of the existing graph embedding techniques
101 measure node proximity using cosine distance (or dot product after normalization). However,
102 cosine distance is known to be slower than Jaccard distance, because dot product with many
103 dimensions is a limiting step¹⁷. Hashing-based methods such as NetHash and NodeSketch on
104 the other hand, avoids SGD and matrix factorization via sketching algorithms¹⁸, ¹⁹. ProbMinHash,
105 a MinHash-like sketching algorithm can be used to compute Jaccard-like distance $J_p(J_p =$
106 $\sum_{d \in D} \frac{1}{\sum_{d' \in D} \max(\omega_A(d') \omega_B(d'))}$) instead of cosine distance between node vectors²⁰, ²¹. MinHash has been
107 widely used for set similarity estimation in large-scale datasets including documents and
108 genomes²², ²³, ²⁴. NodeSketch showed significant improvement for both CPU time and memory
109 consumption via ProbMinHash. Moreover, it is possible to further optimize the computation of
110 ProbMinHash to be even faster²¹. However, there are no standalone and parallelized
111 implementations for NodeSketch, limiting its application in solving real-world large-scale network
112 embedding problems despite its computationally efficiency.
113 Benchmarking network embedding algorithms for downstream tasks is another important topic.
114 For example, link prediction or node classification tasks are the main applications in industry. A
popular metric to evaluate the link prediction accuracy of network embedding algorithms is AUC (area under the receiver operator characteristic curve, or simply AUC-ROC)³, ⁴, ²⁵. AUC has been widely accepted as a universal benchmark and a downstream task for representation learning. However, its validity is seldom questioned. When link prediction performance is measured according to localized metrics, there is a significant drop in quality²⁶. AUC in link prediction is used to benchmark algorithms²⁷; used to evaluate new techniques²⁸; and draw conclusions about properties of ML algorithms²⁵. However, AUC for link prediction by node embedding methods leads to incorrect conclusions about quality²⁶. Therefore, a new link prediction accuracy benchmark metric is urgently needed. For node classification accuracy, the F1 score, a widely used metric of precision, is still the gold standard. Using edge weights or other attributes can greatly improve node classification accuracy (F1 score for example), especially for difficult multi-label classification tasks¹⁴. However, most current embedding algorithms only support unweighted networks due to easier implementation.

Graph embedding has also been applied in computational biology recently, for example, protein-protein interactions prediction²⁹, and inferring gene regulatory networks from single-cell transcriptomic data³⁰, mass spectrometry data³¹ and other biomedical network datasets³². Real-world network and biological network commonly follow an approximately scale-free power-law distribution, meaning that the probability that a node in the network interacts with k other vertices decays as a power-law distribution. Intuitively, scale-free networks contain a few hubs that are connected to many other nodes and many nodes with one or only a few connections. This degree distribution creates a challenge for evaluating the accuracy of network embedding algorithms, for example in the case of link prediction tasks. Recent progress such as VCMPR@k²⁶, studied this problem but still, the skewed node degree problem in link prediction tasks remains unsolved (see Methods & Materials section for details).
Here we implemented and engineered an improved network embedding framework that boosts the performance of network embedding algorithms. We also solved the skewed degree distribution problem in link prediction tasks and unweighted edge problem in node classification tasks. We showed that our implementation is on average 60-100 times faster than other popular network embedding algorithms and can scale to networks with up to 3.5 billion nodes. The link prediction metric we proposed, centric AUC, can provide a new standard for link prediction accuracy evaluation for various network embedding algorithms.

146

## 147 Results

### Centric AUC vs AUC and VCMPR@k, Precision and Recall for Link Prediction

We first analyze node degree distribution for some real-world graphs and how it impacts VCMPR@k. With an edge deletion probability p of 0.2, the binomial distribution of a random graph implies that nodes of degree less than 4 will contribute 0 with probability at least 0.41. Degree quantiles of the Blog, Amazon and Dblp datasets showed we can expect around 10% of nodes to have no edge deleted for the first graph, and around 50% for the second and third (Figure S1A, B and C). Therefore, 12%, 39% and 41% of nodes that do not contribute to VCMPR@k for the Blog, Amazon and Dblp networks respectively. We then compute centric AUC, AUC and VCMPR@k for those networks via GraphEmbed. The Amazon and Dblp datasets have a similar centric AUC with global AUC in sketching-based embeddings (Table 1). The BlogCatalog dataset has a smaller centric AUC value compared to traditional AUC but in a less pronounced way (e.g., smaller value and standard variation) than that of VCMPR@k (Table 1). In both HOPE and sketching embeddings, AUCs are close to 1 while VCMPR@k are close to 0, both showing extreme values due to skewed degree distribution (Table 1). We conclude that centric AUC is more versatile for real world graphs with skewed edge distribution and thus should replace AUC
163 as the standard metric for accuracy evaluation of link prediction tasks, a key application of network
164 embedding algorithms.

165 We then studied the effects of hyperparameters on those link prediction metrics. For HOPE
166 precision mode, hop (i.e., iteration around a node) and precision (RandGSVD precision) had
167 almost no effect on AUC but small effect on VCMPR@10 and centric AUC (Figure 3C, D and E).
168 For the sketching algorithm, we observe a clear convex surface for each metric (Figure 4C, D and
169 E) with respect to two hyperparameters, hop and decay weight α. For precision and recall in
170 sketching mode, a similar convex surface was observed, suggesting optimal hop and α for link
171 prediction task (α=0.3 and k=5) (Figure S3A and B). Those results suggest that node embeddings
172 are often task-specific and should be appropriately generated by tuning parameters for individual
173 network analysis tasks, see also discussion in Yang et al. (2022)³³. For HOPE with RandGSVD
174 in precision mode, the effect of RandGSVD precision and hop on link prediction recall and
175 precision is small (Figure S4A and B). However, we observed that VCMPR@k and centric AUC
176 are more sensitive than AUC (Figure 3C, D and E). In the rank mode, the effects of hop on all 3
177 metrics are small but still VCMPR@k and centric AUC are more sensitive than AUC (Figure S5).

178 Link Prediction Precision and Recall

179 Benchmarks of our HOPE implementation and ProbMinHash-based sketching showed that
180 GraphEmbed is in line with the original implementation for various datasets (Table S2). Based on
181 precision and recall, GraphEmbed (sketching) beat other sketching-based or lean-to-hash based
182 embedding methods consistently across all benchmark datasets and can be more accurate than
183 some of the matrix factorization or random walk-based methods for the Dblp and PPI datasets
184 (Table S2) while being much faster (see next section). However, GraphEmbed (HOPE) is slightly
185 less accurate than other matrix factorization methods such as VERSE and node2vec in terms of
186 precision and recall, the later methods are overall more than 30 times slower than our HOPE
187 implementation and cannot scale even for medium size networks (Table 2). We did not use AUC
188 for benchmarking link prediction accuracy in this case because all datasets mentioned above
189 have skewed node degree distribution.

190 Node Classification Accuracy

191 GraphEmbed sketching algorithm outperforms all sketching baselines except for the Wiki dataset,
192 where baseline KatzSketch is slightly better than GraphEmbed (Table S3). However, KatzSketch
193 involves expensive matrix multiplication/inversion operations to compute the Katz index while
194 GraphEmbed simply relies on ProbMinHash and showed a 243x speedup over KatzSketch on
195 average (Table 2). Among classical network embedding methods, NetMF achieves the best
196 performance on Blog, Wiki and DBLP, while DeepWalk and VERSE are the best ones on POI
197 and YouTube datasets, respectively (Table S3). GraphEmbed sketching shows comparable
198 performance to these best-performing baselines; it has better results on the PPI, Wiki and DBLP
199 datasets, and slightly worse results on Blog and YouTube datasets (Table S3). However,
200 GraphEmbed sketch is far more efficient than these baselines, i.e., 183x, 7840x and 2114x faster
201 than NetMF, DeepWalk and VERSE, respectively (Table 2). The HOPE implementation in
202 GraphEmbed showed similar accuracy with the original implementation in terms of both Micro-F1
203 and Macro-F1 (Table S3), and 7X faster than original HOPE (Table 2). For weighted network,
204 node classification accuracy is significantly improved by considering weight (Table S6) despite
205 that link prediction accuracy is compromised (Table S5).

206 Embedding Gigascale Networks in Approximately One and A Half Hours

207 To compare our ProbMinHash implementation with reference implementations, we simulated
208 weighted vectors and tested the sketching speed. We found that our implementation is about
209 ~1000 times faster than the original ProbMinHash in NodeSketch for vectors with a million
210 elements or more, and performance is comparable for fewer elements (Figure 3a and b). For
sparse networks (many entries are empty in adjacency vectors), we did not expect such a huge speedup because the second pass of data stopped earlier for both original ProbMinHash and our implementation (Figure S2). Next, we compared GraphEmbed HOPE with other matrix factorization or random walk-based methods. First, we compare the accuracy and running time of the limiting step in HOPE, randomized-generalized SVD, with that of traditional SVD. We showed that RandGSVD achieves accuracies almost as good as those of the traditional GSVD but up to dozens of times faster, especially when the dimension is large (Figure 3a and b). Overall, our HOPE implementation in GraphEmbed is about 7 times faster than the original HOPE, which utilizes Jacobi-Davidson partial SVD, due to computational optimization provided through RandGSVD (Table 2, single thread). We observed a ~20 times speedup with our HOPE implementation if parallelized with 64 threads. For small and dense network datasets GraphEmbed sketching method is on average ~60 times faster or more than other hashing-based methods (Table 2) and scales well with respect to the number of computing threads (Figure S6). Detailed CPU and memory usage analysis for test datasets showed that the sketching algorithm is highly efficient (Figure S7). For large-scale sparse networks (unweighted), GraphEmbed sketching took ~1.5h for Hylerlink2012 dataset and is as fast as cutting-edge network embedding algorithms such as SketchNE, that aiming at sparse networks only and is 5 to 10 times faster than other sparse network embedding algorithms (Table S4). However, the memory consumption for processing 3.2 billion nodes in parallel is approximating 1.8T, slightly larger than sparse-signed randomized SVD in SketchNE (1.5T) for the same dataset due to ProbMinHash sketching algorithm (Table S4).

232

233 **Discussion**
In this paper, we provided a fast and efficient network embedding system that is standalone and can be easily deployed to commercial platforms for large-scale (biological) network embedding.

We also provide embedding quality evaluation (e.g., link prediction accuracy and node classification accuracy) so that we can directly compare the performance of various network embedding algorithms. In the case for link prediction tasks, the new metric, centric AUC we proposed showed interesting properties compared to the traditional AUC and VCMPR@k for real-world networks. We suggest that centric AUC should be used instead of traditional AUC because it considers highly uneven node degree distributions, as typically found in real-world networks.

We showed that in many of our benchmarks for real-world networks, AUC is very close to 1 while VCMPR@k is very close to 0 and centric AUC is in the middle. Centric AUC is versatile and has a less extreme distribution on different datasets (Table 1). It has been pointed out that the global "dense metric" of AUC is not attuned to the sparse ground truth, which was the motivation for VCMPR@k26. However, the VCMPR@k, for small k, is an averaged "local" score, and is more appropriate for sparse ground truth without considering from the global "dense metric" perspective. It was suggested that VCMPR@k can only be used in networks that are "globally sparse, yet locally dense" (often measured as low global density and high clustering coefficients)²⁶. For example, VCMPR@k is not meaningful for the PPI (protein-protein interaction) dataset, which has low clustering coefficients, as do many other biological networks. Our centric AUC method can be considered as a mixture of AUC and VCMPR@k and can be applied to any type of networks because the edge sampling is proportional to the degree of nodes. It has been pointed out that AUC is deeply flawed because it creates a data-dependent reweighting of false positives vs. false negatives³⁴. Therefore, precision and recall measures in a global manner should be used³⁵. We also implemented global precision and recall according to³⁶ but it is extremely computationally expensive because it requires computing the whole (number of nodes) matrix similarity between embedded nodes and sorting them to compare to the deleted edges.
This method becomes impractical at a few thousand nodes or above (e.g., the YouTube dataset) even though recall has been proven to be an unbiased metric towards different node degrees³⁷.

Centric AUC employs a degree-specific sampling strategy and is thus more scalable for large networks (Table S7). Another implicit bias related to node degree was also found recently and the author proposed a degree-corrected link prediction task that more effectively trains graph machine-learning models by reducing overfitting to node degrees³⁸. This degree-corrected idea is different from our centric AUC and it also yields smaller values than traditional AUC for various benchmark datasets. A node degree specific sampling strategy was used in our implementation instead of sampling negative edges with the same degree bias as positive edges³⁸. However, it was shown in the degree-corrected sampling paper that for real-world networks with high degree heterogeneity, naive degree-based methods (our method) can achieve near-optimal performance ³⁸. Since there is no need to sample both negative edges and positive edges, naive degree-based methods can be significantly faster and scale to large networks. The degree-corrected VCMPR@k also yields much larger value than the original VCMPR@k and smaller values than AUC, consistent with centric AUC.

Our implementation of HOPE adopted Adamic Adar representation/index of network, which is the most widely used set similarity metric in social networks. The index was proposed as an alternative to Jaccard index for the problem of predicting links, such as friendship or co-authorship, in social networks³⁹. Recent work on this index showed that we can approximate it via a new sketching algorithm called DotHash⁴⁰, in which one can estimate the set intersection cardinality (or shared neighbors between two nodes) without bias by computing the dot product of between two DotHash sketches. Then the Adamic Adar index can then be efficiently approximated. The current limiting step in our HOPE implementation for large-scale networks is the singular value decomposition (SVD) despite our efforts to speed it up via RandGSVD. Single-
pass randomized SVD (key step of RandGSVD) can be further improved as in Yu et.al. 2017<sup>41</sup>, so that a new iterative QB approximation and the power iteration scheme can be incorporated into the single-pass SVD <sup>42</sup> via window-based power iteration<sup>41, 43</sup>, which will further improve accuracy but will require 2 passes. A dynamically shifted power iteration technique can also be applied to improve the accuracy of the randomized SVD. Sparse-signed randomized SVD can also be employed in HOPE for better scalability and less memory constraint, e.g., via the sparse Personalized PageRank proximity measurement between nodes <sup>44</sup>.

The sketching-based network embedding scheme (ProbMinHash) in our system is as fast as the cutting-edge network embedding algorithm such as SketchNE <sup>45</sup> or STRAP <sup>44</sup>, which employed sparse-sign randomized streaming SVD<sup>42, 46</sup>. However, sparse-sign randomized SVD works well only if eigenvalues are well separated and that is only expected for sparse networks<sup>47</sup>, not dense networks, which also helps explain why SketchNE is slower than other sketching-based embedding methods and less accurate for small and dense dataset such as BlogCatalog<sup>45</sup>. Therefore, SketchNE cannot be used for regular networks. Additionally, SketchNE only considers unweighted network data. However, SketchNE is memory efficient than other large-scale network embedding algorithms, including GraphEmbed because the Graph Based Benchmark Suite (GBBS) graph representation format<sup>48</sup> is a better graph data compression format than compressed row representation (CSR) format<sup>49</sup>, which GraphEmbed relies on. We plan to use GBBS graph representation format in future to reduce the memory requirement for graph processing.

Our ProbMinHash-based sketching algorithm for computing Jaccard-like distance ($J_p$) is highly efficient and thus can scale to large networks, either sparse or dense, with weighted edges or unweighted edges. Similar approaches such as SimHash<sup>50</sup>, which is also a locality sensitive hashing and approximates cosine similarity, have also been applied in large-scale attributed
network embedding⁵¹. Another interesting perspective regarding the actual similarity metric for
measuring distance between node representation is that $J_w$ can be calculated via BagMinHash⁵²
or a faster alternative DartMinHash⁵³, instead of ProbMinHash or D²HistoSketch (which
approximate $J_p$), because the weight in recursive sketching can be considered. Both $J_p$ and $J_w$ are
metric distances and the MinHash algorithm approximating them are all locality sensitive hashing.
It would be interesting to also implement DartMinHash in GraphEmbed in the future. However,
MinHash algorithms for simple Jaccard, which are generally much faster²³, ⁵⁴, ⁵⁵, ⁵⁶, cannot be used
under the recursive sketching scheme because element weight is not considered in those
algorithms (there will always be a weight for the approximate k-order adjacency vector, Figure 2).
GraphEmbed does not provide implementation or benchmark for random-walk based network
embedding because it has been shown that SkipGram with random-walk is theoretically
connected to matrix factorization-based methods: SkipGram with random-walk is essentially
performing implicit matrix factorization¹⁰. Those methods were compared with NetMF in previous
work, which we frequently benchmarked GraphEmbed against. Additionally, GRAPE provided a
convenient network processing and random walk embedding system and is also in Rust⁵⁷. The
current GraphEmbed system also does not consider deep structural information of networks,
which can be important since real-world networks contain global structures. Structure Deep
Network Embedding (SDNE) first considers the high nonlinearity in network embedding and
proposes a deep autoencoder to preserve the first- and the second-order proximities jointly to
preserve the deep network structure⁵⁸. However, SDNE is very difficult to scale to large networks
since the limiting step is still stochastic gradient descent. A specific case for structural information
of networks is the bipartite networks, in which 2 classes of nodes (they are not treated equally)
will be jointly modeled so that the bipartite structure can be considered⁵⁹. Bipartite network
embedding is another interesting problem that has been carefully analyzed at large-scale⁶⁰ and
can be applied for large-scale microbiome data analysis. Recently, it was found that node-specific metrics such as the node local intrinsic dimension (NC-LID) can reflect the local degree of the discriminatory power of an arbitrary graph-based distance function (all above network embedding algorithms use the same graph-based distance function for all nodes)⁶¹. NC-LID can identify nodes with high link reconstruction errors in Node2Vec embeddings. NC-LID can be used as a choice for designing elastic graph embedding algorithms in which hyper-parameters are personalized per node and/or link and adjusted from some base values according to structural graph measures to effectively improve the quality of network embedding algorithms⁶¹. Additionally, node LID-aware methods can also help design new sampling strategies for link prediction accuracy evaluation, e.g., node LID-aware centric AUC or VCMPR@k. However, designing such an embedding algorithm considering different nodes with different NC-LID values can be challenging because we need to compute NC-LID for each node, which can be computationally expensive and difficult to scale to large networks.

In summary, the GraphEmbed network embedding system GraphEmbed we developed will aid large-scale network analysis and facilitate application in industry-level recommending systems, as well as designing faster and more efficient network embedding algorithms (via the new link prediction metric). The flexible interface and parallelized implementation can be easily tuned to integrate new network embedding algorithms. GraphEmbed will save a vast number of computational resources (in terms of CPU hours) and thus facilitate knowledge capture in network biology and more generally, network and machine learning sciences.

## Methods & Materials

The overall schematic overview of the GraphEmbed system can be found in Figure 1. Specifically, there are two modes in GraphEmbed, embedding mode and validation mode. Embedding mode
only performs embedding while validation mode also performs embedding accuracy evaluation,
including link prediction accuracy evaluation with AUC, centric AUC and VCMPR@k and multi-
node classification accuracy with F1 score (Macro or Micro, see below). For both modes, 2
embedding options, HOPE and Sketching can be chosen. We applied cutting-edge computational
optimization to speed up HOPE and sketching algorithms. We also made GraphEmbed a flexible
system so that new embedding algorithms can be easily integrated into this framework without
worrying about other implementations (e.g., network representation and processing, embedding
performance evaluation). For validation mode, we also provided an option to vary the subsampling
ratio of the full network and an option for running a given number of repeated experiments for
training and evaluation.

365 Precision, AUC, VCMPR@k and Centric AUC

366 First, we revisit the link prediction metric VCMPR@k 26, which is an alternative to frequently-used
367 AUC and considered an uneven distribution of edge degree. It is defined as the mean over nodes
368 i of VCMPRᵢ(k) = tᵢ(k) / min(rᵢ,k) with rᵢ being the number of edges deleted from the full graph to the train
369 graph and tᵢ being the number of ground truth edges in this list. However, for many real-world
370 graphs, node degrees follow a power law distribution62; a large fraction of nodes may have degree
371 much lower than the mean degree. These impacts VCMPR@k as VCMPRᵢ(k) is not defined for
372 nodes with no edge to delete. However, it is possible to sample the nodes according to node
373 degree distribution for edge deletion. We define centric AUC in the following way: Let i be a node,
374 dᵢ its degree, rᵢ the number of deleted edges incident to i. After edge deletion, a node i has
375 degree dᵢ - rᵢ and we have n - 1 - (dᵢ - rᵢ) potential edges to test. Given a node i, we first sort
376 the n-1 edges by decreasing prediction of existence of a true edge between nodes i and j. We
377 then define cⱼ as the number of true edges seen up to node j. When exploring the j-th node, there
are 2 possibilities: (1). *j* corresponds to a training edge, if so, we increment *c*<sub>*j*</sub> by 1; 2. *j* corresponds to a deleted edge. As our array is sorted, the probability that this edge has a higher ranking than a random edge is simply the ratio of potential edges after *j* to the total number of potential edges $\frac{n-j-(d_i-r_i)(-c_j))}{n-1-(d_i-r_i)}$. Averaging over deleted edge indexes *j*, this defines a centric AUC at node *i*, then averaging over uniformly sampled nodes, we have a centric AUC for all sampled nodes. The centric AUC estimation was then compared with original AUC and *VCMPR@k*. Note that centric AUC and *VCMPR@k* works for both directed and undirected networks but the sampling for each node should be direction aware for directed networks.

We also implemented precision and recall according to Lü and Zhou³⁶. Specifically, precision and recall were calculated the following equation: *precision* = $\frac{TP}{TP+FP}$, *recall* = $\frac{TP}{TP+FN}$, where TP is true positives, FP false positive and FN is false negative. Precision is the proportion of correctly predicted positive links (edges) out of all the predicted positive links while recall is the proportion of correctly predicted positive links (edges) out of all the actual positive links in the network. Since precision and recall works for both directed and undirected networks, the edge deletion is performed as follows: For a directed network edge *i* to *j* and *j* to *i* are deleted/kept together whereas for an undirected network they are treated independently.

*Computational optimization for HOPE: Randomized and Generalized Singular Value Decomposition (RandGSVD) with parallelization*

In several network node representation formats in original HOPE (High-Order Proximity preserved Embedding), we implemented 3 of them, Katz index, Personalized PageRank and Adamic Adar⁹.

Adamic Adar is the default option since it is widely used in social network link prediction³⁹. Instead of the generalized SVD (Jacobi–Davidson type partial SVD) used in original paper⁶³, we instead use randomized and generalized SVD (RandGSVD)⁶⁴ for matrix factorizations step in our HOPE
401 implementation, as it works for all matrices, dense or sparse with deterministic error bound under
402 both the spectral norm and Frobenius norm<sup>42, 65</sup>. Specifically, the node proximity measurements
403 problem (multiplication of two polynomials of matrices) under any of the 3 indexes mentioned
404 above can be transformed into a generalized SVD problem<sup>9</sup>. Randomized-generalized SVD is
405 more efficient in time and space than traditional generalized SVD due to randomized SVD
406 algorithm<sup>42</sup>. Furthermore, randomized SVD has also been used for dimensionality reduction tasks
407 (e.g. PCA) in large-scale biological data analysis in a streaming fashion (e.g., single cell RNA
408 sequencing data, microbiome data)<sup>41, 42, 43</sup> although it exhibits some accuracy loss for high rank
409 matrices<sup>66</sup>. We implemented both versions of RandGSVD, fixed precisions and fixed rank,
410 corresponding to algorithm 2.2 and 2.4 as in Wei et.al. (2021)<sup>64</sup>. The underlying single-pass
411 randomized SVD was implemented according to Halko et.al. (2010)<sup>42</sup>, including both fixed
412 precisions and fixed rank mode. Basic matrix operations were supported via BLAS (Basic Linear
413 Algebra Subprograms) interface. The original HOPE algorithm was designed for directed
414 networks to preserve transitivity<sup>9</sup> but in our implementation, we provided additional support for
415 undirected networks so that both VCMPR@k and centric AUC can be applied to evaluate link
416 prediction performance, which also preserve transitivity for undirected networks.

417 *ProbMinHash sketching considering edge weights*

418 Our network embedding algorithm based on sketching extends and improves the original
419 sketching algorithm in NodeSketch<sup>18</sup>. Briefly, GraphEmbed sketching learns high-order node
420 embeddings in a recursive manner via ProbMinHash (Figure 2A, B and Supplementary Figure
421 S2). To output the k-order embedding of a node, it sketches approximate k-order Self-Loop-
422 Augmented (SLA) adjacency vector of the node via ProbMinHash, which is generated by merging
423 the node's SLA adjacency vector with (k-1)-order embeddings of all the neighbors of the node in
424 a weighted manner. One key property of the sketching technique is the uniformity of the generated
samples, which serves the foundation of the recursive sketching process. Based on the uniformity property, the sketching process works in the following way. First, for each node r, we compute an approximate k-order SLA adjacency vector $\tilde{V}^r(r)$, by $\tilde{V}_i^r(k) = V_i^r + \sum_{n \in \Gamma(r)} \frac{\alpha^n}{n} \sum_{j=1}^L \mathbf{1}_{[S_j^n(k-1)=i]}$, $i = 1, 2, 3, \dots, D$, where $\Gamma(r)$ is the set of neighbors of node r, $S_j^n(k-1)$ is the (k-1)-order sketch vector of node n, and $\mathbf{1}_{[\text{cond}]}$ is an indicator function, which equals 1 when cond is true and 0 otherwise (Figure 2B). More precisely, the sketch element distribution for one neighbor n, (e.g., $\frac{1}{L} \sum_{j=1}^L \mathbf{1}_{[S_j^n(k-1)=i]}$) approximates the (k-1)-order SLA adjacency vector of the neighbor, which preserves the (k-1)-order proximity. Subsequently, by merging the sketch element distribution for all the node's neighbors with node's SLA adjacency vector, we indeed expand the order of proximity by one and therefore obtain an approximate k-order SLA adjacency vector of the node (Figure 2B). During the summing step, we assign an exponential decay weight $\alpha$ to the sketch element distribution, in order to give less importance to high-order node proximity. This is a widely used weighting scheme in measuring high-order node proximity⁹. Finally, we generate the k-order node embeddings $S(k)$ by sketching the approximate k-order SLA adjacency vector $\tilde{V}^r(r)$ using hash function in ProbMinHash. Note that for the weighted edge network, the SLA adjacency vector of each node will have weight for each of its edges but 1 for itself (diagonal) (Figure 2A), other steps are the same with unweighted edge. We also extend the original NodeSketch algorithm (that only supports undirected network) to allow directed network embedding. All the steps are the same except that the SLA adjacency matrix is not symmetric.

We implemented and optimized the ProbMinHash algorithm as introduced in Ertl (2020)²¹ and Li et al. (2022)⁶⁷ as an alternative to D²HistoSketch in NodeSketch for the sketch step mentioned above¹⁸, ⁶⁸. Specifically, a class of optimized ProbMinHash algorithms were implemented, including ProbMinHash1, ProbMinHash1a, ProbMinHash2, ProbMinHash2a, ProbMinHash3,
ProbMinHash3a, ProbMinHash4 and ProbMinHash4a. They all share the same estimation accuracy with original ProbMinHash. Note that both ProbMinHash and D²HistoSketch approximate $J_p = \sum_{d \in D} \frac{1}{\sum_{d' \in D} \max\left(\frac{\omega_A(d') \omega_B(d')}{\omega_A(d') \omega_B(d')}\right)}$, instead of $J_W = \frac{\sum_{d \in D} \min(\omega_A(d), \omega_B(d))}{\sum_{d \in D} \max(\omega_A(d), \omega_B(d))}$ (or min-max similarity)²¹. $J_p$ is a generalized min-max similarity index on probability distributions, and it is pareto optimal⁶⁷. See supplementary methods for the comparisons between $J_p$ and $J_W$. Similar to SuperMinHash, multiple hash functions were used in ProbMinHash so that when there are empty buckets, up to s rounds of re-hashing the input with a new hash function $h_i$. This is sufficiently fast in expectation, since it's exceedingly rare to have empty buckets. If there are still empty buckets, we fall back to s hashes $h'_i$, the ith of which maps all values into bucket i so that it is guaranteed each bucket will eventually be non-empty. Over the first s rounds, every element is mapped exactly once to each bucket by explicitly constructing a permutation to control the bucket each element is mapped to in each round⁶⁹. ProbMinHash also tracks for each bucket the best value seen so far, and ensures that for each element, the hash-values for each bucket are generated in increasing order so that the insertion of an element can be stopped early (Figure S2). In practice, we used ProbMinHash3a because it is the fastest among all variants due to computational optimization. In addition, the performance gain of ProbMinHash3a is achieved by calculating signature components (or sketch) not independently, but collectively²¹. To further speedup distance computation, we employed Simple Instruction Multiple Data (SIMD) for hamming distance computation between sketch vectors, which are collision probability of hashes. The SIMD distance implementation showed significant improvement only for large sketch sizes (e.g., > 1000).

Link Prediction task
Link prediction predicts potential links between nodes in a network. In this task, we use the same setting as in Yang et al. (2019)⁹. Specifically, we first randomly sample 20% of the edges from each graph as testing data, and then use the rest of the graph for training (Figure 1). After learning the node embeddings based on the training graph, we predict the missing edges by generating a ranked list of potential edges. For each pair of nodes, we use the Cosine or $J_p$ (according to the embedding techniques) of their embeddings to generate the ranked list. We randomly sample 0.1% pairs of nodes for evaluation (0.01% on YouTube). We report the average precision@100 and recall@100 on the Blog, PPI, Wiki and DBLP datasets, and precision@1000 and recall@1000 on the YouTube dataset from 5 repeated trials. We did not benchmark GraphEmbed with large and sparse graph for link prediction tasks due to computational challenges (due to their large sizes).

## Multi-label Node classification tasks

Multi-label node classification tasks predict the most probable label(s) for some nodes based on other labeled nodes. In this experiment, we randomly pick a set of nodes as labeled nodes for training and use the rest for testing. To fairly compare node embeddings with different similarity measures, we train a support vector machine (SVM) classifier (cosine or $J_p$ according to the embedding techniques) to return the most probable labels for each node. In classification tasks, we report the average Macro-F1 and Micro-F1 scores from 5 repeated trials, with 90% training ratio on the BlogCatalog, PPI, Wiki and DBLP datasets, and 10% training ratio on the YouTube dataset. In multi-label classification tasks, F1 score is defined below: $F1\ score = \frac{TP}{TP+0.5*(FP+FN)}$.

We calculate the F1 score for each class in a One-vs-Rest (OvR) approach instead of a single overall F1 score, as seen in binary classification. The macro F1 score is computed using the arithmetic mean (aka unweighted mean) of all the per-class F1 scores while Micro F1 computes a global average F1 score by counting the sums of the True Positives (TP), False Negatives (FN),
and False Positives (FP). We did not benchmark node classification tasks for large and sparse network datasets because training SVM classifiers for millions of nodes is computationally prohibitive. For weighted networks, the training and testing steps are the same but we only use the Coauth-MAG and Colisten-Spotify dataset. The calculation of Macro F1 and Micro F1 was performed via the Python package Scikit-Learn⁷⁰.

### Other network embedding algorithms and parameters for benchmark

We chose a total of 15 published network embedding algorithms for benchmark. For random-walk based and matrix factorization-based algorithms, we choose DeepWalk³, LINE⁶, Node2Vec⁴, VERSE, NetMF¹⁰, GraRep⁸ and original HOPE⁹. Same parameters were used as in Yang et al. (2019)⁹ for those algorithms. For hashing-based algorithms, we chose NetHash¹⁹, KatzSketch⁹ and original NodeSketch¹⁸. Same parameters were used for those algorithms. For randomized SVD-based network embedding algorithms, we chose RandNE⁷¹, FastRP¹⁵, ProNE⁷², LightNE¹⁶ and SkethNE⁴⁵. The same parameters were used as in Xie et al. (2023)⁴⁵ for those algorithms.

### Parameter setup in GraphEmbed

For our HOPE implementation, a default setup was used according to original paper. However, for NodeSketch, decay weight $α = 0.001$ and number of iterations 5 for multi-node classification tasks, and $α = 0.3$ and $k = 5$ for link prediction tasks were used. We varied $α$ and $k$ on several small to medium testing datasets to determine $α$ and $k$ according to the highest precision and recall (Figure S3A and B).

### Benchmark Datasets and Implementation Details

Several standard network benchmark datasets were used, including both undirected, directed, unweighted and weighted networks. Several large-scale networks were also included for testing the performance of GraphEmbed. See Table S1 for detailed characteristics of each dataset.
GraphEmbed utilizes compressed raw representation (CSR) format to represent adjacent matrix extracted from networks. The whole embedding system is in pure Rust and is fully parallelized whenever possible. Intel MKL library (OpenMP for multi-threading) or OpenBLAS (OpenMP for multi-threading) as the backend system level support for matrix operation through ndarray-linalg interface, the former is only supported on x86 systems while the latter supports various systems including ARM. All benchmarks throughout the paper were performed on 2 AMD EPYC 7302 16-core processor with a total of 64 threads available, unless specified otherwise. The output of embeddings is stored in MongoDB bson format (or binary JSON) for space efficiency and fast parsing. We provide scripts for parsing embeddings so that the embeddings can be easily used in Python Numpy vector or matrix format.

527

## Code and Data Availability

Code for GraphEmbed can be found here: https://gitlab.com/Jianshu_Zhao/graphembed or via Zenodo^73. ProbMinHash library can be found here: https://github.com/jean-pierreBoth/probminhash. Scripts for reproducing results can be found here: https://gitlab.com/Jianshu_Zhao/graphembed-analysis. All testing data used in this study are open sourced and can be found freely online. GraphEmbed is also available in Bioconda (https://anaconda.org/bioconda/graphembed) or PyPi (https://pypi.org/project/graphembed-rs/) as a python library, also as part of the scikit-bio library.

529

530

531

532

533

534

535

## Acknowledgements

We want to thank Daniel McDonald and Igor Sfiligoi for the helpful discussion about the main results of our manuscript. We want to thank Ertl Otmar for reference implementation of ProbMinHash algorithms. We also want to thank Claire Wang and Sherlyn Weng for testing

537

538

539
GraphEmbed, and Celeste Allaband for help with proofreading. This work was funded in part by
the Department of Energy, USA to R.K. (DE-SC0024320)

## Author contribution

J.Z, J.P.B and R.K designed the work. J.Z and J.P.B implemented the ProbMinHash and
GraphEmbed library. R.K supervised the work. J.Z. did the analysis and benchmark. J.Z., J.P.B
and R.K wrote the manuscript. All authors read and edited the manuscript.

## Conflict of interest Statement

Rob Knight is a scientific advisory board member, and consultant for BiomeSense, Inc., has equity
and receives income. He is a scientific advisory board member and has equity in GenCirq. He
has equity in and acts as a consultant for Cybele. He is a co-founder of Biota, Inc., and has equity.
He is a cofounder of Micronoma and has equity and is a scientific advisory board member. He is
a board member of Microbiota Vault, Inc. He is a board member of N=1 IBS advisory board and
receives income. He is a Senior Visiting Fellow of HKUST Jockey Club Institute for Advanced
Study. The terms of these arrangements have been reviewed and approved by the University of
California, San Diego in accordance with its conflict-of-interest policies.

## References

1. Cui P, Wang X, Pei J, Zhu W. A survey on network embedding. *IEEE transactions on knowledge and data engineering* **31**, 833-852 (2018).

2. Xu M. Understanding graph embedding methods and their applications. *SIAM Review* **63**, 825-853 (2021).

3. Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations. In: *Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining* (2014).
616 17. Wang J, Zhang T, Sebe N, Shen HT. A survey on learning to hash. *IEEE transactions on pattern analysis and machine intelligence* **40**, 769-790 (2017).

618 18. Yang D, Rosso P, Li B, Cudre-Mauroux P. Nodesketch: Highly-efficient graph embeddings via recursive sketching. In: *Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining* (2019).

622 19. Wu W, Li B, Chen L, Zhang C. Efficient attributed network embedding via recursive randomized hashing. In: *IJCAI international joint conference on artificial intelligence* (2018).

626 20. Li P, Li X, Samorodnitsky G. ρ-MinHash Algorithm for Continuous Probability Measures: Theory and Application to Machine Learning. In: *Proceedings of the 31st ACM International Conference on Information & Knowledge Management* (2022).

630 21. Ertl O. ProbMinHash – A Class of Locality-Sensitive Hash Algorithms for the (Probability) Jaccard Similarity. *IEEE Transactions on Knowledge and Data Engineering*, 1-1 (2020).

633 22. Broder AZ, Charikar M, Frieze AM, Mitzenmacher M. Min-wise independent permutations. In: *Proceedings of the thirtieth annual ACM symposium on Theory of computing* (1998).

636 23. Shrivastava A. Optimal densification for fast and accurate minwise hashing. *International Conference on Machine Learning*, 3154-3163 (2017).

639 24. Zhao J, Both JP, Rodriguez-R LM, Konstantinidis KT. GSearch: ultra-fast and scalable genome search by combining K-mer hashing with hierarchical navigable small world graphs. *Nucleic Acids Research* **52**, e74-e74 (2024).

643 25. Mara AC, Lijffijt J, De Bie T. Benchmarking network embedding models for link prediction: Are we making progress? In: *2020 IEEE 7th International conference on data science and advanced analytics (DSAA)*). IEEE (2020).

647 26. Menand N, Seshadhri C. Link prediction using low-dimensional node embeddings: The measurement problem. *Proceedings of the National Academy of Sciences* **121**, e2312527121 (2024).

651 27. Gurukar S, et al. Network representation learning: Consolidation and renewed bearing. *arXiv preprint arXiv:190500987*, (2019).

654 28. Ghasemian A, Hosseinmardi H, Galstyan A, Airoldi EM, Clauset A. Stacking models for nearly optimal link prediction in complex networks. *Proceedings of the National Academy of Sciences* **117**, 23393-23400 (2020).

658 29. Yan R, Islam MT, Xing L. Deep representation learning of protein-protein interaction networks for enhanced pattern discovery. *Science Advances* **10**, eadq4324 (2024).

661 30. Gan Y, Yu J, Xu G, Yan C, Zou G. Inferring gene regulatory networks from single-cell transcriptomics based on graph embedding. *Bioinformatics* **40**, btae291 (2024).

664
665 31. Alvarez-Mamani E, Dechant R, Beltran-Castañón CA, Ibáñez AJ. Graph embedding on mass spectrometry-and sequencing-based biomedical data. BMC bioinformatics 25, 1 (2024).

668 32. Yue X, et al. Graph embedding on biomedical networks: methods, applications and evaluations. Bioinformatics 36, 1241-1251 (2019).

671 33. Yang D, Qu B, Hussein R, Rosso P, Cudré-Mauroux P, Liu J. Revisiting embedding based graph analyses: Hyperparameters matter! IEEE Transactions on Knowledge and Data Engineering 35, 11830-11845 %@ 11041-14347 (2022).

675 34. Hand DJ. Measuring classifier performance: a coherent alternative to the area under the ROC curve. Machine learning 77, 103-123 (2009).

678 35. Lichtnwalter R, Chawla NV. Link prediction: fair and effective evaluation. In: 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining). IEEE (2012).

682 36. Lü L, Zhou T. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications 390, 1150-1170 (2011).

685 37. Wang Y, Derr T. Degree-related bias in link prediction. In: 2022 IEEE International Conference on Data Mining Workshops (ICDMW)). IEEE (2022).

688 38. Aiyappa R, et al. Implicit degree bias in the link prediction task. arXiv preprint arXiv:240514985, (2024).

691 39. Adamic LA, Adar E. Friends and neighbors on the web. Social networks 25, 211-230 (2003).

694 40. Nunes I, et al. Dothash: estimating set similarity metrics for link prediction and document deduplication. In: Proceedings of the 29th ACM SIGKDD conference on knowledge discovery and data mining) (2023).

698 41. Yu W, Gu Y, Li J. Single-pass PCA of large high-dimensional data. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence) (2017).

701 42. Halko N, Martinsson P-G, Tropp JA. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review 53, 217-288 (2011).

705 43. Li Z, Meisner J, Albrechtsen A. Fast and accurate out-of-core PCA framework for large scale biobank data. Genome Research 33, 1599-1608 (2023).

708 44. Yin Y, Wei Z. Scalable graph embeddings via sparse transpose proximities. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining) (2019).

712
713 45. Xie Y, Dong Y, Qiu J, Yu W, Feng X, Tang J. SketchNE: Embedding billion-scale networks accurately in one hour. *IEEE Transactions on Knowledge and Data Engineering* **35**, 10666-10680 (2023).

714
715
716
717 46. Tropp JA, Yurtsever A, Udell M, Cevher V. Streaming low-rank matrix approximation with an application to scientific simulation. *SIAM Journal on Scientific Computing* **41**, A2430-A2463 (2019).

720
721 47. Tropp JA, Yurtsever A, Udell M, Cevher V. Practical sketching algorithms for low-rank matrix approximation. *SIAM Journal on Matrix Analysis and Applications* **38**, 1454-1485 (2017).

724
725 48. Dhulipala L, Blelloch GE, Shun J. Theoretically efficient parallel graph algorithms can be fast and scalable. *ACM Transactions on Parallel Computing (TOPC)* **8**, 1-70 (2021).

727
728 49. Kepner J, Gilbert J. *Graph algorithms in the language of linear algebra*. SIAM (2011).

729
730 50. Charikar MS. Similarity estimation techniques from rounding algorithms. In: *Proceedings of the thirt-y-fourth annual ACM symposium on Theory of computing*) (2002).

732
733 51. Wu W, Li S, Jiang M, Luo C, Li F. Time-and Space-Efficiently Sketching Billion-Scale Attributed Networks. *IEEE Transactions on Knowledge and Data Engineering*, (2024).

735
736 52. Ertl O. BagMinHash - Minwise Hashing Algorithm for Weighted Sets. *Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining*, 1368-1377 (2018).

739
740 53. Christiani T. DartMinHash: Fast Sketching for Weighted Sets. *arXiv preprint arXiv:200511547*, (2020).

742
743 54. Li P, Owen A, Zhang C-H. One permutation hashing. *Advances in Neural Information Processing Systems* **25**, (2012).

745
746 55. Mai T, Rao A, Kapilevich M, Rossi R, Abbasi-Yadkori Y, Sinha R. On densification for minwise hashing. In: *Uncertainty in Artificial Intelligence*. PMLR (2020).

748
749 56. Li P, Li X, Zhang C-H. Re-randomized densification for one permutation hashing and bin-wise consistent weighted sampling. *Advances in Neural Information Processing Systems* **32**, (2019).

752
753 57. Cappelletti L, et al. GRAPE for fast and scalable graph processing and random-walk-based embedding. *Nature Computational Science* **3**, 552-568 (2023).

755
756 58. Wang D, Cui P, Zhu W. Structural deep network embedding. In: *Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining*) (2016).

758
759 59. Gao M, Chen L, He X, Zhou A. Bine: Bipartite network embedding. In: *The 41st international ACM SIGIR conference on research & development in information retrieval*) (2018).
762 60. Yang R, Shi J, Huang K, Xiao X. Scalable and effective bipartite network embedding. In: *Proceedings of the 2022 International Conference on Management of Data*) (2022).

765 61. Savić M, Kurbalija V, Radovanović M. Local intrinsic dimensionality measures for graphs, with applications to graph embeddings. *Information Systems* **119**, 102272 (2023).

768 62. Clauset A, Shalizi CR, Newman ME. Power-law distributions in empirical data. *SIAM review* **51**, 661-703 (2009).

771 63. Hochstenbach ME. A Jacobi-Davidson type method for the generalized singular value problem. *Linear Algebra and its Applications* **431**, 471-487 %@ 0024-3795 (2009).

774 64. Wei W, Zhang H, Yang X, Chen X. Randomized generalized singular value decomposition. *communications on Applied mathematics and computation* **3**, 137-156 (2021).

777 65. Halko N, Martinsson P-G, Shkolnisky Y, Tygert M. An algorithm for the principal component analysis of large data sets. *SIAM Journal on Scientific computing* **33**, 2580-2594 (2011).

781 66. Romanov E. On the Noise Sensitivity of the Randomized SVD. *IEEE Transactions on Information Theory*, (2024).

784 67. Moulton R, Jiang Y. Maximally Consistent Sampling and the Jaccard Index of Probability Distributions. In: *2018 IEEE International Conference on Data Mining (ICDM)*). IEEE (2018).

787 68. Yang D, Li B, Rettig L, Cudré-Mauroux P. D2HistoSketch: Discriminative and dynamic similarity-preserving sketching of streaming histograms. *IEEE Transactions on Knowledge and Data Engineering* **31**, 1898-1911 (2018).

791 69. Ertl O. Superminhash-A new minwise hashing algorithm for jaccard similarity estimation. *arXiv preprint arXiv:170605698*, (2017).

794 70. Pedregosa F, et al. Scikit-learn: Machine learning in Python. *the Journal of machine Learning research* **12**, 2825-2830 (2011).

797 71. Zhang Z, Cui P, Li H, Wang X, Zhu W. Billion-scale network embedding with iterative random projection. In: *2018 IEEE international conference on data mining (ICDM)*). IEEE (2018).

801 72. Zhang J, Dong Y, Wang Y, Tang J, Ding M. Prone: Fast and scalable network representation learning. In: *IJCAI*) (2019).

804 73. Zhao, J. and Both, J. Pierre. (2025) "Efficient and Robust Graph Embedding via High-Order Proximity Preservation or Recursive Sketching". Zenodo. doi: 10.5281/zenodo.15277670.

808
809
810
<figure><img src="image_2.png" /></figure>

**Figure 1.** Schematic overview of GraphEmbed. Upper panel is the embedding mode, in which only the actual embedding process will be performed. HOPE algorithm or sketching algorithm can be used by default. Bottom panel is the validation mode, in which detailed accuracy benchmarks for link prediction and node classification can be performed. The subsampling ratio for training and testing can be easily tuned.
<figure><img src="image_3.png" /><figcaption>**Figure 2.** Overview of GraphEmbed sketching algorithm, an improvement over NodeSketch. (A) Low-order node embeddings can be obtained by sketching the Self-Loop-Augmented (SLA, that is the diagonal in red) adjacency vector of each node, where the sketch length is set to 3. The SLA adjacency vector and the corresponding embeddings of node 1 were highlighted as an example. Then $J_p$ can be efficiently approximated by computing the hamming similarity between node embeddings, which equals the collision probability of hashes in the sketch. (B) High-order node embeddings (in this case $k=3$) via recursive sketching. The detailed recursive sketching process for node 1 based on the SLA adjacency matrix and k-order node embeddings was used as an example. The approximated k-order SLA adjacency vector $\tilde{V}(k)$ by summing the SLA adjacency vector of node 1 and the sketch element distribution in (k-1)-order embeddings of all nodes 1's neighbors (node 1 has only one neighbor node 2 in this case) in a weighted manner (weight is $\alpha=0.2$). Then, the k-order node embeddings were obtained by sketching the approximated k-order SLA adjacency vector $\tilde{V}(k)$ via ProbMinHash.</figcaption></figure>

819

820

821

822

823

824

825

826

827

828

829

830

831

832

833

834

835

836

837

838
<figure><img src="image_4.png" /><figcaption>**Figure 3.** Accuracy (A) and speed (B) benchmark for Randomized Generalized SVD against original generalized SVD for simulated data with increasing dimension. Effects of HOPE RandGSVD precision and hop on link prediction accuracy in the fixed precision algorithm for traditional AUC (C), VCMPR@10 (D) and centric AUC (E), respectively. Maximum rank was set to 128. The BlogCatalog dataset was used for the plot.</figcaption></figure>

839

840

841

842

843

844

845

846

847

848

849

850

851

852

853

854

855

856

857

858
<figure><img src="image_5.png" /><figcaption>**Figure 4.** ProbMinHash algorithm benchmark with respect to number of set elements (or dimension in adjacent vector) and sketch size $m=1024$ (A) and $m=4096$ (B). The weight of set elements was simulated via an exponential function $w(d) \sim \text{Exp}(1)$. The effect of decay ($\alpha$) (x-axis) and number of iterations or hops (y-axis) in GraphEmbed sketching on AUC (C), VCMPR@10 (D) and centric AUC (E) (z-axis). The underlying dataset is BlogCatalog for (A), (B) and (C).</figcaption></figure>

859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
**Table 1.** Comparison of AUC, VCMPR@10 and Centric AUC for link prediction tasks (unweighted network datasets). Dataset information can be found in **Table S1**. Each estimate is the average of 5 independent runs. 2 improved graph embedding algorithms implemented in GraphEmbed, Sketching and HOPE were evaluated.

<table><thead><tr><th>Dataset</th><th>Algo Parameters</th><th>AUC</th><th>VCMPR@10</th><th>Centric AUC (ours)</th></tr></thead><tbody><tr><td colspan="5"><strong>A. Sketching embedding.</strong> Parameters given in a triplet: dimension, nbhops, decay</td></tr><tr><td>BlogCatalog</td><td>1000,5,0.3</td><td>0.930±1.2E-2</td><td>0.044±3.1E-4</td><td>0.681±5.9E-3</td></tr><tr><td>Amazon</td><td>1000,5,0.3</td><td>0.978±3.2E-4</td><td>0.542±1.3E-2</td><td>0.961±4.0E-3</td></tr><tr><td>PPI</td><td>1000,5,0.3</td><td>0.940±2.7E-3</td><td>0.118±6.2E-3</td><td>0.699±6.7E-3</td></tr><tr><td>Dblp</td><td>1000,5,0.3</td><td>0.915±6.6E-3</td><td>0.571±1.35E-2</td><td>0.905±6.5E-3</td></tr><tr><td>YouTube</td><td>1000,5,0.3</td><td>0.898±1.8E-3</td><td>0.056±3.25E-4</td><td>0.810±2.4E-3</td></tr><tr><td>Live-Journal (undirected)</td><td>128,5,0.3</td><td>0.958±3.7E-4</td><td>0.137±8.32E-3</td><td>0.868±7.1E-3</td></tr><tr><td>Friendster</td><td>128,5,0.3</td><td>0.932±1.9E-4</td><td>0.0033±8.5E-4</td><td>0.908±4.8E-3</td></tr><tr><td colspan="5"><strong>B. HOPE embedding<fnref n="1" />.</strong> Parameters given in a couple: dimension/rank, nb iterations</td></tr><tr><td>BlogCatalog</td><td>400,5</td><td>0.952±1.1E-2</td><td>0.167±5.1E-3</td><td>0.698±7.4E-3</td></tr><tr><td>Amazon</td><td>400,5</td><td>0.856±6.1E-3</td><td>0.045±2.9E-4</td><td>0.834±6.4E-3</td></tr><tr><td>PPI</td><td>400,5</td><td>0.901±4.0E-2</td><td>0.119±6.6E-3</td><td>0.549±1.0E-3</td></tr><tr><td>Dblb</td><td>400,5</td><td>0.930±1.7E-2</td><td>0.064±4.7E-4</td><td>0.890±2.2E-3</td></tr><tr><td>YouTube</td><td>400,5</td><td>0.889±2.3E-2</td><td>0.035±7.1E-3</td><td>0.725±1.5E-3</td></tr><tr><td>Live-Journal (undirected)</td><td>400,5</td><td>0.932±1.5E-2</td><td>0.011±1.2E-4</td><td>0.783±1.9E-3</td></tr></tbody></table>

882

883

884

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899

900

901

902

903

904

905

<footnote n="1">¹HOPE employed full matrix factorization via RandGSVD, which is slow for very large datasets such as Friendster. Therefore, we only reported results for small datasets. We use the fixed rank algorithm in RandGSVD.</footnote>
**Table 2.** Embedding speed benchmark (in seconds) and the average speedup over state-of-the-art matrix-factorization and random-walk based methods. Note that GraphEmbed (sketching) multi-threaded implementation can be more than ~60 times faster than GraphEmbed (HOPE) implementation. Speedup within the category was calculated using GraphEmbed method (HOPE or sketching) as the reference point, respectively. Speedup across categories was calculated using GraphEmbed (sketching) as the reference point. – indicates that the algorithm cannot produce results in less than 3 days.

<table><thead><tr><th>Methods</th><th>Blog</th><th>PPI</th><th>Dblp</th><th>Wiki</th><th>YouTube</th><th>Speedup (within category)</th><th>Speedup (across categories)</th></tr></thead><tbody><tr><td>DeepWalk</td><td>3143.2</td><td>1145.0</td><td>4421.3</td><td>1134.1</td><td>698509.1</td><td>117.9x</td><td>7840.3x</td></tr><tr><td>LINE</td><td>1994.7</td><td>2001.6</td><td>2322.1</td><td>1776.0</td><td>24736.8</td><td>58.4x</td><td>3383.6x</td></tr><tr><td>node2vec</td><td>1012.3</td><td>335.5</td><td>472.0</td><td>1208.45</td><td>-</td><td>36.1x</td><td>2400.6x</td></tr><tr><td>VERSE</td><td>983.1</td><td>181.9</td><td>1025.4</td><td>259.3</td><td>215432.0</td><td>31.8x</td><td>2114.7x</td></tr><tr><td>NetMF</td><td>453.0</td><td>111.2</td><td>209.7</td><td>631.9</td><td>-</td><td>17.8x</td><td>183.7x</td></tr><tr><td>GraRep</td><td>3019.5</td><td>321.1</td><td>8912.3</td><td>408.2</td><td>-</td><td>90.6x</td><td>6024.9x</td></tr><tr><td>HOPE</td><td>251.4</td><td>97.7</td><td>325.0</td><td>83.6</td><td>15265.3</td><td>7.0x</td><td>332.5x</td></tr><tr><td><strong>GraphEmbed-HOPE<sup>1</sup></strong></td><td><strong>42.1</strong></td><td><strong>13.0</strong></td><td><strong>54.8</strong></td><td><strong>11.1</strong></td><td><strong>2483.4</strong></td><td><strong>1.0X</strong></td><td><strong>66.5x</strong></td></tr><tr><td>NetHash</td><td>701.3</td><td>183.9</td><td>29.1</td><td>131.6</td><td>11432.9</td><td>341.2x</td><td>341.2x</td></tr><tr><td>KatzSketch</td><td>189.6</td><td>19.1</td><td>232.1</td><td>35.4</td><td>8949.2</td><td>243.4x</td><td>243.4x</td></tr><tr><td>NodeSketch<sup>1</sup></td><td>56.9</td><td>7.4</td><td>9.2</td><td>15.2</td><td>2513.7</td><td>59.6x</td><td>59.6x</td></tr><tr><td><strong>GraphEmbed-Sketch (1)</strong></td><td><strong>13.5</strong></td><td><strong>4.4</strong></td><td><strong>4.3</strong></td><td><strong>5.4</strong></td><td><strong>843.9</strong></td><td><strong>28.2x</strong></td><td><strong>28.2x</strong></td></tr><tr><td><strong>GraphEmbed-Sketch (64)<sup>2</sup></strong></td><td><strong>0.2</strong></td><td><strong>0.3</strong></td><td><strong>0.1</strong></td><td><strong>0.4</strong></td><td><strong>28.4</strong></td><td><strong>1.0X</strong></td><td><strong>1.0X</strong></td></tr></tbody></table>

913
914
915
916
917

<footnote n="1">¹Single-threaded only; ²Parallelized for all steps. 64 threads were used.</footnote>