Graph Kernels: State-of-the-Art and Future Challenges

• Graph representations describe entities and relationships with metadata and are used across fields including chemoinformatics, biology, neuroscience, and social network analysis.Their flexibility also encompasses vectorial and other structured data types.Source: §1 · p. 3
• Graphs' discrete structure and combinatorial number of substructures make graph isomorphism and subgraph isomorphism difficult, requiring methods to balance tractability with information use.No polynomial-time algorithm is known for graph isomorphism, while subgraph isomorphism is NP-complete.Source: §1 · p. 4
• Hand-engineered topological descriptors embed graphs as fixed-dimensional vectors but can require application-specific expertise and limit captured information.Their dimensionality may also be kept low to obtain parsimonious representations.Source: §1 · p. 4
• Graph kernels quantify pairwise graph similarity through positive-definite kernels and implicit feature-space inner products, with this review using the term for kernels between graphs.The term is distinguished from kernels between nodes within a single graph.Source: §1 · p. 4
• The review provides in-depth kernel descriptions, a conceptual categorization, empirical comparisons, and discussion of trends and future challenges.It also gathers, reproduces, and analyzes empirical results across application domains.Source: §1 · p. 5
• The review proceeds from graph theory and kernel concepts to kernel descriptions and empirical evaluation, then closes with future trends and open challenges.It also discusses kernel applicability and requirements for benchmark datasets.Source: §1 · p. 5

2.1 A primer in graph theory

• Graphs can carry node or edge labels and attributes, and be analyzed through walks, cycles, distances, neighborhoods, and Laplacians; detecting a Hamiltonian cycle is NP-complete.The primer also introduces graph representations including adjacency matrices and k-hop neighborhoods.Source: §2.1 · pp. 6–9

2.2.1 The graph isomorphism problem

• Isomorphism gives a binary similarity through an adjacency-preserving vertex bijection, but observational noise makes it brittle and its complexity limits scalability; no polynomial-time general algorithm is known.The problem is not known to be NP-complete, and a quasi-polynomial algorithm has been claimed.Source: §2.2.1 · pp. 10–11

2.2.2 Graph edit distances

• Graph edit distance minimizes the costs of vertex or edge insertions, deletions, and substitutions, enabling domain-specific costs but requiring careful parameterization and generally NP-complete computation.Efficient polynomial-time algorithms are known for some graph classes, such as trees.Source: §2.2.2 · p. 11

2.2.3 Invariants and topological descriptors

• Descriptors and invariants enable vector-based machine learning, but simple examples can conflate nonisomorphic graphs, while complete invariants require exponential time; graph kernels seek a middle ground.The Wiener index and Laplacian spectrum are examples of descriptors that may be identical for nonisomorphic graphs.Source: §2.2.3 · pp. 12–13

2.3 A brief introduction to kernel methods

• Kernel methods model inputs from arbitrary sets through feature maps and inner products, allowing linear models to operate on potentially nonlinear representations without explicitly constructing the feature vectors.This implicit computation is the kernel trick and supports feature spaces of arbitrary dimensionality, provided the learning algorithm uses inner products.Source: §2.3 · pp. 13–14

2.3.1 Fundamental concepts

• A kernel is a function that equals the inner product of feature-map representations in a Hilbert space, which can be defined implicitly through the kernel itself.Kernel design can encode a task-relevant notion of similarity while kernel theory provides principled control of model complexity.Source: §2.3.1 · pp. 14–15, §2.3 · p. 14
• Kernel functions are central to kernel methods, whose research seeks task-specific kernels with favorable properties such as high expressivity and low computational cost.Source: §2.3.1 · p. 15

2.3.2 Characterisation of kernels

• A function is a valid kernel if and only if it is symmetric and positive definite, equivalent to being a reproducing kernel for a unique RKHS.The Moore–Aronszajn theorem establishes this equivalence.Source: §2.3.2 · p. 16

2.3.3 Examples of kernels

• On Euclidean inputs, kernel methods let linear models capture nonlinear patterns; the Dirac delta, polynomial, and RBF kernels illustrate simple, widely used choices.The Dirac delta kernel also applies to categorical and structured data, including graphs, and serves as a building block; kernels are closed under sums and positive scalar multiplication.Source: §2.3.3 · pp. 16–17

2.3.4 R-convolution kernels

• R-convolution constructs valid graph kernels from substructure decompositions by combining base kernels, with finite decomposition fibres ensuring kernel existence.Parts may be subgraphs or vertex subsets; examples of substructure sets include all nodes or all shortest paths.Source: §2.3.4 · pp. 17–18

3 Kernels for graph-structured data

