{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:51:25Z","timestamp":1773481885963,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T00:00:00Z","timestamp":1707696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["62020106005, 61960206002, 42050105, 62061146002"],"award-info":[{"award-number":["62020106005, 61960206002, 42050105, 62061146002"]}]},{"name":"Shanghai Pilot Program for Basic Research - Shanghai Jiao Tong University"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2024,5,31]]},"abstract":"<jats:p>\n            Graph pooling refers to the operation that maps a set of node representations into a compact form for graph-level representation learning. However, existing graph pooling methods are limited by the power of the Weisfeiler\u2013Lehman (WL) test in the performance of graph discrimination. In addition, these methods often suffer from hard adaptability to hyper-parameters and training instability. To address these issues, we propose Hi-PART, a simple yet effective graph neural network (GNN) framework with\n            <jats:underline>Hi<\/jats:underline>\n            erarchical\n            <jats:underline>Par<\/jats:underline>\n            tition\n            <jats:underline>T<\/jats:underline>\n            ree (HPT). In HPT, each layer is a partition of the graph with different levels of granularities that are going toward a finer grain from top to bottom. Such an exquisite structure allows us to quantify the graph structure information contained in HPT with the aid of structural information theory. Algorithmically, by employing GNNs to summarize node features into the graph feature based on HPT\u2019s hierarchical structure, Hi-PART is able to adequately leverage the graph structure information and provably goes beyond the power of the WL test. Due to the separation of HPT optimization from graph representation learning, Hi-PART involves the height of HPT as the only extra hyper-parameter and enjoys higher training stability. Empirical results on graph classification benchmarks validate the superior expressive power and generalization ability of Hi-PART compared with state-of-the-art graph pooling approaches.\n          <\/jats:p>","DOI":"10.1145\/3636429","type":"journal-article","created":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T11:42:38Z","timestamp":1702554158000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Hi-PART: Going Beyond Graph Pooling with Hierarchical Partition Tree for Graph-Level Representation Learning"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5750-8401","authenticated-orcid":false,"given":"Yuyang","family":"Ren","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9671-2058","authenticated-orcid":false,"given":"Haonan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7796-9168","authenticated-orcid":false,"given":"Luoyi","family":"Fu","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-2917-2033","authenticated-orcid":false,"given":"Shiyu","family":"Liang","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3123-5270","authenticated-orcid":false,"given":"Lei","family":"Zhou","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0357-8356","authenticated-orcid":false,"given":"Xinbing","family":"Wang","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2315-4219","authenticated-orcid":false,"given":"Xinde","family":"Cao","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4121-4163","authenticated-orcid":false,"given":"Fei","family":"Long","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Media Convergence Production Technology and Systems, Xinhua News Agency, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3331-2302","authenticated-orcid":false,"given":"Chenghu","family":"Zhou","sequence":"additional","affiliation":[{"name":"Institute of Geographical Sciences and Natural Resources Research, Chinese Academy of Sciences, China"}]}],"member":"320","published-online":{"date-parts":[[2024,2,12]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.045102"},{"key":"e_1_3_1_3_2","first-page":"684","volume-title":"Proceedings of the 48th Annual ACM Symposium on Theory of Computing","author":"Babai L\u00e1szl\u00f3","year":"2016","unstructured":"L\u00e1szl\u00f3 Babai. 2016. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing. 684\u2013697."},{"key":"e_1_3_1_4_2","unstructured":"J. Baek M. Kang and S. J. Hwang. 2021. Accurate learning of graph representations with graph multiset pooling. The International Conference on Learning Representations (ICLR\u201921)."},{"key":"e_1_3_1_5_2","first-page":"874","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Bianchi Filippo Maria","year":"2020","unstructured":"Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. 2020. Spectral clustering with graph neural networks for graph pooling. In Proceedings of the International Conference on Machine Learning. PMLR, 874\u2013883."},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-006-0289-3"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_3_1_9_2","unstructured":"F. Diehl. 2019. Edge contraction pooling for graph neural networks. arXiv preprint arXiv:1905.10990."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(03)00628-4"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.46"},{"key":"e_1_3_1_12_2","first-page":"2083","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Gao Hongyang","year":"2019","unstructured":"Hongyang Gao and Shuiwang Ji. 2019. Graph U-Nets. In Proceedings of the International Conference on Machine Learning. PMLR, 2083\u20132092."},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/3294771.3294869"},{"key":"e_1_3_1_14_2","unstructured":"T. N. Kipf and M. Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907."},{"key":"e_1_3_1_15_2","first-page":"3734","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Lee Junhyun","year":"2019","unstructured":"Junhyun Lee, Inyeop Lee, and Jaewoo Kang. 2019. Self-attention graph pooling. In Proceedings of the International Conference on Machine Learning. PMLR, 3734\u20133743."},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2555904"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403076"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330982"},{"key":"e_1_3_1_19_2","unstructured":"C. Morris M. N. Kriege F. Bause et\u00a0al. 2020. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.066133"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3404835.3463074"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.5997"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02477860"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_3_1_26_2","first-page":"1","volume-title":"ACM Multimedia Asia","author":"Su Zidong","year":"2021","unstructured":"Zidong Su, Zehui Hu, and Yangding Li. 2021. Hierarchical graph representation learning with local capsule pooling. In ACM Multimedia Asia. 1\u20137."},{"key":"e_1_3_1_27_2","unstructured":"P. Veli\u010dkovi\u0107 G. Cucurull A. Casanova et\u00a0al. 2017. Graph attention networks. arXiv preprint arXiv:1710.10903."},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-007-0103-5"},{"key":"e_1_3_1_29_2","first-page":"9952","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Wang Yu Guang","year":"2020","unstructured":"Yu Guang Wang, Ming Li, Zheng Ma, Guido Montufar, Xiaosheng Zhuang, and Yanan Fan. 2020. Haar graph pooling. In Proceedings of the International Conference on Machine Learning. PMLR, 9952\u20139962."},{"key":"e_1_3_1_30_2","unstructured":"Z. Wang and S. Ji. 2020. Second-order pooling for graph neural networks. IEEE Transactions on Pattern Analysis & Machine Intelligence 1 (2020) 1\u20131."},{"issue":"9","key":"e_1_3_1_31_2","first-page":"12","article-title":"The reduction of a graph to canonical form and the algebra which appears therein","volume":"2","author":"Weisfeiler Boris","year":"1968","unstructured":"Boris Weisfeiler and Andrei Leman. 1968. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series 2, 9 (1968), 12\u201316.","journal-title":"NTI, Series"},{"key":"e_1_3_1_32_2","unstructured":"K. Xu W. Hu J. Leskovec et\u00a0al. 2018. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826."},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783417"},{"key":"e_1_3_1_34_2","first-page":"2134","article-title":"A structural smoothing framework for robust graph comparison","author":"Yanardag Pinar","year":"2015","unstructured":"Pinar Yanardag and S. V. N. Vishwanathan. 2015. A structural smoothing framework for robust graph comparison. In Proceedings of the 28th International Conference on Neural Information Processing Systems . 2134\u20132142.","journal-title":"Proceedings of the 28th International Conference on Neural Information Processing Systems"},{"key":"e_1_3_1_35_2","unstructured":"Z. Ying J. You C. Morris et\u00a0al. 2018. Hierarchical graph representation learning with differentiable pooling. Advances in Neural Information Processing Systems. (2018) 31."},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i12.17283"},{"key":"e_1_3_1_37_2","volume-title":"Proceedings of the 8th International Conference on Learning Representations","author":"Yuan Hao","year":"2020","unstructured":"Hao Yuan and Shuiwang Ji. 2020. StructPool: Structured graph pooling via conditional random fields. In Proceedings of the 8th International Conference on Learning Representations."},{"key":"e_1_3_1_38_2","first-page":"5165","article-title":"Link prediction based on graph neural networks","author":"Zhang Muhan","year":"2018","unstructured":"Muhan Zhang and Yixin Chen. 2018. Link prediction based on graph neural networks. In Proceedings of the International Conference on Neural Information Processing Systems . 5165\u20135175.","journal-title":"Proceedings of the International Conference on Neural Information Processing Systems"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11782"},{"key":"e_1_3_1_40_2","doi-asserted-by":"crossref","unstructured":"J. Zhou G. Cui S. Hu et\u00a0al. 2020. Graph neural networks: A review of methods and applications. AI Open 1 (2020) 57\u201381.","DOI":"10.1016\/j.aiopen.2021.01.001"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3636429","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3636429","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:35:41Z","timestamp":1750178141000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3636429"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,12]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,5,31]]}},"alternative-id":["10.1145\/3636429"],"URL":"https:\/\/doi.org\/10.1145\/3636429","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,12]]},"assertion":[{"value":"2022-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-29","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}