Отклонение изоморфизмов из набора графов

У меня есть коллекция из 15M (Million) DAG (собственно направленных ациклических графов - направленных гиперкубов), которые я хотел бы удалить изоморфизмы из. Каков общий алгоритм для этого? Каждый график довольно мал: гиберкуб размерности N, где N от 3 до 6 (на данный момент), в результате чего для случая N = 6 вычисляются графики по 64 узла.

Используя networkx и python, я реализовал его так, как это работает для небольших наборов, таких как 300 000 (Thousand), просто отлично (работает через несколько дней).

def isIsomorphicDuplicate(hcL, hc):
    """checks if hc is an isomorphism of any of the hc in hcL
    Returns True if hcL contains an isomorphism of hc
    Returns False if it is not found"""
    #for each cube in hcL, check if hc could be isomorphic
    #if it could be isomorphic, then check if it is
    #if it is isomorphic, then return True
    #if all comparisons have been made already, then it is not an isomorphism and return False

    for saved_hc in hcL:
        if nx.faster_could_be_isomorphic(saved_hc, hc):
            if nx.fast_could_be_isomorphic(saved_hc, hc):
                if nx.is_isomorphic(saved_hc, hc):
                    return True
    return False

Одним из лучших способов сделать это было бы преобразование каждого графика в его каноническое упорядочение, сортировку коллекции, а затем удаление дубликатов. Это исключает проверку каждого из 15M-графиков в бинарном is_isomophic() тесте, я считаю, что приведенная выше реализация - это что-то вроде O (N! N) (не учитывая изоморфное время), тогда как чистое преобразование всех в каноническое упорядочение и сортировку должно выполняться O (N) для преобразования + O (log (N) N) для поиска + O (N) для удаления дубликатов. O (N! N) → O (log (N) N)

Я нашел эту статью о канонической маркировке графа, но ее очень сложно описать математическими уравнениями, а не псевдокодом: "Алгоритм Labical Graph Labeling McKay" - http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf

TL;DR: У меня есть невероятно большое количество графиков для проверки посредством проверки бинарного изоморфизма. Я считаю, что общий путь это делается через каноническое упорядочение. Существуют ли какие-либо упакованные алгоритмы или опубликованные простые для реализации алгоритмов (т.е. Имеют псевдокод)?

Ответы

Ответ 1

Вот разбивка алгоритма маркировки канонического графа Маккей, представленная в статье Хартке и Рэдклиффом [ссылка на бумагу ].

Я должен начать с указания, что реализация с открытым исходным кодом доступна здесь: nauty и исходный код Traces.

Хорошо, сделай это! К сожалению, этот алгоритм тяжел в теории графов, поэтому нам нужны некоторые термины. Сначала я начну с определения изоморфного и автоморфного.

Изоморфизм:

Два графика изоморфны, если они одинаковы, за исключением того, что вершины обозначены по-разному. Следующие два графика изоморфны.

Isomorphic graphs

Автоморфизм:

Два графика являются автоморфными, если они полностью совпадают, включая метку вершин. Следующие два графика являются автоморфными. Это кажется тривиальным, но оказывается важным по техническим причинам.

Automorphic graphs

Хеширование графика:

Основная идея всего этого заключается в том, чтобы иметь способ хеширования графика в строку, а затем для данного графика вы вычисляете хэш-строки для всех изоморфных ему графиков. Изоморфная хэш-строка, которая по алфавиту (технически лексикографически) наибольшая, называется "Канонический хэш", а созданный ею график называется "Канонический изоморф" или "Каноническая маркировка".

