Universally Consistent Latent Position Estimation and Vertex Classification for Random Dot Product Graphs
This provides a method for vertex classification in graph data, but it is incremental as it builds on existing eigen-decomposition techniques for random dot product graphs.
The authors tackled the problem of estimating latent positions and classifying vertices in random dot product graphs, showing that eigen-decomposition of the adjacency matrix yields consistent estimation and that k-nearest-neighbors classification achieves error converging to Bayes optimal when class labels are available for many vertices.
In this work we show that, using the eigen-decomposition of the adjacency matrix, we can consistently estimate latent positions for random dot product graphs provided the latent positions are i.i.d. from some distribution. If class labels are observed for a number of vertices tending to infinity, then we show that the remaining vertices can be classified with error converging to Bayes optimal using the $k$-nearest-neighbors classification rule. We evaluate the proposed methods on simulated data and a graph derived from Wikipedia.