PaperlayerView exact revision on arXiv

Source-linked AI summary

GraKeL: A Graph Kernel Library in Python

Giannis Siglidis, Giannis Nikolentzos, Stratis Limnios, Christos Giatsidis, Konstantinos Skianis, Michalis Vazirgiannis

arXiv:1806.02193v2stat.MLcs.LG

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.

    Source: §1 · p. 1

  • Method

    GraKeL unifies several graph kernels in a Python package using a common scikit-learn-compatible framework.

    Source: §1 · p. 2, §3 · p. 3

  • 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.

    Source: §4 · p. 3

  • 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.

    Source: §4 · p. 3, §6 · p. 4

    Some kernels cannot handle vector attributes, while others assume unlabeled graphs.

    Source: §3 · p. 3

Abstract

from arXiv · show

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.Source: §1 · p. 1
  • Measuring graph similarity or distance is a key component of many machine learning algorithms involving graphs.Source: §1 · p. 1
  • Graph kernels are functions corresponding to inner products in a Hilbert space and act as similarity measures defined directly on graphs.Source: §1 · p. 1
  • Graph kernels allow kernel methods to be applied directly to graphs.Source: §1 · p. 1
  • GraKeL implements several graph kernels in a common, scikit-learn-compatible framework.Source: §1 · p. 2

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.Source: §2 · p. 2
  • SciPy provides scientific-computing modules and support for sparse matrix representations and operations.Source: §2 · p. 2
  • Cython addresses efficiency issues in interpreted Python code and integrates low-level implementations.Source: §2 · p. 2
  • scikit-learn provides GraKeL’s development template and interoperability for machine-learning tasks on graphs.Source: §2 · p. 2

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.Source: §3 · p. 2
  • The fit method extracts kernel-dependent features from an input graph collection.Source: §3 · p. 2
  • fit_transform computes a kernel matrix for an input collection, while transform computes a matrix between new and fitted graph collections.Source: §3 · p. 2
  • diagonal returns self-kernel values for fitted and transformed graphs and supports kernel-matrix normalization.Source: §3 · pp. 2–3
  • GraphKernel provides a unified interface and supports operations such as the Nyström method and frameworks including Weisfeiler Lehman.Source: §3 · p. 3
  • Inputs are iterable graph collections whose representations may include adjacency matrices, edge dictionaries, vertex attributes, and edge attributes.Source: §3 · p. 3

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.Source: §4 · p. 3
  • GraKeL provides implementations of 15 kernels and 2 kernel frameworks, compared with graphkernels’ 5 kernels and 1 framework.Source: §4 · p. 3
  • GraKeL is compatible with scikit-learn pipelines, enabling integration into machine-learning algorithms and a common ground for kernel comparisons.Source: §4 · p. 3
  • GraKeL includes detailed documentation and examples for applying graph kernels to real-world data.Source: §4 · p. 3
  • On the ENZYMES dataset, several Python-based GraKeL kernels are reported as more efficient than corresponding graphkernels implementations.Source: §4 · pp. 3–4, Figure 1 · p. 4

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.Source: §5 · p. 4
  • 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.Source: §5 · p. 4

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.Source: §5 · p. 4

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.Source: §6 · p. 4
  • The library is designed to remain user-friendly.Source: §6 · p. 4

Integration

  • GraKeL can be easily integrated into machine-learning applications through the scikit-learn pipeline.Source: §6 · p. 4

Related papers

Loading 1806.02193v2…