Graph Kernels: A Survey

Giannis Nikolentzos; Giannis Siglidis; Michalis Vazirgiannis

Source-linked AI summary

Graph Kernels: A Survey

Giannis Nikolentzos, Giannis Siglidis, Michalis Vazirgiannis

arXiv:1904.12218v2Apr 27, 2019stat.MLcs.LG

TL;DR

Graph learning needs methods that compare structured objects while preserving graph information despite computational challenges. This survey reviews and experimentally compares graph kernels, finding strong, scope-dependent performance while highlighting limits in expressiveness and efficiency.

Problem
Graph learning requires meaningful graph similarity, but direct graph comparison is complex and vectorization can discard rich topological information.
Method
The survey unifies graph-kernel literature and evaluates kernels across effectiveness, running time, expressiveness, and comparisons with graph neural networks.
Results
Graph kernels perform strongly in some settings: GH is the best kernel on continuous-attribute datasets, while WL-PM and SM exceed 0.7 correlation with the reference similarity function.
Takeaways & Limitations
Graph kernels remain useful tools for graph similarity and learning across diverse applications, with practical choice requiring attention to performance and running time.
Takeaways & Limitations
Complete graph kernels are impractical, and efficient kernels may fail to distinguish some non-isomorphic graphs or essential graph properties.

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-structured data is widespread, motivating learning methods that can operate on graphs rather than forcing them into feature vectors. This survey unifies graph-kernel research, evaluates many kernels empirically, and compares them with graph neural networks and each other.

1. Introduction: Graph data arise across social networks, biology, chemistry, and other domains because graphs represent entities together with their relationships.Their use supports learning tasks such as predicting protein function from structural similarity.
1. Introduction: Graph kernels provide similarity functions that capture graph semantics while remaining computationally efficient enough to support kernel methods directly on graphs.They enable kernel algorithms to operate on structured domains rather than only vector spaces.
1. Introduction: Dozens of graph kernels have been proposed over the past 20 years, with some achieving state-of-the-art results on several datasets.The survey positions these methods alongside the more recent growth of graph neural networks.
1. Introduction: The survey comprehensively reviews foundational and recent graph kernels, evaluates most of them experimentally, and studies their applications and comparative behavior.Its evaluation includes running times, comparisons with graph neural networks, and kernel expressiveness.
1. Introduction: The survey is intended to guide practitioners and researchers working on graph learning, graph similarity, and graph comparison.It emphasizes the value of a broader experimental comparison for understanding kernel strengths, weaknesses, and practical running times.

2. Motivation and Challenges

Graphs offer flexible representations of entities and relationships, but their combinatorial structure makes direct learning and comparison difficult. These challenges motivate graph kernels and other methods that preserve graph structure while remaining computationally tractable.

2. Motivation and Challenges: Graphs represent both entities and their relationships, allowing them to model structured objects more flexibly than fixed-length feature vectors.Vectors generally cannot capture relationships among an object's entities and commonly impose a shared dimensionality.
2. Motivation and Challenges: The combinatorial nature of graphs makes algorithms operating directly on them computationally expensive and difficult to scale to large datasets.This has contributed to the dominance of vector-based learning algorithms.
2. Motivation and Challenges: No polynomial-time transformation to feature vectors can preserve all graph representational power, so vectorization may lose rich topological information.The paper therefore motivates methods that operate directly on graphs.
2. Motivation and Challenges: Graph-level learning depends on meaningful graph similarity or distance measures, which can support tasks such as classification and clustering.Similarity functions are central to methods including nearest-neighbor classification and learning in proximity spaces.
2. Motivation and Challenges: Graph comparison is difficult because graphs lack the convenient mathematical structure of vector spaces and many operations are computationally expensive.Determining whether two graphs are identical is a particularly striking example of this complexity.

3. Preliminaries

The preliminaries introduce graph representations, structural notation, and the kernel concepts used throughout the survey. They distinguish unlabeled, labeled, and attributed graphs and explain how kernels measure similarity through implicit Hilbert-space representations.