• Complete graph kernels are at least as hard to compute as graph isomorphism, so polynomial-time kernels must leave some distinct graphs indistinguishable.The passage notes that limited-capacity function classes may nevertheless support generalization from finite data sets.Source: §3 · p. 19
• Graph-kernel design is a form of feature engineering, exploring graph substructures and base kernels within the flexible R-convolution framework.These choices investigate which graph aspects define useful similarity for different statistical learning problems.Source: §3 · p. 19
• State-of-the-art graph kernels are orders of magnitude faster than the earliest kernels and perform better in many unsupervised and supervised learning tasks.The chapter attributes this progress to both computational-efficiency contributions and kernel-design advances.Source: §3 · p. 20
• Many kernels restrict graph inputs, especially by excluding attributes or supporting labels but not arbitrary continuous attributes.Developing kernels for continuous attributes or adapting existing kernels to them has motivated further work.Source: §3 · p. 20
• Many R-convolution kernels use simple instantiations such as Dirac kernels, whose exact substructure matching can cause diagonal dominance and affect generalization performance.Recent developments seek to extend the framework without compromising computational tractability.Source: §3 · p. 20
• The chapter groups kernels as bag of structures, information propagation, or framework extensions, while noting that specific information support and complexity vary within each category.Its overview materials summarize graph type, node and edge labels or attributes, and evaluation complexity; the taxonomy is not a ranking of expressivity.Source: §3 · pp. 20–21, Figure 3.1 · p. 22, Table 3.1 · p. 23
• Kernel choice can consider graph direction, available node and edge information, computational efficiency, relevant substructures, and empirical benchmark performance.The chapter provides an initial property-based reference and reserves a more comprehensive choice guide for its later experimental analysis.Source: §3 · p. 21

3.1.1 Graph kernels based only on nodes

• Node-only kernels ignore edges, providing a baseline for topology’s importance; with explicit node features, the node histogram kernel counts label occurrences and has complexity O(ndv).The all node-pairs kernel sums similarities between node attributes, while the histogram implementation is especially efficient when its feature dimension dv is small.Source: §3.1.1 · p. 25, §3.1.1.1 · p. 26, §3.1.1.2 · pp. 26–27

3.1.2 Graph kernels based only on edges

• Edge-only kernels capture direct relationships but ignore indirect ones; the edge histogram kernel counts edge-label occurrences and has complexity O(mde).Node-only and edge-only kernels can be combined as a baseline using node and/or edge attributes while ignoring other topology.Source: §3.1.2 · p. 27, §3.1.2.1 · p. 28, §3.1.2.2 · p. 29

3.1.3 Graph kernels based on paths

• All path-pairs comparison is NP-hard, so path kernels commonly use shortest paths, which can be computed in polynomial time and capture relations between non-adjacent nodes.The shortest-path kernel compares shortest paths using kernels on endpoint nodes and path lengths, with flexibility to incorporate attributes.Source: §3.1.3 · p. 29, §3.1.3.1 · p. 30

3.1.3.2 GraphHopper kernel

• GraphHopper was developed to address shortest-path kernel runtime; it compares nodes encountered along shortest paths and decomposes into a weighted sum of node kernels.It applies to undirected graphs with edge weights and optional node attributes when comparison kernels are available; its average complexity estimate assumes node-kernel time O(d).Source: §3.1.3.2 · pp. 31–32

3.1.4.1 Subtree pattern kernel

• The subtree pattern kernel compares neighborhood matchings up to height h, permits repeated nodes and edges, and is computationally nontrivial.Its matching-based approach provided a foundation for later kernels, including an extension that controls the effect of more complex subtree patterns.Source: §3.1.4.1 · pp. 32–33

3.1.4.2 Cyclic pattern kernel

• Horváth et al. (2004) proposed a cyclic pattern kernel that captures diversity of cycle and tree patterns by comparing their sets; computation is NP-hard.A variant has an upper-bounded runtime when graphs in the dataset have a bounded number of simple cycles, with graphs exceeding the bound disregarded.Source: §3.1.4.2 · pp. 33–34

3.1.4.3 Graph edit distance kernels

• Graph edit distance kernels select graph prototypes from the dataset and represent each graph by its edit distances to them, enabling feature-based or kernel methods for attributed graphs.Modifying edit costs can accommodate graph types such as directed graphs and graphs with continuous attributes.Source: §3.1.4.3 · pp. 35–36
• A spanning prototype scheme builds a diverse set by repeatedly adding the graph farthest from its nearest selected prototype; prototype selection can be cross-validated.Bunke and Riesen (2007) describe the selection scheme, with prototype choice treated as an algorithm hyperparameter for real-world applications.Source: §3.1.4.3 · p. 36
• Fast graph-edit-distance algorithms determine feature-vector creation costs, while Bai et al. (2018)'s learned approximation varies in quality by dataset, leaving a need for further approximations.Riesen (2015) provides a detailed introduction to state-of-the-art graph-edit-distance algorithms.Source: §3.1.4.3 · p. 37

3.1.4.4 Graphlet kernel

• The graphlet kernel counts occurrences of fixed-size, connectivity-only subgraphs to form a k-spectrum, then compares spectra with a linear kernel.The enumeration ignores labels and attributes; spectra are typically normalized by dividing counts by the total number of graphlets in each graph.Source: Figure 3.6 · p. 37, §3.1.4.4 · p. 38
• Because arbitrary graphlet enumeration grows exponentially with graphlet size, Shervashidze et al. (2009) suggest computing only k ∈ {3, 4, 5} and combining kernels across sizes.The provided passage identifies enumeration as the computational bottleneck; its complexity expression is incomplete in the supplied text.Source: §3.1.4.4 · p. 38
• Kondor et al. (2009) extend graphlet kernels to account for relative graphlet positions and incorporate node and edge attributes.Source: §3.1.4.4 · p. 38

3.2 Information propagation

• Walks and spectral methods model graph-based information diffusion, while iterative label refinement propagates information between neighboring nodes.Source: §3.2 · p. 39

3.2.1 Graph kernels based on walks

• Walks allow polynomial-time counting of length-k paths and capture higher-order node relations, but repeated visits cause tottering and small convergence-safe λ can cause halting.Truncating the random-walk series is one proposed way to ameliorate these issues.Source: §3.2.1 · p. 39

3.2.1.1 Direct product graph kernel

• The direct product graph aligns matching node and edge labels so its walks correspond one-to-one with pairs of matching label-sequence walks in the input graphs.Counting walks in the product graph reduces matching-walk computation to polynomial-time matrix multiplication.Source: §3.2.1.1 · p. 41

3.2.1.2 Marginalized random walk kernel

• Marginalized random-walk kernels average a nonnegative kernel on attribute sequences over walk probabilities, extending the framework to continuous node and edge attributes.Under restrictions on the sequence kernel, matrix inversion computes it with the same worst-case complexity as the direct product graph kernel.Source: §3.2.1.2 · p. 42

3.2.1.3 Fast computation of walk-based kernels

• Vishwanathan et al.’s framework covers a broad family of walk kernels when attribute feature maps are explicit, exploiting Kronecker structure for computation.RetGK adds return-probability information and can handle attributed and non-attributed graphs within one framework.Source: §3.2.1.3 · p. 43

3.2.1.4 Continuous-time quantum walk kernel

• The quantum-walk treatment assumes unlabelled, undirected graphs and compares their density operators through von Neumann entropy and a scaled Jensen–Shannon kernel.Its decay factor limits domination by large values; related quantum-walk methods have also been applied to image edge detection.Source: §3.2.1.4 · pp. 44–46

3.2.2 Graph kernels based on iterative label refinement

• Iterative label-refinement kernels can be orders of magnitude faster on sufficiently large graphs, achieve state-of-the-art performance across many supervised tasks, and precede most modern graph neural networks.Source: §3.2.2 · p. 47

3.2.2.1 The Weisfeiler–Lehman kernel framework

• The Weisfeiler–Lehman framework uses perfect hashing to distinguish neighborhoods differing by one node, with linear-edge-time relabeling and multiscale label-count kernels.The subtree kernel compares label-count feature vectors by their inner product and can be extended to include edge labels.Source: §3.2.2.1 · pp. 48–50

3.2.2.2 Neighbourhood hash kernel

• Hido and Kashima (2009)’s binary-hash kernel is faster and more memory-efficient than Weisfeiler–Lehman but risks collisions; count-sensitive hashing preserves multiplicities at a sorting cost.The simple scheme’s XOR hashing retains only whether each label count is even or odd.Source: §3.2.2.2 · pp. 51–52

3.2.2.3 Fast Neighbourhood Subgraph Pairwise Distance Kernel

• Costa and De Grave (2010) compare hashed representations of induced radius-r subgraphs rooted at node pairs within distance d, with linear-in-node complexity when r and d are small.The method uses a proxy rather than testing subgraph isomorphism directly.Source: §3.2.2.3 · pp. 53–54

3.2.2.4 Hadamard code kernel

• Kataoka and Inokuchi (2016) propose Hadamard matrices for hashing intended to retain simple-neighborhood-hash efficiency while reducing collisions.A Hadamard matrix has mutually orthogonal rows, whose entries are −1 or 1.Source: §3.2.2.4 · p. 55
• Hadamard codes aggregate orthogonal label codewords into fixed-length bit strings without sorting, matching count-sensitive neighborhood hashing’s predictive performance.Their asymptotic complexity matches that of the neighborhood hash kernel and Weisfeiler–Lehman framework, while they run faster than the count-sensitive neighborhood hash version.Source: §3.2.2.4 · pp. 55–57

3.2.2.5 Propagation kernels

