Awesome
VERSE: Versatile Graph Embeddings from Similarity Measures
This repository provides a reference implementation of VERSE as well as links to the data.
Installation and usage
We make VERSE available in two forms: fast, optimized C++ code that was used in the experiments, and more convenient python wrapper. Note that wrapper is still experimental and may not provide optimal performance.
For C++ executables:
cd src && make;
should be enough on most platforms. If you need to change the default compiler (i.e. to Intel), use:
make CXX=icpc
VERSE is able to encompass diverse similarity measures under its model. For performance reasons, we have implemented three different similarities separately.
Use the command
verse -input data/karate.bcsr -output karate.bin -dim 128 -alpha 0.85 -threads 4 -nsamples 3
to run the default version (that corresponds to PPR similarity) with 128 embedding dimension, PPR alpha 0.85, using 3 negative samples.
Graph file format
This implementation uses a custom graph format, namely binary compressed sparse row (BCSR) format for efficiency and reduced memory usage. Converter for three common graph formats (MATLAB sparse matrix, adjacency list, edge list) can be found in the python
directory of the project. Usage:
$ convert-bcsr --help
Usage: convert-bcsr [OPTIONS] INPUT OUTPUT
Converter for three common graph formats (MATLAB sparse matrix, adjacency
list, edge list) can be found in the root directory of the project.
Options:
--format [mat|edgelist|weighted_edgelist|adjlist]
File format of input file
--matfile-variable-name TEXT variable name of adjacency matrix inside a
.mat file.
--undirected / --directed Treat graph as undirected.
--sep TEXT Separator of input file
--help Show this message and exit.
-
--format adjlist
for an adjacency list, e.g:1 2 3 4 5 6 7 8 9 11 12 13 14 18 20 22 32 2 1 3 4 8 14 18 20 22 31 3 1 2 4 8 9 10 14 28 29 33 ...
-
--format edgelist
for an edge list, e.g:1 2 1 3 1 4 ...
-
--format weighted_edgelist
for an edge list, e.g:1 2 0.1 1 3 2 1 4 0.5 ...
-
--format mat
for a Matlab MAT file containing an adjacency matrix (note, you must also specify the variable name of the adjacency matrix--matfile-variable-name
)
Working with embeddings in Python
Michael Loster provided an example of working with the embedding file from Python. After learning the embeddings the saved binary file can be used the following way:
# The binary file that is the output of the compiled verse binary.
embedding_file = "/path/to/binary/embeddings.bin"
# An optional csv that should contain the mapping of id to some string key.
# E.g., each line should look like "0,http://dbpedia.org/resource/Audi".
index_file = "/path/to/uri/id/mapping.csv"
# Our embeddings have 128 dimensions.
embeddings = Embedding(embedding_file, 128, index_file)
audi_embedding = embeddings['http://dbpedia.org/resource/Audi']
Citation
If you use the code or the datasets, please consider citing the paper:
@inproceedings{Tsitsulin:2018:VVG:3178876.3186120,
author = {Tsitsulin, Anton and Mottin, Davide and Karras, Panagiotis and M\"{u}ller, Emmanuel},
title = {VERSE: Versatile Graph Embeddings from Similarity Measures},
booktitle = {Proceedings of the 2018 World Wide Web Conference},
series = {WWW '18},
year = {2018},
isbn = {978-1-4503-5639-8},
location = {Lyon, France},
pages = {539--548},
numpages = {10},
url = {https://doi.org/10.1145/3178876.3186120},
doi = {10.1145/3178876.3186120},
acmid = {3186120},
publisher = {International World Wide Web Conferences Steering Committee},
address = {Republic and Canton of Geneva, Switzerland},
keywords = {feature learning, graph embedding, graph representations, information networks, node embedding, vertex similarity},
}
Contact
echo "%7=87@=<2=<>5.27" | tr '#-)/->' '_-|'