README.md 3.09 KB
Newer Older
Fize Jacques's avatar
Fize Jacques committed
1 2
# Gmatch4py a graph matching library for Python

Fize Jacques's avatar
Fize Jacques committed
3
Gmatch4py is a library dedicated to graph matching. Graph structure are stored in NetworkX graph objects.
Fize Jacques's avatar
Fize Jacques committed
4

Fize Jacques's avatar
Fize Jacques committed
5 6 7 8 9 10 11 12 13

## Requirements
 
 * Python3
 * Cython
 * networkit (for Bag of Cliques)
 
## Installation

Fize Jacques's avatar
Fize Jacques committed
14
To install `GMatch4py`, run the following commands:
Fize Jacques's avatar
Fize Jacques committed
15 16

```
Fize Jacques's avatar
Fize Jacques committed
17 18 19
$ git clone https://github.com/Jacobe2169/GMatch4py.git
$ cd GMatch4py
$ python3 setup.py install
Fize Jacques's avatar
Fize Jacques committed
20 21 22 23 24 25 26 27 28 29 30 31 32 33
```


## Get Started

For now, every algorithms class is composed with a static method called `compare()`. `compare()` takes
two arguments :

 * An array containing the graphs to compare
 * An array containing indexes of graph you want to compare. Set to `None`, if you want to
 measure the similarity/distance between every graphs. 


## List of algorithms
Fize Jacques's avatar
Fize Jacques committed
34 35 36 37

 * DeltaCon and DeltaCon0 (*debug needed*) [1]
 * Vertex Ranking (*debug needed*) [2]
 * Vertex Edge Overlap [2]
Fize Jacques's avatar
Fize Jacques committed
38
 * Bag of Cliques (a bag of words model using cliques as vocabulary)
Fize Jacques's avatar
Fize Jacques committed
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
 * Graph kernels
    * Random Walk Kernel (*debug needed*) [3]
        * Geometrical 
        * K-Step 
    * Shortest Path Kernel [3]
    * Weisfeiler-Lehman Kernel [4]
        * Subtree Kernel 
        * Edge Kernel
 * Graph Edit Distance [5]
    * Approximated Graph Edit Distance 
    * Hausdorff Graph Edit Distance 
    * Bipartite Graph Edit Distance 
    * Greedy Edit Distance
 * MCS [6]
    

## Publications associated

  * [1] Koutra, D., Vogelstein, J. T., & Faloutsos, C. (2013, May). Deltacon: A principled massive-graph similarity function. In Proceedings of the 2013 SIAM International Conference on Data Mining (pp. 162-170). Society for Industrial and Applied Mathematics.
  * [2] Papadimitriou, P., Dasdan, A., & Garcia-Molina, H. (2010). Web graph similarity for anomaly detection. Journal of Internet Services and Applications, 1(1), 19-30.
  * [3] Vishwanathan, S. V. N., Schraudolph, N. N., Kondor, R., & Borgwardt, K. M. (2010). Graph kernels. Journal of Machine Learning Research, 11(Apr), 1201-1242.
  * [4] Shervashidze, N., Schweitzer, P., Leeuwen, E. J. V., Mehlhorn, K., & Borgwardt, K. M. (2011). Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(Sep), 2539-2561.
  * [5] Fischer, A., Riesen, K., & Bunke, H. (2017). Improved quadratic time approximation of graph edit distance by combining Hausdorff matching and greedy assignment. Pattern Recognition Letters, 87, 55-62.
  * [6] A graph distance metric based on the maximal common subgraph, H. Bunke and K. Shearer, Pattern Recognition Letters, 1998  

Fize Jacques's avatar
Fize Jacques committed
64 65 66
## Author(s)

Jacques Fize, *jacques[dot]fize[at]cirad[dot]fr*
Fize Jacques's avatar
Fize Jacques committed
67

Fize Jacques's avatar
Fize Jacques committed
68 69
Some algorithms coming from other projects were integrated to Gmatch4py. **Be assured that
each code is associated with a reference to the original.**
Fize Jacques's avatar
Fize Jacques committed
70

Fize Jacques's avatar
Fize Jacques committed
71
## TODO List
Fize Jacques's avatar
Fize Jacques committed
72

Fize Jacques's avatar
Fize Jacques committed
73 74
  * Debug algorithms with --> (*debug needed*)
  * Improve code structure and performance
Fize Jacques's avatar
Fize Jacques committed
75
  * Simplify `setup.py` :heavy_check_mark:
Fize Jacques's avatar
Fize Jacques committed
76 77
  * Some algorithms are distance and others are similarity measure. Must change the compare
  methods so it can adapt to the user need. For example, maybe the user want to deal with 
Fize Jacques's avatar
Fize Jacques committed
78 79
  graph similarity rather than distance between graph.:heavy_check_mark:
  * Write the documentation :see_no_evil: