Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees

Graph representation learning is a ubiquitous task in machine learning where\nthe goal is to embed each vertex into a low-dimensional vector space. We\nconsider the bipartite graph and formalize its representation learning problem\nas a statistical estimation problem of parameters in a semiparametric\nexponential family distribution. The bipartite graph is assumed to be generated\nby a semiparametric exponential family distribution, whose parametric component\nis given by the proximity of outputs of two one-layer neural networks, while\nnonparametric (nuisance) component is the base measure. Neural networks take\nhigh-dimensional features as inputs and output embedding vectors. In this\nsetting, the representation learning problem is equivalent to recovering the\nweight matrices. The main challenges of estimation arise from the nonlinearity\nof activation functions and the nonparametric nuisance component of the\ndistribution. To overcome these challenges, we propose a pseudo-likelihood\nobjective based on the rank-order decomposition technique and focus on its\nlocal geometry. We show that the proposed objective is strongly convex in a\nneighborhood around the ground truth, so that a gradient descent-based method\nachieves linear convergence rate. Moreover, we prove that the sample complexity\nof the problem is linear in dimensions (up to logarithmic factors), which is\nconsistent with parametric Gaussian models. However, our estimator is robust to\nany model misspecification within the exponential family, which is validated in\nextensive experiments.\n