### 6 stable releases

1.2.0 | Nov 29, 2022 |
---|---|

1.1.0 | Nov 24, 2022 |

1.0.4 | Nov 21, 2022 |

1.0.2 | Nov 17, 2022 |

1.0.1 | Nov 13, 2022 |

#**180** in Machine learning

**36** downloads per month

**MIT**license

185KB

3K
SLoC

# GraphRox

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

## Using the Library

### Rust

To use the library in Rust, add it to

in `[``dependencies``]`

.`Cargo .toml`

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

## 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.

## GraphRox Tutorial

### Graph Basics

The

struct is a basic, unweighted graph structure and the
`graphrox ::`Graph

`graphrox``::`GraphRepresentation

trait defines some methods for some basic graph operations.
Edges and vertices can be added to or removed from a graph. Each vertex in a graph has an
ID, indexed from zero. If an edge is created from the vertex with ID 3 to the vertex with
ID 5, vertices with IDs 0, 1, 2, and 4 are created implicitly.`use` `graphrox``::``{`Graph`,` GraphRepresentation`}``;`
`let` `mut` graph `=` `Graph``::`new_directed`(``)``;`
graph`.``add_edge``(``3``,` `5``)``;`
`//` Vertices 0 through 5 have been defined
`assert_eq!``(`graph`.``vertex_count``(``)``,` `6``)``;`
`assert!``(`graph`.``does_edge_exist``(``3``,` `5``)``)``;`
`let` edges_to_2 `=` `[``4``,` `0``,` `5``,` `1``]``;`
graph`.``add_vertex``(``2``,` `Some``(``&`edges_to_2`)``)``;`
`assert_eq!``(`graph`.``edge_count``(``)``,` `5``)``;`
`//` Add a vertex with ID 8 and no edges. This implicitly defines all vertices IDs less
`//` than 8
graph`.``add_vertex``(``8``,` `None``)``;`
`assert_eq!``(`graph`.``vertex_count``(``)``,` `9``)``;`
`assert_eq!``(`graph`.``edge_count``(``)``,` `5``)``;`
`//` Edges can be removed
graph`.``delete_edge``(``2``,` `5``)``;`
`assert_eq!``(`graph`.``edge_count``(``)``,` `4``)``;`
`assert!``(``!`graph`.``does_edge_exist``(``2``,` `5``)``)``;`

### Graph Approximations

A graph can be approximated into a

with a lower dimensionality. This is
done by average pooling blocks of a given dimension in the adjacency matrix representation
of the graph, then applying a threshold to the average pooled matrix to determine which
entries in the adjacency matrix of the resulting graph will be 1 rather than 0.`graphrox ::`Graph

`use` `graphrox``::``{`Graph`,` GraphRepresentation`}``;`
`let` `mut` graph `=` `Graph``::`new_directed`(``)``;`
graph`.``add_vertex``(``0``,` `Some``(``&``[``1``,` `2``,` `6``]``)``)``;`
graph`.``add_vertex``(``1``,` `Some``(``&``[``1``,` `2``]``)``)``;`
graph`.``add_vertex``(``2``,` `Some``(``&``[``0``,` `1``]``)``)``;`
graph`.``add_vertex``(``3``,` `Some``(``&``[``1``,` `2``,` `4``]``)``)``;`
graph`.``add_vertex``(``5``,` `Some``(``&``[``6``,` `7``]``)``)``;`
graph`.``add_vertex``(``6``,` `Some``(``&``[``6``]``)``)``;`
graph`.``add_vertex``(``7``,` `Some``(``&``[``6``]``)``)``;`
`//` Average pool 2x2 blocks in the graph's adjacency matrix, then apply a threshold of 0.5,
`//` or 50%. Any blocks with at least 50% of their entries being 1 (rather than 0) will be
`//` represented with a 1 in the adjacency matrix of the resulting graph.
`let` approx_graph `=` graph`.``approximate``(``2``,` `0.``5``)``;`
`println!``(``"``{}``"``,` graph`.``matrix_representation_string``(``)``)``;`
`println!``(``)``;`
`println!``(``"``{}``"``,` approx_graph`.``matrix_representation_string``(``)``)``;`
`/*` Ouput:
[ 0, 0, 1, 0, 0, 0, 0, 0 ]
[ 1, 1, 1, 1, 0, 0, 0, 0 ]
[ 1, 1, 0, 1, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 1, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 1, 0, 0, 0, 0, 1, 1, 1 ]
[ 0, 0, 0, 0, 0, 1, 0, 0 ]
[ 1, 1, 0, 0 ]
[ 1, 0, 0, 0 ]
[ 0, 0, 0, 0 ]
[ 0, 0, 1, 1 ]
`*/`

