Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs

Wang, K; Lin, X; Qin, L; Zhang, W; Zhang, Y

Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs

Wang, K Lin, X Qin, L Zhang, W Zhang, Y

Permalink

Publisher:: Springer Science and Business Media LLC
Publication Type:: Conference Proceeding
Citation:: VLDB Journal, 2021, pp. 1-24
Issue Date:: 2021-01-01

Closed Access

	Filename	Description	Size
	Wang2021_Article_TowardsEfficientSolutionsOfBit.pdf	Accepted version	1.45 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Wang, K
dc.contributor.author	Lin, X
dc.contributor.author	Qin, L
dc.contributor.author	Zhang, W
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.date.accessioned	2021-04-12T04:53:36Z
dc.date.available	2021-04-12T04:53:36Z
dc.date.issued	2021-01-01
dc.identifier.citation	VLDB Journal, 2021, pp. 1-24
dc.identifier.issn	1066-8888
dc.identifier.issn	0949-877X
dc.identifier.uri	http://hdl.handle.net/10453/148021
dc.description.abstract	In recent years, cohesive subgraph mining in bipartite graphs becomes a popular research topic. An important cohesive subgraph model k-bitruss is the maximal cohesive subgraph where each edge is contained in at least k butterflies (i.e., (2, 2)-bicliques). In this paper, we study the bitruss decomposition problem which aims to find all the k-bitrusses for k≥ 0. The existing algorithms follow a bottom-up strategy which peels the edges with the lowest butterfly support iteratively. In this peeling process, these algorithms are time-consuming to enumerate all the supporting butterflies for each edge. To solve this issue, we propose a novel online index, the BE-Index which compresses butterflies into k-blooms (i.e., (2, k)-bicliques). Based on the BE-Index, the new bitruss decomposition algorithm BiT-BU is proposed, along with two batch-based optimizations, to accomplish the butterfly enumeration of the peeling process efficiently. Furthermore, the BiT-PC algorithm is designed which is more efficient against handling the edges with high butterfly supports. Besides, we explore shared-memory parallel solutions to handle large graphs in a more efficient way. In the parallel algorithms, we propose effective techniques to reduce conflicts among threads. We theoretically show that our new algorithms significantly reduce the time complexities of the existing algorithms. In addition, extensive empirical evaluations are conducted on real-world datasets. The experimental results further validate the effectiveness of the bitruss model and demonstrate that our proposed solutions significantly outperform the state-of-the-art techniques by several orders of magnitude.
dc.language	en
dc.publisher	Springer Science and Business Media LLC
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation	http://purl.org/au-research/grants/arc/DP210101393
dc.relation	http://purl.org/au-research/grants/arc/FT200100787
dc.relation.ispartof	VLDB Journal
dc.relation.isbasedon	10.1007/s00778-021-00658-5
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0804 Data Format, 0805 Distributed Computing, 0806 Information Systems
dc.subject.classification	Information Systems
dc.title	Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs
dc.type	Conference Proceeding
utslib.for	0804 Data Format
utslib.for	0805 Distributed Computing
utslib.for	0806 Information Systems
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
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access	*
dc.date.updated	2021-04-12T04:53:35Z
pubs.publication-status	Published

Abstract:

In recent years, cohesive subgraph mining in bipartite graphs becomes a popular research topic. An important cohesive subgraph model k-bitruss is the maximal cohesive subgraph where each edge is contained in at least k butterflies (i.e., (2, 2)-bicliques). In this paper, we study the bitruss decomposition problem which aims to find all the k-bitrusses for k≥ 0. The existing algorithms follow a bottom-up strategy which peels the edges with the lowest butterfly support iteratively. In this peeling process, these algorithms are time-consuming to enumerate all the supporting butterflies for each edge. To solve this issue, we propose a novel online index, the BE-Index which compresses butterflies into k-blooms (i.e., (2, k)-bicliques). Based on the BE-Index, the new bitruss decomposition algorithm BiT-BU is proposed, along with two batch-based optimizations, to accomplish the butterfly enumeration of the peeling process efficiently. Furthermore, the BiT-PC algorithm is designed which is more efficient against handling the edges with high butterfly supports. Besides, we explore shared-memory parallel solutions to handle large graphs in a more efficient way. In the parallel algorithms, we propose effective techniques to reduce conflicts among threads. We theoretically show that our new algorithms significantly reduce the time complexities of the existing algorithms. In addition, extensive empirical evaluations are conducted on real-world datasets. The experimental results further validate the effectiveness of the bitruss model and demonstrate that our proposed solutions significantly outperform the state-of-the-art techniques by several orders of magnitude.

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

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