3. Preliminaries: A graph consists of vertices and edges, and may additionally carry discrete labels or real-valued attributes on vertices and edges.Labeled graphs use a discrete label function, while attributed graphs assign vectors; labeled graphs can be encoded with one-hot vectors.
3. Preliminaries: The preliminaries establish adjacency and Laplacian matrices alongside standard structural notions including degree, induced subgraph, clique, path, cycle, shortest path, diameter, and neighborhoods.These notions provide notation for describing graph structure and kernel constructions.
3. Preliminaries: The notation section defines common graph quantities such as size, number of edges, density, and radius-based neighborhoods used in later discussions.A graph's size is denoted by |V| or n, while its edge count is denoted by |E| or m.
3. Preliminaries: Kernel values measure object similarity and can be represented as inner products of mapped objects in a Hilbert space.The associated reproducing kernel Hilbert space provides the mathematical setting for this representation.
3. Preliminaries: A positive semidefinite kernel is a function whose kernel matrices are positive semidefinite, enabling kernel methods over structured domains such as graphs.Kernel methods use an implicit feature-space mapping rather than requiring the input domain itself to be a vector space.

4. Graph Kernels

This section introduces graph kernels as graph-to-graph similarity functions and frames their design around expressive, efficient positive semidefinite comparisons.

4.1 Kernels between Graphs: The survey reviews representative graph-kernel approaches, covering foundational and recent methods alongside detailed descriptions and experimental evaluation.
4.1 Kernels between Graphs: Graph kernels compare graphs through positive semidefinite similarity functions, representable as inner products in a Hilbert space.The survey focuses on kernels between graphs rather than kernels comparing nodes within graphs.
4.1 Kernels between Graphs: Graph kernels combine graph representation with kernel-based discrimination for graph similarity and learning tasks.
4.1 Kernels between Graphs: Designing graph kernels requires balancing expressive similarity assessment with computational efficiency.The main challenge is defining appropriate positive semidefinite kernels that reliably assess similarity among input graphs.

4.2 Simple Kernels

Simple graph kernels construct explicit histograms of vertex or edge labels and compare them with linear kernels, yielding linear-time computation in the corresponding graph size.

4.2.1 Simple Kernels: The vertex histogram kernel compares node-labeled graphs through a linear kernel on vertex-label histograms.Each histogram component counts vertices carrying one label.
4.2 Simple Kernels: Vertex-histogram computation is linear in the number of vertices, whereas edge-histogram computation is linear in the number of edges.
4.2.2 Simple Kernels: The edge histogram kernel compares edge-labeled graphs through a linear kernel on edge-label histograms.Each histogram component counts edges carrying one label.

4.3 Expressiveness vs Efficiency

Graph-kernel expressiveness is constrained by the computational difficulty of complete kernels, creating a central trade-off between distinguishing graph structure and efficiency.

4.3 Expressiveness vs Efficiency: The survey identifies efficiency-effectiveness trade-offs as vital when designing expressive graph kernels.Simple histogram kernels are positive semidefinite but correspond to relatively naive structural concepts.
4.3 Expressiveness vs Efficiency: Complete graph kernels use injective feature maps and can distinguish all non-isomorphic graphs in the feature space.
4.3 Expressiveness vs Efficiency: Computing any complete graph kernel is at least as hard as graph-isomorphism testing, limiting the practicality of complete kernels.
4.3 Expressiveness vs Efficiency: Several established kernels, including Weisfeiler-Lehman subtree kernels, cannot distinguish properties such as connectivity, planarity, and bipartiteness.
4.3 Expressiveness vs Efficiency: The taxonomy organizes graph kernels within a broader landscape of structural and representational design choices.

4.4 Taxonomy of Graph Kernels

The survey organizes graph kernels by structural focus, graph-label support, and whether they use explicit or implicit computation schemes.

4.4 Taxonomy of Graph Kernels: Graph kernels are grouped by structural aspects such as random walks, subtrees, cycles, paths, and small subgraphs.
4.4 Taxonomy of Graph Kernels: They are also categorized by support for unlabeled, node-labeled, or node-attributed graphs.
4.4 Taxonomy of Graph Kernels: Another distinction separates explicit feature-mapping approaches from implicit computation schemes.
4.4 Taxonomy of Graph Kernels: The summary table records explicit mapping, label support, kernel type, and worst-case evaluation complexity, while noting that practical runtimes can be lower.
4.4 Taxonomy of Graph Kernels: The survey proceeds from random-walk and Weisfeiler-Lehman-inspired kernels to assignment kernels, continuous-attribute kernels, and frameworks built on existing kernels.

4.5 Early Days of Graph Kernels

Early graph kernels decomposed graphs into comparable substructures, balancing expressive power against polynomial-time computation. The section traces random-walk, subtree, cyclic-pattern, and shortest-path approaches.

