Расстояние редактирования графа
Расстояние редактирования графа — это коэффициент сходства (или несходства) между двумя графами. Концепцию расстояния редактирования графа впервые сформулировали математически Альберто Санфелиу и Кинг-Сан Фу в 1983[1]. Главное приложение расстояния редактирования графа — в неточном сопоставлении графов[англ.], таких как устойчивое распознавание образов в машинном обучении[2].
Расстояние редактирования графа между двумя графами связано с расстоянием редактирования[англ.] между строками. При интерпретации сток как связных направленных ациклических графов с максимальной степенью два, классические определения расстояния редактирования, такие как расстояние Левенштейна[3], расстояние Хэмминга[4] и расстояние Джаро — Винклера, могут интерпретироваться как расстояния редактирования графов между подходящими графами. Подобным образом, расстояние редактирования графа является обобщением расстояния редактирования дерева между деревьями с корнями[5][6][7][8].
Формальные определения и свойства
Математическое определение расстояния редактирования графа зависит от определения графов, для которых расстояние определяется. Например, оно зависит от того, размечены ли и как размечены вершины и рёбра графа, а также от того, является ли граф ориентированным. В общем случае, если дан набор операций редактирования графа (известных также как элементарные операции над графами), расстояние редактирования графа между двумя графами и , записываемое как , можно определить как
- ,
где означает набор путей преобразования в (изоморфный графу) , а равна стоимости каждой операции редактирования .
Набор элементарных операций над графом обычно включает:
- вставку вершины — в граф вставляется одна новая помеченная вершина.
- удаление вершины — из графа удаляется одна (зачастую не связанная с другими) вершина.
- подстановка вершины — изменение метки (или цвета) данной вершины.
- вставка ребра — в граф вставляется новое цветное ребро между парой вершин.
- удаление ребра — удаление одного ребра между парой вершин.
- подстановка ребра — изменение метки (или цвета) данного ребра.
Кроме этого, но более редко, включаются такие операции, как разбиение ребра, при котором вставляется новая вершина в ребро (что приводит к образованию двух рёбер), и стягивание ребра, которое удаляет вершину степени два между рёбрами (одного цвета) с объединением двух рёбер в одно. Хотя такие сложные операции можно определить в терминах более простых преобразований, их использование позволяет лучше параметризовать функцию цены , когда оператор дешевле, чем сумма его составляющих.
Приложения
Расстояние редактирования графа находит применение в распознавании рукописного ввода[9], распознавании отпечатков пальцев[10] и хемоинформатике[11].
Алгоритмы и сложность
Точные алгоритмы вычисления расстояния редактирования графа между парой графов обычно преобразуют проблему в задачу поиска минимального пути преобразований между двумя графами. Вычисление оптимального пути редактирования сводится к поиску пути или задаче о кратчайшем пути, часто реализуемой как алгоритм поиска A*.
Кроме точных алгоритмов, известно много эффективных аппроксимационных алгоритмов[12][13].
Несмотря на то, что вышеупомянутые алгоритмы работают на практике иногда хорошо, в общем случае задача вычисления расстояния редактирования графа является NP-полной[14] (доказательство этого доступно в разделе 2 на сайте Zeng et al.) и даже трудна для аппроксимации (формально, она APX-трудна[15]).
Примечания
- ↑ Sanfeliu, Fu, 1983, с. 353–363.
- ↑ Gao, Xiao, Tao, Li, 2010, с. 113-129.
- ↑ Левенштейн, 1965, с. 845–848.
- ↑ Hamming, 1950, с. 147–160.
- ↑ Shasha, Zhang, 1989, с. 1245–1262.
- ↑ Zhang, 1996, с. 205–222.
- ↑ Bille, 2005, с. 22–34.
- ↑ Demaine, Mozes, Rossman, Weimann, 2010, с. A2.
- ↑ Fischer, Suen, Frinken, Riesen, Bunke, 2013, с. 194–203.
- ↑ Neuhaus, Bunke, 2005, с. 191–200.
- ↑ Birchall, Gillet, Harper, Pickett, 2006, с. 557–586.
- ↑ Neuhaus, Bunke, 2007.
- ↑ Riesen, 2016.
- ↑ Garey, Johnson, 1979.
- ↑ Lin, 1994, с. 74–82.
Литература
- Alberto Sanfeliu, King-Sun Fu. A distance measure between attributed relational graphs for pattern recognition // IEEE Transactions on Systems, Man and Cybernetics. — 1983. — Т. 13, вып. 3. — С. 353–363. — doi:10.1109/TSMC.1983.6313167.
- Xinbo Gao, Bing Xiao, Dacheng Tao, Xuelong Li. A survey of graph edit distance // Pattern Analysis and Applications. — 2010. — Т. 13. — С. 113–129. — doi:10.1007/s10044-008-0141-y.
- Влади́мир И. Левенштейн. Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады Академий Наук СCCP. — 1965. — Т. 163, вып. 4. — С. 845–848.
- Richard W. Hamming. Error detecting and error correcting codes // Bell System Technical Journal. — 1950. — Т. 29, вып. 2. — С. 147–160. — doi:10.1002/j.1538-7305.1950.tb00463.x. Архивировано 25 мая 2006 года.
- Shasha D., Zhang K. Simple fast algorithms for the editing distance between trees and related problems // SIAM J. Comput.. — 1989. — Т. 18, № 6. — С. 1245–1262. — doi:10.1137/0218082.
- Zhang K. A constrained edit distance between unordered labeled trees // Algorithmica. — 1996. — Т. 15, № 3. — С. 205–222. — doi:10.1007/BF01975866.
- Bille P. A survey on tree edit distance and related problems // Theor. Comput. Sci.. — 2005. — Т. 337, вып. 1–3. — С. 22–34. — doi:10.1016/j.tcs.2004.12.030.
- Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann. An optimal decomposition algorithm for tree edit distance // ACM Transactions on Algorithms. — 2010. — Т. 6, вып. 1. — С. A2. — doi:10.1145/1644015.1644017.
- Andreas Fischer, Ching Y. Suen, Volkmar Frinken, Kaspar Riesen, Horst Bunke. A Fast Matching Algorithm for Graph-Based Handwriting Recognition // Graph-Based Representations in Pattern Recognition. — 2013. — Т. 7877. — С. 194–203. — (Lecture Notes in Computer Science). — ISBN 978-3-642-38220-8. — doi:10.1007/978-3-642-38221-5_21.
- Michel Neuhaus, Horst Bunke. A Graph Matching Based Approach to Fingerprint Classification using Directional Variance // Audio- and Video-Based Biometric Person Authentication. — 2005. — Т. 3546. — С. 191–200. — (Lecture Notes in Computer Science). — ISBN 978-3-540-27887-0. — doi:10.1007/11527923_20.
- Kristian Birchall, Valerie J. Gillet, Gavin Harper, Stephen D. Pickett. Training Similarity Measures for Specific Activities: Application to Reduced Graphs // Journal of Chemical Information and Modeling. — 2006. — Январь (т. 46, № 2). — С. 557–586. — doi:10.1021/ci050465e. — PMID 16562986.
- Michel Neuhaus, Horst Bunke. Bridging the Gap between Graph Edit Distance and Kernel Machines. — World Scientific, 2007. — Т. 68. — (Machine Perception and Artificial Intelligence). — ISBN 978-9812708175.
- Kaspar Riesen. Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications. — Springer, 2016. — (Advances in Computer Vision and Pattern Recognition). — ISBN 978-3319272511.
- Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W. H. Freeman and Company, 1979. — ISBN 978-0-7167-1045-5.
- Chih-Long Lin. Hardness of approximating graph transformation problem // Algorithms and Computation / Ding-Zhu Du, Xiang-Sun Zhang. — Springer Berlin Heidelberg, 1994. — Т. 834. — (Lecture Notes in Computer Science). — ISBN 9783540583257. — doi:10.1007/3-540-58325-4_168.