Алгоритм уточнения цвета

В теории графов и теоретической информатике алгоритм уточнения цвета , также известный как наивная классификация вершин или одномерная версия алгоритма Вейсфейлера-Лемана , представляет собой процедуру, используемую для проверки изоморфности двух графов . ^{[ 1 ]} Хотя он решает изоморфизм графов почти на всех графах, существуют графы, такие как все обычные графы, которые невозможно различить с помощью уточнения цвета.

Описание

Алгоритм принимает на вход график $G$ с $n$ вершины. Он выполняется итерациями, и на каждой итерации создается новая раскраска вершин. Формально « раскраска » — это функция преобразования вершин этого графа в некоторое множество («цветов»). На каждой итерации мы определяем последовательность раскрасок вершин $\lambda _{i}$ следующее:

$\lambda _{0}$ это первоначальная окраска. Если граф не помечен, первоначальная раскраска присваивает тривиальный цвет. $\lambda _{0}(v)$ к каждой вершине $v$ . Если график помечен, $\lambda _{0}$ это метка вершины $v$ .
Для всех вершин $v$ , мы установили $\lambda _{i+1}=\left(\lambda _{i}(v),\{\{\lambda _{i}(w)\mid w{\text{ is a neighbor of }}v\}\}\right)$ .

Другими словами, новый цвет вершины $v$ — это пара, образованная из предыдущего цвета и мультимножества цветов его соседей. Этот алгоритм продолжает уточнять текущую окраску. В какой-то момент оно стабилизируется, т.е. $\lambda _{i+1}\equiv \lambda _{i}$ . Эта окончательная раскраска называется устойчивой раскраской .

Изоморфизм графа

Уточнение цвета можно использовать как подпрограмму для решения важной вычислительной задачи: изоморфизма графов . В этой задаче мы имеем на входе два графика $G,H$ и наша задача — определить, изоморфны ли они . Неформально это означает, что два графа одинаковы с точностью до перемаркировки вершин.

Чтобы проверить, если $G$ и $H$ изоморфны, мы могли бы попробовать следующее. Запустите уточнение цвета на обоих графиках. Если полученные устойчивые раскраски различны, мы знаем, что два графа не изоморфны. Однако может случиться так, что одна и та же устойчивая раскраска будет получена, несмотря на то, что два графа не изоморфны; см. ниже.

Сложность

Легко видеть, что если задать уточнение цвета $n$ граф вершин в качестве входных данных, устойчивая раскраска получается не более чем через $n-1$ итерации. И наоборот, существуют графы, в которых эта граница реализуется. ^{[ 2 ]} Это приводит к $O((n+m)\log n)$ реализация, где $n$ количество вершин и $m$ количество ребер. ^{[ 3 ]} Доказано, что эта сложность оптимальна при разумных предположениях. ^{[ 4 ]}

Выразительность

Мы говорим, что два графа $G$ и $H$ отличаются уточнением цвета , если алгоритм дает другой результат на $G$ как на $H$ . Есть простые примеры графиков, не отличающихся детализацией цвета. Например, он не отличает цикл длины 6 от пары треугольников (пример V.1 в ^{[ 5 ]}). Несмотря на это, алгоритм очень мощный, поскольку случайный граф будет идентифицирован алгоритмом асимптотически почти наверняка. ^{[ 6 ]} Еще сильнее было показано, что, как $n$ увеличивается, доля графиков, которые не идентифицируются уточнением цвета, уменьшается экспоненциально по порядку $n$ . ^{[ 7 ]}

Выразительность уточнения цвета также имеет логическую характеристику: два графа можно различить уточнением цвета тогда и только тогда, когда их можно различить двухпеременным фрагментом логики первого порядка со счетом . ^{[ 8 ]}

История

Ссылки

