Efficient Deep Generative Models for Spatial Networks via Spanning Tree Sampler

In the big data era, spatial-network data has become increasingly important and popular in many real-world objects, ranging from micro-scale (e.g., molecule structures), to middle-scale (e.g., biological neural networks), to macro-scale (e.g., mobility networks). Spatial networks consist of nodes and edges that are embedded in a geometric space. Although, it is critical to model and understand the generative process of spatial networks, this task remains largely under-explored due to the significant difficulty in automatically modeling and distinguishing the dependency and relevance among various spatial and network semantic factors. In addition, containing both spatial and network information makes the modeling of spatial networks bear large time and memory cost, especially for large graphs. To address the aforementioned challenges, we first propose a novel objective for joint spatial-network disentangled representation learning from the perspective of information bottleneck as well as a novel progressive optimization algorithm to optimize the intractable objective. Based on this, a Spatial-Network Disentangled Variational Autoencoder (SND-VAE) is proposed to discover the independent and dependent latent factors of spatial and networks. To reduce the time complexity, an efficient version SND-VAE-light is proposed, which is based on a novel Efficient Spatial-Network Message Passing Neural Network (ES-MPNN). Qualitative and quantitative experiments on both synthetic and real-world datasets with various scales of graph size demonstrate the superiority of the proposed model over the state-of-the-arts by up to 66.9% for graph generation and 37.3% for interpretability. In addition, the ES-MPNN is also proved to reduce the time complexity of the encoder in the generative model from cubic to linear growth (The implementation of this work can be found at https://github.com/xguo7/SND-VAE ).