Additionally, a graph can be average pooled without applying a threshold:

`use` `graphrox``::``{`Graph`,` GraphRepresentation`}``;`
`let` `mut` graph `=` `Graph``::`new_directed`(``)``;`
graph`.``add_vertex``(``0``,` `Some``(``&``[``1``,` `2``,` `6``]``)``)``;`
graph`.``add_vertex``(``1``,` `Some``(``&``[``1``,` `2``]``)``)``;`
graph`.``add_vertex``(``2``,` `Some``(``&``[``0``,` `1``]``)``)``;`
graph`.``add_vertex``(``3``,` `Some``(``&``[``1``,` `2``,` `4``]``)``)``;`
graph`.``add_vertex``(``5``,` `Some``(``&``[``6``,` `7``]``)``)``;`
graph`.``add_vertex``(``6``,` `Some``(``&``[``6``]``)``)``;`
graph`.``add_vertex``(``7``,` `Some``(``&``[``6``]``)``)``;`
`let` avg_pool_matrix `=` graph`.``find_avg_pool_matrix``(``2``)``;`
`println!``(``"``{}``"``,` graph`.``matrix_representation_string``(``)``)``;`
`println!``(``)``;`
`println!``(``"``{}``"``,` avg_pool_matrix`.``to_string``(``)``)``;`
`/*` Ouput:
[ 0, 0, 1, 0, 0, 0, 0, 0 ]
[ 1, 1, 1, 1, 0, 0, 0, 0 ]
[ 1, 1, 0, 1, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 1, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 1, 0, 0, 0, 0, 1, 1, 1 ]
[ 0, 0, 0, 0, 0, 1, 0, 0 ]
[ 0.50, 0.75, 0.00, 0.00 ]
[ 0.50, 0.25, 0.00, 0.00 ]
[ 0.00, 0.25, 0.00, 0.00 ]
[ 0.25, 0.00, 0.50, 0.50 ]
`*/`

### Graph Compression

Graphs can be compressed into a space-efficient form. Using the same approximation technique mentioned above, a threshold can be 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.

`use` `graphrox``::``{`Graph`,` GraphRepresentation`}``;`
`let` `mut` graph `=` `Graph``::`new_directed`(``)``;`
graph`.``add_vertex``(``23``,` `None``)``;`
`for` i `in` `8``..``16` `{`
`for` j `in` `8``..``16` `{`
graph`.``add_edge``(`i`,` j`)``;`
`}`
`}`
`for` i `in` `0``..``8` `{`
`for` j `in` `0``..``4` `{`
graph`.``add_edge``(`i`,` j`)``;`
`}`
`}`
graph`.``add_edge``(``22``,` `18``)``;`
graph`.``add_edge``(``15``,` `18``)``;`
`let` compressed_graph `=` graph`.``compress``(``0.``2``)``;`
`assert_eq!``(`compressed_graph`.``vertex_count``(``)``,` `24``)``;`
`assert_eq!``(`compressed_graph`.``edge_count``(``)``,` `96``)``;` `//` 64 + 32
`//` Because half of the 8x8 block was filled, half of the bits in the u64 are ones.
`assert_eq!``(`compressed_graph`.``get_adjacency_matrix_entry``(``0``,` `0``)``,``0x00000000ffffffff``u64``)``;`
`//` Because the entire 8x8 block was filled, the block is represented with u64::MAX
`assert_eq!``(`compressed_graph`.``get_adjacency_matrix_entry``(``1``,` `1``)``,` `u64``::``MAX``)``;`

