Тест на изоморфизм графа Вайсфейлера-Лемана

В теории графов тест изоморфизма графов Вейсфейлера-Лемана представляет собой эвристический тест на существование изоморфизма между двумя графами G и H. ^[1] Он является обобщением алгоритма уточнения цвета и был впервые описан Вейсфейлером и Леманом в 1968 году. ^[2] Первоначальная формулировка основана на канонизации графа , нормальной форме для графов, хотя существует также комбинаторная интерпретация в духе уточнения цвета и связи с логикой.

Существует несколько версий теста (например, k-WL и k-FWL), упоминаемых в литературе под разными названиями, что легко приводит к путанице. Кроме того, в нескольких старых статьях Андрей Леман пишется как «Lehman».

Эвристика изоморфизма графов на основе Вайсфейлера-Лемана

Все варианты уточнения цвета являются односторонними эвристиками, которые принимают в качестве входных данных два графа G и H и выводят сертификат, что они различны, или «Я не знаю». Это означает, что если эвристика способна различить G и H , то они определенно различны, но другое направление не выполняется: для каждого варианта теста WL (см. ниже) существуют неизоморфные графы, где различие не обнаруживается. Эти графы являются высокосимметричными графами, такими как регулярные графы для уточнения цвета 1-WL.

1-мерный Вайсфейлер-Леман (1-WL)

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

Инициализация Все узлы инициализируются одним и тем же цветом 0

Уточнение Два узла u, v получают разный цвет, если а) они имели разный цвет раньше или б) существует цвет c, такой что u и v имеют разное количество соседей цвета c .

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

Чтобы использовать этот алгоритм в качестве теста на изоморфизм графов, алгоритм запускается на двух входных графах G и H параллельно, т. е. с использованием цветов при разделении таким образом, что некоторый цвет c (после одной итерации) может означать «узел с ровно 5 соседями цвета 0». На практике это достигается путем запуска уточнения цвета на несвязном графе объединения G и H. Затем можно посмотреть на гистограмму цветов обоих графов (подсчитав количество узлов после стабилизации уточнения цвета), и если они различаются, это является свидетельством того, что оба графа не изоморфны.

Алгоритм завершается после максимум раундов, где — число узлов входного графа, поскольку он должен разделить один раздел на каждом шаге уточнения, и это может происходить максимум до тех пор, пока каждый узел не будет иметь свой собственный цвет. Обратите внимание, что существуют графы, для которых требуется это число итераций, хотя на практике число раундов до завершения, как правило, очень мало (<10). $n-1$ $n$

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

Высший порядок Вайсфейлера-Лемана

Это то место, где появляются вышеупомянутые два варианта алгоритма WL. Как k -мерный алгоритм Вайсфейлера-Лемана (k-WL), так и k -мерный фольклорный алгоритм Вайсфейлера-Лемана (k-FWL) являются расширениями 1-WL сверху, работающими над k-кортежами вместо отдельных узлов. Хотя их различие на первый взгляд выглядит невинным, можно показать, что k-WL и (k-1)-FWL (для k>2) различают одни и те же пары графов.

к-БЛ (к>1)

Вход : график G = (V,E)# инициализировать $c^{0}({\bar {v}})={\text{Хэш}}({\text{тип}}({\bar {v}}))$ для всех повторять для всех пока (обе раскраски не индуцируют идентичные разбиения ) вернуть ${\bar {v}}\in V^{k}$   $c_{i}^{\ell }({\bar {v}})=\{\!\{c^{\ell -1}({\bar {w}}):{\bar {w}}\in {\mathcal {N}}_{i}({\bar {v}})\}\!\}$  ${\bar {v}}\in V^{k},i\in [k]$   $c^{\ell }({\bar {v}})={\text{Hash}}(c^{\ell -1}({\bar {v}}),c_{1}^{\ell }({\bar {v}}),\dots ,c_{k}^{\ell }({\bar {v}}))$   $c^{\ell }\equiv c^{\ell -1}$  $V^{k}$   $c^{\ell }$

