Installing GraKeL

The GraKeL library requires the following packages to be installed:

  • Python (>=2.7, >=3.5)

  • NumPy (>=1.8.2)

  • SciPy (>=0.13.3)

  • Cython (>=0.27.3)

  • cvxopt (>=1.2.0) [optional]

  • future (>=0.16.0) (for python 2.7)

GraKeL is available via PyPI . You can install the latest release of GraKeL using the following command:

$ pip install grakel

To also install the cvxopt package, which is a requirement of the Lovász-\(\vartheta\) kernel, you can use the following command:

$ pip install grakel[lovasz]

Building GraKeL

In order to build your own version of GraKeL, you need a C++ compiler since the package contains some C++ extensions. To build and install a local version of GraKeL, you need to execute pip install . or python setup.py install on the root folder. Furthermore, in case you want to build the extensions locally, execute python setup.py build_ext.

In order for the C++ extensions to compile our extensions, a system-specific build environment should be configured. What you generally need is a C++ compiler and some python header files.

Unix Environment

In the case of Unix environments, you need to have installed:

  • A C++ compiler like g++

  • The package that contains the Python.h file such as python-dev

Windows Environment

In the case of a Windows environment, you need to install parts of the Windows Virtual Studio SDK (for C++) (for more details, please have a look here).

Note

If you have trouble building GraKeL, please raise an issue so that we can enrich our installation instructions, as well as addressing the problem.

Why so Many Packages?

Graph kernels deal with the problem of graph comparison, a very challenging problem which has been studied for decades. Due to the complex nature of the problem, different types of approaches have been developed so far. Some approaches employ combinatorial algorithms, others formulate the graph comparison algorithm as a continuous optimization problem, while there are also other approaches that apply heuristics. The field of graph kernels is also characterized by such a large diversity of methods. For instance, the graphlet kernel solves the graph isomorphism problem to determine the identity of each graphet, while the Lovász-\(\vartheta\) kernel solves a semidefinite programming problem to compute the Lovász number of each graph and the associated orthonormal representations. To solve such problems, GraKeL relies on well-established external libraries that provide optimized software that has been developed to address these problems. For example, GraKeL uses [bliss] to test graph isomorphism and the cvxopt library to optimize semidefinite programs.

bliss

To test graph isomorphism, GraKeL extended PyBliss, a Python wrapper for bliss. This allowed GraKeL to remain compatible with Python 2/3 and its installation on Windows. Among all the candidate packages, PyBliss was chosen thanks to the information shared by Tamás Nepusz (developer of the iGraph library), who pointed out that this package was the most efficient (both in terms of time and memory) for deciding isomorphism between small graphs in experiments conducted using the iGraph library. Other candidate packages include pynauty (a Python extension of nauty) and networkx (contains an implementation of the VF2 algorithm).