Out-of-sample extension of graph adjacency spectral embedding
This work addresses the need for out-of-sample extensions in graph embedding methods, which is incremental as it builds on existing spectral embedding techniques.
The paper tackles the problem of extending adjacency spectral embedding to out-of-sample vertices in graphs, presenting two approaches (least-squares and maximum-likelihood) and showing that under a random dot product graph model, both achieve the same error rate for estimating latent positions, with a central limit theorem proven for the least-squares method.
Many popular dimensionality reduction procedures have out-of-sample extensions, which allow a practitioner to apply a learned embedding to observations not seen in the initial training sample. In this work, we consider the problem of obtaining an out-of-sample extension for the adjacency spectral embedding, a procedure for embedding the vertices of a graph into Euclidean space. We present two different approaches to this problem, one based on a least-squares objective and the other based on a maximum-likelihood formulation. We show that if the graph of interest is drawn according to a certain latent position model called a random dot product graph, then both of these out-of-sample extensions estimate the true latent position of the out-of-sample vertex with the same error rate. Further, we prove a central limit theorem for the least-squares-based extension, showing that the estimate is asymptotically normal about the truth in the large-graph limit.