Title: Adaptive Estimation of Nonparametric Geometric Graphs,
Abstract: This article studies the recovery of graphons when they are convolution
kernels on compact (symmetric) metric spaces. This case is of particular
interest since it covers the situation where the probability of an edge depends
only on some unknown nonparametric function of the distance between latent
points, referred to as Nonparametric Geometric Graphs (NGG). In this setting,
almost minimax adaptive estimation of NGG is possible using a spectral
procedure combined with a Goldenshluger-Lepski adaptation method. The latent
spaces covered by our framework encompasses (among others) compact symmetric
spaces of rank one, namely real spheres and projective spaces. For these
latter, explicit computations of the eigenbasis and of the model complexity can
be achieved, leading to quantitative non-asymptotic results. The time
complexity of our method scales cubicly in the size of the graph and
exponentially in the regularity of the graphon. Hence, this paper offers an
algorithmically and theoretically efficient procedure to estimate smooth NGG.
As a by product, this paper shows a non-asymptotic concentration result on the
spectrum of integral operators defined by symmetric kernels (not necessarily
positive).