Source-linked AI summary
GraKeL: A Graph Kernel Library in Python
Giannis Siglidis, Giannis Nikolentzos, Stratis Limnios, Christos Giatsidis, Konstantinos Skianis, Michalis Vazirgiannis
TL;DR
Measuring similarity between graphs is important for machine-learning applications, but graph kernels address different structural aspects through diverse implementations. GraKeL unifies several kernels in a Python library with a scikit-learn interface, and the paper reports broader coverage and greater efficiency for several kernels than graphkernels on ENZYMES.
Problem
Measuring graph similarity is central to many applications, while graph kernels address different structural aspects through diverse kernels.
Method
GraKeL unifies several graph kernels in a Python package using a common scikit-learn-compatible framework.
Results
GraKeL provides 15 kernels and 2 kernel frameworks, while graphkernels provides 5 kernels and 1 framework; several GraKeL kernels are more efficient on ENZYMES.
Takeaways & Limitations
GraKeL can be integrated into machine-learning pipelines for graph tasks and provides a common ground for comparing existing and newly designed kernels.
Takeaways & Limitations
Some kernels cannot handle vector attributes, while others assume unlabeled graphs.
Abstract
from arXiv · showhide
The problem of accurately measuring the similarity between graphs is at the core of many applications in a variety of disciplines. Graph kernels have recently emerged as a promising approach to this problem. There are now many kernels, each focusing on different structural aspects of graphs. Here, we present GraKeL, a library that unifies several graph kernels into a common framework. The library is written in Python and adheres to the scikit-learn interface. It is simple to use and can be naturally combined with scikit-learn's modules to build a complete machine learning pipeline for tasks such as graph classification and clustering. The code is BSD licensed and is available at: https://github.com/ysig/GraKeL .
1. Introduction
Graph-structured data is growing across domains, creating a need to measure graph similarity for machine learning. Graph kernels address this need by representing graph similarity as Hilbert-space inner products, allowing kernel methods to operate directly on graphs.
- Graph-structured data is increasingly used in domains including social networks and bioinformatics.
- Measuring graph similarity or distance is a key component of many machine learning algorithms involving graphs.
- Graph kernels are functions corresponding to inner products in a Hilbert space and act as similarity measures defined directly on graphs.
- Graph kernels allow kernel methods to be applied directly to graphs.
- GraKeL implements several graph kernels in a common, scikit-learn-compatible framework.
2. Underlying Technologies
GraKeL is built within the Python scientific-computing ecosystem, using NumPy, SciPy, Cython, and scikit-learn to support graph representation, sparse operations, efficiency, and machine-learning interoperability.
- NumPy supplies graph data structures and linear-algebra operations used for kernel calculation.
- SciPy provides scientific-computing modules and support for sparse matrix representations and operations.
- Cython addresses efficiency issues in interpreted Python code and integrates low-level implementations.
- scikit-learn provides GraKeL’s development template and interoperability for machine-learning tasks on graphs.
3. Code Design
GraKeL standardizes graph-kernel operation through scikit-learn-style classes and methods. Its interface accepts varied graph representations and attributes, while supporting kernel composition and common graph-kernel frameworks.
- Code Design: Every GraKeL kernel inherits from Kernel, which derives from scikit-learn’s TransformerMixin.
- Code Design: The fit method extracts kernel-dependent features from an input graph collection.
- Code Design: fit_transform computes a kernel matrix for an input collection, while transform computes a matrix between new and fitted graph collections.
- Code Design: diagonal returns self-kernel values for fitted and transformed graphs and supports kernel-matrix normalization.
- Code Design: GraphKernel provides a unified interface and supports operations such as the Nyström method and frameworks including Weisfeiler Lehman.
- Code Design: Inputs are iterable graph collections whose representations may include adjacency matrices, edge dictionaries, vertex attributes, and edge attributes.
4. Comparison to Other Software
GraKeL addresses limitations in earlier graph-kernel software through object-oriented design, broader kernel and framework coverage, scikit-learn integration, and documentation. On the ENZYMES benchmark, several GraKeL kernels are reported as more efficient than corresponding graphkernels implementations.
- Comparison to Other Software: Earlier graph-kernel collections lacked a shared structure for usability, while GraKeL uses object-oriented design to support kernel integration.
- Comparison to Other Software: GraKeL provides implementations of 15 kernels and 2 kernel frameworks, compared with graphkernels’ 5 kernels and 1 framework.
- Comparison to Other Software: GraKeL is compatible with scikit-learn pipelines, enabling integration into machine-learning algorithms and a common ground for kernel comparisons.
- Comparison to Other Software: GraKeL includes detailed documentation and examples for applying graph kernels to real-world data.
- Comparison to Other Software: On the ENZYMES dataset, several Python-based GraKeL kernels are reported as more efficient than corresponding graphkernels implementations.
5. Sample Code
GraKeL computes separate training and test kernel matrices with fit_transform and transform, then passes them to an SVM for graph classification. The example reports 84.21% accuracy.
- Kernel workflow: fit_transform computes the n × n training kernel matrix, while transform computes the m × n test-to-training matrix.These matrices are then supplied to an SVM classifier for graph classification.
- Kernel workflow: The sample initializes a ShortestPath kernel, splits MUTAG into training and test sets, and applies the two matrix transformations.The workflow uses a precomputed-kernel SVC and preserves the corresponding labels for training and evaluation.
- Reported result: 84.21% accuracy is reported for the MUTAG graph-classification example.The value is produced by comparing SVM predictions with the held-out test labels.
6. Conclusion
GraKeL implements several state-of-the-art graph kernels in a user-friendly library. Its scikit-learn pipeline integration supports use within machine-learning applications.
- Contribution: GraKeL implements several state-of-the-art graph kernels.
- Contribution: The library is designed to remain user-friendly.
- Integration: GraKeL can be easily integrated into machine-learning applications through the scikit-learn pipeline.