В этом посте будет обобщена статья SimGNN, нацеленная на быстрое вычисление подобия графов. Графы - это структуры, которые используются для связывания различных сущностей, которые мы называем узлами, с помощью отношений, называемых ребрами. Графики существуют повсюду, от связей между атомами до друзей на Facebook, все эти сценарии можно представить в виде графика. Одна из фундаментальных проблем с графами - это нахождение сходства между графами. Сходство между графиками можно определить с помощью этих показателей:

  1. Расстояние редактирования графика
  2. Максимальный общий подграф

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

Вот несколько способов вычисления этих показателей:

  1. Структура проверки обрезки
  2. Быстрое и эвристическое приближение к GED

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

Прежде чем перейти к тому, как работает SimGNN, мы должны знать требования, которым должна удовлетворять эта модель. Это включает в себя :

  1. Инвариант представления: разные представления одного и того же графика должны давать одинаковые результаты.
  2. Индуктивный: должен уметь предсказывать результаты для невидимых графиков.
  3. Обучаемость: должен работать с разными показателями сходства, такими как GED и MCS.

Подход SimGNN: для достижения вышеуказанных требований SimGNN использует две стратегии.

  1. Функция встраивания, доступная для обучения дизайну: отображает график в вектор встраивания, который обеспечивает общую сводку графика. Здесь выбираются некоторые важные узлы, которые используются для встраивания вычислений. (меньшая временная сложность)
  2. Попарное сравнение узлов: приведенные выше вложения являются слишком грубыми, поэтому дополнительно вычисляются оценки попарного сходства между узлами из двух графов, из которых извлекаются характеристики гистограммы и объединяются с информацией уровня графа. (это трудоемкая стратегия)

Некоторые определения:

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

Расстояние редактирования графика - это один из показателей для определения сходства графиков. Он равен минимальному количеству операций редактирования, необходимых для преобразования одного графика в другой. Операции редактирования:

  1. Добавление вершины или удаление вершины или подстановка вершин
  2. Добавление кромки удаления кромки или замена кромки

SimGNN: подход

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

  1. Взаимодействие при внедрении на уровне графика
  2. Сравнение узлов PairWise

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

  1. Встраивание на уровне узла
    GCN используется для встраивания узла. GCN - это архитектура GNN, в которой взаимодействие соседей таково, что он изучает функцию агрегирования. Узлы кодируются в горячем режиме в зависимости от их типов. Узлы без метки получают новую отдельную, но ту же категорию. Наконец, полученные таким образом встраивания узлов передаются в модуль внимания.

2. Встраивание уровня графика:

  • Теперь у нас есть набор встраиваемых узлов, и мы можем агрегировать, производить взвешенную сумму, чтобы получить по одному встраиванию для каждого графа. Но какие узлы должны получить больший вес? Для этого авторы представили механизм «Внимание». Как это работает?
  • Пусть U будет встраиванием узла размера NXD, где n-я строка - это встраивание n-го узла, который равен u размера DX 1. . Теперь мы находим невзвешенное среднее значение этих u и вычисляем контекст графика c, который представляет собой вектор размера D, как:

  • здесь W имеет размер D X D, а u - размер D X 1. Здесь обучаемым параметром является W, и, таким образом, нахождение конкретных весов для каждого элемента 1 x 1 в u, в конечном итоге становится эквивалентным поиску элементов W, таких что они присваивают соответствующий вес каждому элементу u
  • Далее, чтобы привлечь внимание a (n), для каждого узла находят u (n) внутренний продукт c и сопоставляют от 0 до 1. используя сигмовидную функцию.

  • Наконец, вложение графа размером 1 x D находится как:
    h = ∑ a (n) u (n)

3. Взаимодействие графа с графом: нейронная тензорная сеть

  • Теперь, когда у нас есть графовые вложения разных графов, мы хотим найти между ними сходство. Это делается с помощью нейронной тензорной сети.
  • Это дает вектор K x 1, который затем вводится в нейронную сеть для определения оценки сходства.

  • Вскоре я опубликую еще одну статью для NTN (Link) и GNN (почти полную, основанную на этом Video), однако это можно рассматривать как лучший способ найти связь между вложениями двух графов.

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

Сравнение узлов PairWise

Это более сложная вычислительная стратегия по сравнению с предыдущей, в которой выполняются следующие шаги:

  1. Вычисление матрицы подобия графа
    Здесь каждое вложение узла, которое мы собрали на шаге 1, берется и умножается на каждое другое вложение (включая его самого), а затем применяется сигмоидальная активация для получения матрицы N x N. где N = max (N1, N2) и N1, N2 - узлы обоих графов. В случае графов с разными узлами дополнительные узлы добавляются с нулевыми столбцами.

2. Извлечение функций гистограммы

3. Concatenate and Feed: объединение с выходными данными стратегии 1 Neural Tensor Network, полученными на предыдущем шаге, и прохождение через полносвязный слой.

Комбинирование двух стратегий, внедрения на уровне графа и взаимодействия узла с узлом, как обсуждалось выше, дает использование следующей SimGNN:

Заключение

Когда с SimGNN используются разные наборы данных и сравниваются с достоверными значениями, полученными из вычислений GED, или эвристические методы GED дают некоторые многообещающие результаты. Наряду с быстрым вычислением сходства SimGNN лучше всех остальных способов работает с двумя наборами данных и занимает второе место в третьем наборе данных. Более подробную информацию можно прочитать в упомянутой ниже статье.

Реализацию Keras можно найти здесь: «https://github.com/pulkit1joshi/SimGN Анар.

Ссылки:
SimGNN: нейросетевой подход к быстрому вычислению подобия графов. Юньшэн Бай, Хао Дин, Сон Бянь, Тин Чен, Ичжоу Сунь, Вэй Ван. WSDM, 2019. [Бумага]

Https://github.com/pulkit1joshi/SimGNN