PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Kernels

S. V. N. Vishwanathan, Karsten M. Borgwardt, Imre Risi Kondor, Nicol N. Schraudolph

arXiv:0807.0093v1cs.LG

TL;DR

Graph-kernel computation was limited by methods requiring O(n^6) time and by disconnected treatments of related kernel families. The paper unifies these approaches through RKHS linear algebra and Sylvester-equation methods, reducing computation to O(n^3) and often achieving up to three orders of magnitude speed gains while proposing additional connections and kernels.

  • Problem

    Existing graph kernels required computationally expensive evaluation, while related graph-kernel approaches had largely been studied separately.

  • Method

    The paper unifies graph kernels using RKHS extensions of linear algebra, Sylvester-equation reductions, iterative solvers, and connections to rational, R-convolution, and diffusion kernels.

  • Results

    O(n^3) computation and up to three orders of magnitude speed gains were obtained, while the composite graph kernel improved accuracy by around 4–5% over the vanilla graph kernel.

  • Takeaways & Limitations

    The framework makes random walk graph-kernel computation viable for practical problem sizes and supports new graph kernels and theoretical connections.

  • Takeaways & Limitations

    The composite-kernel experiments used a graph model capturing only 10% of the genes examined in both studies, and diffusion kernels required prior probabilities or sufficiently rich features.

Abstract

from arXiv · show

We present a unified framework to study graph kernels, special cases of which include the random walk graph kernel \citep{GaeFlaWro03,BorOngSchVisetal05}, marginalized graph kernel \citep{KasTsuIno03,KasTsuIno04,MahUedAkuPeretal04}, and geometric kernel on graphs \citep{Gaertner02}. Through extensions of linear algebra to Reproducing Kernel Hilbert Spaces (RKHS) and reduction to a Sylvester equation, we construct an algorithm that improves the time complexity of kernel computation from $O(n^6)$ to $O(n^3)$. When the graphs are sparse, conjugate gradient solvers or fixed-point iterations bring our algorithm into the sub-cubic domain. Experiments on graphs from bioinformatics and other application domains show that it is often more than a thousand times faster than previous approaches. We then explore connections between diffusion kernels \citep{KonLaf02}, regularization on graphs \citep{SmoKon03}, and graph kernels, and use these connections to propose new graph kernels. Finally, we show that rational kernels \citep{CorHafMoh02,CorHafMoh03,CorHafMoh04} when specialized to graphs reduce to the random walk graph kernel.

1. Introduction

The paper unifies several graph-kernel approaches while developing efficient computation methods. It frames graph kernels as similarity measures over structured graph data and outlines extensions connecting graph kernels with other kernel families.

  • Background: The paper addresses graph-structured relationships arising in bioinformatics, chemoinformatics, drug discovery, web mining, and social networks.Graphs represent objects as nodes and their relationships as edges.
  • Background: Graph kernels measure similarity between nodes or graphs while aiming to capture graph structure efficiently.Kernel functions must be symmetric and positive semi-definite.
  • Contributions: The paper presents theoretical connections among four graph-kernel research strands and new algorithms for efficiently computing kernels between graphs.The framework includes linear-algebraic and graph-theoretic foundations, with RKHS extensions discussed as part of the development.
  • Graph Concepts: The paper works with connected graphs and introduces weighted graphs, adjacency matrices, normalized transition matrices, and random walks as core graph concepts.A random walk’s t-step transitions are represented by powers of the normalized adjacency matrix.
  • Paper Outline: The first part develops a unifying framework covering random walk, geometric, and marginalized graph kernels as special cases.The framework also proves positive semi-definiteness and provides efficient computation methods.
  • Paper Outline: The second part connects graph kernels with rational kernels, R-convolution kernels, semirings, and diffusion processes, while proposing new graph kernels.It also notes that semiring extensions do not always preserve positive semi-definiteness.

2. Random Walk Graph Kernels

Random walk graph kernels compare simultaneous walks across two graphs using their direct product graph. The framework recovers established marginalized, random walk, and geometric kernels through suitable choices of weights, probabilities, and walk-length measures.

  • Direct Product Graphs: Generalized random walk graph kernels count matching random walks performed simultaneously on two graphs.The direct product graph provides the representation for these paired walks.
  • Direct Product Graphs: The direct product graph contains paired vertices, with adjacency requiring corresponding adjacency in both original graphs.Its adjacency matrix is the Kronecker product of the two original adjacency matrices.
  • Random Walk Kernels: A random walk on the direct product is equivalent to simultaneous random walks on the two component graphs.Initial distributions combine through the Kronecker product, and entries of A×^k encode paired k-step transition probabilities.
  • Weighting Walks: The RKHS weight matrix W× encodes edge similarity and is nonzero only for edges present in the direct product graph.With multiple edge labels, nonzero entries additionally require matching labels.
  • Kernel Construction: The generalized kernel is defined from W×, initial and stopping distributions, and a discrete measure over walk lengths.Under convergence conditions, the resulting kernel is positive semi-definite.
  • Special Cases: The framework recovers marginalized, random walk, and geometric graph kernels through specific choices of transition matrices, adjacency matrices, probabilities, and walk-length weights.Uniform endpoint distributions and adjacency-based weights recover the random walk kernel up to a constant factor; factorial walk weights recover the geometric kernel.