• Propagation kernels extend iterative refinement to continuous or partially missing attributes, using adaptable schemes and node kernels, with complexity comparable to Weisfeiler–Lehman and neighborhood hash kernels.Schemes include diffusion for labelled or unlabelled graphs, adaptations for partially labelled graphs, and Gaussian-mixture parameter updates for continuous attributes.Source: §3.2.2.5 · pp. 57, 59

3.2.2.6 Message passing graph kernels

• Message-passing kernels handle continuous attributes through graph-neural-network-inspired updates defined by auxiliary kernels rather than neural-network transformations (Nikolentzos and Vazirgiannis, 2018).With a pre-calculated hierarchy, Nyström evaluation of the optimal-assignment variant can run in O(|V|); the framework includes the Weisfeiler–Lehman subtree kernel, though the survey’s formulation is computationally more efficient.Source: §3.2.2.6 · pp. 60–61

3.2.3 Graph kernels based on spectral theory

• Small-eigenvalue Laplacian eigenvectors describe smoothly varying node functions, and Laplacian properties have informed kernels connected to random walks and diffusion.The graph Laplacian is described as a discretized differential operator.Source: §3.2.3 · p. 62
• Extending Laplacian approaches to graph comparison raises challenges of isomorphism invariance, node attributes, and capturing localized structure beyond global properties.Source: §3.2.3 · p. 62

3.2.3.1 Multiscale Laplacian graph kernel

• The generalized feature-space Laplacian kernel uses a base kernel on a shared vertex space to incorporate node attributes while remaining invariant to vertex permutations.Its construction uses transformed graph Laplacians and a regularization factor.Source: §3.2.3.1 · pp. 63–64
• The feature-space Laplacian kernel combines spectral information with node attributes and compares graph-associated probability densities using the Bhattacharyya kernel.Its Gaussian Markov random field construction incorporates graph structure and is invariant to vertex reorderings.Source: §3.2.3.1 · p. 63
• The multiscale kernel recursively compares subgraphs in a nested neighborhood hierarchy, using the base kernel at the first stage and the preceding kernel at higher stages.The hierarchy can use k-hop neighborhoods, so each scale’s kernel compares nodes through their neighborhoods at the preceding scale.Source: §3.2.3.1 · pp. 63–65

3.3.1 Extending graph kernels to handle continuous attributes

• Three generic approaches extend many graph kernels, including those limited to categorical attributes, to graphs with continuous node or edge attributes.The approaches are subgraph matching kernels, graph invariant kernels, and hash graph kernels.Source: §3.3.1 · p. 66

3.3.1.2 Graph invariant kernel framework

• The graph invariant framework combines node kernels that accommodate continuous attributes but miss topology with weights computed using existing graph kernels to capture higher-order structure.The framework can adapt kernels such as the Weisfeiler–Lehman graph kernel to continuous attributes.Source: §3.3.1 · p. 66, §3.3.1.2 · p. 68

3.3.1.1 Subgraph matching kernels

• Subgraph matching kernels weight common subgraph isomorphisms, found via maximal cliques in the direct product graph, using node and edge label or attribute kernels.Continuous attributes can be incorporated by multiplying label kernels by attribute kernels, such as Brownian bridge kernels for nodes or triangular kernels for edges.Source: §3.3.1.1 · pp. 66–67

3.3.1.3 Hash graph kernels

• Hash graph kernels average a discrete base kernel's similarities across randomly hashed discretizations of continuous attributes, adapting arbitrary kernels that support discrete attributes.The framework's runtime depends on the base kernel, the number of hash functions, and the cost of evaluating one hash function.Source: §3.3.1.3 · p. 70

3.3.2 Beyond simple instances of the R-convolution framework

• R-convolution kernels can produce very high-dimensional feature maps with many irrelevant features, causing diagonal dominance and overfitting; their lack of adaptivity motivates alternatives.When large annotated graph datasets are available, graph neural networks can learn feature maps end-to-end for a task.Source: §3.3.2 · p. 71

3.3.2.1 Weighted decomposition kernels

• Weighted decomposition kernels compare selectors exactly and contexts with attribute-based probability-distribution kernels, using context similarity to weight selector matches.The choice of selector and context depends on the application; one example uses a source vertex as selector and its fixed-radius neighborhood as context.Source: §3.3.2 · p. 72, §3.3.2.1 · p. 73

3.3.2.2 Optimal assignment kernels

