Maximum biclique search at billion scale

Lyu, B; Qin, L; Lin, X; Zhang, Y; Qian, Z; Zhou, J

Maximum biclique search at billion scale

Lyu, B Qin, L

Lin, X Zhang, Y

Qian, Z Zhou, J

Permalink

Publisher:: ASSOC COMPUTING MACHINERY
Publication Type:: Journal Article
Citation:: Proceedings of the VLDB Endowment, 2020, 13, (9), pp. 1359-1372
Issue Date:: 2020-05-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published versionAdobe PDF (622.05 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Lyu, B
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Lin, X
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Qian, Z
dc.contributor.author	Zhou, J
dc.date.accessioned	2021-02-28T21:19:43Z
dc.date.available	2021-02-28T21:19:43Z
dc.date.issued	2020-05-01
dc.identifier.citation	Proceedings of the VLDB Endowment, 2020, 13, (9), pp. 1359-1372
dc.identifier.issn	2150-8097
dc.identifier.issn	2150-8097
dc.identifier.uri	http://hdl.handle.net/10453/146526
dc.description.abstract	© 2020, VLDB Endowment. Maximum biclique search, which finds the biclique with the maximum number of edges in a bipartite graph, is a fun-damental problem with a wide spectrum of applications in different domains, such as E-Commerce, social analysis, web services, and bioinformatics. Unfortunately, due to the dif-ficulty of the problem in graph theory, no practical solution has been proposed to solve the issue in large-scale real-world datasets. Existing techniques for maximum clique search on a general graph cannot be applied because the search objec-tive of maximum biclique search is two-dimensional, i.e., we have to consider the size of both parts of the biclique simul-taneously. In this paper, we divide the problem into several subproblems each of which is specified using two parameters. These subproblems are derived in a progressive manner, and in each subproblem we can restrict the search in a very small part of the original bipartite graph. We prove that a loga-rithmic number of subproblems is enough to guarantee the algorithm correctness. To minimize the computational cost, we show how to reduce significantly the bipartite graph size for each subproblem while preserving the maximum biclique satisfying certain constraints by exploring the properties of one-hop and two-hop neighbors for each vertex. We use several real datasets from various application domains, one of which contains over 300 million vertices and 1:3 billion edges, to demonstrate the high efficiency and scalability of our proposed solution. It is reported that 50% improve-ment on recall can be achieved after applying our method in Alibaba Group to identify the fraudulent transactions in their e-commerce networks. This further demonstrates the usefulness of our techniques in practice.
dc.language	English
dc.publisher	ASSOC COMPUTING MACHINERY
dc.relation.ispartof	Proceedings of the VLDB Endowment
dc.relation.isbasedon	10.14778/3397230.3397234
dc.rights	This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. To view a copyof this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. Forany use beyond those covered by this license, obtain permission by emailinginfo@vldb.org. Copyright is held by the owner/author(s). Publication rightslicensed to the VLDB Endowment.
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	0802 Computation Theory and Mathematics, 0806 Information Systems, 0807 Library and Information Studies
dc.title	Maximum biclique search at billion scale
dc.type	Journal Article
utslib.citation.volume	13
utslib.for	0802 Computation Theory and Mathematics
utslib.for	0806 Information Systems
utslib.for	0807 Library and Information Studies
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	open_access	*
dc.date.updated	2021-02-28T21:19:41Z
pubs.issue	9
pubs.publication-status	Published
pubs.volume	13
utslib.citation.issue	9

Abstract:

© 2020, VLDB Endowment. Maximum biclique search, which finds the biclique with the maximum number of edges in a bipartite graph, is a fun-damental problem with a wide spectrum of applications in different domains, such as E-Commerce, social analysis, web services, and bioinformatics. Unfortunately, due to the dif-ficulty of the problem in graph theory, no practical solution has been proposed to solve the issue in large-scale real-world datasets. Existing techniques for maximum clique search on a general graph cannot be applied because the search objec-tive of maximum biclique search is two-dimensional, i.e., we have to consider the size of both parts of the biclique simul-taneously. In this paper, we divide the problem into several subproblems each of which is specified using two parameters. These subproblems are derived in a progressive manner, and in each subproblem we can restrict the search in a very small part of the original bipartite graph. We prove that a loga-rithmic number of subproblems is enough to guarantee the algorithm correctness. To minimize the computational cost, we show how to reduce significantly the bipartite graph size for each subproblem while preserving the maximum biclique satisfying certain constraints by exploring the properties of one-hop and two-hop neighbors for each vertex. We use several real datasets from various application domains, one of which contains over 300 million vertices and 1:3 billion edges, to demonstrate the high efficiency and scalability of our proposed solution. It is reported that 50% improve-ment on recall can be achieved after applying our method in Alibaba Group to identify the fraudulent transactions in their e-commerce networks. This further demonstrates the usefulness of our techniques in practice.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/146526