С этим, чтобы проверить, являются ли какие-либо два графика изоморфными, вам просто нужно проверить, равны ли их канонические изоморфные (или канонические эталонные) (т.е. являются автоморфами друг друга). Ничего себе жаргон! Несомненно, это еще более запутанно без жаргона: - (

Хеш-функция, которую мы собираемся использовать, называется я (G) для графа G: постройте двоичную строку, посмотрев на каждую пару вершин из G (в порядке вершины метки) и положим "1", если там - это ребро между этими двумя вершинами, а "0" - нет. Таким образом, j-й бит в я (G) представляет присутствие отсутствия этого ребра в графике.

Алгоритм маркировки канонических графиков Маккей

Проблема заключается в том, что для графа на n вершин существуют O (n!) возможные изоморфные хэш-строки, основанные на том, как вы наклеиваете вершины, и многое другое, если нам приходится вычислять одну и ту же строку несколько раз (т.е. автоморфы). В общем, мы должны вычислить каждую изоморфную хэш-строку, чтобы найти самую большую, нет волшебной сортировки. Алгоритм Маккея - это алгоритм поиска, который быстрее находит эту каноническую изомоприю, отсекая все автоморфы из дерева поиска, заставляя вершины в канонической изоморфе отмечать в порядке возрастания степени и несколько других трюков, которые уменьшают число изоморфов. должны иметь хэш.

(1) Раздел 4: первый шаг Маккей состоит в сортировке вершин в соответствии со степенью, которая вырезает большинство изомоприймов для поиска, но не гарантируется, что это уникальный порядок, поскольку может быть более одной вершины данной степени. Например, следующий график имеет 6 вершин; verts {1,2,3} имеют степень 1, verts {4,5} имеют степень 2, а vert {6} имеет степень 3. Частичное упорядочение по степени вершины равно {1,2,3 | 4,5 | 6 }.

vertex degree example

(2) Sect 5: Наложить искусственную симметрию на вершины, которые не отличались степенью вершин; в основном мы берем одну из групп вершин с одинаковой степенью и, в свою очередь, выбираем один за другим в общем порядке (рис .2 в статье), поэтому в нашем примере выше node {1, 2,3 | 4,5 | 6} будут иметь детей {{ 1 | 2,3 | 4,5 | 6}, { 2 | 1,3 | 4,5 | 6}}, { 3 | 1,2 | 4,5 | 6}}}, разложив группу {1,2,3}, а также дети {{1,2, 3 | 4 | 5 | 6}, {1,2,3 | 5 | 4| 6}}, разложив группу {4,5}. Это расщепление может быть выполнено вплоть до листовых узлов, которые являются полными порядками типа {1 | 2 | 3 | 4 | 5 | 6}, которые описывают полный изоморфизм G. Это позволяет взять частичное упорядочение по вершине степень от (1), {1,2,3 | 4,5 | 6} и построить дерево, в котором перечислены все кандидаты для канонического изоморфизма - это уже ПУТЬ меньше n! потому что, например, вершина 6 никогда не будет первой. Обратите внимание, что McKay сначала оценивает детей с глубиной, начиная с самой маленькой группы, это приводит к более глубокому, но более узкому дереву, которое лучше для онлайн-обрезки на следующем шаге. Также обратите внимание, что каждый общий лист упорядочения node может отображаться более чем в одном поддереве, там, где происходит обрезка!

(3) Sect. 6: При поиске дерева найдите автоморфизмы и используйте это, чтобы обрезать дерево. Математика здесь немного выше меня, но я думаю, что идея состоит в том, что если вы обнаружите, что два узла в дереве являются автоморфизмами друг друга, тогда вы можете безопасно обрезать одно из своих поддеревьев, потому что знаете, что они оба будут давать один и тот же лист узлы.

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

Ответ 2

Это интересный вопрос, на который у меня нет ответа! Вот мои два цента:

Под 15M вы имеете в виду 15 миллионов неориентированных графов? Насколько велика каждая из них? Любые свойства, известные о них (деревья, planar, k-trees)?

Вы пытались минимизировать количество проверок, заранее обнаружив ложные срабатывания? Что-то включает в себя вычисление и сравнение чисел, таких как вершины, степени граней и последовательности степеней? В дополнение к другим эвристикам, чтобы проверить, не являются ли эти два графика НЕ ​​изоморфными. Кроме того, проверьте nauty. Это может быть ваш способ проверить их (и создать канонический порядок).

Ответ 3

Это действительно интересная проблема.

Я бы подошел к нему из угла матрицы смежности. Два изоморфных графа будут иметь матрицы смежности, где строки/столбцы находятся в другом порядке. Поэтому моя идея состоит в том, чтобы вычислить для каждого графика несколько свойств матрицы, которые являются инвариантными к свопам строк/столбцов, с верхней части головы:

