PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Kernels: A Survey

Giannis Nikolentzos, Giannis Siglidis, Michalis Vazirgiannis

arXiv:1904.12218v2stat.MLcs.LG

TL;DR

Learning on graphs requires meaningful similarity measures, yet graph algorithms can be computationally expensive and difficult to scale. This survey reviews graph kernels and evaluates them experimentally, reporting that their performance exceeds that of graph neural networks for certain graph types.

  • Problem

    Learning on graphs depends on meaningful similarity measures, while graph algorithms can be computationally expensive and difficult to scale.

    Source: §2.2 · pp. 5–6

  • Method

    The paper surveys foundational and recent graph kernels, experimentally evaluates many of them, and discusses applications and remaining challenges.

    Source: §1 · p. 3

  • Results

    Graph kernels have superior empirical performance to graph neural networks for certain types of graphs.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Graph kernels are powerful tools with a wide range of applications.

    Source: §1 · p. 3

    Complete graph kernels are at least as hard to compute as deciding graph isomorphism, while incomplete kernels may map non-isomorphic graphs identically.

    Source: §4.3 · p. 12

Abstract

from arXiv · show

Graph kernels have attracted a lot of attention during the last decade, and have evolved into a rapidly developing branch of learning on structured data. During the past 20 years, the considerable research activity that occurred in the field resulted in the development of dozens of graph kernels, each focusing on specific structural properties of graphs. Graph kernels have proven successful in a wide range of domains, ranging from social networks to bioinformatics. The goal of this survey is to provide a unifying view of the literature on graph kernels. In particular, we present a comprehensive overview of a wide range of graph kernels. Furthermore, we perform an experimental evaluation of several of those kernels on publicly available datasets, and provide a comparative study. Finally, we discuss key applications of graph kernels, and outline some challenges that remain to be addressed.

1. Introduction

Graph kernels provide similarity measures that let kernel-based machine-learning methods operate directly on graphs. This survey reviews their foundations and methods, evaluates them empirically, and discusses applications and open challenges.

1. Introduction

  • Graph-based machine learning can support costly or data-intensive tasks, including protein-function prediction and malware detection using function-call graphs.The paper frames these as graph-classification problems, comparing new proteins or code samples with known examples (Borgwardt et al., 2005; Anderson et al., 2011).Source: §1 · p. 2
  • A graph kernel is a symmetric, positive semidefinite similarity function expressible as an inner product in a Hilbert space, enabling kernel methods to work directly on graphs.Graph kernels seek to capture graph semantics while remaining computationally efficient.Source: §1 · p. 2
  • The survey evaluates classification performance and running times, compares kernels with graph neural networks, and empirically examines kernel expressiveness against an intractable graph-similarity function.The authors note that GNNs and many graph kernels share neighborhood-aggregation ideas, while GNN complexity is linear in sample count and computing all kernel values takes quadratic time.Source: §1 · p. 4
  • The manuscript proceeds from graph-learning challenges and background to kernel methods, GNNs, applications, benchmark experiments, practical guidelines, expressiveness analysis, and future directions.Its kernel overview distinguishes early methods, neighborhood-aggregation and other kernels, assignment methods, continuous-node-attribute methods, and performance-improving frameworks.Source: §1 · p. 4

2. Motivation and Challenges

Graphs offer a flexible way to represent data, but their combinatorial structure makes learning directly on them challenging. This section motivates graph representations and frames graph-level learning in relation to graph comparison.

2.1 Why Graphs

  • Graphs capture entities and their relationships while accommodating objects with different numbers of vertices and edges, unlike fixed-length vectors that cannot represent such relationships.These properties address limitations of vector representations and motivate methods for learning on graphs.Source: §2.1 · p. 5

2.2 Learning on Graphs and Challenges

  • The survey focuses on graph-level learning tasks, such as graph classification, and therefore considers kernels that are functions between graphs.Graph-level tasks are distinguished from node-level tasks such as node classification.Source: §2.2 · p. 5
  • Direct graph algorithms may be computationally expensive and difficult to scale, while converting graphs to vectors in polynomial time without losing representational power is not possible.Vectors are efficient to process but can discard the rich topological information encoded in graphs.Source: §2.2 · pp. 5–6
  • Graph comparison lacks vector spaces’ convenient mathematical structure and efficient universal distance metric; graph isomorphism has no discovered polynomial-time algorithm, and related problems can be NP-complete.Finding common parts can require considering exponentially many pairs of vertex subsets.Source: §2.2 · p. 6