• Optimal assignment kernels match each substructure to one partner, alleviating diagonal dominance, but positive semidefiniteness is guaranteed only for restricted base kernels, including strong kernels arising from hierarchical partitions.The original optimal assignment kernel is not guaranteed to be positive semidefinite for all substructure-kernel choices.Source: §3.3.2 · p. 72, §3.3.2.2 · p. 74
• The Weisfeiler–Lehman optimal assignment kernel compares compressed-subtree labels hierarchically using histogram intersection, outperforms regular vertex- and edge-label kernels, and runs in O(hm) time [Kriege et al., 2016].Here, m is the maximum number of edges; the hierarchy represents vertices by their paths through Weisfeiler–Lehman labels.Source: Figure 3.11 · p. 75, §3.3.2.2 · p. 76

3.3.2.3 Deep graph kernels

• Yanardag and Vishwanathan (2015) reweight graph-kernel substructures using embeddings learned from their co-occurrence contexts, with slightly higher classification accuracy but greater computational cost.They define co-occurrence relationships for shortest-path, graphlet, and Weisfeiler–Lehman subtree kernels; the extra embedding calculation increases complexity.Source: §3.3.2.3 · pp. 76–77

3.3.2.4 Core based kernel framework

• Nikolentzos et al. (2018a) compare nested k-core subgraphs with a base kernel to capture similarity across graph scales, improving performance over the base kernels.A k-core is a maximal subgraph in which every vertex has degree at least k; the decomposition is a nested sequence, and the framework can use shortest-path or Weisfeiler–Lehman kernels.Source: §3.3.2.4 · pp. 77–78

3.4 Conclusion

• Many graph kernels compare graphs by enumerating substructures such as shortest paths or subgraphs and measuring their co-occurrence.The chapter identifies this as one of the field’s most common themes.Source: §3.4 · p. 78
• Recent work also examines topological graph attributes and optimal-transport approaches such as Wasserstein distances, which the review omits in detail for brevity.Source: §3.4 · pp. 78–79
• The review discusses practical performance similarities among kernels to help readers select one for a given application.Source: §3.4 · p. 79

4 Experimental evaluation of graph kernels

• The evaluation uses numerous benchmark data sets and a fair comparative setup to analyse kernel behaviour and inform practical kernel choice and future directions.Source: §4 · p. 80

4.1 Data sets

• The benchmark graphs tend to be sparse, and node or edge attributes are under-represented; 27 data sets have node labels and 12 have edge labels.Source: §4.1 · p. 80
• Missing labels are generated from node degrees or incident-node labels, and label or attribute availability may limit which kernels apply.Source: §4.1 · pp. 80–81
• The source collection contains more than 50 graph data sets, while the section analyzes 41; Tox_21 collections and FIRSTMM_DB are excluded because of computational scale and training-procedure constraints, respectively.The Tox_21 collections preclude running a sufficiently large number of kernels, while FIRSTMM_DB is too small for the training procedure.Source: §4.1 · pp. 80–81

4.1.1 Data set categorisation

• The data sets are grouped into social networks, small molecules, bioinformatics, computer vision, and synthetic graphs; social-network graphs are unlabelled, while small-molecule graphs have labels or attributes.Some small-molecule data sets are fully connected, which presents a challenge for neighbourhood-aggregation methods.Source: §4.1.1 · p. 81
• Bioinformatics graphs have node labels but lack edge information, computer-vision graphs vary widely in size and attributes, and synthetic graphs have node attributes by design.Source: §4.1.1 · pp. 81–82

4.2 Experimental setup

• The setup has two phases: computing kernel matrices for each graph kernel, then training classifiers from those matrices.Source: §4.2 · p. 82

4.2.1 Inclusion criteria

• The review selects openly available implementations to represent every Chapter 3 kernel category; data set sizes vary, but most graphs are comparatively small.Implementations come from graphkernels, graKel, and other sources.Source: §4.2.1 · p. 82, Table 4.1 · p. 83

4.2.2 Kernel matrix computation

• For each kernel, full pairwise matrices are computed across parameter combinations for hyperparameter selection, subject to time limits and implementation capabilities.Suggested parameter ranges were sometimes reduced when they could not be run within 120 hours; available implementations did not always support all graph information.Source: §4.2.2 · pp. 85–86

4.2.3 Training procedure

• Nested stratified 10-fold cross-validation uses an inner 5-fold grid search and is repeated ten times; normalization is tunable but rarely needed for good performance.A precomputed-kernel SVM is used, with C selected from 10^-3 to 10^3.Source: §4.2.3 · pp. 87–88

4.2.4 Training environment

• Each kernel receives 120 hours for matrix computation and 120 hours for hyperparameter search and fitting, with 128 GB RAM; runs may be marked OOM, OOT, or NA.SVM fitting is capped at 500 iterations.Source: §4.2.4 · p. 88

4.2.5 Evaluation procedure

• For multi-class data sets, the review reports macro-averaged AUROC alongside accuracy, and uses macro-averaged AUROC when comparing kernels across data sets.AUROC is calculated one-versus-rest and averaged across classes.Source: §4.2.5 · p. 90

4.3 Classification performance