3. Efficient Computation

The paper replaces costly graph-kernel computations with Sylvester-equation, conjugate-gradient, fixed-point, and spectral methods. These approaches reduce key costs from O(n^6) to O(n^3), with further savings for sparse graphs and geometric kernels.

  • Random Walk Kernels: O(n^6) direct computation arises from inverting an n^2 × n^2 matrix for two n-vertex graphs.The relevant matrix is I − λW×.
  • Sylvester Equation Methods: O(n^3) computation of the random walk graph kernel follows by reducing the problem to a Sylvester equation.The final kernel extraction costs O(n^2) after solving the equation.
  • Sylvester Equation Methods: Generalized Sylvester equations require generalized simultaneous Schur factorizations of d symmetric matrices, where d is the number of labels.The computational cost is higher when the number of labels is large.
  • Iterative Solvers: Sparse feature matrices reduce each conjugate-gradient matrix-vector product to O(n^2) when they contain O(n) non-ζ entries.Without this sparsity condition, the product costs O(n^3d) when φ(·) ∈ R^d.
  • Iterative Solvers: Fixed-point iterations converge when all eigenvalues of λW× lie inside the unit disk, ensured by λ < 1/ξmax.Each iteration can use the same accelerated matrix-vector products as conjugate-gradient methods.
  • Geometric Kernel: O(n^3) computation of the geometric kernel is obtained through spectral decompositions of the two graph adjacency matrices.The resulting Kronecker-structured terms and their product can then be computed in O(n^2) time.

4. Experiments

The experiments compare graph-kernel computation methods on synthetic, real-world, unlabeled, labeled, and protein-interaction datasets, emphasizing runtime scaling and practical speedups. The proposed approaches achieve substantial runtime improvements, while the composite kernel improves prediction accuracy on two biological tasks.

  • Experimental design: The evaluation compares the direct method with Sylvester equation, conjugate gradient, and fixed-point approaches across randomly generated and real-world graphs.Experiments include scaling studies, four real-world datasets, and protein-interaction applications.
  • Randomly generated graphs: On graphs with 1024 nodes, Sylvester-solver runtimes are fairly independent of filling degree, whereas conjugate-gradient and fixed-point runtimes increase as graphs become denser.The iterative methods are especially efficient for filling degrees below 20%, while the Sylvester solver cannot exploit adjacency sparsity.
  • Unlabeled graphs: On unlabeled real-world graphs, conjugate-gradient and accelerated fixed-point methods are consistently about two orders of magnitude faster than the conventional direct method.The Sylvester approach is competitive on smaller graphs but slows with increasing graph size and still outperforms the direct method.
  • Labeled graphs: On labeled graphs, the proposed methods outperform the direct approach by about a factor of 1000 with a linear edge-label kernel, while conjugate gradient and fixed point remain at least two orders faster with a delta kernel.The Sylvester approach is slowed for the delta kernel by a Kronecker-product approximation in place of a generalized Sylvester solver.
  • Protein-interaction networks: The composite graph kernel improves prediction accuracy over the vanilla kernel by around 4–5% on both leukemia and breast-cancer experiments.Reported accuracies are 63.33% for leukemia and 61.54% for breast cancer.
  • Protein-interaction networks: The composite kernel models missing interactions, whereas the vanilla kernel remains near baseline because it cannot measure network discrepancies and uses a sparse graph model covering only 10% of examined genes.The cited analysis also identifies limited mapping of genes to interacting proteins as a constraint on the vanilla kernel.

5. Rational Kernels

