AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (2.2 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Efficient Maximum Vertex (k,ℓ)-Biplex Computation on Bipartite Graphs

School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen 518055, China
Science and Technology Office, Harbin Institute of Technology, Shenzhen 518055, China
Show Author Information

Abstract

Cohesive subgraph search is a fundamental problem in bipartite graph analysis. Given integers k and ℓ, a (k,ℓ)-biplex is a cohesive structure which requires each vertex to disconnect at most k or ℓ vertices in the other side. Computing (k,ℓ)-biplexes has been a popular research topic in recent years and has various applications. However, most existing studies considered the problem of finding (k,ℓ)-biplex with the largest number of edges. In this paper, we instead consider another variant and focus on the maximum vertex (k,ℓ)-biplex problem which aims to search for a (k,ℓ)-biplex with the maximum cardinality. We first show that this problem is Non-deterministic Polynomial-time hard (NP-hard) for any positive integers k and ℓ while max{k,ℓ} is at least 3. Guided by this negative result, we design an efficient branch-and-bound algorithm with a novel framework. In particular, we introduce a branching strategy based on whether there is a pivot in the current set, with which our proposed algorithm has the time complexity of γnnO(1), where γ<2. In addition, we also apply multiple speed-up techniques and various pruning strategies. Finally, we conduct extensive experiments on various real datasets which demonstrate the efficiency of our proposed algorithm in terms of running time.

Keywords

bipartite graphscohesive subgraph searchmaximum vertex $(k,\ell)$-biplexbranch-and-bound algorithm

References

[1]
J. Wang, A. P. de Vries, and M. J. T. Reinders, Unifying user-based and item-based collaborative filtering approaches by similarity fusion, in Proc. 29th Annual Int. ACM SIGIR Conf. Research and Development in Information Retrieval, Seattle, WA, USA, 2006, pp. 501–508.
Crossref
[2]

Y. Zhang, C. A. Phillips, G. L. Rogers, E. J. Baker, E. J. Chesler, and M. A. Langston, On finding bicliques in bipartite graphs: A novel algorithm and its application to the integration of diverse biological data types, BMC Bioinformatics, vol. 15, p. 110, 2014.
Crossref Google Scholar
[3]

B. Lyu, L. Qin, X. Lin, Y. Zhang, Z. Qian, and J. Zhou, Maximum biclique search at billion scale, Proc. VLDB Endow., vol. 13, no. 9, pp. 1359–1372, 2020.
Crossref Google Scholar
[4]

S. Selvan and R. V. Nataraj, Efficient mining of large maximal bicliques from 3D symmetric adjacency matrix, IEEE Trans. Knowl. Data Eng., vol. 22, no. 12, pp. 1797–1802, 2010.
Crossref Google Scholar
[5]
A. Ahmed, V. Batagelj, X. Fu, S. H. Hong, D. Merrick, and A. Mrvar, Visualisation and analysis of the Internet movie database, in Proc. 6th Int. Asia-Pacific Symp. on Visualization, Sydney, Australia, 2007, pp. 17–24.
Crossref
[6]

K. Sim, J. Li, V. Gopalkrishnan, and G. Liu, Mining maximal quasi-bicliques: Novel algorithm and applications in the stock market and protein networks, Stat. Anal. Data Min., vol. 2, no. 4, pp. 255–273, 2009.
Crossref Google Scholar
[7]

N. Mishra, D. Ron, and R. Swaminathan, A new conceptual clustering framework, Mach. Lang., vol. 56, nos. 1–3, pp. 115–151, 2004.
Crossref Google Scholar
[8]

K. Yu and C. Long, Maximum k-biplex search on bipartite graphs: A symmetric-BK branching approach, Proc. ACM Manag. Data, vol. 1, no. 1, p. 49, 2023.
Crossref Google Scholar
[9]

K. Yu, C. Long, P. Deepak, and T. Chakraborty, On efficient large maximal biplex discovery, IEEE Trans. Knowl. Data Eng., vol. 35, no. 1, pp. 824–829, 2021.
Crossref Google Scholar
[10]
W. Luo, K. Li, X. Zhou, Y. Gao, and K. Li, Maximum biplex search over bipartite graphs, in Proc. IEEE 38th Int. Conf. Data Engineering (ICDE), Kuala Lumpur, Malaysia, 2022, pp. 898–910.
Crossref
[11]
A. K. Poernomo and V. Gopalkrishnan, Towards efficient mining of proportional fault-tolerant frequent itemsets, in Proc. 15th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Paris, France, 2009, pp. 697–706.
Crossref
[12]

A. Tanay, R. Sharan, and R. Shamir, Discovering statistically significant biclusters in gene expression data, Bioinformatics, vol. 18, no. Suppl 1, pp. S136–S144, 2002.
Crossref Google Scholar
[13]

R. Henriques and S. C. Madeira, BicNET: Flexible module discovery in large-scale biological networks using biclustering, Algorithms Mol. Biol., vol. 11, p. 14, 2016.
Crossref Google Scholar
[14]
M. Allahbakhsh, A. Ignjatovic, B. Benatallah, S. M. R. Beheshti, E. Bertino, and N. Foo, Collusion detection in online rating systems, in Proc. 15th Asia-Pacific Web Conference, Sydney, Australia, 2013, pp. 196–207.
Crossref
[15]

B. Lyu, L. Qin, X. Lin, Y. Zhang, Z. Qian, and J. Zhou, Maximum and top- k diversified biclique search at scale, VLDB J., vol. 31, no. 6, pp. 1365–1389, 2022.
Crossref Google Scholar
[16]

L. Chang, M. Xu, and D. Strash, Efficient maximum k-plex computation over large sparse graphs, Proc. VLDB Endow., vol. 16, no. 2, pp. 127–139, 2022.
Crossref Google Scholar
[17]
C. Lund and M. Yannakakis, The approximation of maximum subgraph problems, in Automata, Languages and Programming, A. Lingas, R. Karlsson, and S. Carlsson, eds. Berlin, Germany: Springer, 1993, pp. 40–51.
Crossref
[18]
U. Feige and S. Kogan, The hardness of approximating hereditary properties, http://research.microsoft.com/research/theory/feige/homepagefiles/hereditary.pdf, 2005.
[19]
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. London, UK: Palgrave Macmillan, 1976.
Crossref
[20]

S. Trukhanov, C. Balasubramaniam, B. Balasundaram, and S. Butenko, Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations, Comput. Optim. Appl., vol. 56, no. 1, pp. 113–130, 2013.
Crossref Google Scholar
[21]

D. Eppstein, Arboricity and bipartite subgraph listing algorithms, Inf. Process. Lett., vol. 51, no. 4, pp. 207–211, 1994.
Crossref Google Scholar
[22]

J. Li, G. Liu, H. Li, and L. Wong, Maximal biclique subgraphs and closed pattern pairs of the adjacency matrix: A one-to-one correspondence and mining algorithms, IEEE Trans. Knowl. Data Eng., vol. 19, no. 12, pp. 1625–1637, 2007.
Crossref Google Scholar
[23]
A. Das, S. V. Sanei-Mehri, and S. Tirthapura, Shared-memory parallel maximal clique enumeration, in Proc. IEEE 25th Int. Conf. High Performance Computing (HiPC), Bengaluru, India, 2018, pp. 62–71.
Crossref
[24]
A. Abidi, R. Zhou, L. Chen, and C. Liu, Pivot-based maximal biclique enumeration, in Proc. 29th Int. Joint Conf. Artificial Intelligence, Yokohama, Japan, 2020, pp. 3558–3564.
Crossref
[25]

L. Chen, C. Liu, R. Zhou, J. Xu, and J. Li, Efficient maximal biclique enumeration for large sparse bipartite graphs, Proc. VLDB Endow., vol. 15, no. 8, pp. 1559–1571, 2022.
Crossref Google Scholar
[26]

M. Dawande, P. Keskinocak, J. M. Swaminathan, and S. Tayur, On bipartite and multipartite clique problems, J. Algoritms., vol. 41, no. 2, pp. 388–403, 2001.
Crossref Google Scholar
[27]

J. Hartmanis, Computers and intractability: A guide to the theory of NP-completeness (Michael R. Garey and David S. Johnson), SIAM Rev., vol. 24, no. 1, pp. 90–91, 1982.
Crossref Google Scholar
[28]

R. Peeters, The maximum edge biclique problem is NP-complete, Discrete Appl. Math., vol. 131, no. 3, pp. 651–654, 2003.
Crossref Google Scholar
[29]
E. Shaham, H. Yu, and X. L. Li, On finding the maximum edge biclique in a bipartite graph: A subspace clustering approach, in Proc. 2016 SIAM Int. Conf. Data Mining, Philadelphia, PA, USA, 2016, pp. 315–323.
Crossref
[30]
K. Wang, W. Zhang, X. Lin, L. Qin, and A. Zhou, Efficient personalized maximum biclique search, in Proc. IEEE 38th Int. Conf. Data Engineering (ICDE), Kuala Lumpur, Malaysia, 2022, pp. 498–511.
Crossref
[31]
R. Sun, Y. Wu, C. Chen, X. Wang, W. Zhang, and X. Lin, Maximal balanced signed biclique enumeration in signed bipartite graphs, in Proc. IEEE 38th Int. Conf. Data Engineering (ICDE), Kuala Lumpur, Malaysia, 2022, pp. 1887–1899.
Crossref
[32]

J. Wang, J. Yang, C. Zhang, and X. Lin, Efficient maximum edge-weighted biclique search on large bipartite graphs, IEEE Trans. Knowl. Data Eng., vol. 35, no. 8, pp. 7921–7934, 2023.
Crossref Google Scholar
[33]
K. Yu, C. Long, S. Liu, and D. Yan, Efficient algorithms for maximal k-biplex enumeration, in Proc. 2022 Int. Conf. Management of Data, Philadelphia, PA, USA, 2022, pp. 860–873.
Crossref
[34]
D. Ding, H. Li, Z. Huang, and N. Mamoulis, Efficient fault-tolerant group recommendation using alpha-beta-core, in Proc. 2017 ACM on Conf. Information and Knowledge Management, Singapore, 2017, pp. 2047–2050.
Crossref
[35]
K. Wang, W. Zhang, X. Lin, Y. Zhang, L. Qin, and Y. Zhang, Efficient and effective community search on large-scale bipartite graphs, in Proc. IEEE 37th Int. Conf. Data Engineering (ICDE), Chania, Greece, 2021, pp. 85–96.
Crossref
[36]
B. Liu, L. Yuan, X. Lin, L. Qin, W. Zhang, and J. Zhou, Efficient (α, β)-core computation: An index-based approach, in Proc. the World Wide Web Conference, San Francisco, CA, USA, 2019, pp. 1130–1141.
Crossref
[37]
Z. Zou, Bitruss decomposition of bipartite graphs, in Proc. 21st Int. Conf. Database Systems for Advanced Applications, Dallas, TX, USA, 2016, pp. 218–233.
Crossref
[38]
A. E. Sarıyüce and A. Pinar, Peeling bipartite networks for dense subgraph discovery, in Proc. 11th ACM Int. Conf. Web Search and Data Mining, Marina Del Rey, CA, USA, 2018, pp. 504–512.
Crossref
[39]
X. Liu, J. Li, and L. Wang, Modeling protein interacting groups by quasi-bicliques: Complexity, algorithm, and application, IEEE/ACM Trans. Comput. Biol. Bioinform., vol. 7, no. 2, pp. 354–364, 2010.
Crossref
[40]
Y. Onoue and K. Koyamada, Quasi-biclique edge concentration: A visual analytics method for biclustering, in Proc. IEEE Pacific Visualization Symp. (PacificVis), Seoul, Republic of Korea, 2017, pp. 215–219.
Crossref
[41]

T. F. Gonzalez, Clustering to minimize the maximum intercluster distance, Theor. Comput. Sci., vol. 38, pp. 293–306, 1985.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 30 Issue 2,
April 2025
Pages 569-584
DOI: 10.26599/TST.2024.9010009
Cite this article:
Zhou H, Liu S, Cao R. Efficient Maximum Vertex (k,ℓ)-Biplex Computation on Bipartite Graphs. Tsinghua Science and Technology, 2025, 30(2): 569-584. https://doi.org/10.26599/TST.2024.9010009

524

Views

264

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 31 July 2023
Revised: 23 October 2023
Accepted: 11 December 2023
Published: 09 December 2024
© The Author(s) 2025.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return