{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T06:34:32Z","timestamp":1774766072685,"version":"3.50.1"},"reference-count":42,"publisher":"MIT Press","issue":"5","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Graph clustering, which aims to partition a set of graphs into groups with similar structures, is a fundamental task in data analysis. With the great advances made by deep learning, deep graph clustering methods have achieved success. However, these methods have two limitations: (1) they learn graph embeddings by a neural language model that fails to effectively express graph properties, and (2) they treat embedding learning and clustering as two isolated processes, so the learned embeddings are unsuitable for the subsequent clustering. To overcome these limitations, we propose a novel capsule-based graph clustering (CGC) algorithm to cluster graphs. First, we construct a graph clustering capsule network (GCCN) that introduces capsules to capture graph properties. Second, we design an iterative optimization strategy to alternately update the GCCN parameters and clustering assignment parameters. This strategy leads GCCN to learn cluster-oriented graph embeddings. Experimental results show that our algorithm achieves performance superior to that of existing graph clustering algorithms in terms of three standard evaluation metrics: ACC, NMI, and ARI. Moreover, we use visualization results to analyze the effectiveness of the capsules and demonstrate that GCCN can learn cluster-oriented embeddings.<\/jats:p>","DOI":"10.1162\/neco_a_01493","type":"journal-article","created":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T23:22:03Z","timestamp":1648509723000},"page":"1256-1287","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":3,"title":["Graph Clustering With Graph Capsule Network"],"prefix":"10.1162","volume":"34","author":[{"given":"Xianchao","family":"Zhang","sequence":"first","affiliation":[{"name":"School of Software, Dalian University of Technology, Dalian 116024, China"},{"name":"Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province, Dalian 116024, China xczhang@dlut.edu.cn"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Mu","sequence":"additional","affiliation":[{"name":"School of Software, Dalian University of Technology, Dalian 116024, China"},{"name":"Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province, Dalian 116024, China jiem@mail.dlut.edu.cn"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Han","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Software, Dalian University of Technology, Dalian 116024, China"},{"name":"Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province, Dalian 116024, China liu.han.dut@gmail.com"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaotong","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Software, Dalian University of Technology, Dalian 116024, China"},{"name":"Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province, Dalian 116024, China zxt.dut@hotmail.com"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Linlin","family":"Zong","sequence":"additional","affiliation":[{"name":"School of Software, Dalian University of Technology, Dalian 116024, China"},{"name":"Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province, Dalian 116024, China llzong@dlut.edu.cn"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guanglu","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Software, Dalian University of Technology, Dalian 116024, China"},{"name":"Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province, Dalian 116024, China glwang@mail.dlut.edu.cn"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2022,4,15]]},"reference":[{"key":"2022042221321248700_B1","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1145\/1281192.1281201","article-title":"Xproj: A framework for projected structural clustering of XML documents","volume-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Aggarwal","year":"2007"},{"key":"2022042221321248700_B2","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/978-1-4419-6045-0_9","volume-title":"Managing and mining graph data","author":"Aggarwal","year":"2010"},{"key":"2022042221321248700_B3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-662-44415-3_1","article-title":"A graph kernel from the depth- based representation","volume-title":"Proceedings of the Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition and Structural and Syntactic Pattern Recognition","author":"Bai","year":"2014"},{"key":"2022042221321248700_B4","first-page":"2729","article-title":"Spectral clustering with graph neural networks for graph pooling","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Bianchi","year":"2020"},{"key":"2022042221321248700_B5","doi-asserted-by":"crossref","DOI":"10.1109\/ICDM.2005.132","article-title":"Shortest-path kernels on graphs","volume-title":"Proceedings of the IEEE International Conference on Data Mining","author":"Borgwardt","year":"2005"},{"key":"2022042221321248700_B6","article-title":"Videocapsulenet: A simplified network for action detection","volume-title":"Advances in neural information processing systems","author":"Duarte","year":"2018"},{"key":"2022042221321248700_B7","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/978-3-540-45167-9_11","volume-title":"Learning theory and kernel machines","author":"G\u00e4rtner","year":"2003"},{"key":"2022042221321248700_B8","doi-asserted-by":"crossref","DOI":"10.1145\/2939672.2939754","article-title":"Node2vec: scalable feature learning for networks","volume-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Grover","year":"2016"},{"key":"2022042221321248700_B9","first-page":"1753","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence","author":"Guo","year":"2017"},{"key":"2022042221321248700_B10","first-page":"307","article-title":"Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics","volume":"13","author":"Gutmann","year":"2012","journal-title":"Journal of Machine Learning Research"},{"key":"2022042221321248700_B11","first-page":"4116","article-title":"Contrastive multi-view representation learning on graphs","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Hassani","year":"2020"},{"key":"2022042221321248700_B12","first-page":"78","article-title":"Generalized shortest path kernel on graphs","volume-title":"Proceedings of the International Conference on Discovery Science","author":"Hermansson","year":"2015"},{"key":"2022042221321248700_B13","first-page":"44","article-title":"Transforming auto-encoders","volume-title":"Proceedings of the International Conference on Artificial Neural Networks, Lecture Notes in Computer Science","author":"Hinton","year":"2011"},{"key":"2022042221321248700_B14","article-title":"Matrix capsules with EM routing","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Hinton","year":"2018"},{"key":"2022042221321248700_B15","first-page":"2191","article-title":"Anonymous walk embeddings","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Ivanov","year":"2018"},{"key":"2022042221321248700_B16","article-title":"Certified robustness of graph convolution networks for graph classification under topological attacks","volume-title":"Advances in neural information processing systems","author":"Jin","year":"2020"},{"key":"2022042221321248700_B17","first-page":"2982","article-title":"The multiscale Laplacian graph kernel","volume-title":"Advances in neural information processing systems","author":"Kondor","year":"2016"},{"key":"2022042221321248700_B18","first-page":"881","article-title":"Explicit versus implicit graph feature maps: A computational phase transition for walk kernels","volume-title":"Proceedings of the IEEE International Conference on Data Mining","author":"Kriege","year":"2014"},{"key":"2022042221321248700_B19","author":"LaLonde","year":"2018","journal-title":"Capsules for object segmentation"},{"key":"2022042221321248700_B20","first-page":"8858","article-title":"Group equivariant capsule networks","volume-title":"Advances in neural information processing systems","author":"Lenssen","year":"2018"},{"key":"2022042221321248700_B21","first-page":"266","article-title":"Neural network encapsulation","volume-title":"Proceedings of the European Conference on Computer Vision","author":"Li","year":"2018"},{"key":"2022042221321248700_B22","first-page":"2579","article-title":"Visualizing data using t-SNE","volume":"9","author":"Maaten","year":"2008","journal-title":"Journal of Machine Learning Research"},{"key":"2022042221321248700_B23","first-page":"5134","article-title":"Graph-hist: Graph classification from latent feature histograms with application to bot detection","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","author":"Magelinski","year":"2020"},{"key":"2022042221321248700_B24","first-page":"327","article-title":"Glocalized Weisfeiler-Lehman graph kernels: Global-local feature maps of graphs","volume-title":"Proceedings of the IEEE International Conference on Data Mining","author":"Morris","year":"2017"},{"key":"2022042221321248700_B25","volume-title":"Subgraph2vec: Learning distributed representations of rooted sub-graphs from large graphs.","author":"Narayanan","year":"2016"},{"key":"2022042221321248700_B26","article-title":"Graph2vec: Learning distributed representations of graphs","volume-title":"Proceedings of the 13 International Workshop on Mining and Learning with Graphs","author":"Narayanan","year":"2017"},{"key":"2022042221321248700_B27","article-title":"Dynamic routing between capsules","volume-title":"Advances in neural information processing systems, 30.","author":"Sabour","year":"2017"},{"key":"2022042221321248700_B28","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","article-title":"Graph clustering","volume":"1","author":"Schaeffer","year":"2007","journal-title":"Computer Science Review"},{"key":"2022042221321248700_B29","first-page":"1660","volume-title":"Advances in neural information processing systems","author":"Shervashidze","year":"2009"},{"key":"2022042221321248700_B30","first-page":"2539","article-title":"Weisfeiler-Lehman graph kernels","volume":"12","author":"Shervashidze","year":"2011","journal-title":"Journal of Machine Learning Research"},{"key":"2022042221321248700_B31","article-title":"Efficient graphlet kernels for large graph comparison","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics","author":"Shervashidze","year":"2009"},{"key":"2022042221321248700_B32","article-title":"Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Sun","year":"2020"},{"key":"2022042221321248700_B33","first-page":"2837","article-title":"Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance","volume":"11","author":"Vinh","year":"2010","journal-title":"Journal of Machine Learning Research"},{"key":"2022042221321248700_B34","article-title":"Capsule graph neural network","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Xinyi","year":"2019"},{"key":"2022042221321248700_B35","article-title":"How powerful are graph neural networks?","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Xu","year":"2019"},{"key":"2022042221321248700_B36","first-page":"267","article-title":"Document clustering based on non-negative matrix factorization","volume-title":"Proceedings of the Annual International ACM SIGIR Conference on Research and Development in Information Retrieval","author":"Xu","year":"2003"},{"key":"2022042221321248700_B37","first-page":"1365","article-title":"Deep graph kernels","volume-title":"ACM International Conference on Knowledge Discovery and Data Mining","author":"Yanardag","year":"2015"},{"key":"2022042221321248700_B38","first-page":"858","article-title":"Graph clustering with embedding propagation","volume-title":"Proceedings of the IEEE International Conference on Big Data","author":"Yang","year":"2020"},{"key":"2022042221321248700_B39","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1093\/bioinformatics\/17.9.763","article-title":"Details of the adjusted Rand Index and clustering algorithms, supplement to the paper on empirical study on principal component analysis for clustering gene expression data","volume":"17","author":"Yeung","year":"2001","journal-title":"Bioinformatics"},{"key":"2022042221321248700_B40","first-page":"4805","volume-title":"Advances in neural information processing systems","author":"Ying","year":"2018"},{"key":"2022042221321248700_B41","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.aiopen.2021.01.001","article-title":"Graph neural networks: A review of methods and applications","volume":"1","author":"Zhou","year":"2020","journal-title":"AI Open"},{"key":"2022042221321248700_B42","first-page":"9324","article-title":"Dynamic capsule attention for visual question answering","volume-title":"Proceedings of the Association for the Advancement of Artificial Intelligence","author":"Zhou","year":"2019"}],"container-title":["Neural Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/34\/5\/1256\/2008640\/neco_a_01493.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/34\/5\/1256\/2008640\/neco_a_01493.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T04:40:25Z","timestamp":1726893625000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/neco\/article\/34\/5\/1256\/110048\/Graph-Clustering-With-Graph-Capsule-Network"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,15]]},"references-count":42,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2022,4,15]]},"published-print":{"date-parts":[[2022,4,15]]}},"URL":"https:\/\/doi.org\/10.1162\/neco_a_01493","relation":{},"ISSN":["0899-7667","1530-888X"],"issn-type":[{"value":"0899-7667","type":"print"},{"value":"1530-888X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,5]]},"published":{"date-parts":[[2022,4,15]]}}}