Опубликован быстрый алгоритм для задачи изоморфизма графов

[Scratch]

Мне бы такая штука пригодилась когда я писал диплом по триангуляции поверхностей. А так, написали же, что многие комбинаторные задачи сводятся к графам

[Mrrl]

Чаще нужна ещё более общая задача — найти в графе A фрагмент, изоморфный графу B. Может быть очень полезна в компьютерном зрении, в задачах совмещения изображений и сцен (особенно с нелинейными искажениями), распознавании объекта по топологической схеме… Про поиски фрагментов программ и схем для оптимизации и прочего уже писали.

[netmaxed]

а есть, кстати, что-нибудь интересное на этом поприще? какие-нибудь прорывы?

[Mrrl]

Понятия не имею. Когда мне нужно что-то подобное, я пишу очередной велосипед. Пока лучше всего работает алгоритм с использованием матриц, в которых вычисляется вероятность соответствия для каждой пары вершин — но я уже забыл, откуда он взялся и как называется.

[chernouhov]

Да вот и по этому алгоритму хорошо бы популярное изложение — я, например, не смог его понять.

А что до изобретения велосипедов — у меня получилось что-то для частного случая, не знаю, вдруг будет полезным (хотя бы в виде элементов при развитии иных алгоритмов)
habr.com/ru/post/491846

[chernouhov]

Я имел ввиду тут алгоритм Ласло Бабая — жаль, по нему нет «популярных картинок»

[mihaild]

А вот это уже NP-полная задача.
И даже проверка наличия полного подграфа из k вершин тоже np полна.

[knagaev]

Дополню, если позволите.
Алгоритмы работы с графами сейчас в большинстве популярных случаев применяются в обработке данных соцсетей.
И Вы абсолютно правы — это фактически подзадача для задачи поиска паттерна в графе.
Поиск паттерна практически можно отнести к классу «почти универсальных» методов обработки связанных данных.

А статья (точнее новость, в ней упомянутая) мне показалась интересной, хоть Ализар и считается любителем «скандалов, интриг, расследований».

[Mrrl]

Но там ориентированные графы, да ещё и ациклические. Может быть, для них эта задача проще?

[Mrrl]

Действительно. Задача о неориентируемых графах элементарно сводится к ориентируемым ациклическим, с утроенным числом вершин (на всякий случай, чтобы думать меньше).

[yorko]

Есть еще одно приложение, где часто возникает необходимость проверки изоморфизма подграфу (задача NP-полна) — машинное обучение на графах. Успешнее всего применяется в химинформатике при анализе зависимости типа «структура-свойство» (QSAR). Обучающая выборка может выглядеть так: молекулярные графы этих веществ — положительные объекты (обладают свойством, например, токсичностью, канцерогенностью, мутагенностью и т.д.), молекулярные графы других веществ — отрицательные объекты (то есть вешества соот-но не токсичны, не канцерогенны, не мутагенны). Самая простая идея — настроить подграфы всех обучающих графов и представить каждый граф бинарным вектором, где 1 стоит там, где соответствующий «маленький» граф изоморфен подграфу обучающейго графа. (Банальный пример: помеченные графы A-B-C и B-C-D представятся векторами [1,1,1,0,1,1,0] и [0,1,1,1,0,1,1], в признаковом пространстве подграфов [A, B, C, D, A-B, B-C, C-D]). Вычислительная сложность такого представления очень высокая, потому что подграфов очень много, а также много раз необходимо проверять изоморфизм подграфу. Тем не менее, GBoost работает именно так — это «обычный» бустинг вот в таком признаковом пространстве подграфов, где «деревянным» методом важности признаков определяются важные для классифкации подграфы (их потом можно принести и показать эксперту, и он скажет, что да, например, такой подграф — бензольное кольцо — действительно свидетельствует о таком-то свойстве вещества).
Но state-of-the-art в классификации графовых данных — это ядерные методы, в большинстве из которых все равно надо часто проверять изоморфизм подграфу.

[Hypuk]

Тут больше теоретическая важность — уменьшилось количество задач в NP-intermediate кандидатах.
Сложность алгоритма квази-полиномиальная и особого значения в «реальном» мире иметь не будет. Сам Бабай в одной из лекций говорил что существующие эвристические и вероятностные алгоритмы более полезны для реальных задач.

[QtRoS]

Алгоритм Ласло Бабая работает путём виртуального «окрашивания» вершин графа. Сначала случайным образом выбираются несколько вершин, они «окрашиваются» в разные цвета. Затем выбираются несколько вершин во втором графе, предположительно соответствующих вершинам из первого графа, им присваиваются те же цвета. В конце концов, перебираются все варианты. После первоначального выбора алгоритм окрашивает на обоих графах предположительно изоморфные вершины, соседствующие с первоначально выбранными, в другие цвета до тех пор, пока не остаётся связей между вершинами.

Но ведь идея крайне простая, где за этими словами кроется трюк? Или это из-за перевода?

[Mrrl]

«предположительно изоморфные вершины». Почему именно эти вершины «предположительно изоморфны», где гарантия, что мы ничего не потеряем, и при этом не уйдём в комбинаторный взрыв? И что при неудаче получим доказательство, что графы неизоморфны?

[Nashev]

Вот тоже пришёл в комменты за этим вопросом. Это ж тупой перебор в лоб, если выкинуть мистику слова «предположительно» и брать всё подряд, отказываясь от гипотезы при обломе, и начиная проверять другую. Единственно, могу предположить что новизна в том, что впервые кто-то проанализировал этот алгоритм на P/NP-полноту

[mihaild]

Что такое «P/NP полнота»? (что такое P-полнота знаю, что такое NP-полнота знаю, что такое P/NP полнота — не знаю)
И что такое анализ алгоритма на нее? (что такое анализ алгоритма на P полноту — не знаю, что такое анализ алгоритма на NP полноту — не знаю)

А новизна в том, что предложен алгоритм, работающий быстрее чем всё, что было известно раньше.

[PsyHaSTe]

Есть мнение, что большинство реально крутых алгоритмов простые. И чем проще, тем круче :) Равно как и простое объяснение как правило вернее сложного (из истории можно припомнить хотя бы те же эпициклы против объяснения Коперника)

[avsmal]

Настолько простая, что потребовалось три лекции, чтоб её объяснить =)
Только если эту идею применить в лоб, то получится экспоненциальный алгоритм.

Это ооочень поверхностное описание одной из идей, которые в этом алгоритме используются.
Почитайте, например, тут: rjlipton.wordpress.com/2015/11/21/a-little-more-on-the-graph-isomorphism-algorithm

[Nashev]

Вы разобрались, в чём фишка? Можете пересказать?

[avsmal]

Насколько я понимаю, там нет какой-то «фишки», по которой можно понять так сразу как алгоритм работает. Это сложный алгоритм с очень сложным анализом. Сейчас объяснение основных идей алгоритма и оценки его времени работы занимает три лекции для хорошо подготовленной аудитории. Для этого нужен определённый бекграунд, необходимо понимать, что это за задача, и какие есть проблемы на пути к её решению. В CS клубе был соответствующий курс: old.compsciclub.ru/courses/graphisomorphism
Но для понимания алгоритма этого недостаточно — нужно намного больше знаний и в т.ч. очень хорошее понимание алгебры.
Можете для интереса глянуть в статью: arxiv.org/pdf/1512.03547v1.pdf
Если не готовы читать оригинал, то смотрите обзорные статьи вроде этой:
jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details

[stas404]

Бабая боятся не только дети, но и изоморфные графы.