research-article

Public Access

Deep Generative Models for Spatial Networks

Authors:

Liang ZhaoAuthors Info & Claims

KDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining

Pages 505 - 515

https://doi.org/10.1145/3447548.3467394

Published: 14 August 2021 Publication History

Abstract

Spatial networks represent crucial data structures where the nodes and edges are embedded in a geometric space. Nowadays, spatial network data is becoming increasingly popular and important, ranging from microscale (e.g., protein structures), to middle-scale (e.g., biological neural networks), to macro-scale (e.g., mobility networks). Although, modeling and understanding the generative process of spatial networks are very important, they remain largely under-explored due to the significant challenges in automatically modeling and distinguishing the independency and correlation among various spatial and network factors. To address these challenges, we first propose a novel objective for joint spatial-network disentanglement from the perspective of information bottleneck as well as a novel optimization algorithm to optimize the intractable objective. Based on this, a spatial-network variational autoencoder (SND-VAE) with a new spatial-network message passing neural network (S-MPNN) is proposed to discover the independent and dependent latent factors of spatial and networks. Qualitative and quantitative experiments on both synthetic and real-world datasets 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.

Supplementary Material

MP4 File (video.mp4)

Presentation video.

Download
35.05 MB

References

[1]

Farras Abdelnour, Michael Dayan, and Orrin et al. Devinsky. 2018. Functional brain connectivity is predictable from anatomic network's Laplacian eigen-structure. NeuroImage, Vol. 172 (2018), 728--739.

[2]

Alexander A Alemi, Ian Fischer, Joshua V Dillon, and Kevin Murphy. 2016. Deep variational information bottleneck. arXiv preprint arXiv:1612.00410 (2016).

[3]

Namrata Anand and Po-Ssu Huang. 2018. Generative modeling for protein structures. In NeurIPS. 7505--7516.

[4]

Tristan Aumentado-Armstrong, Stavros Tsogkas, Allan Jepson, and Sven Dickinson. 2019. Geometric disentanglement for generative latent shape models. In ICCV. 8181--8190.

[5]

Marc Barthélemy. 2011. Spatial networks. Physics Reports, Vol. 499, 1--3 (2011), 1--101.

[6]

Yoshua Bengio, Aaron Courville, and Pascal Vincent. 2013. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, Vol. 35, 8 (2013), 1798--1828.

Digital Library

[7]

Milan Bradonjić, Aric Hagberg, and Allon G Percus. 2007. Giant component and connectivity in geographical threshold graphs. In International Workshop on Algorithms and Models for the Web-Graph. Springer, 209--216.

[8]

Christopher P Burgess, Irina Higgins, and Arka et al. Pal. 2018. Understanding disentangling in β-VAE. arXiv preprint arXiv:1804.03599 (2018).

[9]

Daniel T Chang. 2020. Geometric Graph Representations and Geometric Graph Convolutions for Deep Learning on Three-Dimensional (3D) Graphs. arXiv preprint arXiv:2006.01785 (2020).

[10]

Ricky TQ Chen, Xuechen Li, Roger B Grosse, and David K Duvenaud. 2018. Isolating sources of disentanglement in variational autoencoders. In NeurIPS. 2610--2620.

[11]

Hyeoncheol Cho and Insung S Choi. 2018. Three-dimensionally embedded graph convolutional network (3dgcn) for molecule interpretation. arXiv preprint arXiv:1811.09794 (2018).

[12]

Christopher B Choy, Danfei Xu, and JunYoung et al. Gwak. 2016. 3d-r2n2: A unified approach for single and multi-view 3d object reconstruction. In European conference on computer vision. Springer, 628--644.

[13]

Tomasz Danel, Przemysław Spurek, and Jacek et al Tabor. 2019. Spatial Graph Convolutional Networks. arXiv preprint arXiv:1909.05310 (2019).

[14]

Yuanqi Du, Xiaojie Guo, Amarda Shehu, and Liang Zhao. 2020. Interpretable Molecule Generation via Disentanglement Learning. In Proceedings of the 11th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics. 1--8.

Digital Library

[15]

Anastasia Dubrovina, Fei Xia, and Panos et al. Achlioptas. 2019. Composite shape modeling via latent space factorization. In Proceedings of the IEEE/CVF International Conference on Computer Vision. 8140--8149.

[16]

Aditya Grover, Aaron Zweig, and Stefano Ermon. 2019. Graphite: Iterative Generative Modeling of Graphs. In ICML. 2434--2444.

[17]

Xiaojie Guo, Yuanqi Du, and Liang Zhao. 2021. Property Controllable Variational Auto-encoder via Invertible Mutual Dependence. In ICLR.

[18]

Xiaojie Guo, Sivani Tadepalli, Liang Zhao, and Amarda Shehu. 2020 a. Generating tertiary protein structures via an interpretative variational autoencoder. arXiv preprint arXiv:2004.07119 (2020).

[19]

