Глубокое обучение графов - часть 2

ЗАМЕТКИ ЛЕКЦИИ FAU ПО ГЛУБОКОМУ ОБУЧЕНИЮ

Глубокое обучение графов - часть 2

От спектральной к пространственной области

Это конспекты лекции FAU Глубокое обучение на YouTube. Это полный текст лекции и соответствующие слайды. Надеемся, вам понравится это не меньше, чем видео. Конечно, эта стенограмма была создана с помощью методов глубокого обучения в значительной степени автоматически, и были внесены лишь незначительные изменения вручную. "Попробуй сам!" Если вы заметили ошибки, сообщите нам об этом!

Навигация

Предыдущая лекция / Посмотрите это видео / Верхний уровень / Следующая лекция

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

Помните, что у нас был этот многочлен для определения свертки в спектральной области. Мы видели, что, вычисляя собственные векторы матрицы Лапласа, мы смогли найти подходящее преобразование Фурье, которое затем дало бы нам спектральное представление конфигурации графа. Затем мы могли бы выполнить свертку в спектральной области и преобразовать ее обратно. Это было довольно дорого, потому что нам нужно вычислить U. Для U, мы должны выполнить разложение по собственным значениям для всей этой симметричной матрицы. Кроме того, мы увидели, что мы не можем использовать приемы быстрого преобразования Фурье, потому что это не обязательно справедливо для нашего U.

Итак, как мы можем теперь выбрать наши k и θ, чтобы избавиться от U? Итак, если мы выберем k равным 1, θ нижний индекс 0 до 2θ и θ нижний индекс 1 до -θ, мы получим следующий многочлен. Итак, у нас все еще есть конфигурация, которую мы преобразовали x в пространство Фурье, умноженное на наш полином, выраженный здесь как матрица, умноженная на обратное преобразование Фурье. Теперь давайте посмотрим на конфигурацию шляпы G. G на самом деле можно выразить как 2, умноженные на θ, умноженные на Λ в степени 0. Помните, что Λ - диагональная матрица. Итак, мы возводим каждый элемент в степень 0. На самом деле это единичная матрица, и мы вычитаем θ, умноженное на Λ, в степени 1. Ну, на самом деле это просто Λ . Затем мы можем выразить таким образом нашу полную матрицу G hat. Конечно, затем мы можем втянуть нашу U с левой и правой стороны, что дает нам следующее выражение. Теперь мы используем то свойство, что θ на самом деле является скаляром. Итак, мы можем вытащить его вперед. Λ в степени 0 сокращается, потому что это, по сути, единичная матрица. Λ в правой части по-прежнему остается, но мы также можем вытащить θ. Что ж, транспозиция UU просто отменяется. Итак, это снова единичная матрица, и мы можем использовать наше определение симметричной версии лапласиана нашего графа. Вы можете видеть, что мы только что нашли это здесь, в нашем уравнении. Таким образом, мы также можем заменить его на этот. Теперь вы видите, что U внезапно исчез. Итак, мы можем снова вытащить θ, и все, что остается, это то, что у нас есть удвоенная единичная матрица за вычетом симметричной версии лапласиана графа. Если мы теперь подключим определение симметричной версии, связанной с исходной матрицей смежности и матрицей степеней, мы увидим, что мы все еще можем подключить это определение. Затем одна из матриц идентичности отменяется, и мы наконец получаем identity plus D в степени -0,5 умножить на A умножить на D в степени -0,5. Итак, помните, D - это диагональная матрица. Мы можем легко инвертировать элементы по диагонали, а также можем поэлементно извлекать квадратный корень. Так что это прекрасно. Таким образом, у нас вообще не будет U. Мы можем выразить свертку всего нашего графа таким прекрасным способом, используя матрицу Лапласа графа.

А теперь давайте еще немного проанализируем этот термин. Итак, мы можем видеть это тождество в левой части, мы видим, что можем сворачивать в спектральной области, и мы можем построить шляпу G как полином от лапласовских фильтров. Тогда мы можем видеть, что при определенном выборе k равно 1, θ нижний индекс 0 равен 2θ и θ нижний индекс 1 равен -θ. Тогда этот член внезапно зависит только от скалярного значения θ. С помощью всех этих уловок мы избавились от преобразования Фурье U транспонирования. Итак, мы внезапно можем выразить свертки графов таким упрощенным способом.

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

Что ж, теперь вопрос: «Действительно ли необходимо мотивировать свертку графа из спектральной области?» И ответ нет.". Таким образом, мы также можем мотивировать это пространственно.

Что ж, давайте посмотрим на следующую концепцию. Для математика граф - это многообразие, но дискретное. Мы можем дискретизировать многообразие и выполнить спектральную свертку, используя матрицу Лапласа. Итак, это привело нас к сверткам спектральных графов. Но как ученый-компьютерщик, вы можете интерпретировать граф как набор узлов и вершин, соединенных ребрами. Теперь нам нужно определить, как агрегировать информацию об одной вершине через ее соседей. Если мы это сделаем, мы получим свертку пространственного графа.

Ну как это делается? Один из подходов, показанный в [2], - это GraphSAGE. Здесь мы, по сути, определяем интересующую вершину и определяем, как соседи вносят вклад в интересующую вершину. Таким образом, технически мы реализуем это, используя вектор признаков в узле v и k-м слое. Это можно описать как индекс h k v. Итак, для нулевого слоя он содержит входные данные. Это просто исходная конфигурация вашего графика. Затем нам нужно иметь возможность агрегировать, чтобы вычислить следующий уровень. Это выполняется функцией пространственного агрегирования на предыдущем уровне. Следовательно, вы используете всех соседей и обычно определяете эту окрестность так, чтобы каждый узел, который подключен к рассматриваемому узлу, был включен в эту окрестность.