3. Preliminaries

The preliminaries establish graph notation and structural concepts, then introduce positive semidefinite kernels and the feature-space view underlying kernel methods.

3.1 Definitions and Notations

  • A graph G=(V,E) has n=|V| vertices and m=|E| edges; labels assign discrete symbols, while attributed graphs assign real-valued vectors to vertices and edges.Graphs may be node-labeled, edge-labeled, or fully labeled; discrete labels can be represented as one-hot vectors, a special case of attributes.Source: §3.1 · p. 7
  • Graphs can be represented by adjacency and Laplacian matrices, each with n×n dimensions.Source: §3.1 · pp. 7–8
  • An induced subgraph retains a selected vertex set and the edges between its members; density 1 defines a complete graph, and a clique induces a complete subgraph.Source: §3.1 · p. 8
  • Walks, paths, cycles, and shortest paths characterize routes through a graph, while a radius-r neighborhood contains vertices within shortest-path distance r.Source: §3.1 · pp. 8–9

3.2 Kernel Functions and Kernel Methods

  • A kernel is a function whose Gram matrix is positive semidefinite for every finite input set, with entries defined by k(x_i,x_j).Source: §3.2 · p. 9
  • Kernel values measure object similarity and can be represented as inner products in a Hilbert space, whose associated space is a reproducing kernel Hilbert space.Source: §3.2 · pp. 9–10
  • Kernel methods use implicit feature-space inner products to learn on structured domains such as graphs, without requiring an explicit feature map.For methods such as Support Vector Machines, the optimization problem is convex only when the employed function is positive semidefinite.Source: §3.2 · p. 10

4. Graph Kernels · 4.1 Kernels between Graphs

This section surveys representative, though not exhaustive, graph-kernel approaches, focusing on kernels between graphs and the challenge of defining positive semidefinite functions that reliably measure graph similarity.

4. Graph Kernels

  • The survey aims to provide an overview of representative graph-kernel approaches rather than an exhaustive account.It first presents fundamentals, then discusses details of several kernel instances.Source: §4 · p. 10

4.1 Kernels between Graphs

  • Graph kernels compare graphs rather than nodes; this survey uses the term exclusively for graph-to-graph kernels.Kernels that compare nodes are outside the survey’s focus.Source: §4.1 · p. 10
  • A graph kernel maps graphs into a feature space, where it can be represented as an inner product.The mapping may be implicit or explicit.Source: Figure 2 · p. 11, §4.1 · p. 11
  • Graph kernels combine graphs’ representative power with kernel methods’ discrimination, supporting graph similarity and learning tasks together.The survey describes them as a promising approach for learning on graph-structured data.Source: §4.1 · pp. 10–11
  • Because mature kernel-based classifiers are available, graph-kernel research has focused on designing expressive, efficient functions to measure input-graph similarity.The workflow constructs a kernel matrix from a kernel function, then applies a learning algorithm such as Support Vector Machines or kernel k-means.Source: §4.1 · p. 11
  • The central challenge is defining positive semidefinite kernels on input graphs that reliably assess similarity between them.The section next illustrates this challenge with simple kernels comparing node and edge labels.Source: §4.1 · p. 11
  • The section introduces two simple illustrative kernels that compare node and edge labels across graphs.These examples follow the discussion of defining kernels that reliably assess graph similarity.Source: §4.1 · p. 11

4.2 Simple Kernels

These simple kernels generate explicit graph representations from vertex- or edge-label histograms.

4.2.1 Vertex Histogram Kernel

  • The vertex histogram kernel applies a linear kernel to node-label count vectors and has complexity linear in graph vertices.Source: §4.2.1 · p. 12

4.2.2 Edge Histogram Kernel

  • The edge histogram kernel applies a linear kernel to edge-label count vectors and has complexity linear in graph edges.Source: §4.2.2 · p. 12

4.3 Expressiveness vs Efficiency

Complete graph kernels distinguish all non-isomorphic graphs, but their computational hardness limits practical use. Less complete kernels trade expressiveness for efficiency, complicating kernel choice.

4.3 Expressiveness vs Efficiency

  • A graph kernel is complete when its feature map is injective, allowing it to distinguish all non-isomorphic graphs.Completeness is defined by injectivity of the feature map.Source: §4.3 · p. 12
  • Gärtner et al. (2003) showed that computing any complete graph kernel is at least as hard as deciding graph isomorphism, limiting practical use.With incomplete kernels, non-isomorphic graphs may map to the same feature-space point, so expressiveness must be balanced against efficiency.Source: §4.3 · p. 12
  • Kriege et al. (2018) showed that the Weisfeiler-Lehman subtree kernel cannot distinguish connectivity, planarity, or bipartiteness, despite state-of-the-art benchmark results.This limitation further complicates choosing a kernel for a particular application.Source: §4.3 · p. 12

