On the Effect of Misspecifying the Embedding Dimension in Low-rank Network Models

As network data has become ubiquitous in the sciences, there has been growing interest in network models whose structure is driven by latent node-level variables in a (typically low-dimensional) latent geometric space. These "latent positions" are often estimated via embeddings, whereby the nodes of a network are mapped to points in Euclidean space so that "similar" nodes are mapped to nearby points. Under certain model assumptions, these embeddings are consistent estimates of the latent positions, but most such results require the embedding dimension to be chosen correctly. Methods for choosing the embedding dimension have been studied extensively, but little is known about the behavior of embeddings when the dimension is misspecified. In this work, we provide a theoretical description of the effects of dimension misspecification under the random dot product graph, a class of latent space network models that includes several widely-used network models, most notably the stochastic blockmodel, as special cases. We show that when the dimension is chosen too large, consistent estimation still holds, albeit at a slower rate than when the embedding dimension is chosen correctly. On the other hand, when the dimension is chosen too small, there is a fundamental estimation error lower bound that need not go to zero in the large-network limit. A range of synthetic data experiments support our theoretical results. Our main technical result, which may be of independent interest, is a generalization of earlier work in random matrix theory showing that all non-signal eigenvectors of a low-rank matrix subject to additive noise are delocalized.

Networks are a useful way to represent data like transportation systems or people’s social interactions. Because they are complicated objects, we often try to represent a network in a simpler form, as a short list of numbers. The problem is that, because our data are noisy, we do not know how the appropriate dimension, that is, how long this list should be. If we use too few entries in our list, we fail to represent our data. If we use too many, we risk being inefficient or capturing uninformative noise in our representation. For example, to describe a photo to someone, you could describe give a one-dimensional sliver of it, but because photos are two-dimensional objects, a single sliver would be an incomplete representation of the photo. You would need to give a two-dimensional example or a three-dimensional printout to accurately describe it. Our work analyzes what happens when someone gets the dimensions of their data wrong, like describing their data as a circle when it is a sphere. Our results say that if you provide enough dimensions to describe the shape of your data, your description of it will be accurate. Consequently, when representing data, it is better to use possibly too many dimensions than too few dimensions.