numVerts, min, max, sum/mean, trace (probably not useful if there are no reflexive edges), norm, rank, min/max/mean column/row sums, min/max/mean column/row norm

и любая пара изоморфных графов будет одинаковой для всех свойств.

Вы можете создать хеш-функцию, которая принимает в графе и выплескивает хеш-строку, например

string hashstr = str(numVerts)+str(min)+str(max)+str(sum)+...

затем отсортировать все графики по хэш-строке, и вам нужно всего лишь выполнить полные проверки изоморфизма для графов, которые хеш-то же самое.

Учитывая, что у вас 15 миллионов графиков на 36 узлах, я предполагаю, что вы имеете дело с взвешенными графиками, для невзвешенных неориентированных графиков этот метод будет менее эффективным.

Ответ 4

Если все ваши графы являются гиперкубами (как вы сказали), то это тривиально: все гиперкубы с одинаковой размерностью изоморфны, гиперкубы с различной размерностью - нет. Таким образом, бегите через свою коллекцию в линейном времени и бросайте каждый граф в ведро в соответствии с его количеством узлов (для гиперкубов: другое измерение <= > различное количество узлов) и выполняются с ним.

Ответ 5

поскольку вы упомянули, что тестирование меньших групп графов ~ 300k можно проверить на изоморфность. Я бы попытался разбить 15M-графы на группы из ~ 300k узлов и запустить тест для изоморфности в каждой группе

скажем: каждый граф Gi: = VixEi (Вершины x Края)

(1) создать ведра графов, так что n-е ведро содержит только графики с | V | = n

(2) для каждого ведра, созданного в (1), создает суббаккеты, так что (n, m) -ый подбактерий содержит только графики, что | V | = n и | E | = m

(3), если группы все еще слишком велики, сортируйте узлы внутри каждого графа по их степеням (что означает nr ребер, связанных с node), создайте из него вектор и распределите графики этим вектором

пример для (3): предположим, что 4 узла V = {v1, v2, v3, v4}. Пусть d (v) - степень v с d (v1) = 3, d (v2) = 1, d (v3) = 5, d (v4) = 4, затем найдите < := transitive hull ( { (v2,v1), (v1,v4), (v4,v3) } ) и создайте вектор, зависящий от степеней и порядок, который оставляет вас с

(1,3,4,5) = (d (v2), d (v1), d (v4), d (v3)) = d ({v2, v1, v4, v3}) = d (<)

теперь вы разделили графики 15M на ведра, где каждое ведро имеет следующие характеристики:

  • n узлов
  • m edge
  • каждый граф в группе имеет один и тот же 'out-degree-vector'

Я предполагаю, что это достаточно тонко, если вы ожидаете, что не найдете слишком много изоморфизмов

стоимость: O (n) + O (n) + O (n * log (n))

(4) теперь вы можете предположить, что члены внутри каждого ведра, вероятно, будут изоморфными. вы можете выполнить изоморфную проверку в ведре и только сравнить текущий проверенный график со всеми представителями, которые вы уже нашли в этом ковше. по предположению, не должно быть слишком много, поэтому я предполагаю, что это довольно дешево.

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

Ответ 6

Возможно, вы можете просто использовать реализацию McKay? Он находится здесь: http://pallini.di.uniroma1.it/

Вы можете преобразовать ваши 15M-графики в компактный формат graph6 (или sparse6), который nauty использует, а затем запустить инструмент nauty labelg для генерации канонических меток (также в формате graph6).

Например, удаление изоморфных графов из набора случайных графов:

#gnp.py
import networkx as nx
for i in range(100000):
    graph = nx.gnp_random_graph(10,0.1)
    print nx.generate_graph6(graph,header=False)


[nauty25r9]$ python gnp.py > gnp.g6
[nauty25r9]$ cat gnp.g6 |./labelg |sort |uniq -c |wc -l
>A labelg
>Z  10000 graphs labelled from stdin to stdout in 0.05 sec.
710