GOSH: Embedding Big Graphs on Small Hardware

GOSH is a GPU-based graph embedding tool that takes a graph and produces d-dimensional vector for every node in the graph. The embeddings can then be used for a multitude of machine learning tasks including node classification, link prediction, graph visualization, and anomaly detection.

GOSH employs a novel coarsening algorithm (MultiEdgeCollapse) to compress the graph into smaller graphs and embeds the smaller graphs to produce very accurate embeddings very quickly. Besides, it uses a special scheduling algorithm to embed any graph using a single GPU - even if the memory requirement of the graph exceeds that of the GPU.

Getting Started

Requirements

We compiled this program with nvcc using CUDA 10.1and ran it on Ubuntu 4.4.0-159.

Compiling

You can build the executables of the project with a single command. Simply clone the repo, navigate to it and call the make command:

git clone https://github.com/SabanciParallelComputing/GOSH
cd GOSH
make clean && make

This will produce two executables:

execs/gosh.out # this executable takes inputs as flags and options. 
execs/gosh_nargparse.out # this executable takes all the parameters as a sequence of strings and none of the parameters are optional

Executing

The most basic execution of GOSH can be done as follows:

execs/gosh.out --input-graph $string --output-embedding $string --directed $number --epochs $number

--input-graph $string: An edge list file with the vertex IDs as zero-indexed integers. i.e, the file should be of the form:

i j
k l
...
a b

Where i, j, k, l, a, b are vertex IDs from the graph. Please note that all vertices will get embeddings - even those without any edges.

--output-embedding $string: The file to which the embeddings are to be printed. The embeddings can either be printed as an ASCII formatted text file or a binary file (can be triggered with the --binary-output flag). The output format in ASCII text is as follows:

num_vertices dimension
0 e_1 e_2 e_3 ... e_dimension-1
1 e_1 e_2 e_3 ... e_dimension-1
...
num_vertices-1 e_1 e_2 e_3 ... e_dimension-1

Where num_vertices and dimension are the number of vertices and the embedding dimensionality, respectively, and every line afterward corresponds to a vertex from the graph. A line starts with the ID of the vertex and is followed by its embeddings. All elements within a line are space-separated.

--epochs $number: The number of epochs to run on the entirety of the graph. Running an epoch on a graph Gi which has been coarsening i times corresponds to running |Vi| positive samples on that graph.
- Note: the strategy in which the epochs are distributed across different levels of coarsening can be tuned using the options --epoch-strategy and --smoothing-ratio and are discussed further below.
--directed $number: Whether the graph is directed (1), undirected (0), or passed as in a Binary Compressed Sparse Row format (2).

Optional Parameters

Many optional parameters can be used to fine-tune the embedding:

Global parameters

-d --dimension $number: an integer with the dimensionality of the embedding.
-s --negative_samples $number: number of negative samples used with every positive update.
--negative-weight $float: a scaling factor used with negative samples to scale the gradients to be used when updating embeddings during negative updates.
--device-id $nummber: the ID of the GPU device to be used during the embedding.
--binary-output: whether the outputs are printed in binary format for compactness and ease of processing on memory. The format of the binary output is as follows:
- The number of vertices as a signed integer
- The embedding dimension as s signed integer
- The embeddings of all the vertices printed sequentially as single precision floats in C++.

Sampling parameters

--sampling-algorithm $number: the method used to create positive samples during training. Currently, two sampling strategies are implemented:
- --sampling-algorithm 0: 1-hop neighbor sampling or PPR sampling as described in VERSE. Depending on the value of --alpha.
  - --alpha 0: positive samples for a node are sampled from its direct neighbors
  - --alpha > 0 && --alpha < 1: positive samples of a node are nodes reached after performing a Personalized Page Rank random walk, with --alpha being the damping factor as defined in VERSE.
- --sampling-algorithm 1: random-walk based sampling. With this method, random walks are generated on the CPU and samples are extracted from them and sent to the GPU. It is controlled with three parameters:
  - --walk-length $number: length of each random walk.
  - --augmentation-distance $number: within a walk, from each sequence of $number$ , all the pairs of nodes are used as poisitive samples.
  - --sample-pool-size: the number of samples to be added to the pool on the CPU which is copied to the GPU.
-a --alpha $number: A value for the positive sampling strategy to be used in the model based on VERSE. alpha = 0 will use an adjacency similarity positive sampling approach while 0 > alpha > 100 will use PPR with alpha/100 as its damping factor.

Learning Rate Parameters

-l --learning_rate $float: The global learning rate of the model.
--learning-rate-decay-strategy $num: The strategy used to decay the learning rate during a level and between different levels. There are four strategies (0/1/2/3), their differences are shown below:
- 0, 1: At every level, learning rate decays linearly from the initial learning rate starting at the first epoch until the last epoch based on the following equation:
```
current_learning_rate = (max(1-current_epoch/total_epochs), 1e-4)*initial_learning_rate
```
where current_epoch and total_epochs are the current and total epochs for the current coarsening level.
- 2, 3: The learning rate at the end of a level i is the same as it is at the beginning. No decay.
- 1, 3; initial learning rate for every coarsening level differs based on the following heuristic:
```
lr_i = lr;  if  |Vi| < LR_REV_NV
lr_i = lr/sqrt(|Vi|/ LR_REV_NV); otherwise
```
Where:
lr = input learning rate (global)
lri = initial learning rate at coarsening level i.
LR_REV_NV = tunable hyperparameter in the src/main.cu
- 0, 2: initial learning rate at each level is the same as the original learning rate given as input

