Out-of-sample Extension for Latent Position Graphs
We consider the problem of vertex classification for graphs constructed from the latent position model. It was shown previously that the approach of embedding the graphs into some Euclidean space followed by classification in that space can yields a universally consistent vertex classifier. However, a major technical difficulty of the approach arises when classifying unlabeled out-of-sample vertices without including them in the embedding stage. In this paper, we studied the out-of-sample extension for the graph embedding step and its impact on the subsequent inference tasks. We show that, under the latent position graph model and for sufficiently large $n$, the mapping of the out-of-sample vertices is close to its true latent position. We then demonstrate that successful inference for the out-of-sample vertices is possible.
Code (0)
등록된 구현이 없습니다.
Tasks
General ClassificationGraph EmbeddingPositionSimilar Papers 제목 키워드 기반
Intensity Dot Product Graphs
Latent-position random graph models usually treat the node set as fixed once the sample size is chosen, while graphon-based and random-measure constructions allow more randomness at the cost of weaker geometric interpret…
Limit theorems for out-of-sample extensions of the adjacency and Laplacian spectral embeddings
Graph embeddings, a class of dimensionality reduction techniques designed for relational data, have proven useful in exploring and modeling network structure. Most dimensionality reduction methods allow out-of-sample ext…
Dimensionality ReductionGraph EmbeddingStochastic Block ModelOut-of-sample extension of graph adjacency spectral embedding
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 t…
Dimensionality ReductionPositionSemisupervised regression in latent structure networks on unknown manifolds
Random graphs are increasingly becoming objects of interest for modeling networks in a wide range of applications. Latent position random graph models posit that each node is associated with a latent position vector, and…
Graph EmbeddingPositionregressionBayesian Nonparametric Models on Decomposable Graphs
Over recent years Dirichlet processes and the associated Chinese restaurant process (CRP) have found many applications in clustering while the Indian buffet process (IBP) is increasingly used to describe latent feature m…
Clustering