Графические нейронные сети как PDE нейронной диффузии

Это сообщение в блоге написано в соавторстве с Беном Чемберленом и Джеймсом Роуботтомом и основано на нашей статье Б. Чемберлена, Дж. Роуботтома и др. GRAND: Graph Neural Diffusion (2021) ICML.

В марте 1701 года Философские труды Королевского общества опубликовали анонимную заметку на латыни под названием «Шкала градусов тепла» [1]. Хотя имя не было указано, не было секретом, что автором был Исаак Ньютон (четыре года спустя он стал «сэром Исааком»). В серии экспериментов Ньютон заметил, что

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

- современное изложение закона, носящего сегодня его имя [2]. Выраженный математически, закон охлаждения Ньютона приводит к уравнению диффузии тепла, уравнению в частных производных (PDE), которое в простейшей форме имеет вид

ẋ= aΔx.

Здесь x (u, t) обозначает температуру в момент времени t и точку u в некоторой области, lhs (временная производная ẋ) - это «скорость изменения температуры», а rhs (пространственная производная второго порядка или лапласиан Δ x ) выражает локальную разницу между температурой точки и окружающей среды, а a - коэффициент пропорциональности, известный как температуропроводность. Это УЧП является линейным, и его решение может быть дано в замкнутой форме как свертка начального распределения температуры с гауссовым ядром, зависящим от времени [3],

x (u, t) = x (u, 0) ﹡ exp (- | u | ² / 4 t).

В более общем плане необходимо учитывать различные свойства теплопроводности объекта, что приводит к PDE в форме

ẋ (u, t) = div (a (u, t) ∇ x (u, t))

кодирует более общий закон теплопередачи Фурье [4].

Диффузионные PDE возникают во многих физических процессах, включающих передачу «материала» (будь то энергия или материя) или, более абстрактно, информации. При обработке изображений можно использовать вышеупомянутую интерпретацию диффузии как линейную фильтрацию нижних частот для уменьшения шума изображения. Однако при удалении шума такой фильтр также нежелательно размывает переходы между областями разного цвета или яркости («края»). Влиятельная идея Пьетро Перона и Джитендры Малик [5] заключалась в том, чтобы рассмотреть коэффициент адаптивной диффузии, обратно зависимый от нормы градиента изображения | ∇ x |: таким образом, диффузия сильна в «плоском» области (где | ∇ x | ≈0) и слабые при наличии скачков яркости (где | ∇ x | большое). Результатом стал нелинейный фильтр, способный удалять шум с изображения, сохраняя при этом края.

Распространение Перона-Малика и подобные схемы создали целую область методов на основе PDE, которые также черпали вдохновение и методы из геометрии, вариационного исчисления и численного анализа [6]. Лично для меня работы Рона Киммела по числовой геометрии изображений [7] стали поводом влюбиться в дифференциальную геометрию и защитить докторскую диссертацию по этой теме. Вариационные методы и методы на основе PDE доминировали на этапе обработки изображений и компьютерного зрения в течение почти двадцати лет, уступив место глубокому обучению во втором десятилетии 2000-х годов [8].

В нашей недавней работе в Twitter [9] мы использовали ту же философию, чтобы по-новому взглянуть на графовые нейронные сети. GNN работают, обмениваясь информацией между соседними узлами в форме передачи сообщений, процесс, который концептуально эквивалентен распространению. В этом случае базовым пространством является граф, а распространение происходит по краям, где аналогией пространственных производных являются различия между элементами соседних узлов.

Формально обобщение диффузионных процессов на графы почти несложно: уравнение выглядит идентично,

Ẋ (t) = div (A (X (t)) ∇ X (t))

где X (t) теперь представляет собой матрицу узловых элементов размером n × d в момент времени t градиент представляет собой оператор, назначающий каждому ребру u ~ v разность соответствующих векторов признаков узла, (∇ X) ᵤᵥ = x ᵥ - x ᵤ где расхождение в узле u суммирует характеристики ребер, исходящих из него, (div (X)) ᵤ = ∑ ᵥ wᵤᵥ x ᵤᵥ [10]. Коэффициент диффузии представлен матричнозначной функцией вида A (X) = diag (a (x ᵤ, x ᵥ)), где, как и раньше, a - функция, определяющая силу распространения по краю u ~ v на основе сходства соответствующих функций x ᵤ и x ᵥ [11].

Уравнение диффузии графа удобно записать в виде матричного дифференциального уравнения вида

Ẋ(t) =(A(X(t))−I)X(t).

В большинстве случаев [12] это дифференциальное уравнение не имеет решения в замкнутой форме и требует численного решения. Существует множество численных методов решения нелинейных уравнений диффузии, различающихся в первую очередь выбором пространственной и временной дискретизации.

При простейшей дискретизации временная производная Ẋ заменяется прямой разницей во времени,

[X(k+1)−X(k)]/𝜏=[A(X(k))−I]X(k)

где k обозначает дискретный временной индекс (номер итерации), а 𝜏 - размер шага, такой что t = k 𝜏. Переписывая приведенную выше формулу как

X(k+1)=[(1−𝜏)I+𝜏A(X(k))]X(k)=Q(k)X(k)

мы получаем формулу явной или прямой схемы Эйлера, где следующая итерация X (k + 1) вычисляется из предыдущего X (k) путем применения линейного оператора Q (k) [ 13], начиная с некоторого X (0). Эта схема численно стабильна (в том смысле, что небольшое возмущение на входе X (0) приводит к небольшому возмущению на выходе X (k)) только тогда, когда шаг по времени достаточно мал, 𝜏 ‹1.

Использование обратной разницы во времени для дискретизации временной производной приводит к (полу) неявной схеме,

[(1+𝜏)I−𝜏A(X(k))]X(k+1)=B(k)X(k+1)=X(k)

назван таким образом, потому что выведение следующей итерации из предыдущей требует решения линейной системы, равной инверсии B (в большинстве случаев выполняется приблизительно, с помощью нескольких итераций линейного решателя). Эта схема безусловно устойчива, что означает, что мы можем использовать любой 𝜏 ›0, не беспокоясь о том, что итерации взорвутся.

Это простейшие в концептуальном плане методы дискретизации, которые не обязательно работают наилучшим образом на практике. В литературе по PDE обычно используются многошаговые схемы, такие как Рунге-Кутта [14], где последующая итерация вычисляется как линейная комбинация нескольких предыдущих. Как явный, так и неявный случаи можно сделать многоэтапными. Кроме того, размер шага можно сделать адаптивным в зависимости от ошибки аппроксимации [15].

Уравнения диффузии с параметрической функцией диффузии, оптимизированной для данной задачи, определяют широкое семейство архитектур, подобных графической нейронной сети, которые мы называем нейронной диффузией графа (или, несколько нескромно, GRAND для краткости). Результатом является решение X (T) уравнения диффузии в некоторый конечный момент времени T. Многие популярные архитектуры GNN могут быть формализованы как экземпляры GRAND - параметрических уравнений диффузии дискретизированных графов. В частности, явная схема, упомянутая выше, имеет форму сети внимания графа [16], где наша диффузность играет роль внимания.

Подавляющее большинство GNN используют явную одношаговую схему Эйлера, где дискретный временной индекс k соответствует сверточному или внимательному слою нейронной сети графа, а запуск распространения для нескольких итераций означает применение слой GNN несколько раз. В нашем формализме параметр времени диффузии t действует как непрерывный аналог слоев [17] - интерпретация, позволяющая нам использовать более эффективные и стабильные численные схемы, использующие адаптивные шаги во времени. В частности, GRAND позволяет решить широко известную проблему деградации производительности в глубоких GNN.

Неявные схемы позволяют использовать большие временные шаги и, следовательно, меньшее количество итераций (слоев) за счет вычислительной сложности итерации, которая требует обращения оператора диффузии. Оператор диффузии (матрица A в нашем уравнении) имеет ту же структуру, что и матрица смежности графа (1-шаговый фильтр), в то время как его обратный элемент обычно представляет собой плотную матрицу, которую можно интерпретировать как многопозиционный фильтр.

Поскольку эффективность обращения матрицы в решающей степени зависит от структуры матрицы, в некоторых ситуациях может быть полезно отделить граф, используемый для распространения, от входного графа. Такие методы, известные под общим названием перепрограммирование графа, стали популярным подходом к решению проблемы масштабируемости или информационных узких мест в GNN. Среда распространения предлагает принципиальный взгляд на перепрограммирование графа, рассматривая граф как пространственную дискретизацию некоторого непрерывного объекта (например, многообразия) [18], а некоторые дискретизации более выгодны в численном отношении.

Graph Neural Diffusion предоставляет принципиальную математическую основу для изучения многих популярных архитектур для глубокого обучения на графах, а также план для разработки новых. Этот образ мышления проливает новый свет на некоторые общие проблемы GNN, такие как чрезмерное сглаживание функций и сложность проектирования глубоких нейронных сетей, а также эвристические методы, такие как перепрограммирование графов. В более широком смысле, мы полагаем, что изучение связей между графом ML, дифференциальными уравнениями и геометрией и использование обширной литературы по этим темам приведет к новым интересным результатам в этой области.

[1] Аноним, Scala Graduum Caloris. Calorum Descriptiones et signa (1701) Philosophical Transactions 22 (270): 824–829 описал новую температурную шкалу и линейное устройство на масляной основе для ее измерения, получившее название Thermometrum . На протяжении всей статьи Ньютон использует слово калор (тепло, которое в современной физике имеет значение потока тепловой энергии и измеряется в Джоулях) вместо более подходящего термина температура ( средняя кинетическая энергия молекул, измеряемая в градусах Кельвина), которая еще не была придумана. С. Маруяма и С. Мория, Закон охлаждения Ньютона: продолжение и исследование (2021) International Journal of Heat and Mass Transfer 164 недавно точно воспроизвели экспериментальную работу Ньютона и утверждали, что множество факторов Автор не мог объяснить вероятные причины анонимной публикации статьи.

[2] Ясно, что Ньютон не понимал разницы между температурой и теплом, и поэтому современные формы закона охлаждения, основанные на концепции коэффициента теплопередачи, неправильно интерпретируются. Э. Ф. Адиутори, Истоки коэффициента теплопередачи (1990) Машиностроение, яростно утверждает, что Ньютону не следует приписывать открытие закона, носящего его имя, и что честь должна быть оказана Джозеф Блэк и Джозеф Фурье .

[3] В этом легко убедиться, расширив x в ряд Фурье и вставив его в обе части уравнения. Фактически, решение уравнений теплопроводности было одной из мотиваций для разработки этого аппарата Ж. Фурье, Аналитическая теория шлера (1824 г.), которая сегодня носит его имя. Тепловое ядро ​​в нашей формуле также должно иметь дополнительный зависящий от размера коэффициент нормализации, который мы опускали для простоты.

[4] Согласно закону Фурье, тепловой градиент ∇ x создает тепловой поток h = - a ∇ x, удовлетворяющий уравнению неразрывности ẋ = −div (h), которое кодирует предположение, что единственное изменение температура обусловлена ​​тепловым потоком (измеренным оператором дивергенции), т. е. тепло не создается и не разрушается. Этот принцип также известен в химии как закон Фика, в честь А. Фика, Über Diffusion (1855) Annalen der Physik 94. Интересно, что позиция Адольфа Флика сформулирована как Прозектором в Цюрихе - сомнительно полезным постом, который он занимал в первые три года своей карьеры, прежде чем стать профессором, сначала в Цюрихе, а затем в Вюрцбурге.

[5] П. Перона и Дж. Малик, Обнаружение масштабного пространства и краев с использованием анизотропной диффузии (1990), PAMI 12 (7): 629–639, является плодотворной статьей, предлагающей Адаптивная фильтрация изображений на основе PDE, ошибочно названная анизотропной. Строго говоря, уравнение нелинейной диффузии Перона-Малика ẋ = div (a (u) ∇ x), где a - константа коэффициента диффузии, зависящая от положения, является неоднородной (что означает, что коэффициент диффузии не является постоянной), но изотропной (не зависит от направления, поскольку a - это скаляр, просто масштабирующий градиент); истинное анизотропное уравнение диффузии имеет вид ẋ = div (A (u) ∇ x ), где A (u) - это позиционно-зависимая матрица 2 × 2 (тензор диффузии), которая масштабирует градиент по-разному в зависимости от направление.

[6] См. Книгу J. Weickert, Anisotropic Diffusion in Image Processing (1998) Teubner для очень педагогического введения в эти методы. Среди некоторых влиятельных фреймворков обработки изображений, которые следуют аналогичной парадигме Перона и Малика, можно выделить потоки Бельтрами, моделирующие изображения как встроенные многообразия, представленные Н. Соченом и др., Общая структура для зрения низкого уровня ( 1998) IEEE Trans. Обработка изображений 7 (3): 310–318; двусторонние фильтры К. Томази и Р. Мандучи, Двусторонняя фильтрация для серых и цветных изображений (1998) ICCV; и нелокальные средства А. Буадеса и др., Нелокальный алгоритм шумоподавления изображения (2005), ICCV. Различные версии этих методов были реализованы в оборудовании для обработки изображений; Я даже разработал ее сам в ранних версиях камеры Intel RealSense. Методы компьютерного зрения низкого уровня на основе PDE включают методы завершения изображения, такие как M. Bertalmio et al., Image inpainting (2000) Компьютерная графика и интерактивные методы и активные контуры методы сегментации, такие как В. Каселлес и др., Геодезические активные контуры (1997) IJCV 22 (1): 61–79 и Т.Ф. Чан и Л.А. Весе, Активные контуры без ребер (2001) IEEE Trans. Обработка изображений 10 (2): 266–277.

[7] Р. Киммел, Числовая геометрия изображений (2004), Спрингер.

[8] Связь между методами на основе PDE и вариационными методами проистекает из того факта, что многие PDE могут быть получены как условия оптимальности (известные как уравнения Эйлера-Лагранжа) некоторого функционала, например измерение качества полученного изображения. Уравнение однородной диффузии, например, является минимизирующим потоком (грубо говоря, непрерывная аналогия градиентного спуска в вариационных задачах) энергии Дирихле. Парадигма разработки функционала, получения PDE, минимизирующего его, и запуска его на изображении, концептуально очень привлекательна; однако большинство таких созданных вручную функционалов часто идеализируются и демонстрируют худшую производительность по сравнению с глубоким обучением, что является основной причиной упадка методов на основе PDE в последнее десятилетие. Однако некоторые идеи продолжают жить (часто без соответствующей атрибуции): например, концептуально можно рассматривать адаптивную диффузию в схеме Перона-Малика, которая агрегирует информацию в пикселях на основе их отношений, в качестве предшественника механизма внимания.

[9] Б. Чемберлен, Дж. Роуботтом и др., GRAND: Graph Neural Diffusion (2021) ICML. Чтобы быть исторически справедливым, различные разновидности уравнений диффузии графов использовались раньше во множестве приложений, и все они назывались hanc marginis exiguitas non caperet. В компьютерной графике уравнения теплопроводности на дискретных многообразиях (сетках) давно используются в качестве дескрипторов формы из-за связи между фундаментальным решением (тепловым ядром) уравнения диффузии на многообразии и его гауссовой кривизной. (см., например, мой старый Учебник по EUROGRAPHICS 2012, где я упоминаю многие применения диффузии в обработке геометрии и графике). При графической обработке сигналов фильтры нижних частот можно отождествить с процессами диффузии (например, в обзорной статье Л. Станковича Введение в обработку графических сигналов (2019) упоминается эта связь), и они использовались для восстановления графов из данных ( см., например, D. Thanou et al., Learning heat diffusion graphs (2017) IEEE Trans. Signal and Information Processing over Networks 3 (3): 484–499). Интерпретация классических фильтров изображений с точки зрения графиков, включая несколько обобщений, представлена ​​в P. Milanfar, A Tour of Modern Image Filtering (2013) IEEE Signal Processing Magazine 30 (1): 106–128. В машинном обучении класс методов множественного обучения (нелинейного уменьшения размерности), называемых диффузионными картами, представленный Р. Р. Койфманом и др., Геометрические диффузии как инструмент гармонического анализа и определения структуры данных: карты диффузии (2005) PNAS 102 (21): 7426–7431 реализует евклидово вложение метрики диффузии, связанной с распространением тепла между парой узлов в графе. Наконец, в литературе GNN уравнения диффузии упоминались уже в классической статье Ф. Скарселли и др. Модель графической нейронной сети (2009) IEEE Trans. Neural Networks 27 (8): 61–80, а также недавно опубликованные в M. Poli et al., Графические нейронные обыкновенные дифференциальные уравнения (2019) arXiv: 1911.07532, J. Zhuang, Обычные дифференциальные уравнения на графовые сети (2019) arXiv: 1911.07532, Ф. Гу и др., Неявные графовые нейронные сети (2020) NeurIPS и Л.-П. Xhonneux et al., Нейронные сети с непрерывным графом (2020) ICML.

