Efficiently Answering Minimum Reachable Label Set Queries in Edge-Labeled Graphs
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.
Supplementary Material
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 ?, ?, the MRLS problem aims to find a label set L with the minimum size such that ? can reach ? 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.
- Download
- 30.86 MB
References
[1]
Xiaoshuang Chen, Kai Wang, Xuemin Lin, Wenjie Zhang, Lu Qin, and Ying Zhang. 2021. Efficiently answering reachability and path queries on temporal bipartite graphs. Proceedings of the VLDB Endowment (2021).
[2]
Ruoming Jin, Hui Hong, Haixun Wang, Ning Ruan, and Yang Xiang. 2010. Computing label-constraint reachability in graph databases. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. 123--134.
[3]
Richard M Karp. 1972. Reducibility among combinatorial problems. In Complexity of computer computations. Springer, 85--103.
[4]
Xijuan Liu, Mengqi Zhang, Xianming Fu, Chen Chen, Xiaoyang Wang, and Yanping Wu. 2021. Efficient reachability queries in multi-relation graph: an index-based approach. Computers & Electrical Engineering, Vol. 96 (2021), 107469.
[5]
You Peng, Ying Zhang, Xuemin Lin, Lu Qin, and Wenjie Zhang. 2020. Answering billion-scale label-constrained reachability queries within microsecond. Proceedings of the VLDB Endowment, Vol. 13, 6 (2020), 812--825.
[6]
Renjie Sun, Chen Chen, Xiaoyang Wang, Yanping Wu, Mengqi Zhang, and Xijuan Liu. 2022. The art of characterization in large networks: Finding the critical attributes. World Wide Web (2022).
[7]
Renjie Sun, Chen Chen, Xiaoyang Wang, Ying Zhang, and Xun Wang. 2020. Stable community detection in signed social networks. IEEE Transactions on Knowledge and Data Engineering (2020).
[8]
Silke Trißl and Ulf Leser. 2007. Fast and practical indexing and querying of very large graphs. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Beijing, China, June 12--14, 2007.
[9]
Lucien DJ Valstar, George HL Fletcher, and Yuichi Yoshida. 2017. Landmark indexing for evaluation of label-constrained reachability queries. In Proceedings of the 2017 ACM International Conference on Management of Data.
[10]
Xiaoyang Wang, Ying Zhang, Wenjie Zhang, and Xuemin Lin. 2016. Distance-aware influence maximization in geo-social network. In ICDE. 1--12.
[11]
Dong Wen, Yilun Huang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2020. Efficiently Answering Span-Reachability Queries in Large Temporal Graphs. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 1153--1164.
[12]
Jeffrey Xu Yu and Jiefeng Cheng. 2010. Graph Reachability Queries: A Survey. In Managing and Mining Graph Data.
[13]
Chengyuan Zhang, Ying Zhang, Wenjie Zhang, Xuemin Lin, Muhammad Aamir Cheema, and Xiaoyang Wang. 2014. Diversified spatial keyword search on road networks. In EDBT.
[14]
Xiaofei Zhang and M. Tamer Ö zsu. 2019. Correlation Constraint Shortest Path over Large Multi-Relation Graphs. Proc. VLDB Endow. (2019).
[15]
Lei Zou, Kun Xu, Jeffrey Xu Yu, Lei Chen, Yanghua Xiao, and Dongyan Zhao. 2014. Efficient processing of label-constraint reachability queries in large graphs. Information Systems (2014).
Index Terms
- Efficiently Answering Minimum Reachable Label Set Queries in Edge-Labeled Graphs
Recommendations
Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
A set D ⊆ V of a graph G =( V , E ) is a dominating set of G if every vertex in V D has at least one neighbor in D . A dominating set D of G is a paired-dominating set of G if the induced subgraph, G [ D ], has a perfect ...
Edge-deletable IM-extendable graphs with minimum number of edges
A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every F@?E(G) with |...
Hamiltonian claw-free graphs involving minimum degrees
Favaron and Fraisse proved that any 3-connected claw-free graph H with order n and minimum degree @d(H)>=n+3810 is hamiltonian [O. Favaron and P. Fraisse, Hamiltonicity and minimum degree in 3-connected claw-free graphs, J. Combin. Theory B 82 (2001) ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2022
5274 pages
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 17 October 2022
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
CIKM '22: The 31st ACM International Conference on Information and Knowledge Management
October 17 - 21, 2022
GA, Atlanta, USA
Acceptance Rates
CIKM '22 Paper Acceptance Rate 621 of 2,257 submissions, 28%;
Overall Acceptance Rate 1,861 of 8,427 submissions, 22%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 135Total Downloads
- Downloads (Last 12 months)41
- Downloads (Last 6 weeks)7
Reflects downloads up to 23 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in