• Neighborhood-propagating kernels tend to use multiple iterations to reach their final accuracy, supporting analysis of graphs at multiple scales.Figure 4.3 summarizes the mean iteration depth across training folds.Source: §4.3 · p. 91, Figure 4.3 · p. 91
• Weisfeiler–Lehman-based kernels outperform other kernels on 21 of 41 data sets, led by MP on 10, WL-OA on 6, HGK-WL on 4, and WL subtree on 1.The comparison is based on the empirical accuracy results.Source: §4.3 · pp. 90–91, Table 4.5 · p. 93
• A Monte Carlo ranking based on simulated accuracy distributions reinforces Weisfeiler–Lehman approaches’ overall strength, while vertex histogram kernels are not among the worst-performing methods.The simulation treats accuracy values as normally distributed using each kernel’s mean and standard deviation.Source: §4.3 · p. 98, Table 4.8 · p. 98

4.3.1 Breakdown of results per data set type

• For data-set types i, ii, and iii, WL subtree or WL optimal assignment appear most suitable; MP is an alternative at higher complexity, while vertex histograms perform suitably on type vi.Type vi comprises data sets with node labels and edge information but no node attributes.Source: §4.3.1 · p. 99, Table 4.9 · p. 101
• Performance differs by data-set type: fully labelled graphs show more consistent results, while full-node-information and node-labelled sets show kernel divisions.For node-labelled sets, the AUROC distributions also have large variances, and the overall mean-accuracy ranking is not evident in mean AUROC distributions.Source: Figure 4.4 · p. 100, §4.3.1 · p. 101

4.3.2 Performance of histogram kernels

• Pure vertex- or edge-label histogram kernels outperform all others on 4 of 41 data sets, with vertex histograms best on 3.The authors suggest that graph structure is not needed for good predictive performance on some benchmark sets.Source: §4.3.2 · p. 101

4.3.2.1 Distribution analysis

• On 16 of 41 data sets, the relative accuracy difference between vertex histogram and the best kernel is below 10%, so more complex kernels do not always yield a large accuracy gain.The difference is calculated relative to the best-performing graph kernel for each data set and displayed as a histogram.Source: §4.3.2.1 · p. 102, Figure 4.5 · p. 102

4.3.2.2 Visual analysis

• In the scatterplots, several data sets—including some without node labels and some feature-rich sets—sit well above the diagonal, while other classes lie closer; vertex histograms provide a useful baseline for the latter.The plots compare vertex-histogram performance with the best kernel and color points by data-set type; the accuracy plot’s relative distances should not be interpreted as similarities between data sets.Source: §4.3.2.2 · p. 103, Figure 4.6 · p. 104, Figure 4.7 · p. 105

4.4.1 Accuracies and standard deviations

• Mean accuracies and standard deviations across cross-validation repetitions show when fold variation makes kernels hard to distinguish and when gaps separate their performance.The authors caution that low overlap may result from different dataset properties, including small size or difficulty, rather than clear kernel superiority.Source: §4.4.1 · pp. 107, 109, Figure 4.9 · p. 108
• Most datasets have 0–50% pairwise error-bar overlaps, while REDDIT-MULTI-12K has none and Peking_1 has the most; low overlap can slightly reduce statistical power.A low overlap count can also reflect an easy, small, or generally difficult dataset, so overlap alone does not settle dataset suitability.Source: §4.4.1 · pp. 107, 109, Figure 4.9 · p. 108, Figure 4.10 · p. 109

4.4.2 Boxplot analysis

• Accuracy boxplots assess how similarly kernels perform within each dataset, but cannot establish whether a kernel is suitable for classification because they omit random-classifier baselines.The number of values can vary because kernels that did not finish computing were excluded.Source: Figure 4.11 · p. 110, §4.4.2 · p. 111

4.4.2.1 High-variance data sets

• High-variance datasets include COIL-RAG, COIL-DEL, ENZYMES, Letter-high, Letter-low, Letter-med, Mutagenicity, NCI1, NCI109, and SYNTHETICnew.Most have node or edge attributes, and the authors connect this group to weaker vertex-histogram performance and the need for kernels that handle attributes and scale well.Source: §4.4.2.1 · p. 111

4.4.2.3 Summarising differences in accuracy

• For AIDS, DHFR_MD, KKI, OHSU, PROTEINS, PROTEINS_full, PTC_FM, PTC_MR, and Peking_1, kernel accuracy differences are below 10%, with small standard deviations.The authors say these datasets can help compare kernel types, but superiority claims should also use datasets that reveal generalisation performance.Source: §4.4.2.3 · p. 112, Table 4.10 · p. 113

4.4.3 Estimating maximum predictive performance

