graphrox Release 1.2.0

A graph library for graph compression and fast processing of graph approximations

Keywords
approximation, machine-learning, graph
MIT

GraphRox

GraphRox is a network graph library for efficiently generating approximations of graphs. GraphRox additionally provides a high-fidelity, lossy graph compression algorithm.

See https://docs.rs/graphrox/latest/graphrox/ for documentation on using the library in Rust.

Using the Library

Rust

To use the library in Rust, add it to `[dependencies]` in `Cargo.toml`.

```[dependencies]
graphrox = "1.1"```

Python

GraphRox is available on PyPi, so you can install the package with:

`pip3 install graphrox`

And then you can import it:

`import graphrox as gx`

C

After downloading and building GraphRox from source (with `cargo build —release`), a static library and a dynamic link library will each be produced in the `target/release` directory. C code can link to the GraphRox library statically using the compile library and the `gphrx.h` header from the `graphrox-c` directory, or dynamically using the DLL.

How it works

Approximation

The approximation algorithm applies average pooling to a graph's adjacency matrix to construct an approximation of the graph. The approximation will have a lower dimensionality than the original graph. The adjacency matrix will be partitioned into blocks of a specified of dimension and then the matrix entries within each partition will be average pooled. A given threshold will be applied to the average pooled entries such that each entry that is greater than or equal to the threshold will become a 1 in the adjacency matrix of the resulting approximate graph. Average pooled entries that are lower than the threshold will become zeros in the resulting approximate graph. The graph's adjacency matrix will be padded with zeros if a block to be average pooled does not fit withing the adjacency matrix.

Graph Compression

Using the same approximation technique mentioned above, a threshold is applied to 8x8 blocks in a graph's adjacency matrix. If a given block in the matrix meets the threshold, the entire block will be losslessly encoded in an unsigned 64-bit integer. If the block does not meet the threshold, the entire block will be represented by a 0 in the resulting matrix. Because GraphRox stores matrices as adjacency lists, 0 entries have no effect on storage size.

A threshold of 0.0 is essentially a lossless compression.

Testing and Building the Library

The GraphRox library is written in Rust. Building it produces two artifacts: 1) a `.rlib` Rust library that Rust programs can statically link to and 2) a dynamic link library (a `.so` file on Linux, `.dylib` on macOS, or `.dll` on Windows) with a C ABI. These artifacts get placed in the `./target` directory, relative to the top-level of the project.

To build the library, you need to have the Rust Toolchain installed. From the project directory, run `cargo build --release` to build the Binaries.

To run unit tests, run `cargo test`. To generate formatted documentation, run `cargo doc`.