Out-of-sample Extension for Latent Position Graphs
Out-of-sample Extension for Latent Position Graphs
复制标题
潜在位置图的样本外扩展
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
C. Priebe
中科院分区：
文献类型：
--
作者：
M. Tang;Youngser Park;C. Priebe
我们考虑了由潜在位置模型构造的图的顶点分类问题。以前已经证明，将图嵌入到某个欧几里德空间中，然后在该空间中进行分类的方法可以产生一个普遍一致的顶点分类器。然而，当对未标记的样本外顶点进行分类而不将它们包括在嵌入阶段时，该方法出现了主要的技术困难。本文研究了图嵌入步骤的样本外扩展及其对后续推理任务的影响。我们证明了，在潜在位置图模型下，对于足够大的$n$，超出样本的顶点的映射接近其真实的潜在位置。然后，我们证明了对样本外顶点的成功推断是可能的。
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.