Передача сообщений по всем парам с O(N)
В последнее время создание моделей Transformer для обработки графоструктурированных данных вызвало широкий интерес в сообществе исследователей машинного обучения. Одна из критических проблем связана с квадратичной сложностью глобального внимания, которая мешает трансформерам масштабироваться до больших графов. В этом блоге будет кратко представлена недавняя работа над NeurIPS22:
NodeFormer: масштабируемый преобразователь структуры графа для классификации узлов с его общедоступной реализацией.
В этой работе предлагаются масштабируемые преобразователи графов для графов классификации больших узлов, где количество узлов может варьироваться от тысяч до миллионов (или даже больше). Ключевой модуль представляет собой передачу сообщений на основе ядра Gumbel-Softmax, которая обеспечивает распространение функций по всем парам со сложностью O(N) (N для #nodes).
Нижеследующее содержание подытожит основную идею и результаты данной работы.
Графические трансформаторы против Граф нейронных сетей
В отличие от нейронных сетей графа (GNN), которые прибегают к передаче сообщений по фиксированной топологии входного графа, преобразователи графов могут более гибко агрегировать глобальную информацию со всех узлов посредством адаптивной топологии на каждом уровне распространения. В частности, графические трансформеры имеют ряд преимуществ:
- Обработка несовершенных структур.Для графических данных с гетерофилией, долгосрочной зависимостью и ложными краями GNN часто показывает недостаточную мощность из-за своей схемы агрегирования локальных признаков. Тем не менее, Трансформеры привлекают внимание всего мира, объединяя информацию со всех узлов на одном уровне, что позволяет преодолеть ограничения входных структур.
- Избегание чрезмерного сжатия.GNN могут экспоненциально терять информацию при агрегировании информации в вектор фиксированной длины, в то время как преобразователи графов используют глобальное внимательное агрегирование, которое может адаптивно обслуживать доминирующие узлы, которые являются информативными для задач прогнозирования целевого узла.
- Гибкость для задач без графа.Помимо проблем с графами, также существует множество задач, в которых нет графовой структуры. Например, классификация изображений и текста (каждое изображение можно рассматривать как узел, но нет соединяющего их графа) и моделирование физики (каждая частица является узлом, но нет явно наблюдаемого графа). Хотя общепринятой практикой является использование k-NN поверх входных признаков для построения графа подобия для передачи сообщений, такой искусственно созданный граф часто не зависит от последующих задач прогнозирования и может привести к неоптимальной производительности. Преобразователи решают эту проблему, позволяя автоматически изучать структуры адаптивного графа для передачи сообщений.
Проблемы построения трансформаторов на больших графах
Несколько проблем делают нетривиальной задачу построения трансформеров на больших графах, особенно тех, которые содержат более тысячи узлов.
- Квадратичная сложность для глобального внимания. Вычисление внимания для агрегирования всех пар признаков требует сложности O(N²), что недопустимо для больших графов, где N может быть сколь угодно большим, например, от тысяч до миллионов. Конкретно говоря, обычный графический процессор с 16 ГБ памяти не сможет обеспечить такое глобальное внимание ко всем узлам, если N больше 10 КБ.
- Согласие с разреженностью графа.Реальные графы часто бывают разреженными по сравнению с внимательным графом (мы можем рассматривать матрицу внимания как взвешенную матрицу смежности графа), которая плотно соединяет все пары узлов. Проблема в том, что когда N становится большим, распространение признаков по такому плотному графу может вызвать то, что мы называем проблемой чрезмерной нормализации, что означает, что информация из разных узлов разбавляется другими. Вероятное средство для разреживания обучаемых структур перед распространением.
Ядро передачи сообщений на основе Gumbel-Softmax
Наша работа NodeFormer сочетает в себе карту случайных признаков и Gumbel-Softmax как единую модель для решения вышеупомянутых проблем. В частности, Gumbel-Softmax впервые используется для замены исходной агрегации внимательных функций на основе Softmax:
Приведенное выше уравнение определяет вычисление для узла u, которое требует O (N), а для вычисления представлений для N узлов требуется сложность O (N²), поскольку необходимо независимо вычислять оценки внимания для всех пар. Чтобы решить эту трудность, мы прибегаем к основной идее в Исполнителе и применяем карту случайных признаков (RFM) для аппроксимации Gumbel-Softmax (первоначальное внедрение RFM в Performer направлено на аппроксимацию детерминированного внимания Softmax, и здесь мы расширяем такие метод Gumbel-Softmax со стохастическим шумом).
Важно отметить, что в новом вычислении, то есть в правой части приведенного выше уравнения, два члена суммирования (по N узлам) являются общими для всех узлов и могут быть вычислены только один раз в одном слое. Следовательно, это приводит к сложности O(N) для обновления N узлов на одном уровне.
Как использовать входные графики
Еще один важный вопрос заключается в том, как использовать входные структуры (если они доступны), поскольку описанная выше передача сообщений по всем парам игнорирует входной граф. Мы дополнительно предлагаем две простые стратегии:
- Добавление реляционного смещения: мы дополнительно предполагаем обучаемый скалярный термин, который добавляется к показателю внимания между узлами u и v, если на входном графике между ними есть ребро.
- Потери при регуляризации краев. Используйте показатель внимания для края (u, v) в качестве оценочной вероятности и определите потерю оценки максимального правдоподобия (MLE) для всех наблюдаемых краев. Интуитивно понятно, что этот дизайн максимизирует вес внимания для наблюдаемых краев.
Но важность (или, скажем, информативность) входного графика различается для разных наборов данных. Таким образом, на практике необходимо настроить вес (как гиперпараметр), который определяет, сколько внимания уделяется входным графикам. На следующем рисунке показан общий поток данных NodeFormer.
Результаты эксперимента
Мы применяем NodeFormer для задач классификации узлов и достигаем очень конкурентоспособных результатов на восьми наборах данных по сравнению с обычными GNN и современными моделями обучения структуры графа LDS и IDGL.
Помимо классификации узлов, мы также рассматриваем задачи классификации изображений и текста, в которых отсутствуют входные графы. Мы используем k-NN с разными значениями k (5, 10, 15, 20) для построения графа, а также рассматриваем возможность отказа от использования входного графа для NodeFormer. Интересно, что последний случай не приводит к явному падению производительности, а иногда может повысить производительность.
В качестве нового класса модели мы выделяем некоторые преимущества NodeFormer:
- Емкость: NodeFormer адаптивно изучает структуру графа за счет разреженного внимания на каждом уровне и потенциально собирает информацию со всех узлов.
- Масштабируемость. NodeFormer обеспечивает сложность O(N) и мини-пакетное обучение разделов. На практике он успешно масштабируется до больших графов с миллионами узлов, используя всего 4 ГБ памяти.
- Эффективность.Обучение NodeFormer может быть эффективным сквозным способом с оптимизацией на основе градиента. Например, обучение и оценка Cora в 1000 эпох занимает всего 1–2 минуты.
- Гибкость.NodeFormer является гибким для индуктивного обучения и обработки случаев отсутствия графа.
Мы также кратко обсудим возможные применения NodeFormer. В общем случае NodeFormer можно использовать в качестве кодировщика общего назначения для графически структурированных данных или для обработки взаимозависимостей между экземплярами в стандартных задачах прогнозирования. В частности, его можно легко применить к двум классам задач:
- Прогностические задачи на (больших) графах, то есть цель состоит в том, чтобы предсказать метку каждого узла (или ребра) на основе характеристик узла и структуры графа. Например, прогнозирование активности пользователей в крупных социальных сетях.
- Стандартные прогностические задачи (классификация или регрессия) без входных графиков и NodeFormer могут использоваться для использования потенциальной взаимозависимости между экземплярами в наборе данных. Например, классификация изображений.
В этом блоге представлены новые преобразователи графов, которые успешно масштабируются до больших графов и демонстрируют многообещающую производительность по сравнению с обычными GNN. Модели в стиле трансформатора обладают некоторыми неотъемлемыми преимуществами, которые могут преодолеть ограничения GNN в отношении обработки зависимости дальнего действия, гетерофилии, чрезмерного сжатия, графического шума и полного отсутствия графов. Несмотря на это, создание мощных преобразователей графов, которые могут служить моделью представления графов следующего поколения, все еще остается открытой и недостаточно изученной проблемой, и мы надеемся, что эта работа может пролить свет на это направление.
Если вы заинтересованы в этой работе, можно прочитать статью для получения более подробной информации.
Все изображения, если не указано иное, принадлежат автору.