Итак, эта строка подводит нас к алгоритму GraphSAGE. Здесь вы начинаете с графика и входных функций. Затем вы выполняете следующий алгоритм: вы инициализируете в h 0, просто вводя конфигурацию графа. Затем вы перебираете слои. Вы перебираете узлы. Для каждого узла вы запускаете функцию агрегирования, которая каким-то образом вычисляет сводку по всем вашим соседям. Затем результатом является вектор определенной размерности, а затем вы берете агрегированный вектор и текущую конфигурацию вектора, объединяете их и умножаете на матрицу весов. Затем это проходит через нелинейность. Наконец, вы увеличиваете масштаб своих активаций. Затем это повторяется по всем слоям, и, наконец, вы получаете выходной z, который является результатом свертки вашего графа.

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

Вы уже видите, что существует множество агрегаторов. Это также является причиной того, что существует так много разных подходов к глубокому обучению графов. Вы можете разделить их на определенные виды, потому что есть спектральные, есть пространственные и есть повторяющиеся. Итак, это, по сути, ключ к решению проблемы сверточных нейронных сетей с графами. Итак, что мы на самом деле хотим делать? Что ж, вы можете взять один из этих алгоритмов и применить его к какой-нибудь сетке. Конечно, это также можно сделать на очень сложных сетках, и я приведу пару ссылок ниже, чтобы вы могли увидеть, какие приложения могут быть выполнены. Например, вы можете использовать эти методы для обработки информации о коронарных артериях.

Что ж, в следующий раз, когда мы будем заниматься глубоким обучением, останется всего пара тем. Одна вещь, которую я хочу показать вам, - это то, как вы можете встроить предыдущие знания в глубокие сети. Это также довольно хорошая идея, потому что она позволяет нам объединить многое из того, что мы знаем из теории и обработки сигналов, с нашими подходами к глубокому обучению. Конечно, у меня также есть несколько ссылок, и если у вас есть время, пожалуйста, прочтите их. Они гораздо более подробно развивают идеи, которые мы здесь представили. Есть также отсылки к изображениям, которые я помещу в описание этого видео. Итак, большое спасибо за внимание и до встречи на следующей лекции. Пока-пока!

Если вам понравился этот пост, вы можете найти больше эссе здесь, больше образовательных материалов по машинному обучению здесь или взглянуть на нашу Лекцию Глубокое обучение. Я также был бы признателен за подписку на YouTube, Twitter, Facebook или LinkedIn, если вы хотите получать информацию о новых эссе, видео и исследованиях в будущем. Эта статья выпущена под лицензией Creative Commons 4.0 Attribution License и может быть перепечатана и изменена при наличии ссылки. Если вас интересует создание стенограмм видеолекций, попробуйте Автоблог.

Спасибо

Большое спасибо за отличное вступление Майкла Бронштейна на MISS 2018! и особая благодарность Флориану Тамму за подготовку этого набора слайдов.

использованная литература

[1] Кипф, Томас Н. и Макс Веллинг. «Классификация с полууправлением со сверточными сетями на графах». Препринт arXiv arXiv: 1609.02907 (2016).
[2] Гамильтон, Уилл, Чжитао Инь и Юре Лесковец. «Обучение индуктивному представлению на больших графах». Достижения в области нейронных систем обработки информации. 2017.
[3] Вольтеринк, Елмер М., Тим Лейнер и Ивана Ишгум. «Графические сверточные сети для сегментации коронарных артерий в КТ-ангиографии сердца». Международный семинар по изучению графов в медицинской визуализации. Springer, Cham, 2019.
[4] Wu, Zonghan, et al. «Комплексный обзор графовых нейронных сетей». Препринт arXiv arXiv: 1901.00596 (2019).
[5] Бронштейн, Майкл и др. Лекция «Глубокое геометрическое обучение на графах и многообразиях» в SIAM Tutorial Portland (2018)

Ссылки на изображения

[a] https://de.serlo.org/mathe/funktionen/funktionsbegriff/funktionen-graphen/graph-funktion
[b] https://www.nwrfc.noaa.gov/snow/ plot_SWE.php? id = AFSW1
[c] https://tennisbeiolympia.wordpress.com/meilensteine/steffi-graf/
[d] https://www.pinterest.de / pin / 624381935818627852 /
[e] https://www.uihere.com/free-cliparts/the-pentagon-pentagram-symbol-regular-polygon-golden-five-pointed-star-2282605
[f] http://geometricdeeplearning.com/ (Глубокое геометрическое обучение на графах и многообразиях)
[g] https://i.stack.imgur.com/NU7y2.png
[h] https://de.wikipedia.org/wiki/Datei:Convolution_Animation_(Gaussian).gif
[i] https://www.researchgate.net/publication/306293638/ figure / fig1 / AS: 396934507450372 @ 1471647969381 / Example-of-centerline- extract-left-and-coronary-artery-tree-mesh-reconstruction.png
[j] https://www.eurorad.org /sites/default/files/styles/figure_image_teaser_large/public/figure_image/2018-08/0000015888/000006.jpg?itok=hwX1sbCO