Poster
Out-of-sample extension of graph adjacency spectral embedding
Keith Levin · Fred Roosta · Michael Mahoney · Carey Priebe

Fri Jul 13th 06:15 -- 09:00 PM @ Hall B #76
in Posters Fri »

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.

Author Information

Keith Levin (University of Michigan)
Fred Roosta (University of Queensland)
Michael Mahoney (UC Berkeley)
Carey Priebe (Johns Hopkins University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors