PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Graph Kernels

Nils M. Kriege, Fredrik D. Johansson, Christopher Morris

arXiv:1903.11835v2cs.LGstat.ML

TL;DR

Graph classification requires methods that exploit graph structure and annotations rather than treating observations as vectors. This survey categorizes graph kernels, evaluates them across datasets, and finds that Gaussian RBF transformations can substantially improve simple kernels on several datasets while motivating dataset- and scale-dependent kernel choices.

  • Problem

    Graph data encode relational structure and annotations that traditional vector- or grid-based learning methods cannot directly exploit, motivating effective graph classification techniques.

  • Method

    The survey categorizes graph kernels by extracted features, computation, and practical applicability, then evaluates diverse kernels, baselines, transformations, and prediction agreement across datasets.

  • Results

    Gaussian RBF transformations substantially improve simple kernels on several datasets, while different kernels show dataset-dependent accuracy and structural completeness patterns.

  • Takeaways & Limitations

    The authors recommend VL, EL, and GL3 with Gaussian RBF as baselines, WL-OA for small and medium datasets, and WL with linear classifiers for large datasets.

  • Takeaways & Limitations

    Gaussian RBF combinations require optimizing an additional hyper-parameter and complicate fast linear classifiers, limiting their general recommendation for WL and WL-OA.

Abstract

from arXiv · show

Graph kernels have become an established and widely-used technique for solving classification tasks on graphs. This survey gives a comprehensive overview of techniques for kernel-based graph classification developed in the past 15 years. We describe and categorize graph kernels based on properties inherent to their design, such as the nature of their extracted graph features, their method of computation and their applicability to problems in practice. In an extensive experimental evaluation, we study the classification accuracy of a large suite of graph kernels on established benchmarks as well as new datasets. We compare the performance of popular kernels with several baseline methods and study the effect of applying a Gaussian RBF kernel to the metric induced by a graph kernel. In doing so, we find that simple baselines become competitive after this transformation on some datasets. Moreover, we study the extent to which existing graph kernels agree in their predictions (and prediction errors) and obtain a data-driven categorization of kernels as result. Finally, based on our experimental results, we derive a practitioner's guide to kernel-based graph classification.

1 Introduction

Graph kernels enable learning on relational data that cannot be represented as vectors or fixed grids, motivating a broad literature of graph-similarity methods. This survey organizes that literature, evaluates kernels and baselines experimentally, analyzes their agreement, and provides practitioner guidance.

  • Motivation: Graph kernels measure graph similarity and can be used with kernel machines such as support vector machines for graph-structured learning.Their importance is linked to the prevalence of graph-structured data and the empirical success of kernel-based classification.
  • Survey scope: The survey categorizes graph kernels by design paradigm, graph features, computation method, expressivity, and practical applicability.It considers kernels for continuous attributes, discrete labels, and unlabeled graphs, and discusses reliance on the kernel trick.
  • Experimental evaluation: The experimental study compares state-of-the-art kernels with simple baselines and examines their ability to distinguish graphs in benchmark datasets.The comparison assesses whether more sophisticated methods are needed to capture additional structural features.
  • Experimental evaluation: Applying a Gaussian RBF kernel to a graph-kernel-induced metric makes simple baselines competitive with state-of-the-art kernels on some datasets but not others.The transformation is intended to learn non-linear decision boundaries in the graph-kernel feature space.
  • Analysis and guidance: The survey studies agreement among graph kernels through their classification predictions and errors, yielding a data-driven assessment of which graphs they deem similar.It also provides guidelines for practitioners and new researchers applying graph kernels successfully.
  • Positioning: Compared with existing surveys, it covers more kernels and uses a unified experimental study because results across papers may rely on incomparable setups.The cited setup differences include hyperparameter choices and the number of cross-validation folds.

2 Fundamentals