• The conservative estimate counts graphs never classified correctly by any included kernel on any split; unlabelled IMDB-MULTI, REDDIT-MULTI-12, and REDDIT-MULTI-5k are exceptions to the generally low fractions.The authors suggest duplicates or quasi-isomorphic graphs with different labels may explain these cases, and caution that such graphs could reflect either data issues or limits of the kernels tested.Source: §4.4.3 · p. 114, §4.4.3.1 · p. 114, Figure 4.12 · p. 115

4.4.4 Consequences

• AIDS, Letter-low, Synthie, and SYNTHETICnew are within 0.5% of their estimated performance upper limit and should not be used in formal kernel comparisons.The authors suggest excluding Letter-low, Letter-med, and Letter-high from analyses of node-attributed datasets; Synthie is considered solved, while COIL-DEL and FRANKENSTEIN warrant caution when used alone.Source: §4.4.3.2 · p. 117, §4.4.4.1 · p. 118, §4.4.4.2 · p. 118

4.4.3.2 Gauging the difficulty of all data sets

• The best kernel comes within 5% of the estimated upper limit for COIL-RAG and Letter-med, but a remaining gap suggests future kernels may improve performance by a few points.Unlabelled class i datasets are challenging by this measure; class vi datasets also appear to have hidden complexity.Source: §4.4.3.2 · pp. 117–118

4.5.1 Critical difference analysis

• The critical-difference analysis finds no significant performance difference among MP, WL-OA, WL, and both Hash Graph Kernel variants; the conservative test limits claims to individual pairs.Among those kernels, only MP versus the vertex histogram kernel and WL-OA versus the vertex histogram kernel show significant differences; the authors note limited statistical power.Source: §4.5.1 · pp. 119–120, Figure 4.14 · p. 119

4.5.2 Grouping based on predictions

• Prediction profiles are compared with Hamming distance and embedded in two dimensions, but show no obvious groups and are insufficient on their own to pick a kernel.MP predicts labels differently from other kernels, while HGK-WL and HGK-SP are relatively close in the embedding.Source: §4.5.2 · p. 120, Figure 4.15 · p. 121

4.5.3 Grouping based on hierarchical clustering

• Hierarchical clustering provides multiple-level views of kernel similarities, using either accuracies or predicted labels.The section presents these as distinct bases for comparing kernels.Source: §4.5.3 · p. 121

4.5.3.1 Clustering based on AUROC values

• Clustering AUROC values groups WL-OA, MP, WL, and HGK-WL, indicating similar performance across datasets and offering a coarse preselection.A more precise analysis would also incorporate predictions.Source: §4.5.3.1 · p. 121, Figure 4.16 · p. 122

4.5.3.2 Clustering based on Hamming distance

• Clustering prediction Hamming distances places WL with MP and HGK-SP with HGK-WL, but the higher-level clusters are less informative.The distance reflects similarity of predictions across datasets and folds.Source: §4.5.3.2 · p. 122

4.6 Choosing a graph kernel

• The recommendations distinguish unlimited-resource and restricted-resource settings, drawing mainly on per-type rankings and the kernel groupings.Runtime comparisons are not fair because implementations use different programming languages.Source: §4.6 · pp. 122–123

4.6.1 Scenario 1: unlimited computational resources

• With unlimited resources, select by graph density and predictive performance; for complete graphs, consider histogram-based kernels or a shortest-path Hash Graph Kernel instead of Weisfeiler–Lehman propagation.The suggested density threshold for calling a graph dense is greater than 0.5, though the authors leave the definition open.Source: §4.6.1 · p. 123, Figure 4.17 · p. 123

4.6.2 Scenario 2: limited computational resources

• With restricted resources, the recommended flowchart accounts for dataset type, runtime requirements, and parameter choices, listing kernels from fewer to more hyperparameters.Fewer hyperparameters require less complex search strategies, which may be more feasible when resources are limited.Source: §4.6.2 · p. 124, Figure 4.18 · p. 124

4.7 Conclusion

• The chapter assesses benchmark-dataset difficulty and suitability and recommends how datasets should be used.Source: §4.7 · p. 125
• The comprehensive performance comparison places graph kernels based on some form of Weisfeiler–Lehman among the best performers.Source: §4.7 · p. 125
• After comparing grouping strategies based on statistical measures and clustering, the chapter gives guidance for choosing kernels on new datasets.Source: §4.7 · p. 125

5.1.1 Limitations of benchmark data sets

• Current benchmarks often lack informative topology, provenance, difficulty, and feature or dataset diversity, prompting calls for new datasets with documented construction choices.The review recommends developing synthetic and real-world benchmarks and recording generation parameters and edge or vertex pre-selection choices.Source: §5.1.1 · pp. 126–127

5.1.2 Challenges in graph kernels usage

