Statistical inference on random dot product graphs: a survey

Abstract

The random dot product graph (RDPG) is an independent-edge random graph that is analytically tractable and, simultaneously, either encompasses or can successfully approximate a wide range of random graphs, from relatively simple stochastic block models to complex latent position graphs. In this survey paper, we describe a comprehensive paradigm for statistical inference on random dot product graphs, a paradigm centered on spectral embeddings of adjacency and Laplacian matrices. We examine the analogues, in graph inference, of several canonical tenets of classical Euclidean inference: in particular, we summarize a body of existing results on the consistency and asymptotic normality of the adjacency and Laplacian spectral embeddings, and the role these spectral embeddings can play in the construction of single- and multi-sample hypothesis tests for graph data. We investigate several real-world applications, including community detection and classification in large social networks and the determination of functional and biologically relevant network properties from an exploratory data analysis of the Drosophila connectome. We outline requisite background and current open problems in spectral graph inference.

arXiv commentAn expository survey paper on a comprehensive paradigm for inference for random dot product graphs, centered on graph adjacency and Laplacian spectral embeddings. Paper outlines requisite background; summarizes theory, methodology, and applications from previous and ongoing work; and closes with a discussion of several open problems

References in corpus (12)

• Modularity and community structure in networks
• Community detection in graphs
• Stochastic blockmodels and community structure in networks
• Spectral redemption: clustering sparse networks
• Matrix estimation by Universal Singular Value Thresholding
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
• A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference
• A nonparametric two-sample hypothesis testing problem for random dot product graphs
• Vertex nomination schemes for membership prediction
• Laplacian Eigenmaps from Sparse, Noisy Similarity Measurements
• On the Incommensurability Phenomenon

Cited by in corpus (26)

• Principled approach to the selection of the embedding dimension of networks
• The impossibility of low rank representations for triangle-rich complex networks
• Learning by Unsupervised Nonlinear Diffusion
• Interpretable brain age prediction using linear latent variable models of functional connectivity
• Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence
• Revisiting Chernoff Information with Likelihood Ratio Exponential Families
• Network cross-validation by edge sampling
• Network Representation Using Graph Root Distributions
• Mutually exciting point process graphs for modelling dynamic networks
• Link prediction in dynamic networks using random dot product graphs
• A generalized hypothesis test for community structure in networks
• A Multivariate Extreme Value Theory Approach to Anomaly Clustering and Visualization
• Stratified stochastic variational inference for high-dimensional network factor model
• Online Change Point Detection for Weighted and Directed Random Dot Product Graphs
• A Simple Spectral Failure Mode for Graph Convolutional Networks
• Graph link prediction in computer networks using Poisson matrix factorisation
• Unseeded low-rank graph matching by transform-based unsupervised point registration
• Bias-Variance Tradeoffs in Joint Spectral Embeddings
• Singular value distribution of dense random matrices with block Markovian dependence
• Latent structure blockmodels for Bayesian spectral graph clustering
• Multiscale Comparative Connectomics
• Co-factor analysis of citation networks
• Consistent Spectral Clustering of Network Block Models under Local Differential Privacy
• Vertex Classification on Weighted Networks
• CALF-SBM: A Covariate-Assisted Latent Factor Stochastic Block Model
• Valid Two-Sample Graph Testing via Optimal Transport Procrustes and Multiscale Graph Correlation with Applications in Connectomics