Efficiently Answering Minimum Reachable Label Set Queries in Edge-Labeled Graphs

Wu, Y; Sun, R; Chen, C; Wang, X; Fu, X

Efficiently Answering Minimum Reachable Label Set Queries in Edge-Labeled Graphs

Wu, Y

Sun, R Chen, C Wang, X Fu, X

Permalink

Publisher:: ACM
Publication Type:: Conference Proceeding
Citation:: International Conference on Information and Knowledge Management, Proceedings, 2022, pp. 4585-4589
Issue Date:: 2022-10-17

Closed Access

	Filename	Description	Size
	[CIKM 2022] Efficiently Answering Minimum Reachable Label Set Queries in Edge-Labeled Graphs.pdf	Published version	1.83 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	Wu, Y https://orcid.org/0000-0001-8804-4208
dc.contributor.author	Sun, R
dc.contributor.author	Chen, C
dc.contributor.author	Wang, X
dc.contributor.author	Fu, X
dc.date.accessioned	2023-01-16T06:02:34Z
dc.date.available	2023-01-16T06:02:34Z
dc.date.issued	2022-10-17
dc.identifier.citation	International Conference on Information and Knowledge Management, Proceedings, 2022, pp. 4585-4589
dc.identifier.isbn	9781450392365
dc.identifier.uri	http://hdl.handle.net/10453/165028
dc.description.abstract	The reachability query is a fundamental problem in graph analysis. Recently, many studies focus on label-constraint reachability queries, which tries to verify whether two vertices are reachable under a given label set. However, in many real-life applications, it is more practical to find the minimum label set required to ensure the reachability of two vertices, which is neglected by previous research. To fill the gap, in this paper, we propose and investigate the minimum reachable label set (MRLS) problem in edge-labeled graphs. Specifically, given an edge-labeled graph and two vertices s, t, the MRLS problem aims to find a label set L with the minimum size such that s can reach t through L. We prove the hardness of our problem, and develop different optimization strategies to improve the scalability of the algorithms. Extensive experiments on 6 datasets demonstrate the advantages of the proposed algorithms.
dc.language	en
dc.publisher	ACM
dc.relation.ispartof	International Conference on Information and Knowledge Management, Proceedings
dc.relation.ispartof	Proceedings of the 31st ACM International Conference on Information & Knowledge Management
dc.relation.isbasedon	10.1145/3511808.3557593
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Efficiently Answering Minimum Reachable Label Set Queries in Edge-Labeled Graphs
dc.type	Conference Proceeding
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/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access	*
dc.date.updated	2023-01-16T06:02:33Z
pubs.publication-status	Published

Abstract:

The reachability query is a fundamental problem in graph analysis. Recently, many studies focus on label-constraint reachability queries, which tries to verify whether two vertices are reachable under a given label set. However, in many real-life applications, it is more practical to find the minimum label set required to ensure the reachability of two vertices, which is neglected by previous research. To fill the gap, in this paper, we propose and investigate the minimum reachable label set (MRLS) problem in edge-labeled graphs. Specifically, given an edge-labeled graph and two vertices s, t, the MRLS problem aims to find a label set L with the minimum size such that s can reach t through L. We prove the hardness of our problem, and develop different optimization strategies to improve the scalability of the algorithms. Extensive experiments on 6 datasets demonstrate the advantages of the proposed algorithms.

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

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