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 inﬁnity, then we showthat the remaining vertices can be classiﬁed with error converging to Bayes opti-mal using the k -nearest-neighbors classiﬁcation 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 deﬁne D=f( X i , Y i )gas the train-ing set. The goal is to learn a classiﬁer 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
If we suppose that the latent positions are i.i.d. from some distribution, then the latent space approach is closely related to the theory of exchangeable random graphs . For exchangeable graphs, we have a (measurable) link function @math and each vertex is associated with a latent i.i.d. uniform @math random variable denoted @math . Conditioned on the @math , the adjacency of vertices @math and @math is determined by a Bernoulli trial with parameter @math . For a treatment of exchangeable graphs and estimation using the method of moments, see @cite_6 .
@cite_6
2038949443
Probability models on graphs are becoming increasingly important in many applications, but statistical tools for fitting such models are not yet well developed. Here we propose a general method of moments approach that can be used to fit a large class of probability models through empirical counts of certain patterns in a graph. We establish some general asymptotic properties of empirical graph moments and prove consistency of the estimates as the graph size grows for all ranges of the average degree including @math . Additional results are obtained for the important special case of degree distributions.