This section defines graphs, their representations, and kernel methods, then motivates graph-specific kernels by the need for permutation-invariant comparisons. It introduces convolution kernels as a dominant framework while noting diagonal dominance and component-correspondence limitations.

  • Graph fundamentals: A graph G=(V,E) consists of finite vertices and edges, with the survey restricting attention to undirected graphs without duplicate edges or self-cycles.Vertices represent objects and edges represent relations; labeled graphs add a vertex-label function l: V(G) → Σ.
  • Graph fundamentals: Neighborhoods, degrees, walks, paths, connectivity, isomorphism, subgraphs, and induced subgraphs provide basic structural graph concepts.For labeled graphs, isomorphism requires the bijection to preserve labels.
  • Graph fundamentals: Adjacency, Laplacian, and incidence matrices are alternative graph representations that carry the same information, with L=D−A and L=MM⊤.The adjacency matrix records edges, while D is the diagonal degree matrix.
  • Kernel methods: A kernel compares pairs of data points through an inner product in a Hilbert space, equivalently requiring positive semidefiniteness; its Gram matrix contains pairwise kernel values.Kernel methods support paradigms including SVM classification, GP regression, kernel PCA, k-means, and KDE.
  • Graph kernels: Graph comparisons must be permutation invariant because vertex and edge ordering does not change graph structure, making vector distances between adjacency matrices typically uninformative.Most graph kernels use convolution kernels, which decompose graphs into substructures and compare pairs of components.
  • Graph kernels: Convolution kernels can suffer from diagonal dominance and may be unsuitable when components correspond one-to-one across objects.Weights between components were introduced to alleviate diagonal dominance, while mapping kernels use a predetermined subset of component pairs.

3 Graph Kernels

Graph kernels emerged in 2003 and subsequently focused on computational tractability for large, predominantly discretely labeled graphs. Since 2012, research has expanded to continuous attributes, while neural methods still seek representations superior to fixed graph-kernel feature spaces.

  • Origins: Graph kernels were first proposed in 2003, although related graph-comparison methods existed earlier in chemoinformatics.A timeline summarizes milestones in graph kernels and related graph-learning algorithms.
  • Research directions: Subsequent work focused on making kernels computationally tractable for large graphs with predominantly discrete vertex labels.
  • Research directions: Since 2012, several graph kernels specifically designed for continuous attributes have been proposed.
  • Research directions: Developing neural graph techniques that clearly outperform fixed graph-kernel feature spaces remains a current research challenge.
  • Organization: The literature is organized by neighborhood aggregation, assignment and matching, subgraph-pattern extraction, walks and paths, and other kernels.The survey presents these design paradigms in sequence across the following subsections.

3.1 Neighborhood Aggregation Approaches

Neighborhood aggregation kernels compare graphs through iteratively computed vertex attributes that summarize local structure, with the 1-dimensional Weisfeiler–Lehman algorithm providing a prominent discrete-label framework. The Weisfeiler–Lehman subtree kernel concatenates feature vectors across iterations, while related variants and higher-dimensional, propagation-, and depth-based methods extend the paradigm.

  • Core paradigm: Neighborhood aggregation assigns each vertex an attribute by repeatedly aggregating attributes from its immediate neighbors.This approach represents local graph structure through iterative vertex-level summaries.
  • 1-WL relabeling: The 1-dimensional Weisfeiler–Lehman algorithm iteratively relabels each vertex using its own label and the sorted multiset of neighboring labels.Relabeling uses an injective mapping to assign previously unused labels to these combinations.
  • Weisfeiler–Lehman subtree kernel: The Weisfeiler–Lehman subtree kernel concatenates per-iteration label-count feature vectors and compares graphs with their inner product.For h iterations, the feature vector aggregates representations from all iterations, including the initial labeling.
  • Weisfeiler–Lehman subtree kernel: A single Weisfeiler–Lehman feature-vector computation runs in O(hm), while Gram-matrix computation over N graphs runs in O(Nhm + N^2hn).Here n and m are the maximum numbers of vertices and edges across the graphs, respectively.
  • Extensions and related approaches: Related methods count refined endpoint colors on edges, apply shortest-path kernels to refined labels, label k-tuples, propagate labels and real-valued attributes, or use depth-based vertex representations.Depth-based methods compute Shannon entropy over m-layer expansion subgraphs or strengthen vertex labels before matching-based graph-kernel construction.