4.4 Taxonomy of Graph Kernels

Graph kernels can be classified by structural focus, graph-label support, computation scheme, or design paradigm, and the categories may overlap. The survey organizes its coverage from early random-walk kernels through later approaches and summarizes selected kernels’ properties in Table 2.

4.4 Taxonomy of Graph Kernels

  • Graph kernels can be grouped by structural focus, support for unlabeled or labeled/attributed graphs, explicit or implicit computation, and design paradigm, with categories that may overlap.For example, kernels handling node-attributed graphs usually employ implicit computation schemes; Figure 3 illustrates the survey’s taxonomy.Source: §4.4 · p. 13
  • The survey proceeds from early random-walk approaches to the Weisfeiler-Lehman subtree kernel, related neighborhood-aggregation kernels, other kernel families, assignment kernels, kernels for continuous node attributes, and frameworks applied atop existing kernels.Table 2 summarizes selected kernels’ explicit feature mapping, support for node-labeled and node-attributed graphs, type, and worst-case evaluation complexity.Source: §4.4 · p. 14, Table 2 · p. 14

4.5 Early Days of Graph Kernels

Most graph kernels decompose graphs into substructures and aggregate pairwise similarities; early designs balanced expressive graph comparison against computational tractability, motivating kernels based on walks, subtrees, cycles, paths, graphlets, and relabeling.

4.5 Early Days of Graph Kernels

  • Most graph kernels are R-convolution kernels, summing pairwise similarities over decomposed substructures; comparing all subgraphs is NP-hard, motivating polynomial-time kernels that retain expressive graph similarity.Source: §4.5 · p. 15

4.5.1 Random Walk Kernel

  • Random-walk kernels compare common walks; geometric variants weight length-k walks by λ^k and converge only under an eigenvalue bound, while efficient methods reduce direct O(n^6) computation to O(n^3).Mahé et al. (2004) enriched labels and addressed tottering; Sugiyama and Borgwardt (2015) addressed halting.Source: §4.5.1 · pp. 15–16

4.5.2 Subtree Kernel

  • Ramon and Gärtner (2003) introduced subtree kernels that count shared rooted patterns, distinguishing some non-isomorphic graphs missed by walk kernels, at higher computational cost.The kernel iteratively compares vertex neighborhoods; its runtime can be lower in practice on sparse graphs or when vertex labels are diverse.Source: §4.5.2 · p. 17

4.5.3 Cyclic Pattern Kernel

  • The cyclic-pattern kernel (Horváth et al., 2004) compares canonical cycle and bridge-tree patterns, but is NP-hard and can be useful when input graphs have bounded cycle counts.Source: §4.5.3 · p. 18

4.5.4 Shortest-Path Kernel

  • Shortest-path kernels (Borgwardt and Kriegel, 2005) compare shortest paths by length and endpoint labels; shortest paths are polynomial-time computable, unlike all or longest paths, and runtime is O(n^4).Source: §4.5.4 · pp. 18–19

4.5.5 Graphlet Kernel

  • Graphlet kernels count distributions of small k-vertex subgraphs (k=3, 4, 5), enabling scalable handling of very large graphs via sampling, though theory does not establish graphlets as superior similarity features.Source: §4.5.5 · p. 20

4.5.6 Weisfeiler-Lehman Subtree Kernel

  • The Weisfeiler–Lehman subtree kernel scales labeled-graph comparison through iterative neighborhood relabeling, counting shared subtrees up to height h in O(hm) time.It was motivated by the need for a fast subtree kernel for large, labeled graphs and is described as state-of-the-art in graph classification.Source: §4.5.6 · pp. 20–23

4.6 Neighborhood Aggregation Approaches

Neighborhood aggregation extends Weisfeiler-Lehman-style label updates by incorporating messages from neighboring vertices. The section develops neighborhood hash methods that encode neighborhood-label distributions and compare graphs.

4.6 Neighborhood Aggregation Approaches

  • Following the Weisfeiler-Lehman subtree kernel, variants mainly sought faster computation, while others introduced streaming, k-dimensional tests, or topological features.The Weisfeiler-Lehman relabeling procedure can be viewed as neighborhood aggregation, in which vertices receive messages from neighbors to update their representations.Source: §4.6 · p. 23

