Efficient Deep Generative Models for Spatial Networks via Spanning Tree Sampler
Open Access
- 19 December 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Knowledge Discovery From Data
- Vol. 20 (1) , 1-28
Abstract
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 ).Keywords
Funding Information
- National Science Foundation (No. 1755850, No. 1841520, No. 2007716, No. 2007976, No. 1942594, No. 1907805)
- Jeffress Memorial Trust Award, Amazon Research Award, NVIDIA GPU Grant, and Design Knowledge Company (10827.002.120.04)
This publication has 26 references indexed in Scilit:
- A Systematic Survey on Deep Generative Models for Graph GenerationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2022
- Traffic Flow Prediction via Spatial Temporal Graph Neural Network2020
- Variational Autoencoders for Deforming 3D Mesh Models2018
- Functional brain connectivity is predictable from anatomic network's Laplacian eigen-structureNeuroImage, 2018
- 3D-R2N2: A Unified Approach for Single and Multi-view 3D Object Reconstruction2016
- Spatial networksPhysics Reports, 2011
- The small-world phenomenon2000
- Nonlinear Programming1994
- Routing of multipoint connectionsIEEE Journal on Selected Areas in Communications, 1988
- Matrix Tree TheoremsJournal of Combinatorial Theory, Series A, 1978