
Learning (on) graphs and other combinatorial structures
In many learning problems, esp. in the realm of biology, social networks, etc., data instances
come in the form of graphs (learning graphs) or in the form of vertices of a given fixed
graph (learning on graphs).
My paper with J. Lafferty [P1] and the followup with A. Smola [P3] established diffusion kernels
and, more generally, spectral graph kernels, as a standard approach to kernelbasedlearning
on graphs. [P4] and [P5] addressed the other problem, learning in the space of graphs, by constructing
algebraically motivated efficiently computable graph invariants (see here for
more on the Fourier methods on the symmetric group).
[P6] is a review article.
When it comes to larger graphs, all these methods leave something to be desired because they cannot
take into account the fact that large graphs have structure at multiple different scales
(for example, to represent organic molecules, one would like to take into the simiarity between them at the
level of atoms, functional groups, subunits, and the full molecule).
[P7] addresses this issue by proposing a recursively defined kernel that explicitly accounts
for structure at multiple different scales.
Papers
[P1] R. Kondor and J. Lafferty:
Diffusion kernels on graphs and other discrete input spaces
(ICML 2002)
(winner of "test of time" award)
[paper]
[bib]
[P2] R. Kondor and J.P. Vert:
Diffusion kernels
in "Kernel Methods in Computational Biology" ed. B. Scholkopf, K. Tsuda and J.P. Vert,
(The MIT Press, 2004)
[paper]
[P3] A. Smola and R. Kondor:
Kernels and regularization on graphs
(COLT 2003)
[paper]
[bib]
[P4] R. Kondor and K. M. Borgwardt:
The skew spectrum of graphs
(ICML 2008)
[paper]
[ICML video]
[C++ code]
[P5] R. Kondor, N. Shervashidze and K. M. Borgwardt:
The graphlet spectrum
(ICML 2009)
[paper]
[P6] S. V. N. Vishwanathan, N. N. Schraudolf, R. Kondor and K. M. Borgwardt:
Graph kernels
(Journal of Machine Learning Research 11, 2010)
[paper]
[arXiv]
[P7] R. Kondor and H. Pan:
The Multiscale Laplacian Graph Kernel
(NIPS 2016)
[paper]
[code]
[slides]