4.6.1 Neighborhood Hash Kernel

  • The neighborhood hash kernel updates labels on node-labeled graphs using fixed-length binary arrays and logical operations to encode neighborhood structure.XOR and bit rotation (ROT) combine neighbor labels; the simple hash is order-independent, so label distributions can be compared without sorting or matching.Source: §4.6.1 · pp. 23–24
  • Count-sensitive hashing addresses problematic collisions by sorting neighbor labels, counting each label’s occurrences, and incorporating those counts into the update.The simple procedure can assign identical hashes to independent nodes, potentially affecting kernel positive semidefiniteness.Source: §4.6.1 · pp. 24–25
  • The kernel compares updated graph labels with a positive-semidefinite Tanimoto coefficient and can iterate updates to capture higher-order neighborhood relationships.After h updates, a vertex label represents the label distribution of its h-neighbors; computational complexity is O(deg nhd), where n is the number of vertices and deg the average degree.Source: §4.6.1 · pp. 25–26

4.7 Other Approaches

This section surveys R-convolution kernels that avoid neighborhood aggregation, detailing pairwise rooted-neighborhood comparisons, Lovász-representation kernels, and DAG-based decomposition.

4.7.1 Neighborhood Subgraph Pairwise Distance Kernel

  • The neighborhood subgraph pairwise distance kernel compares graphs by counting matching pairs of radius-r rooted neighborhoods whose roots are distance d apart, using graph-invariant encodings instead of direct isomorphism tests (Costa & De Grave, 2010).Its invariant relabels vertices using labels and distances, then hashes the resulting rooted-subgraph encoding; with small maximum radius and root distance, its complexity is linear in graph size in practice.Source: §4.7.1 · pp. 26–27

4.7.2 Lov´asz ϑ Kernel

  • The Lovász ϑ kernel compares unlabeled graphs using vertex-subset Lovász values derived from orthonormal representations, but exact evaluation over all 2^n subsets is generally infeasible, requiring sampling.The Lovász number itself can be computed to arbitrary precision in polynomial time by solving a semidefinite program.Source: §4.7.2 · p. 28

4.7.3 SVM-ϑ Kernel

  • For certain graph families such as Erdős–Rényi random graphs, ω(KLS) is with high probability a constant-factor approximation to ϑ(G); SVM-ϑ is a more efficient unlabeled-graph alternative (Jethava et al., 2013; Johansson et al., 2014).It constructs KLS, solves a one-class SVM, and samples vertex subsets; its stated complexity is O(n^3 + s^2T(k) + sn).Source: §4.7.3 · pp. 29–30

4.7.4 Ordered Decomposition DAGs Kernel

  • The ordered decomposition DAGs kernel handles node-labeled graphs by decomposing each graph into rooted shortest-path DAGs, ordering DAG vertices, and applying ordered-tree kernels to tree visits (Da San Martino et al., 2012).Using subtree and subset tree kernels gives time complexities O(n^3 log n) and O(n^4), respectively; caching computations for unique subtree pairs and limiting visit depth can reduce computation.Source: §4.7.4 · pp. 30–31

4.8 Assignment Kernels

Assignment kernels maximize matches between substructures of two objects to reveal structural correspondences, but ensuring that these kernels are valid is not trivial.

4.8 Assignment Kernels

  • Assignment kernels maximize substructure correspondences, but some optimal assignment kernels are not positive semidefinite; strong base kernels can guarantee validity.The survey contrasts an early molecular-atom assignment kernel later shown not always positive semidefinite with valid approaches based on strong base kernels.Source: §4.8 · p. 32

4.8.1 Pyramid Match Graph Kernel

  • Pyramid Match Graph Kernel approximates vertex correspondences by spectrally embedding nodes and comparing multiresolution histograms, with finer-cell matches weighted more.Its complexity is O(dnL); for labeled graphs, it sums separate kernels for vertices sharing each label.Source: §4.8.1 · pp. 32–33

4.8.2 Weisfeiler-Lehman Optimal Assignment Kernel

  • The Weisfeiler-Lehman optimal assignment kernel uses a strong base kernel derived from nested Weisfeiler-Lehman refinement labels to ensure a valid assignment kernel.Strong kernels correspond to hierarchy-induced kernels, and the assignment computation can use histogram intersection in time linear in the hierarchy-tree size.Source: §4.8.2 · pp. 34–36

4.9 Kernels for Graphs with Continuous Attributes