Xiaojie Guo, Lingfei Wu, and Liang Zhao. 2018. Deep graph translation. arXiv preprint arXiv:1805.09980 (2018).

[20]

Xiaojie Guo and Liang Zhao. 2020. A systematic survey on deep generative models for graph generation. arXiv preprint arXiv:2007.06686 (2020).

[21]

Xiaojie Guo, Liang Zhao, and et al. 2019. Deep Multi-attributed Graph Translation with Node-Edge Co-evolution. In ICDM.

[22]

Xiaojie Guo, Liang Zhao, and Zhao et al Qin. 2020 b. Interpretable Deep Graph Generation with Node-Edge Co-Disentanglement. In KDD.

[23]

Irina Higgins, Loic Matthey, and Arka et al. Pal. 2017. beta-VAE: Learning Basic Visual Concepts with a Constrained Variational Framework. ICLR, Vol. 2, 5 (2017), 6.

[24]

Dou Huang, Xuan Song, and Zipei et al. Fan. 2019. A variational autoencoder based generative model of urban human mobility. In MIPR. IEEE, 425--430.

[25]

John Ingraham, Vikas Garg, and Regina et al Barzilay. 2019. Generative models for graph-based protein design. In NeurIPS. 15820--15831.

[26]

Hyunjik Kim and Andriy Mnih. 2018. Disentangling by factorising. ICML (2018).

[27]

Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. ICLR (2016).

[28]

Jon Kleinberg. 2000. The small-world phenomenon: An algorithmic perspective. In Proceedings of the thirty-second annual ACM symposium on Theory of computing. 163--170.

Digital Library

[29]

Konstantin Klemmer, Adriano Koshiyama, and Sebastian Flennerhag. 2019. Augmenting correlation structures in spatial data using deep generative models. arXiv preprint arXiv:1905.09796 (2019).

[30]

Johannes Klicpera, Janek Groß, and Stephan Günnemann. 2020. Directional message passing for molecular graphs. arXiv preprint arXiv:2003.03123 (2020).

[31]

Abhishek Kumar, Prasanna Sattigeri, and Avinash Balakrishnan. 2018. Variational Inference of Disentangled Latent Concepts from Unlabeled Observations. In ICLR.

[32]

Jake Levinson, Avneesh Sud, and Ameesh Makadia. 2019. Latent feature disentanglement for 3D meshes. arXiv preprint arXiv:1906.03281 (2019).

[33]

Francesco Locatello, Stefan Bauer, and Mario et al. Lucic. 2019. Challenging Common Assumptions in the Unsupervised Learning of Disentangled Representations. In ICML. 4114--4124.

[34]

Jianxin Ma, Peng Cui, and Kun et al. Kuang. 2019. Disentangled graph convolutional networks. In ICML. 4212--4221.

[35]

Olvi L Mangasarian. 1994. Nonlinear programming. SIAM.

[36]

Charlie Nash and Christopher KI Williams. 2017. The shape variational autoencoder: A deep generative model of part-segmented 3D objects. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 1--12.

[37]

Arun Pandey, Michael Fanuel, and Joachim et al. Schreurs. 2020. Disentangled Representation Learning and Generation with Manifold Optimization. arXiv preprint arXiv:2006.07046 (2020).

[38]

Mathew Penrose et al. 2003. Random geometric graphs. Vol. 5. Oxford university press.

[39]

Taseef Rahman, Yuanqi Du, Liang Zhao, and Amarda Shehu. 2021. Generative Adversarial Learning of Protein Tertiary Structures. Molecules, Vol. 26, 5 (2021), 1209.

[40]

Scott Reed, Kihyuk Sohn, and Yuting et al Zhang. 2014. Learning to disentangle factors of variation with manifold interaction. In ICML. PMLR, 1431--1439.

[41]

Martin Simonovsky and Nikos Komodakis. 2018. Graphvae: Towards generation of small graphs using variational autoencoders. In ICANN. Springer, 412--422.

[42]

Qingyang Tan, Lin Gao, Yu-Kun Lai, and Shihong Xia. 2018. Variational autoencoders for deforming 3d mesh models. In CVPR. 5841--5850.

[43]

Diego Valsesia, Giulia Fracastoro, and Enrico Magli. 2018. Learning localized generative models for 3d point clouds via graph convolution. In ICLR.

[44]

Xiaoyang Wang, Yao Ma, and Yiqiet al. Wang. 2020. Traffic flow prediction via spatial temporal graph neural network. In Proceedings of The Web Conference 2020. 1082--1092.

Digital Library

[45]

Bernard M Waxman. 1988. Routing of multipoint connections. IEEE journal on selected areas in communications, Vol. 6, 9 (1988), 1617--1622.

Digital Library

[46]

Sijie Yan, Yuanjun Xiong, and Dahua Lin. 2018. Spatial temporal graph convolutional networks for skeleton-based action recognition. In AAAI, Vol. 32.

[47]

Jiaxuan You, Rex Ying, and et al. 2018. GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models. In ICML. 5708--5717.

