Abstract
The Random Dot Product Graph (RDPG) is a generative model for relationaldata, where nodes are represented via latent vectors in low-dimensionalEuclidean space. RDPGs crucially postulate that edge formation probabilitiesare given by the dot product of the corresponding latent positions.Accordingly, the embedding task of estimating these vectors from an observedgraph is typically posed as a low-rank matrix factorization problem. Theworkhorse Adjacency Spectral Embedding (ASE) enjoys solid statisticalproperties, but it is formally solving a surrogate problem and can becomputationally intensive. In this paper, we bring to bear recent advances innon-convex optimization and demonstrate their impact to RDPG inference. Weadvocate first-order gradient descent methods to better solve the embeddingproblem, and to organically accommodate broader network embedding applicationsof practical relevance. Notably, we argue that RDPG embeddings of directedgraphs loose interpretability unless the factor matrices are constrained tohave orthogonal columns. We thus develop a novel feasible optimization methodin the resulting manifold. The effectiveness of the graph representationlearning framework is demonstrated on reproducible experiments with bothsynthetic and real network data. Our open-source algorithm implementations arescalable, and unlike the ASE they are robust to missing edge data and can trackslowly-varying latent positions from streaming graphs.