1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//! This module implements embedding of directed/undirected graph with labels attached to nodes/edges.
//!
//! **It is in a preliminary state**
//!
//! It uses the same strategy as the *nodesketch* module, see [nodesketch](crate::embed::nodesketch).
//! We hash labels as they propagate through the the edges of the graph.
//! It is inspired by the Weisfeiler-Lehman algorithm used in Graph Kernel litterature.
//!
//!
//! Some References on Graph Kernels are :
//!
//! - Graph Kernels : A survey. Nikolentzos-Siglidis-Vazirgiannis 2021
// panorama of graphs kernels. links with GNN. Examples et perfs GNN et Graph Kernels comparées.
// Core Weisfeiler-Lehman and Optimal Assignement Vertex Histogram are OK on unlabeled or discrete labeled node graph
//!
//! - Graph Kernels : State of the art and futures challenges Borgwart 2020.
// Taxonomy of graph kernels according to directed/undirected edges continuous/discrete labelling of nodes or edges.
// Message passing Kernels of Nikolentsos seems good and covers the directed/undirected graphs and labelled/continuous nodes.
// (but not edges labelling)
//!
//!
// The first paper :
// - Shervashidze-Borgwardt Weisfeiler-Lehman Graph Kernels 2011
// provides a framework for kernels on unlabeled and discrete labels.
// sorting neighbours labels+ compression (hash) and h iterations.
// complexity h* nb edges
// provides a feature vector for each node, and the whole graph
// local and global WL!
//
// - Power Iterated Color Refinement Kersting-Grohe 2014
// Establishes a link between power iterated color algorithm and relaxed matricial optimization between adjacency matrices.
// Systeme de Hash avec nombre premiers!
//
// - Faster Kernels for Graphs with continuous Attributes via Hashing. 2016
// - Weisfeiler and Lehman go sparse Morris Rattan Mutzel 2020
// - Global Weisfeiler Lehman Kernel Morris-Kersting 2017
//
// - Graph invariant Kernels Orsini IJCAI 2015
// definit un kernel pour les attributs. Le kernel global est le kernel sur les attributs * poids
// dependant du kernel sur les sommets et d'une fonction d appariement des structures matchées sous graphes.
// gere les attributs continus et montre l amelioration des perf avec que sans.
// WL meilleur kernel sur les sommets. Kernel sur les patterns , lables discrets, à batir avec du hash (par 3.1)
//
//
// Comparison GNN with KGraph
//
// - How powerful are Graph Neural Networks Xu-Hu Leskovec 2019
// GNN <= Weisfeiler-Lehman test
//pub mod mgraph;
//pub mod sketch;
/// Defines interface to petgraph.
/// Sketching on top of petgraph.
/// Defines sketching parameters.
/// Defines translations of labels and ranks between raw data from io and our structures in MgraphSketcher.
/// some utilities to load data examples.