Foundations: R-convolution kernels decompose graphs into substructures and sum pairwise similarities, but comparing all subgraphs is NP-hard.This motivates less powerful graph kernels with polynomial-time computation.
Random Walk Kernels: Random-walk kernels measure graph similarity through common walks and can be computed in polynomial time using direct-product constructions.The direct product represents simultaneous walks in two graphs.
Random Walk Kernels: The geometric random-walk kernel requires λ < 1/λ× for convergence, while direct computation takes O(n6) time.Efficient methods reduce random-walk kernel complexity generally to O(n3).
Subtree Kernel: The subtree kernel counts common rooted subtree patterns and is more expressive than walk-based kernels, but computationally more expensive.Its worst-case complexity is O(n24deg∗h), although sparse graphs or diverse labels can make it practical.
Other Early Kernels: Cyclic-pattern kernels compare canonical representations of shared cycles and bridge-induced trees, whereas shortest-path kernels use vertex-label and path-length features.The shortest-path kernel can be computed in O(n4) time.
Weisfeiler-Lehman Subtree Kernel: The Weisfeiler-Lehman subtree kernel was introduced as a fast subtree-kernel approach that scales to large labeled graphs.It is considered state-of-the-art in graph classification.

4.6 Neighborhood Aggregation Approaches

Neighborhood aggregation kernels enrich node labels with neighborhood information and compare the resulting labels across graphs. Variants trade simplicity against collision resistance and capture increasingly high-order relationships through iteration.

Overview: Neighborhood aggregation updates each vertex representation from neighboring labels, forming the basis of several graph-kernel variants.The Weisfeiler-Lehman relabeling procedure can be viewed as neighborhood aggregation or message passing.
Simple Neighborhood Hash: Simple neighborhood hashing combines neighbor bit labels with XOR and ROT to produce a new label encoding local label distributions.Identical center labels and neighbor-label sets yield the same hash except for accidental collisions.
Count-Sensitive Neighborhood Hash: Count-sensitive hashing addresses problematic collisions by aligning neighbor labels, counting occurrences, and updating each unique label accordingly.Simple-hash collisions can affect the kernel’s positive semidefiniteness.
Kernel Calculation: The neighborhood hash kernel compares updated labels using a Tanimoto-equivalent similarity function and has complexity O(deg nhd).Here n is the number of vertices and deg is the average vertex degree.
Iterative Updates: Iterating label updates h times lets neighborhood hash kernels represent label distributions over h-neighbors and higher-order vertex relationships.Vertices with identical labels and corresponding connections can receive identical updated labels.

4.7 Other Approaches

Other graph kernels avoid standard neighborhood aggregation by comparing localized subgraph pairs, graph invariants, or global graph representations. These methods introduce alternatives with explicit computational and applicability trade-offs.

Neighborhood Subgraph Pairwise Distance Kernel: The neighborhood subgraph pairwise distance kernel compares rooted subgraph pairs whose roots have a specified distance and radius.Graph invariants and hashing approximate isomorphism checks instead of testing subgraphs directly.
Neighborhood Subgraph Pairwise Distance Kernel: For small radius and distance parameters, the neighborhood subgraph pairwise distance kernel is practically linear in graph size.Its stated complexity is O(n|S||E(S)| log |E(S)|).
Lovász ϑ Kernel: Lovász ϑ kernels represent vertices orthonormally, compute Lovász values for vertex subsets, and compare those values with a positive semidefinite base kernel.The kernel applies only to unlabeled graphs.
Lovász ϑ Kernel: Exact Lovász ϑ-kernel computation is generally infeasible because it requires minimum enclosing cones for 2^n vertex subsets, motivating sampling.The sampled formulation has complexity O(n2mϵ−1 + s2T(k) + sn).
SVM-ϑ Kernel: The SVM-ϑ kernel was developed as a more efficient alternative to the computationally expensive Lovász ϑ kernel and also assumes unlabeled graphs.Its matrix construction is positive semidefinite, and on certain graph families it approximates ϑ(G) within a constant factor with high probability.
Ordered Decomposition DAGs Kernel: Ordered decomposition DAG kernels project sub-DAGs into tree space and apply tree kernels, with complexity depending on the chosen tree kernel.Subtree and subset-tree kernels yield O(n3 log n) and O(n4), respectively.

4.8 Assignment Kernels

Assignment kernels maximize similarity through correspondences between graph substructures, but valid positive semidefinite constructions require careful design. The section develops embedding-based and hierarchy-based assignments, including the Weisfeiler-Lehman optimal assignment kernel.

Assignment Kernels: Assignment kernels match substructures across graphs to maximize overall similarity, potentially revealing structural correspondences.Not every optimal-assignment construction is positive semidefinite.
Pyramid Match Graph Kernel: The pyramid match graph kernel has complexity O(dnL) and restricts labeled-graph matchings to vertices sharing the same label.Separate pyramid-match kernels are summed across labels.
Weisfeiler-Lehman Optimal Assignment Kernel: The Weisfeiler-Lehman optimal assignment kernel uses WL-refined node labels in a valid assignment construction based on a strong base kernel.The base kernel reflects similarity between vertex neighborhoods.
Strong Kernels and Hierarchies: A strong kernel satisfies k(x,y) ≥ min{k(x,z), k(z,y)} and is induced by a hierarchy whose leaf elements are the kernel domain.Hierarchy weights define similarities through the lowest common ancestor.
Strong Kernels and Hierarchies: Hierarchy-induced strong kernels admit explicit feature maps using nonnegative additive weights, enabling histogram-intersection computation of the assignment kernel.The resulting computation is linear in the hierarchy-tree size.

4.9 Kernels for Graphs with Continuous Attributes

Continuous node attributes remain less well supported by graph kernels than discrete labels, motivating kernels that directly compare attributes or discretize them first. The section presents attribute-aware path and subgraph-matching approaches alongside multiscale Laplacian approximations.

Motivation: Continuous multi-dimensional node attributes remain a major gap because scalable kernels for such graphs are less available than for discrete labels.Examples include cybersecurity call graphs, computer vision, and bioinformatics.
Subgraph Matching Kernels: Subgraph matching kernels count bounded-size subgraph matchings and can incorporate node or edge labels and attributes.A weighted product graph represents compatible vertex and edge pairs, whose cliques are enumerated to score matchings.
Subgraph Matching Kernels: The common subgraph isomorphism kernel counts isomorphic subgraphs by enumerating product-graph cliques corresponding to common subgraphs.Its vertex and edge kernels enforce label and adjacency compatibility.
Computational Considerations: Subgraph matching has worst-case complexity O(knk+1), while GraphHopper uses recursive message passing with stated complexity O(n2(m + log n + d + δ2)).The subgraph-matching cost depends on product-graph clique enumeration, whereas GraphHopper uses shortest-path statistics.
GraphHopper Kernel: GraphHopper compares shortest paths of equal discrete length by summing node-kernel similarities at corresponding hop positions.Node kernels can compare discrete labels with delta kernels or continuous attributes with linear or Gaussian kernels.
Multiscale Laplacian Graph Kernel: The multiscale Laplacian kernel makes computation feasible by approximating the joint feature space and retaining only the leading ˆp basis vectors through kernel PCA.For N graphs, the stated complexity becomes O(N˜c2ˆp3lmax +N˜c3lmax +N2ˆp3).

4.10 Frameworks

The survey describes frameworks that improve existing graph kernels by exploiting label-substructure relationships, hierarchical smoothing, or graph core structure. These methods trade additional modeling or approximation choices for improved comparisons or computational feasibility.

Framework Scope: The Weisfeiler-Lehman framework can wrap any kernel that handles discrete node labels, while deep and smoothing frameworks require explicitly computable feature maps.These applicability conditions constrain which existing kernels each framework can extend.
Deep Graph Kernels: Deep graph kernels address diagonal dominance by applying a positive semidefinite matrix that encodes similarities among explicitly represented substructures.The matrix may be manually designed or learned using techniques inspired by natural language processing.
Structural Smoothing: Structural smoothing propagates discounted count mass through a DAG of lower- and higher-order substructures, giving absent substructures positive feature values.A substructure with count zero can receive PSS(s) > 0 from its parents.
Core Framework: The core framework improves graph comparison by decomposing graphs into nested k-cores and aggregating similarities between corresponding hierarchical subgraphs.The k-core decomposition recursively removes vertices below a degree threshold and can be computed in O(n + m) time.
Core Framework: Core-kernel complexity depends on the base algorithm and the minimum degeneracy of the compared graphs.The framework’s stated complexity is expressed using the base complexity O_A and the minimum degeneracy δ∗.

4.11 Tree Kernels

Tree kernels apply kernel methods to structured tree representations, especially in natural language processing, to capture syntactic and semantic information without manually engineered features. Like graph kernels, they fix features in advance and decouple representation from learning.

Applications: Tree kernels operate on structured representations such as dependency parse trees and have been applied mainly to natural language processing tasks.Examples include semantic role labeling, relation extraction, parsing reranking, and question classification.
Motivation: Tree kernels reduce reliance on expensive, domain-expert feature engineering by operating directly on structured representations that encode syntactic and semantic information.The surveyed motivation is to avoid computing manually designed features for structured text.
Limitations: Graph and tree kernels share limitations because both fix feature sets in advance, decoupling data representation from subsequent learning.The survey also notes that task-specific superiority among tree kernels lacks a general justification.

