Isotropic Gaussian Processes on Finite Spaces of Graphs

Abstract

We propose a principled way to define Gaus- sian process priors on various sets of unweighted graphs: directed or undirected, with or without loops. We endow each of these sets with a ge- ometric structure, inducing the notions of close- ness and symmetries, by turning them into a ver- tex set of an appropriate metagraph. Building on this, we describe the class of priors that respect this structure and are analogous to the Euclidean isotropic processes, like squared exponential or Mate ́rn. We propose an efficient computational technique for the ostensibly intractable problem of evaluating these priors’ kernels, making such Gaussian processes usable within the usual tool- boxes and downstream applications. We go fur- ther to consider sets of equivalence classes of un- weighted graphs and define the appropriate ver- sions of priors thereon. We prove a hardness re- sult, showing that in this case, exact kernel com- putation cannot be performed efficiently. How- ever, we propose a simple Monte Carlo approxi- mation for handling moderately sized cases. In- spired by applications in chemistry, we illus- trate the proposed techniques on a real molecular property prediction task in the small data regime.