Здесь соседство k-кортежа задается набором всех k-кортежей, достижимых путем обмена i-й позиции : Атомарный тип кортежа кодирует информацию о ребрах между всеми парами узлов из . Например, 2-кортеж имеет только два возможных атомарных типа, а именно, два узла могут иметь общее ребро или нет. Обратите внимание, что если граф имеет несколько (различных) отношений ребер или дополнительных узловых особенностей, членство в них также представлено в . ${\mathcal {N}}_{i}({\bar {v}})$ ${\bar {v}}$ ${\bar {v}}$ ${\mathcal {N}}_{i}({\bar {v}})=\{(v_{1},\dots ,v_{i-1},w,v_{i+1},\dots ,v_{k}):w\in V\}$ ${\text{type}}({\bar {v}})$ ${\bar {v}}$ ${\text{type}}({\bar {v}})$

Основная идея k-WL заключается в расширении понятия соседства до k-кортежей, а затем в эффективном выполнении уточнения цвета на полученном графе.

к-ФВЛ (к>1)

Вход : график G = (V,E)# инициализировать $c^{0}({\bar {v}})={\text{Hash}}({\text{type}}({\bar {v}})$ ) для всех повторять для всех пока (обе раскраски не индуцируют идентичные разбиения ) вернуть ${\bar {v}}\in V^{k}$   $c_{w}^{\ell }({\bar {v}})={\big (}c^{\ell -1}({\bar {v}}[1]\!\!\leftarrow \!w),\dots ,c^{\ell -1}({\bar {v}}[k]\!\!\leftarrow \!w){\big )}$  ${\bar {v}}\in V^{k},w\in V$   $c^{\ell }({\bar {v}})={\text{Hash}}{\big (}c^{\ell -1}({\bar {v}}),\{\!\{c_{w}^{\ell }({\bar {v}}):w\in V\}\!\}{\big )}$   $c^{\ell }\equiv c^{\ell -1}$  $V^{k}$   $c^{\ell }$

Вот кортеж , в котором i-я позиция заменена на . ${\bar {v}}[i]\!\!\leftarrow \!w$ ${\bar {v}}$ $w$

Обратите внимание, что между k-WL и k-FWL есть одно важное различие: k-FWL проверяет, что произойдет, если один узел w поместить в любую позицию k-кортежа (и затем вычисляет мультимножество этих k-кортежей), тогда как k-WL смотрит на мультимножества, которые вы получаете при изменении только i-го компонента исходного k-кортежа. Затем он использует все эти мультимножества в хэше, который вычисляет новый цвет.

Можно показать (хотя только через связь с логикой), что k-FWL и (k+1)-WL эквивалентны (для ). Поскольку оба алгоритма масштабируются экспоненциально по k (оба перебирают все k-кортежи), использование k-FWL гораздо эффективнее, чем использование эквивалентного (k+1)-WL. $k\geq 2$

Примеры и код для 1-WL

Код

# АЛГОРИТМ WLpairs # ВХОД: два графа G и H для проверки на изоморфизм # ВЫХОД: Сертификаты для G и H и их согласие U  =  combineTwo ( G ,  H ) glabels  =  initializeLabels ( U )  # словарь, в котором каждый узел получает одинаковую метку 0 labels  =  {}  # словарь, который обеспечит перевод строки меток узла и его соседей в целое число newLabel  =  1 done  =  False while  not ( done ):  glabelsNew  =  {} #  настроить словарь меток для следующего шага  for  node  in  U :  label  =  str ( glabels [ node ])  +  str ([ glabels [ x ]  for  x  in  neighbors  of  node ] .sort ()) if not ( label in labels ): # комбинация меток узла и его соседей встречается впервые labels [ label ] = newLabel # назначить строку меток новый номер как сокращенная метка newLabel + = 1 # увеличиваем счетчик для назначения новых сокращенных меток glabelsNew [ узел ] = labels [ метка ] if ( количество различных меток в glabels ) == ( количество различных меток в glabelsNew ) : done = True else : glabels = glabelsNew . copy ( ) certificateG = сертификат для G из отсортированных меток G - части U certificateH = сертификат для H из отсортированных меток                                                           H  - часть U  если сертификатG == сертификатH : тест = Истина иначе : тест = Ложь

Вот реальный код Python , включающий описание первых примеров.

