Лучшее из двух миров: преимущества гибридных моделей граф-секвенция

В современном мире машинного обучения на графах, последовательные модели, такие как трансформеры и рекуррентные нейронные сети (RNN), получили широкое признание за их способность эффективно обрабатывать последовательные данные. Эти модели, изначально разработанные для обработки текста и временных рядов, теперь адаптируются для работы с графами, предлагая альтернативу традиционным графовым нейронным сетям (GNN), таким как Message Passing Neural Networks (MPNN).

Графовые нейронные сети (GNN) долгое время были основным инструментом для обработки графовых данных. Однако, с появлением трансформеров, которые показали выдающиеся результаты в задачах обработки естественного языка и компьютерного зрения, исследователи начали разрабатывать графовые трансформеры (GT), которые могут лучше справляться с глобальными зависимостями в графах, чем MPNN.

Трансформеры обладают рядом преимуществ:

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

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

• Разряжение матрицы внимания.
• Приближение внимания с помощью низкоранговых матриц.
• Использование механизмов внимания на основе ядер.

Графовые Секвенционные Модели (GSM)

В этом исследовании мы представляем Графовую Секвенционную Модель (GSM), которая объединяет преимущества последовательных моделей для обработки графов. GSM состоит из трех основных этапов:

1. Токенизация: Граф переводится в набор последовательностей.
2. Локальное Кодирование: Кодируются локальные соседства вокруг каждого узла.
3. Глобальное Кодирование: Используется масштабируемая последовательная модель для захвата долгосрочных зависимостей в последовательностях.

Токенизация

Токенизация графа в последовательности может быть выполнена двумя основными способами:

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

Локальное Кодирование

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

Глобальное Кодирование

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

Выбор Последовательной Модели

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

Задачи Подсчета

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

Важность Порядка Узлов

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

Задачи Связности

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

Выбор Токенизатора

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

Улучшение GSM

Иерархическая Аффинитная Кластеризация (HAC) для Токенизации

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

Гибридные Модели

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

Смешение Токенизации (MoT)

Мы также вводим концепцию MoT, позволяющую использовать различные токенизации для разных узлов, что может улучшить эффективность и производительность модели.

Заключение

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