Graph Principal Flow Network for Conditional Graph Generation
Pages 768 - 779
Abstract
Conditional graph generation is crucial and challenging since the conditional distribution of graph topology and feature is complicated and the semantic information is hard to capture by the generative model. In this work, we propose a novel graph conditional generative model, Graph Principal Flow Network (GPrinFlowNet), which enables us to progressively generate high-quality graphs from low- to high-frequency components for a given graph label. We show that GPrinFlowNet follows a coarse-to-fine resolution generation curriculum, which enables it to capture subtle semantic information by generating intermediate graphs with high mutual information relative to the graph label. Extensive experiments and ablation studies showcase that our model achieves state-of-the-art performance compared to existing conditional graph generation models.
Supplemental Material
MP4 File
Supplemental video
- Download
- 8.30 MB
References
[1]
Usman Ahmed, Jerry Chun-Wei Lin, and Gautam Srivastava. 2022. Hyper-graph-based attention curriculum learning using a lexical algorithm for mental health. Pattern Recogn. Lett., Vol. 157, C (may 2022), 135--143. https://doi.org/10.1016/j.patrec.2022.03.018
[2]
Rim Assouel, Mohamed Ahmed, Marwin H Segler, Amir Saffari, and Yoshua Bengio. 2018. Defactor: Differentiable edge factorization-based probabilistic graph generation. arXiv preprint arXiv:1811.09766 (2018).
[3]
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. 2018. Mutual information neural estimation. In International conference on machine learning. PMLR, 531--540.
[4]
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. 2021b. Flow network based generative models for non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, Vol. 34 (2021), 27381--27394.
[5]
Yoshua Bengio, Tristan Deleu, Edward J. Hu, Salem Lahlou, Mo Tiwari, and Emmanuel Bengio. 2021a. GFlowNet Foundations. CoRR, Vol. abs/2111.09266 (2021). showeprint[arXiv]2111.09266 https://arxiv.org/abs/2111.09266
[6]
Gene Cheung, Enrico Magli, Yuichi Tanaka, and Michael K Ng. 2018. Graph spectral image processing. Proc. IEEE, Vol. 106, 5 (2018), 907--930.
[7]
Hyuna Cho, Minjae Jeong, Sooyeon Jeon, Sungsoo Ahn, and Won Hwa Kim. 2023. Multi-resolution Spectral Coherence for Graph Generation with Score-based Diffusion. In Thirty-seventh Conference on Neural Information Processing Systems. https://openreview.net/forum?id=qUlpDjYnsp
[8]
Guanyi Chu, Xiao Wang, Chuan Shi, and Xunqiang Jiang. 2021. CuCo: Graph Representation with Curriculum Contrastive Learning. In International Joint Conference on Artificial Intelligence. https://api.semanticscholar.org/CorpusID:235671564
[9]
Fabrizio Costa and Kurt De Grave. 2010. Fast neighborhood subgraph pairwise distance kernel. In ICML.
[10]
Nicola De Cao and Thomas Kipf. 2018. MolGAN: An implicit generative model for small molecular graphs. arXiv preprint arXiv:1805.11973 (2018).
[11]
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Proceedings of the 30th International Conference on Neural Information Processing Systems (Barcelona, Spain) (NIPS'16). Curran Associates Inc., Red Hook, NY, USA, 3844--3852.
[12]
Tristan Deleu, António Góis, Chris Chinenye Emezue, Mansi Rankawat, Simon Lacoste-Julien, Stefan Bauer, and Yoshua Bengio. 2022. Bayesian Structure Learning with Generative Flow Networks. In The 38th Conference on Uncertainty in Artificial Intelligence. https://openreview.net/forum?id=HElfed8j9g9
[13]
Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen de Bruijne, and Karsten Borgwardt. 2013. Scalable kernels for graphs with continuous attributes. Advances in neural information processing systems, Vol. 26 (2013).
[14]
Chen Gong. 2017. Exploring Commonality and Individuality for Multi-Modal Curriculum Learning. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 31, 1 (Feb. 2017). https://doi.org/10.1609/aaai.v31i1.10774
[15]
Yaowen Gu, Si Zheng, Zidu Xu, Qijin Yin, Liang Li, and Jiao Li. 2022. An efficient curriculum learning-based strategy for molecular graph learning. Briefings in Bioinformatics (04 2022). https://doi.org/10.1093/bib/bbac099
[16]
Xiaojie Guo and Liang Zhao. 2020. A Systematic Survey on Deep Generative Models for Graph Generation. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 45 (2020), 5370--5390. https://api.semanticscholar.org/CorpusID:220514457
[17]
Florentin Guth, Simon Coste, Valentin De Bortoli, and Stéphane Mallat. 2022. Wavelet Score-Based Generative Modeling. ArXiv, Vol. abs/2208.05003 (2022).
[18]
Jonathan Ho and Tim Salimans. 2021. Classifier-Free Diffusion Guidance. In NeurIPS 2021 Workshop on Deep Generative Models and Downstream Applications. https://openreview.net/forum?id=qw8AKxfYbI
[19]
Han Huang, Leilei Sun, Bowen Du, and Weifeng Lv. 2023. Conditional diffusion based on discrete graph structures for molecular graph generation. arXiv preprint arXiv:2301.00427 (2023).
[20]
Moksh Jain, Emmanuel Bengio, Alex Hernandez-Garcia, Jarrid Rector-Brooks, Bonaventure FP Dossou, Chanakya Ajit Ekbote, Jie Fu, Tianyu Zhang, Michael Kilgour, Dinghuai Zhang, et al. 2022. Biological sequence design with gflownets. In International Conference on Machine Learning. PMLR, 9786--9801.
[21]
Bowen Jing, Gabriele Corso, Renato Berlinghieri, and Tommi Jaakkola. 2022. Subspace Diffusion Generative Models. In ECCV.
[22]
Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. 2022a. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference on Machine Learning. PMLR, 10362--10383.
[23]
Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. 2022b. Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations. arXiv preprint arXiv:2202.02514 (2022).
[24]
Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B. Aditya Prakash, and Chao Zhang. 2023. Autoregressive Diffusion Model for Graph Generation. https://openreview.net/forum?id=98J48HZXxd5
[25]
Greg Landrum et al. 2016. RDKit: Open-Source Cheminformatics Software. (2016). http://www.rdkit.org/
[26]
Haoyang Li, Xin Wang, and Wenwu Zhu. 2023. Curriculum Graph Machine Learning: A Survey. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, Edith Elkind (Ed.). International Joint Conferences on Artificial Intelligence Organization, 6674--6682. https://doi.org/10.24963/ijcai.2023/748 Survey Track.
[27]
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. 2018. Learning deep generative models of graphs. arXiv preprint arXiv:1803.03324 (2018).
[28]
Huafeng Liu, Liping Jing, Jingxuan Wen, Pengyu Xu, Jiaqi Wang, Jian Yu, and Michael K Ng. 2021a. Interpretable Deep Generative Recommendation Models. J. Mach. Learn. Res., Vol. 22 (2021), 202--1.
[29]
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. 2019. Graph normalizing flows. In NeurIPS.
[30]
Meng Liu, Keqiang Yan, Bora Oztekin, and Shuiwang Ji. 2021b. GraphEBM: Molecular Graph Generation with Energy-Based Models. In Energy Based Models Workshop - ICLR 2021. https://openreview.net/forum?id=Gc51PtL_zYw
[31]
Qi Liu, Miltiadis Allamanis, Marc Brockschmidt, and Alexander Gaunt. 2018. Constrained graph variational autoencoders for molecule design. Advances in neural information processing systems, Vol. 31 (2018).
[32]
Yue Liu, Xihong Yang, Sihang Zhou, Xinwang Liu, Zhen Wang, Ke Liang, Wenxuan Tu, Liang Li, Jingcan Duan, and Cancan Chen. 2023. Hard Sample Aware Network for Contrastive Deep Graph Clustering. In Proc. of AAAI.
[33]
T. Luo, Z. Mo, and S. Pan. 2023 a. Fast Graph Generation via Spectral Diffusion. IEEE Transactions on Pattern Analysis and Machine Intelligence 01 (dec 2023), 1--12. https://doi.org/10.1109/TPAMI.2023.3344758
[34]
Tianze Luo, Zhanfeng Mo, and Sinno Jialin Pan. 2023 b. Fast graph generation via spectral diffusion. IEEE Transactions on Pattern Analysis and Machine Intelligence (2023).
[35]
Youzhi Luo, Keqiang Yan, and Shuiwang Ji. 2021. Graphdf: A discrete flow model for molecular graph generation. In ICML. 7192--7203.
[36]
Tengfei Ma, Jie Chen, and Cao Xiao. 2018. Constrained generation of semantically valid graphs via regularizing variational autoencoders. In NeurIPS.
[37]
Nikolay Malkin, Moksh Jain, Emmanuel Bengio, Chen Sun, and Yoshua Bengio. 2022. Trajectory balance: Improved credit assignment in GFlowNets. In Advances in Neural Information Processing Systems, Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (Eds.). https://openreview.net/forum?id=5btWTw1vcw1
[38]
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. 2020. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663 (2020).
[39]
Andrei Cristian Nica, Moksh Jain, Emmanuel Bengio, Cheng-Hao Liu, Maksym Korablyov, Michael M Bronstein, and Yoshua Bengio. 2022. Evaluating generalization in gflownets for molecule design. In ICLR2022 Machine Learning for Drug Discovery.
[40]
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. 2020a. Permutation invariant graph generation via score-based generative modeling. In AISTATS. 4474--4484.
[41]
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. 2020b. Permutation invariant graph generation via score-based generative modeling. In International Conference on Artificial Intelligence and Statistics. PMLR, 4474--4484.
[42]
Yassaman Ommi, Matin Yousefabadi, Faezeh Faez, Amirmojtaba Sabour, Mahdieh Soleymani Baghshah, and Hamid R. Rabiee. 2022. CCGG: A Deep Autoregressive Model for Class-Conditional Graph Generation. In Companion Proceedings of the Web Conference 2022 (Virtual Event, Lyon, France) (WWW '22). Association for Computing Machinery, New York, NY, USA, 1092--1098. https://doi.org/10.1145/3487553.3524721
[43]
Ling Pan, Dinghuai Zhang, Aaron Courville, Longbo Huang, and Yoshua Bengio. 2023. Generative Augmented Flow Networks. In The Eleventh International Conference on Learning Representations. https://openreview.net/forum?id=urF_CBK5XC0
[44]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: an imperative style, high-performance deep learning library. Curran Associates Inc., Red Hook, NY, USA.
[45]
Kristina Preuer, Philipp Renz, Thomas Unterthiner, Sepp Hochreiter, and Gunter Klambauer. 2018. Fréchet ChemNet distance: a metric for generative models for molecules in drug discovery. Journal of chemical information and modeling, Vol. 58, 9 (2018), 1736--1741.
[46]
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. 2014. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, Vol. 1, 1 (2014), 1--7.
[47]
Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. 2004. BRENDA, the enzyme database: updates and major new developments. Nucleic acids research, Vol. 32, suppl_1 (2004), D431--D433.
[48]
Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. 2020. Graphaf: a flow-based autoregressive model for molecular graph generation. arXiv preprint arXiv:2001.09382 (2020).
[49]
Jianbo Shi and Jitendra Malik. 1997. Normalized Cuts and Image Segmentation. In Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97) (CVPR '97). IEEE Computer Society, USA, 731.
[50]
Martin Simonovsky and Nikos Komodakis. 2018. Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Learning--ICANN 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4--7, 2018, Proceedings, Part I 27. Springer, 412--422.
[51]
Petru Soviany, Radu Tudor Ionescu, Paolo Rota, and Nicu Sebe. 2022. Curriculum Learning: A Survey. Int. J. Comput. Vision, Vol. 130, 6 (jun 2022), 1526--1565. https://doi.org/10.1007/s11263-022-01611-x
[52]
Nidhi Vakil and Hadi Amiri. 2023. Curriculum Learning for Graph Neural Networks: A Multiview Competence-based Approach. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (Eds.). Association for Computational Linguistics, Toronto, Canada, 7036--7051. https://doi.org/10.18653/v1/2023.acl-long.389
[53]
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. 2023. DiGress: Discrete Denoising diffusion for graph generation. In The Eleventh International Conference on Learning Representations. https://openreview.net/forum?id=UaAD-Nu86WX
[54]
Hao Wang, Tong Xu, Qi Liu, Defu Lian, Enhong Chen, Dongfang Du, Han Wu, and Wen Su. 2019. MCNE: an end-to-end framework for learning multiple conditional network representations of social network. In KDD. 1064--1072.
[55]
Hui Wang, Kun Zhou, Xin Zhao, Jingyuan Wang, and Ji-Rong Wen. 2023. Curriculum Pre-training Heterogeneous Subgraph Transformer for Top-N Recommendation. ACM Trans. Inf. Syst., Vol. 41, 1, Article 19 (jan 2023), 28 pages. https://doi.org/10.1145/3528667
[56]
Carl Yang, Peiye Zhuang, Wenhan Shi, Alan Luu, and Li Pan. 2019. Conditional structure generation through graph variational generative adversarial nets. In NeurIPS.
[57]
Yiding Yang, Zunlei Feng, Mingli Song, and Xinchao Wang. 2020. Factorizable graph convolutional networks. In NeurIPS. 20286--20296.
[58]
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. 2018. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (London, United Kingdom) (KDD '18). Association for Computing Machinery, New York, NY, USA, 974--983. https://doi.org/10.1145/3219819.3219890
[59]
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. 2018. Graphrnn: Generating realistic graphs with deep auto-regressive models. In ICML. 5708--5717.
[60]
Chengxi Zang and Fei Wang. 2020. MoFlow: an invertible flow model for generating molecular graphs. In KDD. 617--626.
[61]
Hector Zenil, Narsis A Kiani, and Jesper Tegnér. 2015. Numerical investigation of graph spectra and information interpretability of eigenvalues. In Bioinformatics and Biomedical Engineering: Third International Conference, IWBBIO 2015, Granada, Spain, April 15--17, 2015. Proceedings, Part II 3. Springer, 395--405.
[62]
Dinghuai Zhang, Ricky TQ Chen, Nikolay Malkin, and Yoshua Bengio. 2022a. Unifying generative models with gflownets. arXiv preprint arXiv:2209.02606 (2022).
[63]
Dinghuai Zhang, Ricky T. Q. Chen, Nikolay Malkin, and Yoshua Bengio. 2022b. Unifying Generative Models with GFlowNets. ArXiv, Vol. abs/2209.02606 (2022).
[64]
Dinghuai Zhang, Nikolay Malkin, Zhen Liu, Alexandra Volokhova, Aaron Courville, and Yoshua Bengio. 2022c. Generative Flow Networks for Discrete Probabilistic Modeling. In Proceedings of the 39th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 162), Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (Eds.). PMLR, 26412--26428. https://proceedings.mlr.press/v162/zhang22v.html
[65]
Dinghuai Zhang, Nikolay Malkin, Zhen Liu, Alexandra Volokhova, Aaron Courville, and Yoshua Bengio. 2022d. Generative flow networks for discrete probabilistic modeling. In International Conference on Machine Learning. PMLR, 26412--26428.
[66]
Dawei Zhou, Lecheng Zheng, Dongqi Fu, Jiawei Han, and Jingrui He. 2022. MentorGNN: Deriving Curriculum for Pre-Training GNNs. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management (Atlanta, GA, USA) (CIKM '22). Association for Computing Machinery, New York, NY, USA, 2721--2731. https://doi.org/10.1145/3511808.3557393
[67]
Yanqiao Zhu, Yuanqi Du, Yinkai Wang, Yichen Xu, Jieyu Zhang, Qiang Liu, and Shu Wu. 2022. A survey on deep graph generation: Methods and applications. arXiv preprint arXiv:2203.06714 (2022).
Index Terms
- Graph Principal Flow Network for Conditional Graph Generation
Recommendations
Exhaustive generation of k‐critical H‐free graphs
AbstractWe describe an algorithm for generating all k‐critical H‐free graphs, based on a method of Hoàng et al. A graph G is k‐critical H‐free if G is H‐free, k‐chromatic, and every H‐free proper subgraph of G is k−1‐colorable. Using this algorithm, we ...
Conditional fault hamiltonian connectivity of the complete graph
A path in G is a hamiltonian path if it contains all vertices of G. A graph G is hamiltonian connected if there exists a hamiltonian path between any two distinct vertices of G. The degree of a vertex u in G is the number of vertices of G adjacent to u. ...
Exhaustive Generation of k-Critical $${\mathcal H}$$-Free Graphs
WG 2016: Revised Selected Papers of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science - Volume 9941We describe an algorithm for generating all k-critical $${\mathcal H}$$-free graphs, based on a method of Hoíng et al. Using this algorithm, we prove that there are only finitely many 4-critical $$P_7,C_k$$-free graphs, for both $$k=4$$ and $$k=5$$. We ...
Comments
Information & Contributors
Information
Published In
May 2024
4826 pages
ISBN:9798400701719
DOI:10.1145/3589334
- General Chairs:
- Tat-Seng Chua,
- Chong-Wah Ngo,
- Proceedings Chair:
- Roy Ka-Wei Lee,
- Program Chairs:
- Ravi Kumar,
- Hady W. Lauw
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 May 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
WWW '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,899 of 8,196 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 527Total Downloads
- Downloads (Last 12 months)527
- Downloads (Last 6 weeks)90
Reflects downloads up to 09 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in