[48]

Liang Zhao. 2021. Event Prediction in the Big Data Era: A Systematic Survey. ACM Comput. Surv., Vol. 54, 5, Article 94 (May 2021), bibinfonumpages37 pages.

Digital Library

Cited By

Wang SDu YGuo XPan BQin ZZhao L(2024)Controllable Data Generation by Deep Learning: A ReviewACM Computing Surveys10.1145/364860956:9(1-38)Online publication date: 25-Apr-2024
https://dl.acm.org/doi/10.1145/3648609
Guo JHuang KZhang RYi X(2024)ES-GNN: Generalizing Graph Neural Networks Beyond Homophily With Edge SplittingIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.345993246:12(11345-11360)Online publication date: Dec-2024
https://doi.org/10.1109/TPAMI.2024.3459932
Zheng LZhou DTong HXu JZhu YHe J(2024)Fairgen: Towards Fair Graph Generation2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00181(2285-2297)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00181
Show More Cited By

Index Terms

Deep Generative Models for Spatial Networks

Recommendations

A Graph-based Approach for Trajectory Similarity Computation in Spatial Networks
KDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining

Trajectory similarity computation is an essential operation in many applications of spatial data analysis. In this paper, we study the problem of trajectory similarity computation over spatial network, where the real distances between objects are ...
Diversity in Deep Generative Models and Generative AI
Machine Learning, Optimization, and Data Science
Abstract
The decoder-based machine learning generative algorithms such as Generative Adversarial Networks (GAN), Variational Auto-Encoders (VAE), Transformers show impressive results when constructing objects similar to those in a training ensemble. ...
Algorithms that Get Old: The Case of Generative Deep Neural Networks
Machine Learning, Optimization, and Data Science
Abstract
Generative deep neural networks used in machine learning, like the Variational Auto-Encoders (VAE), and Generative Adversarial Networks (GANs) produce new objects each time when asked to do so with the constraint that the new objects remain ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining

August 2021

4259 pages

ISBN:9781450383325

DOI:10.1145/3447548

General Chairs:
Feida Zhu
Singapore Management University
,
Beng Chin Ooi
National University of Singapore
,
Chunyan Miao
Nanyang Technology University
,
Program Chairs:
Haixun Wang,
Iryna Skrypnyk,
Wynne Hsu,
Sanjay Chawla

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 August 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Jeffress Memorial Trust Award
Amazon Research Award
National Science Foundation
NVIDIA GPU Grant
Design Knowledge Company

Conference

KDD '21

Sponsor:

KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 14 - 18, 2021

Virtual Event, Singapore

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
1,328
Total Downloads

Downloads (Last 12 months)370
Downloads (Last 6 weeks)50

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang SDu YGuo XPan BQin ZZhao L(2024)Controllable Data Generation by Deep Learning: A ReviewACM Computing Surveys10.1145/364860956:9(1-38)Online publication date: 25-Apr-2024
https://dl.acm.org/doi/10.1145/3648609
Guo JHuang KZhang RYi X(2024)ES-GNN: Generalizing Graph Neural Networks Beyond Homophily With Edge SplittingIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.345993246:12(11345-11360)Online publication date: Dec-2024
https://doi.org/10.1109/TPAMI.2024.3459932
Zheng LZhou DTong HXu JZhu YHe J(2024)Fairgen: Towards Fair Graph Generation2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00181(2285-2297)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00181
Gao XLi HZhang HXue JSun SLiu W(2024)Traffic prediction based on spatial-temporal disentangled generative modelsInformation Sciences: an International Journal10.1016/j.ins.2024.121142680:COnline publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.121142
Guo XZhao L(2023)A Systematic Survey on Deep Generative Models for Graph GenerationIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2022.321483245:5(5370-5390)Online publication date: 3-Apr-2023
https://dl.acm.org/doi/10.1109/TPAMI.2022.3214832
Hu BWang XFeng ZSong JZhao JSong MWang X(2023)HSDN: A High-Order Structural Semantic Disentangled Neural NetworkIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.320860435:9(8742-8756)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3208604
Zhang YGu SGao YPan BYang XZhao L(2023)MAGI: Multi-Annotated Explanation-Guided Learning2023 IEEE/CVF International Conference on Computer Vision (ICCV)10.1109/ICCV51070.2023.00189(1977-1987)Online publication date: 1-Oct-2023
https://doi.org/10.1109/ICCV51070.2023.00189
Mercatali GFreitas AGarg VKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Symmetry-induced disentanglement on graphsProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602554(31497-31511)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602554
Ling CCao HZhao L(2022)STGEN: Deep Continuous-Time Spatiotemporal Graph GenerationMachine Learning and Knowledge Discovery in Databases10.1007/978-3-031-26409-2_21(340-356)Online publication date: 19-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-26409-2_21
Xu DCheng WLuo DChen HZhang XRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)InfoGCLProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3542588(30414-30425)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3542588
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten