Efficient Top-k Graph Similarity Search With GED Constraints
It is essential to identify similarity between graphs for various tasks in data mining, machine learning and pattern recognition. Graph edit distance (GED) is the most popular graph similarity measure thanks to its flexibility and versatility. In this paper, we study the problem of top-<inline-fo...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2022-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9843962/ |
| _version_ | 1811309348119379968 |
|---|---|
| author | Jongik Kim |
| author_facet | Jongik Kim |
| author_sort | Jongik Kim |
| collection | DOAJ |
| description | It is essential to identify similarity between graphs for various tasks in data mining, machine learning and pattern recognition. Graph edit distance (GED) is the most popular graph similarity measure thanks to its flexibility and versatility. In this paper, we study the problem of top-<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> graph similarity search, which finds <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> graphs most similar to a given query graph under the GED measure. We propose incremental GED computation algorithms that compute desired GED lower and upper bounds. Based on the algorithms, we develop novel search frameworks to address the top-<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> search problem. Our frameworks are also designed to use a state-of-the art indexing technique to speed up top-<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> search. By conducting extensive experiments on real datasets, we show that the proposed frameworks significantly improve the performance of top-<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> graph similarity search. |
| first_indexed | 2024-04-13T09:40:40Z |
| format | Article |
| id | doaj.art-154444faf91e4dbab60f8f6394da82f4 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-13T09:40:40Z |
| publishDate | 2022-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-154444faf91e4dbab60f8f6394da82f42022-12-22T02:51:55ZengIEEEIEEE Access2169-35362022-01-0110791807919110.1109/ACCESS.2022.31945599843962Efficient Top-k Graph Similarity Search With GED ConstraintsJongik Kim0https://orcid.org/0000-0002-5857-6091Department of Artificial Intelligence, Chungnam National University, Daejeon, South KoreaIt is essential to identify similarity between graphs for various tasks in data mining, machine learning and pattern recognition. Graph edit distance (GED) is the most popular graph similarity measure thanks to its flexibility and versatility. In this paper, we study the problem of top-<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> graph similarity search, which finds <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> graphs most similar to a given query graph under the GED measure. We propose incremental GED computation algorithms that compute desired GED lower and upper bounds. Based on the algorithms, we develop novel search frameworks to address the top-<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> search problem. Our frameworks are also designed to use a state-of-the art indexing technique to speed up top-<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> search. By conducting extensive experiments on real datasets, we show that the proposed frameworks significantly improve the performance of top-<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> graph similarity search.https://ieeexplore.ieee.org/document/9843962/Top-<italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">k</italic> similarity searchgraph edit distanceincremental GED computation |
| spellingShingle | Jongik Kim Efficient Top-k Graph Similarity Search With GED Constraints IEEE Access Top-<italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">k</italic> similarity search graph edit distance incremental GED computation |
| title | Efficient Top-k Graph Similarity Search With GED Constraints |
| title_full | Efficient Top-k Graph Similarity Search With GED Constraints |
| title_fullStr | Efficient Top-k Graph Similarity Search With GED Constraints |
| title_full_unstemmed | Efficient Top-k Graph Similarity Search With GED Constraints |
| title_short | Efficient Top-k Graph Similarity Search With GED Constraints |
| title_sort | efficient top k graph similarity search with ged constraints |
| topic | Top-<italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">k</italic> similarity search graph edit distance incremental GED computation |
| url | https://ieeexplore.ieee.org/document/9843962/ |
| work_keys_str_mv | AT jongikkim efficienttopkgraphsimilaritysearchwithgedconstraints |