Compressing a graph yields a

. `graphrox ::`CompressedGraph

`CompressedGraph`

s can be easily
decompressed back into a `graphrox``::`Graph

:`use` `graphrox``::``{`Graph`,` GraphRepresentation`}``;`
`let` `mut` graph `=` `Graph``::`new_undirected`(``)``;`
graph`.``add_vertex``(``0``,` `Some``(``&``[``1``,` `2``,` `6``]``)``)``;`
graph`.``add_vertex``(``3``,` `Some``(``&``[``1``,` `2``]``)``)``;`
`let` compressed_graph `=` graph`.``compress``(``0.``1``)``;`
`let` decompressed_graph `=` compressed_graph`.``decompress``(``)``;`
`assert_eq!``(`graph`.``edge_count``(``)``,` decompressed_graph`.``edge_count``(``)``)``;`
`assert_eq!``(`graph`.``vertex_count``(``)``,` decompressed_graph`.``vertex_count``(``)``)``;`
`for` `(`from_vertex`,` to_vertex`)` `in` `&`decompressed_graph `{`
`assert!``(`graph`.``does_edge_exist``(`from_vertex`,` to_vertex`)``)``;`
`}`

### Saving graphs to disk

GraphRox provides

and `to_bytes``(``)`

methods on `try_from ::`

`<``&``[``u8``]``>``(`

`)`

`graphrox``::`Graph

and
`graphrox``::`CompressedGraph

which convert to and from efficient big-endian byte-array
representations of graphs. The byte arrays are perfect for saving to disk or sending over
a websocket.`use` `graphrox``::``{`CompressedGraph`,` Graph`,` GraphRepresentation`}``;`
`use` `std``::`fs`;`
`let` `mut` graph `=` `Graph``::`new_undirected`(``)``;`
graph`.``add_vertex``(``0``,` `Some``(``&``[``1``,` `2``,` `6``]``)``)``;`
graph`.``add_vertex``(``3``,` `Some``(``&``[``1``,` `2``]``)``)``;`
`//` Convert the graph to bytes
`let` graph_bytes `=` graph`.``to_bytes``(``)``;`
`//` Save the bytes to a file
`fs``::`write`(``"`my-graph.gphrx`"``,` graph_bytes`)``.``unwrap``(``)``;`
`//` Read the bytes from a file (then delete the file)
`let` graph_file `=` `fs``::`read`(``"`my-graph.gphrx`"``)``.``unwrap``(``)``;`
`fs``::`remove_file`(``"`my-graph.gphrx`"``)``.``unwrap``(``)``;`
`let` graph_from_bytes `=` `Graph``::`try_from`(`graph_file`.``as_slice``(``)``)``.``unwrap``(``)``;`
`assert_eq!``(`graph`.``edge_count``(``)``,` graph_from_bytes`.``edge_count``(``)``)``;`
`for` `(`from_vertex`,` to_vertex`)` `in` `&`graph_from_bytes `{`
`assert!``(`graph`.``does_edge_exist``(`from_vertex`,` to_vertex`)``)``;`
`}`
`//` Compressed graphs can be converted to bytes as well
`let` compressed_graph `=` graph`.``compress``(``0.``05``)``;`
`fs``::`write`(``"`compressed-graph.cgphrx`"``,` compressed_graph`.``to_bytes``(``)``)``.``unwrap``(``)``;`
`//` Read the compressed_graph from a file (then delete the file)
`let` compressed_graph_file `=` `fs``::`read`(``"`compressed-graph.cgphrx`"``)``.``unwrap``(``)``;`
`fs``::`remove_file`(``"`compressed-graph.cgphrx`"``)``.``unwrap``(``)``;`
`let` compressed_graph_from_bytes `=`
`CompressedGraph``::`try_from`(`compressed_graph_file`.``as_slice``(``)``)``.``unwrap``(``)``;`
`assert_eq!``(`compressed_graph_from_bytes`.``edge_count``(``)``,` compressed_graph`.``edge_count``(``)``)``;`