Joint Embedding of Graphs
arXiv:1703.03862 · doi:10.1109/TPAMI.2019.2948619
Abstract
Feature extraction and dimension reduction for networks is critical in a wide variety of domains. Efficiently and accurately learning features for multiple graphs has important applications in statistical inference on graphs. We propose a method to jointly embed multiple undirected graphs. Given a set of graphs, the joint embedding method identifies a linear subspace spanned by rank one symmetric matrices and projects adjacency matrices of graphs into this subspace. The projection coefficients can be treated as features of the graphs, while the embedding components can represent vertex features. We also propose a random graph model for multiple graphs that generalizes other classical models for graphs. We show through theory and numerical experiments that under the model, the joint embedding method produces estimates of parameters with small errors. Via simulation experiments, we demonstrate that the joint embedding method produces features which lead to state of the art performance in classifying graphs. Applying the joint embedding method to human brain graphs, we find it extracts interpretable features with good prediction accuracy in different tasks.
References in corpus (13)
- Multilayer Networks
- Stochastic blockmodels and community structure in networks
- Mixed membership stochastic blockmodels
- Spectra of complex networks
- Inferring the mesoscale structure of layered, edge-valued and time-varying networks
- DELTACON: A Principled Massive-Graph Similarity Function
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Consistent estimation of dynamic and multi-layer block models
- Anomaly Detection in Time Series of Graphs using Fusion of Graph Invariants
- Numerical Optimization for Symmetric Tensor Decomposition
- Universally consistent vertex classification for latent positions graphs
- A statistical interpretation of spectral embedding: the generalised random dot product graph
- Connectome Smoothing via Low-rank Approximations
Cited by in corpus (12)
- Inference for multiple heterogeneous networks with a common invariant subspace
- The multilayer random dot product graph
- The Multiple Random Dot Product Graph Model
- Clustering of heterogeneous populations of networks
- Compressing network populations with modal networks reveals structural diversity
- Link prediction in dynamic networks using random dot product graphs
- Connectome Smoothing via Low-rank Approximations
- The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks
- Optimal Bayesian Estimation for Random Dot Product Graphs
- Simultaneous prediction and community detection for networks with application to neuroimaging
- Community Detection in Weighted Multilayer Networks with Ambient Noise
- Maximum a Posteriori Inference of Random Dot Product Graphs via Conic Programming