3.2 Assignment- and Matching-based Approaches

Assignment-based graph kernels compare structured objects by finding correspondences between their components, often through optimal matching. Although optimal assignment similarities are generally indefinite, several constructions recover valid positive-semidefinite kernels, including prototype, restricted-base-kernel, and transitive approaches.

  • 3.2 Assignment- and Matching-based Approaches: Assignment kernels compare graph components by selecting the best matching between them, such as mapping chemically or structurally similar vertices across graphs.Vertices can be embedded in a common space, then matched through a weighted bipartite graph.
  • 3.2 Assignment- and Matching-based Approaches: Optimal assignment kernels search over component mappings rather than summing base-kernel values under a fixed ordering.For sets with different cardinalities, the smaller set is padded with objects whose base-kernel values are zero.
  • 3.2 Assignment- and Matching-based Approaches: Optimal assignment similarities are not positive-semidefinite in general, complicating their direct use in kernel methods.Proposed remedies include prototype-based kernels derived from metric matching distances and graph embeddings for Euclidean matching.
  • 3.2 Assignment- and Matching-based Approaches: Strong base kernels make optimal assignment kernels valid and computable in linear time by histogram intersection.For graph classification, the base kernel can come from Weisfeiler-Lehman refinement.
  • 3.2 Assignment- and Matching-based Approaches: The Weisfeiler-Lehman optimal assignment kernel often achieves better classification accuracy on real-world benchmark datasets than the Weisfeiler-Lehman subtree kernel.Hierarchy weights associated with strong base kernels can also be optimized using multiple kernel learning.
  • 3.2 Assignment- and Matching-based Approaches: Transitive assignment kernels find one assignment across all dataset graphs, satisfying mapping transitivity and producing positive-semidefinite kernels.This global assignment replaces pairwise optimal assignments and may therefore be non-optimal for individual graph pairs.

3.3 Subgraph Patterns

Subgraph-pattern kernels represent graphs by counts of fixed-size subgraph isomorphism types, capturing structure that vertex- and edge-label kernels ignore. Graphlet kernels are expressive but computationally expensive because their cost grows exponentially with graphlet size.

  • Graphlet kernels: Graphlet kernels address the limits of bag-of-vertices or bag-of-edges representations by counting occurrences of fixed-size subgraph patterns.They are motivated by baseline representations that ignore object structure and by the limited informativeness of label kernels for unlabeled graphs.
  • Graphlet kernels: The graphlet feature map counts all induced, possibly disconnected subgraphs on k > 0 vertices according to their isomorphism types.For each type σ_i, the feature value φ_GR(G)_σ_i is the number of its instances in graph G.
  • Graphlet kernels: The graphlet kernel compares two graphs using the inner product of their graphlet feature maps.Equivalently, it compares the number of instances of each pattern in the two graphs.
  • Computation and limitations: Graphlet-kernel computation scales exponentially with graphlet size, motivating faster algorithms for k ∈ {3, 4} and restrictions to connected graphlets.Graph canonization has no known polynomial-time algorithm, although practical algorithms handle small graphlets efficiently.
  • Alternative subgraph patterns: Tree-pattern kernels consider subsets of neighbors and repeated vertices, but their broader pattern search prevents scaling to larger datasets.They are similar to Weisfeiler-Lehman subtree kernels while differing by considering all possible neighbor subsets.

3.4 Walks and Paths

