{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T01:18:05Z","timestamp":1789435085017,"version":"build-2803163510"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62302414, 62202404"],"award-info":[{"award-number":["62302414, 62202404"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["22202623, 25201221"],"award-info":[{"award-number":["22202623, 25201221"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>A bipartite graph contains inter-set edges between two disjoint vertex sets, and is widely used to model real-world data, such as user-item purchase records, author-article publications, and biological interactions between drugs and proteins. k-Bipartite Graph Clustering (k-BGC) is to partition the target vertex set in a bipartite graph into k disjoint clusters. The clustering quality is important to the utility of k-BGC in various applications like social network analysis, recommendation systems, text mining, and bioinformatics, to name a few. Existing approaches to k-BGC either output clustering results with compromised quality due to inadequate exploitation of high-order information between vertices, or fail to handle sizable bipartite graphs with billions of edges.<\/jats:p>\n          <jats:p>Motivated by this, this paper presents two efficient k-BGC solutions, HOPE and HOPE+, which achieve state-of-the-art performance on large-scale bipartite graphs. HOPE obtains high scalability and effectiveness through a new k-BGC problem formulation based on the novel notion of high-order perspective (HOP) vectors and an efficient technique for low-rank approximation of HOP vectors. HOPE+ further elevates the k-BGC performance to another level with a judicious problem transformation and a highly efficient two-stage optimization framework. Two variants, HOPE+ (FNEM) and HOPE+ (SNEM) are designed when either the Frobenius norm or spectral norm is applied in the transformation. Extensive experiments, comparing HOPE and HOPE+ against 13 competitors on 10 real-world datasets, exhibit that our solutions, especially HOPE+, are superior to existing methods in terms of result quality, while being up to orders of magnitude faster. On the largest dataset MAG with 1.1 billion edges, HOPE+ is able to produce clusters with the highest clustering accuracy within 31 minutes, which is unmatched by any existing solution for k-BGC.<\/jats:p>","DOI":"10.1145\/3639278","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-27","source":"Crossref","is-referenced-by-count":15,"title":["Efficient High-Quality Clustering for Large Bipartite Graphs"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7284-3096","authenticated-orcid":false,"given":"Renchi","family":"Yang","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0465-1551","authenticated-orcid":false,"given":"Jieming","family":"Shi","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(77)90114-7"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.066102"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.2956795"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.036113"},{"key":"e_1_2_1_5_1","volume-title":"International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=r1ZdKJ-0W","author":"Bojchevski Aleksandar","year":"2018","unstructured":"Aleksandar Bojchevski and Stephan G\u00fcnnemann. 2018. Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking. In International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=r1ZdKJ-0W"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Aleksandar Bojchevski Johannes Klicpera Bryan Perozzi Amol Kapoor Martin Blais Benedek R\u00f3zemberczki Michal Lukasik and Stephan G\u00fcnnemann. 2020. Scaling Graph Neural Networks with Approximate PageRank. In SIGKDD.","DOI":"10.1145\/3394486.3403296"},{"key":"e_1_2_1_7_1","article-title":"Detecting the number of clusters in a network","volume":"8","author":"Budel Gabriel","year":"2020","unstructured":"Gabriel Budel and Piet Van Mieghem. 2020. Detecting the number of clusters in a network. Journal of Complex Networks, Vol. 8, 6 (2020), cnaa047.","journal-title":"Journal of Complex Networks"},{"key":"e_1_2_1_8_1","volume-title":"Bipartite Network Community Detection: Algorithms and Applications","author":"Pes\u00e1ntez Cabrera Paola Gabriela","unstructured":"Paola Gabriela Pes\u00e1ntez Cabrera. 2018. Bipartite Network Community Detection: Algorithms and Applications. Washington State University."},{"key":"e_1_2_1_9_1","volume-title":"Music Recommendation and Discovery in the Long Tail","author":"Celma O.","unstructured":"O. Celma. 2010. Music Recommendation and Discovery in the Long Tail. Springer."},{"key":"e_1_2_1_10_1","first-page":"93","article-title":"Biclustering of expression data","volume":"8","author":"Cheng Yizong","year":"2000","unstructured":"Yizong Cheng and George M Church. 2000. Biclustering of expression data.. In Ismb, Vol. 8. 93--103.","journal-title":"Ismb"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281218"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502550"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1111\/2041-210X.12139"},{"key":"e_1_2_1_14_1","volume-title":"Network structure and biodiversity loss in food webs: robustness increases with connectance. Ecology letters","author":"Dunne Jennifer A","year":"2002","unstructured":"Jennifer A Dunne, Richard J Williams, and Neo D Martinez. 2002. Network structure and biodiversity loss in food webs: robustness increases with connectance. Ecology letters, Vol. 5, 4 (2002), 558--567."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.35.11.652"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Workshop on Semantic Web Technologies for Searching and Retrieving Scientific Data. Colocated with the Second International Semantic Web Conference (ISWC-03)","author":"Frederico Fonseca Yiling Chen","year":"2003","unstructured":"Yiling Chen Frederico Fonseca. 2003. A bipartite graph co-clustering approach to ontology mapping. In Proceedings of the Workshop on Semantic Web Technologies for Searching and Retrieving Scientific Data. Colocated with the Second International Semantic Web Conference (ISWC-03), CEUR-WS. org."},{"key":"e_1_2_1_17_1","volume-title":"Community detection in graphs. Physics reports","author":"Fortunato Santo","year":"2010","unstructured":"Santo Fortunato. 2010. Community detection in graphs. Physics reports, Vol. 486, 3--5 (2010), 75--174."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0605965104"},{"key":"e_1_2_1_19_1","volume-title":"Advanced methods for knowledge discovery from complex data","author":"Getoor Lise","unstructured":"Lise Getoor. 2005. Link-based classification. In Advanced methods for knowledge discovery from complex data. Springer, 189--207."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_21_1","volume-title":"Matrix computations","author":"Golub Gene H","year":"1996","unstructured":"Gene H Golub and Charles F Van Loan. 1996. Matrix computations. Johns Hopkins University, Press (1996)."},{"key":"e_1_2_1_22_1","volume-title":"Procrustes problems","author":"Gower John C","unstructured":"John C Gower and Garmt B Dijksterhuis. 2004. Procrustes problems. Vol. 30. OUP Oxford."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036102"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2307\/2346830"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.149"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018667"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908075"},{"key":"e_1_2_1_28_1","volume-title":"Invariant properties in coevolutionary networks of plant--animal interactions. Ecology letters","author":"Jordano Pedro","year":"2003","unstructured":"Pedro Jordano, Jordi Bascompte, and Jens M Olesen. 2003. Invariant properties in coevolutionary networks of plant--animal interactions. Ecology letters, Vol. 6, 1 (2003), 69--81."},{"key":"e_1_2_1_29_1","volume-title":"Finding groups in data: an introduction to cluster analysis","author":"Kaufman Leonard","unstructured":"Leonard Kaufman and Peter J Rousseeuw. 2009. Finding groups in data: an introduction to cluster analysis. Vol. 344. John Wiley & Sons."},{"key":"e_1_2_1_30_1","volume-title":"An efficient heuristic procedure for partitioning graphs. The Bell system technical journal","author":"Kernighan Brian W","year":"1970","unstructured":"Brian W Kernighan and Shen Lin. 1970. An efficient heuristic procedure for partitioning graphs. The Bell system technical journal, Vol. 49, 2 (1970), 291--307."},{"key":"e_1_2_1_31_1","volume-title":"Spectral biclustering of microarray data: coclustering genes and conditions. Genome research","author":"Kluger Yuval","year":"2003","unstructured":"Yuval Kluger, Ronen Basri, Joseph T Chang, and Mark Gerstein. 2003. Spectral biclustering of microarray data: coclustering genes and conditions. Genome research, Vol. 13, 4 (2003), 703--716."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.90.012805"},{"key":"e_1_2_1_33_1","volume-title":"Biclique communities. Physical review E","author":"Lehmann Sune","year":"2008","unstructured":"Sune Lehmann, Martin Schwartz, and Lars Kai Hansen. 2008. Biclique communities. Physical review E, Vol. 78, 1 (2008), 016108."},{"key":"e_1_2_1_34_1","volume-title":"Drug repositioning for personalized medicine. Genome medicine","author":"Li Yvonne Y","year":"2012","unstructured":"Yvonne Y Li and Steven JM Jones. 2012. Drug repositioning for personalized medicine. Genome medicine, Vol. 4 (2012), 1--14."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1527\/tjsai.25.16"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0097823"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSE.2009.81"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0030028"},{"key":"e_1_2_1_39_1","volume-title":"Finding community structure in networks using the eigenvectors of matrices. Physical review E","author":"Newman Mark EJ","year":"2006","unstructured":"Mark EJ Newman. 2006. Finding community structure in networks using the eigenvectors of matrices. Physical review E, Vol. 74, 3 (2006), 036104."},{"key":"e_1_2_1_40_1","volume-title":"Finding and evaluating community structure in networks. Physical review E","author":"Newman Mark EJ","year":"2004","unstructured":"Mark EJ Newman and Michelle Girvan. 2004. Finding and evaluating community structure in networks. Physical review E, Vol. 69, 2 (2004), 026113."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1101\/105197"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/11569596_31"},{"key":"e_1_2_1_44_1","series-title":"SIAM journal on matrix analysis and applications","volume-title":"Partitioning sparse matrices with eigenvectors of graphs","author":"Pothen Alex","year":"1990","unstructured":"Alex Pothen, Horst D Simon, and Kang-Pu Liou. 1990. Partitioning sparse matrices with eigenvectors of graphs. SIAM journal on matrix analysis and applications, Vol. 11, 3 (1990), 430--452."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3411866"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tree.2007.11.003"},{"key":"e_1_2_1_47_1","volume-title":"Collective classification in network data. AI magazine","author":"Sen Prithviraj","year":"2008","unstructured":"Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008. Collective classification in network data. AI magazine, Vol. 29, 3 (2008), 93--93."},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Arnab Sinha Zhihong Shen Yang Song Hao Ma Darrin Eide and Kuansan Wang. 2015. An Overview of Microsoft Academic Service (MAS) and Applications. In The WebConf.","DOI":"10.1145\/2740908.2742839"},{"key":"e_1_2_1_49_1","volume-title":"Introduction to linear algebra","author":"Strang Gilbert","unstructured":"Gilbert Strang, Gilbert Strang, Gilbert Strang, and Gilbert Strang. 1993. Introduction to linear algebra. Vol. 3. Wellesley-Cambridge Press."},{"key":"e_1_2_1_50_1","first-page":"583","article-title":"Cluster ensembles--a knowledge reuse framework for combining multiple partitions","volume":"3","author":"Strehl Alexander","year":"2002","unstructured":"Alexander Strehl and Joydeep Ghosh. 2002. Cluster ensembles--a knowledge reuse framework for combining multiple partitions. Journal of machine learning research, Vol. 3, Dec (2002), 583--617.","journal-title":"Journal of machine learning research"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSE.2009.451"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-72150-7_23"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557109"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.70"},{"key":"e_1_2_1_55_1","volume-title":"A tutorial on spectral clustering. Statistics and computing","author":"Luxburg Ulrike Von","year":"2007","unstructured":"Ulrike Von Luxburg. 2007. A tutorial on spectral clustering. Statistics and computing, Vol. 17, 4 (2007), 395--416."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098072"},{"key":"e_1_2_1_57_1","unstructured":"David P Woodruff. 2014. Sketching as a Tool for Numerical Linear Algebra. (2014)."},{"key":"e_1_2_1_58_1","volume-title":"MIND: A Large-scale Dataset for News Recommendation. In ACL. 3597--3606.","author":"Wu Fangzhao","year":"2020","unstructured":"Fangzhao Wu, Ying Qiao, Jiun-Hung Chen, Chuhan Wu, Tao Qi, Jianxun Lian, Danyang Liu, Xing Xie, Jianfeng Gao, Winnie Wu, and Ming Zhou. 2020. MIND: A Large-scale Dataset for News Recommendation. In ACL. 3597--3606."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835776.2835836"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v28i1.8950"},{"key":"e_1_2_1_61_1","doi-asserted-by":"crossref","unstructured":"Wei Xu Xin Liu and Yihong Gong. 2003. Document clustering based on non-negative matrix factorization. In SIGIR. 267--273.","DOI":"10.1145\/860435.860485"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3511959"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517838"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377376"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449875"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020491"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.102.032309"},{"key":"e_1_2_1_68_1","volume-title":"Evolutionary method for finding communities in bipartite networks. Physical review E","author":"Zhan Weihua","year":"2011","unstructured":"Weihua Zhan, Zhongzhi Zhang, Jihong Guan, and Shuigeng Zhou. 2011. Evolutionary method for finding communities in bipartite networks. Physical review E, Vol. 83, 6 (2011), 066120."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233324"},{"key":"e_1_2_1_70_1","volume-title":"Bipartite network projection and personal recommendation. Physical review E","author":"Zhou Tao","year":"2007","unstructured":"Tao Zhou, Jie Ren, Mat\u00favs Medo, and Yi-Cheng Zhang. 2007. Bipartite network projection and personal recommendation. Physical review E, Vol. 76, 4 (2007), 046115."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-011-0021-0"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639278","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639278","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:14:23Z","timestamp":1755789263000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639278"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":71,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639278"],"URL":"https:\/\/doi.org\/10.1145\/3639278","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}