Learning Submanifolds for Subsequent Inference on Random Dot Product Graphs, Part 1: Theory

Statistical inference on networks often relies on latent position models, such as Random Dot Product Graphs (RDPGs). While standard methods assume latent positions exist in a Euclidean space, many real-world networks exhibit structure constrained to a low-dimensional manifold. This paper addresses the challenge of performing statistical inference when this support manifold is unknown, proposing a semisupervised approach that leverages auxiliary data to learn the manifold's geometry.

The authors develop a framework where auxiliary data points are used to approximate the Riemannian distance on the unknown manifold. Their method involves three main steps: estimating latent positions using Adjacency Spectral Embedding (ASE), constructing a dissimilarity matrix based on shortest-path distances on a localization graph (a technique adapted from Isomap), and embedding these dissimilarities into a low-dimensional Euclidean space using a modified multidimensional scaling approach. They evaluate three embedding strategies—Partial Graph Embedding, Complete Graph Embedding, and Complete Graph Embedding with Approximate Lipschitz Embedding—to map the graph data into a space where standard, isometrically invariant decision rules can be applied.

The study provides a rigorous theoretical analysis of how these semisupervised decision rules behave as the amount of auxiliary data grows. The authors demonstrate that, under appropriate conditions, the estimated dissimilarity functions converge in ratio to the true Riemannian distance on the manifold. Consequently, the risk of the proposed semisupervised decision rule converges to the risk of an oracle rule that possesses perfect knowledge of the manifold's Euclidean structure. This confirms that if the manifold structure is beneficial for inference, it is possible to learn that structure sufficiently well from auxiliary data to capture those benefits.