Способность графовых нейронных сетей (GNN) работать со структурами данных графов сделала их пригодными для реальных приложений в социальных сетях, биоинформатике, а также в задачах навигации и планирования в робототехнике. Но, несмотря на их растущую популярность, GNN не лишены своих ограничений, которые включают эффективность обработки, проблему высокой вычислительной сложности и квадратичные требования к памяти для плотных графов.
Для решения этих проблем исследовательская группа Google Brain, Колумбийского и Оксфордского университетов предложила новый класс графовых нейронных сетей, Graph Kernel Attention Transformers (GKAT), которые объединяют ядра графов, сети на основе внимания со структурными априорными параметрами и недавние трансформаторные архитектуры, которые применяют методы неявного внимания с малым объемом памяти с помощью методов низкоранговой декомпозиции. Команда демонстрирует, что GKAT достигают гораздо большей выразительности, чем SOTA GNN, а также сокращают вычислительную нагрузку.
Статья Graph Kernel Attention Transformers начинается с постановки вопроса: «Можно ли спроектировать GNN с уплотненными отдельными слоями, моделируя явно более длинные отношения между узлами в графе, что позволяет использовать более мелкие архитектуры и в то же время масштабировать до более крупных (не обязательно разреженных) графиков? »
Затем исследователи резюмируют преимущества своего подхода GKAT по сравнению с предыдущими методами:
- GKAT могут моделировать зависимости между удаленными узлами в пределах одного уровня внимания.
- Уровни внимания GKAT масштабируют линейное время и память, не требуя явного хранения представлений графов (таких как матрицы смежности) для вычисления слоев внимания, если ядро графа имеет конечное (по крайней мере, на ожидании) (случайное) представление характеристик.
- GKAT очень гибкие, поскольку их можно использовать с различными ядрами графов.
Предложенные GKAT были вдохновлены недавним исследованием плотных линейных преобразователей внимания, где исследования показали, что подходы на основе ядра очень эффективны для разреженных слоев внимания. Следуя этому пути, GKAT моделируют внимание графа внутри каждого слоя как произведение Адамара матрицы ядра векторов признаков узлов и матрицы ядра графа. Это позволяет GKAT использовать эффективные с вычислительной точки зрения механизмы неявного внимания и моделировать зависимости более дальнего действия на одном уровне, повышая их выразительность по сравнению с традиционными GNN.
Чтобы определить выразительные ядра на узлах графа, которые приводят к эффективным сопоставлениям, исследователи используют новый подход случайных блужданий графических узлов (RWGNKs), где значение для двух узлов дается как скалярное произведение двух частотных векторов, которые регистрируют посещения случайные блуждания в узлах графа.
Полная архитектура GKAT состоит из нескольких блоков, каждый из которых состоит из уровня внимания и стандартного уровня MLP. Слои внимания масштабируются линейно, а не квадратично с количеством узлов входных графов, тем самым уменьшая вычислительную сложность по сравнению с их обычными аналогами внимания графов.
Чтобы оценить GKAT с ядрами RWGNK, команда провела эксперименты, от чисто комбинаторных до задач биоинформатики. Они сравнили GKAT с сетями свертки графов (GCN), сетями свертки спектральных графов (SGC), сетями внимания на графах (GAT) и т. Д.
В задаче обнаружения мотивов GKAT превзошел все другие методы по всем мотивам. GKAT также показал лучшую производительность на трех из четырех наборов данных биоинформатики и был одним из двух лучших методов для четырех из пяти наборов данных социальных сетей. В эксперименте по тестированию временной сложности GKAT был быстрее, чем его аналоги GCN, GAT и SGC.
В целом предлагаемые GKAT демонстрируют превосходную производительность для широкого круга задач, от чисто комбинаторных задач через данные социальных сетей до задач биоинформатики, что указывает на их способность повышать выразительность при одновременном снижении вычислительных затрат.
Статья Graph Kernel Attention Transformers находится на arXiv.
Автор: Геката Хе | Редактор: Майкл Саразен, Чейн Чжан
Мы знаем, что вы не хотите пропустить какие-либо новости или научные открытия. Подпишитесь на нашу популярную рассылку Synced Global AI Weekly, чтобы получать еженедельные обновления AI.