This section surveys kernels for graphs with continuous node attributes, covering approaches that handle attributes directly or discretize them for existing kernels. It also describes a multiscale Laplacian graph kernel that uses sampled and truncated feature spaces to make kernel-stack computation feasible.

4.9.1 Subgraph Matching Kernel

  • The subgraph matching kernel counts bounded-size subgraph matchings using vertex and edge kernels, accommodating node and edge labels or attributes.Its worst-case runtime for subgraphs of size up to k is O(kn^k+1), where n is the total number of vertices in the two graphs.Source: §4.9.1 · pp. 37–38

4.9.2 GraphHopper Kernel

  • GraphHopper compares shortest paths by summing node-kernel similarities at matching hops, handling attributes more efficiently than the O(n4) attributed shortest-path kernel.It compares paths only when their discrete lengths match, and the node kernel can compare continuous attributes.Source: §4.9.2 · pp. 38–39

4.9.3 Graph Invariant Kernels

  • Graph invariant kernels weight vertex-attribute similarities by matching structural roles in decomposed patterns, using invariants such as Weisfeiler-Lehman relabeling.Decompositions can use neighborhood subgraphs, and different graph invariants yield different kernel instances.Source: §4.9.3 · pp. 39–40

4.9.4 Propagation Kernel

  • The propagation kernel hashes continuous attributes into bins, iteratively updates node attributes, and compares graphs by counts of nodes occupying the same bins.Its procedure quantizes attributes to discrete labels before neighborhood-based propagation and counting.Source: §4.9.4 · pp. 40–41

4.9.5 Multiscale Laplacian Graph Kernel

  • The multiscale Laplacian kernel compares nested-subgraph hierarchies via feature-space Laplacian kernels and randomized projection, but exact dataset computation costs O(N2n5lmax).Local permutation-invariant vertex features make the feature-space kernel permutation invariant and applicable to graphs of different sizes.Source: §4.9.5 · pp. 41–44
  • The kernel approximates the joint feature space by sampling ˜c ≪ c vertices, since full vertex-kernel storage, eigendecomposition, and p × p matrices are infeasible.It constructs an orthonormal basis for the sampled feature space from the smaller kernel matrix.Source: §4.9.5 · p. 44
  • Restricting the sampled space to its first ˆp < ˜p eigenvectors applies kernel PCA and reduces dataset kernel-matrix complexity to O(N˜c2ˆp3lmax + N˜c3lmax + N2ˆp3).The basis vectors are ordered by descending eigenvalue; together, sampling and truncation make computing the kernel stack feasible.Source: §4.9.5 · p. 45

4.10 Frameworks

Graph-kernel frameworks adapt existing kernels to capture structural relationships, combine kernels, or compare graphs through hierarchical subgraphs. The section explains two approaches to diagonal dominance and a core-based framework for graph comparison.

4.10 Frameworks

  • The Weisfeiler-Lehman framework accepts any kernel that handles discrete node labels; other approaches use substructure similarity, multiple-kernel learning, hierarchical subgraphs, or successive embeddings.The survey also describes NLP-inspired variants of popular R-convolution kernels and kernel combinations using multiple-kernel learning.Source: §4.10 · p. 45

4.10.1 Frameworks Dealing with Diagonal Dominance

  • Exact-match R-convolution kernels can yield zero similarity between graphs with related but nonidentical substructures, causing diagonal dominance in sparse, exponentially large feature spaces.The deep graph kernels framework uses a positive semidefinite matrix M to encode substructure relationships in explicit feature representations; it can also learn substructure embeddings using CBOW or Skip-gram after defining meaningful co-occurrences.Source: §4.10.1 · pp. 45–46
  • Structural smoothing propagates probability mass through a DAG of parent and child substructures, so an absent substructure can receive a positive feature value.The DAG relates lower- and higher-order substructures, and the framework applies to kernels with explicitly computable feature maps.Source: §4.10.1 · pp. 46–47

4.10.2 Core Framework

  • The core framework (Nikolentzos et al., 2018) compares graphs by summing a base kernel over corresponding nested k-core subgraphs, capturing structure through progressively more connected subgraphs.A k-core is a maximal subgraph whose vertices each have degree at least k; the decomposition can be computed in O(n + m) time.Source: §4.10.2 · pp. 47–48

4.11 Tree Kernels

Tree kernels compare structured trees through shared substructures and have been used mainly in natural language processing as an alternative to costly handcrafted features. They are specialized graph kernels, and both graph and tree kernels share limitations in feature selection and learning.

