Efficient Maximum Signed Biclique Identification

Sun, R; Chen, C; Wang, X; Zhang, W; Zhang, Y; Lin, X

Efficient Maximum Signed Biclique Identification

Sun, R Chen, C Wang, X Zhang, W Zhang, Y

Lin, X

Permalink

Publisher:: Institute of Electrical and Electronics Engineers (IEEE)
Publication Type:: Conference Proceeding
Citation:: Proceedings - International Conference on Data Engineering, 2023, 2023-April, pp. 1313-1325
Issue Date:: 2023-01-01

Embargoed

	Filename	Description	Size
	Efficient Maximum Signed Biclique Identification.pdf	Accepted version	1.46 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Embargoed
Open Access

This item is currently unavailable due to the publisher's embargo.

The embargo period expires on 26 Jul 2025

Full metadata record

Field	Value	Language
dc.contributor.author	Sun, R
dc.contributor.author	Chen, C
dc.contributor.author	Wang, X
dc.contributor.author	Zhang, W
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Lin, X
dc.date	2023-04-03
dc.date.accessioned	2024-03-04T03:57:56Z
dc.date.available	2024-03-04T03:57:56Z
dc.date.issued	2023-01-01
dc.identifier.citation	Proceedings - International Conference on Data Engineering, 2023, 2023-April, pp. 1313-1325
dc.identifier.isbn	9798350322279
dc.identifier.issn	1084-4627
dc.identifier.uri	http://hdl.handle.net/10453/176063
dc.description.abstract	Maximum biclique identification, which aims to find the biclique with the largest size, can find a wide spectrum of applications in different domains, such as E-Commerce, healthcare and bioinformatics. However, the previous studies mainly focus on unsigned bipartite graphs. The signed information naturally exists in real applications, such as like and dislike. The neglect of signed information may fail to discover the inherent properties of networks. In this paper, we propose a novel model, named signed (k,l)-biclique (SKLB), by enforcing constraints over the number of positive and negative connections. Specifically, given a signed bipartite graph and two positive integers k,l, SKLB is a biclique, where each vertex has no less than k positive neighbors and no more than l negative neighbors. We prove the problem of finding the maximum signed (k,l)-biclique (MaxSKLB) is NP-hard. Moreover, we show that the problem is still NP-hard, even if the input graph is a biclique itself. A baseline algorithm is first presented through biclique enumeration, which tries to find the MaxSKLB for each encountered biclique and return the largest one. However, considering that the extraction of MaxSKLB from a biclique is still NP-hard, a greedy strategy is developed to accelerate the processing with competitive result. Furthermore, to efficiently handle large graphs, we optimize the algorithm from different perspectives, including unnecessary search branches and unpromising vertices filtering. Finally, comprehensive experiments are conducted over 10 graphs to validate the efficiency and effectiveness of proposed techniques and model.
dc.language	en
dc.publisher	Institute of Electrical and Electronics Engineers (IEEE)
dc.relation	http://purl.org/au-research/grants/arc/DP210101393
dc.relation	http://purl.org/au-research/grants/arc/DP230101445
dc.relation	http://purl.org/au-research/grants/arc/LP210301046
dc.relation	http://purl.org/au-research/grants/arc/DP240101322
dc.relation.ispartof	Proceedings - International Conference on Data Engineering
dc.relation.ispartof	2023 IEEE 39th International Conference on Data Engineering (ICDE)
dc.relation.isbasedon	10.1109/ICDE55515.2023.00105
dc.rights	info:eu-repo/semantics/embargoedAccess
dc.title	Efficient Maximum Signed Biclique Identification
dc.type	Conference Proceeding
utslib.citation.volume	2023-April
pubs.organisational-group	University of Technology Sydney
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
utslib.copyright.status	embargoed	*
utslib.copyright.embargo	2025-07-26T00:00:00+1000Z
dc.date.updated	2024-03-04T03:57:55Z
pubs.finish-date	2023-04-07
pubs.publication-status	Published
pubs.start-date	2023-04-03
pubs.volume	2023-April

Abstract:

Maximum biclique identification, which aims to find the biclique with the largest size, can find a wide spectrum of applications in different domains, such as E-Commerce, healthcare and bioinformatics. However, the previous studies mainly focus on unsigned bipartite graphs. The signed information naturally exists in real applications, such as like and dislike. The neglect of signed information may fail to discover the inherent properties of networks. In this paper, we propose a novel model, named signed (k,l)-biclique (SKLB), by enforcing constraints over the number of positive and negative connections. Specifically, given a signed bipartite graph and two positive integers k,l, SKLB is a biclique, where each vertex has no less than k positive neighbors and no more than l negative neighbors. We prove the problem of finding the maximum signed (k,l)-biclique (MaxSKLB) is NP-hard. Moreover, we show that the problem is still NP-hard, even if the input graph is a biclique itself. A baseline algorithm is first presented through biclique enumeration, which tries to find the MaxSKLB for each encountered biclique and return the largest one. However, considering that the extraction of MaxSKLB from a biclique is still NP-hard, a greedy strategy is developed to accelerate the processing with competitive result. Furthermore, to efficiently handle large graphs, we optimize the algorithm from different perspectives, including unnecessary search branches and unpromising vertices filtering. Finally, comprehensive experiments are conducted over 10 graphs to validate the efficiency and effectiveness of proposed techniques and model.

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

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