Scaling Graph Kernels to Large Networks and Datasets

61 concepts62 papers4 proposals

Graph kernels offer a mathematically rigorous way to measure structural similarity between graphs, bridging the gap between structured data and non-parametric machine learning methods. They allow us to compute kernel matrices for downstream tasks like classification, clustering, and regression, and even provide theoretical foundations for understanding deep architectures via frameworks like the Graph Neural Tangent Kernel introduced by Du et al..

However, traditional graph kernels hit a scalability wall. They suffer from two distinct computational bottlenecks:

  1. The Node Bottleneck ($O(N^3)$ or worse): Computing similarity between nodes within a single graph or across a pair of graphs often requires evaluating global topological properties. For instance, computing the regularized Laplacian kernel requires inverting a large matrix, a process that scales cubically with the number of nodes ($N$). Shortest-path kernels can scale as poorly as $O(N^4)$, as noted by Feragen et al..
  2. The Dataset Bottleneck ($O(M^2)$): To train a kernel-based classifier (like a Support Vector Machine) on a dataset of $M$ graphs, one must compute a pairwise similarity matrix (the Gram matrix). This quadratic scaling makes direct application to datasets with hundreds of thousands or millions of graphs computationally prohibitive.

To resolve these bottlenecks, recent research focuses on randomized approximations, structural hashing, and explicit vector embeddings that bypass exact matrix operations and pairwise comparisons.

Sub-Quadratic Node Similarity via Graph Random Features

To eliminate the $O(N^3)$ matrix inversion bottleneck inherent in global node kernels, researchers have turned to random feature maps. The core intuition is simple: if we can find a low-dimensional randomized feature map $\phi(v)$ for each node such that the inner product $\langle \phi(u), \phi(v) \rangle$ approximates the exact kernel value $K(u,v)$, we never need to compute or invert the full kernel matrix.

Krzysztof Marcin Choromanski introduced this approach via Graph Random Features (GRFs) in Taming graph kernels with random features. Instead of explicitly calculating the regularized Laplacian kernel—which requires computing $(I + \gamma L)^{-1}$—the GRF framework uses random walks as stochastic probes of the graph's topology. Because a random walk of length $l$ implicitly computes powers of the transition matrix, simulating a finite number of random walks allows researchers to construct randomized signature vectors for each node. This reduces the computational complexity from cubic to sub-quadratic time.

Reid et al. generalized this mechanism in General Graph Random Features (g-GRFs). By introducing a "modulation function" to weight walks of varying lengths, the authors enabled the unbiased estimation of a much wider class of graph functions.

Exact Kernel Method:
[Large Graph] ---> Matrix Inversion (O(N³)) ---> Exact Node Similarity

Graph Random Features Method:
[Large Graph] ---> Simulate Random Walks ---> Low-Dim Signatures ---> Inner Product (Sub-quadratic)

A primary challenge with Monte Carlo random walk sampling is the variance of the estimator. To address this, Reid et al. proposed Quasi-Monte Carlo Graph Random Features (q-GRFs). By forcing pairs of random walks to have negatively correlated lengths—meaning if one walk is short, its partner is structurally long—they significantly reduced approximation variance with zero added computational overhead.

Handling Continuous Attributes with Locality-Sensitive Hashing

When graphs contain continuous node attributes (such as physical coordinates or high-dimensional feature vectors), calculating similarity becomes even more expensive. Comparing continuous probability distributions across thousands of nodes typically introduces a quadratic overhead per node pair.

To scale kernels to attributed graphs, Propagation Kernels—developed by Neumann et al. and expanded in Propagation kernels: efficient graph kernels from propagated information—leverage Locality-Sensitive Hashing (LSH).

Instead of performing expensive pairwise comparisons of continuous distributions as information propagates through the network, the authors use LSH to map continuous node attribute distributions into discrete bins. Nodes that fall into the same bin are assigned identical integer labels. This transforms a complex continuous comparison problem into an efficient counting and binning process, allowing the kernel to capture both structural propagation and continuous attribute information in linear time relative to the number of edges.

Bypassing the Pairwise Graph Bottleneck

Even if node-level computations are optimized, the $O(M^2)$ dataset bottleneck remains a challenge when comparing $M$ different graphs.

To achieve linear scalability relative to the dataset size ($O(M)$), modern frameworks focus on mapping entire graphs directly into fixed-length vector spaces, completely bypassing the need to compute an explicit pairwise Gram matrix.

Traditional Pairwise Bottleneck:
Graph 1 \
Graph 2 ---> Compute Pairwise Gram Matrix ---> O(M²) Complexity
Graph 3 /

Explicit Embedding Approach:
Graph 1 ---> Vector Embedding 1 \
Graph 2 ---> Vector Embedding 2 ---> Linear Classifier / Downstream Task ---> O(M) Complexity
Graph 3 ---> Vector Embedding 3 /

One way to achieve this is through stochastic substructure counting. Sherashidze et al. demonstrated that by sampling small subgraphs (graphlets) of 3 to 5 nodes, one can efficiently approximate the structural distribution of large graphs. Building on this idea, Dutta et al. proposed Stochastic Graphlet Embedding (SGE). SGE uses a stochastic search to sample high-order subgraphs and applies topological hashing to count them, mapping each graph to a fixed-length vector of subgraph counts.

Alternatively, the problem can be framed through the lens of optimal transport. Kolouri et al. introduced Wasserstein Embedding for Graph Learning (WEGL), which treats the node embeddings of a graph as a probability distribution. By utilizing Linear Optimal Transport, WEGL projects these distributions into a linear space where the Wasserstein distance between graphs can be approximated via standard Euclidean distances.

By representing entire graphs as independent, fixed-length vectors, both SGE and WEGL allow researchers to utilize standard linear classifiers or fast clustering algorithms, reducing the dataset scaling factor from $O(M^2)$ to $O(M)$ and enabling the analysis of web-scale graph databases.

Key Foundational Work

Extensions of marginalized graph kernels (2004) — contributed 1 concept elements to this direction.
Application of kernels to link analysis (2005) — contributed 1 concept elements to this direction.
Translation invariant classification of non-stationary signals (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_graph_kernel_scalability_50a67e81,
  title = {graph kernel scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-kernel-scalability/rdr_50a67e81830647d78b5f451696caf3b9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_kernel_scalability_50a67e81_v1,
  title = {graph kernel scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-kernel-scalability/rdr_50a67e81830647d78b5f451696caf3b9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake