Q: Почему свертка на графике?

О: Свертка — одна из основных операций[2] обработки сигналов. В SP люди разрабатывают фильтры в частотной области, чтобы отфильтровать низкочастотные/высокочастотные компоненты сигнала. Обратите внимание, что *свертка во временном пространстве эквивалентна умножению в частотной области*. Поэтому люди хотят определить такую ​​базовую операцию также и для графических сигналов.[1]

Q: Как определить свертки на графике?

A: Поскольку переход, например, x-$\delta$(x) не определен на графике, нам нужно определить свертку в частотной области. Для этого, прежде всего, необходимо провести мост между преобразованием Фурье в непрерывном поле и преобразованием Фурье в графическом поле. Это делается с учетом того, что первое преобразование Фурье определяется собственной функцией оператора Лапласа из этого поля. Унаследовав этот дух, мы можем определить Фурье в поле графа, используя собственные векторы оператора Лапласа в поле графа, т. е. лапласиан графа. [1] Но означает ли работа с матрицей Лапласа, что мы уже работаем с частотной областью? Ответ - нет. Только после преобразования сигнала графика с использованием собственных векторов лапласиана мы работаем в частотной области.

После преобразования собственные значения (упорядоченные по возрастанию) соответствуют частотам, а собственные векторы соответствуют основаниям (функциям синуса) в непрерывном поле.

Q:

В: Каков вклад [2]?

A: Они фиксируют фильтр как полиномиальный фильтр, так что по сравнению с уравнением. (2) в [2] он усекает рецептивное поле. После некоторых математических формул. (4)–(5) в [7, раздел 7] формула принимает вид

что дорого вычислять. Далее авторы используют полином Чебышева для аппроксимации (5). Заметим, что до Чебышева свертка была естественной, а после Чебышева свертка стала искусственной и приближенной. Так что подшитый после Чебышева рецептив не К, а примерно К. Но (может быть) не беда так как все выучено :). Наконец, слой свертки становится

Но это приближение хорошо, так как нам больше не нужно выполнять собственное разложение, которое требует O (N³), а просто нужно выполнять некоторые полиномиальные операции над матрицей Лапласа.

В: Каков вклад [3]?

В [2] авторы используют в экспериментах K=25. Авторы фиксируют аппроксимацию с помощью Чебышева на очень низком уровне, т. е. K=1. Затем использует стековые слои для увеличения рецептивного поля, при этом каждый слой является только линейным слоем. Затем автор добавляет трюк с перенормировкой, чтобы дать более аккуратную формулировку.

Таким образом, математически вклад кажется не очень значительным (может быть, поэтому он представлен в ICLR), но он настолько прост, что люди могут складывать его, чтобы сделать сеть глубже и кодировать ее очень легко. Таким образом, она становится одной из самых цитируемых статей в этом сообществе.

В: Какова связь с GraphSAGE[4] и GAT[5]?

Хотя математика делает очень красивые выводы между сверточной и спектральной теориями. Но упрощение в [2] и особенно в [3] уже компенсирует строгость удобством использования. Поэтому возьмем свертку с другой точки зрения: получение информации от соседей. Вместо этого люди разрабатывают пространственные методы, такие как GraphSAGE и GAT, чтобы просто получать информацию от соседей. Эти пространственные методы также напрямую применимы к ориентированным графам без необходимости использования методов мотивов [6], хотя они утверждают, что существует некоторая эквивалентность.

Еще много интересных дискуссий см. в [7].

[1] Шуман, Дэвид И. и др. «Новая область обработки сигналов на графиках: расширение анализа многомерных данных на сети и другие нерегулярные области». Журнал IEEE по обработке сигналов 30.3 (2013): 83–98.

[2] Дефферрар, Микаэль, Ксавье Брессон и Пьер Вандергейнст. «Сверточные нейронные сети на графах с быстрой локализованной спектральной фильтрацией». Достижения в области нейронных систем обработки информации. 2016.

[3] Кипф, Томас Н. и Макс Веллинг. «Полуконтролируемая классификация с использованием графовых сверточных сетей». препринт arXiv arXiv:1609.02907 (2016 г.).

[4] Гамильтон, Уилл, Житао Ин и Юре Лесковец. «Индуктивное репрезентативное обучение на больших графах». Достижения в области нейронных систем обработки информации. 2017.

[5] Величкович, Петар и др. «Нарисуйте сети внимания». препринт arXiv arXiv:1710.10903 (2017 г.).

[6] Монти, Федерико, Карл Отнесс и Майкл М. Бронштейн. «Motifnet: сверточная сеть графов на основе мотивов для ориентированных графов». Семинар IEEE по науке о данных (DSW), 2018 г.. ИИЭР, 2018.

[7] 如何理解 Graph Convolutional Network（GCN）？ — superbrother的回答 — 知乎 https://www.zhihu.com/question/54504471/answer/332657604