{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T14:58:37Z","timestamp":1766156317553,"version":"3.48.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"National Science Foundation","award":["No. 1755850, No. 1841520, No. 2007716, No. 2007976, No. 1942594, No. 1907805"],"award-info":[{"award-number":["No. 1755850, No. 1841520, No. 2007716, No. 2007976, No. 1942594, No. 1907805"]}]},{"name":"Jeffress Memorial Trust Award, Amazon Research Award, NVIDIA GPU Grant, and Design Knowledge Company","award":["10827.002.120.04"],"award-info":[{"award-number":["10827.002.120.04"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2026,1,31]]},"abstract":"<jats:p>\n                    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\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/xguo7\/SND-VAE\">https:\/\/github.com\/xguo7\/SND-VAE<\/jats:ext-link>\n                    ).\n                  <\/jats:p>","DOI":"10.1145\/3774416","type":"journal-article","created":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T13:28:45Z","timestamp":1762435725000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Deep Generative Models for Spatial Networks via Spanning Tree Sampler"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1946-1179","authenticated-orcid":false,"given":"Xiaojie","family":"Guo","sequence":"first","affiliation":[{"name":"Microsoft, Reston, Virginia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2988-0374","authenticated-orcid":false,"given":"Yuanqi","family":"Du","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-9808-6020","authenticated-orcid":false,"given":"Zheng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Emory University, Atlanta, Georgia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2648-9989","authenticated-orcid":false,"given":"Liang","family":"Zhao","sequence":"additional","affiliation":[{"name":"Emory University, Atlanta, Georgia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,12,19]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.neuroimage.2018.02.016"},{"key":"e_1_3_2_3_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Alemi Alexander A.","year":"2017","unstructured":"Alexander A. Alemi, Ian Fischer, Joshua V. Dillon, and Kevin Murphy. 2017. Deep variational information bottleneck. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_4_2","first-page":"7505","volume-title":"Advances in Neural Information Processing Systems","volume":"31","author":"Anand Namrata","year":"2018","unstructured":"Namrata Anand and Po-Ssu Huang. 2018. Generative modeling for protein structures. In Advances in Neural Information Processing Systems, Vol. 31, 7505\u20137516."},{"key":"e_1_3_2_5_2","first-page":"8181","volume-title":"Proceedings of the International Conference on Computer Vision","author":"Aumentado-Armstrong Tristan","year":"2019","unstructured":"Tristan Aumentado-Armstrong, Stavros Tsogkas, Allan Jepson, and Sven Dickinson. 2019. Geometric disentanglement for generative latent shape models. In Proceedings of the International Conference on Computer Vision, 8181\u20138190."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2010.11.002"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.50"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1287\/orsc.1100.0641"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-3-540-77004-6_18","volume-title":"Proceedings of the International Workshop on Algorithms and Models for the Web-Graph","author":"Bradonji\u0107 Milan","year":"2007","unstructured":"Milan Bradonji\u0107, Aric Hagberg, and Allon G. Percus. 2007. Giant component and connectivity in geographical threshold graphs. In Proceedings of the International Workshop on Algorithms and Models for the Web-Graph. Springer, 209\u2013216."},{"key":"e_1_3_2_10_2","unstructured":"Christopher P. Burgess Irina Higgins Arka Pal Loic Matthey Nick Watters Guillaume Desjardins and Alexander Lerchner. 2018. Understanding disentangling in \\(\\beta\\) -VAE. arXiv:1804.03599. Retrieved from https:\/\/arxiv.org\/abs\/1804.03599"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989121"},{"issue":"3","key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0097-3165(78)90067-5","article-title":"Matrix tree theorems","volume":"24","author":"Chaiken Seth","year":"1978","unstructured":"Seth Chaiken and Daniel J. Kleitman. 1978. Matrix tree theorems. Journal of Combinatorial Theory, Series A 24, 3 (1978), 377\u2013381.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"e_1_3_2_13_2","unstructured":"Daniel T. Chang. 2020. Geometric graph representations and geometric graph convolutions for deep learning on three-dimensional (3D) graphs. arXiv:2006.01785. Retrieved from https:\/\/arxiv.org\/abs\/2006.01785"},{"key":"e_1_3_2_14_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Chen Jie","year":"2018","unstructured":"Jie Chen, Tengfei Ma, and Cao Xiao. 2018. FastGCN: Fast learning with graph convolutional networks via importance sampling. In Proceedings of the International Conference on Learning Representations. International Conference on Learning Representations."},{"key":"e_1_3_2_15_2","first-page":"942","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Chen Jianfei","year":"2018","unstructured":"Jianfei Chen, Jun Zhu, and Le Song. 2018. Stochastic training of graph convolutional networks with variance reduction. In Proceedings of the International Conference on Machine Learning. PMLR, 942\u2013950."},{"key":"e_1_3_2_16_2","first-page":"2610","volume-title":"Advances in Neural Information Processing Systems","volume":"31","author":"Chen Ricky T. Q.","year":"2018","unstructured":"Ricky T. Q. Chen, Xuechen Li, Roger B. Grosse, and David K. Duvenaud. 2018. Isolating sources of disentanglement in variational autoencoders. In Advances in Neural Information Processing Systems, Vol. 31, 2610\u20132620."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/3618408.3618589"},{"key":"e_1_3_2_18_2","unstructured":"Hyeoncheol Cho and Insung S. Choi. 2018. Three-dimensionally embedded graph convolutional network (3DGCN) for molecule interpretation. arXiv:1811.09794. Retrieved from https:\/\/arxiv.org\/abs\/1811.09794"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46484-8_38"},{"key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1007\/978-3-030-63823-8_76","volume-title":"Proceedings of the International Conference on Neural Information Processing","author":"Danel Tomasz","year":"2020","unstructured":"Tomasz Danel, Przemys\u0142aw Spurek, Jacek Tabor, Marek \u015amieja, \u0141ukasz Struski, Agnieszka S\u0142owik, and \u0141ukasz Maziarka. 2020. Spatial graph convolutional networks. In Proceedings of the International Conference on Neural Information Processing. Springer, 668\u2013675."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3388440.3414709"},{"key":"e_1_3_2_22_2","first-page":"8140","volume-title":"Proceedings of the IEEE\/CVF International Conference on Computer Vision","author":"Dubrovina Anastasia","year":"2019","unstructured":"Anastasia Dubrovina, Fei Xia, Panos Achlioptas, Mira Shalah, Raphael Groscot, and Leonidas J. Guibas. 2019. Composite shape modeling via latent space factorization. In Proceedings of the IEEE\/CVF International Conference on Computer Vision, 8140\u20138149."},{"key":"e_1_3_2_23_2","first-page":"2434","volume-title":"Proceedings of the 36th International Conference on Machine Learning","author":"Grover Aditya","year":"2019","unstructured":"Aditya Grover, Aaron Zweig, and Stefano Ermon. 2019. Graphite: Iterative generative modeling of graphs. In Proceedings of the 36th International Conference on Machine Learning, 2434\u20132444."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioadv\/vbab036"},{"key":"e_1_3_2_25_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Guo Xiaojie","year":"2021","unstructured":"Xiaojie Guo, Yuanqi Du, and Liang Zhao. 2021. Property controllable variational auto-encoder via invertible mutual dependence. In Proceedings of the International Conference on Learning Representations."},{"issue":"11","key":"e_1_3_2_26_2","first-page":"8225","article-title":"Deep graph translation","volume":"34","author":"Guo Xiaojie","year":"2022","unstructured":"Xiaojie Guo, Lingfei Wu, and Liang Zhao. 2022. Deep graph translation. IEEE Transactions on Neural Networks and Learning Systems 34, 11 (2022), 8225\u20138234.","journal-title":"IEEE Transactions on Neural Networks and Learning Systems"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2022.3214832"},{"key":"e_1_3_2_28_2","volume-title":"Proceedings of the 2019 IEEE International Conference on Data Mining","author":"Guo Xiaojie","year":"2019","unstructured":"Xiaojie Guo, Liang Zhao, Cameron Nowzari, Setareh Rafatirad, Houman Homayoun, and Sai Manoj Pudukotai Dinakarrao. 2019. Deep multi-attributed graph translation with node-edge co-evolution. In Proceedings of the 2019 IEEE International Conference on Data Mining."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403221"},{"key":"e_1_3_2_30_2","volume-title":"Exploring Network Structure, Dynamics, and Function Using Network X","author":"Hagberg Aric","year":"2008","unstructured":"Aric Hagberg, Pieter Swart, and Daniel S. Chult. 2008. Exploring Network Structure, Dynamics, and Function Using Network X. Technical Report. Los Alamos National Lab, Los Alamos, NM, USA."},{"key":"e_1_3_2_31_2","first-page":"1","article-title":"Inductive representation learning on large graphs","volume":"30","author":"Hamilton Will","year":"2017","unstructured":"Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, Vol. 30, 1\u201311.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_32_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Higgins Irina","year":"2017","unstructured":"Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. 2017. beta-VAE: Learning basic visual concepts with a constrained variational framework. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_33_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Higgins Irina","year":"2022","unstructured":"Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. 2022. beta-VAE: Learning basic visual concepts with a constrained variational framework. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/MIPR.2019.00086"},{"key":"e_1_3_2_35_2","first-page":"15820","article-title":"Generative models for graph-based protein design","volume":"32","author":"Ingraham John","year":"2019","unstructured":"John Ingraham, Vikas Garg, Regina Barzilay, and Tommi Jaakkola. 2019. Generative models for graph-based protein design. In Advances in Neural Information Processing Systems, Vol. 32, 15820\u201315831.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_36_2","first-page":"10362","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Jo Jaehyeong","year":"2022","unstructured":"Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. 2022. Score-based generative modeling of graphs via the system of stochastic differential equations. In Proceedings of the International Conference on Machine Learning. PMLR, 10362\u201310383."},{"key":"e_1_3_2_37_2","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Kim Hyunjik","year":"2018","unstructured":"Hyunjik Kim and Andriy Mnih. 2018. Disentangling by factorising. In Proceedings of the International Conference on Machine Learning."},{"key":"e_1_3_2_38_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Kipf Thomas N.","year":"2016","unstructured":"Thomas N. Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_3_2_40_2","unstructured":"Konstantin Klemmer Adriano Koshiyama and Sebastian Flennerhag. 2019. Augmenting correlation structures in spatial data using deep generative models. arXiv:1905.09796. Retrieved from https:\/\/arxiv.org\/abs\/1905.09796"},{"key":"e_1_3_2_41_2","first-page":"1","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Klicpera Johannes","year":"2020","unstructured":"Johannes Klicpera, Janek Gro\u00df, and Stephan G\u00fcnnemann. 2020. Directional message passing for molecular graphs. In Proceedings of the International Conference on Learning Representations, 1\u201313."},{"key":"e_1_3_2_42_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Kumar Abhishek","year":"2018","unstructured":"Abhishek Kumar, Prasanna Sattigeri, and Avinash Balakrishnan. 2018. Variational inference of disentangled latent concepts from unlabeled observations. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_43_2","unstructured":"Jake Levinson Avneesh Sud and Ameesh Makadia. 2019. Latent feature disentanglement for 3D meshes. arXiv:1906.03281. Retrieved from https:\/\/arxiv.org\/abs\/1906.03281"},{"key":"e_1_3_2_44_2","first-page":"4114","volume-title":"Proceedings of the 36th International Conference on Machine Learning","author":"Locatello Francesco","year":"2019","unstructured":"Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Raetsch, Sylvain Gelly, Bernhard Sch\u00f6lkopf, and Olivier Bachem. 2019. Challenging common assumptions in the unsupervised learning of disentangled representations. In Proceedings of the 36th International Conference on Machine Learning, 4114\u20134124."},{"key":"e_1_3_2_45_2","first-page":"4212","volume-title":"Proceedings of the 36th International Conference on Machine Learning","author":"Ma Jianxin","year":"2019","unstructured":"Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, and Wenwu Zhu. 2019. Disentangled graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, 4212\u20134221."},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971255"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13240"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1162\/neco_a_01528"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2019.00025"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.3390\/molecules26051209"},{"key":"e_1_3_2_52_2","first-page":"1431","volume-title":"Proceedings of the 31st International Conference on Machine Learning","author":"Reed Scott","year":"2014","unstructured":"Scott Reed, Kihyuk Sohn, Yuting Zhang, and Honglak Lee. 2014. Learning to disentangle factors of variation with manifold interaction. In Proceedings of the 31st International Conference on Machine Learning. PMLR, 1431\u20131439."},{"key":"e_1_3_2_53_2","first-page":"412","volume-title":"Proceedings of the International Conference on Artificial Neural Networks","author":"Simonovsky Martin","year":"2018","unstructured":"Martin Simonovsky and Nikos Komodakis. 2018. GraphVAE: Towards generation of small graphs using variational autoencoders. In Proceedings of the International Conference on Artificial Neural Networks. Springer, 412\u2013422."},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00612"},{"key":"e_1_3_2_55_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Valsesia Diego","year":"2018","unstructured":"Diego Valsesia, Giulia Fracastoro, and Enrico Magli. 2018. Learning localized generative models for 3D point clouds via graph convolution. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380186"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/49.12889"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.12328"},{"key":"e_1_3_2_59_2","first-page":"5708","volume-title":"Proceedings of the 35th International Conference on Machine Learning","author":"You Jiaxuan","year":"2018","unstructured":"Jiaxuan You and Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. 2018. GraphRNN: Generating realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference on Machine Learning, 5708\u20135717."},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3450287"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3774416","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T14:54:46Z","timestamp":1766156086000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3774416"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,19]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1,31]]}},"alternative-id":["10.1145\/3774416"],"URL":"https:\/\/doi.org\/10.1145\/3774416","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2025,12,19]]},"assertion":[{"value":"2024-09-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-20","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}