TY - GEN
T1 - Consistent Subgraph Matching over Large Graphs
AU - Yuan, Ye
AU - Ma, Delong
AU - Zhang, Aoqian
AU - Wang, Guoren
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - Subgraph matching over graphs has been extensive-ly studied, due to its wide applications in knowledge bases, social networks, and among others. To catch the inconsistency and errors that commonly exist in these graphs, this paper studies consistent subgraph matching (CSM), i.e., finding the common matches in every consistent graph repair w.r.t a set of conditional graph dependencies (CGDs). We concentrate on subset, superset and symmetric difference graph repairs. We study fundamental problems for CGDs and CSM. We show that the satisfiability, im-plication, and validation problems of CGDs are coNP-complete, coNP-complete and NP-complete, respectively. We also show that the CSM problem (under any kind of repair) is NP-complete. We provide (parallel) algorithms to solve CSM, and guarantee to reduce running time when given more processors. Using real-life and synthetic graphs, we empirically verify the efficiency and effectiveness of our algorithms.
AB - Subgraph matching over graphs has been extensive-ly studied, due to its wide applications in knowledge bases, social networks, and among others. To catch the inconsistency and errors that commonly exist in these graphs, this paper studies consistent subgraph matching (CSM), i.e., finding the common matches in every consistent graph repair w.r.t a set of conditional graph dependencies (CGDs). We concentrate on subset, superset and symmetric difference graph repairs. We study fundamental problems for CGDs and CSM. We show that the satisfiability, im-plication, and validation problems of CGDs are coNP-complete, coNP-complete and NP-complete, respectively. We also show that the CSM problem (under any kind of repair) is NP-complete. We provide (parallel) algorithms to solve CSM, and guarantee to reduce running time when given more processors. Using real-life and synthetic graphs, we empirically verify the efficiency and effectiveness of our algorithms.
UR - http://www.scopus.com/inward/record.url?scp=85136416561&partnerID=8YFLogxK
U2 - 10.1109/ICDE53745.2022.00235
DO - 10.1109/ICDE53745.2022.00235
M3 - Conference contribution
AN - SCOPUS:85136416561
T3 - Proceedings - International Conference on Data Engineering
SP - 2536
EP - 2548
BT - Proceedings - 2022 IEEE 38th International Conference on Data Engineering, ICDE 2022
PB - IEEE Computer Society
T2 - 38th IEEE International Conference on Data Engineering, ICDE 2022
Y2 - 9 May 2022 through 12 May 2022
ER -