Source-linked AI summary
The Multiscale Laplacian Graph Kernel
Risi Kondor, Horace Pan
TL;DR
Existing graph kernels often emphasize either local or global structure, despite applications such as molecular analysis requiring information across scales. The paper introduces FLG and recursively constructs MLG kernels over nested subgraphs, with randomized projection for efficient computation. Experiments report the highest prediction accuracy on all datasets except NCI1 and NCI109, where MLG outperforms all non-Weisfeiler–Lehman kernels.
Problem
Most existing graph kernels are primarily local or global, leaving multiscale graph structure insufficiently represented.
Method
The FLG kernel combines vertex features with graph-Laplacian information, while MLG recursively builds subgraph kernels across increasing sizes using randomized low-rank projection for efficiency.
Results
MLG achieves the highest prediction accuracy for all datasets except NCI1 and NCI109, where it performs better than all non-Weisfeiler–Lehman kernels.
Takeaways & Limitations
MLG captures topological relationships between individual vertices and subgraphs, supporting graph comparison at multiple scales.
Takeaways & Limitations
The FLG kernel alone cannot account for structure at multiple different scales.
Abstract
from arXiv · showhide
Many real world graphs, such as the graphs of molecules, exhibit structure at multiple different scales, but most existing kernels between graphs are either purely local or purely global in character. In contrast, by building a hierarchy of nested subgraphs, the Multiscale Laplacian Graph kernels (MLG kernels) that we define in this paper can account for structure at a range of different scales. At the heart of the MLG construction is another new graph kernel, called the Feature Space Laplacian Graph kernel (FLG kernel), which has the property that it can lift a base kernel defined on the vertices of two graphs to a kernel between the graphs. The MLG kernel applies such FLG kernels to subgraphs recursively. To make the MLG kernel computationally feasible, we also introduce a randomized projection procedure, similar to the Nyström method, but for RKHS operators.
1. Introduction
Graph kernels support applications such as chemoinformatics, but existing approaches generally capture either local or spectral structure. The paper motivates kernels that compare graphs across multiple scales and introduces recursive Laplacian-based constructions to do so efficiently.
- Graph learning applies to domains including web data mining, protein function prediction, and molecular screening for drug safety and efficacy.
- Graph kernels must capture task-relevant similarity, remain invariant to vertex ordering, and be efficiently computable.
- Many graph invariants and kernels reduce to either local properties, such as subgraph counts, or spectral functions of adjacency or Laplacian eigenvalues.
- Molecular comparison requires sensitivity to global shapes, smaller structures, and the placement of those smaller structures within the global graph.
- The MLG kernel addresses this gap by recursively applying the FLG kernel to build a hierarchy of subgraph kernels at increasing sizes.
- A linearization strategy combined with randomized low-rank projection reduces recursive kernel computation to operations on small matrices.
2. Laplacian Graph Kernels
The paper develops Laplacian-based graph kernels that compare global graph shape while addressing vertex-labeling, graph-size, and multiscale limitations. The FLG kernel uses local, permutation-invariant vertex features, and the MLG construction extends this kernel recursively across subgraphs.
- Laplacian Graph Kernel: The graph Laplacian encodes overall graph shape through its low-eigenvalue eigenvectors, which vary smoothly across adjacent vertices.A regularized Laplacian is used because the unregularized Laplacian has a zero eigenvalue and cannot be inverted directly.
- Laplacian Graph Kernel: The LG kernel compares Gaussian distributions with covariances based on inverse regularized Laplacians, yielding a positive semi-definite similarity measure.Its value is largely determined by the alignment of subspaces associated with the largest eigenvalues of the inverse Laplacians.
- Laplacian Graph Kernel: The LG kernel is limited because it requires equal-sized graphs, captures only overall structure, and is not invariant to vertex permutations.The permutation problem arises because the ordering of the variables associated with vertices is arbitrary.
- Feature Space Laplacian Graph Kernel: The FLG kernel transforms vertex-space variables into feature-space variables using local, permutation-invariant vertex features such as degree, diffusion values, or atom type.The resulting covariance has the form UL^-1U^⊤, allowing the kernel to compare feature distributions rather than vertex-indexed distributions.
- Feature Space Laplacian Graph Kernel: Because its features are local and permutation invariant, the FLG kernel supports graphs with different numbers of vertices while retaining information about global shape.Its remaining limitation is that it does not represent structure at multiple scales.
- Kernelized Construction: The FLG kernel can be induced from any symmetric positive semi-definite base kernel, enabling computation without explicit finite-dimensional feature vectors.The base kernel is the inner product of vertex feature vectors, and the generalized construction also permits abstract vertex spaces.
3. Multiscale Laplacian Graph Kernels
MLG kernels compare graphs through recursively constructed kernels on nested subgraphs, capturing similarity across multiple scales. The construction combines FLG kernels with neighborhood hierarchies, while implementation strategies reduce redundant computation.
- A multiscale graph kernel captures similarity through both individual-vertex relationships and relationships between subgraphs.
- The construction starts with small, typically overlapping subgraphs, attaches each subgraph to a graph vertex, and uses induced kernels as new vertex-level base kernels.
- At successive levels, FLG kernels are recursively applied to larger induced subgraphs, producing MLS kernels K1 through KL.
- The MLG kernel compares two full graphs by applying an additional FLG kernel to their top-level subgraph representations, provided they share a base kernel.
- Neighborhoods can be defined as expanding graph balls Br(v), with radius r = r0η^(ℓ−1), and η = 2 supports a simple construction.
- Naive recursive evaluation may require O(n^(2L+2)) kernel evaluations, motivating on-demand computation, memoization, and hashing of recurring subgraphs.On-demand computation avoids unnecessary distant pairs, while hash tables reuse previously computed entries and identify repeated subgraph structures.
4. Linearized Kernels and Low Rank Approximation
The paper linearizes graph kernels in a shared feature space and uses randomized low-rank projections to make recursively defined MLG kernels computationally feasible.
- Computational Challenge: O(LM^2n^5) Gram-matrix computation motivates replacing the full joint feature space with a smaller approximate space.The unapproximated approach also requires costly cross-graph basis computations and large Gram matrices.
- Linearized Kernels: A joint basis across all graph vertices lets kernel evaluations use fixed per-graph matrices that can be precomputed independently.Individual evaluations then reduce to plugging these matrices into the FLG kernel.
- Linearized Kernels: Linearization converts each hierarchy level into explicit finite-dimensional vertex features, allowing MLG computation level by level without recursion.Each level updates vertex feature vectors before the next FLG computation.
- Randomized Low-Rank Approximation: The randomized approximation samples vertices, forms a smaller Gram matrix, and retains the leading ˜P basis vectors to approximate the joint feature space.This procedure is similar to Nyström approximation but targets the matrices used to form the FLG kernel.
- Randomized Low-Rank Approximation: With rapidly decaying eigenvalues, ˜P ∼10 and ˜N around 100 can reduce dataset Gram-matrix computation to O(ML˜N^2˜P^3 + ML˜N^3 + M^2˜P^3).For ENZYMES, all-pairs FLG computation took about 2 minutes on a 16-core machine.
5. Experiments
The experiments compare MLG with established graph kernels using cross-validated binary SVM classification on standard benchmark datasets. MLG achieves the highest accuracy on most datasets, with two or three hierarchy levels typically optimal.
- Experimental Setup: MLG is compared with Weisfeiler–Lehman, Weisfeiler–Lehman Edge, Shortest Path, Graphlet, and p-random Walk kernels on standard benchmark datasets.The comparison evaluates several prominent kernel families.
- Experimental Setup: Binary C-SVM classification uses 10-fold cross-validation, repeated 10 times, with prediction accuracy and runtime reported.The experiments were run on a 16-core Intel E5-2670 processor with 32 GB memory.
- Results: MLG achieves the highest prediction accuracy on every dataset except NCI1 and NCI109, where it outperforms all non-Weisfeiler–Lehman kernels.The reported conclusion concerns the benchmark datasets evaluated in the experiments.
- Results: The optimal MLG settings generally use two or three levels and comparable radius sizes, while η and γ are typically selected from small values between 0.01 and 1.Increasing η or γ smooths differences between reasonably similar graphs, which is not always desirable.
6. Conclusions
The paper introduces FLG and recursively defined MLG kernels for multiscale graph structure, reporting competitive performance with limited tuning. It identifies chemical-domain optimization and broader multiresolution applications as directions for further work.
- Contributions: FLG combines vertex-attached information with the graph Laplacian, while MLG recursively captures topological relationships among vertices and subgraphs.MLG is the paper’s multilevel extension of the single-level FLG kernel.
- Conclusions: With only one or two parameters tuned, MLG performs on par with or slightly better than other well-known graph kernels.The conclusion describes this as an encouraging result rather than an optimal solution for chemical compounds.
- Limitations and Future Work: Optimally modeling the multiscale structure of chemical compounds remains challenging and requires further work and domain knowledge.The paper also suggests that chaining local spectral analysis across scales may apply to multiresolution data such as images.