Walk- and path-based graph kernels compare traversal-derived information, including shortest-path attributes and shared random-walk label sequences. The section also describes computational strategies, scalability limitations, tottering avoidance, and fixed-length variants.

  • Shortest-path kernels: The shortest-path kernel compares vertex attributes and shortest-path lengths between all vertex pairs in two graphs.Its general evaluation for a graph pair takes O(n^4), while discrete labels and indicator kernels permit an explicit feature map counting labeled distance triples.
  • Random-walk kernels: Random-walk kernels count shared label sequences generated by walks, with feature spaces containing all possible sequences when walk length is unbounded.The unrestricted formulation produces a high-dimensional feature space.
  • Random-walk kernels: Tottering, in which a walk immediately reverses along the same edge, can introduce uninformative repeated vertices and is addressed with a second-order Markov random-walk model.This modification removes walks containing v_i = v_i+2 for some i, but does not eliminate every possible repetition.
  • Random-walk kernels: The direct-product approach computes shared-label walk comparisons through a graph whose walks correspond one-to-one with identically labeled walks in the two input graphs.For geometric weights, computation is dominated by direct-product adjacency-matrix inversion and takes roughly O(n^6).
  • Random-walk kernels: Fixed-length variants restrict walks to length ℓ or at most ℓ, yielding the ℓ-walk and Max-ℓ-walk kernels used in application studies and systematic analyses.Application examples include protein-function prediction and image classification.

3.5 Kernels for Graphs with Continuous Labels

Kernels for continuously attributed graphs typically combine user-defined label kernels with structural graph kernels through valid kernel operations. The section presents weighted vertex kernels, specialized alternatives, and scalable approaches that discretize continuous attributes.

  • Kernel design: Attributed-graph kernels combine user-defined kernels for vertex and edge labels with structural kernels using operations such as addition or multiplication.GraphHopper and GraphInvariant are examples of this design.
  • Weighted vertex kernels: Weighted vertex kernels use a vertex-attribute kernel k_V together with a structure-based weighting kernel k_W and form instances of R-convolution kernels.k_V compares vertex attributes, while k_W assigns weights based on individual graph structures.
  • Weighted vertex kernels: For real-valued attributes, k_V can be a Gaussian RBF kernel, while k_W determines how strongly graph structure contributes to the resulting kernel.A Weisfeiler-Lehman-based k_W measures structural similarity through refined neighborhood labels.
  • Specialized kernels: GraphHopper is another weighted vertex kernel that represents vertices with shortest-path position-count matrices and compares them using the Frobenius inner product.Each matrix entry counts occurrences of a vertex at a shortest-path position and discrete length up to the maximum graph diameter.
  • Other approaches: Other approaches include subgraph matching with custom attribute kernels, Descriptor Matching with propagated neighborhood structure and pyramid matching, and randomized hashing that enables explicit discrete-feature maps for continuous attributes.Descriptor Matching can be computed in time linear in the number of edges, while the hashing framework also yields approximation results and a continuous-attribute Weisfeiler-Lehman subtree variant.

3.6 Other Approaches

Other graph-kernel approaches use group representation theory, spectral graph theory, eigen decompositions, explicit feature-map analysis, streaming algorithms, and neural language-modeling techniques. These methods extend graph kernels to multiple scales, dynamic and streaming settings, scalable computation, and relationships between graph features.

  • Alternative kernel constructions: Graph invariants from group representation theory and spectral graph theory provide alternative graph kernels, including one capturing neighborhoods at multiple scales.The spectral approach also includes a low-rank approximation algorithm for scaling computation to large graphs.
  • Dynamic and streaming graphs: A dynamic-graph kernel handles vertices and edges added or deleted over time using eigen decompositions.The cited approach is specifically designed for graph evolution over time.
  • Explicit feature maps: Kriege et al. studied when graph-kernel feature maps can be computed explicitly and efficiently, providing theoretical and empirical results for walk-based kernels.Their analysis concerns both the possibility and efficiency of explicit feature-map computation.
  • Neural feature relationships: Neural language-modeling methods allow kernels to respect relationships between graph features through hand-designed similarity matrices for graphlet and Weisfeiler-Lehman subtree kernels.The approach uses techniques such as skip-gram and is demonstrated on selected established graph kernels.

4 Expressivity of Graph Kernels

This section frames graph-kernel expressivity as the ability to distinguish graph patterns and properties, formalized through complete kernels and related theoretical measures. It also summarizes evidence that practical kernels have limited expressivity and discusses statistical analyses of its bounds and privacy tradeoffs.

  • Graph-kernel expressivity is the ability to distinguish certain graph patterns and properties.A complete graph kernel has a feature map that is an injection.
  • If a kernel is not complete, some non-isomorphic graphs share the same feature-map representation and cannot be distinguished by any classifier based on that kernel.
  • Practical graph kernels are not complete, motivating expressivity characterizations based on the graph properties they can distinguish.
  • The Weisfeiler-Lehman subtree, shortest-path, and graphlet kernels cannot distinguish basic properties such as planarity or connectedness.
  • Statistical studies bound expressivity using Rademacher complexity and stability theory, compare estimated expressivity experimentally, and examine its tradeoff with differential privacy.

5 Applications of Graph Kernels

Graph kernels have been applied across scientific areas by representing domain objects and relational data as graphs. Applications include chemoinformatics, bioinformatics, neuroscience, natural language processing, and computer vision, with a neuroscience kernel consistently outperforming baseline kernels.

  • Chemoinformatics: In chemoinformatics, molecules are represented as graphs whose vertices are atoms and edges are bonds, supporting in-silico modeling for drug development.Atomic and bond chemistry can be encoded as graph attributes.
  • Chemoinformatics: Classical molecular fingerprints enumerate graph substructures or encode atom neighborhoods, while random-walk and path-based kernels achieve similar classification performance on molecular datasets.Fingerprints are commonly compared with similarity measures such as the Tanimoto coefficient, which are closely related to kernels.
  • Bioinformatics: In bioinformatics, protein graphs represent structural components as vertices and spatial or sequence proximity as edges, with categorical and real-valued attributes on both.The cited protein representation uses components such as helices, sheets, and turns.
  • Neuroscience: In neuroscience, graph kernels compare brain networks to identify disease- or stimulus-related patterns, and an iterative neighborhood-expansion kernel consistently outperforms baseline kernels.The kernel exploits the one-to-one mapping between brain regions across graphs and is similar to the Weisfeiler-Lehman kernel.
  • Natural language processing: Graph kernels measure similarity in natural language processing by modeling documents, terms, publication venues, authors, and named entities as relational graphs.One example uses the shortest-path kernel on document graphs connecting terms that co-occur within a fixed-size text window.
  • Computer vision: In computer vision, walk-based and tree-pattern kernels support image classification, while graph kernels also encode frame features and temporal changes for human action recognition.A dynamic programming approach was developed for computing fixed-length walk kernels.

6 Experimental Study … 6.3 Graph Kernels

The experimental study evaluates state-of-the-art graph kernels against simple histogram baselines across diverse graph datasets. It examines expressivity, nonlinear decision boundaries, accuracy, prediction agreement, and continuous attributes using carefully specified classification protocols and kernel implementations.

  • 6 Experimental Study: The study compares state-of-the-art graph kernels with vertex- and edge-label histogram baselines while investigating expressivity, nonlinear boundaries, accuracy, agreement, and continuous attributes.These questions organize the experimental evaluation across several aspects of graph-kernel performance.
  • 6.1 Methods: Classification experiments use LIBSVM’s C-SVM with nested 10-fold cross-validation for selecting kernel and regularization parameters.Parameter selection is performed within the training data for each outer fold.
  • 6.1.2 Complete Graph Kernels: Label completeness measures whether a kernel distinguishes graphs from different classes, and the kernel metric tests feature-map equality without explicitly constructing feature vectors.The label completeness ratio is the fraction of graphs distinguishable from all differently labeled graphs in a dataset.
  • 6.1.2 Complete Graph Kernels: Label completeness limits a kernel’s dataset accuracy, but complete kernels need not yield high accuracy or linearly separable representations.An additional high-dimensional mapping may improve accuracy when feature vectors are not linearly separable.
  • 6.1.3 Non-linear Decision Boundaries in the Feature Space of Graph Kernels: The evaluation applies a Gaussian RBF kernel to graph-kernel metrics, replacing Euclidean distance with the kernel-induced metric.The metric can be computed from feature vectors or through the kernel trick, with σ selected experimentally.
  • 6.2 Datasets: The datasets span molecular and macromolecular graphs, including new Tox21-derived collections containing more than 7000 graphs each.The datasets were made publicly available and include labels representing biological properties or macromolecular characteristics.
  • 6.3 Graph Kernels: The graph-kernel comparison includes VL, EL, WL, WL-OA, GL3, SP, MK-IL, MK-L, PM, DeepGK, DBR, and Prop.WL and WL-OA use cross-validated refinement counts, while MK kernels lack hyperparameters and PM uses d = 6 and L = 3.
  • 6.3 Graph Kernels: For continuous vertex attributes, the study compares shortest-path, GraphHopper, GraphInvariant, P2K, and Hash Graph kernels with specified attribute and iteration settings.The Hash Graph kernel uses 20 iterations generally and 100 for the Sythnie datasets; DeepGK parameters were not searched.

6.4 Results and Discussion · 6.5 A practitioner’s guide

The experiments compare graph kernels’ expressivity, accuracy, agreement, and handling of continuous attributes, while the practitioner’s guide recommends kernels according to dataset properties, computational constraints, and available representations.

  • 6.4 Results and Discussion: SP and WL_h kernels with h≥2 achieve completeness ratios close to one on most datasets, whereas VL, EL, and GL3 are weaker.WL-OA matches WL and is omitted from the completeness-ratio figure.
  • 6.4 Results and Discussion: The Gaussian RBF kernel drastically improves VL and EL accuracy on several datasets and improves GL3 on average, but usually changes WL and WL-OA only slightly.Optimizing the RBF parameter σ can be computationally demanding, especially alongside graph-kernel parameters.
  • 6.4 Results and Discussion: WL and WL-OA provide the best accuracy on most datasets, with WL-OA highest on average; the authors recommend WL-OA for small or medium datasets and WL for large datasets.They pair these choices with kernel SVMs and linear SVMs, respectively.
  • 6.4 Results and Discussion: Hash graph kernel variants achieve state-of-the-art results on every dataset except FRANKENSTEIN, where high-dimensional vertex attributes are difficult to compare with hash functions.The results are consistent with theoretical approximations of established graph kernels using a small number of iterations.
  • 6.5 A practitioner’s guide: The practitioner’s guide prioritizes kernels based on vertex attributes, graph size and density, global structure, and the number of graphs available.Because kernel expressivity is difficult to assess a priori, suitability depends on the problem at hand.
  • 6.5 A practitioner’s guide: For very large graphs, approximations can reduce computational cost, while simple edge-label and vertex-label kernels provide baselines but ignore graph structure.The guide also highlights specialized kernels for global structure and cautions that label-kernel multiplication misses dependencies between labels and structure.
  • 6.5 A practitioner’s guide: For large datasets, explicit feature representations such as WL, GL, and subtree kernels avoid full N×N kernel-matrix computation and are recommended starting points.Vertex label, Weisfeiler-Lehman, and graphlet kernels admit d-dimensional representations with d≪N.

7 Conclusion

The survey provides an overview of graph kernel literature and offers recommendations intended to support graph-kernel design, graph classification, and practical applications. It also aims to stimulate further progress and assist practitioners solving real-world problems.

  • The survey gives an overview of the graph kernel literature.
  • The survey hopes to spark further progress in graph kernel design and graph classification.
  • Its recommendations are justified based on the graph kernel literature.
  • The article aims to support practitioners applying graph classification methods to real-world problems.
Loading 1903.11835v2…