Механизм передачи сообщений в графовых нейронных сетях (GNN) до сих пор остается загадкой. Помимо сверточных нейронных сетей, не было предложено никакого теоретического происхождения GNN. К нашему удивлению, передачу сообщений лучше всего можно понять с точки зрения итерации мощности. Полностью или частично удаляя функции активации и веса слоев GNN, мы предлагаем модели кластеризации мощности подпространства (SPIC), которые итеративно обучаются только с одним агрегатором. Эксперименты показывают, что наши модели расширяют GNN и улучшают их способность обрабатывать сети со случайными признаками. Кроме того, мы демонстрируем избыточность некоторых современных GNN в дизайне и определяем нижний предел для оценки модели случайным агрегатором передачи сообщений. Наши выводы раздвигают границы теоретического понимания нейронных сетей.

Основной вывод

  1. Кластеризация мощной итерации может быть рациональным и ценным теоретическим источником для GNN.
  2. Текущие GNN имеют избыточность в модели и функциях.
  3. Агрегаторы со случайным взвешиванием также могут быть очень мощными.
  4. Power GNN может работать со случайным графиком.

GNN и Power Iteration

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

При приведенном выше упрощении модели ReLU недействителен из-за того, что агрегатор M неотрицательный, а признак графа всегда можно преобразовать, чтобы он стал неотрицательным, и каждый узел в графе всегда будет получать неотрицательную информацию. Тогда вышеуказанная GNN k-слоя может быть выражена как

Идеи для этой статьи

Эта работа в основном вдохновлена ​​двумя документами:

  1. Ю. Корень. (2005). Построение графов по собственным векторам: теория и практика // Ж. вычисл. Мат. с заявл. 49, 1867–1888 гг.
  2. Ф. Лин и В. В. Коэн. (2010). Power Iteration Clustering, в ICML, стр. 655–662.

Первая статья дает мне интуитивное представление о механизме GNN:

Давайте построим график в одном измерении, скажем, по оси X. Итеративное размещение каждого узла в среднем между его старым местом и центроидом его соседей в течение k раз может быть выражено как

Вопрос:

  1. Кажется, что GNN делает то же самое, но обычно состоит из неглубокой структуры, двух или трех слоев. Он не вычисляет собственные векторы.

Второй документ отвечает на вопрос:

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

Ограничения:

  1. Он использует только одномерный вектор в итерации мощности.
  2. Неконтролируемое обучение с использованием k-средних для вышеуказанного вектора.
  3. Он следует строгому правилу степенной итерации, нормализуя результат на каждой итерации.

Кластеризация мощности подпространства

Обсуждались пять случаев:

  1. Все функции активации и веса слоев удалены.
  2. Все веса слоев удаляются, и ReLU помещается на первый слой.
  3. Все слои имеют функции активации и имеют одинаковый вес.
  4. Все слои имеют одинаковый вес, и все активации удаляются.
  5. Используются случайные агрегаторы.

Тип данных определяется GAT:

Линейный: при выполнении GAT веса внимания распределяются почти равномерно независимо от головок и слоев. Активации и веса слоев в некоторой степени недействительны для этих данных.

Нелинейный: можно наблюдать значительные различия во внимании.

вопросы и ответы

Вопрос. Почему мы можем удалять активации из GNN, всегда ли это работает?

О: Причина удаления активаций двояка.

#1: Как было показано ранее, без весов слоев и активаций.

№ 2: Веса внимания GAT почти равномерно распределяются по всем эталонным сетям цитирования, независимо от заголовков и слоев. Эти дублированные агрегаторы являются просто сдвинутыми версиями друг друга и указывают на линейность модели и данных.

Но существенные отличия наблюдаются для случая ИЦП. Мы интерпретируем это как нелинейность. В модели SPIC следует добавлять нелинейные слои.

Вопрос. Какова избыточность GNN?

A: Избыточность модели №1:

# 2 Избыточность функций:

Это два раза:

# 1 Мы немного теряем, уменьшая размерность признаков сети Cora (например, 1433->800, 1433->193), особенно для моделей SPIC, что означает, что мы можем дополнительно оптимизировать функции графа.

# 2 GNN хорошо обслуживают только сети с реальными функциями, тогда как модели SPIC по-прежнему могут захватывать сообщества в случайных сетях. Примечательным изменением здесь является то, что случайные функции требуют большего количества итераций (например, ​).

Вопрос Какова связь между GNN и SPIC?

A Мы рассматриваем SPIC как возможное теоретическое происхождение GNN. По сути, они разделяют идею: полезную информацию можно получить из этих траекторий различной конвергенции с разными размерностями вектора признаков. Успех случайных агрегаторов делает этот механизм более понятным, а это, в свою очередь, сужает возможности для разработки более инновационных уровней распространения.

Вопрос Как вы относитесь к другим объяснениям GNN?

A Очевидно, что в объяснении механизма GNN есть большая свобода действий и творческий подход. Такие объяснения, как лапласовское сглаживание, оптимизация градиентного спуска и оптимизация подгонки фильтра признаков, разумны и интересны. Сглаживание похоже на абстрактный родительский класс в языке программирования, и все объяснения вытекают из него. Я уделяю больше внимания случайному распространению, потому что оно также сужает пространство для объяснения GNN.

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

Примечание. Если у вас возникнут вопросы о мощных GNN, свяжитесь со мной по адресу:

[email protected]