5. Link to Graph Neural Networks

Graph neural networks address limitations of graph kernels by learning representations through differentiable neighborhood aggregation, but their expressive power depends on the aggregation and readout functions. The survey relates these operations to Weisfeiler-Lehman graph comparison and reviews four evaluated GNN models.

Comparison with Graph Kernels: Graph kernels typically use fixed feature-generation schemes, whereas GNNs learn representations jointly with the task-specific model.This addresses the decoupling between representation and learning identified as a graph-kernel limitation.
Comparison with Graph Kernels: GNNs also improve support for continuous multi-dimensional node attributes, a setting where efficient graph kernels remain limited.The survey contrasts scalable kernels for unlabeled or discrete-label graphs with weaker support for continuous attributes.
Message-Passing GNNs: GNNs learn graph representations through differentiable, permutation-invariant neighborhood aggregation followed by a differentiable, permutation-invariant readout.Common readouts include sum, mean, and max aggregation over final vertex representations.
Expressive Power: If AGGREGATE, COMBINE, and READOUT are injective, a GNN distinguishes every pair of graphs that the Weisfeiler-Lehman test declares non-isomorphic.Most standard GNNs are otherwise less powerful than the Weisfeiler-Lehman test, motivating higher-order variants.
Evaluated Models: The evaluation covers DGCNN, GraphSAGE, DiffPool, and GIN, including sampling-based, hierarchical pooling, and graph-level representation mechanisms.GraphSAGE scales to very large graphs by uniformly sampling a fixed-size neighbor set, while DiffPool learns soft cluster assignments hierarchically.

6. Applications of Graph Kernels

Graph kernels have been applied across bioinformatics, chemoinformatics, computer vision, biomedical imaging, malware detection, text, and other relational-data problems.

Chemoinformatics models compounds as atom-and-bond graphs to computationally identify molecules with desired properties or activities.
Bioinformatics applications include predicting protein function, identifying disease-related interactions, and analyzing functional non-coding RNA sequences.
Graph kernels support computer-vision tasks by operating on image graphs whose vertices represent pixels or segmented regions and whose edges encode neighborhood.
Biomedical-imaging applications use graphs extracted from fMRI data to distinguish brain states and address related subject-level classification problems.
Beyond biology and imaging, graph kernels have been used for malware detection, text represented as linguistic graphs, RDF classification, entity disambiguation, architectural-style classification, and relational reinforcement learning.

7. Experimental Comparison

The experiments show that kernel performance depends on graph annotations and computational constraints: neighborhood-aggregation kernels are strong for node-labeled graphs, while GIN leads on unlabeled graphs and continuous attributes create major runtime challenges.

Node-Labeled Graphs: WL-OA is best on 3 of 7 node-labeled datasets, CORE-WL-VH on 2, and all GNNs are outperformed by some graph kernel across these datasets.
Node-Labeled Graphs: 58.0% versus 16.7% accuracy on ENZYMES shows an exception to generally low kernel variability, while near-perfect AIDS classification raises comparison concerns.
Runtime: VH is fastest for node-labeled graphs, whereas many continuous-attribute kernels are expensive; PK finishes all datasets within two minutes but usually has low accuracy.
Unlabeled Graphs: GIN is best on unlabeled graphs, but CORE-WL-VH leads on 3 of 6 datasets and several neighborhood-aggregation kernels outperform the other three GNNs.
Unlabeled Graphs: For unlabeled graphs, assigning degree-based discrete labels and using neighborhood aggregation yields kernels with high accuracy and relatively low complexity; kernels win on 4 of 6 datasets.
Continuous Attributes: Continuous vertex attributes remain a scalability challenge because most kernels have prohibitive runtimes, despite GNNs naturally handling continuous features.
Similarity Analysis: Most kernels correlate above 0.5 with the reference graph-similarity function and often have MSE below 0.1, indicating substantial empirical similarity capture.

8. Conclusion

The survey reviews graph kernels, evaluates their effectiveness and running times, and identifies continuing challenges and directions for more scalable and efficient methods.

The survey provides a detailed overview of graph kernels and empirically evaluates their effectiveness and running time.
Most kernels for continuous node attributes remain computationally expensive or produce noncompetitive results, motivating scalable alternatives.
Developing scalable kernels for continuously attributed graphs is identified as an important research direction.
Assignment-kernel frameworks offer a direction toward more efficient kernels by optimally assigning graph substructures with more attractive complexity than R-convolution kernels.