This section connects rational kernels on transducers to random walk graph kernels through transducer composition and product graphs. It shows that graph-specialized rational kernels recover random walk graph kernels while preserving positive semidefiniteness under suitable constructions.

  • Transducer connections: Transducer composition is analogous to computing product graphs, linking rational kernels on weighted transducers to generalized random walk graph kernels.The framework views rational kernels on weighted transducers as extensions of random walk graph kernels to weighted automata.
  • Weighted transducers: A weighted finite-state transducer encodes states, initial and final weights, and labeled transitions over a semiring.Its transition structure is represented by a four-dimensional tensor indexed by states and input-output labels.
  • Rational kernels: Rational kernels map transducer output weights to real values through a function ψ, with semiring morphisms connecting abstract operations to ordinary arithmetic.The construction applies ψ to the output weight assigned to a pair of strings.
  • Positive semidefiniteness: Replacing a transducer T by T ◦ T^-1 and using a semiring morphism yields a positive semidefinite rational kernel.The proof decomposes the kernel into positive semidefinite terms and uses closure under addition.
  • Recovering random walk graph kernels: Specializing the semiring to real arithmetic and restricting accepted strings to a^k reduces rational kernels on graphs to random walk graph kernels.Using the normalized adjacency matrix of the direct product graph recovers the corresponding random walk kernel form.

6. R-convolution Kernels

R-convolution kernels construct similarities for compound objects by summing component-wise kernels over valid decompositions. Applied to graphs, this provides a unifying view of many graph kernels, while abstract-semiring variants may lose positive semidefiniteness.

  • R-convolution framework: R-convolution kernels compare compound objects by aggregating component kernels over all valid decompositions.A finite measure ensures convergence, and positive semidefiniteness follows when the individual component kernels are positive semidefinite.
  • Graph-kernel interpretations: Most graph kernels can be understood as R-convolutions that differ in their graph decomposition and component similarity measure.Graph substructures may include paths, label sequences, cycles, subtrees, shortest paths, fingerprints, rings, and functional groups.
  • Graph-kernel interpretations: Random walk graph kernels decompose graphs into paths, whereas marginalized graph kernels use label sequences and related component comparisons.Other approaches compare node-edge random walks or count shared cyclic patterns.
  • Abstract semirings: Abstract-semiring extensions generalize R-convolution aggregation beyond ordinary addition and multiplication.The optimal assignment graph kernel is motivated by this approach and uses the tropical semiring.
  • Limitations: The optimal assignment graph kernel is not always positive semidefinite, and necessary and sufficient conditions for the abstract construction remain open.This limits the generality of the semiring-based formulation when valid kernels are required.

7. Diffusion-Based Graph Kernels?

This section extends diffusion-kernel ideas from graph vertices to graph pairs using Cartesian product graphs and develops efficient computation methods. It ultimately finds that diffusion-based graph kernels are not useful generally because uniform initial and stopping distributions can make them identically zero.

  • Diffusion and regularization: The graph Laplacian is symmetric and connects diffusion processes with smoothness-based regularization on graphs.The resulting regularization is described as a graph-adapted analogue of Gaussian-kernel regularization.
  • Diffusion-based graph kernels: Replacing direct-product adjacency matrices with Laplacian-based weights motivates diffusion-based kernels between graphs.The construction seeks a similarity measure based on diffusion over a product graph.
  • Cartesian product graphs: Cartesian product graphs preserve the intended diffusion interpretation when the direct-product Laplacian does not decompose as a Kronecker product.Their vertices pair nodes from the two input graphs, with edges connecting pairs that agree in one coordinate and are adjacent in the other.
  • Kernel validity: A convergent discrete measure produces a valid positive semidefinite Cartesian-product diffusion kernel.The construction uses Kronecker-product initial and stopping distributions and a Kronecker-sum weight matrix.
  • Efficient computation: Cartesian-product diffusion kernels can be computed with conjugate-gradient, fixed-point, and Sylvester-equation methods.The Cartesian-product computation takes about twice as long as the direct-product computation because the generalized Sylvester equation has degree 2d instead of d.
  • A deficiency of diffusion-based graph kernels: With uniform initial and stopping distributions, the diffusion-based graph kernel is uniformly zero because positive powers of the Laplacian annihilate the uniform vector.Avoiding this requires prior probability knowledge or a sufficiently rich feature representation that prevents rank deficiency.
  • A deficiency of diffusion-based graph kernels: The authors therefore report no diffusion-based graph-kernel experiments because their datasets satisfy neither requirement for avoiding the deficiency.Arbitrarily breaking uniformity would destroy permutation invariance.

8. Outlook and Discussion

The paper unifies several graph-kernel frameworks and relates them to rational, diffusion, and R-convolution kernels while improving computational feasibility. It also identifies limitations of random-walk and diffusion approaches and highlights higher-order graph comparison as future work.

  • Random walk, marginalized, and geometric graph kernels are unified through extended linear algebra in RKHS, clarifying their similarities and differences.
  • Rational kernels specialized to graphs are closely related to graph kernels, connecting graph-kernel design with semirings and transducers.
  • Diffusion kernels share computational connections with generalized random-walk kernels, but rank deficiency limits the applicability of the diffusion-based approach.
  • Sparsity, low effective rank, and Kronecker structure greatly reduce graph-kernel computation, making random-walk kernels viable for practical problem sizes.
  • Random-walk kernels can underweight long walks because admissible decay parameters may be small, while normalization can cause short self-repeating walks to dominate.
  • Future graph comparison should integrate higher-order structures such as spanning trees while retaining efficient computation.

