{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T15:45:26Z","timestamp":1780501526553,"version":"3.54.1"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:p>\n            Graph coarsening techniques aim at simplifying the graph structure while preserving key properties in the resulting coarsened graph, have been widely used in graph partitioning and graph neural networks (GNNs). Existing graph coarsening techniques mainly focus on preserving cuts or graph spectrums. In this paper, we propose a new method that focuses on preserving graph topological features. In particular, we develop a novel graph coarsening approach, called Graph Elementary Collapse (GEC), by extending the concept of elementary collapse in algebraic topology to graph analysis. With this novel method, we can ensure a kind of equivalence relationship called\n            <jats:italic>homotopy equivalence<\/jats:italic>\n            of the graph during the coarsening process, thereby preserving numerous topological properties, including connectivity, rings, and voids. To enhance the scalability, we also propose several carefully-designed optimization techniques to reduce the time and memory consumption of our approach. Extensive experiments on several real-world datasets demonstrate the effectiveness and efficiency of our proposed method across various GNN prediction tasks.\n          <\/jats:p>","DOI":"10.14778\/3704965.3704981","type":"journal-article","created":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T17:22:57Z","timestamp":1739899377000},"page":"4760-4772","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Topology-Preserving Graph Coarsening: An Elementary Collapse-Based Approach"],"prefix":"10.14778","volume":"17","author":[{"given":"Yuchen","family":"Meng","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Key Laboratory of Intelligent Supply Chain Technology, Shenzhen, China and Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Longlong","family":"Lin","sequence":"additional","affiliation":[{"name":"Southwest University, Chongqing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xunkai","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,2,18]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning. 1026--1037","author":"Bodnar Cristian","year":"2021","unstructured":"Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Li\u00f3, and Michael Bronstein. 2021. Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks. In Proceedings of the 38th International Conference on Machine Learning. 1026--1037."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Aleksandar Bojchevski Johannes Gasteiger Bryan Perozzi Amol Kapoor Martin Blais Benedek R\u00f3zemberczki Michal Lukasik and Stephan G\u00fcnnemann. 2020. Scaling Graph Neural Networks with Approximate PageRank. In KDD.","DOI":"10.1145\/3394486.3403296"},{"key":"e_1_2_1_3_1","unstructured":"Aleksandar Bojchevski and Stephan G\u00fcnnemann. 2018. Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking. In ICLR."},{"key":"e_1_2_1_4_1","unstructured":"Gecia Bravo Hermsdorff and Lee Gunderson. 2019. A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening. In NeurIPS."},{"key":"e_1_2_1_5_1","volume-title":"Finding All Cliques of an Undirected Graph (Algorithm 457). Commun. ACM","author":"Bron Coenraad","year":"1973","unstructured":"Coenraad Bron and Joep Kerbosch. 1973. Finding All Cliques of an Undirected Graph (Algorithm 457). Commun. ACM (1973), 575--576."},{"key":"e_1_2_1_6_1","volume-title":"Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203","author":"Bruna Joan","year":"2013","unstructured":"Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2013. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203 (2013)."},{"key":"e_1_2_1_7_1","unstructured":"Jie Chen Tengfei Ma and Cao Xiao. 2018. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. In ICLR."},{"key":"e_1_2_1_8_1","unstructured":"Tianlong Chen Yongduo Sui Xuxi Chen Aston Zhang and Zhangyang Wang. 2021. A Unified Lottery Ticket Hypothesis for Graph Neural Networks. In ICMR. 1695--1706."},{"key":"e_1_2_1_9_1","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Chen Zhengdao","year":"2019","unstructured":"Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. 2019. On the equivalence between graph isomorphism testing and function approximation with GNNs. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada. 15868--15876."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Wei-Lin Chiang Xuanqing Liu Si Si Yang Li Samy Bengio and Cho-Jui Hsieh. 2019. Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. In KDD. 257--266.","DOI":"10.1145\/3292500.3330925"},{"key":"e_1_2_1_11_1","volume-title":"pbitMCE: A bit-based approach for maximal clique enumeration on multicore processors","author":"Dasari Naga Shailaja","unstructured":"Naga Shailaja Dasari, Desh Ranjan, and Mohammad Zubair. 2014. pbitMCE: A bit-based approach for maximal clique enumeration on multicore processors. In IEEE. 478--485."},{"key":"e_1_2_1_12_1","volume-title":"Convolutional neural networks on graphs with fast localized spectral filtering. NeurIPS","author":"Defferrard Micha\u00ebl","year":"2016","unstructured":"Micha\u00ebl Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional neural networks on graphs with fast localized spectral filtering. NeurIPS (2016)."},{"key":"e_1_2_1_13_1","volume-title":"Computational topology for data analysis","author":"Dey Tamal Krishna","unstructured":"Tamal Krishna Dey and Yusu Wang. 2022. Computational topology for data analysis. Cambridge University Press."},{"key":"e_1_2_1_14_1","volume-title":"A computationally intractable problem on simplicial complexes. Computational Geometry","author":"E\u011fecio\u011flu \u00d6mer","year":"1996","unstructured":"\u00d6mer E\u011fecio\u011flu and Teofilo F Gonzalez. 1996. A computationally intractable problem on simplicial complexes. Computational Geometry (1996)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"David Eppstein Maarten L\u00f6ffler and Darren Strash. 2010. Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. In ISAAC. 403--414.","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"e_1_2_1_16_1","volume-title":"Fast Graph Representation Learning with PyTorch Geometric. CoRR","author":"Fey Matthias","year":"2019","unstructured":"Matthias Fey and Jan Eric Lenssen. 2019. Fast Graph Representation Learning with PyTorch Geometric. CoRR (2019)."},{"key":"e_1_2_1_17_1","volume-title":"Kai Zheng, and Hongzhi Yin.","author":"Gao Xinyi","year":"2023","unstructured":"Xinyi Gao, Tong Chen, Yilong Zang, Wentao Zhang, Quoc Viet Hung Nguyen, Kai Zheng, and Hongzhi Yin. 2023. Graph Condensation for Inductive Node Representation Learning."},{"key":"e_1_2_1_18_1","unstructured":"Will Hamilton Zhitao Ying and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In NeurIPS."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2024.123915"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Bruce Hendrickson Robert W Leland et al. 1995. A Multi-Level Algorithm For Partitioning Graphs. SC (1995) 1--14.","DOI":"10.1145\/224170.224228"},{"key":"e_1_2_1_21_1","unstructured":"Weihua Hu Matthias Fey Marinka Zitnik Yuxiao Dong Hongyu Ren Bowen Liu Michele Catasta and Jure Leskovec. 2020. Open Graph Benchmark: Datasets for Machine Learning on Graphs. In NeurIPS. 22118--22133."},{"key":"e_1_2_1_22_1","volume-title":"Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv preprint arXiv:2005.00687","author":"Hu Weihua","year":"2020","unstructured":"Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv preprint arXiv:2005.00687 (2020)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Zengfeng Huang Shengzhong Zhang Chong Xi Tang Liu and Min Zhou. 2021. Scaling Up Graph Neural Networks Via Graph Coarsening. In KDD. 675--684.","DOI":"10.1145\/3447548.3467256"},{"key":"e_1_2_1_24_1","unstructured":"Bo Hui Da Yan Xiaolong Ma and Wei-Shinn Ku. 2023. Rethinking Graph Lottery Tickets: Graph Sparsity Matters. In The Eleventh ICLR."},{"key":"e_1_2_1_25_1","volume-title":"The Power of Pivoting for Exact Clique Counting. In WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining","author":"Jain Shweta","year":"2020","unstructured":"Shweta Jain and C. Seshadhri. 2020. The Power of Pivoting for Exact Clique Counting. In WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining, Houston, TX, USA, February 3-7, 2020, James Caverlee, Xia (Ben) Hu, Mounia Lalmas, and Wei Wang (Eds.). 268--276."},{"key":"e_1_2_1_26_1","unstructured":"Wei Jin Lingxiao Zhao Shichang Zhang Yozen Liu Jiliang Tang and Neil Shah. 2022. Graph Condensation for Graph Neural Networks. (2022)."},{"key":"e_1_2_1_27_1","volume-title":"Kipf and Max Welling","author":"Thomas","year":"2017","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR."},{"key":"e_1_2_1_28_1","unstructured":"Johannes Klicpera Aleksandar Bojchevski and Stephan G\u00fcnnemann. 2019. Predict then Propagate: Graph Neural Networks meet Personalized PageRank. In ICLR."},{"key":"e_1_2_1_29_1","unstructured":"Manoj Kumar Anurag Sharma Shashwat Saxena and Sandeep Kumar. 2023. Featured Graph Coarsening with Similarity Guarantees. In ICML."},{"key":"e_1_2_1_30_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection."},{"key":"e_1_2_1_31_1","volume-title":"PSMC: Provable and Scalable Algorithms for Motif Conductance Based Graph Clustering. CoRR abs\/2406.07357","author":"Lin Longlong","year":"2024","unstructured":"Longlong Lin, Tao Jia, Zeli Wang, Jin Zhao, and Rong-Hua Li. 2024. PSMC: Provable and Scalable Algorithms for Motif Conductance Based Graph Clustering. CoRR abs\/2406.07357 (2024)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Longlong Lin Ronghua Li and Tao Jia. 2023. Scalable and Effective Conductance-Based Graph Clustering. In AAAI. 4471--4478.","DOI":"10.1609\/aaai.v37i4.25568"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3648160.3648163"},{"key":"e_1_2_1_34_1","volume-title":"Graph Reduction with Spectral and Cut Guarantees. Journal of Machine Learning Research","author":"Loukas Andreas","year":"2019","unstructured":"Andreas Loukas. 2019. Graph Reduction with Spectral and Cut Guarantees. Journal of Machine Learning Research (2019), 1--42."},{"key":"e_1_2_1_35_1","unstructured":"Andreas Loukas and Pierre Vandergheynst. 2018. Spectrally Approximating Large Graphs with Smaller Graphs. In ICML. 3237--3246."},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"John Milnor. 1966. Whitehead torsion. Bull. Amer. Math. Soc. (1966).","DOI":"10.1090\/S0002-9904-1966-11484-2"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.576"},{"key":"e_1_2_1_38_1","volume-title":"Elements of algebraic topology","author":"Munkres James R.","unstructured":"James R. Munkres. 1984. Elements of algebraic topology. Addison-Wesley."},{"key":"e_1_2_1_39_1","unstructured":"Morteza Ramezani Weilin Cong Mehrdad Mahdavi Anand Sivasubramaniam and Mahmut Kandemir. 2020. GCN meets GPU: Decoupling \"When to Sample\" from \"How to Sample\". In NeurIPS."},{"key":"e_1_2_1_40_1","article-title":"Advanced Coarsening Schemes for Graph Partitioning","volume":"19","author":"Safro Ilya","year":"2014","unstructured":"Ilya Safro, Peter Sanders, and Christian Schulz. 2014. Advanced Coarsening Schemes for Graph Partitioning. ACM J. Exp. Algorithmics 19, 1 (2014).","journal-title":"ACM J. Exp. Algorithmics"},{"key":"e_1_2_1_41_1","volume-title":"Pitfalls of Graph Neural Network Evaluation. CoRR","author":"Shchur Oleksandr","year":"2018","unstructured":"Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan G\u00fcnnemann. 2018. Pitfalls of Graph Neural Network Evaluation. CoRR (2018)."},{"key":"e_1_2_1_42_1","volume-title":"Mohammad Javad Faraji, and Pierre Vandergheynst","author":"Shuman David I","year":"2016","unstructured":"David I Shuman, Mohammad Javad Faraji, and Pierre Vandergheynst. 2016. A Multiscale Pyramid Transform for Graph Signals. IEEE Transactions on Signal Processing (2016)."},{"key":"e_1_2_1_43_1","volume-title":"Spielman and Nikhil Srivastava","author":"Daniel","year":"2011","unstructured":"Daniel A. Spielman and Nikhil Srivastava. 2011. Graph Sparsification by Effective Resistances. SIAM J. Comput. (2011), 1913--1926."},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Jie Tang Jing Zhang Limin Yao Juanzi Li Li Zhang and Zhong Su. 2008. Arnet-Miner: extraction and mining of academic social networks. In SIGKDD. 990--998.","DOI":"10.1145\/1401890.1402008"},{"key":"e_1_2_1_45_1","unstructured":"Petar Velickovic Guillem Cucurull Arantxa Casanova Adriana Romero Pietro Li\u00f2 and Yoshua Bengio. 2018. Graph Attention Networks. In ICLR."},{"key":"e_1_2_1_46_1","volume-title":"A Multilevel Algorithm for Force-Directed Graph-Drawing. Journal of Graph Algorithms and Applications","author":"Walshaw Chris","year":"2003","unstructured":"Chris Walshaw. 2003. A Multilevel Algorithm for Force-Directed Graph-Drawing. Journal of Graph Algorithms and Applications (2003)."},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Lu Wang Yanghua Xiao Bin Shao and Haixun Wang. 2014. How to partition a billion-node graph. In ICDE. 568--579.","DOI":"10.1109\/ICDE.2014.6816682"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Ryan Wickman Xiaofei Zhang and Weizi Li. 2022. A Generic Graph Sparsification Framework using Deep Reinforcement Learning. In ICDM. 1221--1226.","DOI":"10.1109\/ICDM54844.2022.00158"},{"key":"e_1_2_1_49_1","unstructured":"Felix Wu Amauri Souza Tianyi Zhang Christopher Fifty Tao Yu and Kilian Weinberger. 2019. Simplifying Graph Convolutional Networks. In ICML."},{"key":"e_1_2_1_50_1","unstructured":"Keyulu Xu Weihua Hu Jure Leskovec and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In ICLR."},{"key":"e_1_2_1_51_1","unstructured":"Zuoyu Yan Tengfei Ma Liangcai Gao Zhi Tang and Chao Chen. 2022. Cycle Representation Learning for Inductive Relation Prediction. In ICML. 24895--24910."},{"key":"e_1_2_1_52_1","volume-title":"Cycle Invariant Positional Encoding for Graph Representation Learning. CoRR","author":"Yan Zuoyu","year":"2023","unstructured":"Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, Chao Chen, and Yusu Wang. 2023. Cycle Invariant Positional Encoding for Graph Representation Learning. CoRR (2023)."},{"key":"e_1_2_1_53_1","unstructured":"Zhilin Yang William Cohen and Ruslan Salakhudinov. 2016. Revisiting Semi-Supervised Learning with Graph Embeddings. In ICML. 40--48."},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Yunfeng Yu Longlong Lin Qiyu Liu Zeli Wang Xi Ou and Tao Jia. 2024. GSD-GNN: Generalizable and Scalable Algorithms for Decoupled Graph Neural Networks. In ICMR.","DOI":"10.1145\/3652583.3658051"},{"key":"e_1_2_1_55_1","unstructured":"Hanqing Zeng Hongkuan Zhou Ajitesh Srivastava Rajgopal Kannan and Viktor Prasanna. 2020. GraphSAINT: Graph Sampling Based Inductive Learning Method. In ICLR."},{"key":"e_1_2_1_56_1","unstructured":"Cheng Zheng Bo Zong Wei Cheng Dongjin Song Jingchao Ni Wenchao Yu Haifeng Chen and Wei Wang. 2020. Robust graph representation learning via neural sparsification. In ICML. 11458--11468."},{"key":"e_1_2_1_57_1","volume-title":"DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs. In 2020 IEEE\/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3).","author":"Zheng Da","year":"2020","unstructured":"Da Zheng, Chao Ma, Minjie Wang, Jinjing Zhou, Qidong Su, Xiang Song, Quan Gan, Zheng Zhang, and George Karypis. 2020. DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs. In 2020 IEEE\/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3)."},{"key":"e_1_2_1_58_1","volume-title":"Xingquan Zhu, and Shirui Pan.","author":"Zheng Xin","year":"2023","unstructured":"Xin Zheng, Miao Zhang, Chunyang Chen, Quoc Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan. 2023. Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data. In NeurIPS."},{"key":"e_1_2_1_59_1","volume-title":"The Eleventh International Conference on Learning Representations.","author":"Zhu Jinhua","year":"2023","unstructured":"Jinhua Zhu, Kehan Wu, Bohan Wang, Yingce Xia, Shufang Xie, Qi Meng, Lijun Wu, Tao Qin, Wengang Zhou, Houqiang Li, and Tie-Yan Liu. 2023. $\\mathcal{O}$-GNN: incorporating ring priors into molecular modeling. In The Eleventh International Conference on Learning Representations."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3704965.3704981","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T17:36:06Z","timestamp":1739900166000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3704965.3704981"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9]]},"references-count":59,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["10.14778\/3704965.3704981"],"URL":"https:\/\/doi.org\/10.14778\/3704965.3704981","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,9]]},"assertion":[{"value":"2025-02-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}