• Kernel comparisons should tune competitive methods to include simple label statistics and use histogram baselines, while benchmark difficulty can be assessed against vertex-histogram performance and error overlap.A vertex histogram outperforming more complex kernels may indicate that topology is unnecessary for classification; similar performance calls for examining which graphs each method misclassifies to assess whether a dataset is already solved.Source: §5.1.1 · pp. 127–128, §5.1.2 · pp. 128–129

5.1.3 Reproducibility and software availability

• Reproducible comparisons require shared experimental protocols and benchmark splits, published code and data splits, and clear reporting of competitor setups.The review notes that inconsistent folds, splits, code availability, and benchmark selection can yield inconclusive results or incorrect performance claims; public packages can also address software and language heterogeneity.Source: §5.1.3 · pp. 129–130

5.1.4 Scalability

• Some graph kernels remain inefficient even on high-performance clusters, so the review recommends continued efficiency work through parallelization and approximation strategies.Examples include Nyström approximation for message-passing kernels, less restrictive hashing for hash kernels, and probabilistic data structures such as Bloom filters.Source: §5.1.4 · pp. 130–131

5.2.1.1 Ensembles of graph kernels

• In most data sets, majority-vote ensembles underperformed the best individual kernel, improving performance on only five: COX2_MD, DD, ENZYMES, PROTEINS, and PROTEINS_full.The simple vote does not weight kernels according to task-relevant specialization; confidence-aware or more complex ensemble methods are suggested, although computational complexity remains a major obstacle.Source: §5.2.1.1 · pp. 131–132, Figure 5.1 · p. 132

5.2.1.2 Alternatives to the R-convolution framework

• Alternatives to R-convolution aggregation could capture interactions among substructures, while topological descriptors and improved graph-level READOUT schemes offer further directions.WL-OA and WWL are positive semi-definite for categorical node labels, but WWL’s positive definiteness on continuous node-attributed graphs remains open; topological features have improved kernels, and attention or pooling are proposed for READOUT.Source: §5.2.1.2 · pp. 133–134

5.2.2 Link between graph kernels and graph neural networks

• GNNs propagate neighborhood features iteratively, while Weisfeiler–Lehman uses perfect hashing rather than learnable smooth updates and is at least as expressive but not end-to-end task-tunable.The simplest Weisfeiler–Lehman READOUT concatenates unnormalized node-label histograms across propagation steps; GNNs offer a broader range of graph-level representations.Source: §5.2.2 · pp. 134–135

5.2.2.1 Link to the graph isomorphism problem

• Xu et al. (2019) conclude that GNNs are at most as powerful as the WL test, and propose GIN with comparable discriminative power and an injective READOUT.An injective READOUT is needed to ensure non-isomorphic graphs receive different graph embeddings.Source: §5.2.2.1 · p. 136

5.2.2.2 Learning node representations with GNNs & graph kernels

• Graph kernels can provide underexplored node representations, while hybrid kernel–GNN methods offer a promising direction for combining their strengths.Existing kernels can yield explicit or approximate graph feature vectors and, through the R-convolution framework, implicit node representations that could serve as baselines. Nikolentzos et al. (2018b) and Du et al. (2019) report promising hybrid performance; Du et al. (2019) introduce a graph neural tangent kernel equivalent under certain assumptions to an infinitely wide neural network trained by gradient descent, while retaining a convex objective.Source: §5.2.2.2 · pp. 136–137

5.2.3 New application domains

• Beyond structural biology and chemoinformatics, emerging domains—particularly medical and mathematical applications—could broaden graph datasets and learning tasks.The review identifies these domains as promising because their distinct data types may enrich future research.Source: §5.2.3 · p. 137

5.2.3.1 Medical applications

• Medical applications include electronic health records and brain connectivity networks as promising settings for graph-based methods.Graphical information in multi-modal electronic health records has been used for mortality or medication prediction, and knowledge graphs have been learned from records; these large, noisy graphs present challenges and potential patient-welfare benefits. MRI thresholding can produce brain functional-connectivity networks, motivating kernels for heterogeneous, multiscale data; topology remains a challenge, while early Weisfeiler–Lehman studies of fMRI graphs show encouraging results.Source: §5.2.3.1 · pp. 137–138

5.2.3.2 Mathematical applications

• Mathematical applications include geometric graphs as a basis for new kernels and the planted clique problem as a potential graph-kernel classification task.Geometric graphs built from point clouds using proximity rules offer a principled starting point for kernel development (Bach, 2008). The planted clique task distinguishes random graphs from those with an added clique; the review proposes exploring kernels for accurate, faster classification.Source: §5.2.3.2 · pp. 138–139

5.3 Conclusion

• The survey presents graph kernels as a vibrant, theoretically grounded field with opportunities for future work and hopes to stimulate novel research.It notes that contributions can range from assessing kernel properties theoretically to empirically evaluating new graph features.Source: §5.3 · p. 139