Can graph kernels compare graphs of different sizes?

Yes. Many constructions map them into a shared feature space based on patterns rather than vertex-by-vertex alignment.

Do they always require matching corresponding vertices?

No. Pattern-count kernels can compare graphs without an explicit node correspondence.

Is normalization always beneficial?

Not universally. It can reduce size effects, but size may be relevant to the task. The choice should be evaluated and documented.

AI Glossary / Computer vision and multimodal AI / Intermediate

Graph kernel

Definition

A graph kernel is a function that compares two graphs in a way suitable for kernel-based learning, typically corresponding to an inner product between their feature representations. It can measure shared structural patterns, labels or other graph properties without requiring every graph to have the same number of vertices.

What it means

Many datasets contain structured objects rather than fixed-length rows. A molecule, workflow or relationship network can be represented as a graph, but its size and connectivity may differ from those of another example. A graph kernel supplies a principled comparison for such objects.

The comparison might count shared walks, paths, small subgraphs or refined neighborhood patterns. Different kernels focus on different properties, so the word “similarity” needs to be interpreted in relation to the chosen construction.

In the usual kernel-learning sense, the function must satisfy positive-semidefinite requirements. An arbitrary graph-similarity score is not automatically a valid kernel. A graph kernel is also different from the small convolution kernel used to filter an image.

How it works

One explicit approach maps each graph G to a feature vector φ(G), then defines K(G, H) = φ(G)·φ(H). The features can count selected patterns, with matching definitions shared across all graphs. Some methods compute equivalent comparisons without constructing every feature explicitly.

A training set produces a kernel matrix containing pairwise graph comparisons. A kernel-based classifier or regressor can use that matrix to learn from labeled examples.

The Weisfeiler - Lehman subtree-style construction repeatedly refines vertex labels using their neighborhood information and compares resulting label counts across stages. It is one influential family, not a complete test of all possible graph differences. Normalization and graph size can strongly affect scores, so the evaluation must distinguish structural resemblance from simply having more counted features.

Three practical examples

1. Molecular learning: A model compares labeled molecular graphs using selected structural patterns, with separate validation of the property-prediction task.

2. Workflow classification: Graphs of business processes are compared according to activity labels and their neighborhood relationships.

3. Visual structure analysis: A system represents segmented regions and their relationships as graphs, then uses a kernel to compare those representations across images.

Think of it this way

Think of describing each building by counts of selected architectural patterns and comparing the resulting checklists. Two buildings can be similar under those counts even if their complete layouts differ.

The analogy explains feature-based comparison but not every implicit kernel. It also highlights a limitation: the chosen checklist determines which distinctions are visible and which are lost.

Worked example

Define a deliberately simple graph feature vector as [number of edges, number of triangles]. Suppose graph A has features [3, 1] and graph B has [4, 0]. Their dot-product kernel is K(A, B) = 3×4 + 1×0 = 12.

The self-comparisons are K(A, A) = 10 and K(B, B) = 16. A normalized version gives 12/√(10×16), approximately 0.949.

That high value does not mean the graphs are isomorphic or that triangles are unimportant. The edge-count component dominates this toy representation. Changing feature weights changes the comparison. The example is a valid explicit dot-product construction but is intentionally too limited to serve as a general-purpose graph-analysis method.

Illustrative case study

Fictional case: Linden Analytics classifies small process graphs. Its first kernel mostly groups large workflows together, even when their activity relationships differ. The analysts inspect the feature counts and find that graph size strongly influences the comparison.

They evaluate normalization and richer labeled-neighborhood features, using separate test graphs to assess the final prediction task. They also retain examples where different structures receive similar scores. The team documents what the kernel represents instead of calling it a universal measure of process similarity. This case illustrates feature design and evaluation, not a reported accuracy gain.

Common misconceptions and mistakes

A graph kernel is not necessarily a graph neural network. It can be a fixed mathematical comparison used by a separate learning algorithm.

A large kernel value is not automatically a probability of two graphs belonging to the same class. Its scale depends on the construction and normalization.

Matching kernel features does not prove graph isomorphism. Distinct graphs can share the selected statistics or remain indistinguishable to a particular refinement scheme.

An arbitrary symmetric similarity function may fail the positive-semidefinite condition needed by standard kernel methods. Also, a kernel that works well on one graph type may ignore essential information in another.

Business use

Graph kernels offer an interpretable route to learning from structured data, especially when useful pattern counts or neighborhood relationships can be specified. They can provide a meaningful baseline alongside learned graph representations.

Choose graph construction and kernel features together. Check labels, direction, edge attributes and size effects before training. Evaluate both predictive performance and computational cost, because storing all pairwise comparisons grows with the square of the number of training graphs even when individual comparisons are efficient.

Check your understanding

Two non-isomorphic graphs receive the same feature vector under a kernel. Can that kernel distinguish them through its dot-product comparisons alone?

Answer: No. Identical feature representations produce identical comparisons to every graph in that feature space. Distinguishing the graphs requires richer features or another representation that retains the relevant difference.

Related terms

Kernel method
Gram matrix
Support vector machine
Graph neural network
graph classification
Weisfeiler–Lehman refinement
graph feature

Learn next

Construct small graph feature vectors and compare raw with normalized dot products. Find two different graphs sharing the same simple counts to see what information is lost. Then study neighborhood-refinement kernels and evaluate whether their distinctions match the intended prediction task.

Sources

Primary research: Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn and Karsten M. Borgwardt, “Weisfeiler-Lehman Graph Kernels,” Journal of Machine Learning Research, 2011, https://www.jmlr.org/beta/papers/v12/shervashidze11a.html ; paper: https://www.jmlr.org/papers/volume12/shervashidze11a/shervashidze11a.pdf . The publisher's author abstract was read. The edge-and-triangle kernel is an original simplified example, not the paper's implementation.

Previous: Graph isomorphism Next: Graph Language Model