^ Гроэ, Мартин; Керстинг, Кристиан; Младенов, Мартин; Швейцер, Паскаль (2021). «Уточнение цвета и его применение» . Введение в расширенный вероятностный вывод . дои : 10.7551/mitpress/10548.003.0023 . ISBN 9780262365598 . S2CID 59069015 .
^ Кифер, Сандра; Маккей, Брендан Д. (20 мая 2020 г.), Число итераций улучшения цвета , arXiv : 2005.10182
^ Кардон, А.; Крочемор, М. (1 июля 1982 г.). «Разбиение графа за O(¦A¦log2¦V¦)» . Теоретическая информатика . 19 (1): 85–98. дои : 10.1016/0304-3975(82)90016-0 . ISSN 0304-3975 .
^ Беркхольц, Кристоф; Бонсма, Пол; Гроэ, Мартин (01 мая 2017 г.). «Жесткие нижняя и верхняя границы сложности канонического уточнения цвета» . Теория вычислительных систем . 60 (4): 581–614. arXiv : 1509.08251 . дои : 10.1007/s00224-016-9686-0 . ISSN 1433-0490 . S2CID 12616856 .
^ Гроэ, Мартин (29 июня 2021 г.). «Логика графовых нейронных сетей» . 2021 36-й ежегодный симпозиум ACM/IEEE по логике в информатике (LICS) . ЛИКС '21. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 1–17. arXiv : 2104.14624 . дои : 10.1109/LICS52264.2021.9470677 . ISBN 978-1-6654-4895-6 . S2CID 233476550 .
^ Бабай, Ласло; Эрдош, Пол; Селков, Стэнли М. (август 1980 г.). «Случайный изоморфизм графов» . SIAM Journal по вычислительной технике . 9 (3): 628–635. дои : 10.1137/0209047 . ISSN 0097-5397 .
^ Бабай, Л.; Кучера, К. (1979). «Каноническая разметка графов в линейном среднем времени» . 20-й ежегодный симпозиум по основам информатики (SFCS, 1979) . стр. 39–46. дои : 10.1109/SFCS.1979.8 . Проверено 18 января 2024 г.
^ Гроэ, Мартин. «Логика конечных переменных в описательной теории сложности». Бюллетень символической логики 4.4 (1998): 345-398.

[1] Гроэ, Мартин; Керстинг, Кристиан; Младенов, Мартин; Швейцер, Паскаль (2021). «Уточнение цвета и его применение» . Введение в расширенный вероятностный вывод . дои : 10.7551/mitpress/10548.003.0023 . ISBN 9780262365598 . S2CID 59069015 .

[2] Кифер, Сандра; Маккей, Брендан Д. (20 мая 2020 г.), Число итераций улучшения цвета , arXiv : 2005.10182

[3] Кардон, А.; Крочемор, М. (1 июля 1982 г.). «Разбиение графа за O(¦A¦log2¦V¦)» . Теоретическая информатика . 19 (1): 85–98. дои : 10.1016/0304-3975(82)90016-0 . ISSN 0304-3975 .

[4] Беркхольц, Кристоф; Бонсма, Пол; Гроэ, Мартин (01 мая 2017 г.). «Жесткие нижняя и верхняя границы сложности канонического уточнения цвета» . Теория вычислительных систем . 60 (4): 581–614. arXiv : 1509.08251 . дои : 10.1007/s00224-016-9686-0 . ISSN 1433-0490 . S2CID 12616856 .

[5] Гроэ, Мартин (29 июня 2021 г.). «Логика графовых нейронных сетей» . 2021 36-й ежегодный симпозиум ACM/IEEE по логике в информатике (LICS) . ЛИКС '21. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 1–17. arXiv : 2104.14624 . дои : 10.1109/LICS52264.2021.9470677 . ISBN 978-1-6654-4895-6 . S2CID 233476550 .

[6] Бабай, Ласло; Эрдош, Пол; Селков, Стэнли М. (август 1980 г.). «Случайный изоморфизм графов» . SIAM Journal по вычислительной технике . 9 (3): 628–635. дои : 10.1137/0209047 . ISSN 0097-5397 .

[7] Бабай, Л.; Кучера, К. (1979). «Каноническая разметка графов в линейном среднем времени» . 20-й ежегодный симпозиум по основам информатики (SFCS, 1979) . стр. 39–46. дои : 10.1109/SFCS.1979.8 . Проверено 18 января 2024 г.

[8] Гроэ, Мартин. «Логика конечных переменных в описательной теории сложности». Бюллетень символической логики 4.4 (1998): 345-398.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]