g5_00  =  { 0 :  { 1,2,4 } , 1 : { 0,2 } , 2 : { 0,1,3 } , 3 : { 2,4 } , 4 : { 0,3 } } g5_01 = { 0 : {  3,4 } , 1 : { 2,3,4 } , 2 : { 1,3 } , 3 : { 0,1,2 } , 4 : { 0,1 } } g5_02 = { 0 : { 1,2,4 } , 1 : { 0,3 } , 2 : { 0,3 } , 3 : { 1,2,4 } , 4: { 0 , 3 }}                                                  def  combineTwo ( g1 ,  g2 ) :  g  =  {  } n  =  len ( g1 )  для  узла  в  g1 :  s  =  set ( )  для  соседа  в  g1 [ узел ]  : s.add ( сосед ) g [ узел ] = s.copy ( ) для узла в g2 : s = set ( ) для соседа в g2 [ узел ] : s.add ( сосед + n ) g [ узел + n ] = s.copy ( ) return g                        g  =  combineTwo ( g5_00 ,  g5_02 ) labels  =  {} glabels  =  {} для  i  в  диапазоне ( len ( g )):  glabels [ i ]  =  0 glabelsCount  =  1 newlabel  =  1done  =  False while  not  ( done ):  glabelsNew  =  {}  glabelsCountNew  =  0  for  node  in  g :  label  =  str ( glabels [ node ])  s2  =  []  for  neighbor  in  g [ node ]:  s2 . append ( glabels [ neighbor ])  s2 . sort ()  for  i  in  range ( len ( s2 )):  label  +=  "_"  +  str ( s2 [ i ])  if  not  ( label  in  labels ):  labels [ label ]  =  newlabel  newlabel  +=  1  glabelsCountNew  +=  1  glabelsNew [ node ]  =  labels [ label ]  if  glabelsCount  ==  glabelsCountNew :  done  =  True  else :  glabelsCount  =  glabelsCountNew  glabels  =  glabelsNew . copy () print ( glabels )g0labels  =  [] для  i  в  диапазоне ( len ( g0 )):  g0labels . append ( glabels [ i ]) g0labels . sort () certificate0  =  "" для  i  в  диапазоне ( len ( g0 )):  certificate0  +=  str ( g0labels [ i ])  +  "_" g1labels  =  [] для  i  в  диапазоне ( len ( g1 )):  g1labels . append ( glabels [ i  +  len ( g0 )]) g1labels . sort () certificate1  =  "" для  i  в  диапазоне ( len ( g1 )):  certificate1  +=  str ( g1labels [ i ])  +  "_"если  сертификат0  ==  сертификат1 :  тест  =  Истина иначе :  тест  =  Ложь print ( "Сертификат 0:" ,  сертификат0 ) print ( "Сертификат 1:" ,  сертификат1 ) print ( "Результаты теста:" ,  тест )

Примеры

Первые три примера относятся к графам 5-го порядка ^{. [3]}

WLpair проходит 3 раунда на 'G0' и 'G1'. Тест проходит успешно, так как сертификаты совпадают.

WLpair проходит 4 раунда на 'G0' и 'G2'. Тест не пройден, так как сертификаты не совпадают. Действительно, 'G0' имеет цикл длиной 5, а 'G2' — нет, поэтому 'G0' и 'G2' не могут быть изоморфными.

WLpair проходит 4 раунда на 'G1' и 'G2'. Тест провален, так как сертификаты не совпадают. Из предыдущих двух случаев мы уже знаем . $G_{1}\cong G_{0}\not \cong G_{2}$

Действительно, G0 и G1 изоморфны. Любой изоморфизм должен уважать компоненты и, следовательно, метки. Это можно использовать для кернелизации проблемы изоморфизма графов. Обратите внимание, что не каждое отображение вершин, уважающее метки, дает изоморфизм. Пусть и будут отображениями, заданными соответственно . В то время как не является изоморфизмом, составляет изоморфизм. $\varphi :G_{0}\rightarrow G_{1}$ $\psi :G_{0}\rightarrow G_{1}$ $\varphi (a)=D,\varphi (b)=C,\varphi (c)=B,\varphi (d)=E,\varphi (e)=A$ $\psi (a)=B,\psi (b)=C,\psi (c)=D,\psi (d)=E,\psi (e)=A$ $\varphi$ $\psi$

