{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T18:26:30Z","timestamp":1775759190606,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,17]],"date-time":"2022-11-17T00:00:00Z","timestamp":1668643200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,17]],"date-time":"2022-11-17T00:00:00Z","timestamp":1668643200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Luxembourg National Research Fund","award":["PRIDE15\/10621687\/SPsquared"],"award-info":[{"award-number":["PRIDE15\/10621687\/SPsquared"]}]},{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["109-2636-E-006-017"],"award-info":[{"award-number":["109-2636-E-006-017"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["108-2218-E-006-036"],"award-info":[{"award-number":["108-2218-E-006-036"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Graph Neural Networks (GNNs) have become a prominent approach to machine learning with graphs and have been increasingly applied in a multitude of domains. Nevertheless, since most existing GNN models are based on <jats:italic>flat<\/jats:italic> message-passing mechanisms, two limitations need to be tackled: (i) they are costly in encoding long-range information spanning the graph structure; (ii) they are failing to encode features in the high-order neighbourhood in the graphs as they only perform information aggregation across the observed edges in the original graph. To deal with these two issues, we propose a novel <jats:italic>Hierarchical Message-passing Graph Neural Networks<\/jats:italic> framework. The key idea is generating a hierarchical structure that re-organises all nodes in a flat graph into multi-level super graphs, along with innovative intra- and inter-level propagation manners. The derived hierarchy creates shortcuts connecting far-away nodes so that informative long-range interactions can be efficiently accessed via message passing and incorporates meso- and macro-level semantics into the learned node representations. We present the first model to implement this framework, termed <jats:italic>Hierarchical Community-aware Graph Neural Network<\/jats:italic> (HC-GNN), with the assistance of a hierarchical community detection algorithm. The theoretical analysis illustrates HC-GNN\u2019s remarkable capacity in capturing long-range information without introducing heavy additional computation complexity. Empirical experiments conducted on 9 datasets under transductive, inductive, and few-shot settings exhibit that HC-GNN can outperform state-of-the-art GNN models in network analysis tasks, including node classification, link prediction, and community detection. Moreover, the model analysis further demonstrates HC-GNN\u2019s robustness facing graph sparsity and the flexibility in incorporating different GNN encoders.\n<\/jats:p>","DOI":"10.1007\/s10618-022-00890-9","type":"journal-article","created":{"date-parts":[[2022,11,17]],"date-time":"2022-11-17T15:05:03Z","timestamp":1668697503000},"page":"381-408","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":68,"title":["Hierarchical message-passing graph neural networks"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1226-5597","authenticated-orcid":false,"given":"Zhiqiang","family":"Zhong","sequence":"first","affiliation":[]},{"given":"Cheng-Te","family":"Li","sequence":"additional","affiliation":[]},{"given":"Jun","family":"Pang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,17]]},"reference":[{"key":"890_CR1","unstructured":"Alon U, Yahav E (2021) On the bottleneck of graph neural networks and its practical implications. In: Proceedings of the 2021 international conference on learning representations (ICLR)"},{"key":"890_CR2","doi-asserted-by":"crossref","unstructured":"Bhowmick AK, Meneni K, Danisch M, Guillaume J, Mitra B (2020) Louvainne: Hierarchical louvain method for high quality and scalable network embedding. In: Proceedings of the 2020 ACM international conference on web search and data mining (WSDM), pp 43\u201351","DOI":"10.1145\/3336191.3371800"},{"issue":"10","key":"890_CR3","doi-asserted-by":"publisher","first-page":"10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","volume":"2008","author":"VD Blondel","year":"2008","unstructured":"Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):10008","journal-title":"J Stat Mech Theory Exp"},{"issue":"suppl\u20131","key":"890_CR4","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1093\/bioinformatics\/bti1007","volume":"21","author":"KM Borgwardt","year":"2005","unstructured":"Borgwardt KM, Ong CS, Sch\u00f6nauer S, Vishwanathan SVN, Smola AJ, Kriegel H (2005) Protein function prediction via graph kernels. Bioinformatics 21(suppl\u20131):47\u201356","journal-title":"Bioinformatics"},{"key":"890_CR5","unstructured":"Chen Z, Li L, Bruna J (2019) Supervised community detection with line graph neural networks. In: Proceedings of the 2019 international conference on learning representations (ICLR)"},{"key":"890_CR6","doi-asserted-by":"crossref","unstructured":"Chen H, Perozzi B, Hu Y, Skiena S (2018) HARP: Hierarchical representation learning for networks. In: Proceedings of the 2018 AAAI conference on artificial intelligence (AAAI), pp 2127\u20132134","DOI":"10.1609\/aaai.v32i1.11849"},{"key":"890_CR7","unstructured":"Chen M, Wei Z, Huang Z, Ding B, Li Y (2020) Simple and deep graph convolutional networks. In: Proceedings of the 2020 international conference on machine learning (ICML)"},{"key":"890_CR8","doi-asserted-by":"crossref","unstructured":"Freeman LC (1977) A set of measures of centrality based on betweenness. Sociometry, 35\u201341","DOI":"10.2307\/3033543"},{"key":"890_CR9","unstructured":"Gao H, Ji S (2019) Graph u-nets. In: Proceedings of the 2019 international conference on machine learning (ICML)"},{"key":"890_CR10","unstructured":"Gilmer J, Schoenholz SS, Riley PF, Vinyals O, Dahl GE (2017) Neural message passing for quantum chemistry. In: Proceedings of the 2017 international conference on machine learning (ICML)"},{"key":"890_CR11","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99:7821\u20137826","journal-title":"Proc Natl Acad Sci"},{"key":"890_CR12","unstructured":"Gu F, Chang H, Zhu W, Sojoudi S, El Ghaoui L (2020) Implicit graph neural networks. In: Proceedings of the 2020 annual conference on neural information processing systems (NeurIPS)"},{"key":"890_CR13","unstructured":"Hamilton WL, Ying Z, Leskovec J (2017) Inductive representation learning on large graphs. In: Proceedings of the 2017 annual conference on neural information processing systems (NIPS), pp 1025\u20131035"},{"key":"890_CR14","doi-asserted-by":"crossref","unstructured":"Huang J, Li Z, Li N, Liu S, Li G (2019) Attpool: Towards hierarchical feature representation in graph convolutional networks via attention mechanism. In: Proceedings of the 2019 IEEE international conference on computer vision (ICCV), pp 6480\u20136489","DOI":"10.1109\/ICCV.2019.00658"},{"key":"890_CR15","doi-asserted-by":"crossref","unstructured":"Huang X, Song Q, Li Y, Hu X (2019) Graph recurrent networks with attributed random walks. In: Proceedings of the 2019 ACM conference on knowledge discovery and data mining (KDD), pp 732\u2013740","DOI":"10.1145\/3292500.3330941"},{"key":"890_CR16","unstructured":"Hu W, Fey M, Zitnik M, Dong Y, Ren H, Liu B, Catasta M, Leskovec J (2020) Open graph benchmark: Datasets for machine learning on graphs. In: Proceedings of the 2020 annual conference on neural information processing systems (NeurIPS)"},{"key":"890_CR17","unstructured":"Kipf TN, Welling M (2017) Semi-supervised classification with graph convolutional networks. In: Proceedings of the 2017 international conference on learning representations (ICLR)"},{"issue":"7553","key":"890_CR18","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1038\/nature14539","volume":"521","author":"Y LeCun","year":"2015","unstructured":"LeCun Y, Bengio Y, Hinton GE (2015) Deep learning. Nature 521(7553):436\u2013444","journal-title":"Nature"},{"key":"890_CR19","unstructured":"Leskovec J, Krevl A (2014) SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"key":"890_CR20","unstructured":"Li M, Chen S, Zhang Y, Tsang IW (2020) Graph cross networks with vertex infomax pooling. In: Proceedings of the 2020 annual conference on neural information processing systems (NeurIPS)"},{"key":"890_CR21","doi-asserted-by":"crossref","unstructured":"Li Q, Han Z, Wu X (2018) Deeper insights into graph convolutional networks for semi-supervised learning. In: Proceedings of the 2018 AAAI conference on artificial intelligence (AAAI), pp. 3538\u20133545","DOI":"10.1609\/aaai.v32i1.11604"},{"key":"890_CR22","unstructured":"Li Z, Kovachki NB, Azizzadenesheli K, Liu B, Stuart AM, Bhattacharya K, Anandkumar A (2020) Multipole graph neural operator for parametric partial differential equations. In: Proceedings of the 2020 annual conference on neural information processing systems (NeurIPS)"},{"key":"890_CR23","unstructured":"Li P, Wang Y, Wang H, Leskovec J (2020) Distance encoding - design provably more powerful graph neural networks for structural representation learning. In: Proceedings of the 2020 annual conference on neural information processing systems (NeurIPS)"},{"key":"890_CR24","unstructured":"Min Y, Wenkel F, Wolf G (2020) Scattering GCN: overcoming oversmoothness in graph convolutional networks. In: Proceedings of the 2020 annual conference on neural information processing systems (NeurIPS)"},{"issue":"18","key":"890_CR25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.108.188701","volume":"108","author":"RR Nadakuditi","year":"2012","unstructured":"Nadakuditi RR, Newman MEJ (2012) Graph spectra and the detectability of community structure in networks. Phys Rev Lett 108(18):188701","journal-title":"Phys Rev Lett"},{"key":"890_CR26","unstructured":"Namata G, London B, Getoor L, Huang B (2012) Query-driven active surveying for collective classification. In: Proceedings of the 2012 international workshop on mining and learning with graphs, p 8"},{"key":"890_CR27","doi-asserted-by":"crossref","unstructured":"Ramp\u00e1sek L, Wolf G (2021) Hierarchical graph neural nets can capture long-range interactions. In: IEEE international workshop on machine learning for signal processing (MLSP), pp 1\u20136","DOI":"10.1109\/MLSP52302.2021.9596069"},{"key":"890_CR28","doi-asserted-by":"crossref","unstructured":"Ranjan E, Sanyal S, Talukdar PP (2020) ASAP: adaptive structure aware pooling for learning hierarchical graph representations. In: Proceedings of the 2020 AAAI conference on artificial intelligence (AAAI), pp. 5470\u20135477","DOI":"10.1609\/aaai.v34i04.5997"},{"key":"890_CR29","doi-asserted-by":"crossref","unstructured":"Ronneberger O, Fischer P, Brox T (2015) U-net: convolutional networks for biomedical image segmentation. In: Proceedings of the 2015 medical image computing and computer-assisted intervention (MICCAI). Lecture notes in computer science, vol 9351, pp 234\u2013241","DOI":"10.1007\/978-3-319-24574-4_28"},{"key":"890_CR30","doi-asserted-by":"crossref","unstructured":"Rossetti G, Guidotti R, Pennacchioli D, Pedreschi D, Giannotti F (2015) Interaction prediction in dynamic networks exploiting community discovery. In: Proceedings of the 2015 IEEE\/ACM international conference on advances in social networks analysis and mining (ASONAM), pp 553\u2013558","DOI":"10.1145\/2808797.2809401"},{"issue":"3","key":"890_CR31","first-page":"93","volume":"29","author":"P Sen","year":"2008","unstructured":"Sen P, Namata G, Bilgic M, Getoor L, Galligher B, Eliassi-Rad T (2008) Collective classification in network data. AI Mag 29(3):93\u201393","journal-title":"AI Mag"},{"key":"890_CR32","doi-asserted-by":"crossref","unstructured":"Sun Y, Han J (2012) Mining heterogeneous information networks: a structural analysis approach. ACM SIGKDD explorations newsletter","DOI":"10.1145\/2481244.2481248"},{"issue":"3","key":"890_CR33","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.92.032801","volume":"92","author":"VA Traag","year":"2015","unstructured":"Traag VA (2015) Faster unfolding of communities: Speeding up the louvain algorithm. Phys Rev E 92(3):032801","journal-title":"Phys Rev E"},{"key":"890_CR34","unstructured":"Velickovic P, Cucurull G, Casanova A, Romero A, Lio P, Bengio Y (2018) Graph attention networks. In: Proceedings of the 2018 international conference on learning representations (ICLR)"},{"key":"890_CR35","doi-asserted-by":"crossref","unstructured":"Wang X, Cui P, Wang J, Pei J, Zhu W, Yang S (2017) Community preserving network embedding. In: Proceedings of the 2017 AAAI conference on artificial intelligence (AAAI), pp 203\u2013209","DOI":"10.1609\/aaai.v31i1.10488"},{"key":"890_CR36","unstructured":"Wang J, Peng J, Liu O (2014) An approach for hesitant node classification in overlapping community detection. In: Processings of the 2014 Pacific Asia conference on information systems (PACIS), p 47"},{"key":"890_CR37","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts DJ, Strogatz SH (1998) Collective dynamics of small-world networks. Nature 393:440","journal-title":"Nature"},{"issue":"1","key":"890_CR38","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1109\/TNNLS.2020.2978386","volume":"32","author":"Z Wu","year":"2021","unstructured":"Wu Z, Pan S, Chen F, Long G, Zhang C, Yu PS (2021) A comprehensive survey on graph neural networks. IEEE Trans Neural Netw Learn Syst 32(1):4\u201324","journal-title":"IEEE Trans Neural Netw Learn Syst"},{"key":"890_CR39","unstructured":"Xu K, Hu W, Leskovec J, Jegelka S (2019) How powerful are graph neural networks? In: Proceedings of the 2019 international conference on machine learning (ICML)"},{"key":"890_CR40","unstructured":"Ying R, You J, Morris C, Ren X, Hamilton WL, Leskovec J (2018) Hierarchical graph representation learning with differentiable pooling. In: Proceedings of the 2018 annual conference on neural information processing systems (NeurIPS), pp 4805\u20134815"},{"key":"890_CR41","unstructured":"You J, Ying R, Leskovec J (2019) Position-aware graph neural networks. In: Proceedings of the 2019 international conference on machine learning (ICML)"},{"key":"890_CR42","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2981333","author":"Z Zhang","year":"2020","unstructured":"Zhang Z, Cui P, Zhu W (2020) Deep learning on graphs: a survey. IEEE Trans Knowl Data Eng. https:\/\/doi.org\/10.1109\/TKDE.2020.2981333","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"890_CR43","unstructured":"Zhang M, Chen Y (2018) Link prediction based on graph neural networks. In: Proceedings of the 2018 annual conference on neural information processing systems (NeurIPS), pp 5171\u20135181"},{"key":"890_CR44","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1093\/bioinformatics\/btx252","volume":"33","author":"M Zitnik","year":"2017","unstructured":"Zitnik M, Leskovec J (2017) Predicting multicellular function through multi-layer tissue networks. Bioinformatics 33:190\u2013198","journal-title":"Bioinformatics"},{"issue":"13","key":"890_CR45","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1093\/bioinformatics\/bty294","volume":"34","author":"M Zitnik","year":"2018","unstructured":"Zitnik M, Agrawal M, Leskovec J (2018) Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics 34(13):457\u2013466","journal-title":"Bioinformatics"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-022-00890-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-022-00890-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-022-00890-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,4]],"date-time":"2023-01-04T17:46:12Z","timestamp":1672854372000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-022-00890-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,17]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["890"],"URL":"https:\/\/doi.org\/10.1007\/s10618-022-00890-9","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,17]]},"assertion":[{"value":"10 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}