Расстояние редактирования графика - Graph edit distance

В математика и Информатика, расстояние редактирования графика (GED) это мера сходства (или несходство) между двумя графики Впервые концепция расстояния редактирования графа была математически формализована Альберто Санфелиу и Кинг-Сун Фу в 1983 году.^[1]Основное применение расстояния редактирования графиков находится в неточное сопоставление графов, например, устойчивый к ошибкам распознавание образов в машинное обучение.^[2]

Расстояние редактирования графика между двумя графиками связано срасстояние редактирования строки между струны.С интерпретацией строк как связаны, ориентированные ациклические графы из максимальная степень одно, классические определения расстояния редактирования, такие как Расстояние Левенштейна,^[3][4]Расстояние Хэмминга^[5]и Расстояние Яро – Винклера может быть интерпретировано как расстояние редактирования графа между графами с соответствующими ограничениями. Аналогичным образом, расстояние редактирования графика также является обобщением дерево редактировать расстояние междуукоренившиеся деревья.^[6][7][8][9]

Формальные определения и свойства

Математическое определение расстояния редактирования графа зависит от определений графов, на которых оно определяется, т.е. от того, являются ли вершины и ребра графа маркированный и являются ли края направленный Как правило, учитывая набор операции редактирования графика (также известный как элементарный графические операции ), расстояние редактирования графика между двумя графиками ${\displaystyle g_{1}}$ и ${\displaystyle g_{2}}$, записанный как ${\displaystyle GED(g_{1},g_{2})}$ можно определить как

${\displaystyle GED(g_{1},g_{2})=\min _{(e_{1},...,e_{k})\in {\mathcal {P}}(g_{1},g_{2})}\sum _{i=1}^{k}c(e_{i})}$

куда ${\displaystyle {\mathcal {P}}(g_{1},g_{2})}$ обозначает набор путей редактирования, преобразующих ${\displaystyle g_{1}}$ в (график изоморфный к) ${\displaystyle g_{2}}$ и ${\displaystyle c(e)\geq 0}$ стоимость каждой операции редактирования графика ${\displaystyle e}$.

Набор операторов редактирования элементарного графа обычно включает:

вставка вершины чтобы ввести в граф одну новую помеченную вершину.

удаление вершины для удаления единственной (часто несвязанной) вершины из графа.

подстановка вершин для изменения метки (или цвета) данной вершины.

вставка края чтобы ввести новое цветное ребро между парой вершин.

удаление края чтобы удалить единственное ребро между парой вершин.

замена края для изменения метки (или цвета) данного края.

Дополнительные, но менее распространенные операторы включают такие операции, как расщепление краев который вводит новую вершину в ребро (также создает новое ребро), и сжатие края который удаляет вершины степени два между ребрами (одного цвета). Хотя такие сложные операторы редактирования могут быть определены в терминах более элементарных преобразований, их использование позволяет более точно параметризовать функцию стоимости. ${\displaystyle c}$ когда оператор дешевле суммы его составляющих.

Подробный анализ простейших операторов редактирования графов представлен в ^[10][11]

И некоторые методы были представлены для автоматического вывода этих элементарных операторов редактирования графа.^{[12][13][14][15]}

Приложения

Расстояние редактирования графика находит применение в распознавание почерка,^[16] распознавание отпечатков пальцев^[17] и хеминформатика.^[18]

Алгоритмы и сложность

Точные алгоритмы для вычисления расстояния редактирования графа между парой графов обычно преобразуют проблему в задачу поиска пути редактирования с минимальной стоимостью между двумя графами. Расчет оптимального пути редактирования приводится как Найти путь поиск или проблема кратчайшего пути, часто реализуется как Алгоритм поиска A *.

Помимо точных алгоритмов известен также ряд эффективных алгоритмов аппроксимации. Большинство из них имеют кубическое вычислительное время. ^{[19][20][21][22][23]}

Более того, существует алгоритм, который выводит приближение GED за линейное время. ^[24]

Несмотря на то, что приведенные выше алгоритмы иногда хорошо работают на практике, в целом проблема вычисления расстояния редактирования графа является NP-полной.^[25] (доказательство, доступное в Интернете, см. в разделе 2 Zeng et al. ) и даже трудно аппроксимировать (формально APX -жесткий^[26]).

Рекомендации

1. Санфелиу, Альберто; Фу, Король-Солнце (1983). «Мера расстояния между атрибутированными реляционными графами для распознавания образов». IEEE Transactions по системам, человеку и кибернетике. 13 (3): 353–363. Дои:10.1109 / TSMC.1983.6313167.
2. Гао, Синьбо; Сяо, Бин; Тао, Дачэн; Ли, Сюэлун (2010). "Обзор дистанции редактирования графика". Анализ шаблонов и приложения. 13: 113–129. Дои:10.1007 / s10044-008-0141-y.
3. Влади́мир И. Левенштейн (1965). Двоичные коды с исправлением выпадений, вставок и замен символов [Двоичные коды, способные исправлять удаления, вставки и обращения]. Доклады Академий Наук СССР (на русском). 163 (4): 845–848.
4. Левенштейн, Владимир Иванович (февраль 1966 г.). «Двоичные коды, способные исправлять удаления, вставки и обращения». Советская физика.. 10 (8): 707–710.
5. Хэмминг, Ричард В. (1950). «Коды обнаружения и исправления ошибок» (PDF). Технический журнал Bell System. 29 (2): 147–160. Дои:10.1002 / j.1538-7305.1950.tb00463.x. HDL:10945/46756. МИСТЕР  0035935. Архивировано 25 мая 2006 года.
6. Шаша, Д; Чжан, К. (1989). «Простые быстрые алгоритмы редактирования расстояния между деревьями и смежными задачами». SIAM J. Comput. 18 (6): 1245–1262. CiteSeerX  10.1.1.460.5601. Дои:10.1137/0218082.
7. Чжан, К. (1996). «Ограниченное расстояние редактирования между неупорядоченными помеченными деревьями». Алгоритмика. 15 (3): 205–222. Дои:10.1007 / BF01975866.
8. Билле, П. (2005). «Обзор расстояния редактирования дерева и связанные с этим проблемы». Теор. Comput. Sci. 337 (1–3): 22–34. Дои:10.1016 / j.tcs.2004.12.030.
9. Демейн, Эрик Д.; Мозес, Шей; Россман, Бенджамин; Вейманн, Орен (2010). «Оптимальный алгоритм декомпозиции для расстояния редактирования дерева». ACM-транзакции на алгоритмах. 6 (1): A2. CiteSeerX  10.1.1.163.6937. Дои:10.1145/1644015.1644017. МИСТЕР  2654906.
10. Серратоса, Франсеск (2019). Расстояние редактирования графика: ограничения для метрики. Распознавание образов, 90, стр: 250-256.
11. Серратоса, Франсеск; Кортес, Ксавье (2015). Расстояние редактирования графа: переход от глобальной к локальной структуре для решения проблемы сопоставления графов. Письма о распознавании образов, 65, стр: 204-210.
12. Сантакрус, Пеп; Серратоса, Франсеск (2020). Изучение затрат на редактирование графика на основе модели обучения, применяемой для неоптимального сопоставления графиков. Письма о нейронной обработке, 51, стр: 881–904.
13. Алгабли, Шайма; Серратоса, Франсеск (2018). Встраивание сопоставлений узлов с узлами для изучения параметров расстояния редактирования графика. Письма о распознавании образов, 112, стр: 353-360.
14. Ксавье, Кортес; Серратоса, Франсеск (2016). График обучения, соответствующий весам подстановки на основе соответствия узлов основной истины. Международный журнал распознавания образов и искусственного интеллекта, 30 (2), стр: 1650005 [22 страницы].
15. Ксавье, Кортес; Серратоса, Франсеск (2015). Изучение затрат на редактирование сопоставления графов на основе оптимальности соответствий узлов Oracle. Письма о распознавании образов, 56, стр: 22 - 29.
16. Фишер, Андреас; Suen, Ching Y .; Фринкен, Фолькмар; Ризен, Каспар; Бунке, Хорст (2013), «Алгоритм быстрого сопоставления для распознавания рукописного ввода на основе графиков», Графические представления в распознавании образов, Конспект лекций по информатике, 7877, стр. 194–203, Дои:10.1007/978-3-642-38221-5_21, ISBN  978-3-642-38220-8
17. Нейгауз, Мишель; Бунке, Хорст (2005), "Подход на основе сопоставления графиков к классификации отпечатков пальцев с использованием отклонения по направлению", Биометрическая аутентификация человека на основе аудио и видео, Конспект лекций по информатике, 3546, стр. 191–200, Дои:10.1007/11527923_20, ISBN  978-3-540-27887-0
18. Бирчалл, Кристиан; Жилле, Валери Дж .; Харпер, Гэвин; Пикетт, Стивен Д. (январь 2006 г.). «Меры подобия обучения для конкретных видов деятельности: приложение к сокращенным графам». Журнал химической информации и моделирования. 46 (2): 557–586. Дои:10.1021 / ci050465e. PMID  16562986.
19. Нейгауз, Мишель; Бунке, Хорст (ноябрь 2007 г.). Устранение разрыва между Graph Edit Distance и ядром. Машинное восприятие и искусственный интеллект. 68. World Scientific. ISBN  978-9812708175.
20. Ризен, Каспар (февраль 2016 г.). Распознавание структурных образов с помощью расстояния редактирования графика: алгоритмы аппроксимации и приложения. Достижения в области компьютерного зрения и распознавания образов. Springer. ISBN  978-3319272511.
21. Серратоса, Франсеск (2014). Быстрое вычисление соответствия двудольного графа. Письма о распознавании образов, 45, стр: 244 - 250.
22. Серратоса, Франсеск (2015). Ускорение быстрого сопоставления двудольных графов с помощью новой матрицы затрат. Международный журнал распознавания образов и искусственного интеллекта, 29 (2), 1550010, [17 страниц].
23. Серратоса, Франсеск (2015). Вычисление расстояния редактирования графика: рассуждения об оптимальности и ускорении. Image and Vision Computing, 40, стр: 38-48.
24. Сантакрус, Пеп; Серратоса, Франсеск (2018). Устойчивое к ошибкам сопоставление графов в линейных вычислительных затратах с использованием начального малого частичного сопоставления. Письма с распознаванием образов.
25. Гэри и Джонсон (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. В. Х. Фриман и компания. ISBN  978-0-7167-1045-5.
26. Линь, Чи-Лонг (1994-08-25). «Трудность аппроксимирующей задачи преобразования графов». Ин Ду, Дин-Чжу; Чжан, Сян-Сунь (ред.). Алгоритмы и вычисления. Конспект лекций по информатике. 834. Springer Berlin Heidelberg. С. 74–82. Дои:10.1007/3-540-58325-4_168. ISBN  9783540583257.