Graph kernels

Kernels on graphs

Methods for kernels on graphs, i.e., between two nodes of a single graph:

  • Kondor & Lafferty, 2002: Diffusion kernels on graphs and other discrete input spaces (pdf)
  • Smola & Kondor, 2003: Kernels and regularization on graphs (doi, pdf)
  • Gartner & Smola: A short tour of kernel methods for graphs (pdf)
    • Sec 1.2.2: Intersection and Jaccard kernels on arbitrary sets

Kernels between graphs

Methods for kernels between graphs, i.e., between two different graphs:

  • Haussler, 1999: Convolution kernels on discrete structures (pdf)
    • A general, though rather vague, framework for defining kernels between discrete structures, not necessarily graphs
  • Gartner et al, 2003: On graph kernels: Hardness results and efficient alternatives (doi)
  • Kashima et al, 2003: Marginal kernels between labeled graphs (pdf)
  • Borgwardt & Kriegel, 2005: Shortest-path kernels on graphs (doi, slides)
  • Vishwanathan et al, 2010, JMLR: Graph kernels (pdf, slides)
    • Start here: very well-written survey
    • Synthesizes existing literature, including:
      • random walk kernels (Kondor et al’s early papers; Gartner et al, 2003)
      • marginal kernels (Kashima et al, 2003)
      • shortest-path kernels (Borgwardt & Kriegel, 2005)
      • R-convolution kernels (Haussler, 1999)
  • Shervashidze et al, 2011: Weisfeiler-Lehman graph kernels (pdf)
    • Based on the Weisfeiler-Lehman test of graph isomorphism
  • Neumann et al, 2016: Propagation kernels (doi, arxiv)
    • Fancy name notwithstanding, this paper is squarely within the random walk paradigm
    • Main contribution is support for missing or uncertain labels
    • Sec. 2 has a recent summary of literature on graph kernels
  • Kondor & Pan, 2016: The multiscale Laplacian graph kernel (arxiv, pdf)

Kernels between DAGs

In DAGs, the generic problem of tottering in random walk kernels is eliminated, since cyclic walks are by definition impossible.

  • Kashima et al, 2004: Kernels for graphs (pdf)
    • Sec 1.2.3: Dynamic programming algorithm for random walks (“label sequences”) on labeled DAGs
  • Suzuki et al, 2006: Hierarchical directed acyclic graph kernel (doi)
  • Navarin, 2014, PhD thesis: Learning with kernels on graphs: DAG-based kernels, data streams, and RNA function prediction
    • Sec 4.2: Reviews previous work on DAG kernels (summary: there isn’t much of it and it doesn’t exploit acyclicity)
    • Sec 4.2: Extends tree kernels to rooted, ordered DAGs

Kernels on knowledge graphs

How to define kernels between nodes of a knowledge graph?

  • Bloehdorn, 2008, PhD thesis: Kernel methods for knowledge structures (pdf)
    • Sec 4.2: Set-based similarity functions usually are kernels
    • Sec 4.3: Taxonomic similarity functions are usually not kernels
  • Rettinger et al, 2012: Mining the semantic web (doi, pdf)
  • Losch et al, 2012: Graph kernels for RDF data (doi, pdf)
    • Kernels based on intersection graphs and intersection trees
    • “The essential difference is that, as RDF builds on unique node labels, each RDF subgraph can occur at most once in the input graph”
  • de Vries, 2013: A fast approximation of the Weisfeiler-Lehman graph kernel for RDF data (doi)
    • Claims to be better than intersection tree (but comparable to intersection graph)