.png){kind=icon}
返回
Improved Lower Bounds for Graph Edit Distance
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2017.2772243.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The problem of deriving lower and upper bounds for the edit distance between undirected, labeled graphs has recently received increasing attention. However, only one algorithm has been proposed that allegedly computes not only an upper but also a lower bound for non-uniform edit costs and incorporates information about both node and edge labels. In this paper, we demonstrate that this algorithm is incorrect. We present a corrected version BRANCH that runs in O(n(2)Delta(3) + n(3)) time, where Delta is the maximum of the maximum degrees of input graphs G and H. We also develop a speed-up BRANCHFAST that runs in O(n(2)Delta(3) + n(3)) time and computes an only slightly less accurate lower bound. The lower bounds produced by BRANCH and BRANCHFAST are shown to be pseudo-metrics on a collection of graphs. Finally, we suggest an anytime algorithm BRANCHTIGHT that iteratively improves BRANCH's lower bound. BRANCHTIGHT runs in O(n(3)Delta(2) + I (n(2)Delta(3) + n(3)) time, where the number of iterations I is controlled by the user. A detailed experimental evaluation shows that all suggested algorithms are Pareto optimal, that they are very effective when used as filters for edit distance range queries, and that they perform excellently when used within classification frameworks.
Keyword:
Graph edit distance
lower bounds
anytime algorithm
graph databases
graph matching
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
10.4
论文数:
6.9K
被引数:
3.2W
机构
引用论文
.png){kind=icon}
分享收藏A Hybrid Classification Model for Digital Pathology Using Structural and Statistical Pattern Recognition使用结构和统计模式识别的数字病理学混合分类模型
PREAI
分享收藏
查看更多内容