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 follow-up with A. Smola [P3] established diffusion kernels and, more generally, spectral graph kernels, as a standard approach to kernel-based-learning 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]