TD; LR - Учитывая представление Graph в терминах матрицы смежности, оно не фиксирует пространственную корреляцию, необходимую для свертки. Этот пост отражает интуицию о том, как домен Фурье помогает в свертке.
Предварительные условия для представления графа - https://medium.com/analytics-vidhya/unboxai-introduction-to-graph-machine-learning-e4b88514258c
Почему свертка
Прежде чем мы углубимся в свертки графов, позвольте нам понять, что делает свертка в пространственной области - стандартный ответ - сказать «она фиксирует скрытые пространственные особенности». Это говорит нам, что делает свертка, но все же необходимо решить, почему свертка.
Возьмем стандартные MNIST-данные с изображениями 28 * 28.
Многослойный персептрон
В случае MLP - мы сглаживаем каждое изображение (матрица 28 * 28) в один вектор-строку размером 784 (28 * 28) и передаем его в качестве входных данных. Скажем, наше скрытое измерение - достичь 256-мерного вложения. Таким образом, соответствующая весовая матрица здесь будет 784 x 256-D.
В свертке - мы определяем ядро (или маску 😢), чтобы скользить по изображению, чтобы получить «пространственные особенности» 😏
Интуиция для свертки
Спрашивается - а что в этом нового? Он по-прежнему фиксирует пространственные отношения в данных. Ответ на этот вопрос - посмотреть на количество параметров. В случае MLP - поскольку мы рассматриваем каждый пиксель как независимый от каждого другого пикселя, у нас есть 784 веса для каждого скрытого измерения (если встраивание измерения составляет 256 - тогда у нас есть 784 x 256 в качестве матрицы весов)
В случае двумерной свертки (изображения в оттенках серого) - у нас есть входные данные 28 * 28 и ядро, скажем, размерности 3x3. Тогда общее количество обучаемых параметров для одного канала будет 9 (3 * 3) + 1 (необязательное смещение). и если мы выберем 256 карт функций - у нас будет 256 карт * 10 всего с 2560 обучаемыми весами по сравнению с 200704 весами в случае MLP.
Ключевая идея свертки состоит в том, чтобы извлечь выгоду из локализации изображения - то есть в локальном представлении (область маски) ядра, пиксели в окрестности похожи и имеют очень мало скачков / краев. Это причина того, почему свертка, применяемая к изображениям, имеет смысл.
Давайте рассмотрим случай, когда это не так - нам нужно построить нейронную сеть, чтобы принять решение об одобрении банковской ссуды. Наш вход - это 5-мерный вектор, имеющий следующие особенности
Характеристики - [возраст, доход, пол, семейное положение, стоимость активов]
В этом случае свертка не имеет смысла. Поскольку в пространстве признаков нет общей информации - каждое измерение вектора признаков является «независимым»
Свертка графов
Теперь, когда мы вооружены знаниями о свертке, давайте создадим матрицу смежности для Graph и пропустим ее через столько сверток, сколько захотим.
Но у нас есть проблемы с этим подходом. Назвать несколько:
- Нет понятия близости - скажем, узел 1 подключен к узлу 1-Million. Ядро размера, скажем, 3x3 или 5x5, не улавливает понятие окрестности
- Попытка расширить до крупномасштабных разреженных графов - перемещение-фильтр (скольжение) по смежности здесь не имеет смысла. Большинство элементов будут просто нулями.
Интуиция свертки графов
Идея свертки изображения состоит в том, чтобы представить пиксель средневзвешенным значением его соседей. Это аналогично умножению матрицы смежности на веса.
Давайте возьмем матрицу на приведенной выше диаграмме и умножим на одномерный вектор всех единиц.
In [1]: import numpy as np
In [3]: A = np.array([[0,1,1,1,0],[1,0,0,1,1],[1,0,0,1,0],[1,1,1,1,1],[0,1,0,1,0]])
In [4]: A
Out[4]:
array([[0, 1, 1, 1, 0],
[1, 0, 0, 1, 1],
[1, 0, 0, 1, 0],
[1, 1, 1, 1, 1],
[0, 1, 0, 1, 0]])
In [10]: W = [1,1,1,1,1]
In [11]: np.matmul(A, W)
Out[11]: array([3, 3, 2, 5, 2])
Здесь мы видим, что умножение смежности с весами одномерного вложения W просто сообщает, что представление каждого узла является суммой его соседей.
Это снова создает некоторые проблемы.
- Очень чувствительна к степени узла - скажем, у меня 20 друзей в Facebook, а у кого-то еще 5000 друзей. Выходной вектор будет иметь множество вариаций с точки зрения шкалы значений, которые он может принимать.
- При свертке изображения центральный пиксель является областью фокуса для ядра. Но для подключений может и не быть петли - скажем, в Facebook я не могу дружить со мной (за исключением поддельных учетных записей). Если мы используем смежность, узел (узел фокуса) будет равен нулю, а мой вклад в свертку будет равен NIL.
Есть и другие проблемы - мы рассмотрим их в следующих блогах. А пока давайте предположим, что представление матрицы смежности для свертки графа не совсем подходит.
Таким образом, альтернативой было бы использование «модифицированной» версии графа, например, нормализация графа для решения проблем масштабирования, добавление петель для включения в представление.
Точно так же, как все дороги ведут в Рим - поиск в Google и литературные обзоры на бумаге приводят нас к Лапласианской графике
Давайте рассмотрим граф G, матрицу смежности A, и пусть D будет диагональной матрицей степени G - сумма (A, по строкам / столбцам)
Есть несколько определений графа Лапласиана - и это лишь некоторые из них.
- L = D — A
- Симметричный нормализованный лапласиан L = I - (D ^ (- 1/2) * A * D ^ (- 1/2))
- Нормализованный лапласиан случайного блуждания L = I - D ^ (- 1/2) * A
Примечание. С этого момента, когда мы говорим о свертке графов - это лапласиан, а не матрица смежности.
Дилемма свертки
В этот момент вы, должно быть, задаетесь вопросом, а стоит ли нам вообще делать свертку? имеет ли это смысл?
Свертка хорошо определена для регулярного евклидова пространства признаков, где определены left, right, top, down, близость и локальность. Но для нерегулярного сеточного пространства, такого как графы, многообразия, которые не обязательно обладают этими «хорошими» свойствами, они создают проблему.
Тем не менее было бы хорошо иметь понятие свертки, которое работало бы в общих условиях. Вот тут-то и вступает в дело теория Фурье и спектральных графов (барабанная дробь, пожалуйста!)
Теорема свертки
Теорема свертки гласит: «Существует взаимно однозначное соответствие между сверткой в пространственной области и Адамаром (поэлементным) умножением в области Фурье и наоборот. наоборот »
Итак, чтобы определить свертку в нерегулярной области (такой как графы) - мы сопоставим проблему с областью Фурье, выполним простое поэлементное умножение в области Фурье и применим обратное преобразование Фурье, чтобы вернуться в пространственную область.
В следующем посте мы глубоко погрузимся в лапласиан, теорию спектральных графов и вывод базиса Фурье. А пока береги себя, оставайся дома - пока.
