PecanPy: A parallelized, efficient, and accelerated node2vec(+) in Python
Learning low-dimensional representations (embeddings) of nodes in large graphs is key to applying machine learning on massive biological networks. Node2vec is the most widely used method for node embedding. PecanPy is a fast, parallelized, memory efficient, and cache optimized Python implementation of node2vec. It uses cache-optimized compact graph data structures and precomputing/parallelization to result in fast, high-quality node embeddings for biological networks of all sizes and densities. Detailed source code documentation can be found here.
The details of implementation and the optimizations, along with benchmarks, are described in the application note PecanPy: a fast, efficient and parallelized Python implementation of node2vec, which is published in Bioinformatics. The benchmarking results presented in the preprint can be reproduced using the test scripts provided in the companion benchmarks repo.
v2 update: PecanPy is now equipped with node2vec+, which is a natural extension of node2vec and handles weighted graph more effectively. For more information, see Accurately Modeling Biased Random Walks on Weighted Graphs Using Node2vec+. The datasets and test scripts for reproducing the presented results are available in the node2vec+ benchmarks repo.
Installation
Install from the latest release with:
$ pip install pecanpyInstall latest version (unreleassed) in development mode with:
$ git clone https://github.com/krishnanlab/pecanpy.git
$ cd pecanpy
$ pip install -e .where -e means "editable" mode so you don't have to reinstall every time you make changes.
PecanPy installs a command line utility pecanpy that can be used directly.
Usage
PecanPy operates in three different modes โ PreComp, SparseOTF, and DenseOTF โ that are optimized for networks of different sizes and densities; PreComp for networks that are small (โค10k nodes; any density), SparseOTF for networks that are large and sparse (>10k nodes; โค10% of edges), and DenseOTF for networks that are large and dense (>10k nodes; >10% of edges). These modes appropriately take advantage of compact/dense graph data structures, precomputing transition probabilities, and computing 2nd-order transition probabilities during walk generation to achieve significant improvements in performance.
Example
To run node2vec on Zachary's karate club network using SparseOTF mode, execute the following command from the project home directory:
pecanpy --input demo/karate.edg --output demo/karate.emb --mode SparseOTFNode2vec+
To enable node2vec+, specify the --extend option.
pecanpy --input demo/karate.edge --output demo/karate_n2vplus.emb --mode SparseOTF --extendNote: node2vec+ is only beneficial for embedding weighted graphs. For unweighted graphs, node2vec+ is equivalent to node2vec. The above example only serves as a demonstration of enabling node2vec+.
Demo
Execute the following command for full demonstration:
sh demo/run_pecanpyMode
As mentioned above, PecanPy contains three main modes for generating node2vec random walks, each of which is better optimized for different network sizes/densities:
| Mode | Network size/density | Optimization |
|---|---|---|
PreComp |
<10k nodes, <0.1% edges | Precompute second order transition probabilities, using CSR graph |
SparseOTF (default) |
(โฅ10k nodes, โฅ0.1% and <20% of edges) or (<10k nodes, โฅ0.1% edges) | Transition probabilites computed on-the-fly, using CSR graph |
DenseOTF |
>20% of edges | Transition probabilities computed on-the-fly, using dense matrix |
Compatibility and recommendations
| Mode | Weighted | p,q!=1 |
Node2vec+ | Speed | Use this if |
|---|---|---|---|---|---|
PreComp |
โ | The graph is small and sparse | |||
SparseOTF |
โ | โ | ๐จ | The graph is sparse but not necessarily small | |
DenseOTF |
โ | ๐จ | The graph is extremely dense | ||
PreCompFirstOrder |
โ | โ | Run with p = q = 1 on weighted graph |
||
FirstOrderUnweighted |
โ | ๐จ๐จ๐จ | Run with p = q = 1 on unweighted graph |
Options
Check out the full list of options available using:
pecanpy --helpInput
The supported input is a network file as an edgelist .edg file (node id could be int or string):
node1_id node2_id <weight_float, optional>
Another supported input format (only for DenseOTF) is the numpy array .npz file. Run the following command to prepare a .npz file from a .edg file.
pecanpy --input $input_edgelist --output $output_npz --task todenseThe default delimiter for .edg is tab space (\t), you many change this by passing in the --delimiter option.
Output
The output file has n+1 lines for graph with n vertices, with a header line of the following format:
num_of_nodes dim_of_representation
The following next n lines are the representations of dimension d following the corresponding node ID:
node_id dim_1 dim_2 ... dim_d
Development Note
Run black src/pecanpy/ to automatically follow black code formatting.
Run tox -e flake8 and resolve suggestions before committing to ensure consistent code style.
Additional Information
Documentation
Detailed documentation for PecanPy is available here.
Support
For support, please consider opening a GitHub issue and we will do our best to reply in a timely manner. Alternatively, if you would like to keep the conversation private, feel free to contact Remy Liu at [email protected].
License
This repository and all its contents are released under the BSD 3-Clause License; See LICENSE.md.
Citation
If you use PecanPy, please cite: Liu R, Krishnan A (2021) PecanPy: a fast, efficient, and parallelized Python implementation of node2vec. Bioinformatics https://doi.org/10.1093/bioinformatics/btab202
If you find node2vec+ useful, please cite: Liu R, Hirn M, Krishnan A (2023) Accurately modeling biased random walks on weighted graphs using node2vec+. Bioinformatics https://doi.org/10.1093/bioinformatics/btad047
Authors
Renming Liu, Arjun Krishnan*
*General correspondence should be addressed to AK at [email protected].
Funding
This work was primarily supported by US National Institutes of Health (NIH) grants R35 GM128765 to AK and in part by MSU start-up funds to AK.
Acknowledgements
We thank Christopher A. Mancuso, Anna Yannakopoulos, and the rest of the Krishnan Lab for valuable discussions and feedback on the software and manuscript. Thanks to Charles T. Hoyt for making the software pip installable and for an extensive code review.
References
Original node2vec
- Grover, A. and Leskovec, J. (2016) node2vec: Scalable Feature Learning for Networks. ArXiv160700653 Cs Stat.
Original node2vec software and networks
- https://snap.stanford.edu/node2vec/ contains the original software and the networks (PPI, BlogCatalog, and Wikipedia) used in the original study (Grover and Leskovec, 2016).
Other networks
-
Stark, C. et al. (2006) BioGRID: a general repository for interaction datasets. Nucleic Acids Res., 34, D535โD539.
- BioGRID human protein-protein interactions.
-
Szklarczyk, D. et al. (2015) STRING v10: proteinโprotein interaction networks, integrated over the tree of life. Nucleic Acids Res., 43, D447โD452.
- STRING predicted human gene interactions.
-
Greene, C.S. et al. (2015) Understanding multicellular function and disease with human tissue-specific networks. Nat. Genet., 47, 569โ576.
- GIANT-TN is a generic genome-scale human gene network. GIANT-TN-c01 is a sub-network of GIANT-TN where edges with edge weight below 0.01 are discarded.
BioGRID (Stark et al., 2006), STRING (Szklarczyk et al., 2015), and GIANT-TN (Greene et al., 2015) are available from https://doi.org/10.5281/zenodo.3352323.
- Law, J.N. et al. (2019) Accurate and Efficient Gene Function Prediction using a Multi-Bacterial Network. bioRxiv, 646687.
- SSN200 is a cross-species network of proteins from 200 species with the edges representing protein sequence similarities. Downloaded from https://bioinformatics.cs.vt.edu/~jeffl/supplements/2019-fastsinksource/.