  We propose a principled way to define Gaussian process priors on various sets
of unweighted graphs: directed or undirected, with or without loops. We endow
each of these sets with a geometric structure, inducing the notions of
closeness and symmetries, by turning them into a vertex 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 Mat\'ern. We propose an efficient computational technique for
the ostensibly intractable problem of evaluating these priors' kernels, making
such Gaussian processes usable within the usual toolboxes and downstream
applications. We go further to consider sets of equivalence classes of
unweighted graphs and define the appropriate versions of priors thereon. We
prove a hardness result, showing that in this case, exact kernel computation
cannot be performed efficiently. However, we propose a simple Monte Carlo
approximation for handling moderately sized cases. Inspired by applications in
chemistry, we illustrate the proposed techniques on a real molecular property
prediction task in the small data regime.
