Universally Consistent Latent Position Estimation and Vertex Classification for Random Dot Product Graphs

Abstract In this work we show that, using the eigen-decomposition of the adjacencymatrix, we can consistently estimate latent positions for random dot productgraphs provided the latent positions are i.i.d. from some distribution. If classlabels are observed for a number of vertices tending to infinity, then we showthat the remaining vertices can be classified with error converging to Bayes opti-mal using the k -nearest-neighbors classification rule. We evaluate the proposedmethods on simulated data and a graph derived from Wikipedia. 1 Introduction The classical statistical pattern recognition setting involves( X , Y ),( X 1 , Y 1 ),...,( X n , Y n ) i . i˘ . d . F X , Y ,where the X i : 7!R d are observed feature vectors and the Y i : 7!f0,1gare ob-served class labels for some probability space . We define D=f( X i , Y i )gas the train-ing set. The goal is to learn a classifier h (;D): R d !f0,1gsuch that the probability oferror P[ h ( X ;D)6= Y jD]approaches Bayes optimal as n !1for all distributions