Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs

Wu, Y; Sun, R; Wang, X; Wen, D; Zhang, Y; Qin, L; Lin, X

Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs

Wu, Y Sun, R Wang, X Wen, D

Zhang, Y

Qin, L Lin, X

Permalink

Publisher:: ASSOC COMPUTING MACHINERY
Publication Type:: Journal Article
Citation:: Proceedings of the VLDB Endowment, 2024, 17, (11), pp. 3243-3255
Issue Date:: 2024-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published versionAdobe PDF (1.01 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Wu, Y
dc.contributor.author	Sun, R
dc.contributor.author	Wang, X
dc.contributor.author	Wen, D https://orcid.org/0000-0002-0903-1503
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Qin, L
dc.contributor.author	Lin, X
dc.date.accessioned	2024-11-26T13:31:50Z
dc.date.available	2024-11-26T13:31:50Z
dc.date.issued	2024-01-01
dc.identifier.citation	Proceedings of the VLDB Endowment, 2024, 17, (11), pp. 3243-3255
dc.identifier.issn	2150-8097
dc.identifier.issn	2150-8097
dc.identifier.uri	http://hdl.handle.net/10453/182112
dc.description.abstract	Cohesive subgraph mining is a fundamental problem in bipartite graph analysis. In reality, relationships between two types of entities often occur at some specific timestamps, which can be modeled as a temporal bipartite graph. However, the temporal information is widely neglected by previous studies. Moreover, directly extending the existing models may fail to find some critical groups in temporal 1 bipartite graphs, which appear in a unilateral (i.e., one-layer) form. To fill the gap, in this paper, we propose a novel model, called maximal λ-frequency group (MFG). Given a temporal bipartite graph G = (U,E,ε), a vertex set VS ⊆ V is an MFG if i) there are no less than λ timestamps, at each of which VS can form a (τU, τV)-biclique with some vertices in U at the corresponding snapshot, and ii) it is maximal. To solve the problem, a filter-and-verification (FilterV) method is proposed based on the Bron-Kerbosch framework, incorporating novel filtering techniques to reduce the search space and array-based strategy to accelerate the frequency and maximality verification. Nevertheless, the cost of frequency verification in each valid candidate set computation and maximality check could limit the scalability of FilterV to larger graphs. Therefore, we further develop a novel verification-free (VFree) approach by leveraging the advanced dynamic counting structure proposed. Theoretically, we prove that VFree can reduce the cost of each valid candidate set computation in FilterV by a factor of O(\|V\|). Furthermore, VFree can avoid the explicit maximality verification because of the developed search paradigm. Finally, comprehensive experiments on 15 real-world graphs are conducted to demonstrate the efficiency and effectiveness of the proposed techniques and model.
dc.language	English
dc.publisher	ASSOC COMPUTING MACHINERY
dc.relation	http://purl.org/au-research/grants/arc/LP210301046
dc.relation	http://purl.org/au-research/grants/arc/DP230101445
dc.relation.ispartof	Proceedings of the VLDB Endowment
dc.relation.isbasedon	10.14778/3681954.3681997
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	0802 Computation Theory and Mathematics, 0806 Information Systems, 0807 Library and Information Studies
dc.subject.classification	4605 Data management and data science
dc.title	Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs
dc.type	Journal Article
utslib.citation.volume	17
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
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/UTS Groups
pubs.organisational-group	University of Technology Sydney/UTS Groups/Australian Artificial Intelligence Institute (AAII)
utslib.copyright.status	open_access	*
dc.rights.license	This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0). To view a copy of this license, visit https://creativecommons.org/licenses/by-nc-nd/4.0/
dc.date.updated	2024-11-26T13:31:48Z
pubs.issue	11
pubs.publication-status	Published
pubs.volume	17
utslib.citation.issue	11

Abstract:

Cohesive subgraph mining is a fundamental problem in bipartite graph analysis. In reality, relationships between two types of entities often occur at some specific timestamps, which can be modeled as a temporal bipartite graph. However, the temporal information is widely neglected by previous studies. Moreover, directly extending the existing models may fail to find some critical groups in temporal 1 bipartite graphs, which appear in a unilateral (i.e., one-layer) form. To fill the gap, in this paper, we propose a novel model, called maximal λ-frequency group (MFG). Given a temporal bipartite graph G = (U,E,ε), a vertex set VS ⊆ V is an MFG if i) there are no less than λ timestamps, at each of which VS can form a (τU, τV)-biclique with some vertices in U at the corresponding snapshot, and ii) it is maximal. To solve the problem, a filter-and-verification (FilterV) method is proposed based on the Bron-Kerbosch framework, incorporating novel filtering techniques to reduce the search space and array-based strategy to accelerate the frequency and maximality verification. Nevertheless, the cost of frequency verification in each valid candidate set computation and maximality check could limit the scalability of FilterV to larger graphs. Therefore, we further develop a novel verification-free (VFree) approach by leveraging the advanced dynamic counting structure proposed. Theoretically, we prove that VFree can reduce the cost of each valid candidate set computation in FilterV by a factor of O(|V|). Furthermore, VFree can avoid the explicit maximality verification because of the developed search paradigm. Finally, comprehensive experiments on 15 real-world graphs are conducted to demonstrate the efficiency and effectiveness of the proposed techniques and model.

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

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