Appendix A. Extending Linear Algebra to RKHS

The appendix extends matrix-based linear algebra to RKHS-valued matrices by lifting scalar feature maps entrywise. This provides the foundation for manipulating graph-kernel expressions in RKHS.

  • The feature map φ is lifted entrywise to matrices, producing an RKHS-valued matrix map Φ for extending tensor algebra.

A.1 Matrix Product

This subsection defines RKHS matrix products and identifies where ordinary matrix-algebra properties fail. It then establishes extensions of the vec(ABC) identity for subsequent computations.

  • Definition 10 extends matrix products to RKHS-valued matrices and mixed RKHS–real products.
  • Associativity can fail when all three matrices contain RKHS elements, unlike associativity, transpose-commutativity, and distributivity in ordinary matrix multiplication.
  • The subsection develops an RKHS extension of the vec(ABC) formula despite these altered algebraic properties.

A.2 Kronecker Product

The appendix extends Kronecker products and sums to RKHS and heterogeneous matrix settings, deriving vec identities useful for efficient kernel computation. Finite-dimensional feature maps reduce one direct computation from O(n^4) to O(n^3d).

  • RKHS Kronecker products are defined for pairs of feature-mapped matrices, with corresponding extensions of vec(ABC).
  • Standard Kronecker identities do not necessarily hold for RKHS-valued matrices, motivating heterogeneous products between RKHS and real matrices.
  • When the feature map has finite dimension d, the left-hand side of the RKHS vec identity can be computed in O(n^3d) operations instead of O(n^4) direct kernel evaluations.
  • The heterogeneous Kronecker product supports additional vec(ABC) identities for mixed RKHS–real matrix configurations.
  • The Kronecker sum is extended to RKHS matrices and retains analogous vec-formula relationships, including heterogeneous forms.

A.5 Hadamard Product

This section defines Hadamard products for RKHS-valued matrices and establishes their interaction with Kronecker products, while noting that a general identity does not always hold.

  • A.5 Hadamard Product: The RKHS extension is presented as mathematically interesting but is not required to implement the fast graph kernels.This separates the theoretical construction from the algorithmic requirements of the paper.
  • A.5 Hadamard Product: The RKHS Hadamard products Φ(A) ⊙Φ(B) and Φ(A) ⊙C are defined entrywise through inner products and scalar multiplication.For entries i,j, they equal ⟨φ(Aij), φ(Bij)⟩H and φ(Aij) Cij, respectively.
  • A.5 Hadamard Product: The section proves two extensions of an earlier identity for combining Hadamard and Kronecker products.The extensions are established through lemmas and direct verification using linearity of the inner product.
  • A.5 Hadamard Product: One extension expresses the Kronecker product of Hadamard products as an entrywise construction involving Φ(A), Φ(B), Φ(C), and Φ(D).The displayed relation connects inner products of feature-mapped entries with the corresponding Kronecker-product indexing.
  • A.5 Hadamard Product: The analogous identity does not necessarily hold in general.The section identifies this lack of general validity as the difficulty with equation (78).

Appendix B. Cartesian Product Kernels: Proof of Lemma 9

This appendix proves Lemma 9 through technical lemmas, induction, vectorization identities, and a positive-semidefinite-kernel closure argument.

  • Appendix B. Cartesian Product Kernels: Proof of Lemma 9: The proof of Lemma 9 is preceded by a technical lemma and uses earlier lemmas to establish the required algebraic identity.The appendix explicitly positions these steps as preparation for proving Lemma 9.
  • Appendix B. Cartesian Product Kernels: Proof of Lemma 9: The proof also uses p□ = p ⊗p′ = vec(p′p⊤), the definition of W□, and Lemma 23.These identities connect vectorization and Kronecker products within the proof.
  • Appendix B. Cartesian Product Kernels: Proof of Lemma 9: An induction over k establishes the relevant identity, beginning with the base case k = 1 and continuing from k to k + 1.The induction step uses the induction assumption and Lemma 23, then reorganizes boundary terms before applying a known identity.
  • Appendix B. Cartesian Product Kernels: Proof of Lemma 9: A standard identity from Abramowitz and Stegun is invoked as part of the induction argument.The cited reference is Section 24.1.1.
  • Appendix B. Cartesian Product Kernels: Proof of Lemma 9: Each term in equation (83) is a valid positive-semidefinite kernel because it has the form ρ(G)⊤ρ(G′).The sum remains positive semidefinite because this class is closed under non-negative linear combinations, including the positive coefficients used here.
Loading 0807.0093v1…