Coarsening Parameters

--no-coarsening: will not apply any coarsening and will run the embedding directly on the original graph.
--coarsening-stopping-threshold $num: the number of vertices to stop coarsening at. i.e, when a graph Gi is generated having |Vi|< $num, it will be added to the coarsened set, but the coarsening will not continue.
--coarsening-stopping-precision $float: the accpetable shrinkage of a graph during coarsening. i.e, if graph Gi is coarsened into graph Gi+1, and |Vi+1| > |Vi| * $float, graph Gi+1 is not added to the coarsened set and coarsening will not continue.
--coarsening-matching-threshold-ratio $num: controls the total number of matches allowed per vertex. Given a graph Gi coarsened i times, a vertex in Gi is not allowed to match more than i * i * ($num / |Vi|) vertices.
--coarsening-min-vertices-in-graph $num: the minimum number of vertices acceptable in a graph to be added into the coarsened set, i.e, if a graph Gi is coarsened into a graph Gi+1 and |Vi+1| < $num, the graph Gi+1 is not added to the coarsened set.

Epoch Distribution Parameters

--epoch-strategy: choose the strategy to use to distribute epochs across levels, there are multiple strategies available:
- fast: The smallest graph is given half of the total epochs and the next level is given half of that, and so on.
- s-fast: COARSE_SMOOTHING_RATIO * total_epochs epochs are distributed equally across levels, while the remainder is distributed based on the fast rule.
- normal: equal distribution of epochs across levels.
- accurate: The opposite of fast; the biggest graph is given half of the total epochs and, the smaller level is given half of that, and so on.
- s-accurate: COARSE_SMOOTHING_RATIO * total_epochs epochs are distributed equally across levels, while the remainder is distributed based on the accurate rule.

NOTE: in all of the aforementioned rules, a level is allocated a minimum of 1 epoch.

--smoothing-ratio: the smoothing ratio used in distributing epochs for the smooth strategies, i.e s-fast and s-accurate.

Large Graph Parameters

--epoch-batch-size $num: the number of epochs to run per large graph execution round, where a single round consists of a full rotation over all the embedding part pairs.
--num-parts $num: the number of embedding parts to store concurrently on the GPU.
--num-pools $num: the number of sample pools to store concurrently on the GPU.
--sampling-threads $num: the number of threads to work on sampling in parallel.
--concurrent-samplers $num: the number of sample pools to be sampled into concurrently, where a single pool can be sampled into by a maximum of sampling-threads / concurrent-samplers threads.
--task-queue-threads $num: the number of threads to execute tasks from the task queue.
--num-sample-pool-sets $num: number of sample pool sets.

Authors

Amro Alabsi Aljundi, Taha Atahan Akyildiz, and Kamer Kaya.

Acknowldegments

Adapted the positive sampling and embedding updates from the VERSE paper written by Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller
Used the Argparse header for C++ written by Hilton Bristow to process CLI inputs: https://github.com/hbristow/argparse

Citation

If you find our code useful for your research, please cite us:

@ARTICLE{9623416,
  author = {Alabsi Aljundi, Amro and Akyildiz, Taha Atahan and Kaya, Kamer},
  journal = {IEEE Transactions on Parallel and Distributed Systems}, 
  title = {Boosting Graph Embedding on a Single GPU}, 
  year = {2021},
  volume = {},
  number = {},
  pages = {1-1},
  doi = {10.1109/TPDS.2021.3129617}
}
@INPROCEEDINGS{9377898,
  author={Akyildiz, Taha Atahan and Alabsi Aljundi, Amro and Kaya, Kamer},
  booktitle={2020 IEEE International Conference on Big Data (Big Data)}, 
  title={Understanding Coarsening for Embedding Large-Scale Graphs}, 
  year={2020},
  volume={},
  number={},
  pages={2937-2946},
  doi={10.1109/BigData50022.2020.9377898}
}

@INPROCEEDINGS{10.1145/3404397.3404456,
    author = {Akyildiz, Taha Atahan and Aljundi, Amro Alabsi and Kaya, Kamer},
    title = {GOSH: Embedding Big Graphs on Small Hardware},
    year = {2020},
    isbn = {9781450388160},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    url = {https://doi.org/10.1145/3404397.3404456},
    doi = {10.1145/3404397.3404456},
    booktitle = {49th International Conference on Parallel Processing - ICPP},
    articleno = {4},
    numpages = {11},
    keywords = {GPU, parallel graph algorithms, link prediction, Graph embedding, graph coarsening},
    location = {Edmonton, AB, Canada},
    series = {ICPP '20}
    note = {Nominated for the best-paper award.}
}

SU-HPC/GOSH