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

Современные модели последовательностей (например, трансформеры, линейные РНС и т.д.) вышли на передовые позиции в последних фреймворках глубокого обучения, в основном благодаря своей эффективности, способности к представлению данных и/или возможности захвата дальних зависимостей. Применение этих моделей последовательностей к данным с графовой структурой недавно стало популярным как альтернатива Сетям с Передачей Сообщений (MPNN). Однако, существует недостаток общих основ относительно того, что делает модель последовательности графа хорошей, а также математического описания преимуществ и недостатков использования различных моделей последовательностей для обучения на графах. В этом направлении мы сначала представляем Модель Последовательностей Графов (GSM), единую платформу для адаптации моделей последовательностей к графам, состоящую из трех основных шагов: (1) Токенизация, которая преобразует граф в набор последовательностей; (2) Локальное Кодирование, которое кодирует локальные окрестности вокруг каждой вершины; и (3) Глобальное Кодирование, которое использует масштабируемую модель последовательности для захвата дальних зависимостей в последовательностях. Эта платформа позволяет нам понимать, оценивать и сравнивать мощность различных базовых моделей последовательностей в задачах с графами. Наши теоретические оценки представительной способности трансформеров и современных рекуррентных моделей через призму глобальных и локальных задач графов показывают, что существуют как положительные, так и отрицательные стороны для обоих типов моделей. Опираясь на это наблюдение, мы представляем GSM++, быструю гибридную модель, которая использует алгоритм Иерархического Аффинного Кластеризации (HAC) для токенизации графа в иерархические последовательности, а затем применяет гибридную архитектуру трансформера для кодирования этих последовательностей. Наши теоретические и экспериментальные результаты подтверждают дизайн GSM++, показывая, что GSM++ превосходит базовые модели в большинстве тестов на эталонных примерах.