При применении WLpair к G0 и G2 мы получаем для G0 сертификат 7_7_8_9_9 . Но изоморфный G1 получает сертификат 7_7_8_8_9 при применении WLpair к G1 и G2 . Это иллюстрирует явление о метках в зависимости от порядка выполнения WLtest на узлах. Либо кто-то находит другой метод перемаркировки, который сохраняет уникальность меток, что становится довольно техническим, либо кто-то вообще пропускает перемаркировку и сохраняет строки меток, что значительно увеличивает длину сертификата, либо кто-то применяет WLtest к объединению двух протестированных графов, как мы сделали в варианте WLpair. Обратите внимание, что хотя G1 и G2 могут получить разные сертификаты, когда WLtest выполняется на них по отдельности, они получают один и тот же сертификат с помощью WLpair.

Следующий пример касается регулярных графов . WLtest не может различать регулярные графы одинакового порядка, ^[4]^{: 31} , но WLpair может различать регулярные графы разной степени, даже если они имеют одинаковый порядок. Фактически WLtest завершается после одного раунда, как видно из этих примеров порядка 8, которые все являются 3-регулярными, за исключением последнего, который является 5-регулярным.

Все четыре графа попарно неизоморфны. G8_00 имеет две связные компоненты, а остальные — нет. G8_03 является 5-регулярным, а остальные — 3-регулярными. G8_01 не имеет 3-цикла, а G8_02 имеет 3-цикл.

Другой пример двух неизоморфных графов, которые WLpair не может различить, приведен здесь . ^[5]

Приложения

Теория, лежащая в основе теста Вайсфейлера-Лемана, применяется в графовых нейронных сетях .

Ядра графа Вайсфейлера-Лемана

В машинном обучении нелинейных данных используются ядра для представления данных в пространстве признаков высокой размерности, после чего могут быть применены линейные методы, такие как машины опорных векторов . Данные, представленные в виде графов, часто ведут себя нелинейно . Графовые ядра являются методом предварительной обработки таких нелинейных данных на основе графов для упрощения последующих методов обучения. Такие графовые ядра могут быть построены путем частичного выполнения теста Вайсфейлера-Лемана и обработки раздела, который был построен к этому моменту. ^[6] Эти графовые ядра Вайсфейлера-Лемана привлекли значительное внимание исследователей в течение десятилетия после их публикации. ^[1] Они также реализованы в специализированных библиотеках для графовых ядер, таких как GraKeL. ^[7]

Обратите внимание, что ядра для искусственной нейронной сети в контексте машинного обучения , такие как ядра графов, не следует путать с ядрами, применяемыми в эвристических алгоритмах для снижения вычислительных затрат при решении задач высокой сложности, таких как примеры NP-трудных задач в области теории сложности . Как указано выше, тест Вайсфейлера-Лемана также может быть применен в последнем контексте.

Смотрите также

Ссылки

^ ab Huang, Ningyuan; Villar, Soledad (2022), «Краткое руководство по тесту Вайсфейлера-Лемана и его вариантам», ICASSP 2021 - 2021 IEEE Международная конференция по акустике, речи и обработке сигналов (ICASSP) , стр. 8533–8537, arXiv : 2201.07083 , doi : 10.1109/ICASSP39728.2021.9413523, ISBN 978-1-7281-7605-5, S2CID 235780517
^ Вайсфейлер, Б. Ю. ; Леман, А. А. (1968). «Приведение графа к каноническому виду и возникающая при этом приведении алгебра» (PDF) . Научно-техническая информация . 2 (9): 12–16 . Получено 28.10.2023 .
^ Бибер, Дэвид (2019-05-10). "Тест на изоморфизм Вайсфейлера-Лемана" . Получено 2023-10-28 .
^ Кифер, Сандра (2020). Мощность и ограничения алгоритма Вайсфейлера-Лемана (диссертация). RWTH Aachen University . Получено 29.10.2023 .
^ Бронштейн, Майкл (2020-12-01). "Выразительная сила графовых нейронных сетей и тест Вайсфейлера-Лемана" . Получено 2023-10-28 .
^ Шервашидзе, Нино; Швейцер, Паскаль; Ван Леувен, Эрик Ян; Мельхорн, Курт; Боргвардт, Карстен М. (2011). «Ядра графа Вайсфейлера-Лемана». Журнал исследований машинного обучения . 12 (9): 2539−2561 . Получено 29 октября 2023 г.
^ "Weisfeiler Lehman Framework". 2019. Получено 29 октября 2023 г. Этот фреймворк Weisfeiler Lehman работает поверх существующих графовых ядер и вдохновлен тестом изоморфизма графов Weisfeiler-Lehman [WL68].