Tree Kernels

  • Tree kernels are graph-kernel instances designed for trees, but tree kernels cannot be directly applied to general graphs.Any graph kernel can be applied to trees, while some graph kernels, such as the subtree kernel, build on tree-kernel ideas.Source: §4.11 · p. 48
  • Tree kernels operate on structured text representations such as dependency parse trees, avoiding expensive, time-consuming handcrafted feature design across tasks including semantic role labeling, relation extraction, parsing re-ranking, and question classification.They have been applied to capture syntactic and semantic aspects of text without requiring domain experts to design new features.Source: §4.11 · p. 48
  • Common tree-kernel families count shared subtrees, subset trees, or partial trees, yielding subtree, subset tree, and partial tree kernels.Subtrees include all descendants of a non-leaf root; subset trees allow leaves at non-leaf input vertices while preserving grammatical rules, whereas partial trees relax that constraint through partial production rules.Source: §4.11 · pp. 48–49
  • Graph and tree kernels fix feature sets in advance, decoupling data representation from learning, and there is no justification for why some tree kernels outperform others on a given task (Moschitti, 2006a, 2006b).Source: §4.11 · p. 49

5. Link to Graph Neural Networks

Graph neural networks address graph kernels’ fixed feature schemes and difficulty with continuous node attributes, while message-passing models connect GNNs to the Weisfeiler-Lehman framework. The section describes several GNN variants and approaches combining kernels with neural networks.

5.1 Message Passing Models and the Weisfeiler-Lehman Test of Isomorphism

  • MPNNs update node features by aggregating neighbors, then use a permutation-invariant graph readout; their aggregation and combination steps parallel Weisfeiler-Lehman relabeling, with standard models no more powerful than its test.Differentiable aggregation and combination functions support end-to-end training; injective aggregation, combination, and readout functions attain the test’s distinguishing power.Source: §5 · p. 49, §5.1 · p. 50

5. Link to Graph Neural Networks

  • GNNs address graph kernels’ fixed, data-independent feature schemes and difficulty efficiently handling continuous multidimensional node attributes, which limits their use in bioinformatics and chemoinformatics.Graph kernels can be effective on unlabeled and node-labeled graphs with thousands of nodes, but the same efficiency does not hold for graphs with continuous node attributes.Source: §5 · pp. 49–50

5.1.1 Deep Graph Convolutional Neural Network

  • DGCNN aggregates local neighborhood information across layers, concatenates layer outputs, and uses SortPooling to order vertices and standardize graph sizes before a conventional CNN.SortPooling ranks vertices by representation components and truncates or extends the output to a fixed size.Source: §5.1.1 · p. 51

5.1.2 GraphSAGE

  • GraphSAGE supports large graphs by uniformly sampling a fixed-size neighbor set at each iteration and aggregating with mean, LSTM, or pooling functions.The LSTM aggregator is not permutation invariant.Source: §5.1.2 · pp. 51–52

5.1.3 Differentiable Graph Pooling

  • DiffPool hierarchically coarsens graphs using learned soft assignments informed by topology and features, ultimately assigning all final-layer vertices to one cluster for a graph embedding.Separate message-passing networks generate vertex embeddings and probabilistic cluster assignments.Source: §5.1.3 · p. 52

5.1.4 Graph Isomorphism Network

  • GIN uses sum aggregation to model injective multiset functions and has the same graph-distinguishing power as the Weisfeiler-Lehman test.Its readout also uses sum aggregation.Source: §5.1.4 · p. 53

5.2 Other Models

  • Other approaches connect kernels and neural networks by learning kernel-space GNN states (Lei et al., 2017), approximating local-pattern kernels (Chen et al., 2020), or pretraining networks with kernel features (Navarin et al., 2018; Nikolentzos et al., 2018).Du et al. (2019) proposed a kernel corresponding to infinitely wide GNNs trained by gradient descent; Al-Rfou et al. (2019) learned graph representations by comparing graphs with source graphs, and Nikolentzos and Vazirgiannis (2020) used random-walk-kernel comparisons to latent graphs as neural-network inputs.Source: §5.2 · pp. 53–54

6. Applications of Graph Kernels

Graph kernels have been applied across chemoinformatics, bioinformatics, computer vision, cybersecurity, natural language processing, and other domains. These applications address tasks ranging from predicting molecular and biological properties to recognizing images and analyzing text.