[10] Мы используем стандартные обозначения: граф G имеет n узлов и m ребер, W - это n × n матрица смежности с wᵤᵥ = 1, если u ~ v и нулем иначе. Учитывая d -мерные узлы, расположенные в матрицу n × d X, градиент ∇ X можно представить в виде матрицы размером m × d. Аналогичным образом, для данной кромки имеется матрица Y размером m × d, дивергенция div (Y ) представляет собой матрицу размером n × d. Эти два оператора сопряжены относительно друг друга. соответствующие внутренние продукты ⟨∇ X, Y⟩ = ⟨X, div (Y)⟩. Мы слегка злоупотребляем обозначением, обозначающим посредством x ᵤ узловых характеристик (аналогично скалярным полям в непрерывном случае) и x ᵤᵥ краевые элементы (аналог векторных полей); различие ясно из контекста.

[11] Мы предполагаем, что A нормализовано, ∑ ᵥ aᵤᵥ = 1.

[12] Для константы A решение уравнения диффузии может быть записано в замкнутой форме как X (t) = exp ( t (A - I)) X (0) = exp (t Δ) X (0). Экспонента графа лапласиана Δ известна как тепловое ядро ​​ и может интерпретироваться как обобщенная (спектральная) свертка с фильтром нижних частот.

[13] Обратите внимание, что Q зависит от X (и, таким образом, изменяется на каждой итерации), но его применение к X является линейным и принимает форму матричного произведения. В этом есть точная аналогия с привкусом «внимания» GNN.

[14] Названо в честь К. Рунге, Über die numerische auflösung von Differentialgleichungen (1895) Mathematische Annalen 46 (2): 167–178 и W. Kutta, Beitrag zur naherungsweisen integration totaler Differentialgleichungen (1901) Z. Математика. Физ.. 46: 435–453, метод Рунге-Кутты на самом деле не единственный метод, а класс числовых схем. В частности, в нашей статье мы использовали популярную схему Дорман-Принс.

[15] Обычно ошибка аппроксимации вычисляется как разница между двумя последовательными порядками аппроксимации.

[16] П. Величкович и др., Graph Attention Networks (2018) ICLR. В частности, мы предполагаем отсутствие нелинейности между слоями и параметров общего внимания между слоями (соответствующих не зависящему от времени коэффициенту диффузии). Последнее является большим преимуществом: в наших экспериментах мы получаем результаты, в большинстве случаев превосходящие результаты GAT, при использовании до 20 раз меньшего количества параметров.

[17] Нейронные ОДУ, или интерпретация остаточных нейронных сетей как дискретизация Эйлера обыкновенного дифференциального уравнения, была предложена несколькими группами, в том числе Э. Хабером и Л. Рутотто, Стабильные архитектуры для глубоких нейронных сетей (2017) Обратные задачи 34 (1), Y. Lu et al., За пределами нейронных сетей конечного уровня: мосты между глубокими архитектурами и численными дифференциальными уравнениями (2018) ICML, и, возможно, самый известный из них, Р. Чен и др., Нейронные обыкновенные дифференциальные уравнения (2019) NeurIPS. Наш подход можно рассматривать как Нейронные PDE.

[18] Это определенно верно для безмасштабных графов, таких как социальные сети, которые могут быть реализованы в пространствах с гиперболической геометрией. Геометрическая интерпретация графов как непрерывных пространств является предметом области сетевой геометрии, см., Например, М. Богуна и др., Геометрия сети (2021) Nature Reviews Physics 3: 114–135. Интерпретация графиков как выборки некоторого пространства была центральным механизмом для доказательства обобщения фильтров спектральных графов, например. в R. Levie et al., Переносимость сверточных нейронных сетей со спектральным графом (2019) arXiv: 1907.12972.

Мы благодарны Нильсу Хаммерле за вычитку этого сообщения и Пейману Миланфару за то, что он указал на интерпретацию фильтров изображений с точки зрения графиков. Дополнительные статьи о глубоком обучении на графиках можно найти в других публикациях на Medium или подписаться на меня в Twitter.