7 releases
0.0.7  Mar 30, 2023 

0.0.6  Nov 14, 2022 
0.0.5  Jun 20, 2022 
#302 in Math
129 downloads per month
2MB
7.5K
SLoC
Graphembed
The purpose of this crate is to provide embedding of directed or undirected graphs with positively weighted edges and possibly discrete labels attached to nodes.

embedding methods

For simple graphs, without data attached to nodes/labels, we provide 2 (rust) modules nodesketch and atp. A simple executable with a validation option based on link prediction is also provided.

The module gkernel is dedicated to graphs with discrete labels attached to nodes/edges. We use the petgraph crate for graph description. The algorithm is based on an extension of the hashing strategy used in the module nodesketch.
In the undirected case, this module also computes a global embedding vector for the whole graph. It is still in an early version.


To complement the embeddings we provide also core decomposition of graphs. See the module structure
Methods
The embedding algorithms used in this crate are based on the following papers
 nodesketch
NodeSketch : HighlyEfficient Graph Embeddings via Recursive Sketching KDD 2019. https://dl.acm.org/doi/10.1145/3292500.3330951
D. Yang,P. Rosso,BinLi, P. CudreMauroux.
It is based on multi hop neighbourhood identification via sensitive hashing based on the recent algorithm probminhash. See arxiv or ieee2022.
The algorithm associates a probability distribution on neighbours of each point depending on edge weights and distance to the point.
Then this distribution is hashed to build a (discrete) embedding vector consisting in nodes identifiers.
The distance between embedded vectors is the Jaccard distance so we get
a real distance on the embedding space for the symetric embedding.
An extension of the paper is also implemented to get asymetric embedding for directed graph. The similarity is also based on the hash of sets (nodes going to or from) a given node but then the dissimilarity is no more a distance (no symetry and some discrepancy with the triangular inequality).
The orkut graph with 3 millions nodes and 100 millions of edge is embedded in less than 10' with a 8 core laptop with this algorithm.

gkernel
We use the same scheme as in nodesketch but we hash the nodes labels so the embedding vectors are computed as the summary of node id's or labels attached to nodes flowing through the edges going into or from a node.

atp
Asymetric Transitivity Preserving Graph Embedding 2016
M. Ou, P Cui, J. Pei, Z. Zhang and W. Zhu.
The objective is to provide an asymetric graph embedding and get estimate of the precision of the embedding in function of its dimension.
We use the AdamicAdar matricial representation of the graph. (It must be noted that the ponderation of a node by the number of couples joined by it is called Resource Allocation in the Graph Kernel litterature).
The asymetric embedding is obtained from the left and right singular eigenvectors of the AdamicAdar representation of the graph.
Source node are related to left singular vectors and target nodes to the right ones.
The similarity measure is the dot product, so it is not a norm.
The svd is approximated by randomization as described in HalkoTropp 2011 as implemented in the annembed crate.
The core decomposition algorithms
 Densityfriendly decomposition
Large Scale decomposition via convex programming 2017
M.Danisch T.H Hubert Chan and M.Sozio
The decomposition of the graph in maximally dense groups of nodes is implemented and used to assess the quality of the embeddings in a structural way. See module validation and the comments on the embedding of the Orkut graph where we can use the community data provided with the graph to analyze the behaviour of embedded edge lengths.
In particular it is shown that embedding of edges internal to a community are consistently smaller than embedded edges crossing a block frontier, see results in orkut.md and examples directory together with a small Rust notebook in Notebooks
Some data sets
Without labels
Small datasets are given in the Data subdirectory (with 7z compression) to run tests.
Larger datasets can be downloaded from the SNAP data collections https://snap.stanford.edu/data
Some small test graphs are provided in a Data subdirectory

Symetric graphs

Les miserables http://konect.cc/networks/moreno_lesmis.
This is the graph of cooccurence of characters in Victor Hugo's novel 'Les Misérables'. 
p2pGnutella08.txt.gz https://snap.stanford.edu/data/p2pGnutella08.html


Asymetric graphs

wikivote https://snap.stanford.edu/data/wikiVote.html 7115 nodes 103689 edges

Cora : http://konect.cc/networks/subelj_cora citation network 23166 nodes 91500 edges

Some larger data tests for user to download
These graphs were used in results see below.
Beware of the possible need to convert from Windows to Linux End Of Line, see the dos2unix utility.
Possibly some data can need to be converted from Tsv format to Csv, before being read by the program.

Symetric
 youtube. Nodes: 1 134 890 Edges: 2 987 624 https://snap.stanford.edu/data/comYoutube.html
 orkut. Nodes: 3 072 441 Edges: 117 185 083 https://snap.stanford.edu/data/comOrkut.html

Asymetric
 twitter as tested in Hope http://konect.cc/networks/munmun_twitter_social 465017 nodes 834797 edges
Some results
results for the atp and nodesketch modules
Embedding and link prediction evaluation for the above data sets are given in file resultats.md A more global analysis of the embedding with the nodesketch module is done for the orkut graph in file orkut.md
Some qualitative comments

For the embedding using the randomized svd, increasing the embedding dimension is interesting as far as the corresponding eigenvalues continue to decrease significantly.

The munmun_twitter_social graph shows that treating a directed graph as an undirected graph give significantly different results in terms of link prediction AUC.
Generalized Svd
An implementation of Generalized Svd comes as a byproduct in module gsvd.
Installation and Usage
Installation
The crate provides three features, required by the annembed dependency, to specify which version of lapack you want to use.
For example compilation is done by :
cargo build release features="openblassystem" to use a dynamic link with openblas.
The choice of one feature is mandatory to provide required linear algebra library.
Usage

The Hope embedding relying on matrices computations limits the size of the graph to some hundred thousands nodes. It is intrinsically asymetric in nature. It nevertheless gives access to the spectrum of Adamic Adar matrix representing the graph and so to the required dimension to get a valid embedding in $R^{n}$.

The Sketching embedding is much faster for large graphs but embeds in a space consisting in sequences of node id equipped with the Jaccard distance.

The embed module takes embedding and possibly validation commands (link prediction task) in one directive.
The general syntax is :embed file_description [validation_command validation_arguments] sketching mode embedding_arguments
for example:embed csv ./Data/Graphs/Orkut/comorkut.ungraph.txt symetric "true" validation nbpass 5 skip 0.15 sketching decay 0.2 dim 200 nbiter 5
It is detailed in docs of the embed module. Use cargo doc nodeps as usual.

Use the environment variable RUST_LOG gives access to some information at various level (debug, info, error) via the log and env_logger crates.
Dependencies
~92MB
~1.5M SLoC