6.1 Chemoinformatics

  • Graph kernels predict molecular toxicity and activity, as well as atomization energy, boiling points, HIV activity, and stereoisomer properties.Applications include mutagenicity, toxicity, and anti-cancer activity (Swamidass et al., 2005; Ralaivola et al., 2005; Mahé et al., 2005; Ceroni et al., 2007; Mahé & Vert, 2009; Smalter et al., 2009), atomization energies (Ferré et al., 2017), boiling points and HIV activity (Gaüzère et al., 2011), and stereoisomer properties.Source: §6.1 · p. 54

6.2 Bioinformatics

  • Graph kernels use protein and gene-related graphs for protein-function prediction, disease-interaction analysis, RNA analysis, gene-relationship localization, and domain-peptide prediction.Applications include prediction of protein function (Borgwardt et al., 2005; Schietgat et al., 2015), disease interactions (Borgwardt et al., 2007), functional non-coding RNA analysis, temporally localized gene relationships, and domain-peptide interactions.Source: §6.2 · pp. 54–55

6.3 Computer Vision

  • In computer vision and biomedical imaging, graph kernels support image, object, place, and action recognition, brain-state classification, and prediction of addiction and mild cognitive impairment.The vision applications include image classification, point-cloud object detection (Bach, 2008), place recognition, action recognition, scene modeling, and person matching across cameras. fMRI applications include brain-state classification, cocaine-addiction classification, mild cognitive impairment prediction (Jie et al., 2014, 2016), and handling inter-subject variability.Source: §6.3 · p. 55

6.4 Cybersecurity and Software Verification

  • Graph kernels applied to function-call and control-flow graphs support malware detection, execution-trace analysis, program similarity measurement, and prediction of metamorphic relations.The passage notes that high-level code representations can help detect malware variations and retrieve similar programs.Source: §6.4 · p. 55

6.5 Natural Language Processing

  • Graph kernels model textual data as graphs for event recognition, biomedical-text classification, protein-interaction extraction, and document similarity; tree kernels also serve NLP tasks.Representations include word co-occurrence networks, which capture term relationships beyond bag-of-words models; cited applications include event graphs (Glavaš & Šnajder, 2013), biomedical concept graphs, protein-protein interaction extraction (Airola et al., 2008a, 2008b), and word co-occurrence networks (Nikolentzos et al., 2017).Source: §6.5 · p. 56

6.6 Other Applications

  • Other applications include RDF classification, entity disambiguation in anonymized graphs, architectural-style classification, and relational-state similarity estimation.The passage reports applications to RDF data (Lösch et al., 2012; De Vries & de Rooij, 2015), entity disambiguation, architectural designs, and relational reinforcement learning.Source: §6.6 · p. 56

7. Experimental Comparison

This section experimentally compares graph kernels and GNNs on graph-classification benchmarks spanning unlabeled, node-labeled, and node-attributed graphs, and examines kernel similarity estimates and representations on synthetic graphs.

7.1.1 Datasets

  • The experiments covered publicly available undirected datasets from chemoinformatics, bioinformatics, and social networks, including labeled, attributed, and unlabeled graphs.SYNTHETICnew and Synthie supplied synthetic node-attribute benchmarks.Source: §7.1.1 · pp. 57, 59

7.1.2 Experimental Setup

  • The comparison used 20 graph kernels and four GNNs across three graph-type scenarios, with 10-fold cross-validation for evaluation.Kernels used an SVM classifier; kernel computation was limited to 24 hours and 64 GB of memory per kernel. GNN running times were not compared with kernel times because of differing hardware and hyperparameter dependence.Source: §7.1.2 · pp. 59–60

7.1.3 Experimental Results

  • On node-labeled graphs, WL-OA led on three of seven datasets, CORE-WL-VH led on two others, and some graph kernel outperformed every GNN on all seven.WL-SP lagged related kernels; core methods improved SP on all but one dataset. AIDS was nearly perfectly classified by several kernels, while ENZYMES accuracy ranged from 16.7% to 58.0%.Source: Table 5 · p. 62, §7.1.3 · pp. 63–64
  • For node-labeled graphs, VH was fastest, while WL-VH, CORE-WL-VH, SP, PK, and NH were also relatively efficient; SM timed out on NCI1 and exceeded memory on two datasets.WLVH and NH were recommended for accuracy and efficiency, while WL-OA could perform better at higher computational cost; kernels generally beat GNNs here but do not scale to datasets with hundreds of thousands of graphs. PM runtime varied with graph size, ranking third-fastest on D&D.Source: Table 6 · p. 63, §7.1.3 · p. 64
  • On unlabeled graphs, GIN led on two of six datasets, while CORE-WL-VH led on three; graph kernels achieved the highest accuracy on four of six datasets.WL-OA, NH, and WL-VH also performed strongly, and assigning vertex labels from degree was recommended for kernels; the three multi-class Reddit and IMDb datasets were challenging, with best accuracies of 56.1%, 48.3%, and 51.7%, respectively.Source: §7.1.3 · pp. 64–67, Table 7 · p. 65
  • For unlabeled graphs, VH was fastest, whereas seven kernels failed to compute matrices on the large Reddit datasets within one day and SM timed out or exceeded memory on all six datasets.PK, ODD-STh, and WL-VH were also relatively efficient; the seven expensive kernels were Lo-ϑ, WL-PM, RW, NSPDK, CORE-SP, WL-SP, and GH.Source: §7.1.3 · p. 66, Table 8 · p. 66
  • On node-attributed graphs, GIN performed best overall, while GH was the best kernel on every dataset and outperformed two of the four GNNs.GNNs generally outperformed graph kernels; SP failed to finish any kernel matrix within one day, and SM finished only on BZR.Source: Table 9 · p. 67, §7.1.3 · p. 68
  • For node-attributed graphs, PK handled every dataset in under two minutes, while ML and GH took over two and three hours, respectively, on PROTEINS full.SP and SM were very expensive, limiting their practical usefulness.Source: Table 10 · p. 67, §7.1.3 · p. 68
  • For continuous node attributes, most kernels are prohibitively slow and PK has low accuracy on almost all datasets, so the authors recommend GNNs.They identify scalable kernels for continuous vertex attributes as an open challenge.Source: §7.1.3 · p. 68

7.2 Expessiveness of Graph Kernels

  • Prior theory shows polynomial-time kernels are non-injective (Gärtner et al., 2003), and shortest path, random walk, and Weisfeiler-Lehman subtree kernels miss triangle-freeness and bipartiteness.The section motivates empirically comparing kernel similarities with an oracle based on maximum common-edge overlap under vertex permutations, normalized to [0, 1]; a value of 1 indicates isomorphism, and computing it for large graphs is intractable.Source: §7.2 · pp. 68–69

7.2.1 Dataset

  • The synthetic dataset contains 191 pairwise non-isomorphic connected graphs of at most 9 vertices; most oracle similarities fall between 0.5 and 0.8.The graphs include cycles, paths, grids, complete and star graphs, as well as Erdős–Rényi, Barabási–Albert, and Watts–Strogatz graphs.Source: §7.2.1 · p. 69, Figure 16 · p. 70

7.2.2 Experimental Settings

  • The comparison evaluates 20 kernels on unlabeled synthetic graphs using Pearson correlation and MSE against the oracle, with hyperparameters selected for highest correlation.Kernel values are normalized to [0, 1], and vertices receive identical labels or attributes where required by a kernel.Source: §7.2.2 · pp. 70–71

7.2.3 Results

  • WL-PM and SM achieve correlation above 0.7; PM, WL-VH, WL-SP, and CORE-SP lead on MSE, while most kernels have MSE below 0.1.Most kernels have correlation above 0.5; VH’s constant normalized values make its correlation undefined for unlabeled graphs.Source: §7.2.3 · pp. 71–72, Figure 17 · p. 71
  • PCA projections show VH, RW, PK, and SVM-ϑ cluster together; SP and GH are close, as are the Weisfeiler-Lehman kernels, while NH and Lo-ϑ are isolated.The remaining kernels lie close together in the two-dimensional projection without forming well-defined clusters.Source: §7.2.3 · pp. 72–73, Figure 18 · p. 72

8. Conclusion

The survey reviews graph kernels and empirically evaluates selected kernels’ effectiveness and running time. It identifies challenges and research directions, especially scalable kernels for continuous attributes and more efficient assignment kernels.

8. Conclusion

  • The survey provides a detailed overview of graph kernels and evaluates selected kernels’ effectiveness and running time.The authors aim to clarify progress on graph kernels and graph classification and offer guidance for real-world applications.Source: §8 · p. 73
  • Most kernels for continuous attributes are computationally expensive or uncompetitive, motivating scalable methods that improve on state-of-the-art approaches.Source: §8 · p. 73
  • The authors propose extending valid assignment kernels to optimally match graph substructures, since assignment kernels are generally less complex than R-convolution kernels.They argue this framework could enable more efficient graph kernels.Source: §8 · p. 73

Related papers

Loading 1904.12218v2…